进程调度
目录
参考资料：
进程调度是 OS 中必不可少的一种调度。它也是对系统性能影响最大的一种 CPU 调度。
进程调度的任务和机制
进程调度的任务
- 保存处理机的现场信息
在进行调度时首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等。// 保存当前进程数据
- 按某种算法选取进程
调度程序按某种算法从就绪队列中选取一个进程，将其状态改为运行状态，并准备把处理机分配给它。// 选取进程
- 把处理器分配给进程
由分派程序把处理器分配给该进程，此时需要将选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交予该进程，让它从上次的断点处恢复运行。// 恢复运行
进程调度机制
为了实现进程调度，在进程调度机制中，应具有如下三个基本部分：
排队器：为了提高进程调度的效率，应事先将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便调度程序能最快地找到它。以后每当有一个进程转变为就绪状态时，排队器便将它插入到相应的就绪队列。
分派器：分派器依据进程调度程序所选定的进程，将其从就绪队列中取出，然后进行从分派器到新选出进程间的上下文切换，将处理机分配给新选出的进程。
上下文切换器：在对处理机进行换时，会发生两对上下文的切换操作：
- 第一对上下文切换时，OS 将保存当前进程的上下文，即把当前进程的处理机寄存器内容保存到该进程的进程控制块内的相应单元，再装入分派程序的上下文，以便分派程序运行。// 卸载
- 第二对上下文切换是移出分派程序的上下文，而把新选进程的 CPU 现场信息装入到处理机的各个相应寄存器中，以便新选进程运行。// 装配
在进行上下文切换时，需要执行大量的 Load 和 Store 等操作指令，以保存存器的内容。即使是现代计算机，每一次上下文切换所花费的时间大约可执行上千条指令。为此，现在已有靠硬件实现的方法来减少上下文切换时间。一般采用两组（或多组）寄存器，其中的一组寄存器供处理机在系统态时使用，而另一组寄存器供应用程序使用。在这样条件下的上下文切换，只需改变指针，使其指向当前寄存器组即可。// 使用多组寄存器来减少上下文切换时间
进程调度的方式 | 抢占式和非抢占式
非抢占方式存在着很大的局限性，很难满足交互性作业和实时任务的需求。所以，在进程调度中又引入了抢占方式。
非抢占方式（Nonpreemptive Mode）
在采用这种调度方式时，一旦把处理机分配给某进程后，就一直让它运行下去，绝不会因为时钟中断或任何其它原因去抢占当前正在运行进程的 CPU，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程。
在采用非抢占调度方式时，可能引起进程调度的因素可归结为：
正在执行的进程运行完毕，或因发生某事件而使其无法再继续运行
正在执行中的进程因提出 I/O 请求而暂停执行
在进程通信或同步过程中，执行了某种原语操作，如 Block 原语。
这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统。但它不能用于分时系统和大多数实时系统。
抢占方式（PreemptiveMode）
这种调度方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。
在现代 OS 中广泛采用抢占方式，这是因为：
对于批处理机系统，可以防止一个长进程长时间地占用处理机，以确保处理机能为所有进程提供更为公平的服务。
在分时系统中，只有采用抢占方式才有可能实现人机交互。
在实时系统中，抢占方式能满足实时任务的需求。
抢占方式比较复杂，所需付出的系统开销也较大。“抢占”不是一种任意性行为，必须遵循一定的原则。主要原则有:
优先权原则，指允许优先级高的新到进程抢占当前进程的处理机。
短进程优先原则，指允许新到的短进程可以抢占当前长进程的处理机。
时间片原则，即各进程按时间片轮转运行时，当正在执行的进程的一个时间片用完后，便停止该进程的执行而重新进行调度。
轮转调度算法
分时系统中，最简单也是较常用的是基于时间片的轮转（round robin，RR）调度算法。该算法采取了非常公平的处理机分配方式，即让就绪队列上的每个进程每次仅运行一个时间片。如果就绪队列上有 n 个进程，则每个进程每次大约都可获得 1/n 的处理机时间。
轮转法的基本原理
在轮转（RR）法中，系统将所有的就绪进程按 FCFS 策略排成一个就绪队列。系统可设置每隔一定时间（如 30ms）便产生一次中断，去激活进程调度程序进行调度，把 CPU 分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。这样，就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。
进程切换时机
在 RR 调度算法中，应在何时进行进程的切换，可分为两种情况：
若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。
在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。
时间片大小的确定
在轮转算法中，时间片的大小对系统性能有很大的影响。若选择很小的时间片，将有利于短作业，因为它能在该时间片内完成。但时间片小，意味着会频繁地执行进程调度和进程上下文的切换，这无疑会增加系统的开销。反之，若时间片选择得太长，且为使每个进程都能在一个时间片内完成，RR 算法便退化为 FCFS 算法，无法满足短作业和交互式用户的需求。
一个较为可取的时间片大小是略大于一次典型的交互所需要的时间，使大多数交互式进程能在一个时间片内完成，从而可以获得很小的响应时间。
下图给出了时间片分别为 q=1 和 q=4 时对平均周转时间的影响。 
// 上例中，当 q=4 时，每个作业都能够在一个时间片内执行完。所以会比 q=1 要好
优先级调度算法
在时间片轮转调度算法中，默认系统中所有进程的紧迫性是相同的。但实际情况并非如此。为了能满足实际情况的需要，在进程调度算法中引入优先级，而形成优先级调度算法。
优先级调度算法的类型
优先级进程调度算法，是把处理机分配给就绪队列中优先级最高的进程。该算法可分成如下两种：
非抢占式优先级调度算法。一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去直至完成，或者因该进程发生某事件而放弃处理机时，系统方可将处理机重新分配给另一优先级最高的进程。// 进程不会被抢占
抢占式优先级调度算法。把处理机分配给优先级最高的进程，使之执行。但在其执行期间，只要出现了另一个其优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。因此，在采用这种调度算法时，每当系统中出现一个新的就绪进程 i 时，就将其优先级 P(i) 与正在执行的进程 j 的优先级 P(j) 进行比较，如果 P(j) >= P(i)，原进程 j 便继续执行；但如果是 P(j) < P(i)，则立即停止 j 的执行，进行进程切换，使 i 进程投入执行。// 抢占式，当有新进程时，每次都会要进行比较
优先级的类型
优先级调度算法的关键在于：应如何确定进程的优先级，以及确定是使用静态优先级还是动态优先级。
静态优先级：静态优先级是在创建进程时确定的，在进程的整个运行期间保持不变。优先级是利用某一范围内的一个整数来表示的，例如 0~255 中的某一整数，又把该整数称为优先数。确定进程优先级大小的依据有三个：进程类型、进程对资源的需求、用户要求(紧迫程度)。静态优先级法简单易行，系统开销小，但不够精确，可能会出现优先级低的进程长期没有被调度的情况。// 有可能出现进程不被调度或线程饥饿
动态优先级：在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。例如，可以规定在就绪队列中的进程随其等待时间的增长，使其优先级相应提高。若所有的进程都具有相同优先级初值，则最先进入就绪队列的进程会因其优先级变得最高，而优先获得处理机，这相当千 FCFS 算法若所有的就绪进程具有各不相同的优先级初值，那么对于优先级初值低的进程，在等待了足够的时间后，也可以获得处理机。当采用抢占式调度方式时，若再规定当前进程的优先级随运行时间的推移而下降，则可防止一个长作业长期地垄断处理机。
多队列调度算法
系统中仅设置一个进程的就绪队列，那么低级调度算法就是固定的、单一的，无法满足系统中不同用户对进程调度策略的不同要求，在多处理机系统中，这种单一调度策略实现机制的缺点更显突出。而多级队列调度算法能够在一定程度上弥补这一缺点。
该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。// 拆分多个对列
多队列调度算法由于设置多个就绪队列，因此对每个就绪队列就可以实施不同的调度算法，因此，系统针对不同用户进程的需求，很容易提供多种调度策略。
多级反馈队列（multileved feedback queue）调度算法
多级反馈队列调度算法不必事先知道各种进程所需的执行时间，可以较好地满足各种类型进程的需要，所以它是目前公认的一种较好的进程调度算法。
调度机制
多级反馈队列调度算法的调度机制可描述如下：
- 设置多个就绪队列。在系统中设置多个就绪队列，并为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低。该算法为不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片就愈小。例如第二个队列的时间片要比第一个的时间片长一倍，第 i+1 个队列的时间片要比第 i 个的时间片长一倍。
下图是多级反馈队列算法的示意图：
每个队列都采用 FCFS 算法。当新进程进入内存后，首先将它放入第一队列的末尾按 FCFS 原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。否则，即它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，依此类推。当进程最后被降到第 n 队列后，在第 n 队列中便采取按 RR 方式(时间片轮转)运行。// 进程不断进行队列降级
按队列优先级调度。调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行：换言之，仅当第 1~(i-1) 所有队列均空时，才会调度第 i 队列中的进程运行。如果处理机正在第 i 队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第 i 队列的末尾，而把处理机分配给新到的高优先级进程。
基于公平原则的调度算法
保证调度算法
保证调度算法向用户所做出的保证并不是优先运行，而是明确的性能保证，该算法可以做到调度的公平性。
一种比较容易实现的性能保证是处理机分配的公平性。如果在系统中有 n 个相同类型的进程同时运行，为公平起见，须保证每个进程都获得相同的处理机时间 1/n。在实施公平调度算法时系统中必须具有这样一些功能：// 保证每个进程都能公平得分配到 CPU
跟踪计算每个进程自创建以来已经执行的处理时间。
计算每个进程应获得的处理机时间，即自创建以来的时间除以 n。
计算进程获得处理机时间的比率，即进程实际执行的处理时间和应获得的处理机时间之比。
比较各进程获得处理机时间的比率。如进程 A 的比率最低，为 0.5，而进程 B 的比率为 0.8，进程 C 的比率为 1.2 等。
调度程序应选择比率最小的进程将处理机分配给它，并让该进程一直运行，直到超过最接近它的进程比率为止。
公平分享调度算法
分配给每个进程相同的处理机时间，显然，这对诸进程而言，是体现了一定程度的公平，但如果各个用户所拥有的进程数不同，就会发生对用户的不公平问题。假如系统中仅有两个用户，用户 1 启动了 4 个进程，用户 2 只启动 1 个进程，采用轮转法让每个进程轮流运行一个时间片时间，对进程而言很公平，但用户 1 和用户 2 得到的处理机时间分别 80% 和 20%，显然对用户 2 而言就有失公平。在该调度算法中，调度的公平性主要是针对用户而言，使所有用户能获得相同的处理机时间，或所要求的时间比例。然而调度又是以进程为基本单位，为此，必须考虑到每一个用户所拥有的进程数目。// 从用户和进程角度来看公平性，两种不同的思路