进程调度算法

进程调度的任务

• 保存处理机的现场信息。
  在进行调度时首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等。
• 按某种算法选取进程。
  调度程序按某种算法从就绪队列中选取一个进程，将其状态改为运行状态，并准备把处理器分配给它。
• 把处理器分配给进程。由分派程序把处理器分配给该进程，此时需要将选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交与该进程，让它从上次的断点处恢复运行。

进程调度机制

为了实现进程调度，在进程调度机制中，应具有如下三个基本部分：

• 排队器。
  为了提高进程调度的效率，应事先将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便调度程序能最快地找到它。以后每当有一个进程转变为就绪状态时，排队器便将它插入到相应的就绪队列。
• 分派器
  分派器依据进程调度程序所选定的进程，将其从就绪队列中取出，然后进行从分派器到新选出进程间的上下文切换，将处理器分配给新选出的进程。
• 上下文切换器。
  在对处理机进行切换时，会发生两对上下文的切换操作：
  • 第一对上下文切换时，OS将保存当前进程的上下文，即把当前进程的处理机寄存器内容保存到该进程控制块内的相应单元，再装入分派程序的上下文，以便分派程序运行；
  • 第二对上下文切换是移出分派程序的上下文，而把新选进程的CPU现场信息装入到处理机的各个相应寄存器中，以便新选进程运行。

进程调度方式

• 非抢占方式
  在采用这种调度方式时，一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机，直到该进程完成，或发生某事件而被阻塞时，才把处理机分配给其他进程。
  在采用非抢占调度时，可能引起进程调度的因素可归结为：
  • 正在执行的进程运行完毕，或因发生某事件而使其无法再继续运行；
  • 正在执行中的进程因提出I/O请求而暂停执行；
  • 在进程通信或同步过程中，执行了某种原语操作。
• 抢占方式
  这种调度方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一个进程。
  在现代OS中广泛采用抢占方式，这是因为：
• 对于批处理机系统，可以防止一个长进程长时间地占有处理机，以确保处理机能为所有进程提供更为公平的服务。
• 在分时系统中，只有采用抢占方式才有可能实现人-机交互。
• 在实时系统中，抢占方式能满足实时任务的需求。

“抢占”不是一种任意性行为，必须遵守一定的原则。主要原则有：

• 优先权原则，指允许优先级高的新到进程抢占当前进程的处理机。
• 短进程优先原则，指允许新到的短进程可以抢占当前长进程的处理机。
• 时间片原则，即各进程按时间片轮转运行时，当正在执行的进程的一个时间片用完后，便停止该进程的执行而重新进行调度。

轮转调度算法

基于时间片的轮转（round robin，RR）调度算法。该算法采取了非常公平的处理机分配方式，即让就绪队列上的每一个矜持每次仅运行一个时间片。如果就绪队列上有n个进程，则每个进程每次大约都可获得1/n的处理机时间。

• 原理
  在RR法中，系统根据FCFS策略，将所有的就绪进程排成一个就绪队列。并可设置每隔一定时间间隔即产生一次中断，激活系统中的进程调度程序，完成一次调度，将CPU分配给队首进程，令其执行。当该进程的时间片耗尽或运行完毕时，系统再次将CPU分配给新的队首进程或新到达的紧迫进程。由此，可保证就绪队列中的所有进程在一个确定的时间段内，都能够获得一次CPU执行。
• 切换时机
  • 若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。
  • 在一个时间片用完时，计时器中断处理程序被激活，如果进程尚未运行完毕，调程序将它送往就绪队列的末尾。
• 时间片大小的确定
  • 时间片小，意味着会频繁地执行进程调度和进程上下文的切换，这无疑会增加系统的开销。
  • 时间片大，会使每个进程都能在一个时间片内完成，RR算法便退化为FCFS算法，无法满足短作业和交互式用户的需求。

优先级调度算法

为了满足系统中所有进程的紧迫性是不同的，在进程调度算法中引入优先级，而形成优先级调度算法。

• 优先级调度算法的类型
  • 非抢占式优先级调度算法：该算法规定，一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去直至完成，或者因该进程发生某事件而放弃处理机时，系统方可将处理机重新分配给另一优先级最高的进程。
  • 抢占式优先级调度算法：把处理机分配给优先级最高的进程，使之执行。但在其执行期间，只要出现了另一个其优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。
• 优先级的类型
  • 静态优先级：在创建进程时确定的，在进程的整个运行期间保持不变。
    确定进程优先级大小的依据有如下三个：
    • 进程类型：通常系统进程（如接收进程、对换进程）的优先级高于一般用户进程的优先级。
    • 进程对资源的需求：对资源要求少的进程应赋予较高的优先级。
    • 用户要求：根据进程的紧迫程序及用户所付费用的多少确定优先级。
  • 动态优先级：动态优先级是指在创建进程之初，先赋予其一个优先级，然后其值随进程或等待时间的增加而改变。

多队列调度算法

该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。

多级反馈队列调度算法

• 调度机制
  • 设置多个就绪队列。在系统中设置多个就绪队列，并为每个队列赋予不同的优先级。队列的优先级逐个降低，在优先级愈高的队列中，其时间片就愈小。
  • 每个队列都采用FCFS算法。
  • 按队列优先级调度。

基于公平原则的调度算法

• 保证调度算法
  如果在系统中有n个相同类型的进程同时运行，为了公平起见，须保证每个进程都获得相同的处理机时间1/n，在实施公平调度算法时系统中必须具有这样一些功能：
  • 跟踪计算每个进程自创建以来已经执行的处理时间。
  • 计算每个进程应获得的处理机时间，即自创建以来的时间除以n
  • 计算进程获得处理机时间的比率，即进程实际执行的处理时间和应获得的处理机时间之比
  • 比较各进程获得处理机时间的比率
  • 调度程序应选择比率最小的进程将处理机分配给它，并让该进程一直运行，直到超过最接近它的进程比率为止。
• 公平分享调度算法
  在该调度算法中，调度的公平性主要是针对用户而言，使所有用户能获得相同的处理机时间，或所要求的时间比例。