【文档说明】计算机操作系统(大学课程)第三章课件.ppt，共(67)页，891.012 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-76764.html

以下为本文档部分文字说明：

第三章处理机的调度和死锁3.1处理机调度的基本概念3.1高、中、低三级调度1、高级调度（作业调度、长程调度、接纳调度）▪将外存作业调入内存，创建PCB等，插入就绪队列。▪一般用于批处理系统，分/实时系统一般直接入内存，

无此环节。٭调度特性▪1.接纳作业数（内存驻留数）太多―――>周转时间T长太少―――>系统效率低▪2.接纳策略：即采用何种调度算法：FCFS、短作业优先等处理机调度的基本概念（2）2、低级调度（进程调度，短程调度）主要

是由分派程序（Dispatcher）分派处理机。٭1.非抢占方式：简单，实时性差(如win31)٭2.抢占方式（1）时间片原则（2）优先权原则（3）短作业优先原则。3、中级调度（中程）为提高系统吞吐量和内存利用率而引入的一内------外存对换功能（换出时，进程为挂起或就绪驻

外状态）运行频率：低>中>高。3.1.2调度的队列模型一、仅有进程调度的队列模型就绪队列CPU阻塞队列交互用户时间片完进程调度进程完成等待事件事件出现3.1.2调度的队列模型二、具有高/低级模型就绪队

列CPU阻塞队列时间片完进程调度进程完成等待事件1事件1出现后备队列阻塞队列等待事件2事件2出现作业调度三、具有三级调度就绪队列CPU就绪、挂起队列时间片完进程调度进程完成后备队列阻塞、挂起队列事件出现作业调度阻塞队列等

待事件挂起事件出现中级调度交互型作业3.1.3选择调度方式和算法的若干准则一、面向用户的准则٭1．周转时间短（常用于批处理系统）▪概念：作业从提交――>完成的时间.分为：▪（1）驻外等待调度时间▪（2）驻内等待调度时间▪（3）执行

时间▪（4）阻塞时间一、面向用户的准则٭平均周转时间٭平均带权٭可见带权w越小越好,Ts为实际服务时间。3.1.3选择调度方式和算法的若干准则][11niiTnT][11nisiTTnW一、面向用户的准则٭2．响应时间快：（对交互性作业）▪概念：键盘提交

请求到首次响应时间▪（1）输入传送时间▪（2）处理时间▪（3）响应传送时间٭3．截止时间的保证（特别于实时系统）٭4．优先权准则：（即需要抢占调度）3.1.3选择调度方式和算法的若干准则二、面向系统的

准则٭1．吞吐量高（特别于批处理）：单位时间完成作业数٭2．处理机利用率好：（因CPU贵，特别于大中型多用户系统）٭3．各类资源的平衡利用。（？折算标准）3.1.3选择调度方式和算法的若干准则3.2调度算法——是一个资源分配问题3.2.1先来先服务和短作业（进程）优

先调度算法٭1.FCFS▪特点：简单，有利于长作业即CPU繁忙性作业٭2.短作业进程优先调度算法：SJ(P)F▪提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）▪特点：对长作业不利，有可能得不到服

务（饥饿）▪估计时间不易确定例进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99图3.4FCFS

和SJF比较进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.13.2.2高优先权优先调度算法

1.优先权调度算法类型٭非抢占式优先权算法٭抢占式优先权算法，实时性更好。2.优先权类型：٭1．静态优先权：▪进程优先权在整个运行期不变。▪确定优先权依据–（1）进程类型–（2）进程对资源的需求；–（3）根据用户需求。▪特点：简单，但低优先权作业可能长期不被调度。3.2.2高优先权优先调

度算法(2)2．动态优先权：٭如：优先权随执行时间而下降，随等待时间而升高。٭响应比Rp=（等待时间＋服务时间）/服务时间作为优先权٭优点：长短兼顾缺点：需计算Rp3.高响应比优先算法：٭特点：٭响应比Rp=（tw+ts）/ts٭（1）短作业RP大。

٭（2）ts（要求服务时间）相同的进程间相当于FCFS。٭（3）长作业等待一段时间仍能得到服务。3.2.3基于时间片的轮转调度算法1.时间片轮转٭时间片大小的确定▪太大：退化为FCFS；▪太小：系统开销过大٭系统对响应时间的要求；

T=nq٭就绪队列中进程的数目；٭系统的处理能力：（应保证一个时间片处理完常用命令）3.2.3基于时间片的轮转调度算法2.多级反馈队列调度٭特点：长、短作业兼顾，有较好的响应时间▪（1）短作业一次完成；▪（2）中型作业周转时间不长；▪（3）大型作业不会长期不处理。就

绪队列1至CPUS1就绪队列2S2至CPU就绪队列3S3至CPU就绪队列nSn至CPU时间片：S1<S2<S3图3－5多级队列反馈调度算法3.3.1实现实时调度的基本条件٭1．提供必要的调度信息▪（1）就

绪时间；▪（2）开始/完成截止时间；▪（3）处理时间；▪（4）资源要求；▪（5）优先级；٭2．系统处理能力强3.3实时调度NPCPCmiiimiii111Ci为处理时间，Pi为周期时间（基于周期性实时任务）3.3.1实现实时调度的基本条

件٭3.采用抢占调度方式▪剥夺方式：一般都采用此▪非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。٭4.具有快速切换机制▪具有快速响应外部中断能力。▪快速任务分派3.3实时调度3.3.2实时调度算法的分类1非抢占式调度算法٭时间片轮转秒级٭非抢占优先权（协同）秒~毫秒

级2抢占式调度算法٭时钟中断抢占优先权毫秒级▪基于抢占点抢占٭立即抢占immediatepreemption毫秒~微秒级▪只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间实时进程要求调度调度实时进程运行a非抢占轮转调度当前进程实时进程实时进程要求调度当前进程运行完

成b非抢占优先权调度调度时间c基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程要求调度抢占时刻（其它中断）b立即抢占优先权调度当前进程实时进程实时进程要求调度时钟中断到达时调度时间调度时间3.

3.3常用的几种实时调度算法1.最早截止时间优先EDF（earliestdeadlinefirst)算法٭根据任务的截止时间来确定任务的优先级٭截止时间越早，优先级越高٭可以是抢占式或非抢占式最早截止时间优先EDF例1342

13421234t开始截止时间任务到达任务执行图3－7EDF算法用于非抢占调度方式2.最低松弛度优先LLF算法松弛度：٭若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：

200－100－10＝90٭主要用于可抢占的调度方式中٭例：A1A2A3A4A5A6A7A8B1B2B3020406080100120140160t图3－8A/B任务每次必须完成的时间最低松弛度优先LLF算法(2)A1(10)A2(10)A3(10)A4(10

)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t83.4多处理机系统中的调度1.紧密耦合MPS和松弛耦合MPS٭紧密耦合▪共享RAM和I/O▪高速总线和交叉开关连接٭松弛耦合▪独立RAM和

I/O▪通道和通信线路连接2.对称多处理器系统和非对称多处理器系统٭处理器是否结构相同3.4.2进程分配方式1.SMP中进程分配方式٭静态分配٭动态分配▪可防止系统中多个处理器忙闲不均2.非SMP中进程分配方式٭进程调度在主处理器上执行٭有潜在的不可靠性3.4.3进程（线

程）调度方式1.自调度٭各个处理机自行在就绪队列中取任务。٭特点；简单，分布式调度，调度算法可采用前述方法，多个CPU利用率都不错（不会闲）٭但：▪瓶颈问题，（单队列）▪低效性；（需拷贝现场）▪线程切换频繁（当线程合作时,各线程并行的条件不容易满足）2.成组调度

优点：（1）对相互合作的进（线）程组调度，可以减小切换，减小系统开销。（2）每次分配一组CPU，减少了调度频率。分配时间（1）面向程序（2）面向线程：使处理机利用率更高。2.成组调度应用程序A应用程序BCpu1线程1线程1Cpu2线

程2空闲Cpu3线程3空闲Cpu4线程4空闲时间1/21/2浪费37.5%应用程序A应用程序BCpu1线程1线程1Cpu2线程2空闲Cpu3线程3空闲Cpu4线程4空闲时间4/51/5浪费15%3.专用处理机分配引入：多处理机系统，每个处理已不再属宝贵资源。特点：

每个进（线）程专用处理机，使其切换小，提高效率。主要用于大型计算，实时系统例考虑5个进程P1,P2,P3,P4,P5,见表1.规定进程的优先度越小,优先级越高.试描述在采用下述几种调度算法时各个进程的运行过程.并计算采用每

种算法时的进程平均周转时间.假设忽略进程的调度时间.1、先来先服务调度算法2、时间片轮转调度算法(时间片为1ms)3、非剥夺式SJF调度算法4、剥夺式优先级调度算法表1进程创建时间运行时间(ms)优先级P103

3P2265P3441P4652P5824解:(1)FCFS调度算法,进程的运行过程如图所示:(2)时间片轮转调度算法,进程的运行情况如图所示:0~1:p11~2:p2p12~3:p1p23~4:p3p2p14~5:p3p25~6:p4p2p36~7:p3p4p27~8:

p5p2p3p48~9:p4p5p2p3(3)非剥夺式SJF调度算法,进程的运行情况如图所示:(4)剥夺式优先级调度算法,进程的运行情况如图所示:表2进程的平均周转时间算法进程名创建时间结束时间周转时间平均周转时间(ms)F

CFSP1033(3+7+9+12+12)/5=8.60P2297P34139P461812P582012RRP1044(4+16+13+14+7)/5=10.80P221816P341713P462014P58157非剥夺式优先级P1033(3+7+9+12+12)/5=8

.60P2297P34139P461812P582012剥夺式优先级P1033(3+18+4+7+7)/5=7.8P222018P3484P46137P581573.5产生死锁的原因和必要条件3.5.1产生死锁的原因。一

、竞争资源引起死锁。٭1．可剥夺（CPU、内存，）和非剥夺性（打印机，磁带机）资源٭2．竞争非剥夺性资源——可造成死锁p1p2R1R23.5产生死锁的原因和必要条件3．竞争临时性资源٭临时性资源是指由一个进程产生，被另一个进程使用一段

时间后便无用的资源。二、进程推进顺序不当引起死锁。213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)43.

5.2产生死锁的必要条件1．互斥条件（资源的临界性）2．请求和保持条件3．不剥夺条件4．环路等待3.5.3处理死锁的基本方法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）进程动态地申请资源，系统对资源预分配，进行安全性的检测。系统中描述资源所需的数据结构某类资源：Maxi：某进程所需的最大资源数Allocationi：某进程已分配的资源数Needi：某进程还需要的资源数Availablei：系统中可用的资源数Maxi=Allocatio

ni+NeediAvailablei比较1.安全状态٭按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。٭能找到安全序列的状态为安全状态。3.6.2系统的安全状态（2）2.安全状态例（共有12个该类资源）进程最大需求已分配可用P110

53P242P392安全序列：p2p1p33.6.2系统的安全状态（3）3安全——不安全的转换٭上例中，若P3再申请一台，则不安全进程最大需求已分配可用P11052P242P393安全状态避免死锁不安全状态可能进入死锁不安全状态是否必然

导致系统进入死锁？3.6.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能否顺序完成。3.6.3利用银行家

算法避免死锁2．银行家算法reqi<=needierrorreqi<=availiblock3.6.3利用银行家算法避免死锁avail=avail-reqialloci=alloci+reqineedi=needi-reqifinish[i]=.F.needi<=

workwork=work+allocifinish[i]=.T.预分配安全性检测4实例（五个进程，三类资源，资源数量分别为10、5、7）MaxABCAllocationABCNeedABCAvailable

ABCp0753010743332(230)p1322200(302)122(020)p2902302600p3222211011p4433002431T0时刻的资源分配表4实例WorkABCNeedABCAlloc

ABCWork+allocABCFinishp1332122200532truep3532011211743truep4743431002745truep27456003021047truep010477430101057trueT0时刻的安全序列4实例WorkABCNeedABCAl

locABCWork+allocABCFinishp1230020302532truep3532011211743truep4743431002745truep0745743010755truep27556003021057trueP1申

请资源(1,0,2)时安全性检查(安全)4实例AllocationABCNeedABCAvailableABCp0030723210p1302020p2302600p3211011p4002431为P0分配（0，2，0）后的情况（不安

全）处理机调度与死锁练习考虑一共有150个存储单元的系统,内存的分配情况如下:进程MaxAllocationP17045P26040P36015使用银行家算法,以确定是否可以同意下面的任一请求:(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<m+n若系统已因竞争该类资源而进入死锁状态,则意味着已有一个以上的进程因申请不到该类资源而无限阻塞,而m个资源肯定已全部分配出去,即∑Allocationi=m因此∑Needi=∑Maxi-∑Allocationi<m+

n-m即∑Needi<n这样,至少必须存在一个进程,其Needi≦0,这显然与题意不符,所以该系统不可能因竞争该类资源而进入死锁状态.(3)此时系统可能发生死锁,如n=4,m=3时,若P1的Max为0,而其余三个进程的Max都为2,则任然满足最大需求量之和(即6)小于

m+n(即7)的要求,但当除P1以外的其余三个进程各得到一个资源时.这三个进程将进入死锁状态.3.7死锁的检测和解除3.7.1检测1.资源分配图p1p23.7死锁的检测和解除2.死锁定理简化资源分配图若能完全简化则消去所有的边

。定理：死锁状态的充分条件，资源分配图不可完全简化3.检测死锁的算法：Work=availableL:={Li|alloci=0reqi=0}(孤立进程点)ForallLiLdoBeginForallreqi<=workdoBeginWork=work+allociL=

Li∪LendEndDeadlock=~(L={p1…pn})3.7死锁的检测和解除解除检测到死锁后，回退到上一状态（要进行资源剥夺，且需保存以前状态的分配信息），重新分配，若不行，继续回退……，