网站收录提交入口,设计图网址,外贸建个网站多少钱,关于vi设计的网站文章目录 前言运行队列 runqueue优先级活动队列过期队列活跃队列 VS 过期队列active指针和expired指针O(1)调度算法 前言 在前面学习并认识了进程之后#xff0c;我们会发出一个疑问#xff1a;Linux内核是如何调度进程的呢#xff1f; 接下来我们就以Linux2.6内核为例深入探… 文章目录 前言运行队列 runqueue优先级活动队列过期队列活跃队列 VS 过期队列active指针和expired指针O(1)调度算法 前言 在前面学习并认识了进程之后我们会发出一个疑问Linux内核是如何调度进程的呢 接下来我们就以Linux2.6内核为例深入探讨这个问题。 运行队列 runqueue 下图是Linux2.6内核中运行队列的数据结构。 一个CPU拥有一个runqueue struct runqueue。如果有多个CPU就要考虑进程个数的负载均衡问题。我们现在谈论的OS都是分时操作系统调度时强调的是公平。 优先级 queue下标说明 普通优先级100 ~ 139。实时优先级0 ~ 99。 我们进程的都是普通的优先级我们知道 nice 值的取值范围是 -20 ~ 19共40个级别依次对应 queue 当中普通优先级的下标100~139。 注意 实时优先级对应实时进程实时进程是指先将一个进程执行完毕再执行下一个进程现在基本不存在这种机器了所以对于 queue 当中下标为 0 ~ 99 的元素我们不关心。 活动队列 时间片还没有结束的所有进程都按照优先级放在活动队列当中其中 nr_active 代表总共有多少个运行状态的进程而 queue[140] 数组当中的一个元素就是一个进程队列相同优先级的进程按照FIFO规则进程排队调度。 调度过程如下 从0下标开始遍历queue[140]。找到第一个非空队列该队列必定为优先级最高的队列。拿到选中队列的第一个进程开始运行调度完成。接着拿到选中队列的第二个进程进行调度直到选中进程队列当中的所有进程都被调度。继续向后遍历queue[140]寻找下一个非空队列。 注bitmap[5]queue数组当中一共有140个元素即140个优先级一共140个进程队列为了提高查找非空队列的效率就可以用5 × 32个比特位表示队列是否为空这样一来便可以大大提高查找效率。 总结 在系统当中查找一个最合适调度的进程的时间复杂度是一个常数不会随着进程增多而导致时间成本增加我们称之为进程调度的O(1)算法。 过期队列 过期队列和活动队列的结构相同。过期队列上放置的进程都是时间片耗尽的进程。当活动队列上的进程被处理完毕之后对过期队列的进程进行时间片重新计算。 活跃队列 VS 过期队列 CPU调度时需要把进程拿走的同时把正在执行的进程剥离下来被放入运行队列。运行队列中存在两套相同的结构体类型。拿走的队列活跃队列放入队列过期队列。活跃队列表示当前CPU正在执行的运行队列而正在执行的运行队列是不可以增加新的进程的 。与此同时操作系统设置了一个和活跃队列相同属性的过期队列当活跃队列正在执行时如果有进程需要添加进运行队列那么就会添加至过期队列当中也就是说活跃队列的进程一直在减少而过期队列中的进程一直在增多。活跃队列是只出不进。过期队列是只进不出。两个队列是被存放在结构体数组中的结构体数组存放在运行队列中且运行队列中存在 active 指针和 expired 指针分别指向活跃队列和过期队列。 active指针和expired指针 active指针永远指向活动队列。expired指针永远指向过期队列。 由于活动队列上时间片未到期的进程会越来越少而过期队列上的进程数量会越来越多新创建的进程都会被放到过期队列上那么总会出现活动队列上的全部进程的时间片都到期的情况这时将 active 指针和 expired 指针的内容交换就相当于让过期队列变成活动队列活动队列变成过期队列就相当于又具有了一批新的活动进程如此循环进行即可。 O(1)调度算法 有了对上述概念的认识我们就能很好的理解内核调度进程队列的算法了 CPU正在执行访问的队列是 active 指向的 A 活跃队列只出不进。另外一个被 expired 指向的结构相同的过期队列 B只进不出。新创建的进程的 PCB 只链接到过期队列 B。CPU 调度的活跃队列 A 中的进程 PCB 被 CPU 调度时间片到了之后也链接到过期队列 B。最后 A 队列中的进程被 CPU 全部调度完B 队列则链接了在 A 队列调度期间到来的新进程或是时间片到了的老进程。接着将两个 active 指针和 expired 指针交换 swap(activeexpired)交换的是指针内容。重复上诉过程。 综上在系统当中查找一个最合适调度的进程的时间复杂度是一个常数不随着进程增多而导致时间成本增加我们称之为进程调度O(1)算法
