操作系统概念阅读笔记5

CPU调度

本文总阅读量
Posted by Xiaoxi on January 12, 2016

#操作系统概念阅读笔记5 ##CPU调度


###基本概念

CPU-I/O区间周期

  • 进程执行由CPU和I/O等待周期组成。进程在这两个状态之间切换。

CPU调度程序

  • 所谓CPU调度程序,其实就是:当CPU空闲时,操作系统如何从就绪队列中选择一个进程来执行的策略。

抢占调度

  • 非抢占调度,一旦CPU分配给一个进程,那么该进程会一直使用CPU直到进程终止或切换到等待状态。
  • 抢占调度,可能一个进程正在运行时,另一个新的进程也到来。而依据调度策略与当前各进程状态,新进程应该先执行。那么,新进程会抢占CPU进行执行,原进程切换到就绪状态。

####分派程序 分派程序是一个模块,用来将CPU的控制交给由短期调度程序选择的进程。 功能包括:

  1. 切换上下文
  2. 切换到用户模式
  3. 跳转到用户程序的合适位置,以重新启动程序

调度准则

  • CPU使用率
  • 吞吐量:一个时间单元内所完成进程的数量
  • 周转时间:从进程提交到进程完成的时间段称为周转时间。
  • 等待时间:为在就绪队列中等待所花费时间之和
  • 响应时间:开始响应所需要的时间,响应时间指从进程提交到被运行第一段代码的时间

调度算法

1.先到先服务调度(FCFS)

非抢占。 补充概念:护航效果:所有其他进程等待一个大进程释放CPU的状态

2.最短作业优先调度(SJF)

  • 这一算法将每个进程与其下一个CPU区间段相关联。当CPU为空闲时,它会赋给具有最短CPU区间的进程。 如果两个进程具有同样长度,那可以使用FCFS调度来处理。
  • SJF调度算法的平均等待时间最小。

  • SJF的难点就是如何得知下一个CPU区间的长度。书上采用,预测下一个CPU区间为以前CPU区间的测量长度的指数平均。T(n+1)=åt(n)+(1-å)T(n)
  • 抢占SJF调度:最短剩余时间优先调度 也存在非抢占SJF

3.优先级调度

  • SJF可作为通用优先级调度算法的一个特例
  • (书上默认)优先级越高,数值越小 即 优先级1比优先级2的优先级要高 优先级调度可以是抢占的或者非抢占的。
  • 主要问题:无穷阻塞或饥饿=》它可能会导致某个低优先级进程无线等待CPU
  • 解决:使用老化技术,以逐渐增加在系统中等待很长时间的进程的优先级

4.轮转法调度(RR)

  • 定义一个较小时间单元,称为时间片。
  • 将就绪队列保存为进程的FIFO队列。新进程增加到就绪队列的尾部。CPU调度程序就从就绪队列中选择第一个进程,设置定时器在一个时间片之后中断,再分排该进程。(1进程在时间片中运行完,进程自动释放CPU,下一个进程开始执行 2.进程未在时间片内执行完,定时器产生中断并产生操作系统中断,然后进行上下文切换,将进程加入到就绪队列的尾部,就绪队列中下一个进程开始执行)
  • 该策略的平均等待时间通常较长 具体效率和时间片大小有关 适合分时(交互系统)

5.多级队列调度

将就绪队列分成多个独立队列,每个队列有自己的调度算法,每个队列有自己的优先级

6.多级反馈队列调度

在上面的基础上,允许等待时间过长的进程转移到更高优先级的队列


典型例题

##5.4 考虑下列进程集,进程占用的 CPU 区间长度以毫秒来计算:

进程 区间时间 优先级
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2

假设在时刻 0 以进程 P1,P2,P3,P4,P5 的顺序到达。 a.画出 4 个 Gantt 图分别演示用 FCFS、SJF、非抢占优先级(数字小代表优先级高)和 RR(时间片=1)算法调度时进程的执行过程。 ​ FCFS:P1->P2->P3->P4->P5 SJF:P2->P4->P3->P5->P1 非抢占优先级:P2->P5->P1->P3->P4 RR: P1->P2->P3->P4->P5->P1->P3->P5->P1->P5->P1->P5->P1->P5->P1->P1->P1->P1->P1
b.在 a 里每个进程在每种调度算法下的周转时间是多少? 1.

c.在 a 里每个进程在每种调度算法下的等待时间是多少? d.在 a 里哪一种调度算法的平均等待时间对所有进程而言最小?

答:a.甘特图略 b.周转时间

  FCFS RR SJF 非抢占优先级
P1 10 19 19 16
P2 11 2 1 1
P3 13 7 4 18
P4 14 4 2 19
P5 19 14 9 6

c.等待时间

  FCFS RR SJF 非抢占优先级
P1 0 9 9 6
P2 10 1 0 0
P3 11 5 2 16
P4 13 3 1 18
P5 14 9 4 2

d.SJF平均等待时间最短

##5.5 下面哪些算法会引起饥饿 a.先来先服务 b.最短工作优先调度 c.轮换法调度 d.优先级调度

答:最短工作优先调度和优先级调度算法会引起饥饿 ##5.7

考虑一个运行十个I/O限制任务和一个CPU限制任务的系统。假设,I/O限制任务一次分配给一个I/O操作1毫秒的CPU计算,但每个I/O操作的完成需要 10毫秒。同时,假设间接的上下文切换要0.1毫秒,所有的进程都是长进程。对一个RR调度来说,以下情况时CPU 的利用率是多少:

a.时间片是1毫秒
b.时间片是10毫秒答:

a.时间片是1毫秒:不论是哪个进程被调度,这个调度都会为每一次的上下文切换花费一个0.1毫秒的上下文切换。CPU的利用率是1/1.1*100=92%。

b.时间片是10毫秒:这I/O限制任务会在使用完1毫秒时间片后进行一次上下文切换。这个时间片要求在所有的进程间都走一遍,因此,10*1.1+10.1(因为每个I / O限定任务执行为1毫秒,然后承担上下文切换的任务,而CPU限制任务的执行10毫秒在承担一个上下文切换之前) 。因此,CPU的利用率是20/21.1*100=94%