仅用于站内搜索，没有排版格式，具体信息请跳转上方微信公众号内链接
作为1960年代初期IBM计算机中心的系统工程师，你每天都在面对一个令人头疼的问题：如何让价值数百万美元的大型机发挥最大效率。当时，你刚刚实现了多进程系统，让多个程序可以同时加载到内存中，但很快就发现了问题。
你清晰地记得实现多进程后的那个早晨，走进机房时，你看到三位用户正在争论谁的程序应该先运行。
第一位是财务部门的主管，他需要在上午会议前完成月度报表；第二位是研发部门的工程师，他的模拟程序已经排队等待了整个周末；第三位是物理学教授Sheldon，他需要处理一批实验数据。
后来这种场景几乎每天都在上演，你清楚地知道自己面临的核心问题是什么，这本质是进程调度问题：
如何决定哪个进程先运行？是按照提交顺序吗？那紧急任务怎么办？是按照任务重要性吗？那谁来判断重要性？
一个进程运行多长时间才算合理？
如何保证系统资源被公平高效地利用？显然CPU密集型任务和I/O密集型任务需要不同的处理策略
你们团队的大聪明提出了一个非常直观的方法：先来先服务（First-Come,First-Served，FCFS），也就是排队。
这个想法非常简单：谁先提交任务，谁就先获得CPU时间。
很好，反正也没其它思路，先实现起来再说。很快，你实现了这种进程调度方法。
这个简单的调度器确实解决了”谁先运行”的问题，但很快你就发现了它的严重缺陷。
有一天，一个大型批处理作业占用了CPU整整8小时，而其他几十个只需要几分钟的小任务却不得不等待。用户们开始抱怨系统反应迟钝，尤其是那些需要交互的用户更是不满。
你开始意识到，先来先服务虽然公平，但并不高效。它无法区分任务的紧急程度，也无法处理长短任务混合的情况。
你需要一个更智能的方案。
这时你们团队的大聪明一拍大腿，这还不简单：让进程自己让出CPU，占用CPU时间太长的进程要主动释放CPU好让其它进程运行，貌似很合理，这就是所谓的”协作式多任务处理”（CooperativeMultitasking）。
为了让进程主动释放CPU，你专门设计了一个新的系统调用yield()，允许进程在适当的时候主动让出CPU。
这个方案在一定程度上改善了系统的响应性。你们开始鼓励程序员在他们的代码中定期调用yield()
大家在写代码占用CPU时一定要温良恭谦让，要自觉维护好CPU使用的公众秩序，共同营造和谐的CPU使用氛围，特别是那些要长时间运行的进程。
然而，这个方案很快就暴露出了致命的缺陷。
大聪明是聪明的，但大聪明没有考虑到的一点是人都是自私的，有的程序员故意不定期调用yield释放CPU给其它人的进程，而且还有很多菜鸟程序员根本就忘记了调用yield()，或者因为bug等原因代码中出现了死循环，结果整个系统被这个失控的进程占据，其他所有进程都无法获得CPU时间。你们不得不强制重启系统，导致其他用户的工作全部丢失。
这个事件让你认识到：不能把系统的稳定性完全寄托在用户态那帮程序员的自觉性上。
需要一个能够强制进程让出CPU的机制。
苦思冥想你找不到解决方案，晚上睡觉做梦都在思考，早上的闹钟打断了你梦中思路，气愤你一把抓来闹钟扔到了一旁，烦人的闹钟，总是每天准时打断你的回笼觉。
等等，闹钟？定时？打断？
你一拍大腿，有了，可以给计算机安装一个闹钟，这个时钟定时给CPU产生中断，此后CPU终止运行当前进程并切换到下一个进程，这个机制能确保每个进程只连续运行一个固定的时间片。即使一个进程进入了死循环，系统也能在时间片结束时强制切换到其他进程，保证了系统的响应性和公平性。
你给这种机制起了个名字，”抢占式多任务处理”（PreemptiveMultitasking），就这样你实现了基于时间片的轮转调度算法（Round-Robin）。
现在情况得到了显著的改善。交互式应用变得更加流畅，用户不再抱怨系统卡顿。
但随着系统负载的增加，你又发现了新的问题：所有进程都被平等对待，无法区分任务的重要性和紧急程度，系统中的核武器发射进程竟然和扫雷小游戏进程的优先级是一样的，这也太危险了。
为此，你不得不引入了进程优先级的概念，每个进程被赋予一个优先级值，调度器总是选择优先级最高的进程来运行。
然而，优先级调度也带来了新的问题：低优先级的进程可能永远得不到执行的机会，这就是所谓的”饥饿”（Starvation）问题。
如果系统中一直有高优先级进程到来那么其它进程就没有机会运行了。
为此，你需要设计一个更复杂但更智能的调度算法。。。
推荐一下我写的专栏《深入理解操作系统》，第二版焕新升级，600+精美手绘图、87节精讲，如果你对操作系统感兴趣并且喜欢这篇文章的风格，那么这个专栏就是为你准备的：
