欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

操作系统原理之进程调度与死锁(三)

程序员文章站 2022-04-10 15:42:30
先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。 当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪队列 ......

一、进程调度的功能与时机

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

具体任务:按照某种策略和算法从就绪态进程中为当前空闲的cpu选择在其上运行的新进程。

进程调度的时机:进程正常或异常结束、进程阻塞、有更高优先级进程到来、时间⽚用完时都会导致进程调度。


二、进程调度算法

什么样的算法是好的算法?

  • 周转时间短:作业从提交给系统开始,到作业完成,花费时间短

         操作系统原理之进程调度与死锁(三)

               操作系统原理之进程调度与死锁(三)

 

  • 响应时间快:从用户提交作业开始,到系统开始响应,花费时间短
  • 截止时间的保证:保证作业在“开始截止时间”前开始,在“完成截止时间”前完成
  • 系统吞吐量高:系统在单位时间内完成的作业量多
  • 处理机利用率好:cpu的利用率尽可能高

进程调度算法:

先来先服务调度算法(fcfs) :从就绪队列的队首选择最先到达就绪队列的进程,为该进程分配cpu

操作系统原理之进程调度与死锁(三)

周转时间=进程的周转时间

系统平均周转时间=所有进程的周转时间之和,然后除以进程个数

 带全平均周转时间w=每个进程的周转时间除以该进程的服务时间,然后相加,最后除以进程个数

缺点:服务时间段的进程等待时间较长,整个周转时间较长。

 

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

操作系统原理之进程调度与死锁(三)

 优点 :与fcfs算法相比,短进程优先算法能有效降低进程的平均等待时间,提高系统吞吐量

  缺点: 对长进程不利;不能保证紧迫进程的处理;进程长短由用户估计,不一定准确。


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

  • 非抢占式:运行期间,有更高优先权的进程到来,也不能剥夺cpu
  • 抢占式:运行期间,有更高优先权的进程到来,就可以抢占cpu

优先权类型

  • 静态优先权:创建时确定,运行期间保持不变 
  • 动态优先权:创建时确定,随着进程推进或等待时间增加而改变

该算法存在的问题:无穷阻塞(饥饿问题);解决的方案(老化技术):增加等待时间很长的进程的优先权 

时间片轮转调度算法(rr):

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

操作系统原理之进程调度与死锁(三)

 

 

1、时间片⼤小确定时

t=nq       t:系统响应时间        n:进程数量     q:时间片

  • 系统对响应时间的要求:响应时间要求越短,时间片越小
  • 就绪队列中进程的数目:进程数量越多,时间片越小
  • 系统的处理能力:处理能力越好,时间片越小

【例】进程a、b、c、d需要运行的时间分别为20ms、10 ms、15 ms、5 ms,均在0时刻到达。到达的先后次序为a、b、c、d。如果时间片分别为1 ms和5ms,计算各个进程的带权周转时间和平均带权周转时间。

操作系统原理之进程调度与死锁(三)

 

 

 


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

优先级高队列  p1 、p2、 p3 、p4     

优先级低队列  p5、 p6 、p7             


多级反馈队列调度算法建立多个优先权不同的就绪队列,每个队列有大小不同的时间片

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

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

 

 三、实时系统中的调度

实现实时调度的基本条件:

1、提供必要的调度信息:就绪时间 、开始截止时间 、完成截止时间、处理时间、 资源要求 、优先级

2、系统处理能力强:假定系统中有m个周期性的实时进程,它们的处理时间可表示为ci,周期时间表示为pi,则在单处理机情况下,必须满足如下公式的限制条件:

操作系统原理之进程调度与死锁(三)

 

 

3、采用抢占式调度机制(使用最广泛的方式)

4、具有快速切换机制:   对外部中断的快速响应能力    快速的进程切换能力

 

常用的实时调度算法

 1、最早截止时间优先算法edf(淘宝&京东):开始截止时间越早,进程优先级越高,越优先获得cpu

 

 2、最低松弛度优先算法llf:根据实时进程的紧迫程度来进行调度的算法

操作系统原理之进程调度与死锁(三)

 

 

 

 


四、进程切换


五、 多处理器调度


六、 死锁