【操作系统】操作系统的进程调度算法

什么是进程调度

• Linux是一个多任务操作系统，支持的任务同时运行的数量远大于CPU的数量
• 进程调度就是指【怎样安排】某一时刻CPU运行【哪个进程】

进程调度类型

• 非抢占式调度 Nonpreemptive
  • 一旦把处理机分配给某个进程后，进程就会一直运行，直到该进程【完成】或者【阻塞】时才会把CPU让给其他进程
  • 主要用于【批处理系统】和某些对【实时性要求不严】的实时系统
• 抢占式调度 Preemptive
  • 暂停某个正在执行的进程，将已经分配给该进程的处理及重新分配给另一个进程
  • 系统同样是把处理机分配给优先权最高的进程，在其执行期间出现了另一个其优先权更高的进程
  • 进程调度程序就停止当前进程的执行，重新将处理机分配给新到的优先级最高的进程
  • 主要用于比较严格的【实时系统】中

算法分类

（1）先来先服务调度算法（FCFS，first come first served，非抢占式）

• 按照作业/进程到达的先后顺序进行调度，即：优先考虑在系统中等待事件最长的作业
• 重点：排在长进程后的段进程的等待时间长，不利于短作业/进程，常简称得到CPU就直到执行完成了，不利于短进程执行
• 比如：进程一响应慢，进程二/三/四响应快，那进程一先到，其他本来很快搞定的但是没被调度到导致效率慢

（2）短作业优先调度算法（SJF，Shortest Job First，非抢占式）

• 预计执行时间短的进程优先分派处理机，短进程/作业（要求服务时间最短）
• 在实际情况中占有很大比例，为了使他们优先执行，对长作业不友好
• 重点：缩短进程的等待时间，提高系统的吞吐量
• 比如：进程一响应慢，进程二/三/四响应快，那同等时间下，更多短进程任务完成了，吞吐量也上去了

（3）高响应比优先调度算法（HRRN，Highest Response Ratio Next，非抢占式）

• 在每次调度时，先计算各个作业的优先权：优先权=响应比=（等待时间+要求服务时间）/要求服务时间

• 因为等待时间与服务时间之和就是系统对该作业的响应时间，所以 优先权=响应比=响应时间/要求服务时间
• 选择优先权高的进行服务需要【计算优先权信息，增加了系统的开销】是介于FCFS和SJF之间的一种折中算法

（4）时间轮转调度算法（RR，Round-Robin，抢占式）

• FCFS的方式按时间片轮流使用CPU的调度方式，让每个进程在一定的时间间隔都可以得到响应
• 由于高频率的进程切换，会增加了开销，且不区分任务的紧急程度

（5）优先级调度算法（Priority Scheduling，有抢占式和非抢占式）

• 根据任务的紧急程度进行调度，高优先级的先处理，低优先级的慢处理
• 通常使用【动态优先级】，如果高优先级任务很多切持续产生，那么低优先级的任务可能很慢才会被处理
• 优先级因素：进程的等待时间，已使用的处理机时间或其他资源的使用情况
• 分类
  • 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，在选择优先级高的进程
  • 抢占式：当就绪对列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行

（6）多级反馈对列调度算法（Multilevel Feedback Queue，抢占式）

• 多级：表示有多个对列，每个对列优先级从高到低，同时优先级越高时间片越短
• 高优先级对垒中已没有调度的进程，则调度次优先级队列中的进程
• 对于同个队列中的各个进程，按照时间片轮转法调度
• 比如：
  • Q1、Q2、Q3三个队列，在Q1中没有进程等待时才去调度Q2，只有Q1，Q2都为空的时候才去调度Q3
• 反馈：表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列

不同系统和版本支持的调度算法

• UNIX采用动态优先队列调度
• BSD采用多级反馈队列调度
• Windows采用抢先多任务调度