1.调度概念

  1. 任务很多，资源有限，没法做到同时处理，这时候就需要确定某种规则来决定处理任务的顺序，
  2. 这就是处理机调度要研究的问题。
  4. 在多到程序系统中，进程数大于CPU个数，此时处理机要按照一定的算法选择一个进程并将处理器分配给它 运行。

2.调度算法

2.1 先到先服务（FCFS，队列实现，非抢占）

2.3 处理机调度 - 图3

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

短作业/进程优先调度算法

  1. 每次调度时选择当前已到达且运行时间最短的作业/进程。

image.png

  1. 当第0秒时，P1到达，就开始运行P1。
  2. 当第7秒时，P1执行完毕，此时P2,P3,P4都已经到达，选择最短作业就是P3，开始执行
  3. 当第8秒时，P3执行完毕，此时P2,P4处于就绪状态，并且他们两个作业时间相同，按照到达顺序进行执行，执行P2
  4. 当第12秒时，P2执行完毕，P4处于就绪状态，开始执行P4
  5. 当第16秒时，P4执行完毕。

最短剩余时间优先算法

  1. 最短剩余时间优先算法: 每当有进程加入就绪队列时就要重新调整调度，
  2. 如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，
  3. 当前进行进程重新回到就绪队列，此外，当一个进程完成时也需要重新调整调度方案。

image.png
如上图这个例子，四个进程执行完毕，一共花的时间是 7+4+1+4=16, 但是根据短作业优先，在11时刻时就有三个进程完成作业，对短作业友好，无需因存在长作业而要等待很长时间。

  1. 第0秒时，P1到达，开始执行
  2. 第2秒时，P2到达，此时P1剩余作业时间5秒，P2剩余时间4秒，开始执行P2，P1暂停，进入到就绪状态。
  3. 第4秒时，P3到达，此时P1剩余作业时间5秒，P3剩余作业时间1秒，P2剩余作业时间2秒，开始执行P3
  4. 第5秒时，P4到达，P3执行完毕，此时P1剩余作业时间5秒，P4剩余作业时间4秒，P2剩余作业时间2秒，开始执行P2
  5. 第7秒时，P2执行完毕，此时P1剩余作业时间5秒，P4剩余作业时间4秒，开始执行P4
  6. 第11秒时，P4执行完毕，开始执行P1
  7. 第16秒时，P1执行完毕。

2.3 处理机调度 - 图6

2.3 高响应比优先（HRRN）

高响应比优先算法

  1. 非抢占式的调度算法，只有当前运行的进程主动放弃CPU时（正常/异常完成，或者主动阻塞），才需要进行调度，
  2. 调度时计算所有就绪进程的响应比，选响应比最高的进程处理。
  4. 响应比=（等待时间+要求服务时间）/（要求服务时间）

image.png

  1. 第0秒，P1到达就绪队列，P1上处理器开始处理。
  2. 第7秒，P1执行完毕，主动放弃CPU，此时在就绪队列上，
  3.        有P2(等待时间5秒，要求服务时间4秒),P2(响应比=(5+4)/4=2.25)
  4.        有P3(等待时间3秒，要求服务时间1秒),P3(响应比=(3+1)/1=4)
  5.        有P4(等待时间2秒，要求服务时间4秒),P4(响应比=(2+4)/4=1.5)
  6.        优先处理P3
  7. 第8秒，P3执行完毕，主动放弃CPU，此时在就绪队列上，
  8.        有P2(等待时间6秒，要求服务时间4秒),P2(响应比=(6+4)/4=2.5)
  9.        有P4(等待时间3秒，要求服务时间4秒),P3(响应比=(3+4)/4=1.75)
  10.        优先处理P2
  11. 第12秒，P2执行完毕，主动放弃CPU，开始处理P4

2.3 处理机调度 - 图8

优缺点

  1. 综合考虑了等待时间和运行时间（要求服务时间），等待时间相同时，要求服务时间短的优先（SJF的优点，短作业优先）
  2. 要求服务时间相同时，等待时间长的优先（FCFS的优点，先到先服务）
  3. 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。

2.4 时间片轮转调度算法(RR,Round-Robin)

  1. 时间片轮转调度算法: 轮流让就绪队列中的进程依次执行一个时间片（每次选择的都是排在就绪队列头的进程）

image.png

  1. 假设时间片单位大小为2，以上图为例
  2. 第0秒: 只有P1到达就绪队列，让P1上处理机运行一个时间片。(P1[5])
  3. 第2秒: P2到达就绪队列，P1运行完一个时间片，被剥夺处理机，重新放到队尾(P2[4],P1[3])
  4. 此时P2排在对头，因此让P2上处理机（注意:第2秒时，P1运行完一个时间片，下处理及，同一时刻新进程P2到达，
  5. 默认新到达的进行先进入就绪队列）(P2[4],P1[3])
  6. 第4秒: P3到达，先插入到就绪队尾，紧接着，P2下处理机也插入到对尾。开始执行P1 (P1[3],P3[1],P2[2])
  7. 第5秒: P4到达，插入就绪队列队尾，由于P1的时间片还没用完，因此暂时不调度。
  8.         P1处于运行态，并不在就绪队列中。(P1[2],P3[1],P2[2],P4[6])
  9. 第6秒: P1运行完一个时间片,剥离处理机，重新放到队尾。此时开始处理P3 (P3[1],P2[2],P4[6],P1[1])
  10. 第7秒: P3运行完毕，主动放弃处理机。发生调度。开始执行P2(P2[2],P4[6],P1[1])
  11. 第9秒: P2运行完毕，主动放弃处理机，发生调度。开始执行P4(P4[6],P1[1])
  12. 第11秒: P4运行完一个时间片，剥离处理机，重新放到队尾。开始执行P1(P1[1],P4[4])
  13. 第12秒: P1运行完毕，主动放弃处理机，发生调度。此时就绪队列中只剩下P4,P4上处理机(P4[4])
  14. 第14秒: 就绪队列为空，因此让P4接着运行一个时间片
  15. 第16秒:所有进程运行结束。

时间片大小的讨论

  1. [1] 如果时间片太大，使得每个进程都可以在一个时间片内完成，那么轮转调度算法其实就变成了 先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
  2. [2] 如果时间片太小，进程调度，切换是有时间代价的，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。

2.5 优先级调度算法

分类

非抢占式优先级调度算法

image.png

抢占式优先级调度算法

image.png

优缺点

优点:
  1. 用优先级区分紧急程度，重要程度。适用于实时操作系统，可灵活地调整对各种作业/进程的偏好程度。

缺点
  1. 若源源不断地有高优先级进程到来，则可能导致饥饿现象。

2.6 多级反馈队列调度算法

image.png

image.png

image.png

引用

非抢占式和抢占式进程调度的区别