【进程调度】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)算法

相关文章
|
1天前
|
Linux
Linux如何创建进程扇和进程链
Linux如何创建进程扇和进程链
|
4天前
|
Linux Shell C语言
Linux进程控制——Linux进程程序替换
Linux进程控制——Linux进程程序替换
12 2
|
4天前
|
Linux 调度
Linux进程控制——Linux进程等待
Linux进程控制——Linux进程等待
11 2
|
4天前
|
存储 缓存 Linux
Linux进程控制——Linux进程终止
Linux进程控制——Linux进程终止
13 2
|
4天前
|
安全 Linux 编译器
Linux进程——进程地址空间
Linux进程——进程地址空间
14 2
|
4天前
|
Linux Shell 编译器
Linux进程——Linux环境变量
Linux进程——Linux环境变量
8 3
|
4天前
|
Linux 调度
Linux进程——Linux进程间切换与命令行参数
Linux进程——Linux进程间切换与命令行参数
8 1
|
4天前
|
Linux 调度
Linux进程——Linux进程与进程优先级
Linux进程——Linux进程与进程优先级
7 1
|
4天前
|
Linux Shell 调度
Linux进程——Linux下常见的进程状态
Linux进程——Linux下常见的进程状态
15 4
|
4天前
|
算法 Linux 调度
Linux进程——进程的创建(fork的原理)
Linux进程——进程的创建(fork的原理)
9 2