本文首发于稀土掘金。该平台的作者 逐光而行 也是本人。

关于调度

什么是调度

如果只有一个CPU可用，必须选择下一个要运行的进程。在操作系统中，完成该部分工作的是调度程序，使用的算法叫调度算法。

关于调度的一些背景

• 对于网络服务器而言，多个进程经常竞争CPU。
• “资源充足”的论据在移动设备上也不成立。
• 进程分为计算密集型和I/O密集型两种；前者花较长时间在CPU集中使用上，后者I/O等待的频率高。

随着CPU速度增快，更多进程倾向I/O密集型（因为CPU的速度及其演进速度都比磁盘快，计算本身耗时短了）

调度时机

• 一个进程退出时，必须决定谁来接班（若找不到，会允许系统提供的空闲进程）
• 进程阻塞时，必须选另一个救急
• I/O发生中断时，决定恢复被中断的进程，还是选择别的进程

调度算法目标

• 公平--->系统策略强制执行
• 保持系统整体的高效、持续运转（尽可能使所有部分都保持忙碌）

调度算法分类

批处理

批处理作业的三大指标

• 吞吐量(throughout)
• 周转时间(turnaround time)
• CPU利用率

算法

先来先服务（队列）

最短作业优先

最短剩余时间优先

交互式

重要指标

最小响应时间，均衡性

算法（前两种算法和中断的有点像）

轮转调度

维护一张可运行进程的列表，当前进程被运行后，就移到列表末尾。

优先级调度

多级队列

最短进程优先

不过要解决一个问题：如何找出最短的进程

• 一种方案：根据进程过去的行为进行推测。

保证调度

• 向用户作出明确的性能保证，然后实现它。
• 若有n个用户登录，则每个用户将获得CPU处理能力的1/n。
• 为实现所做的保证，系统必须跟踪各个进程自创建以来使用了多少CPU时间。

彩票调度

• 应用例子：视频流，可将不同帧速率制成彩票，进程会自动按照大致正确的比例划分CPU的使用。

公平分享调度

（取决于如何定义“公平”，比如可定义为每个用户都能用到）

实时

基本要求

一定程度上必须满足deadline

分类：硬实时和软实时

这个嵌入式系统笔记那里讲得很详细，此处不再赘述，可分别以军工系统和DVD作为理解例子。

将调度机制与调度策略分离

使调度机制位于内核，调度策略由用户进程决定。

• 适当放权，可以为主进程控制并掌握许多子进程动向等情况提供最优解，是上述提到的算法做不到的。

经典IPC问题

• 哲学家就餐问题（互斥访问有限资源的竞争问题）
• 读-写者问题（数据库访问）

参考书籍

《现代操作系统》 Andrew S.Tanenbaum,Herbert Bos著，陈向群，马洪兵等译