CPU作为一种系统资源，是唯一的，而在多任务的OS中，每个任务都需要使用CPU，因此需要为任务对CPU的使用提供一种同步机制，这就是调度（Scheduling）。调度器决定了在某一个时刻，应该让哪个任务获得CPU的使用权。
<img src="data:image/svg+xml;utf8,” data-rawwidth=”1038″ data-rawheight=”674″ data-size=”normal” data-caption=”” width=”1038″ data-original=”https://pic4.zhimg.com/v2-523f89d7548eaa75131073e70733c897_r.jpg” data-actualsrc=”https://pic4.zhimg.com/v2-523f89d7548eaa75131073e70733c897_b.jpg”>
基本模型
一个任务开始占有CPU并执行的过程称为”switch in”，释放CPU并结束执行的过程被称为”switch out”：
<img src="data:image/svg+xml;utf8,” data-rawwidth=”656″ data-rawheight=”98″ data-size=”normal” data-caption=”” width=”656″ data-original=”https://pic1.zhimg.com/v2-46f0815656a5fc2b3090ee738a1e0150_r.jpg” data-actualsrc=”https://pic1.zhimg.com/v2-46f0815656a5fc2b3090ee738a1e0150_b.png”>
调度依据的模型是sleep/wakeup，当正在运行的任务主动睡眠或者因为等待一个共享资源而阻塞时，”sleep“操作会将其switch out到一个被称为”sleep queue”（或”wait queue”）的队列上，然后从一个被称为”ready queue”的队列上挑选一个任务，switch in到CPU上执行：
<img src="data:image/svg+xml;utf8,” data-rawwidth=”686″ data-rawheight=”191″ data-size=”normal” data-caption=”” width=”686″ data-original=”https://pic3.zhimg.com/v2-f9b60b42aef902255e246eb203789aea_r.jpg” data-actualsrc=”https://pic3.zhimg.com/v2-f9b60b42aef902255e246eb203789aea_b.jpg”>
“ready queue”是当前可以执行的任务的集合，所谓“可以执行”，是指当前没有因为等待共享资源被阻塞或者进入sleep，那”ready queue”的任务是从哪里过来的呢？一种情况是在sleep queue上完成睡眠，或者等待的资源已释放后被”wakeup“，另一种情况是正在运行的任务主动让出（称为”yield”），或被其他任务抢占。
<img src="data:image/svg+xml;utf8,” data-rawwidth=”932″ data-rawheight=”415″ data-size=”normal” data-caption=”” width=”932″ data-original=”https://pic4.zhimg.com/v2-96e61cabaf458e9f5c582d5e397af9c7_r.jpg” data-actualsrc=”https://pic4.zhimg.com/v2-96e61cabaf458e9f5c582d5e397af9c7_b.jpg”>
可见，一个任务的状态可分为三种：blocked, ready 和running，它们之间的相互转换构成了调度的基石。
不能从blocked直接进入running状态，而是必须先经过ready状态，进入ready后也不会转为block状态。running代表CPU的使用权，如果把ready queue类比为内存的话，那么wait queue就可以被类比为磁盘。CPU只会访问内存里的东西，如果要访问磁盘上的东西，那必须先把磁盘上的内容拷贝到内存中来。
running->blocked, 以及running->ready，都会激活调度器，而调度执行的结果就是ready->running。即便系统中没有可执行的任务，上了电的CPU也不能停下来，所以OS会提供一个ilde线程，供CPU没事的时候撕报纸玩。
调度策略
基本的模型确定了，那根据这个模型，应该如何制定一个具体的调度策略，并衡量其好坏呢？在计算机系统中，衡量一个策略的优劣通常有两个指标：throughput和lantency。
<img src="data:image/svg+xml;utf8,” data-rawwidth=”828″ data-rawheight=”161″ data-size=”normal” data-caption=”” width=”828″ data-original=”https://pic2.zhimg.com/v2-c954132ceaf935a26786bbbc1a4645fd_r.jpg” data-actualsrc=”https://pic2.zhimg.com/v2-c954132ceaf935a26786bbbc1a4645fd_b.jpg”>
对于调度器来说也不例外，只是在OS的应用中，调度的”throughput“体现在对CPU资源的利用率上，而”lantency“体现为任务的平均完成时间（turnaround time）和平均响应时间（response time）。turnaround time是指从任务进入ready queue到完成执行的时间，response time则是指从任务进入ready queue到被CPU开始执行的时间。
<img src="data:image/svg+xml;utf8,” data-rawwidth=”652″ data-rawheight=”50″ data-size=”normal” data-caption=”” width=”652″ data-original=”https://pic4.zhimg.com/v2-0771de5606893f3f14a47d4ed6ca4973_r.jpg” data-actualsrc=”https://pic4.zhimg.com/v2-0771de5606893f3f14a47d4ed6ca4973_b.png”>
【FCFS】
最基础的策略就是基于FIFO模式的First-Come-First-Served (FCFS)，即先进入ready queue的任务优先执行，且必须等待前一个任务执行完毕（run to completion）或阻塞，后一个任务才能执行。
<img src="data:image/svg+xml;utf8,” data-rawwidth=”500″ data-rawheight=”274″ data-size=”normal” data-caption=”” width=”500″ data-original=”https://pic2.zhimg.com/v2-3c212d65d3b6e10ea823e371e27481b5_r.jpg” data-actualsrc=”https://pic2.zhimg.com/v2-3c212d65d3b6e10ea823e371e27481b5_b.jpg”>
来看一下FCFS模式在lantency和throughput这两个维度上的表现。比如现在有三个任务D3, D2和D1，依次进入ready queue（假设进入的时间差异很小，基本都是在0s处），其所需的执行时间分布是3s, 2s和1s，那么它们平均的turnaround time是4.67s，response time是2.67s。
<img src="data:image/svg+xml;utf8,” data-rawwidth=”642″ data-rawheight=”137″ data-size=”normal” data-caption=”” width=”642″ data-original=”https://pic2.zhimg.com/v2-37100efbe80ab9c576c96c9d6e1e0fe5_r.jpg” data-actualsrc=”https://pic2.zhimg.com/v2-37100efbe80ab9c576c96c9d6e1e0fe5_b.jpg”>
FCFS模式非常简单，甚至都感觉不到“调度”的存在，但如果前面任务执行的时间很长，那么后面的任务将受到比较大的影响。
【RR】
一个改进的做法是使用timeslice来分时复用CPU。timslice可理解为申领CPU的配额（quantum），内存分配考虑的是如何分配有限的memory资源，而基于timeslice的调度器考虑的是如何分配有限的CPU资源。
这种改进后的调度策略被称为Round-Robin（简称”RR“），每个任务的执行时间被分拆开来，成了不连续的。在每次switch-out的时候，它的上下文被保存，再次switch-in的时候上下文被恢复，因此从任务的视角，它感觉自己好像是独占CPU，运行时间上也是连续的。
从抽象的角度，这也可以理解为一种映射，跟进程连续的虚拟地址空间对应并不连续的物理内存有着相似之处。
还是同样的三个任务D3, D2和D1，假设timeslice的粒度是1ms，那么使用RR调度，它们平均的turnaround time将是(4.67+ε)s，response time将是(1+ε)s。
<img src="data:image/svg+xml;utf8,” data-rawwidth=”699″ data-rawheight=”217″ data-size=”normal” data-caption=”” width=”699″ data-original=”https://pic4.zhimg.com/v2-dd23fc07ecea712e49d8425420d5ccb7_r.jpg” data-actualsrc=”https://pic4.zhimg.com/v2-dd23fc07ecea712e49d8425420d5ccb7_b.jpg”>
这里的”ε”是上下文切换的时间开销。从“throughput“的角度，因为CPU有一些时间花在了context switch上，利用率比FCFS有所降低。timeslice越长，切换越不频繁，则CPU利用率降低的程度将减少。
从”latency”的角度，其response time比FCFS明显减少了，但turnaround time还略微增加了一些。但这不是绝对的，如果换一种场景，两个任务，执行时间分别是5s和1s，那么FCFS和RR的turnaround time分别是5.5s是和(4+ε)s：
<img src="data:image/svg+xml;utf8,” data-rawwidth=”897″ data-rawheight=”152″ data-size=”normal” data-caption=”” width=”897″ data-original=”https://pic2.zhimg.com/v2-062253f0bf43db25a0e7041ca1011d4d_r.jpg” data-actualsrc=”https://pic2.zhimg.com/v2-062253f0bf43db25a0e7041ca1011d4d_b.jpg”>
可见，如果后面进入的任务执行较短，那么RR相比FCFS所获得的收益就更明显。那如果干脆先执行所需时间较短的任务呢，谁最短就先执行谁。
<img src="data:image/svg+xml;utf8,” data-rawwidth=”938″ data-rawheight=”126″ data-size=”normal” data-caption=”” width=”938″ data-original=”https://pic2.zhimg.com/v2-f54f31d1dbb7ad70060a751d4bc9a739_r.jpg” data-actualsrc=”https://pic2.zhimg.com/v2-f54f31d1dbb7ad70060a751d4bc9a739_b.png”>
这样的话，平均的turnaround time和response time分别是3.33s和1.33s，这种调度策略就是Shortest Job First(SJF)。虽然SJF的表现十分亮眼，但要衡量哪个任务的预期执行时间最短，实际上是相当困难的，所以可以说这是一种理想但难以具体实施的策略，不过下文将要介绍的MLFB将另辟蹊径，从效果上接近SJF。
【I/O的影响】
以上的讨论基于的是比较简洁的模型，实际的系统还需要考虑更多的因素，比如I/O的等待。假设现在有A, B两个任务，所需的执行时间分别都是25ms，但A在执行过程中会因为I/O阻塞，多花掉20ms的时间，CPU的使用率是5/7=71.4%。
<img src="data:image/svg+xml;utf8,” data-rawwidth=”720″ data-rawheight=”234″ data-size=”normal” data-caption=”” width=”720″ data-original=”https://pic2.zhimg.com/v2-9e2d3bbac17b93620a7e1e611165c9dd_r.jpg” data-actualsrc=”https://pic2.zhimg.com/v2-9e2d3bbac17b93620a7e1e611165c9dd_b.jpg”>
如果在A进行I/O等待时，给予B执行机会，那么CPU的利用率将接近100%（之所以说“接近”，是因为还有context switch的开销）。
<img src="data:image/svg+xml;utf8,” data-rawwidth=”720″ data-rawheight=”229″ data-size=”normal” data-caption=”” width=”720″ data-original=”https://pic3.zhimg.com/v2-212d109858c90ae71befe98b64271ae6_r.jpg” data-actualsrc=”https://pic3.zhimg.com/v2-212d109858c90ae71befe98b64271ae6_b.jpg”>
在众多的操作系统，尤其是RTOS中，任务是存在优先级的，那调度器对此是如何应对的呢？请看下文分解。
参考：
http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf
原创文章，转载请注明出处。
