CPU作为一种系统资源，是唯一的，而在多任务的OS中，每个任务都需要使用CPU，因此需要为任务对CPU的使用提供一种同步机制，这就是调度（Scheduling）。调度器决定了在某一个时刻，应该让哪个任务获得CPU的使用权。一个任务开始占有CPU并执行的过程称为'switch in'，释放CPU并结束执行的过程被称为'switch out'：调度依据的模型是sleep/wakeup，当正在运行的任务主动睡眠或者因为等待一个共享资源而阻塞时，'sleep'操作会将其switch out到一个被称为'sleep queue'（或'wait queue'）的队列上，然后从一个被称为'ready queue'的队列上挑选一个任务，switch in到CPU上执行：'ready queue'是当前可以执行的任务的集合，所谓“可以执行”，是指当前没有因为等待共享资源被阻塞或者进入sleep，那'ready queue'的任务是从哪里过来的呢？一种情况是在sleep queue上完成睡眠，或者等待的资源已释放后被'wakeup'，另一种情况是正在运行的任务主动让出（称为'yield'），或被其他任务抢占。可见，一个任务的状态可分为三种：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。对于调度器来说也不例外，只是在OS的应用中，调度的'throughput'体现在对CPU资源的利用率上，而'lantency'体现为任务的平均完成时间（turnaround time）和平均响应时间（response time）。
turnaround time是指从任务进入ready queue到完成执行的时间，response time则是指从任务进入ready queue到被CPU开始执行的时间。
最基础的策略就是基于FIFO模式的First-Come-First-Served (FCFS)，即先进入ready queue的任务优先执行，且必须等待前一个任务执行完毕（run to completion）或阻塞，后一个任务才能执行。
来看一下FCFS模式在lantency和throughput这两个维度上的表现。比如现在有三个任务D3, D2和D1，依次进入ready queue（假设进入的时间差异很小，基本都是在0s处），其所需的执行时间分布是3s, 2s和1s，那么它们平均的turnaround time是4.67s，response time是2.33s。FCFS模式非常简单，甚至都感觉不到“调度”的存在，但如果前面任务执行的时间很长，那么后面的任务将受到比较大的影响。一个改进的做法是使用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。这里的'ε'是上下文切换的时间开销。从'throughput'的角度，因为CPU有一些时间花在了context switch上，利用率比FCFS有所降低。timeslice越长，切换越不频繁，则CPU利用率降低的程度将减少。从'latency'的角度，其response time比FCFS明显减少了，但turnaround time还略微增加了一些。但这不是绝对的，如果换一种场景，两个任务，执行时间分别是5s和1s，那么FCFS和RR的turnaround time分别是5.5s是和(4+ε)s：可见，如果后面进入的任务执行较短，那么RR相比FCFS所获得的收益就更明显。那如果干脆先执行所需时间较短的任务呢，谁最短就先执行谁。这样的话，平均的turnaround time和response time分别是3.33s和1.33s，这种调度策略就是Shortest Job First(SJF)。虽然SJF的表现十分亮眼，但要衡量哪个任务的预期执行时间最短，实际上是相当困难的，所以可以说这是一种理想但难以具体实施的策略，不过下文将要介绍的MLFB将另辟蹊径，从效果上接近SJF。以上的讨论基于的是比较简洁的模型，实际的系统还需要考虑更多的因素，比如I/O的等待。假设现在有A, B两个任务，所需的执行时间分别都是25ms，但A在执行过程中会因为I/O阻塞，多花掉20ms的时间，CPU的使用率是5/7=71.4%。如果在A进行I/O等待时，给予B执行机会，那么CPU的利用率将接近100%（之所以说“接近”，是因为还有context switch的开销）。在众多的操作系统，尤其是RTOS中，任务是存在优先级的，那调度器对此是如何应对的呢？请看下文分解。
