0%

CPU调度

CPU调度

基本概念

CPU-I/O区间周期

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

CPU调度程序

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

抢占调度

  • 非抢占调度,一旦CPU分配给一个进程,那么该进程会一直使用CPU直到进程终止或切换到等待状态。

  • 抢占调度,可能一个进程正在运行时,另一个新的进程也到来。而依据调度策略与当前各进程状态,新进程应该先执行。那么,新进程会抢占CPU进行执行,原进程切换到就绪状态。

分派程序

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

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

调度准则

  • 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.多级反馈队列调度

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

写文不易,感谢支持!
Writing is not easy. Thank you for your support.