chap3处理机调度与死锁

一、处理机的多级调度策略第三章处理机的调度与死锁处理机调度是操作系统的主要功能之一，它的实现策略决定了操作系统的类型，其调度算法的优劣直接影响整个系统的性能。处理机调度的任务是选出待分派的作业或进程，为之分配处理机。一般来说，处理机调度可分为三个级别，分别是高级调度、中级调度和低级调度。1、高级调度又称作业调度，作业就是用户程序及其所需的数据和命令的集合，作业管理就是对作业的执行情况进行系统管理的程序的集合。作业调度程序的主要功能是审查系统是否能满足用户作业的资源要求以及按照一定的算法来选取作业。2、引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量，使得暂时不运行的进程从内存对换到外存上。3、低级调度又称进程调度，其主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。进程调度是操作系统中最基本的一种调度，其调度策略的优劣直接影响整个系统的性能。几点说明：在多道批处理系统中，既有高级调度，又有低级调度，也可以采用中级调度。在分时系统中，一般没有高级调度，只有低级调度，一般会采用中级调度在实时系统中，只有低级调度在支持多道程序的操作系统中，一般存在进程调度有的操作系统采用中级调度，有的操作系统没有中级调度二、处理机的调度队列模型1、仅有进程调度的处理高度队形模型（分时系统中）2、具有两级调度的处理机调度队列模型（多道批处理系统中）该模型与上一模型的主要区别在于如下两个方面：

(1)就绪队列的形式。

(2)设置多个阻塞队列。3、具有三级调度的处理机调度队列模型（多道批处理和分时系统中）三、调度性能的衡量指标对批处理系统应尽量提高各种资源的利用率和增加系统的吞吐量分时系统应保证对用户的响应时间的要求实时系统必须及时和可靠的处理衡量作业调度和进程调度性能的指标如下：（1）CPU利用率

（2）吞吐量--单位时间内CPU完成作业的数量。

（3）周转时间--从作业提交到作业完成的时间间隔。

（4）等待时间—作业或进程从进入系统到被调度并开始执行所经历的时间（5）响应时间--从提交第一个请求到产生第一个响应所用的时间（6）平均带权周转时间作业i周转时间作业i执行时间作业总数作业调度：就是要按一定的策略选取一个或多个作业，为它们分配必需的资源（内存空间、I/O设备等），使它们能够并发执行。作业调度的必要条件是：系统现有尚未分配的资源可以满足该作业的资源需求。作业分类批量型作业终端型作业一、批量型作业的组织1、作业申请（作业情况、资源要求）2、作业实体（作业操作说明书、源程序或目标模块程序、数据集合、修改信息（可没有）3.2调度算法——作业调度二、批处理系统中作业的状态及其转换四种状态：提交、后备、执行和完成3.2调度算法——作业调度三、实现作业状态转换的程序1、SPOOLing系统程序包括输入程序、输出程序、井管理程序（读子程序、写子程序）2、作业调度程序作业调度程序负责作业从“后备状态”到“执行状态”以及从“执行状态”到“完成状态”的转换，作业调度程序为作业分配的是一台虚拟的逻辑处理机。作业调度：按照某种调度算法从后备作业队列中挑选一个/几个作业进入内存，参加运行。同时分配资源，做好运行前的准备。3.2调度算法——作业调度3、进程调度程序进程调度程序的主要任务：实现进程从“就绪状态”到“运行状态”的转变。它总是按照确定的调度算法从就绪队列中选择一个进程，让它占有CPU运行，进程调度程序为作业分配的是一台真实的物理处理机。4、交通控制程序交通控制程序负责进程状态的转换和进程之间的通信。3.2调度算法——作业调度四、作业调度所需的数据结构及其组织1、作业控制块2、作业后备队列3.2调度算法——作业调度五、作业调度算法的设计原则面向用户的准则：周转时间短；响应时间快；截止时间的保证；优先权准则面向系统的准则：系统吞吐量高；处理机利用率好；各类资源的平衡利用3.2调度算法——作业调度六、常用的作业调度算法先来先服务调度算法（FCFS）特点：简单容易实现，有利于长作业，但不利于短作业3.2调度算法——作业调度2、最短作业优先调度算法（SJF）特点：易于实现，会使系统平均周转时间最短，系统吞吐量大。但忽视了作业的等待时间，不利于长作业，会出现“饿死”现象。3.2调度算法——作业调度3、响应比高者优先（HRRF）特点：算法较为复杂，每当调度作业时都需要进行响应比的计算。但它既照顾了用户作业到来的先后，又考虑了要求系统服务时间的长短。3.2调度算法——作业调度3.2调度算法——作业调度例子：分析在多道批处理系统中，有下列1、2、3、4四个作业，提交时间分别是6.0、6.5、7.0、7.5，执行时间分别是2.0、0.5、0.1、0.2，用先来先服务调度算法和短作业调度算法进行调度，哪一种算法调度性能好些？为什么？若后备作业队列中等待运行的同时有三个作业J1、J2、J3，已知它们各自的运行时间为a、b、c，且满足a<b＜c，试证明采用短作业优先算法调度能获得最小平均作业周转时间。

3.2调度算法——进程调度一、设计进程调度程序要考虑的问题1、进程调度方式进程的调度方式是指当一个进程正在处理机上运行时，若有更高优权的进程进入就绪队列时，如何分配CPU的方式，有下列两种方式：（1）非剥夺方式（实时系统中不宜采用）（2）可剥夺方式抢占的原则：时间片原则优先权原则短进程优先原则2、引起进程重新调度的时机（1）现运行进程任务完成或出现异常（2）现运行进程在运行中双提出了新的资源申请（3）现运行进程由于执行某些原语，如P操作原语、阻塞原语等（4）在分时系统中，如果现运行进程给定的时间片用完（5）在采用可剥夺方式的调度方式时，当有更高优先权的进程进入就绪队列时，要引重新高度3.2调度算法——进程调度3、进程调度算法的选择进程调度算法选择的准则CPU利用率、吞吐量、等待时间、响应时间4、进程队列的组织出队：一个进程从所在队列退出入队：一个进程排入指定的队列队列管理：系统负责进程入队和出队的工作PCB的组织有3种方式：3.2调度算法——进程调度（1）线性表方式（如右图）（2）链接表方式对具有相同状态的进程，分别各自链接起来组成进程PCB链队列：运行队列、就绪队列、阻塞队列、空闲队列（3）索引表方式对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址3.2调度算法——进程调度二、常用的进程调度算法1、优先级调度算法优先级的确定方法：（1）按进程的类型系统进程高于用户进程、前台作业高于后台（2）按资源使用的要求资源要求少，优先级高（3）按用户要求的优先权由用户确定作业优先级优先级算法：静态优先级算法：系统在创建进程时就确定了它的优先级，该优先级在进程的整个生存期内不再变化。动态优先级算法：进程的优先级根据进程的某些动态特性可以调整，即系统在进程生存期内经常修改各进程的优先级。一般根据进程占有CPU时间的长短及就绪进程等待CPU的时间长短来确定。3.2调度算法——进程调度3.2调度算法——进程调度3.2调度算法——进程调度2、时间片轮转调度算法通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率。将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过CPU现场切换执行当前的队首进程。进程可以未使用完一个时间片，就出让CPU（如阻塞）。时间片轮转法：固定时间片可变时间片：根据系统的当前负载情况，每当一轮开始时调整时间片的大小，此时间片值作为这一轮的时间片保持不变，在此轮中新到达的就绪进程暂不进入就绪队列，等待下一轮一并进入。3.2调度算法——进程调度【时间片长度变化的影响】：过长－>退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。过短－>用户的一次请求需要多个时间片才能处理完，CPU现场切换次数增加，响应时间长。【对响应时间的要求】：

T(响应时间)=N(进程数目)*q(时间片)【时间片长度的影响因素】：就绪进程的数目：数目越多，时间片越小（当响应时间一定时）。系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。3.2调度算法——进程调度3.2调度算法——进程调度3.2调度算法——进程调度3、多队列轮转调度算法将系统内进程按各自属性分为若干类，每一类组织一个就绪队列，并为每一个就绪队列规定一个调度优先级，且还可以为不同的队列规定不同的调度算法。多队列算法首先将CPU分配给高优先级队列中的进程。只有当高优先级队列为空时，再将CPU分配给较低优先级队列中的进程。各队列需采用的调度算法也应根据系统设计目标而具体确定。例：分时批处理系统中，前台作业（终端）、后台作业（批处理作业）3.2调度算法——进程调度4、多级反馈队列调度算法设置多个就绪队列，分别赋予不同的优先级，队列1的优先级最高，其他逐级降低。每队列分配不同的时间片，规定优先级越低则时间片越长。新进程就绪后，先投入队列1的末尾，按FCFS算法调度。若一个时间片未能执行完，则降低投入到队列2的末尾；依此类推，降低到最后的队列，则按“时间片轮转”算法调度直到完成。进程由于等待事件而放弃CPU后,进入等待队列,一旦等待的事件发生,则回到原来的就绪队列。仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。3.2调度算法——进程调度进程调度—多级反馈队列调度算法的特点合理地考虑了分时系统平均响应时间，考虑了批处理系统短进程优先，能使I/O为主的进程优先于CPU为主的进程。这种调度算法能适用于同时支持分时、实时、批处理的通用操作系统。3.2调度算法——进程调度5、实时调度算法实时调度的基本要求：保证计算机在规定的时间内对外部事件的请求作出响应。强实时系统：计算机对事件的响应必须在规定的时间内（最终期限）弱实时系统：允许偶尔的失误实时调度策略（动态调度和静态调度）静态调度：进程的调度顺序是预先规定好的动态调度：进程的调度顺序是动态变化的且在运行时决定等级单调算法：它根据各个进程的触发事件的发生顺序给每个进程赋予一个优先权，运行时，调度者总是运行优先权最高的可执行进程，调度方式可以采用抢先式。最早最终期限优先法：进程调度的优先级根据相应事件的最终期限的时间来确定，最终期限的时间越短，其优先级越高。最小松弛时间优先：系统首先为每个进程计算它可以让出的时间（松弛时间），调度时系统选取松弛时间最小的运行。练习题：在所学的调度算法中，对所有进程和作业都是公平合理的调度算法是

A；最有利于提高系统吞吐量的作业调度算法是

B；能兼顾作业等待时间和作业执行时间调度算法是

C；最有利于提高资源的使用率、能使短作业、长作业及交互作业用户都比较满意的调度算法是

D；为实现人机交互作用应采用调度算法是

E；能对紧急作业进行及时处理的调度算法是

F。A—F：(1)FCFS调度算法；(2)短作业优先调度算法；

(3)时间片轮转法；(4)多级反馈队列调度算法；

(5)高响应比优先算法；

(6)基于优先权的剥夺调度算法。练习题：1．操作系统的主要性能参数：

A指的是单位时间内系统处理的作业量。A：（1）周转时间；（2）处理时间；（3）消逝时间；（4）利用率；（5）生产率；（6）吞吐量。2．在所学的调度算法中，为实现人机交互作用应采用调度算法是

A。A：（1）FCFS调度算法；（2）短作业优先调度算法；（3）时间片轮转法；（4）多级反馈队列调度算法；（5）高响应比优先算法；（6）基于优先权的剥夺调度算法。3.时间片轮转算法中时间片足够大时，该算法退化为

A。

A：（1）时间片轮转算法（2）先进先出调度算法(3)高响应比优先算法（4）短作业优先算法4.作业调度是按某种算法从磁盘输入井的

A中选一个作业装入主存运行。

A：（1）就绪队列（2）等待队列（3）作业后备队列（4）提交队列5.作业调度与进程调度的主要区别是：

A。A：（1）作业调度比进程调度频繁（2）两种调度的算法完全不同（3）两种调度的性能指标完全不同(4)进程调度比作业调度频繁3.3死锁一、死锁的概念死锁：指多个进程在运行的时候因为竞争资源而陷入的一种僵局，陷入这种僵局的进程，若无外力的作用将无法再向前推进。产生死锁的原因：1、进程对资源的竞争当若干进程需求资源的总数大于系统能提供的资源数时，进程间就会出现竞争资源的现象，若管理不当就可能引起死锁。2、资源分配策略如果按某种资源分配策略分配资源时使得某些进程各自占用了部分资源后又都在等待其他进程所占的资源，且互不相让，则出会引起死锁。3、并发进程执行速度并发进程执行的速度不能由进程自己来控制，如果协调不好的话也会出现循环等待资源的情况。

例：系统有打印机、读卡机各一台，被进程P、Q共享。两个进程并发执行，按以下顺序请求和释放资源：进程P A1：请求读卡机

A2：请求打印机

A3：释放读卡机

A4：释放打印机进程Q B1：请求打印机B2：请求读卡机

B3：释放读卡机

B4：释放打印机A1、A2、A3、A4、B1、B2、B3、B4B1、B2、B3、B4、A1、A2、A3、A4A1、A2、B1、B2、A3、A4、B3、B4A1、B1、A2、B2、A3、B3、A4、B4分析上面四种执行顺序哪个可能会产生死锁产生死锁的必要条件

从以上分析可见，如果在计算机系统中同时具备下面四个必要条件时，那麽会发生死锁。换句话说，只要下面四个条件有一个不具备，系统就不会出现死锁。

〈1〉互斥条件。即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占有。这种独占资源如CD-ROM驱动器，打印机等等，必须在占有该资源的进程主动释放它之后，其它进程才能占有该资源。这是由资源本身的属性所决定的。如独木桥就是一种独占资源，两方的人不能同时过桥。

〈2〉不可抢占条件。进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。如过独木桥的人不能强迫对方后退，也不能非法地将对方推下桥，必须是桥上的人自己过桥后空出桥面（即主动释放占有资源），对方的人才能过桥。

〈3〉占有且申请条件。进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占用已占有的资源。还以过独木桥为例，甲乙两人在桥上相遇。甲走过一段桥面（即占有了一些资源），还需要走其余的桥面（申请新的资源），但那部分桥面被乙占有（乙走过一段桥面）。甲过不去，前进不能，又不后退；乙也处于同样的状况。

〈4〉循环等待条件。存在一个进程等待序列{P1，P2，...，Pn}，其中P1等待P2所占有的某一资源，P2等待P3所占有的某一源，......，而Pn等待P1所占有的的某一资源，形成一个进程循环等待环。就像前面的过独木桥问题，甲等待乙占有的桥面，而乙又等待甲占有的桥面，从而彼此循环等待。

上面我们提到的这四个条件在死锁时会同时发生。也就是说，只要有一个必要条件不满足，则死锁就可以排除。解决死锁的对策1、设计无死锁的系统两种途径：预防死锁、避免死锁2、允许系统出现死锁然后设法排除它加死锁检测手段---一旦发现死锁能够进行排除的死锁解除手段二、死锁的预防1、静态分配资源策略每个进程在开始执行前就申请它所需要的全部资源，仅当系统能满足进程的资源申请要求且把资源分配给进程后，该进程才能开始执行。（打破了（3）占有并申请）特点：简单安全，资源利用率低2、按序分配资源策略把系统中所有资源排一个顺序，对第一个资源给一个确定的编号，规定任何一个进程申请两个以上资源时总是先申请编号小的资源，后申请编号大的资源。（打中〈4〉循环等待条件）

特点：可以提高资源利用率，但资源的使用与实际使用顺序不一致，给用户编制程序带来麻烦。3、抢夺式分配资源策略仅当一个进程已经占有了某些资源又要申请新资源，而系统这时又不能满足其他资源的要求（已被其他进程占用）必须等待时，系统才可以抢夺该进程已占有的资源。（适用于CPU、内存，不能完全防止死锁）三、死锁的避免1、系统的安全与不安全状态系统能按某种进程顺序(P1,P2,…，Pn)(称〈P1,P2,…,Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。★只要系统处于安全状态，系统就不会发生死锁★在系统处于不安全状态下未必一定发生死锁，但是安全状态下的系统是一定不会发生死锁的。我们通过一个例子来说明安全性。假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：进程最大需求已分配可用P1P2P310495223由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。因为，此时也无法再找到一个安全序列，例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。现有同类资源12个供3个进程共享，假定进程所需资源和已占资源的情况如下表所示。3个进程在执行中又都提出申请一个资源的要求，回答：a.如果先满足进程A的要求，系统将会出现什么现象？解释之。

b.你认为应按怎样的次序分配资源才合适？为什么？答：a.在当前状态下，尚余2个资源可供分配，如果先满足进程A的要求，把其中1个资源分配给A进程，此时A、B、C进程仍未拥有足够资源完成任务。系统进入不安全状态，随着进程的继续执行，剩余的1个资源无论分给哪个进程，均导至所有进程进入等告待而出现死锁。b.根据目前的资源占用情况，应该先满足B的要求，把剩下的2个资源分配给他，这样，B进程可执行完毕归还系统6个资源。这6个资源可以满足A和C进程的资源需求，从而使系统处于安全状态。

2、利用银行家算法避免死锁算法：把操作系统比作银行家，操作系统管理的各种资源比作银行的周转资金，申请资源的进程比作银行借款的主顾。银行家占有有限的资金，他不可能满足所有借款人的请求，但可以满足一部分人的借款请求，等这些人归还后，又可把这笔资金借给其他人，其原则是不能使银行家的钱被借完，使资金无法周转。特点：可避免死锁，比静态资源分配法资源利用率高

但资源分配保守，每次分配前均要花较长时间计算时间，系统开销较大，而且必须知道每个进程对资源的最大需求量。3、区分死锁的避免与死锁的防止预防：是在运行之前，预先防止死锁的产生（主要通过破坏产生死锁的四个必要条件中任何一个来实现的）避免：是系统运行过程中注意避免死锁的发生（要求系统每当在进程申请资源时，都应根据一定的算法判断，仅当系统处于安全状态时才把资源分配给进程，使系统一直处于安全状态之中）四、死锁的检测和解除死锁的检测：系统定时运行一个检查程序，来检测系统中是否存在死锁，当检测到死锁时再设法解除死锁。1.资源分配图凡属于E中的一个边e∈E，都连接着P中的一个结点和R中的一个结点，e={pi,rj}是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e={rj,pi}是资源分配边，由资源rj指向进程pi,它表示把一个单位的资源rj分配给进程pi。2、利用资源图可以检测系统中是否存在死锁进程，判定死锁的法则如下：1）如果进程资源图中无环路，则此时系统内不存在死锁。2）如果进程资源图中有环路，且处于环路内的每类资源均只有一个，则此时系统内存在死锁；处于环路内的进程就是卷入死锁的进程。3）如果进程资源图中有环路，但处于环路内的每类资源个数不全为一个，则此时系统内是否存在死锁，还要化简进程资源图才能判定。3、进程资源的化简过程1）找出一个既不阻塞又非孤立的进程节点Pi2）进程Pi所占有的资源全部释放时，可唤醒等待此资源而进入阻塞的进程Pj，使原来处于阻塞的进程可能变成非阻塞进程。3）若进程资源状态图通过上述简化步骤后，都成为孤立点，则该图是可完全化简的，并且该进程资源图所代表的系统状态是安全的。4、死锁定理对于较复杂的资源状态图可能存在着多个非阻塞点，若我们从不同的点开始化简是否可以得到同一个化简图呢？经证明：一个给定的进程资源图的所有化简顺序将导致同一个不可化简图。所以我们进一步可得到如下的死锁定理：若S是死锁状态的话，当且仅当S的进程资源图是不可完全化简的。如果得到一个可完全化简的进程资源状态图，我们就称该状态为安全态，反之为死锁状态。3、死锁的解除当死锁检测程序检测到有死锁存在时，一般采用两种方式来解除死锁。1）删除法：即终止一个或几个涉及死锁的进程的执行，收回它们所占的资源进程再分配，以破坏循环等2）剥夺法：即从涉及死锁的一个或几个进程中抢夺资源，把夺来的资源再分配给卷入死锁的其他进程，直至死锁解除11.某系统中有10台打印机，有三个进程P1，P2，P3分别需要8台，7台和4台。若P1，P2，P3已申请到4台，2台和2台。试问：按银行家算法能安全分配吗？请说明分配过程。系统能为进程P3分配二台打印机。因为尽管此时10台打印机已分配给进程P14台，P22台和P34台，全部分配完，但P3已分配到所需要的全部4台打印机，它不会对打印机再提出申请，所以它能顺利运行下去，能释放占用的4台打印机，使进程P1，P2均可能获得乘余的要求4台和5台，按银行家算法是安全的。一台计算机有8台磁带机，它们由N个进程竞争使用，每个进程可能需要3台磁带机。请问N为多少时，系统没有死锁危