摘要

1. 进程调度
2. 调度原则
3. 调度算法

操作系统-进程调度

线程调度

进程调度是指在进程之间选择一个进程将其送上CPU执行，通常这个是由操作系统中的调度程序执行。

调度原则

• 如果运行的程序发生I/O事件请求，CPU使用率会降低，因为此时进程在等待硬盘数据的返回。所以为了提高CPU运行效率，在由于I/O导致CPU空闲时，调度程序需要从就绪队列中选择一个进程运行。
• 有的程序执行时间较长，一直占有CPU，系统吞吐量（单位时间内CPU完成的进程数量）降低。所以为了提高系统吞吐量，调度程序需要权衡长任务和短任务的完成数量。
• 进程的周转时间包含运行时间和阻塞等待时间。进程的周转时间越小越好，调度程序需要保证周转时间尽可能的小
• 调度程序需要让就绪队列中的等待时间尽可能的短
• 对于交互式比较强的应用，比如键盘、鼠标，调度程序要考虑程序的响应时间尽可能快。

综上所述，调度程序主要从以下几个系统参数来考虑：

• CPU利用率：调度程序尽可能的让CPU繁忙，提高调度程序的利用率
• 系统吞吐量：吞吐量是单位时间内CPU完成的进程数，长作业会降低吞吐量，短作业提高吞吐量
• 周转时间：周转时间是运行时间和阻塞时间的总和，一个进程的调度时间越小越好
• 等待时间：进程在就绪队列中等待时间尽可能的短
• 响应时间：在交互式较强的系统，调度算法需要尽可能的降低响应时间

调度算法

如果硬件提供某个频率的时钟中断，根据如何处理时钟中断调度算法大致分为两类：

• 非抢占式调度算法：该算法挑选一个进程，让该进程运行直到被阻塞或者进程退出，才会调用另外一个进程，不会理会时钟中断
• 抢占式调度算法：该算法挑选一个进程，让该进程在某个时间段内运行，如果运行超出该时间段，则会把它挂起，接着调度程序从就绪队列中挑选另一个进程运行。这种抢占式调度需要在时间段结束时发生时钟中断，以便把CPU控制权返回给调度程序进行调度。这就是常说的时间片机制。

先来先服务（FCFS）算法

先来后到，每次从就绪队列中选择一个进程运行，直到进程阻塞或退出。FCFS适用于CPU繁忙性作业的系统，不适用于I/O繁忙性。

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

优先选择运行时间最短的进程来运行，有利于提高系统的吞吐量。

SJF算法不利于长作业，如果就绪队列中短作业过多，会导致长作业具有较高的延迟。

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

主要是权衡了短作业和长作业，每次进行调度时，先计算响应比，然后把响应比最高的进程运行。

响应比=（等待时间+要求服务时间）/ 要求服务时间

• 如果进程等待时间相同，要求服务时间越短，响应比越高，这样短作业容易被运行
• 如果进程要求服务时间相同，等待时间越长，响应比越高，这样长度作业在等待时间过长时也会被选中运行

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

每一个进程被分给一个时间段，称之为时间片，即允许该进程在该时间段中运行。

• 如果时间片用完，进程还在运行，进程会将CPU释放，调度程序会把CPU分配给另一个进程运行
• 如果该进程在时间片结束之前阻塞或结束，CPU也会立即切换

在该算法中，时间片的长度是一个比较关键的点：

• 如果设置的太短会导致过多的进程上下文切换，降低CPU的效率
• 如果设置的太长有可能会导致短作业的响应时间变长

一般来说，时间片的设置应为略大于一次交互的响应时间，20ms~50ms是一个折中的值。

最高优先级（HPF）调度算法

从就绪队列中选择最高优先级的进程运行。

进程的优先级分为静态优先级和动态优先级：

• 静态优先级：创建进程的时候，就已经确定优先级了，然后整个运行时间优先级都不会变化
• 动态优先级：根据进程的动态变化调整优先级，如果进程运行时间增加，降低优先级，如果进程等待时间增加，则升高优先级

该算法也有两种处理高优先级的方法，非抢占式和抢占式：

• 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程
• 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行

优先级低的进程可能一直无法运行。

多级反馈队列（MFQ）调度算法

该算法是时间片轮转算法和最高优先级算法的结合。

• 多级表示有多个队列，每个队列优先级从高到低，同时优先级越高队列中时间片也越短
• 反馈表示如果有新的进程加入高优先级队列时，立刻停止当前正在运行的进程，转而去运行优先级高的进程

具体的工作流程如下：

• 设置多个队列，每个队列设置不同的优先级，队列的优先级从高到低，且优先级越高时间片越短
• 新的进程会被第一级队列的末尾，按照先来先服务的原则等待被调度，如果在第一优先级的规定的时间片进程没有执行完成，则会将他转入第二队列的末尾，依次类推，直至完成
• 当较高优先级的队列为空时，才能调度较低优先级队列中的进程。如果进程在运行时，有新进程加入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行。

这种算法对于短作业来说很可能就在第一级队列就被处理完成，对于长作业来说，虽然有可能因为在第一级队列无法执行完成而被被移入到第二级队列运行（等待时间变长），但是获得时间片也会变长（运行时间变长），所以该算法很好的兼顾了长短作业，同时有较好的响应时间。