【进程调度】Linux内核的进程调度队列--runqueue

简介: 【进程调度】Linux内核的进程调度队列--runqueue

前言

在了解进程的基本概念后,我们已经清楚一个进程到底是什么了,那么一个进程又是如何被调度的呢?这个过程发生了神呢

runqueuer

runqueue运行队列是Linux系统内核中非常重要的一个组成部分。它是用于管理所有的进程和线程的队列,使它们能够按照特定的优先级被调度执行。

上图是Linux2.6内核中进程队列的数据结构

其中runqueue维护了一个活动队列,和一个过期队列。

活动队列


活动队列维护了正在运行时间片还没有结束的进程,按照优先级放在该队列。

nr_activeb表示总共有多少个运行状态的进程

queue[140]:其中每一个元素都是一个task_struct指针,指向一个队列的首元素。每一个队列都表示一个优先级,queue下标表示的就是优先级。比如一个正在运行的进程的优先级为1,那么这个进程就在队列queue[1]中。

当我们需要在这个queue[]队列数组中找一个进程被CPU执行时。操作系统会在这个数组中从头开始,也就是从优先级最高的队列开始,找到第一个非空的队列。再在这个队列中运行第一个进程,于是这样就完成了一次进程调度。

那系统是如何找到这个“第一个非空进程队列”的呢?

于是我们就可以借用long bitmap[5]这个数组了。

把bitmap当成一个01序列的位图,一共有32*5=160个比特位。第n位比特位为1,表示queue第n个元素指向的队列非空。

于是,我们可以遍历整个bitmap数组,如果bitmap[0]为0,则意味着前32个比特位都是0,也意味着queue前32个元素都是空。直到遇到bitmap[i]>0,再去遍历这个bitmap[i]的二进制位,遇到1就结束。

相比于遍历queue去找到第一个非空进程队列,这样用位图的方式,遍历一次就能筛选32个比特位,也就是32个为空的队列,无疑大大提升了效率。

过期队列

过期队列和活动队列结构一模一样 ,只不过过期队列上的queue里的指针指向的是时间片耗尽的进程。当活动队列上的进程时间片耗尽了就会调出到过期队列。

值得注意的是,当活动队列的所有进程都被处理完的时候,会重新分配给过期队列中的进程时间片。

active指针和expired指针

在runqueue里,active指针永远指向活动队列,相反,expired指针永远指向过期队列。

由于活动队列中的进程只出不进,越来越少。过期队列中的进程,只进不出,越来越多。

当活动队列中的进程都被调度完了之后,一部分进程已经完全运行结束,一部分进程则是回到过期队列等待下次被调度。此时交换active指针和expired指针的内容,原来的过期队列被赋予“生命”成为新的活动队列,继续被调度。原来的活动队列则成为过期队列,接收那些还想被调度但是没有CPU时间片的进程,并等待下一次成为活动队列。

总结:

至此我们清楚了系统是如何查找一个合适的进程被CPU调度的,这种调度算法的时间复杂度是O(1)的,不随着进程的增多而导致时间成本的增加,我们将其称之为进程调度O(1)算法。

相关文章
|
安全 网络协议 Linux
深入理解Linux内核模块:加载机制、参数传递与实战开发
本文深入解析了Linux内核模块的加载机制、参数传递方式及实战开发技巧。内容涵盖模块基础概念、加载与卸载流程、生命周期管理、参数配置方法,并通过“Hello World”模块和字符设备驱动实例,带领读者逐步掌握模块开发技能。同时,介绍了调试手段、常见问题排查、开发规范及高级特性,如内核线程、模块间通信与性能优化策略。适合希望深入理解Linux内核机制、提升系统编程能力的技术人员阅读与实践。
1244 1
|
Ubuntu Linux
Ubuntu 23.04 用上 Linux 6.2 内核,预计下放到 22.04 LTS 版本
Linux 6.2 带来了多项内容更新,修复了 AMD 锐龙处理器设备在启用 fTPM 后的运行卡顿问题,还增强了文件系统。
|
Ubuntu Linux
Ubuntu 23.10 现在由Linux内核6.3提供支持
如果你想在你的个人电脑上测试一下Ubuntu 23.10的最新开发快照,你可以从官方下载服务器下载最新的每日构建ISO。然而,请记住,这是一个预发布版本,所以不要在生产机器上使用或安装它。
|
监控 Ubuntu Linux
什么Linux,Linux内核及Linux操作系统
上面只是简单的介绍了一下Linux操作系统的几个核心组件,其实Linux的整体架构要复杂的多。单纯从Linux内核的角度,它要管理CPU、内存、网卡、硬盘和输入输出等设备,因此内核本身分为进程调度,内存管理,虚拟文件系统,网络接口等4个核心子系统。
1285 0
|
Web App开发 缓存 Rust
|
Ubuntu 安全 Linux
Ubuntu 发行版更新 Linux 内核,修复 17 个安全漏洞
本地攻击者可以利用上述漏洞,攻击 Ubuntu 22.10、Ubuntu 22.04、Ubuntu 20.04 LTS 发行版,导致拒绝服务(系统崩溃)或执行任意代码。
|
存储 Linux API
【Linux进程概念】—— 操作系统中的“生命体”,计算机里的“多线程”
在计算机系统的底层架构中,操作系统肩负着资源管理与任务调度的重任。当我们启动各类应用程序时,其背后复杂的运作机制便悄然展开。程序,作为静态的指令集合,如何在系统中实现动态执行?本文带你一探究竟!
【Linux进程概念】—— 操作系统中的“生命体”,计算机里的“多线程”
|
Unix Linux
对于Linux的进程概念以及进程状态的理解和解析
现在,我们已经了解了Linux进程的基础知识和进程状态的理解了。这就像我们理解了城市中行人的行走和行为模式!希望这个形象的例子能帮助我们更好地理解这个重要的概念,并在实际应用中发挥作用。
385 20
|
存储 缓存 Linux
【Linux】进程概念(冯诺依曼体系结构、操作系统、进程)-- 详解
【Linux】进程概念(冯诺依曼体系结构、操作系统、进程)-- 详解

热门文章

最新文章