操作系统zxj-3处理机的调度和死锁.ppt
第三章处理机的调度和死锁,处理机调度的基本概念,高、中、低三级调度 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各类资源的平衡利用。（？折算标准）,选择调度方式和算法的若干准则,调度算法是一个资源分配问题,先来先服务和短作业（进程）优先调度算法 1.FCFS特点：简单，有利于长作业 即CPU繁忙性作业2.短作业进程优先调度算法：SJ(P)F提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）特点：对长作业不利，有可能得不到服务（饥饿）估计时间不易确定,例,图3.4FCFS和SJF比较,高优先权优先调度算法,1.优先权调度算法类型非抢占式优先权算法抢占式优先权算法，实时性更好。2.优先权类型：1静态优先权：进程优先权在整个运行期不变。确定优先权依据（1）进程类型（2）进程对资源的需求；（3）根据用户需求。特点：简单，但低优先权作业可能长期不被调度。,高优先权优先调度算法(2),2动态优先权：如：优先权随执行时间而下降，随等待时间而升高。响应比Rp=（等待时间服务时间）/服务时间 作为优先权优点：长短兼顾 缺点：需计算Rp3.高响应比优先算法：特点：响应比Rp=（tw+ts）/ts（1）短作业RP大。（2）ts（要求服务时间）相同的进程间相当于FCFS。（3）长作业等待一段时间仍能得到服务。,基于时间片的轮转调度算法,1.时间片轮转时间片大小的确定太大：退化为FCFS；太小：系统开销过大系统对响应时间的要求；T=nq就绪队列中进程的数目；系统的处理能力：（应保证一个时间片处理完常用命令）,基于时间片的轮转调度算法,2.多级反馈队列调度特点：长、短作业兼顾，有较好的响应时间（1）短作业一次完成；（2）中型作业周转时间不长；（3）大型作业不会长期不处理。,就绪队列1,至CPU,S1,就绪队列2,S2,至CPU,就绪队列3,S3,至CPU,就绪队列n,Sn,至CPU,时间片：S1S2S3,图35多级队列反馈调度算法,实现实时调度的基本条件1提供必要的调度信息（1）就绪时间；（2）开始/完成截止时间；（3）处理时间；（4）资源要求；（5）优先级；2系统处理能力强,实时调度,Ci为处理时间，Pi为周期时间（基于周期性实时任务）,实现实时调度的基本条件3.采用抢占调度方式剥夺方式：一般都采用此非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。4.具有快速切换机制具有快速响应外部中断能力。快速任务分派,实时调度,实时调度算法的分类,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,开始截止时间,任务到达,任务执行,图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,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,多处理机系统中的调度,1.紧密耦合MPS和松弛耦合MPS紧密耦合共享RAM和I/O高速总线和交叉开关连接松弛耦合独立RAM和I/O通道和通信线路连接2.对称多处理器系统和非对称多处理器系统处理器是否结构相同,进程分配方式,1.SMP中进程分配方式静态分配动态分配可防止系统中多个处理器忙闲不均2.非SMP中进程分配方式进程调度在主处理器上执行有潜在的不可靠性,进程（线程）调度方式,1.自调度各个处理机自行在就绪队列中取任务。特点；简单，分布式调度，调度算法可采用前述方法，多个CPU利用率都不错（不会闲）但：瓶颈问题，（单队列）低效性；（需拷贝现场）线程切换频繁（当线程合作时,各线程并行的条件不容易满足）,2.成组调度,优点：（1）对相互合作的进（线）程组调度，可以减小切换，减小系统开销。（2）每次分配一组CPU，减少了调度频率。分配时间（1）面向程序（2）面向线程：使处理机利用率更高。,2.成组调度,浪费37.5%,浪费15%,3.专用处理机分配,引入：多处理机系统，每个处理已不再属宝贵资源。特点：每个进（线）程专用处理机，使其切换小，提高效率。主要用于大型计算，实时系统,产生死锁的原因和必要条件,产生死锁的原因。一、竞争资源引起死锁。1可剥夺（CPU、内存，）和非剥夺性（打印机，磁带机）资源2竞争非剥夺性资源可造成死锁,p1,p2,R1,R2,产生死锁的原因和必要条件,3竞争临时性资源临时性资源是指由一个进程产生，被另一个进程使用一段时间后便无用的资源。,二、进程推进顺序不当引起死锁。,2,1,3,D,P2Req(R2),P2Req(R1),P1Req(R1),P1Req(R2),P2Rel(R2),P2Rel(R1),P1Rel(R1),P1Rel(R2),4,产生死锁的必要条件,1互斥条件（资源的临界性）2请求和保持条件3不剥夺条件4环路等待,处理死锁的基本方法,1预防；破坏4个条件之一：有效，使资源利用率低。2避免：防止进入不安全态。3检测：检测到死锁再清除。4解除：与“检”配套。,死锁预防和避免,3.6.1 死锁预防 一、互斥条件是资源固有属性，不能避免。二、摒弃请求和保持条件全分配，全释放（AND）缺点：（1）延迟进程运行（2）资源严重浪费三、摒弃“不剥夺”条件增加系统开销，且进程前段工作可能失效。,死锁预防和避免,3.6.1 死锁预防 四、摒弃“环路”条件有序资源分配法：为资源编号，申请时需按编号进行。缺点：（1）新增资源不便，（原序号已排定）（2）用户不自由（3）资源与进程使用顺序不同造成浪费,系统的安全状态,在“避免死锁”方法中的判断条件 1.安全状态按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。能找到安全序列的状态为安全状态。,系统的安全状态（2）,2.安全状态例,安全序列：p2p1p3,系统的安全状态（3）,3安全不安全的转换 上例中，若P3再申请一台，则不安全,利用银行家算法避免死锁,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,jrequesti进程i请求资源数worki：进程i执行完后系统应有资源数（也即可用数）finishi：布尔量，表进程i能否顺序完成。,利用银行家算法避免死锁,2银行家算法,reqi=needi,error,reqi=availi,block,利用银行家算法避免死锁,avail=avail-reqialloci=alloci+reqineedi=needi-reqi,finishi=.F.needi=work,work=work+allocifinishi=.T.,4实例,T0时刻的资源分配表,4实例,T0时刻的安全序列,4实例,P1申请资源(1,0,2)时安全性检查(安全),4实例,为P0分配（0，2，0）后的情况（不安全）,死锁的检测和解除,检测1.资源分配图,p1,p2,死锁的检测和解除,2.死锁定理简化资源分配图若能完全简化则消去所有的边。定理：死锁状态的充分条件，资源分配图不可完全简化3.检测死锁的算法：,Work=availableL:=Li|alloci=0 reqi=0(孤立进程点)For all Li L doBeginFor all reqi=work doBeginWork=work+allociL=LiLendEndDeadlock=(L=p1 pn),死锁的检测和解除,解除,检测到死锁后，回退到上一状态（要进行资源剥夺，且需保存以前状态的分配信息），重新分配，若不行，继续回退，,
