进程调度的任务

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

进程调度的机制

进程调度机制

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

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

在进行上下文切换时，需要执行大量的load和store等操作指令，以保存寄存器的内容

进程调度方式

• 非抢占式

  • 机制：
    一旦把处理机分配给某个进程后，就让它一直运行下去，绝不会因为时钟中断或其他原因去抢占当前正在运行的处理机，直到该进程完成，或因为发生某事件而被阻塞时，才会把处理机分配给其它进程

  • 引起调度的因素：
    1.进程执行完毕或因某事件而使其无法再继续运行
    2.正在执行的进程因提出I/O请求而暂停执行
    3.在进程通信或者同步过程中，执行了某种原语操作，如BLOCK原语

  • 优缺点：实现简单，系统开销小，适用于大多数批处理系统，但它不能用于分时系统和大多数实时系统

• 抢占式

  • 机制：
    允许调度程序按照某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程
  • 原则：
    1.优先权原则：允许优先级高的新到进程抢占当前进程的处理机
    2.短进程优先原则：允许新到的短进程（新到达进程比正在执行进程尚需运行的时间明显短）可以抢占当前长进程的处理机
    3.时间片原则：各进程按时间片轮转运行时，正在执行的进程一个时间片用完，便停止该进程的执行而重新进行调度

调度算法：

1. 轮转调度算法（round robin, RR）：

   • 机制：
     根据FCFS策略，将所有就绪进程排成一个就绪队列，并设置每隔一段时间产生一次中断，激活系统中的进程调度程序，完成一次调度，将CPU分配给队首进程，令其执行。若在时间片用完之前，正在运行的进程便已完成，就立刻激活调度程序，将它从就绪队列中删除，再开始下一个循环。若时间片用完，进程尚未执行完毕，则调度程序就将其送至队列的末尾。
   • 关键：
     时间片的选取：若太小，意味着会频繁地执行进程调度和进程上下文切换，这无疑会增加系统开销。若太长，极端情况下，每个进程都在一个时间片内执行完成，则算法退化为FCFS算法，无法满足短作业和交互式用户需求

2. 优先级调度算法：

   • 类型：
     静态优先级：在创建进程时确定，在进程整个运行期间保持不变
     动态优先级：创建进程时赋一个初始值，随进程推进或等待时间增加而改变
   • 机制：
     把处理机分配给就绪队列中优先级最高的进程。若为非抢占式优先级算法，一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去直至完成，或者因该进程发生某事件而放弃处理机时，系统方可将处理机重新分配给另一优先级最高的进程。若为抢占式优先级算法，在进程执行期间，只要来了一个优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。
   • 关键：
     优先级的确定与维护

3. 多队列调度算法：

   • 机制：
     该算法将系统中的就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配到不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。
   • 优点：
     弥补了低级调度算法固定，单一，无法满足系统中不同用户对进程调度策略的不同要求的缺点。同时在多处理机系统中，该算法由于安排了多个就绪队列，因此，很方便为每个处理机设置一个单独的就绪队列，这样，不仅对每个处理机的调度可以实施不同的调度策略，对于一个含有多个线程的进程而言，可以根据要求将其所有线程分配在一个就绪队列，全部在一个处理机上执行。再者，对于一组需要相互合作的进程或线程而言，也可以将它们分配在一组处理机所对应的多个就绪队列，使得他们能同时获得处理机并行执行。

4. 多级反馈队列（multileved feedback queue）调度算法：

   • 机制：
     1. 设置多个就绪队列
        在系统中设置多个就绪队列，并为每个队列赋予不同的优先级，第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低，该算法为不同队列中进程所赋予的执行时间片的大小也各不相同，在优先级越高的队列中，其时间片就越小。如第二个队列时间片比第一个的长一倍......第i+1个队列的时间片要比第i个的时间片长一倍。以下为示意图：
        
        多级反馈队列调度算法
     2. 每个队列都采用FCFS算法
        每当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则等待调度。当轮到该进程执行时，如果它能在该时间片内完成，便可撤离系统，否则，即它在一个时间片结束时尚未完成，调度程序将它转入至第二队列的末尾等待调度；依此类推，当进程被将至第n队列后，则在第n队列采用RR方式运行
     3. 按队列优先级调度
        调度程序首先调度最高优先级队列中的诸程序运行，且仅当第1~(i-1)所有队列均为空时，采取调度第i队列中的程序运行，若处理机正在处理的第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时必须把正在运行的进程放回第i队列的末尾，而把处理机分配给新到的高优先级进程

如有叙述错误，欢迎指正~