操作系统【进程的调度】

三层调度

内存调度是为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来，当内存空间宽松时，再将其唤醒。

调度的时机

应该调度的情况：
1. 主动放弃：进程正常终止。运行过程中发生异常而终止。主动阻塞（如等待 I/O ）。
2. 被动放弃：分给进程的时间片用完。有更紧急的事情需要处理（如 I/O 中断）。有更高优先级的进程进入就绪队列。

不能调度的情况：
1. 在处理中断的过程中。
2. 进程在操作系统内和程序临界区中。
3. 原子操作过程中（原语）

进程调度方式

1. 非抢占方式，即非剥夺调度方式。一旦把 CPU 分配给一个进程，该进程就会保持 CPU 直到终止。
2. 抢占方式，即剥夺调度方式。若有某个更为重要或紧急的进程需要使用处理机，则立即暂停正在执行的的进程，将处理机分配给更为重要或紧急的进程。

调度算法

先来先服务调度算法（FCFS）

算法规则：按照作业/进程到达的先后顺序进行服务。
是否可抢占：非抢占式。
优点：公平、算法实现简单。
缺点：对长作业比较有利，但对短作业不利。有利于 CPU 繁忙型作业，而不利于 I/O 繁忙型作业。
是否会导致饥饿：不会。

短作业优先调度算法（SJF）

算法规则：要求服务时间最短的作业/进程优先得到服务。
是否可抢占：非抢占式。但也有抢占式的版本--最短剩余时间优先算法（SRTN）
优点：“最短的”平均等待时间、平均周转时间。
缺点：对短作业有利，对长作业不利，可能产生饥饿现象。
是否会导致饥饿：会。如果有源源不断的短作业/进程到来，可能使长作业/进程一直得不到服务。

高响应比优先调度算法（HRRN）

算法规则：在每次调度时先计算响应比，选择响应比最高的为其服务。响应比 = （等待时间 + 要求服务时间）/ 要求服务时间。
是否可抢占：非抢占式。
优点：综合考虑了等待时间和服务时间。对长作业来说，随着等到时间的增减，其响应比也随之增加，避免了长作业饥饿问题。
是否会导致饥饿：不会。

时间片轮转调度算法（RR）

算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms），若进程未在一个时间片内执行完毕，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
是否可抢占：抢占式。若进程未在时间片内运行完，将被强制剥夺处理机使用权。
优点：公平、响应快、适用于分时操作系统。
缺点：由于高频率的进程切换，因此有一定开销，不区分任务的紧急程度。
是否会导致饥饿：不会。
时间片大小选择：若时间片足够大，以至于所有进程都能在一个时间片内执行完毕，则退化为先来先服务调度算法。若时间片很小，则处理机将在进程间过于频繁地切换，使处理机的开销增大。

优先级调度算法

算法规则：调度时选择优先级最高的作业/进程。
是否可抢占：抢占式、非抢占式都有。
优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。
缺点：若源源不断的高优先级进程到来，则可能导致饥饿。
是否会导致饥饿：会。

多级反馈队列调度算法

算法规则：
1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
2. 新进程到达先进入第一级队列，按 FCFS 原则排队等待被分配时间片，若用完时间片进程还未结束，则进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾。
3. 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片。
是否可抢占：抢占式。在 k 级队列的进程运行过程中，若更高级的队列中进入一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾。
优点：平衡其他算法的缺点，结合优点。
是否会导致饥饿：会。