LinuxO(1)调度算法

概念

在Linux中，O(1)调度算法是一种进程调度算法。O(1)表示算法的时间复杂度是常数级别的，与系统中的进程数量无关。

运行队列结构

• 他采用了两个运行队列，一个活动队列和一个过期队列。活动队列中的进程是有资格获取CPU时间片的进程，过期队列中的进程是已经用完时间片的进程。而操作系统始终只会调度活动队列的进程。
• 多个队列又被分为多个优先级数组，例如从0~139。优先级不同，Linux下版本可能有差异，数值越小优先级越高。
• 利用哈系统指针数组140个元素，类型为struct task_struct*，前100个下标不用考虑是为实时进程进行使用的。剩下的40个元素是对于分时进程进行考虑。对于剩下的40个元素利用哈系统将进程优先级相同的。串在一起。通过优先级挂队里相同优先级的进程会被链接在一起。
• 也可以理解为在一个CPU里面有一个运行队列，一个运行队列里面有两张表，一个是活动队列和一个过期队列。

活动队列

• 时间片还没有结束的所有进程都按照优先级放在该队列。
• nr_active：总共有多少运行状态的进程
• queue[140]：一个元素就是一个进程队列相同优先级的进程按照fifo规则进行排队调度，所以数组下标就是优先级。
• 在该结构中选择一个最合适的进程过程是如何？
• 从0号下标开始，遍历queue[140]
• 找到第一个非空队列，该队列必定为优先级最高的队列。
• 拿到选中队列的第一个进程开始运行，调度完成。
• 遍历queue[140]时间复杂度是常数，但还是太低效了。
• bitmap[5]：一共是140个优先级，一共140个进程队列。为了提高查找非空队列的效率，就可以用五个。32个比特位表示队列是否为空，这样便可以大大提高查找效率。

过期队列

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

active指针和expired指针

• active永远指向活动队列。
• expired永远指向国旗队列。
• 活动队列上的进程越来越少，过期队列上的进程越来越多，因为进程时间片到期时一直都存在的。在最终只要能够交换活动队列指针和过期队列指针的内容，就相当于又具有一批新的活动进程。
• 进程有三种情况，运行退出。不退出，但时间偏到了。有新的进程产生了。

调度过程

初始状态

系统中有活动队列和过期队列，活动队列包含有资格获取CPU时间片的进程，这些进程按照优先级分布在不同的优先级数组中。优先级从0~139。

选择进程运行

当进行进程调度时，调度器首先查看活动队列中优先级最高数组，在这个优先级最高的数组中选择一个进程来运行。这个选择过程比较简单快速，因为它不需要遍历整个系统的所有行程，只需在特定的优先级数组里选择。

时间片用完

当活动队列中的进程用完自己的时间片之后，他不会立刻回到活动队列的头部重新竞争CPU。因为操作系统采用分时操作系统。分时操作系统是要保持绝对的公平，进程调度绝对公平。而是被移动到过期队列中相应的优先级数组里。

队列交换

当活动队列中所有的进程都玩都用完时间片，也就是活动队列中没有可运行的进程时，活动队列和过期队列进行交换。此时原来的过期队列变为活动队列，而原来的活动队列变为过期队列，新的活动队列中的进程又可以开始竞争CPU资源。这个交换操作的时间复杂度也是o1。

优点

由于采用这种结构，查到下一个要运行的进程的时间复杂度为o一，无论系统中有多少个进程都能快速的做出调度决策，提高了系统的响应速度和整体的性能。并且保证了分时操作系统调度进程绝对的公平。

应用场景

多用户交互环境

在桌面Linux系统中，当多个用户同时登录并且运行多个程序时，如打开多个办公软件，浏览器标签等oe1调度算法能够快速的在这些进程中进行切换，保证每个用户操作都能得到及时响应，提供流畅的交互体验。

服务器环境

由于外部服务器就像运行或ngnx服务器可能同时处理多个客户端请求，oe调度算法可以高效的调度处理这些请求的进程。不管同时存在的请求数量多少都能快速的分配cpu响应性能。

多任务处理

在Linux系统执行多任务时，例如一边进行文件下载，一边编译程序，一边运行后台服务等情况。O1调度算法能够合理分配CPU时间片给各个任务。对应的进程使这些任务都能有条不紊的进行。