操作系统课件 第三章【专业教育】.ppt

《操作系统课件 第三章【专业教育】.ppt》由会员分享，可在线阅读，更多相关《操作系统课件 第三章【专业教育】.ppt（66页珍藏版）》请在三一文库上搜索。

1、第三章处理机的调度和死锁,3.1 处理机调度的基本概念,3.1高、中、低三级调度 1、高级调度（作业调度、长程调度、接纳调度） 将外存作业调入内存，创建PCB等，插入就绪队列。 一般用于批处理系统，分/实时系统一般直接入内存，无此环节。 调度特性 1.接纳作业数（内存驻留数） 太多周转时间T长 太少系统效率低 2.接纳策略：即采用何种调度算法：FCFS、短作业优先等,处理机调度的基本概念（2）,2、低级调度（进程调度，短程调度） 主要是由分派程序（Dispatcher）分派处理机。 1.非抢占方式： 简单，实时性差 (如win31) 2.抢占方式 （1）时间片原则 （2）优先权原则 （3）短作

2、业优先原则。,3、中级调度（中程） 为提高系统吞吐量和内存利用率而引入的一内-外存对换功能（换出时，进程为挂起或就绪驻外状态） 运行频率：低中高。,3.1.2调度的队列模型,一、仅有进程调度的队列模型,就绪队列,CPU,阻塞队列,交互用户,时间片完,进程调度,进程完成,等待事件,事件出现,3.1.2调度的队列模型,二、具有高/低级模型,就绪队列,CPU,阻塞队列,时间片完,进程调度,进程完成,等待事件1,事件1出现,后备队列,阻塞队列,等待事件2,事件2出现,作业调度,三、具有三级调度,就绪队列,CPU,就绪、挂起队列,时间片完,进程调度,进程完成,后备队列,阻塞、挂起队列,事件出现,作业调度

3、,阻塞队列,等待事件,挂起,事件出现,中级调度,交互型作业,3.1.3选择调度方式和算法的若干准则,一、面向用户的准则 1周转时间短（常用于批处理系统） 概念：作业从提交 完成的时间.分为： （1）驻外等待调度时间 （2）驻内等待调度时间 （3）执行时间 （4）阻塞时间,一、面向用户的准则 平均周转时间 平均带权 可见带权w越小越好,Ts为实际服务时间。,3.1.3选择调度方式和算法的若干准则,一、面向用户的准则 2响应时间快：（对交互性作业） 概念：键盘提交请求到首次响应时间 （1）输入传送时间 （2）处理时间 （3）响应传送时间 3截止时间的保证（特别于实时系统） 4优先权准则：（即需要抢

4、占调度）,3.1.3选择调度方式和算法的若干准则,二、面向系统的准则 1吞吐量高（特别于批处理）：单位时间完成作业数 2处理机利用率好：（因CPU贵，特别于大中型多用户系统） 3各类资源的平衡利用。（？折算标准）,3.1.3选择调度方式和算法的若干准则,3.2调度算法是一个资源分配问题,3.2.1先来先服务和短作业（进程）优先调度算法 1.FCFS 特点：简单，有利于长作业 即CPU繁忙性作业 2.短作业进程优先调度算法：SJ(P)F 提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量） 特点：对长作业不利，有可能得不到服务（饥饿） 估计时间不易确定,例,图3.4FCFS和SJF比较,

5、3.2.2高优先权优先调度算法,1.优先权调度算法类型 非抢占式优先权算法 抢占式优先权算法，实时性更好。 2.优先权类型： 1静态优先权： 进程优先权在整个运行期不变。 确定优先权依据 （1）进程类型 （2）进程对资源的需求； （3）根据用户需求。 特点：简单，但低优先权作业可能长期不被调度。,3.2.2高优先权优先调度算法(2),2动态优先权： 如：优先权随执行时间而下降，随等待时间而升高。 响应比Rp=（等待时间服务时间）/服务时间 作为优先权 优点：长短兼顾 缺点：需计算Rp 3.高响应比优先算法： 特点： 响应比Rp=（tw+ts）/ts （1）短作业 RP大。 （2）ts（要求服务

6、时间）相同的进程间相当于FCFS。 （3）长作业等待一段时间仍能得到服务。,3.2.3基于时间片的轮转调度算法,1.时间片轮转 时间片大小的确定 太大：退化为FCFS； 太小：系统开销过大 系统对响应时间的要求；T=nq 就绪队列中进程的数目； 系统的处理能力：（应保证一个时间片处理完常用命令）,3.2.3基于时间片的轮转调度算法,2.多级反馈队列调度 特点：长、短作业兼顾，有较好的响应时间 （1）短作业一次完成； （2）中型作业周转时间不长； （3）大型作业不会长期不处理。,就绪队列1,至CPU,S1,就绪队列2,S2,至CPU,就绪队列3,S3,至CPU,就绪队列n,Sn,至CPU,时间片

7、：S1S2S3,图35多级队列反馈调度算法,3.3.1实现实时调度的基本条件 1提供必要的调度信息 （1）就绪时间； （2）开始/完成截止时间； （3）处理时间； （4）资源要求； （5）优先级； 2系统处理能力强,3.3实时调度,Ci为处理时间，Pi为周期时间（基于周期性实时任务）,3.3.1实现实时调度的基本条件 3.采用抢占调度方式 剥夺方式：一般都采用此 非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。 4.具有快速切换机制 具有快速响应外部中断能力。 快速任务分派,3.3实时调度,3.3.2实时调度算法的分类,1非抢占式调度算法 时间片轮转 秒级 非抢占优先权（协同）

8、 秒毫秒级 2抢占式调度算法 时钟中断抢占优先权 毫秒级 基于抢占点抢占 立即抢占immediate preemption 毫秒微秒级 只要不在临界区即抢占（中断引发）,进程1,进程2,进程n,实时进程,调度时间,实时进程要求调度,调度实时进程运行,a 非抢占轮转调度,当前进程,实时进程,实时进程要求调度,当前进程运行完成,b 非抢占优先权调度,调度时间,c 基于时钟中断抢占的优先权抢占调度,当前进程,实时进程,实时进程要求调度,抢占时刻（其它中断）,b 立即抢占优先权调度,当前进程,实时进程,实时进程要求调度,时钟中断到达时,调度时间,调度时间,3.3.3常用的几种实时调度算法,1.最早截止

9、时间优先EDF（earliest deadline first)算法 根据任务的截止时间来确定任务的优先级 截止时间越早，优先级越高 可以是抢占式或非抢占式,最早截止时间优先EDF例,1,3,4,2,1,3,4,2,1,2,3,4,t,开始截止时间,任务到达,任务执行,图37 EDF算法用于非抢占调度方式,2. 最低松弛度优先LLF算法,松弛度： 若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：2001001090 主要用于可抢占的调度方式中 例：,A1,A2,A3,A4,A5,A6,A7,A8,B1,B2,B3,0,20,40,60,80,100,

10、120,140,160,t,图38 A/B任务每次必须完成的时间,最低松弛度优先LLF算法(2),A1(10),A2(10),A3(10),A4(10),t,0,10,20,30,40,50,60,70,80,t1=0,B1(20),B1(5),B2(15),B2(10),t1,t2,t3,t4,t5,t6,t7,t8,3.4多处理机系统中的调度,1.紧密耦合MPS和松弛耦合MPS 紧密耦合 共享RAM和I/O 高速总线和交叉开关连接 松弛耦合 独立RAM和I/O 通道和通信线路连接 2.对称多处理器系统和非对称多处理器系统 处理器是否结构相同,3.4.2进程分配方式,1.SMP中进程分配方式

11、 静态分配 动态分配 可防止系统中多个处理器忙闲不均 2.非SMP中进程分配方式 进程调度在主处理器上执行 有潜在的不可靠性,3.4.3进程（线程）调度方式,1.自调度 各个处理机自行在就绪队列中取任务。 特点；简单，分布式调度，调度算法可采用前述方法，多个CPU利用率都不错（不会闲） 但： 瓶颈问题，（单队列） 低效性；（需拷贝现场） 线程切换频繁（当线程合作时,各线程并行的条件不容易满足）,2.成组调度,优点： （1）对相互合作的进（线）程组调度，可以减小切换，减小系统开销。 （2）每次分配一组CPU，减少了调度频率。 分配时间 （1）面向程序 （2）面向线程：使处理机利用率更高。,2.成

12、组调度,浪费37.5%,浪费15%,3.专用处理机分配,引入：多处理机系统，每个处理已不再属宝贵资源。 特点：每个进（线）程专用处理机，使其切换小，提高效率。 主要用于大型计算，实时系统,例 考虑5个进程P1,P2,P3,P4,P5,见表1.规定进程的优先度越小,优先级越高.试描述在采用下述几种调度算法时各个进程的运行过程.并计算采用每种算法时的进程平均周转时间.假设忽略进程的调度时间. 1、先来先服务调度算法 2、时间片轮转调度算法(时间片为1ms) 3、非剥夺式SJF调度算法 4、剥夺式优先级调度算法,表1,解: (1) FCFS调度算法,进程的运行过程如图所示:,(2) 时间片轮转调度算

13、法,进程的运行情况如图所示:,01:p1 12:p2p1 23:p1p2 34:p3p2p1 45:p3p2 56:p4p2p3 67:p3p4p2 78:p5p2p3p4 89:p4p5p2p3,(3) 非剥夺式SJF调度算法,进程的运行情况如图所示:,(4) 剥夺式优先级调度算法,进程的运行情况如图所示:,表2 进程的平均周转时间,3.5产生死锁的原因和必要条件,3.5.1产生死锁的原因。 一、竞争资源引起死锁。 1可剥夺（CPU、内存，）和非剥夺性（打印机，磁带机）资源 2竞争非剥夺性资源可造成死锁,p1,p2,R1,R2,3.5产生死锁的原因和必要条件,3竞争临时性资源 临时性资源是指

14、由一个进程产生，被另一个进程使用一段时间后便无用的资源。,二、进程推进顺序不当引起死锁。,2,1,3,D,P2Req(R2),P2Req(R1),P1Req(R1),P1Req(R2),P2Rel(R2),P2Rel(R1),P1Rel(R1),P1Rel(R2),4,3.5.2 产生死锁的必要条件,1互斥条件（资源的临界性） 2请求和保持条件 3不剥夺条件 4环路等待,3.5.3处理死锁的基本方法,1预防；破坏4个条件之一：有效，使资源利用率低。 2避免：防止进入不安全态。 3检测：检测到死锁再清除。 4解除：与“检”配套。,3.6 死锁预防和避免,3.6.1 死锁预防 一、互斥条件是资源固

15、有属性，不能避免。 二、摒弃请求和保持条件 全分配，全释放（AND） 缺点：（1）延迟进程运行 （2）资源严重浪费 三、摒弃“不剥夺”条件 增加系统开销，且进程前段工作可能失效。,3.6 死锁预防和避免,3.6.1 死锁预防 四、摒弃“环路”条件 有序资源分配法：为资源编号，申请时需按编号进行。 缺点： （1）新增资源不便，（原序号已排定） （2）用户不自由 （3）资源与进程使用顺序不同造成浪费,3.6.2 避免死锁,方法： （1）系统的状态：安全和不安全 （2）进程动态地申请资源，系统对资源预分配，进行安全性的检测。,系统中描述资源所需的数据结构 某类资源：Maxi：某进程所虚的最大资源数

16、Allocationi：某进程已分配的资源数 Needi：某进程还需要的资源数 Available i：系统中可用的资源数 Maxi= Allocationi + Needi Available i,比较,1. 安全状态 按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。 能找到安全序列的状态为安全状态。,3.6.2 系统的安全状态（2）,2.安全状态例（共有12个该类资源）,安全序列：p2p1p3,3.6.2 系统的安全状态（3）,3 安全不安全的转换 上例中，若P3再申请一台，则不安全,安全状态 避免死锁 不安全状态 可能进入死锁 不安全状态是否必然导致系统进入死锁？,3.

17、6.3利用银行家算法避免死锁,1数据结构 availablej=k: 系统现有Rj类资源k个； maxi,j=k: 进程i需要Rj的最大数k个； alloci,j=k: 进程i已得到Rj类资源k个； needi,j=k:进程i需要Rj类资源k个 有：needi,j= maxi,jalloci,j Requesti：进程i请求资源数 worki：进程i执行完后系统应有资源数（也即可用数） finishi：布尔量，表进程i能否顺序完成。,3.6.3利用银行家算法避免死锁,2银行家算法,reqi=needi,error,reqi=availi,block,3.6.3利用银行家算法避免死锁,avail

18、=avail-reqi alloci=alloci+reqi needi=needi-reqi,finishi=.F. needi=work,work=work+alloci finishi=.T.,预分配,安全性检测,4实例（五个进程，三类资源，资源数量分别为10、5、7）,T0时刻的资源分配表,4实例,T0时刻的安全序列,4实例,P1申请资源(1,0,2)时安全性检查(安全),4实例,为P0分配（0，2，0）后的情况（不安全）,例,(1)3个进程共享4个同种类型的资源,每个进程最大需要2个资源,请问该系统是否会因为竞争该资源而死锁? (2)n个进程共享m个同类资源,若每个进程都需要用该类资

19、源,而且各进程对该类资源的最大需求量之和小于m+n.说明该系统不会因竞争该类资源而阻塞. (3)在(2)中,如果没有“每个进程都需要用该类资源”的限制,情况又会如何?,解: (1)该系统不会因为竞争该类资源而死锁.因为,必有一个进程可获得2个资源,故能顺利完成,并释放其所占用的2个资源给其他进程使用,使他们也顺利完成. (2)用Maxi,Needi和Allocationi来分别表示第i个进程对该类资源的最大需求量,还需要量和已分配到的量,根据题意它们将满足下述条件: Needi0(对所有i) Maxim+n 若系统已因竞争该类资源而进入死锁状态,则意味着已有一个以上的进程因申请不到该类资源而无

20、限阻塞,而m个资源肯定已全部分配出去,即, Allocationi=m 因此 Needi= Maxi- Allocationim+n-m 即 Needin 这样,至少必须存在一个进程,其Needi0,这显然与题意不符,所以该系统不可能因竞争该类资源而进入死锁状态. (3)此时系统可能发生死锁,如n=4,m=3时,若P1的Max为0 ,而其余三个进程的Max都为2,则任然满足最大需求量之和(即6)小于m+n(即7)的要求,但当除P1以外的其余三个进程各得到一个资源时.这三个进程将进入死锁状态.,3.7死锁的检测和解除,3.7.1检测 1.资源分配图,p1,p2,3.7死锁的检测和解除,2.死锁定理 简化资源分配图 若能完全简化则消去所有的边。 定理：死锁状态的充分条件，资源分配图不可完全简化 3.检测死锁的算法：,Work= available L:=Li| alloci=0 reqi=0 (孤立进程点) For all Li L do Begin For all reqi =work do Begin Work=work+alloci L=LiL end End Deadlock= (L=p1 pn),3.7死锁的检测和解除,解除,检测到死锁后，回退到上一状态（要进行资源剥夺，且需保存以前状态的分配信息），重新分配，若不行，继续回退，,