计算机操作系统(大学课程)第三章.ppt

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,处理机调度与死锁,第三章处理机的调度和死锁,3.1 处理机调度的基本概念,3.1高、中、低三级调度,,1、高级调度（作业调度、长程调度、接纳调度）,,将外存作业调入内存，创建PCB等，插入就绪队列一般用于批处理系统，分/实时系统一般直接入内存，无此环节调度特性,,1.接纳作业数（内存驻留数）,,太多―――> 周转时间T长,,太少―――> 系统效率低,,2.接纳策略：即采用何种调度算法：FCFS、短作业优先等,,,处理机调度的基本概念,（2）,2、低级调度（进程调度，短程调度）,,主要是由分派程序（Dispatcher）分派处理机1.非抢占方式：,,简单，实时性差 (如win31),,2.抢占方式,,（1）时间片原则,,（2）优先权原则,,（3）短作业优先原则3,、中级调度（中程）,,为提高系统吞吐量和内存利用率而引入的一内,------,外存对换功能（换出时，进程为挂起或就绪驻外状态）,,,运行频率：低,>,中,>,高,调度的队列模型,一、仅有进程调度的队列模型,就绪队列,CPU,阻塞队列,交互用户,时间片完,进程调度,进程完成,等待事件,事件出现,调度的队列模型,二、具有高/低级模型,,就绪队列,CPU,阻塞队列,时间片完,进程调度,进程完成,等待事件1,事件1出现,后备队列,阻塞队列,等待事件2,事件2出现,作业调度,三、具有三级调度,就绪队列,CPU,就绪、挂起队列,时间片完,进程调度,进程完成,后备队列,阻塞、挂起队列,事件出现,作业调度,阻塞队列,等待事件,挂起,事件出现,中级调度,交互型作业,选择调度方式和算法的若干准则,一、面向用户的准则,,1．周转时间短（常用于批处理系统）,,概念：作业从提交――> 完成的时间.分为：,,（1）驻外等待调度时间,,（2）驻内等待调度时间,,（3）执行时间,,（4）阻塞时间,,一、面向用户的准则,,平均周转时间,,,,,平均带权,,,,,,,可见带权w越小越好,Ts为实际服务时间。

选择调度方式和算法的若干准则,,一、面向用户的准则,,2．响应时间快：（对交互性作业）,,概念：键盘提交请求到首次响应时间,,（1）输入传送时间,,（2）处理时间,,（3）响应传送时间,,3．截止时间的保证（特别于实时系统）,,4．优先权准则：（即需要抢占调度）,选择调度方式和算法的若干准则,,二、面向系统的准则,,1．吞吐量高（特别于批处理）：单位时间完成作业数,,2．处理机利用率好：（因CPU贵，特别于大中型多用户系统）,,3．各类资源的平衡利用折算标准）,选择调度方式和算法的若干准则,,3.2调度算法——是一个资源分配问题,先来先服务和短作业（进程）优先调度算法,,1.FCFS,,特点：简单，有利于长作业 即CPU繁忙性作业,,2.短作业进程优先调度算法：SJ(P)F,,提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）,,特点：对长作业不利，有可能得不到服务（饥饿）,,估计时间不易确定,,例,进程名,到达时间,服务时间,开始执行时间,完成时间,周转时间,带权周转时间,A,0,1,0,1,1,1,B,1,100,1,101,100,1,C,2,1,101,102,100,100,D,3,100,102,202,199,1.99,图3.4FCFS和SJF比较,,进程名,A B C D E,平均,,到达时间,0 1 2 3 4,,,服务时间,4 3 5 2 4,,FCFS,完成时间,4 7 12 14 18,,,周转时间,4 6 10 11 14,9,,带权周转时间,1 2 2 5.5 3.5,2.8,SJF,完成时间,4 9 18 6 13,,,周转时间,4 8 16 3 9,8,,带权周转时间,1 2.67 3.1 1.5 2.25,2.1,高优先权优先调度算法,1.优先权调度算法类型,,非抢占式优先权算法,,抢占式优先权算法，实时性更好。

2.优先权类型：,,1．静态优先权：,,进程优先权在整个运行期不变确定优先权依据,,（1）进程类型,,（2）进程对资源的需求；,,（3）根据用户需求特点：简单，但低优先权作业可能长期不被调度高优先权优先调度算法(2),2．动态优先权：,,如：优先权随执行时间而下降，随等待时间而升高响应比Rp=（等待时间＋服务时间）/服务时间 作为优先权,,优点：长短兼顾 缺点：需计算Rp,,,3.高响应比优先算法：,,特点：,,响应比Rp=（tw+ts）/ts,,（1）短作业 R,P,大2）ts（要求服务时间）相同的进程间相当于FCFS3）长作业等待一段时间仍能得到服务基于时间片的轮转调度算法,1.时间片轮转,,时间片大小的确定,,太大：退化为FCFS；,,太小：系统开销过大,,系统对响应时间的要求；T=nq,,就绪队列中进程的数目；,,系统的处理能力：（应保证一个时间片处理完常用命令）,,基于时间片的轮转调度算法,2.多级反馈队列调度,,特点：长、短作业兼顾，有较好的响应时间,,（1）短作业一次完成；,,（2）中型作业周转时间不长；,,（3）大型作业不会长期不处理就绪队列1,至CPU,S,1,就绪队列2,S,2,至CPU,就绪队列3,S,3,至CPU,就绪队列n,S,n,至CPU,时间片：S1

4.具有快速切换机制,,具有快速响应外部中断能力快速任务分派,3.3实时调度,实时调度算法的分类,1非抢占式调度算法,,时间片轮转 秒级,,非抢占优先权（协同） 秒~毫秒级,,2抢占式调度算法,,时钟中断抢占优先权 毫秒级,,基于抢占点抢占,,立即抢占immediate preemption 毫秒~微秒级,,只要不在临界区即抢占（中断引发）,,进程1,进程2,进程n,实时进程,调度时间,实时进程要求调度,调度实时进程运行,a 非抢占轮转调度,当前进程,实时进程,实时进程要求调度,当前进程运行完成,b 非抢占优先权调度,调度时间,c 基于时钟中断抢占的优先权抢占调度,当前进程,实时进程,实时进程要求调度,抢占时刻（其它中断）,b 立即抢占优先权调度,当前进程,实时进程,实时进程要求调度,时钟中断到达时,调度时间,调度时间,常用的几种实时调度算法,1.最早截止时间优先EDF（earliest deadline first)算法,,根据任务的截止时间来确定任务的优先级,,截止时间越早，优先级越高,,可以是抢占式或非抢占式,,,最早截止时间优先EDF例,1,3,4,2,1,3,4,2,1,2,3,4,t,开始截止时间,任务到达,任务执行,图3－7 EDF算法用于非抢占调度方式,,2. 最低松弛度优先LLF算法,松弛度：,,若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90,,主要用于可抢占的调度方式中,,例：,,A,1,A,2,A,3,A,4,A,5,A,6,A,7,A,8,B,1,B,2,B,3,0,20,40,60,80,100,120,140,160,t,图3－8 A/B任务每次必须完成的时间,,最低松弛度优先LLF算法(2),A,1,(10),A,2,(10),A,3,(10),A,4,(10),t,0,10,20,30,40,50,60,70,80,t,1,=0,B,1,(20),B,1,(5),B,2,(15),B,2,(10),t,1,t,2,t,3,t,4,t,5,t,6,t,7,t,8,3.4多处理机系统中的调度,,1.紧密耦合MPS和松弛耦合MPS,,紧密耦合,,共享RAM和I/O,,高速总线和交叉开关连接,,松弛耦合,,独立RAM和I/O,,通道和通信线路连接,,2.对称多处理器系统和非对称多处理器系统,,处理器是否结构相同,,进程分配方式,1.SMP中进程分配方式,,静态分配,,动态分配,,可防止系统中多个处理器忙闲不均,,2.非SMP中进程分配方式,,进程调度在主处理器上执行,,有潜在的不可靠性,,,进程（线程）调度方式,,,1.自调度,,各个处理机自行在就绪队列中取任务。

特点；简单，分布式调度，调度算法可采用前述方法，多个CPU利用率都不错（不会闲）,,但：,,瓶颈问题，（单队列）,,低效性；（需拷贝现场）,,线程切换频繁（当线程合作时,各线程并行的条件不容易满足）,,2.成组调度,优点：,,（1）对相互合作的进（线）程组调度，可以减小切换，减小系统开销2）每次分配一组CPU，减少了调度频率分配时间,,（1）面向程序,,（2）面向线程：使处理机利用率更高2.成组调度,,应用程序A,应用程序B,Cpu1,线程1,线程1,Cpu2,线程2,空闲,Cpu3,线程3,空闲,Cpu4,线程4,空闲,时间,1/2,1/2,浪费37.5%,,应用程序A,应用程序B,Cpu1,线程1,线程1,Cpu2,线程2,空闲,Cpu3,线程3,空闲,Cpu4,线程4,空闲,时间,4/5,1/5,浪费15%,3.专用处理机分配,,引入：多处理机系统，每个处理已不再属宝贵资源特点：每个进（线）程专用处理机，使其切换小，提高效率主要用于大型计算，实时系统,,,例 考虑5个进程P1,P2,P3,P4,P5,见表1.规定进程的优先度越小,优先级越高.试描述在采用下述几种调度算法时各个进程的运行过程.并计算采用每种算法时的进程平均周转时间.假设忽略进程的调度时间.,,1、先来先服务调度算法,,2、时间片轮转调度算法(时间片为1ms),,3、非剥夺式SJF调度算法,,4、剥夺式优先级调度算法,表,1,,进程,创建时间,运行时间(ms),优先级,P1,0,3,3,P2,2,6,5,P3,4,4,1,P4,6,5,2,P5,8,2,4,解:,,(1) FCFS调度算法,进程的运行过程如图所示:,,(2) 时间片轮转调度算法,进程的运行情况如图所示:,0~1:p1,,1~2:p2p1,,2~3:p1p2,,3~4:p3p2p1,,4~5:p3p2,,5~6:p4p2p3,,6~7:p3p4p2,,7~8:p5p2p3p4,,8~9:p4p5p2p3,,,(3) 非剥夺式SJF调度算法,进程的运行情况如图所示:,,(4) 剥夺式优先级调度算法,进程的运行情况如图所示:,表2 进程的平均周转时间,,算法,进程名,创建时间,结束时间,周转时间,平均周转时间(ms),FCFS,P1,0,3,3,(3+7+9+12+12)/5=8.60,,P2,2,9,7,,,P3,4,13,9,,,P4,6,18,12,,,P5,8,20,12,,RR,P1,0,4,4,(4+16+13+14+7)/5=10.80,,P2,2,18,16,,,P3,4,17,13,,,P4,6,20,14,,,P5,8,15,7,,非剥夺,,式优先,,级,P1,0,3,3,(3+7+9+12+12)/5=8.60,,P2,2,9,7,,,P3,4,13,9,,,P4,6,18,12,,,P5,8,20,12,,剥夺式,,优先级,P1,0,3,3,(3+18+4+7+7)/5=7.8,,P2,2,20,18,,,P3,4,8,4,,,P4,6,13,7,,,P5,8,15,7,,3.5产生死锁的原因和必要条件,产生死锁的原因。

一、竞争资源引起死锁1．可剥夺（CPU、内存，）和非剥夺性（打印机，磁带机）资源,,2．竞争非剥夺性资源——可造成死锁,p,1,p,2,R,1,R,2,,3.5产生死锁的原因和必要条件,3．竞争临时性资源,,临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源二、进程推进顺序不当引起死锁2,1,3,D,P,2,Req(R,2,),P,2,Req(R,1,),P,1,Req(R,1,),P,1,Req(R,2,),P,2,Rel(R,2,),P,2,Rel(R,1,),P,1,Rel(R,1,),P,1,Rel(R,2,),4,,3.5.2 产生死锁的必要条件,1．互斥条件（资源的临界性）,,2．请求和保持条件,,3．不剥夺条件,,4．环路等待,,处理死锁的基本方法,1．预防；破坏4个条件之一：有效，使资源利用率低2．避免：防止进入不安全态3．检测：检测到死锁再清除4．解除：与“检”配套3.6 死锁预防和避免,3.6.1 死锁预防,,一、互斥条件是资源固有属性，不能避免二、摒弃请求和保持条件,,全分配，全释放（AND）,,缺点：（1）延迟进程运行,,（2）资源严重浪费,,三、摒弃“不剥夺”条件,,增加系统开销，且进程前段工作可能失效。

3.6 死锁预防和避免,3.6.1 死锁预防,,四、摒弃“环路”条件,,有序资源分配法：为资源编号，申请时需按编号进行缺点：,,（1）新增资源不便，（原序号已排定）,,（2）用户不自由,,（3）资源与进程使用顺序不同造成浪费,,3.6.2 避免死锁,方法,：,,,（1）系统的状态：安全和不安全,,（2）进程动态地申请资源，系统对资源预分配，进行安全性的检测系统中描述资源所需的数据结构,,,某类资源：Max,i,：某进程所需的最大资源数,,Allocation,i,：某进程已分配的资源数,,Need,i,：某进程还需要的资源数,,Available,i,：系统中可用的资源数,,Max,i=,Allocation,i,+ Need,i,Available,i,比较,,1. 安全状态,,按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列能找到安全序列的状态为安全状态3.6.2 系统的安全状态（2）,2.安全状态例（,共有12个该类资源）,进程,最大需求,已分配,可用,P1,10,5,3,P2,4,2,,P3,9,2,,安全序列：p2,,p1,,p3,,3.6.2 系统的安全状态（3）,3 安全——不安全的转换,,上例中，若P3再申请一台，则不安全,,进程,最大需求,已分配,可用,P1,10,5,2,P2,4,2,,P3,9,3,,,,安全状态 避免死锁,,不安全状态 可能进入死锁,,不安全状态是否必然导致系统进入死锁？,利用银行家算法避免死锁,,1．数据结构,,available[j]=k: 系统现有Rj类资源k个；,,max[i,j]=k: 进程i需要Rj的最大数k个；,,alloc[i,j]=k: 进程i已得到Rj类资源k个；,,need[i,j]=k: 进程i需要Rj类资源k个,,有：need[i,j]= max[i,j]－alloc[i,j],,Requesti：进程i请求资源数,,worki：进程i执行完后系统应有资源数（也即可用数）,,finish[i]：布尔量，表进程i能否顺序完成。

利用银行家算法避免死锁,2．,银行家算法,req,i,<=need,i,error,req,i,<=avail,i,block,利用银行家算法避免死锁,avail=avail-req,i,,alloc,i,=alloc,i,+req,i,,need,i,=need,i,-req,i,finish[i]=.F.,,need,i,<=work,work=work+alloc,i,,finish[i]=.T.,预分配,安全性检测,4实例,（五个进程，三类资源，资源数量分别为10、5、7）,,Max,,A B C,Allocation,,A B C,Need,,A B C,Available,,A B C,p0,7 5 3,0 1 0,7 4 3,3 3 2,,(2 3 0),p1,,3 2 2,2 0 0,,(3 0 2),1 2 2,,(0 2 0),,p2,9 0 2,3 0 2,6 0 0,,p3,2 2 2,2 1 1,0 1 1,,p4,4 3 3,0 0 2,4 3 1,,T0时刻的资源分配表,4实例,,Work,,A B C,Need,,A B C,Alloc,,A B C,Work+alloc,,A B C,Finish,p1,3 3 2,1 2 2,2 0 0,5 3 2,true,p3,5 3 2,0 1 1,2 1 1,7 4 3,true,p4,7 4 3,4 3 1,0 0 2,7 4 5,true,p2,7 4 5,6 0 0,3 0 2,10 4 7,true,p0,10 4 7,7 4 3,0 1 0,10 5 7,true,T0时刻的安全序列,4实例,,Work,,A B C,Need,,A B C,Alloc,,A B C,Work+alloc,,A B C,Finish,p1,2 3 0,0 2 0,3 0 2,5 3 2,true,p3,5 3 2,0 1 1,2 1 1,7 4 3,true,p4,7 4 3,4 3 1,0 0 2,7 4 5,true,p0,7 4 5,7 4 3,0 1 0,7 5 5,true,p2,7 5 5,6 0 0,3 0 2,10 5 7,true,P1申请资源(1,0,2)时安全性检查(安全),4实例,,Allocation,,A B C,Need,,A B C,Available,,A B C,p0,0 3 0,7 2 3,2 1 0,p1,3 0 2,0 2 0,,p2,3 0 2,6 0 0,,p3,2 1 1,0 1 1,,p4,0 0 2,4 3 1,,为P0分配（0，2，0）后的情况（不安全）,练习,,考虑一共有150个存储单元的系统,内存的分配情况如下:,,进程 Max Allocation,,P1 70 45,,P2 60 40,,P3 60 15,,使用银行家算法,以确定是否可以同意下面的任一请求:,,(1)P4到达系统,最多需要60个存储单元,最初需要25个单元;,,(2)P4到达系统,最多需要60个存储单元,最初需要35个单元;,,练习,,(1)3个进程共享4个同种类型的资源,每个进程最大需要2个资源,请问该系统是否会因为竞争该资源而死锁?,,(2)n个进程共享m个同类资源,若每个进程都需要用该类资源,而且各进程对该类资源的最大需求量之和小于m+n.说明该系统不会因竞争该类资源而阻塞.,,(3)在(2)中,如果没有“每个进程都需要用该类资源”的限制,情况又会如何?,,解:,,(1),该系统不会因为竞争该类资源而死锁.因为,必有一个进程可获得2个资源,故能顺利完成,并释放其所占用的2个资源给其他进程使用,使他们也顺利完成.,,(2)用Maxi,Needi和Allocationi来分别表示第i个进程对该类资源的最大需求量,还需要量和已分配到的量,根据题意它们将满足下述条件:,,Needi>0(对所有i),,∑Maxi

定理：死锁状态的充分条件，资源分配图不可完全简化,,3.检测死锁的算法：,Work= available,,L:={Li| alloc,i,=0 req,i,=0} (,孤立进程点,),,For all L,i,L do,,Begin,,For all req,i,<=work do,,Begin,,Work=work+alloc,i,,L=L,i,∪,L,,end,,End,,Deadlock= ~(L={p,1,… p,n,}),3.7,死锁的检测和解除,解除,检测到死锁后，回退到上一状态（要进行资源剥夺，且需保存以前状态的分配信息），重新分配，若不行，继续回退……，,,。