代码炼金工坊

操作系统概论-进程调度与死锁

功能和时机

进程调度功能由操作系统的 进程调度程序 完成。

按照某种策略和算法 从就绪态进程中为当前空闲的 CPU 选择在其上运行的新进程

调度时机:

调度算法

选择方式和准则

FCFS

先来先服务调度算法。从就绪队列的队首 选择最先到达就绪队列的进程 , 为该进程分配 CPU

一个栗子

进程名进入系统时间开始运行时间服务时间等待时间周转时间
p10024024
p212432326
p322732528

系统平均周转时间$T=\frac{1}{n}\times(T_1+T_2+T_3+…+T_n)=\frac{1}{3}\times(24+26+28)=26$

带权平均周转时间$W=\frac{1}{n}\times(\frac{T_1}{T_{1s}}+\frac{T_2}{T_{2s}}+…+\frac{T_n}{T_{ns}})=\frac{1}{3}\times(\frac{24}{24}+\frac{26}{3}+\frac{28}{3})=6.33$

SPF

短进程优先调度算法。从就绪队列中 选择估计运行时间最短的进程 , 为该进程分配 CPU。

一个栗子

进程名进入系统时间开始运行时间服务时间等待时间周转时间
p12624428
p213325
p300303

系统平均周转时间$T=\frac{1}{n}\times(T_1+T_2+T_3+…+T_n)=\frac{1}{3}\times(28+5+3)=12$

带权平均周转时间$W=\frac{1}{n}\times(\frac{T_1}{T_{1s}}+\frac{T_2}{T_{2s}}+…+\frac{T_n}{T_{ns}})=\frac{1}{3}\times(\frac{28}{24}+\frac{5}{3}+\frac{3}{3})=1.28$

PSL

优先权调度算法。系统将 CPU 分配给就绪队列中 优先权最高的进程

分类:

优先权类型:

存在问题:无穷阻塞(饥饿问题)

解决方案:老化技术(增加等待时间很长的进程的优先权)

RR

时间片轮转调度算法。

系统将所有就绪进程按先来先服务的原则排成一个队列,每次调度时把 CPU 分给队首进程,并令其执行一个时间片。当时间片用完时,调度程序终止当前进程的执行,并将它送到就绪队列的队尾。

把 CPU 的1 s 执行时间划分为多个时间片,每个时间片大小 10-100 ms

现在的分时操作系统基本上都是使用以 RR 为基础结合 PSL 的调度算法。

Linux 2.4 的时间片大小是 50 ms

程序需要的时间 < 时间片大小 ,进程结束,调度。

程序需要的时间 > 时间片大小,时间片用完,执行态->就绪态,调度。

系统对响应时间的要求:响应时间要求越短,时间片越小。

就绪队列中进程的数目:进程数越多,时间片越小。

系统的处理能力:处理能力越小,时间片越小,并发越多。

性能评价

时间片很大,等同于 FCFS

时间片很小,增大了 CPU 对进程切换和调度的开销

多级队列调度算法

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

多级反馈队列调度算法

建立多个优先权不同的就绪队列,每个队列有大小不同的时间片。

队列优先权越高,时间片越短。优先权越低,时间片越长。

实时系统中的调度

基本条件

常用实时调度算法

进程切换

当前正在执行的进程成为被替换进程,让出其所使用的 CPU , 以运行被进程调度程序选中的新进程。

切换步骤

多处理器调度 MPS

类型

进程(线程)调度方式

死锁

定义

多个进程竞争共享资源 而引起的 进程不能向前推进 的僵死状态。

产生的原因和必要条件

原因: 竞争 共享资源且分配资源的 顺序不当

必要条件:

处理死锁的基本方法