Linux2.6内核进程调度队列 —— 了解

一、Linux2.6内核进程调度队列 —— 了解

不是本文的重点，所以了解一下即可。

💦 Linux2.6内核中进程队列的数据结构

💦 一个CPU拥有一个runqueue

• 如果有多个 CPU 就要考虑进程个数的负载均衡问题。

💦 优先级

• 普通优先级：100～139 (我们都是普通的优先级，想想 nice 值的取值范围，可与之对应 !)。
• 实时优先级：0～99 (不关心)

💦 活动队列

• 时间片还没有结束的所有进程都按照优先级放在该队列。

• nr_active：总共有多少个运行状态的进程。

• queue[140]：一个元素就是一个进程队列，相同优先级的进程按照 FIFO 规则进行排队调度，所以，数组下标就是优先级。

• 从该结构中，选择一个最合适的进程，过程是怎么的呢 ？

  1、从 0 下标注开始遍历 queue[140]。
  2、找到第一个非空队列，该队列必定为优先级最高的队列。
  3、拿到选中队列的第一个进程，开始运行，调度完成。
  4、遍历 queue[140] 时间复杂度是常数，但还是太低效了。

• bitmap[5]：一共 140 个优先级，一共 140 个进程队列，为了提高查找非空队列的效率，就可以用 5*32 个比特位表示队列是否为空，这样，便可以大大提高查找效率。

💦 过期队列

• 过期队列和活动队列结构一模一样。
• 过期队列上放置的进程，都是时间片耗尽的进程。
• 当活动队列上的进程都被处理完毕之后，对过期队列的进程进行时间片重新计算。

💦 active指针 and expired指针

• active 指针永远指向活动队列。
• expired 指针永远指向过期队列。
• 可是活动队列上的进程会越来越少，过期队列上的进程会越来越多，因为进程时间片到期时一直都会存在的。
• 没关系，在合适的时候，只要能够交换 active 指针和 expired 指针的内容，就相当于有具有了一批新的活动进程。

💦 总结

• 在系统当中查找一个最合适调度的进程的时间复杂度是一个常数，不随着进程增多而导致时间成本增加，我们称之为进程调度 O(1) 算法。

相关阅读