CPU调度

一般来说，CPU调度==处理机调度==进程调度

发生时刻

• running to waiting
• running to ready
• waiting to ready
• terminates

调度方式

• 抢占式：一旦给某个进程分配完cpu就让该进程进行下去；
• 非抢占式：当一个进程在运行中，系统基于某种原则，剥夺分配给该进程的CPU；

调度策略

先来看几个指标，这几个指标可以用来判断调度策略优劣的：

Throughput(吞吐量)：单位时间内进程完成的数量；

Turnaround time(周转时间)：执行一个进程花费的时间(从进入就绪队列到完成 Termination time - Arrival time)；

Waiting time：一个进程在ready队列中等待的时间；

Response time：从进程提出请求道首次被响应的时间（不包括执行完成）；

First come, First served

非抢占式的，根据它们的到达时间，系统维一个FIFO的进程列表；

Shortest-Job-First

系统在ready queue中，优先选择那些CPU burst time最少的进程。

这种调度策略分为抢占式和非抢占式两种，抢占式的没什么好说，非抢占式的：当一个新的需要更少CPU burst time的进程到达时，CPU便会重新分配。

SJF还有一种变形，即highest response ration next（等待时间+要求执行时间/要求执行时间）

Priority

同样，优先级策略也分为抢占式和非抢占式两种。

这种调度策略会导致一个非常严重的问题——starvation，优先级低的进程可能一直无法被执行。为了解决这个问题，我们可以采取动态优先级的策略，随着时间推移，我们提升某些进程的优先级。

优先级范围

• windows的线程
  • windows的每一个线程都有优先级，范围是0-31，0最低，31最高；
• linux的进程
  • linux的进程范围是-20-19，值越小，优先级越高。通常情况下，linux的进程优先级是由父进程继承而来，通常是0；
  • nice值反映了进程优先级；
  • 我们可以通过nice命令来对一个将要执行的命令进程nice值；通过renice重新设置nice值；

Round Robin

这是一种抢占式的策略，给队列里的每个进程分配相同的时间片，无论进程是否执行完，当时间懂啊了都切换到下一个进程。

当时间片Q太大时，就变成了FIFO；

当Q太小，但不能小到切换上下文的花费比Q还小时；

这种策略的turnaround time会比SJF更高，因为SJF选择的是更低burst time，避免等待时间增多；但response time会更少，因为它的切换频率更快，使得响应更快；

Multilevel Queue

分配进程到多个队列中，每个队列使用不同的调度算法：

前台交互式(foreground)——RR

后台批处理(background)——FCFS

Multilevel Feedback

这是一种动态的调度策略，该策略需要定义以下这些部分：

队列个数；

每个队列的调度算法；

更新队列所属队列的方法；

提升或降低进程优先级的方法；