华东理工815操作系统第11讲

1、五、高响应比优先调度算法五、高响应比优先调度算法(HRRN)(1)(HRRN)(1)FCFSFCFS与与SJFSJF是片面的调度算法。是片面的调度算法。FCFSFCFS只考虑作业等候时间而忽视了作业的计算时只考虑作业等候时间而忽视了作业的计算时间；间；SJFSJF只考虑用户估计的作业计算时间而忽视了作业只考虑用户估计的作业计算时间而忽视了作业等待时间。等待时间。HRRNHRRN是介于这两者之间的折衷算法，既考虑作业等是介于这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。不使长作业

2、的等待时间过长，改进了调度性能。五、高响应比优先调度算法（五、高响应比优先调度算法（2 2）v优先权的变化为优先权的变化为 PR要求服务时间响应时间要求服务时间要求服务时间等待时间优先权PR为响应比。为响应比。注：注： 1)1)如等待时间相同如等待时间相同, ,则要求服务时间越短则要求服务时间越短, ,其优先权其优先权越高越高-SPF.-SPF.2)2)如要求服务时间相同如要求服务时间相同, ,优先权决定于等待时间优先权决定于等待时间-FCFSFCFS。3)3)对长作业对长作业, ,若等待时间足够长，优先权也高，也能若等待时间足够长，优先权也高，也能获得获得CPUCPU。五、高响应比优先调度算

3、法（五、高响应比优先调度算法（3 3）高响应比优先算法举例高响应比优先算法举例： 例如，以下四个作业先后到达系统进入调度：例如，以下四个作业先后到达系统进入调度： 作业名作业名 到达时间到达时间 所需所需CPUCPU时间（服务时间）时间（服务时间） P1 0 P1 0 20 20 P2 5 P2 5 15 15 P3 10 5 P3 10 5 P4 15 P4 15 10 10五、高响应比优先调度算法（五、高响应比优先调度算法（4 4）u高响应比优先调度算法高响应比优先调度算法v开始只有开始只有P1P1，被选中，执行时间，被选中，执行时间2020；P1P1的周转时间为的周转时间为2020；vP

4、1P1执行完毕，执行完毕，P2P2、P3P3、P4P4的响应比依次为的响应比依次为1+15/151+15/15、1+10/51+10/5、1+5/101+5/10，P3P3被选中，执行时间被选中，执行时间5 5；P3P3的周转时间的周转时间为为25-10=1525-10=15；vP3P3执行完毕，执行完毕，P2P2、P4P4的响应比依次为的响应比依次为1+20/151+20/15、1+10/101+10/10，P2P2被选中，执行时间被选中，执行时间1515；P2P2的周转时间为的周转时间为40-5=3540-5=35vP2P2执行完毕，执行完毕，P4P4被选中，执行时间被选中，执行时间101

5、0；P4P4的周转时间为的周转时间为50-15=3550-15=35平均周转时间平均周转时间 = (20+15+35+35)/4 = 26.25平均带权周转时间平均带权周转时间 = (20/20+15/5+35/15+35/10)/4 = 2.42q基本思想基本思想： 多级反馈队列调度算法是时间片轮转算法多级反馈队列调度算法是时间片轮转算法和优先级调度算法的综合和发展，通过动态调和优先级调度算法的综合和发展，通过动态调整进程优先级和时间片大小，不必事先估计进整进程优先级和时间片大小，不必事先估计进程的执行时间，多级反馈队列可兼顾多方面的程的执行时间，多级反馈队列可兼顾多方面的系统目标，是目前公

6、认的一种较好的进程调度系统目标，是目前公认的一种较好的进程调度算法。算法。六、多级反馈队列调度算法（六、多级反馈队列调度算法（1 1）六、多级反馈队列调度算法（六、多级反馈队列调度算法（2 2）就绪队列1就绪队列2就绪队列nCPUCPUCPU完成完成完成（1 1）设置）设置多个就绪队列多个就绪队列，并为每个队列赋予，并为每个队列赋予不同的不同的优先级优先级。队列。队列1 1的优先级最高，其余队列逐个降低。的优先级最高，其余队列逐个降低。（2 2）每个队列中）每个队列中进程执行时间片的大小进程执行时间片的大小也各不相同，也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。进程所在队列的优

7、先级越高，其相应的时间片就越短。六、多级反馈队列调度算法（六、多级反馈队列调度算法（3 3）就绪队列1就绪队列2就绪队列nCPUCPUCPU完成完成完成（3 3）当一个）当一个新进程进入新进程进入系统时，首先将它放入队列系统时，首先将它放入队列1 1的末尾，的末尾，按按FCFSFCFS等待调度。如能完成，便可准备撤离系统，反之由调等待调度。如能完成，便可准备撤离系统，反之由调度程序将其转入队列度程序将其转入队列2 2的末尾，按的末尾，按FCFSFCFS再次等待调度，如此下再次等待调度，如此下去，进入队列去，进入队列n n按按RRRR算法调度执行。算法调度执行。（4 4）仅当队列）仅当队列1 1

8、为空时，才调度队列为空时，才调度队列2 2中的进程运行。若队列中的进程运行。若队列i i中的进程正在执行，此时有新进程进入优先级较高的队列中的进程正在执行，此时有新进程进入优先级较高的队列（第（第1(i-1)1(i-1)队列）中，则新进程将队列）中，则新进程将抢占运行抢占运行，原进程转移至，原进程转移至本队列（第本队列（第i i队列）的末尾。队列）的末尾。3.5 3.5 死锁的基本概念（死锁的基本概念（1 1） 在多道程序系统中，由于多个进程的并发执行，改善在多道程序系统中，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力，然而，多了系统资源的利用率并提高了系统的处理能力，

9、然而，多个进程的并发执行也带来了新的问题个进程的并发执行也带来了新的问题-死锁。死锁。u例：设有一台输入机和一台输出机，进程例：设有一台输入机和一台输出机，进程P1P1和和P2P2需要使用需要使用这两个资源。设两个进程的活动分别为：这两个资源。设两个进程的活动分别为：P1P1的活动：的活动：申请输入机申请输入机申请输出机申请输出机释放输出机释放输出机释放输入机释放输入机P2P2的活动：的活动：申请输出机申请输出机申请输入机申请输入机释放输入机释放输入机释放输出机释放输出机P1P1与与P2P2均因得不到资均因得不到资源而无法继续向前推源而无法继续向前推进，这种由于进程竞进，这种由于进程竞争资源而

10、引起的僵持争资源而引起的僵持称为死锁。称为死锁。u死锁死锁u产生死锁的原因产生死锁的原因u产生死锁的必要条件产生死锁的必要条件u处理死锁的基本方法处理死锁的基本方法3.5 3.5 死锁的基本概念（死锁的基本概念（2 2）一、死锁一、死锁 指多个进程在运行过程中因争夺资源而造成的一种僵局指多个进程在运行过程中因争夺资源而造成的一种僵局（deadly-Embrace)deadly-Embrace)，若无外力作用，这些进程都将无法向，若无外力作用，这些进程都将无法向前推进。前推进。u如图如图R1R2P1P2注意：注意：（1 1）参与死锁的进程数至少为）参与死锁的进程数至少为2 2（2 2）参与死锁的

11、所有进程均等待）参与死锁的所有进程均等待资源资源（3 3）参与死锁的进程至少有两个）参与死锁的进程至少有两个占有资源占有资源（4 4）参与死锁的进程是系统中当）参与死锁的进程是系统中当前正在运行进程的一部分。前正在运行进程的一部分。3.5 3.5 死锁的基本概念（死锁的基本概念（3 3）二、产生死锁的原因（二、产生死锁的原因（1 1）u资源分类资源分类 操作系统管理着系统内所有资源，它负责分配不同类操作系统管理着系统内所有资源，它负责分配不同类型的资源给进程使用，系统中的资源从不同角度可分：型的资源给进程使用，系统中的资源从不同角度可分： 根据资源本身的性质根据资源本身的性质v可剥夺资源：如主

12、存、可剥夺资源：如主存、CPUCPUv不可剥夺资源：如驱动器、打印机等不可剥夺资源：如驱动器、打印机等 根据资源使用期限根据资源使用期限v永久性资源：可再次使用，如所有硬件。永久性资源：可再次使用，如所有硬件。v临时性资源：消耗性的资源，如消息、信号和数据临时性资源：消耗性的资源，如消息、信号和数据竞争临时性资源竞争临时性资源若按下列顺序进行无死锁产生：若按下列顺序进行无死锁产生：P1P1：Release(S1);Request(S3);Release(S1);Request(S3);P2P2：Release(S2);Request(S1);Release(S2);Request(S1);P3

13、P3：Release(S3);Request(S2);Release(S3);Request(S2);但若按下列顺序进行可能产生死锁：但若按下列顺序进行可能产生死锁：P1P1：Request(S3); Release(S1); Request(S3); Release(S1); P2P2：Request(S1); Release(S2);Request(S1); Release(S2);P3P3：Request(S2); Release(S3);Request(S2); Release(S3);u竞争资源竞争资源竞争非剥夺性资源竞争非剥夺性资源 竞争临时性资源竞争临时性资源R1R2P1P2竞争

14、非剥夺性资源竞争非剥夺性资源R1R1代表系统中仅有的一台打印机代表系统中仅有的一台打印机R2R2代表系统中仅有的一台磁带机代表系统中仅有的一台磁带机P1P1、 P2P2代表可共享资源的进程代表可共享资源的进程S3S1S2P1P2P3二、产生死锁的原因（二、产生死锁的原因（2 2）u进程推进顺序不当引起死锁进程推进顺序不当引起死锁v进程推进顺序合法进程推进顺序合法v进程推进顺序非法（红色折线）进程推进顺序非法（红色折线）P1P2P1Req(R1)P1Req(R2) P1Rel(R1)P2Req(R2)P1Rel(R2)P2Req(R1)P2Rel(R2)P2Rel(R1)D区二、产生死锁的原因（

15、二、产生死锁的原因（3 3）三、产生死锁的必要条件三、产生死锁的必要条件 产生死锁必须具备以下四个必要条件，这产生死锁必须具备以下四个必要条件，这四个条件是四个条件是CoffmanCoffman首先提出的，所以称为首先提出的，所以称为Coffman Coffman 条件：条件：v互斥条件（资源独占条件）互斥条件（资源独占条件）v请求和保持条件（部分分配条件）请求和保持条件（部分分配条件）v不剥夺条件不剥夺条件v循环等待条件（环路条件）循环等待条件（环路条件）四、四、处理死锁的基本方法处理死锁的基本方法目前处理死锁的基本方法有四种：目前处理死锁的基本方法有四种：u预防死锁：预防死锁：指通过设置某

16、些限制条件，去破坏产生死锁的指通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。四个必要条件中的一个或几个条件，来防止死锁的发生。u避免死锁：避免死锁：指在资源的动态分配过程中，用某种方法去防指在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。止系统进入不安全状态，从而避免死锁的发生。u检测死锁：检测死锁：允许系统在运行过程中发生死锁，但可设置检允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当措施加以清除。测机构及时检测死锁的发生，并采取适当措施加以清除。u解除死锁：解除死锁：当检测出死锁后，便采取

17、适当措施将进程从死当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来。锁状态中解脱出来。3.6 3.6 死锁的预防和避免方法（死锁的预防和避免方法（1 1）一、死锁的预防一、死锁的预防 破坏死锁的四个必要条件（常针对条件破坏死锁的四个必要条件（常针对条件2,3,4)2,3,4)（1 1）破坏互斥条件）破坏互斥条件（不可行）（不可行） 即允许多个进程同时访问资源。但由于资源本即允许多个进程同时访问资源。但由于资源本身固有特性限制，有的资源根本不能同时访问，只身固有特性限制，有的资源根本不能同时访问，只能互斥访问，所以不可能用破坏互斥条件来预防死能互斥访问，所以不可能用破坏互斥条件来预防死锁

18、。锁。3.6 3.6 死锁的预防和避免方法（死锁的预防和避免方法（2 2）（2 2）破坏请求和保持条件）破坏请求和保持条件 可采用预先静态分配方法，即要求进程在运行可采用预先静态分配方法，即要求进程在运行之前一次申请它所需要的全部资源，在它的资源之前一次申请它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦运行后，这些未满足前，不把它投入运行。一旦运行后，这些资源全归其占有，同时它也不再提出其它资源要资源全归其占有，同时它也不再提出其它资源要求，这样可以保证系统不会发生死锁。求，这样可以保证系统不会发生死锁。 此方法虽简单安全，但降低了资源利用率，此方法虽简单安全，但降低了资源利用率

19、，同时必须预知进程所需要的全部资源。同时必须预知进程所需要的全部资源。（3 3）破坏不可剥夺条件）破坏不可剥夺条件 一个已经获得某些资源的进程，若又请求新一个已经获得某些资源的进程，若又请求新的资源时不能得到满足，则它必须释放出已获得的资源时不能得到满足，则它必须释放出已获得的所有资源，以后需要资源时再请求。即一个进的所有资源，以后需要资源时再请求。即一个进程已获得的资源在运行过程中可被剥夺。从而破程已获得的资源在运行过程中可被剥夺。从而破坏了坏了“不剥夺不剥夺”条件。条件。 这种方法实现较复杂，会增加系统开销，降这种方法实现较复杂，会增加系统开销，降低系统吞吐量。低系统吞吐量。3.6 3.6

20、 死锁的预防和避免方法（死锁的预防和避免方法（3 3）（4 4）破坏环路条件）破坏环路条件 可采用可采用有序资源分配方法有序资源分配方法，即将系统中的所有，即将系统中的所有资源都按类型赋予一个编号，要求每一个进程均严资源都按类型赋予一个编号，要求每一个进程均严格按照编号递增的次序来请求资源，同类资源一次格按照编号递增的次序来请求资源，同类资源一次申请完。也就是，只要进程提出请求资源申请完。也就是，只要进程提出请求资源RiRi，则在，则在以后的请求中，只能请求以后的请求中，只能请求RiRi后面的资源，这样不会后面的资源，这样不会出现几个进程请求资源而形成环路。出现几个进程请求资源而形成环路。 该

21、方法虽提高了资源的利用率，但编号难，加该方法虽提高了资源的利用率，但编号难，加重进程负担及因使用资源顺序与申请顺序不同而造重进程负担及因使用资源顺序与申请顺序不同而造成资源浪费。成资源浪费。3.6 3.6 死锁的预防和避免方法（死锁的预防和避免方法（4 4）u死锁的避免死锁的避免 在死锁预防的几种方法中，都施加了较强的限制在死锁预防的几种方法中，都施加了较强的限制条件，严重降低了系统性能。条件，严重降低了系统性能。 在死锁避免的方法中，所施加的限制条件较弱，在死锁避免的方法中，所施加的限制条件较弱，对于进程发出的每一个资源申请命令实施动态检查，对于进程发出的每一个资源申请命令实施动态检查，并根

22、据检查结果决定是否实施资源分配。并根据检查结果决定是否实施资源分配。 在该方法中把系统的状态分为安全状态和不安全在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终处于安全状态，便可以避免状态，只要能使系统始终处于安全状态，便可以避免死锁的发生。死锁的发生。3.6 3.6 死锁的预防和避免方法（死锁的预防和避免方法（5 5） 指在某一时刻，系统能按某种指在某一时刻，系统能按某种进程顺序进程顺序(P1,P2,(P1,P2,，Pn)Pn)来为每个进程来为每个进程PiPi分配其资源分配其资源, ,直到直到满足每个进程对资源的最大需求满足每个进程对资源的最大需求, ,使每个进程都可使每个进

23、程都可顺利地完成，称此时的系统状态为顺利地完成，称此时的系统状态为安全状态，安全状态，称序称序列列(P1,P2,(P1,P2,，Pn)Pn)为为安全序列安全序列。 若某一时刻系统中不存在这样一个安全序列，若某一时刻系统中不存在这样一个安全序列，则称此时的系统状态为则称此时的系统状态为不安全状态。不安全状态。二、系统的安全状态（二、系统的安全状态（1 1） 注：注： 在死锁避免的方法中，允许进程动态申请在死锁避免的方法中，允许进程动态申请资源，系统在进行资源分配之前，先计算资源分资源，系统在进行资源分配之前，先计算资源分配的安全性，若此次分配不会导致系统进入不安配的安全性，若此次分配不会导致系统

24、进入不安全状态，便将资源分配给进程，否则进程等待。全状态，便将资源分配给进程，否则进程等待。二、系统的安全状态（二、系统的安全状态（2 2）安全、不安全、死锁状态空间安全、不安全、死锁状态空间n基本事实基本事实n如果一个系统在安全如果一个系统在安全状态，就没有死锁状态，就没有死锁n如果一个系统处于不如果一个系统处于不安全状态，就有可能安全状态，就有可能死锁死锁n避免死锁的实质避免死锁的实质：确：确保系统不进入不安全保系统不进入不安全状态状态安全状态实例安全状态实例u假定系统中有三个进程假定系统中有三个进程P1P1，P2P2和和P3P3，共有，共有1212台磁带机，台磁带机，T0T0时刻，三个进

25、程对磁带机的需求和占有情况如下表时刻，三个进程对磁带机的需求和占有情况如下表所示：所示：T0T0时刻，存在一个安全序列（时刻，存在一个安全序列（P2P2，P1P1，P3P3），所以系），所以系统是安全的。统是安全的。在在T0T0时刻后，时刻后，P3P3又请求一台磁带机，若满足又请求一台磁带机，若满足P3P3的请求，的请求，系统会怎样？系统会怎样？三、避免死锁的算法三、避免死锁的算法- -银行家算法银行家算法 具有代表性的避免死锁算法，是具有代表性的避免死锁算法，是DijkstraDijkstra给出的银行家算给出的银行家算法，为实现银行家算法，系统中必须设置若干数据结构。假法，为实现银行家算法

26、，系统中必须设置若干数据结构。假定系统中有定系统中有n n个进程（个进程（P1P1，P2P2，PnPn），），m m类资源（类资源（R1R1，R2R2，RmRm），银行家算法中使用的数据结构如下：），银行家算法中使用的数据结构如下：u可利用资源向量：可利用资源向量：availablej=k, availablej=k, 资源资源RjRj类有类有k k个可用个可用u最大需求矩阵：最大需求矩阵：Maxi,j=k,Maxi,j=k,进程进程PiPi最大请求最大请求k k个个RjRj类资源类资源u分配矩阵：分配矩阵：Allocationi,j=k,Allocationi,j=k,进程进程PiPi分配到

27、分配到k k个个RjRj类资源类资源u需求矩阵：需求矩阵：Needi,j=k,Needi,j=k,进程进程PiPi还需要还需要k k个个RjRj类资源类资源三个矩阵的关系：三个矩阵的关系：Need i,j = Maxi,j Need i,j = Maxi,j Allocation i,j Allocation i,j. .银行家算法描述银行家算法描述资源分配算法（资源分配算法（1 1） 设设RequestRequesti i是进程是进程PiPi的请求向量，设的请求向量，设Requesti j =k，表示进程，表示进程PiPi请求分配请求分配RjRj类资源类资源k k个。当进程个。当进程Pi P

28、i 发出资源请求后，系统按如下步发出资源请求后，系统按如下步骤进行检查：骤进行检查：(1)(1)如如RequestijNeedi,j, ,转转(2);(2);否则出错，因为否则出错，因为进程申请资源量超过它声明的最大量。进程申请资源量超过它声明的最大量。(2)(2)如如Requestij Availablej, ,转转(3);(3);否则表示资否则表示资源不够，需等待。源不够，需等待。银行家算法描述银行家算法描述资源分配算法（资源分配算法（2 2）(3)(3)系统系统试分配试分配资源给进程资源给进程PiPi，并作如下修改：，并作如下修改：Availablej:= Availablej- Req

29、uestAvailablej:= Availablej- Requesti ijjAllocationi,j:= Allocationi,j+ Allocationi,j:= Allocationi,j+ RequestRequesti ijjNeedi,j:= Needi,j- RequestNeedi,j:= Needi,j- Requesti ijj(4)(4)系统执行系统执行安全性算法安全性算法，检查此次资源分配后，系，检查此次资源分配后，系统是否处于安全状态。若安全，则正式进行分配，统是否处于安全状态。若安全，则正式进行分配，否则恢复原状态，让进程否则恢复原状态，让进程PiPi等待。

30、等待。银行家算法描述银行家算法描述安全性检查算法安全性检查算法 为了进行安全性检查，需要定义如下为了进行安全性检查，需要定义如下数据结构数据结构：int Workmint Workm 工作变量，记录可用资源。开始工作变量，记录可用资源。开始时，时， Work:= AvailableWork:= Availableboolean Finishnboolean Finishn 工作变量，记录进程是否执工作变量，记录进程是否执行完。开始时，行完。开始时， Finishi=false;Finishi=false;当有足够资源当有足够资源分配给进程分配给进程PiPi时，令时，令Finishi=trueF

31、inishi=true。银行家算法描述银行家算法描述安全性检查算法安全性检查算法安全性检查算法：安全性检查算法：(1) Work := Available(1) Work := Available Finishi := false Finishi := false(2)(2)寻找满足如下条件的进程寻找满足如下条件的进程PiPiFinish i = false Finish i = false 并且并且 Needi,j Needi,j Work Work如果找到，转如果找到，转(3)(3)，否则转，否则转(4)(4)(3)(3)当进程当进程PiPi获得资源后，可顺利执行完，并释获得资源后，可顺利

32、执行完，并释放分配给它的资源放分配给它的资源 ，故执行：，故执行： Work := Work + Allocation Work := Work + Allocation Finishi := true Finishi := true 转转 (2).(2).(4)(4)若所有进程的若所有进程的Finish i = true Finish i = true ，则表示，则表示系统处于安全状态，否则处于不安全状态。系统处于安全状态，否则处于不安全状态。银行家算法的例子银行家算法的例子u假定系统中有假定系统中有5 5个进程个进程P0P0到到P4, 3P4, 3类资源及数量类资源及数量分别为分别为A(1

33、0A(10个）个）,B,B（5 5个）个）,C,C（7 7个），个），T0T0时刻的时刻的资源分配情况。资源分配情况。表表1 T01 T0时刻的资源分配表时刻的资源分配表（1 1） T0T0时刻的安全性时刻的安全性利用安全性算法对利用安全性算法对T0T0时刻的资源分配情况进行分析，可得时刻的资源分配情况进行分析，可得下表。下表。分析得知：分析得知： T0T0时刻存在着一个安全序列时刻存在着一个安全序列P1 P3 P4 P2 P1 P3 P4 P2 P0P0，故，故系统是安全系统是安全的。的。表表2 T02 T0时刻的安全性检查表时刻的安全性检查表(2) P1(2) P1请求资源请求资源 RequestRequest1 1(1,0,2)(1,0,2) P1 P1发出请求向量发出请求向量RequestRequest1 1(1,0,2)(1,0,2)，系统按银，系统按银行家算法进行检查：行家算法进行检查：1) Request1) Request1 1(1,0,2)Need(1,0,2)Need1 1(1,2,2)(1,2,2)2) Request2) Request1 1(1,0,2)Available(3,3,2)(1,0,2)Available(3,3,2)3) 3) 系统试为系统试为P1P1分配资源分配资源, ,并修改相应的向量并修改相应的向量（见下表（见下表( )(