激励学习的一段说说：我多想采来一缕阳光

1、第三章 处理机调度和死锁 http:/ 3.1 处理机调度的基本概念处理机调度的基本概念v3.13.1高、中、低三级调度高、中、低三级调度 1 1、高级调度（作业调度、长程调度、接纳调度）、高级调度（作业调度、长程调度、接纳调度）v将外存作业调入内存，创建将外存作业调入内存，创建PCBPCB等，插入就绪队列。等，插入就绪队列。v一般用于批处理系统，分一般用于批处理系统，分/ /实时系统一般直接入内存，实时系统一般直接入内存，无此环节。无此环节。调度特性调度特性v1.1.接纳作业数（内存驻留数）接纳作业数（内存驻留数）太多太多 周转时间周转时间T T长长太少太少 系统效率低系统效率低v2.2.接

2、纳策略：即采用何种调度算法：接纳策略：即采用何种调度算法：FCFSFCFS、短作业优、短作业优先等先等 处理机调度的基本概念（处理机调度的基本概念（2 2）2 2、低级调度（进程调度，短程调度）、低级调度（进程调度，短程调度）v主要是由分派程序（主要是由分派程序（DispatcherDispatcher）分派处理机。）分派处理机。1.1.非抢占方式：非抢占方式：简单，实时性差简单，实时性差 ( (如如win31)win31)2.2.抢占方式抢占方式（1 1）优先权原则）优先权原则（2 2）短作业优先原则）短作业优先原则（3 3）时间片原则。）时间片原则。 v运行频率：低运行频率：低 中中 高高

3、。 v一、仅有进程调度的一、仅有进程调度的调度调度队列模型队列模型就 绪 队 列就 绪 队 列CPU阻 塞 队 列阻 塞 队 列交互用户交互用户时间片完时间片完进程调度进程调度等待事件等待事件事事件件出出现现.2调度的队列模型调度的队列模型进程完成进程完成.2调度的队列模型调度的队列模型v二、具有高二、具有高/ /低级调度的调度队列模型低级调度的调度队列模型就 绪 队 列就 绪 队 列CPU阻 塞 队 列阻 塞 队 列时间片完时间片完进程调度进程调度进程进程完成完成等待事件等待事件1事件事件1出现出现阻 塞 队 列阻 塞 队 列等待事件等待事件2事件事件2出现出

4、现作业作业调度调度后备队列后备队列N三、具有三级调度的调度队列模型就 绪 队 列就 绪 队 列CPU就绪、挂起队列就绪、挂起队列时间片完时间片完进程调度进程调度进程进程完成完成后备队列后备队列阻塞、挂起队列阻塞、挂起队列事件出现事件出现作业调度作业调度阻 塞 队 列阻 塞 队 列等待事件等待事件挂起挂起事件出现事件出现中级调度中级调度交互型作业交互型作业.3选择调度方式和算法的若干准则选择调度方式和算法的若干准则 v一、面向用户的准则一、面向用户的准则1 1周转时间短（常用于批处理系统）周转时间短（常用于批处理系统）v概念：作业从提交概念：作业从提交 完成的时间完成的时间. .

5、分为：分为：（1 1）驻外等待调度时间）驻外等待调度时间（2 2）驻内等待调度时间）驻内等待调度时间（3 3）执行时间）执行时间（4 4）阻塞时间）阻塞时间v一、面向用户的准则一、面向用户的准则平均周转时间平均周转时间平均带权周转时间平均带权周转时间 可见带权可见带权W W越小越好越小越好,Ts,Ts为实际服务时间。为实际服务时间。.3选择调度方式和算法的若干准则选择调度方式和算法的若干准则 11niiTnT11nisiiTTnWv一、面向用户的准则一、面向用户的准则2 2响应时间快：（对交互性作业）响应时间快：（对交互性作业）v概念：键盘提交请求到首次响应的时间概念：键盘提交

6、请求到首次响应的时间（1 1）输入传送时间）输入传送时间（2 2）处理时间）处理时间（3 3）响应传送时间）响应传送时间3 3截止时间的保证（特别于实时系统）截止时间的保证（特别于实时系统）4 4优先权准则：（即需要抢占调度）优先权准则：（即需要抢占调度）.3选择调度方式和算法的若干准则选择调度方式和算法的若干准则 v二、面向系统的准则二、面向系统的准则1 1吞吐量高（特别于批处理）：单位时间完成作吞吐量高（特别于批处理）：单位时间完成作业数业数2 2处理机利用率好：（因处理机利用率好：（因CPUCPU贵，特别于大中型贵，特别于大中型多用户系统）多用户系统）3 3各类资源的平衡

7、利用。各类资源的平衡利用。.3选择调度方式和算法的若干准则选择调度方式和算法的若干准则 3.2 3.2调度算法调度算法 是一个资源分配问题是一个资源分配问题 v.1先来先服务和短作业（进程）优先调度算先来先服务和短作业（进程）优先调度算法法 1.1.先来先服务调度算法先来先服务调度算法FCFSFCFSv特点：简单，有利于长作业特点：简单，有利于长作业 即即CPUCPU繁忙性作业繁忙性作业.1先来先服务和短作业（进程）先来先服务和短作业（进程）优先调度算法优先调度算法2.2.短作业进程优先调度算法：短作业进程优先调度算法：SJ(P)FSJ(P)F

8、选出估计运行时间最短的作业（进程）选出估计运行时间最短的作业（进程） 提高了平均周转时间和平均带权周转时提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）间（从而提高了系统吞吐量） 对长作业不利，有可能得不到服务（饥对长作业不利，有可能得不到服务（饥饿）饿） 未考虑作业的紧迫性未考虑作业的紧迫性 估计时间不易确定估计时间不易确定图3.4 FCFS和SJF比较0417231241418ABCDEFCFS041923184613ABCDESJF.2高优先权优先调度算法高优先权优先调度算法v1.1.优先权调度算法类型优先权调度算法类型非抢占式优先权算法非抢占式优先权算法抢占

9、式优先权算法，实时性更好。抢占式优先权算法，实时性更好。v2.2.优先权类型：优先权类型：1 1静态优先权：静态优先权：v进程优先权在整个运行期不变。进程优先权在整个运行期不变。v确定优先权依据确定优先权依据（1 1）进程类型）进程类型（2 2）进程对资源的需求；）进程对资源的需求；（3 3）根据用户需求。）根据用户需求。v特点：简单，但低优先权作业可能长期不被调度。特点：简单，但低优先权作业可能长期不被调度。.2高优先权优先调度算法高优先权优先调度算法(2)(2)v2 2动态优先权：动态优先权：如：优先权随执行时间而下降，随等待时间而升高。如：优先权随执行时间而下降，随等待时

10、间而升高。响应比响应比Rp=Rp=（等待时间服务时间）（等待时间服务时间）/ /服务时间服务时间 作为优作为优先权先权优点：长短兼顾优点：长短兼顾 缺点：需计算缺点：需计算RpRpv3.3.高响应比优先算法：高响应比优先算法：特点：特点：响应比响应比Rp=Rp=（tw+tstw+ts）/ts/ts（1 1）短作业）短作业R RP P大。大。（2 2）tsts（要求服务时间）相同的进程间相当于（要求服务时间）相同的进程间相当于FCFSFCFS。（3 3）长作业等待一段时间仍能得到服务。）长作业等待一段时间仍能得到服务。.3基于时间片的轮转调度算法基于时间片的轮转调度算法v1.1.

11、时间片轮转时间片轮转时间片大小的确定时间片大小的确定v太大：退化为太大：退化为FCFSFCFS；v太小：系统开销过大太小：系统开销过大系统对响应时间的要求；系统对响应时间的要求；T=nqT=nq就绪队列中进程的数目；就绪队列中进程的数目；系统的处理能力：（应保证一个时间片处理完常用命令）系统的处理能力：（应保证一个时间片处理完常用命令）v2.2.多级反馈队列调度多级反馈队列调度 多个就绪队列，不同优先级多个就绪队列，不同优先级 新进程首先进入第一队列尾，新进程首先进入第一队列尾，FCFSFCFS；时间片结束后；时间片结束后未完成的进入第二队列未完成的进入第二队列尾尾 第一队列空闲时才调度第二队

12、列，抢占式第一队列空闲时才调度第二队列，抢占式.3基于时间片的轮转调度算法基于时间片的轮转调度算法（2 2）特点：长、短作业兼顾，有较好的响应时间特点：长、短作业兼顾，有较好的响应时间v（1 1）短作业一次完成；）短作业一次完成；v（2 2）中型作业周转时间不长；）中型作业周转时间不长；v（3 3）大型作业不会长期不处理。）大型作业不会长期不处理。就绪队列就绪队列1 1至至CPUS1就绪队列就绪队列2 2S2至至CPU就绪队列就绪队列3 3S3至至CPU就绪队列就绪队列n nSn至至CPU时间片：时间片：S1S2Available(2,3,0) (2)Request4(3,3,

13、0)Available(2,3,0)，让，让P4P4等待。等待。（4 4） P0 P0请求资源请求资源 P P0 0发出请求向量发出请求向量Request0(0,2,0),Request0(0,2,0),系统按银行家算法进行检系统按银行家算法进行检查：查： ( (1 1) )RequestRequest0 0(0,2,0)(0,2,0)N Needeed0 0(7,4,3);(7,4,3); (2)Request (2)Request0 0(0,2,0)Available(2,3,0)(0,2,0)Available(2,3,0)， (3) (3)进行安全性检查进行安全性检查 可用资源可用资源

14、Available2,1,0Available2,1,0已不能满足任何进程的需要，已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。故系统进入不安全状态，此时系统不分配资源。 3.73.7 死锁的检测和解除死锁的检测和解除.1、 死锁的检测死锁的检测v系统必须须提供检测和解除死锁的手段：系统必须须提供检测和解除死锁的手段：（1 1）保存有关资源的请求和分配信息；）保存有关资源的请求和分配信息；（2 2）提供算法以利用这些信息来检测系统是否进入）提供算法以利用这些信息来检测系统是否进入死锁。死锁。1 1、资源分配图（、资源分配图（Resource Ailocat

15、ion GraphResource Ailocation Graph） 系统死锁可利用资源分配图来描述。系统死锁可利用资源分配图来描述。G=G=（N N，E E）：）：（1 1）N N分为两个互斥的子集，进程结点分为两个互斥的子集，进程结点P=P=（P P1 1，P P2 2,P,Pn n）, ,资源结点资源结点R=rR=r1 1,r,r2 2,r,rn n,N=PR,N=PR。（2 2）E E中的边中的边eE,eE,都连接着都连接着P P中的一个结点和中的一个结点和R R中的中的一个结点，一个结点，e=pe=pi i,r,rj j 是资源请求边，由进程是资源请求边，由进程p pi i指向指向

16、资源资源r rj j, ,它表示进程它表示进程p pi i请求一个单位的请求一个单位的r rj j资源。资源。p1p2R2R1分配请求.1 死锁的检测死锁的检测2 2、死锁定理、死锁定理v简化资源分配图来检测系统处于简化资源分配图来检测系统处于S S状态时，是否为死锁状状态时，是否为死锁状态。简化方法如下：态。简化方法如下：（1 1）在资源分配图中，找出一个既不阻塞又非独立的进程结）在资源分配图中，找出一个既不阻塞又非独立的进程结点点p pi i。在顺利情况下，。在顺利情况下，p pi i可获得所需资源而继续执行，直可获得所需资源而继续执行，直至运行完毕，再释放其所占有的全部资

17、源。这相当于消去至运行完毕，再释放其所占有的全部资源。这相当于消去p pi i所有的请求边和分配边，使之成为孤立的结点。所有的请求边和分配边，使之成为孤立的结点。p1p2R2R1p1p2R2R1（2 2）p1p1释放资源后，便可使释放资源后，便可使p2p2获得资源而继续运行，直到获得资源而继续运行，直到p2p2完成又释放出它所占有的全部资源，而形成图（完成又释放出它所占有的全部资源，而形成图（c c）所示的情）所示的情况。况。（3 3）在进行一系列的简化中，若能消去图中所有的边，使所）在进行一系列的简化中，若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是有进程都成为孤立结点，则称该图

18、是可完全简化可完全简化的，若不能的，若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。通过任何过程使该图完全简化，则称该图是不可完全简化的。p1p2R12 2、死锁定理、死锁定理vS S为死锁状态的充分条件是：当且仅当状态为死锁状态的充分条件是：当且仅当状态S S的资源分配图是不可完全简化的。的资源分配图是不可完全简化的。.1 死锁的检测死锁的检测3 3、死锁检测中的数据结构、死锁检测中的数据结构死锁检测中的数据结构，类似于银行家算法中的死锁检测中的数据结构，类似于银行家算法中的数据结构：数据结构： 可利用资源向量可利用资源向量AvailableAvailable。它

19、表示了。它表示了m m类资类资源中的每一类资源的可用数目。源中的每一类资源的可用数目。 把不占用资源的进程向量把不占用资源的进程向量AllocationAllocation：=0=0记记入表入表L L中，即中，即LiLLiL。 从进程集合中找到一个从进程集合中找到一个RequestiWorkRequestiWork的进的进程，做如下处理：程，做如下处理： 将其资源分配图简化，释放出资源，增加工将其资源分配图简化，释放出资源，增加工作向量作向量Work Work ：=Work+Allocation=Work+Allocation。 将它记入将它记入L L表中。表中。.1 死锁的检测死锁的检测若不能把所有的进程都记入若不能把所有的进程都记入L L表中，则表明系统状态表中，则表明系统状态S S的资源的资源分配图是不完全简化的，因此，该系统状态将发生死锁。分配图是不完全简化的，因此，该系统状态将发生死锁。Work:=Available;Work:=Available;L:=Li Allocationi=0L:=Li Allocationi=0Requesti=0Requesti=0