初识Linux · O(1)调度算法

_lazy. 2024-10-03 09:37:01 阅读 86

目录

前言:

O(1)调度算法


前言:

在初识进程的那一块,我们已经知道了进程并不是一直占用cpu资源的,而是存在时间片的概念,即,每个进程都有一定的时间来执行该进程,时间一到,该进程就应该自动到后面进行排队,同时,进程的数据也应该被不同的寄存器记录下来,方便下一次执行该进程的时候,可以接着上次结果运行。

那么问题就来了,进程被调度的时候,是如何调度的,如果调度的过程中,有别的进程来排队,那么会不会导致随着进程数量的增多,导致进程排队的时间越来越多,最后甚至运行不了?

并且,优先级一共就那么几个优先级,实际运行的时候,进程可不止有那么多个,所以优先级并不能真正代替进程是否先运行,并且nice值也是影响进程的运行,这一切,构成了一个新的专题,即Linux中的O(1)调度算法。


O(1)调度算法

正式开始之前,我们不妨整理一下,有多少个问题:

1. 随着进程的增多,进程排队的时间是否会越来越多,甚至导致运行不了?

2. 优先级一定是越小就一定会先运行吗?

3. nice值影响优先级的区间为什么只有40个值

这么多问题的切入点只有一个,即Linux源码中的一个结构:runqueue

这是解决问题的关键。

我们的重点不在于负载因子上,我们今天着重介绍arrary[0],array[1]即可。

我们输入指令top可以看到对应的优先级:

顺便复习一下,进程的状态我们可以使用ps来查看:

while :; do ps -xaj | head -1 && ps -xaj | grep main | grep -v grep; sleep 1;done

优先级

我们通过指令ps -al可以看到,这里的优先级默认的都是80,修改的范围都是在[-20,19]里面,为什么只有40个数字呢?我们后面再谈。

根据上图,array[0]中有一个140个空间的queue,还有一个bitmap[5],因为这两个变量的存在,所以Linux的调度是分时操作的,保证了一定的公平性,还有一种操作是实时操作,实时操作的例子比如出租车,有人就立马就跑,不存在说排队之类的。

这个queue中都是PCB,也就是进程的控制块,OS在里面查找进程的时候,是不是需要一个一个的遍历?OS也不是神人,不可能就是说一下找到。那么这样的话,势必会导致效率的降低。

所以存在另一种变量,即bitmap,相信c++学习阶段有了解的人肯定知道这个数组就是位图。

这里简单描述一下位图,即将字节层面的操作转到了bit层面,如果OS需要确定队列中是否有进程,它不需要一个一个的去遍历较大的数组,只需要遍历bitmap即可,因为每个位对应的就是每个数组中的空间.

因为默认优先级是80,修改之后的范围是60到99,在runqueue中的队列,有140个空间,前0 - 99个空间我们不考虑,我们考虑后面100 - 139,这里面其实和地址空间一样,存在某种映射关系:

存在的映射关系大概就是这样,100 -  139分别对应的就是60 - 99,这恰好就是我们能够修改的范围。

此时对于OS来说,插入进程和干掉进程只需要遍历bitmap,5个空间,几乎就是不需要时间了,代表的是32 * 5,160个空间,甚至还多出来了些。

那么为什么:

存在两个相同的队列呢?

一个是活跃进程,一个是过期进程,过期进程是好理解的,即时间片到了的进程,就会被安排在过期进程,活跃进程也就是时间片还没到,或是第一次都没有运行的进程。

同时,还存在两个指针,active和expired指针,active指针永远指向活跃进程,expired永远指向过期进程,对于不同的队列,活跃进程可以只出不进,过期进程只进不出,当某个队列中一个进程都没有了,比如active中没有进程了,那么active和expired交换队列,此时acitve指向的即活跃,即原来过期的进程变成了活跃进程,活跃的进程变成了过期的进程,这个过程,就被成为O(1)调度算法。

那么回归问题,优先级一样的问题?如果优先级是一样的,OS也是会根据不同的点在判断,但是优先级一样的,都会进到queue中的某个空间的后面,即用task_queue进行链接。所以优先级一样,如何调度也是OS的事,但是我们能确定的事,都会连接到task_queue的指针后面,以链表的形式存在。


感谢阅读!



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。