《计算机操作系统》PPT课件.ppt

《《计算机操作系统》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《计算机操作系统》PPT课件.ppt（156页珍藏版）》请在金锄头文库上搜索。

1、第三章处理机调度与死锁 第三章处理机调度与死锁 3.1处理机调度的层次处理机调度的层次3.2调度队列模型和调度准则调度队列模型和调度准则3.3调度算法调度算法3.4实时调度实时调度3.5产生死锁的原因和必要条件产生死锁的原因和必要条件3.6预防死锁的方法预防死锁的方法3.7死锁的检测与解除死锁的检测与解除第三章处理机调度与死锁 处理机是计算机系统中的重要资源处理机是计算机系统中的重要资源处理机是计算机系统中的重要资源处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综合性处理机调度算法对整个计算机系统的综合性处理机调度算法对整个计算机系统的综合性处理机调度算法对整个计算机系统的综

2、合性能指标有重要影响能指标有重要影响能指标有重要影响能指标有重要影响 不同的不同的不同的不同的OSOSOSOS，处理机管理的策略不同，处理机管理的策略不同，处理机管理的策略不同，处理机管理的策略不同可把处理机调度分成三个层次：可把处理机调度分成三个层次： 高级调度高级调度高级调度高级调度 中级调度中级调度中级调度中级调度 低级调度低级调度低级调度低级调度3.1处理机调度的层次处理机调度的层次 第三章处理机调度与死锁 3.1处理机调度的层次处理机调度的层次n高级调度高级调度高级调度高级调度（宏观调度宏观调度宏观调度宏观调度、作业调度、长程调度、作业调度、长程调度、作业调度、长程调度、作业调度、长

3、程调度） 主要功能：根据作业控制块中的信息，审查系统主要功能：根据作业控制块中的信息，审查系统主要功能：根据作业控制块中的信息，审查系统主要功能：根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算能否满足用户作业的资源需求，以及按照一定的算能否满足用户作业的资源需求，以及按照一定的算能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，法，从外存的后备队列中选取某些作业调入内存，法，从外存的后备队列中选取某些作业调入内存，法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新并为它们创建进程、分配必要

4、的资源。然后再将新并为它们创建进程、分配必要的资源。然后再将新并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。因此，有时创建的进程插入就绪队列，准备执行。因此，有时创建的进程插入就绪队列，准备执行。因此，有时创建的进程插入就绪队列，准备执行。因此，有时也把作业调度称为接纳调度也把作业调度称为接纳调度也把作业调度称为接纳调度也把作业调度称为接纳调度(Admission (Admission (Admission (Admission Scheduling)Scheduling)Scheduling)Scheduling)。 第三章处理机调度与死锁 n低低低低级调度级

5、调度级调度级调度（微观调度、进程调度、短程调度微观调度、进程调度、短程调度微观调度、进程调度、短程调度微观调度、进程调度、短程调度） 功能：决功能：决功能：决功能：决定就绪队列中的哪个进程定就绪队列中的哪个进程定就绪队列中的哪个进程定就绪队列中的哪个进程( ( ( (或内核级线或内核级线或内核级线或内核级线程程程程) ) ) )应获得处理机，然后再由分派程序执行把处理机应获得处理机，然后再由分派程序执行把处理机应获得处理机，然后再由分派程序执行把处理机应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作分配给该进程的具体操作分配给该进程的具体操作分配给该进程的具体操作. . . .

6、n中中中中级调度级调度级调度级调度（中程调度、交换调度）（中程调度、交换调度）（中程调度、交换调度）（中程调度、交换调度） 按照给定的原则和策略，将处于外存交换区中的按照给定的原则和策略，将处于外存交换区中的按照给定的原则和策略，将处于外存交换区中的按照给定的原则和策略，将处于外存交换区中的就绪状态或等待状态的进程调入内存，或把处于内就绪状态或等待状态的进程调入内存，或把处于内就绪状态或等待状态的进程调入内存，或把处于内就绪状态或等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换存就绪状态或内存等待状态的进程交换到外存交换存就绪状态或内存等待状态的进程交换到外存交换

7、存就绪状态或内存等待状态的进程交换到外存交换区中。区中。区中。区中。 目的：提高内存的利用率和系统吞吐量。目的：提高内存的利用率和系统吞吐量。目的：提高内存的利用率和系统吞吐量。目的：提高内存的利用率和系统吞吐量。3.1处理机调度的层次处理机调度的层次 第三章处理机调度与死锁 3.1处理机调度的层次处理机调度的层次3.1.13.1.13.1.13.1.1高级调度（只针对批处理系统）高级调度（只针对批处理系统）高级调度（只针对批处理系统）高级调度（只针对批处理系统）1 1 1 1作业和作业步作业和作业步作业和作业步作业和作业步(1) (1) 作业作业(Job)=(Job)=程序程序+ +数据数据

8、+ +作业说明书作业说明书 系统根据说明书来对程序的运行进行控制。在批处理系系统根据说明书来对程序的运行进行控制。在批处理系统中，以作业为基本单位从外存调入内存的。统中，以作业为基本单位从外存调入内存的。 第三章处理机调度与死锁 (2) (2) (2) (2) 作作作作业业业业步步步步(Job (Job (Job (Job Step)Step)Step)Step)。通通通通常常常常，在在在在作作作作业业业业运运运运行行行行期期期期间间间间，每每每每个个个个作作作作业业业业都都都都必必必必须须须须经经经经过过过过若若若若干干干干个个个个相相相相对对对对独独独独立立立立，又又又又相相相相互互互互关

9、关关关联联联联的的的的顺顺顺顺序序序序加加加加工工工工步步步步骤骤骤骤才才才才能能能能得得得得到到到到结结结结果果果果，我我我我们们们们把把把把其其其其中中中中的的的的每每每每一一一一个个个个加加加加工工工工步步步步骤骤骤骤称称称称为为为为一一一一个个个个作作作作业业业业步步步步，各各各各作作作作业业业业步步步步之之之之间间间间存存存存在在在在着着着着相相相相互互互互联联联联系系系系，往往往往往往往往是是是是把把把把上上上上一一一一个个个个作作作作业业业业步的输出作为下一个作业步的输入。步的输出作为下一个作业步的输入。步的输出作为下一个作业步的输入。步的输出作为下一个作业步的输入。 编译编译编

10、译编译 连结装配连结装配连结装配连结装配 运行运行运行运行 (3)(3)作作作作业业业业流流流流。若若若若干干干干个个个个作作作作业业业业进进进进入入入入系系系系统统统统后后后后，被被被被依依依依次次次次存存存存放放放放在在在在外外外外存存存存上上上上，形形形形成成成成输输输输入入入入的的的的作作作作业业业业流流流流；在在在在操操操操作作作作系系系系统统统统的的的的控控控控制制制制下下下下，逐逐逐逐个个个个作作作作业业业业进行处理，形成处理作业流。进行处理，形成处理作业流。进行处理，形成处理作业流。进行处理，形成处理作业流。 第三章处理机调度与死锁 2 2 2 2作业控制块作业控制块作业控制块

11、作业控制块JCBJCBJCBJCB(Job Control Block)(Job Control Block)(Job Control Block)(Job Control Block)是作业在系统中存在的标志是作业在系统中存在的标志是作业在系统中存在的标志是作业在系统中存在的标志 保存了系统对作业进行管理和调度所需的全部信息。保存了系统对作业进行管理和调度所需的全部信息。保存了系统对作业进行管理和调度所需的全部信息。保存了系统对作业进行管理和调度所需的全部信息。通常应包含的内容有：作业标识、用户名称、用户帐户、通常应包含的内容有：作业标识、用户名称、用户帐户、通常应包含的内容有：作业标识、用

12、户名称、用户帐户、通常应包含的内容有：作业标识、用户名称、用户帐户、作业类型作业类型作业类型作业类型(CPU (CPU (CPU (CPU 繁忙型、繁忙型、繁忙型、繁忙型、I/O I/O I/O I/O 繁忙型、批量型、终端型繁忙型、批量型、终端型繁忙型、批量型、终端型繁忙型、批量型、终端型) ) ) )、作业状态、调度信息作业状态、调度信息作业状态、调度信息作业状态、调度信息( ( ( (优先级、作业已运行时间优先级、作业已运行时间优先级、作业已运行时间优先级、作业已运行时间) ) ) )、资源需、资源需、资源需、资源需求求求求( ( ( (预计运行时间、要求内存大小、要求预计运行时间、要求

13、内存大小、要求预计运行时间、要求内存大小、要求预计运行时间、要求内存大小、要求I/OI/OI/OI/O设备的类型和设备的类型和设备的类型和设备的类型和数量等数量等数量等数量等) ) ) )、进入系统时间、开始处理时间、作业完成时间、进入系统时间、开始处理时间、作业完成时间、进入系统时间、开始处理时间、作业完成时间、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。作业退出时间、资源使用情况等。作业退出时间、资源使用情况等。作业退出时间、资源使用情况等。作业的状态作业的状态作业的状态作业的状态 作业从输入到完成要经历作业从输入到完成要经历作业从输入到完成要经历作业从输入到完

14、成要经历提交，收容，执行，完成提交，收容，执行，完成提交，收容，执行，完成提交，收容，执行，完成四四四四个阶段。个阶段。个阶段。个阶段。第三章处理机调度与死锁 JCBJCB主要信息主要信息第三章处理机调度与死锁 作业的状态及其转换作业的状态及其转换提交状态提交状态提交状态提交状态：一个作业被提交给机房后或用户通过终：一个作业被提交给机房后或用户通过终：一个作业被提交给机房后或用户通过终：一个作业被提交给机房后或用户通过终端设备向计算机中输入其作业时所处的状况。端设备向计算机中输入其作业时所处的状况。端设备向计算机中输入其作业时所处的状况。端设备向计算机中输入其作业时所处的状况。后备状态后备状态

15、后备状态后备状态：作业的全部信息都已输入，并存放在磁：作业的全部信息都已输入，并存放在磁：作业的全部信息都已输入，并存放在磁：作业的全部信息都已输入，并存放在磁盘中等待运行。盘中等待运行。盘中等待运行。盘中等待运行。运行状态运行状态运行状态运行状态：作业被调度程序选中而被送入主存中投：作业被调度程序选中而被送入主存中投：作业被调度程序选中而被送入主存中投：作业被调度程序选中而被送入主存中投入运行。入运行。入运行。入运行。完成状态完成状态完成状态完成状态：作业完成其全部运行，释放其所占用的：作业完成其全部运行，释放其所占用的：作业完成其全部运行，释放其所占用的：作业完成其全部运行，释放其所占用的

16、全部资源，准备退出系统。全部资源，准备退出系统。全部资源，准备退出系统。全部资源，准备退出系统。第三章处理机调度与死锁 提交提交后备后备运行运行就绪就绪等待等待完成完成作业作业调度调度作业作业调度调度作业作业录入录入作业的状态及转换作业的状态及转换作业的状态及转换作业的状态及转换第三章处理机调度与死锁 3作业调度算法的选择作业调度算法的选择 用户：周转时间少最好用户：周转时间少最好用户：周转时间少最好用户：周转时间少最好 系统：作业的平均周转时间尽可能少，有利于提高系统：作业的平均周转时间尽可能少，有利于提高系统：作业的平均周转时间尽可能少，有利于提高系统：作业的平均周转时间尽可能少，有利于提

17、高CPU CPU CPU CPU 的的的的利用率和系统的吞吐量。利用率和系统的吞吐量。利用率和系统的吞吐量。利用率和系统的吞吐量。 既应考虑用户的要求，又能确保系统具有较高的效率。在既应考虑用户的要求，又能确保系统具有较高的效率。在既应考虑用户的要求，又能确保系统具有较高的效率。在既应考虑用户的要求，又能确保系统具有较高的效率。在每次执行作业调度时，都须做出以下两个决定。每次执行作业调度时，都须做出以下两个决定。每次执行作业调度时，都须做出以下两个决定。每次执行作业调度时，都须做出以下两个决定。1) 1) 1) 1) 决决决决定定定定接接接接纳纳纳纳多多多多少少少少个个个个作作作作业业业业：多

18、多多多道道道道程程程程序序序序度度度度的的的的确确确确定定定定应应应应根根根根据据据据系系系系统统统统的规模和运行速度等情况做适当的的规模和运行速度等情况做适当的的规模和运行速度等情况做适当的的规模和运行速度等情况做适当的折衷折衷折衷折衷 2) 2) 2) 2) 决定接纳哪些作业：作业调度算法决定接纳哪些作业：作业调度算法决定接纳哪些作业：作业调度算法决定接纳哪些作业：作业调度算法 第三章处理机调度与死锁 3.1.2 3.1.2 3.1.2 3.1.2 低级调度低级调度低级调度低级调度调调度度的的对对象象是是进进程程( (或或内内核核级级线线程程) )。进进程程调调度度是是最最基基本本的的一一

19、种种调调度度，在在多多道道批批处处理理、分分时时和和实实时时三三种种类类型型的的OSOS中中，都都必必须配置这级调度。须配置这级调度。1 1低级调度的功能低级调度的功能低低级级调调度度用用于于决决定定就就绪绪队队列列中中的的哪哪个个进进程程( (或或内内核核级级线线程程) )应应获获得得处处理理机机，然然后后再再由由分分派派程程序序执执行行把把处处理理机机分分配配给给该该进进程程的具体操作。的具体操作。第三章处理机调度与死锁 低级调度的主要功能如下：低级调度的主要功能如下：低级调度的主要功能如下：低级调度的主要功能如下： (1) (1) (1) (1) 保存处理机的现场信息。保存处理机的现场信

20、息。保存处理机的现场信息。保存处理机的现场信息。(2) (2) (2) (2) 按某种算法选取进程。按某种算法选取进程。按某种算法选取进程。按某种算法选取进程。(3) (3) (3) (3) 把处理器分配给进程。把处理器分配给进程。把处理器分配给进程。把处理器分配给进程。第三章处理机调度与死锁 2 2 2 2进程调度中的三个基本机制进程调度中的三个基本机制进程调度中的三个基本机制进程调度中的三个基本机制为了实现进程调度，应具有如下三个基本机制：为了实现进程调度，应具有如下三个基本机制：为了实现进程调度，应具有如下三个基本机制：为了实现进程调度，应具有如下三个基本机制：(1) (1) (1) (

21、1) 排排排排队队队队器器器器。就就就就绪绪绪绪进进进进程程程程按按按按照照照照一一一一定定定定的的的的方方方方式式式式排排排排成成成成一一一一个个个个或或或或多多多多个个个个队列队列队列队列(2) (2) (2) (2) 分派器分派器分派器分派器( ( ( (分派程序分派程序分派程序分派程序) ) ) )。从就绪队列中取出选中进程，。从就绪队列中取出选中进程，。从就绪队列中取出选中进程，。从就绪队列中取出选中进程，然后进行上下文切换，分配处理机。然后进行上下文切换，分配处理机。然后进行上下文切换，分配处理机。然后进行上下文切换，分配处理机。(3) (3) (3) (3) 上下文切换机制上下文

22、切换机制上下文切换机制上下文切换机制。 当对处理机进行切换时，会发生当对处理机进行切换时，会发生当对处理机进行切换时，会发生当对处理机进行切换时，会发生两对两对两对两对上下文切换上下文切换上下文切换上下文切换操作。操作。操作。操作。在第一对上下文切换时，操作系统将保存当前进程的上下文，在第一对上下文切换时，操作系统将保存当前进程的上下文，在第一对上下文切换时，操作系统将保存当前进程的上下文，在第一对上下文切换时，操作系统将保存当前进程的上下文，而装入分派程序的上下文，以便分派程序运行；在第二对上而装入分派程序的上下文，以便分派程序运行；在第二对上而装入分派程序的上下文，以便分派程序运行；在第二

23、对上而装入分派程序的上下文，以便分派程序运行；在第二对上下文切换时，将移出分派程序，而把新选进程的下文切换时，将移出分派程序，而把新选进程的下文切换时，将移出分派程序，而把新选进程的下文切换时，将移出分派程序，而把新选进程的CPUCPUCPUCPU现场信息现场信息现场信息现场信息装入到处理机的各个相应寄存器中。装入到处理机的各个相应寄存器中。装入到处理机的各个相应寄存器中。装入到处理机的各个相应寄存器中。 耗时？怎么办？耗时？怎么办？耗时？怎么办？耗时？怎么办？P86P86P86P86第三章处理机调度与死锁 n进程调度时机进程调度时机进程调度时机进程调度时机 正在执行的进程执行完毕。正在执行的

24、进程执行完毕。正在执行的进程执行完毕。正在执行的进程执行完毕。 运行中的进程提出运行中的进程提出运行中的进程提出运行中的进程提出I/O I/O I/O I/O 请求。请求。请求。请求。 执行某原语操作。执行某原语操作。执行某原语操作。执行某原语操作。 在可剥夺调度方式中，一个具有更高优先数在可剥夺调度方式中，一个具有更高优先数在可剥夺调度方式中，一个具有更高优先数在可剥夺调度方式中，一个具有更高优先数的进程进入就绪队列。的进程进入就绪队列。的进程进入就绪队列。的进程进入就绪队列。 在分时系统中，分配给该进程的时间片已用在分时系统中，分配给该进程的时间片已用在分时系统中，分配给该进程的时间片已用

25、在分时系统中，分配给该进程的时间片已用完完完完 第三章处理机调度与死锁 3 3进程调度方式（进程调度方式（两种）1) 1) 1) 1) 非抢占方式非抢占方式非抢占方式非抢占方式( ( ( (NonpreemptiveNonpreemptiveNonpreemptiveNonpreemptive Mode) Mode) Mode) Mode) 分派程序一旦把处理机分配给某进程后便让它一直运分派程序一旦把处理机分配给某进程后便让它一直运分派程序一旦把处理机分配给某进程后便让它一直运分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处行下去，直到进程完成或发

26、生某事件而阻塞时，才把处行下去，直到进程完成或发生某事件而阻塞时，才把处行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。理机分配给另一个进程。理机分配给另一个进程。理机分配给另一个进程。 优点：实现简单，开销小，适用于大多数的批处理系优点：实现简单，开销小，适用于大多数的批处理系优点：实现简单，开销小，适用于大多数的批处理系优点：实现简单，开销小，适用于大多数的批处理系统环境。统环境。统环境。统环境。 缺点：难以满足紧急任务的要求缺点：难以满足紧急任务的要求缺点：难以满足紧急任务的要求缺点：难以满足紧急任务的要求立即执行立即执行立即执行立即执行第三章处理机调度与死锁 2)

27、 2) 2) 2) 抢占抢占抢占抢占 方式方式方式方式(Preemptive Mode) (Preemptive Mode) (Preemptive Mode) (Preemptive Mode) 当一个进程正在运行时，系统可以基于某种原则，剥当一个进程正在运行时，系统可以基于某种原则，剥当一个进程正在运行时，系统可以基于某种原则，剥当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。夺已分配给它的处理机，将之分配给其它进程。夺已分配给它的处理机，将之分配给其它进程。夺已分配给它的处理机，将之分配给其它进程。 优点：公平，能满足对响应时间有着较严格要求的实优

28、点：公平，能满足对响应时间有着较严格要求的实优点：公平，能满足对响应时间有着较严格要求的实优点：公平，能满足对响应时间有着较严格要求的实时任务的需求。时任务的需求。时任务的需求。时任务的需求。 缺点：开销较大。缺点：开销较大。缺点：开销较大。缺点：开销较大。 原原原原则则则则：（1 1）优优优优先先先先权权权权（2 2）短短短短作作作作业业业业（进进进进程程程程）优优优优先先先先（3 3）时间片时间片时间片时间片n n选择性剥夺调度选择性剥夺调度选择性剥夺调度选择性剥夺调度第三章处理机调度与死锁 在上述三种调度中，进程调度的运行频率最高，在分时在上述三种调度中，进程调度的运行频率最高，在分时在

29、上述三种调度中，进程调度的运行频率最高，在分时在上述三种调度中，进程调度的运行频率最高，在分时系统中通常是系统中通常是系统中通常是系统中通常是1010100ms100ms便进行一次进程调度，因此把它称便进行一次进程调度，因此把它称便进行一次进程调度，因此把它称便进行一次进程调度，因此把它称为短程调度。为避免进程调度占用太多的为短程调度。为避免进程调度占用太多的为短程调度。为避免进程调度占用太多的为短程调度。为避免进程调度占用太多的CPUCPU时间，进程调时间，进程调时间，进程调时间，进程调度算法不宜太复杂。度算法不宜太复杂。度算法不宜太复杂。度算法不宜太复杂。 作业调度往往是发生在一个作业调度

30、往往是发生在一个作业调度往往是发生在一个作业调度往往是发生在一个( (批批批批) )作业运行完毕，退出系作业运行完毕，退出系作业运行完毕，退出系作业运行完毕，退出系统，而需要重新调入一个统，而需要重新调入一个统，而需要重新调入一个统，而需要重新调入一个( (批批批批) )作业进入内存时，故作业调度作业进入内存时，故作业调度作业进入内存时，故作业调度作业进入内存时，故作业调度的周期较长，大约的周期较长，大约的周期较长，大约的周期较长，大约几分钟（几小时几分钟（几小时几分钟（几小时几分钟（几小时）一次，因此把它称为长）一次，因此把它称为长）一次，因此把它称为长）一次，因此把它称为长程调度。由于其运

31、行频率较低，故允许作业调度算法花费较程调度。由于其运行频率较低，故允许作业调度算法花费较程调度。由于其运行频率较低，故允许作业调度算法花费较程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。中级调度的运行频率基本上多的时间。中级调度的运行频率基本上多的时间。中级调度的运行频率基本上多的时间。中级调度的运行频率基本上介于介于介于介于上述两种调度之上述两种调度之上述两种调度之上述两种调度之间，因此把它称为中程调度。间，因此把它称为中程调度。间，因此把它称为中程调度。间，因此把它称为中程调度。 第三章处理机调度与死锁 3.2调度队列模型和调度准则调度队列模型和调度准则3.2.13.2.1

32、调度队列模型调度队列模型1 1仅有进程调度的调度队列模型（分时、实时仅有进程调度的调度队列模型（分时、实时OSOS）第三章处理机调度与死锁 2 2具有高级和低级调度的调度队列模型（具有高级和低级调度的调度队列模型（批处理）批处理）第三章处理机调度与死锁 3 3同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型当在当在当在当在OSOSOSOS中引入中级调度后，人们可把进程的就绪状态分中引入中级调度后，人们可把进程的就绪状态分中引入中级调度后，人们可把进程的就绪状态分中引入中级调度后，人们可把进程的就绪状态分为为为为内存就绪内存就绪内存就绪内存就绪( ( ( (表示进程在内存中就绪表示进

33、程在内存中就绪表示进程在内存中就绪表示进程在内存中就绪) ) ) )和和和和外存就绪外存就绪外存就绪外存就绪( ( ( (进程在外存进程在外存进程在外存进程在外存中就绪中就绪中就绪中就绪) ) ) )。类似地，也可把阻塞状态进一步分成。类似地，也可把阻塞状态进一步分成。类似地，也可把阻塞状态进一步分成。类似地，也可把阻塞状态进一步分成内存阻塞内存阻塞内存阻塞内存阻塞和和和和外外外外存阻塞存阻塞存阻塞存阻塞两种状态。在调出操作的作用下，可使进程状态由内两种状态。在调出操作的作用下，可使进程状态由内两种状态。在调出操作的作用下，可使进程状态由内两种状态。在调出操作的作用下，可使进程状态由内存就绪转

34、为外存就绪，由内存阻塞转为外存阻塞；在中级调存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中级调存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中级调存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就绪。图度的作用下，又可使外存就绪转为内存就绪。图度的作用下，又可使外存就绪转为内存就绪。图度的作用下，又可使外存就绪转为内存就绪。图3-33-33-33-3示出了具示出了具示出了具示出了具有三级调度的调度队列模型。有三级调度的调度队列模型。有三级调度的调度队列模型。有三级调度的调度队列模型。 第三章处理机调度与死锁 图 3-3具有三级调度时的调度队列模型 第三章

35、处理机调度与死锁 3.2.23.2.23.2.23.2.2选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则1 1 1 1面向用户的准则面向用户的准则面向用户的准则面向用户的准则 (1) (1) (1) (1) 周周周周转转转转时时时时间间间间短短短短。评评评评价价价价批批批批处处处处理理理理系系系系统统统统的的的的性性性性能能能能、选选选选择择择择作业调度方式与算法的重要准则之一。作业调度方式与算法的重要准则之一。作业调度方式与算法的重要准则之一。作业调度方式与算法的重要准则之一。 周周周周转转转转时时时时间间间间

36、：从从从从作作作作业业业业被被被被提提提提交交交交给给给给系系系系统统统统开开开开始始始始，到到到到作作作作业业业业完成为止的这段时间间隔。完成为止的这段时间间隔。完成为止的这段时间间隔。完成为止的这段时间间隔。 平均周转时间平均周转时间平均周转时间平均周转时间带带带带权权权权周周周周转转转转时时时时间间间间：作作作作业业业业的的的的周周周周转转转转时时时时间间间间T T T T与与与与系系系系统统统统为为为为它它它它提提提提供服务的时间供服务的时间供服务的时间供服务的时间TsTsTsTs之比，即之比，即之比，即之比，即W = T/TsW = T/TsW = T/TsW = T/Ts第三章处理

37、机调度与死锁 n平均带权周转时间：平均带权周转时间：平均带权周转时间：平均带权周转时间： 一般，总是一般，总是T T或或W W小的作业被选中，因为小的作业被选中，因为这样资源利用率较高，用户也满意。这样资源利用率较高，用户也满意。第三章处理机调度与死锁 (2) (2) (2) (2) 响应时间快。响应时间快。响应时间快。响应时间快。常把响应时间的长短用来评价常把响应时间的长短用来评价常把响应时间的长短用来评价常把响应时间的长短用来评价分分分分时系统时系统时系统时系统的性能，这是选择分时系统中进程调度算法的重要准的性能，这是选择分时系统中进程调度算法的重要准的性能，这是选择分时系统中进程调度算法

38、的重要准的性能，这是选择分时系统中进程调度算法的重要准则之一。则之一。则之一。则之一。响应时间响应时间响应时间响应时间：从用户通过键盘提交一个请求开始，直至系：从用户通过键盘提交一个请求开始，直至系：从用户通过键盘提交一个请求开始，直至系：从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说，直到屏幕上显示统首次产生响应为止的时间，或者说，直到屏幕上显示统首次产生响应为止的时间，或者说，直到屏幕上显示统首次产生响应为止的时间，或者说，直到屏幕上显示出结果为止的一段时间间隔。出结果为止的一段时间间隔。出结果为止的一段时间间隔。出结果为止的一段时间间隔。包括三部分时间：从键盘输入

39、的请求信息传送到处理机包括三部分时间：从键盘输入的请求信息传送到处理机包括三部分时间：从键盘输入的请求信息传送到处理机包括三部分时间：从键盘输入的请求信息传送到处理机的时间，处理机对请求信息进行处理的时间，以及将所的时间，处理机对请求信息进行处理的时间，以及将所的时间，处理机对请求信息进行处理的时间，以及将所的时间，处理机对请求信息进行处理的时间，以及将所形成的响应信息回送到终端显示器的时间。形成的响应信息回送到终端显示器的时间。形成的响应信息回送到终端显示器的时间。形成的响应信息回送到终端显示器的时间。 第三章处理机调度与死锁 (3) (3) (3) (3) 截截截截止止止止时时时时间间间间

40、的的的的保保保保证证证证。这这这这是是是是评评评评价价价价实实实实时时时时系系系系统统统统性性性性能能能能的的的的重重重重要指标，因而是选择实时调度算法的重要准则。要指标，因而是选择实时调度算法的重要准则。要指标，因而是选择实时调度算法的重要准则。要指标，因而是选择实时调度算法的重要准则。 截截截截止止止止时时时时间间间间：是是是是指指指指某某某某任任任任务务务务必必必必须须须须开开开开始始始始执执执执行行行行的的的的最最最最迟迟迟迟时时时时间间间间，或或或或必必必必须完成的最迟时间。须完成的最迟时间。须完成的最迟时间。须完成的最迟时间。(4) (4) (4) (4) 优先权准则。优先权准则。

41、优先权准则。优先权准则。在批处理、分时和实时系统中选在批处理、分时和实时系统中选在批处理、分时和实时系统中选在批处理、分时和实时系统中选择调度算法时，都可遵循优先权准则，以便让某些紧急的作择调度算法时，都可遵循优先权准则，以便让某些紧急的作择调度算法时，都可遵循优先权准则，以便让某些紧急的作择调度算法时，都可遵循优先权准则，以便让某些紧急的作业能得到及时处理。在要求较严格的场合，往往还须选择抢业能得到及时处理。在要求较严格的场合，往往还须选择抢业能得到及时处理。在要求较严格的场合，往往还须选择抢业能得到及时处理。在要求较严格的场合，往往还须选择抢占式调度方式，才能保证紧急作业得到及时处理。占式

42、调度方式，才能保证紧急作业得到及时处理。占式调度方式，才能保证紧急作业得到及时处理。占式调度方式，才能保证紧急作业得到及时处理。 第三章处理机调度与死锁 2 2 2 2面向系统的准则面向系统的准则面向系统的准则面向系统的准则(1) (1) (1) (1) 系系系系统统统统吞吞吞吞吐吐吐吐量量量量高高高高。这这这这是是是是用用用用于于于于评评评评价价价价批批批批处处处处理理理理系系系系统统统统性性性性能能能能的的的的另一个重要指标，因而是选择批处理作业调度的重要准则。另一个重要指标，因而是选择批处理作业调度的重要准则。另一个重要指标，因而是选择批处理作业调度的重要准则。另一个重要指标，因而是选择

43、批处理作业调度的重要准则。 吞吐量吞吐量吞吐量吞吐量：指在单位时间内系统所完成的作业数。：指在单位时间内系统所完成的作业数。：指在单位时间内系统所完成的作业数。：指在单位时间内系统所完成的作业数。 与与与与批批批批处处处处理理理理作作作作业业业业的的的的平平平平均均均均长长长长度度度度具具具具有有有有密密密密切切切切关关关关系系系系。对对对对于于于于同同同同一一一一批批批批作作作作业业业业，若若若若采采采采用用用用了了了了较较较较好好好好的的的的调调调调度度度度方方方方式式式式和和和和算算算算法法法法，则则则则可可可可显显显显著著著著地地地地提提提提高高高高系统的吞吐量。系统的吞吐量。系统的吞

44、吐量。系统的吞吐量。 第三章处理机调度与死锁 (2) (2) (2) (2) 处理机利用率好。处理机利用率好。处理机利用率好。处理机利用率好。 (3) (3) (3) (3) 各类资源的平衡利用。各类资源的平衡利用。各类资源的平衡利用。各类资源的平衡利用。 在大、中型系统中，不仅要使处理机的利用率高，而在大、中型系统中，不仅要使处理机的利用率高，而在大、中型系统中，不仅要使处理机的利用率高，而在大、中型系统中，不仅要使处理机的利用率高，而且还应能有效地利用其它各类资源，如内存、外存和且还应能有效地利用其它各类资源，如内存、外存和且还应能有效地利用其它各类资源，如内存、外存和且还应能有效地利用其

45、它各类资源，如内存、外存和I/OI/OI/OI/O设设设设备等。选择适当的调度方式和算法可以保持系统中各类资源备等。选择适当的调度方式和算法可以保持系统中各类资源备等。选择适当的调度方式和算法可以保持系统中各类资源备等。选择适当的调度方式和算法可以保持系统中各类资源都处于忙碌状态。但对于微型机和某些实时系统而言，准则都处于忙碌状态。但对于微型机和某些实时系统而言，准则都处于忙碌状态。但对于微型机和某些实时系统而言，准则都处于忙碌状态。但对于微型机和某些实时系统而言，准则(2)(3)(2)(3)(2)(3)(2)(3)并不重要。并不重要。并不重要。并不重要。 第三章处理机调度与死锁 n 设计调度

46、算法时考虑的因素设计调度算法时考虑的因素 应与系统的整个设计目标一致。应与系统的整个设计目标一致。应与系统的整个设计目标一致。应与系统的整个设计目标一致。 系统资源的均衡使用。系统资源的均衡使用。系统资源的均衡使用。系统资源的均衡使用。 平衡系统和用户要求。平衡系统和用户要求。平衡系统和用户要求。平衡系统和用户要求。 大多数系统都根据用户的需要而采用兼大多数系统都根据用户的需要而采用兼大多数系统都根据用户的需要而采用兼大多数系统都根据用户的需要而采用兼顾某些目标的简单调度算法顾某些目标的简单调度算法顾某些目标的简单调度算法顾某些目标的简单调度算法3.3调调度度算算法法 第三章处理机调度与死锁

47、3.3调调度度算算法法3.2.13.2.13.2.13.2.1先来先服务和短作业先来先服务和短作业先来先服务和短作业先来先服务和短作业( ( ( (进程进程进程进程) ) ) )优先调度算法优先调度算法优先调度算法优先调度算法1 1先来先服务调度算法先来先服务调度算法先来先服务先来先服务先来先服务先来先服务(FCFS (FCFS (FCFS (FCFS FirstFirstcomecomefirstfirstservedserved ) ) ) )调度算法是一种调度算法是一种调度算法是一种调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程最简单的调度算法，该算法既可用于作业调

48、度，也可用于进程最简单的调度算法，该算法既可用于作业调度，也可用于进程最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。调度。调度。调度。 当在作业调度中采用该算法时，每次调度都是从后备作业当在作业调度中采用该算法时，每次调度都是从后备作业当在作业调度中采用该算法时，每次调度都是从后备作业当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内队列中选择一个或多个最先进入该队列的作业，将它们调入内队列中选择一个或多个最先进入该队列的作业，将它们调入内队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后

49、放入就绪队列。在进程存，为它们分配资源、创建进程，然后放入就绪队列。在进程存，为它们分配资源、创建进程，然后放入就绪队列。在进程存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用调度中采用调度中采用调度中采用FCFSFCFSFCFSFCFS算法时，则每次调度是从就绪队列中选择一个算法时，则每次调度是从就绪队列中选择一个算法时，则每次调度是从就绪队列中选择一个算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该最先进入该队列的进程，为之分配处理机，使之投入运行。该最先进入该队列的进程，为之分配处理机，使之投入运行。该最先进入该队列的进程，为

50、之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。进程一直运行到完成或发生某事件而阻塞后才放弃处理机。进程一直运行到完成或发生某事件而阻塞后才放弃处理机。进程一直运行到完成或发生某事件而阻塞后才放弃处理机。 第三章处理机调度与死锁 FCFSFCFSFCFSFCFS算法比较有利于长作业算法比较有利于长作业算法比较有利于长作业算法比较有利于长作业( ( ( (进程进程进程进程) ) ) )，而不利于短作业，而不利于短作业，而不利于短作业，而不利于短作业( ( ( (进程进程进程进程) ) ) )。下表列出了。下表列出了。下表列出了。下表列出了A A A A、B B

51、B B、C C C C、D D D D四个作业分别到达系统的四个作业分别到达系统的四个作业分别到达系统的四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时时间、要求服务的时间、开始执行的时间及各自的完成时时间、要求服务的时间、开始执行的时间及各自的完成时时间、要求服务的时间、开始执行的时间及各自的完成时间，并计算出各自的周转时间和带权周转时间。间，并计算出各自的周转时间和带权周转时间。间，并计算出各自的周转时间和带权周转时间。间，并计算出各自的周转时间和带权周转时间。 第三章处理机调度与死锁 从表上可以看出，其中短作业从表上可以看出，其中短作业从表上可以看出，其中短作业从

52、表上可以看出，其中短作业C C C C的带权周转时间竞高达的带权周转时间竞高达的带权周转时间竞高达的带权周转时间竞高达100100100100，这是不能容忍的；而长作业，这是不能容忍的；而长作业，这是不能容忍的；而长作业，这是不能容忍的；而长作业D D D D的带权周转时间仅为的带权周转时间仅为的带权周转时间仅为的带权周转时间仅为1.991.991.991.99。据此可知，据此可知，据此可知，据此可知，FCFSFCFSFCFSFCFS调度算法调度算法调度算法调度算法有利于有利于有利于有利于CPUCPUCPUCPU繁忙型的作业繁忙型的作业繁忙型的作业繁忙型的作业，而不利于，而不利于，而不利于，而

53、不利于I/OI/OI/OI/O繁忙型的作业繁忙型的作业繁忙型的作业繁忙型的作业( ( ( (进程进程进程进程).).).).第三章处理机调度与死锁 在此，我们通过一个例子来说明采用在此，我们通过一个例子来说明采用在此，我们通过一个例子来说明采用在此，我们通过一个例子来说明采用FCFSFCFSFCFSFCFS调度算法时的调度算法时的调度算法时的调度算法时的调度性能。图调度性能。图调度性能。图调度性能。图3-4(a)3-4(a)3-4(a)3-4(a)示出有五个进程示出有五个进程示出有五个进程示出有五个进程A A A A、B B B B、C C C C、D D D D、E E E E，它们到它们到

54、它们到它们到达的时间分别是达的时间分别是达的时间分别是达的时间分别是0 0 0 0、1 1 1 1、2 2 2 2、3 3 3 3和和和和4 4 4 4，所要求的服务时间分别是，所要求的服务时间分别是，所要求的服务时间分别是，所要求的服务时间分别是4 4 4 4、3 3 3 3、5 5 5 5、2 2 2 2和和和和4 4 4 4，其完成时间分别是，其完成时间分别是，其完成时间分别是，其完成时间分别是4 4 4 4、7 7 7 7、12121212、14141414和和和和18181818。从每个。从每个。从每个。从每个进程的完成时间中减去其到达时间，即得到其周转时间，进进程的完成时间中减去其

55、到达时间，即得到其周转时间，进进程的完成时间中减去其到达时间，即得到其周转时间，进进程的完成时间中减去其到达时间，即得到其周转时间，进而可以算出每个进程的带权周转时间。而可以算出每个进程的带权周转时间。而可以算出每个进程的带权周转时间。而可以算出每个进程的带权周转时间。 第三章处理机调度与死锁 图3-4FCFS和SJF调度算法的性能 第三章处理机调度与死锁 2 2 2 2短作业短作业短作业短作业( ( ( (进程进程进程进程) ) ) )优先调度算法优先调度算法优先调度算法优先调度算法短作业短作业短作业短作业( ( ( (进程进程进程进程) ) ) )优先调度算法优先调度算法优先调度算法优先调

56、度算法SJ(P)FSJ(P)FSJ(P)FSJ(P)F（ShortestjobShortestjobfirstfirst ），是指对短作业或短进程优先调度的算法。它们可以分别用于作是指对短作业或短进程优先调度的算法。它们可以分别用于作是指对短作业或短进程优先调度的算法。它们可以分别用于作是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先业调度和进程调度。短作业优先业调度和进程调度。短作业优先业调度和进程调度。短作业优先(SJF)(SJF)(SJF)(SJF)的调度算法是从后备队的调度算法是从后备队的调度算法是从后备队的调度算法是从后备队列中选择一个或若干个估计运

57、行时间最短的作业，将它们调入列中选择一个或若干个估计运行时间最短的作业，将它们调入列中选择一个或若干个估计运行时间最短的作业，将它们调入列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先内存运行。而短进程优先内存运行。而短进程优先内存运行。而短进程优先(SPF)(SPF)(SPF)(SPF)调度算法则是从就绪队列中选调度算法则是从就绪队列中选调度算法则是从就绪队列中选调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立出一个估计运行时间最短的进程，将处理机分配给它，使它立出一个估计运行时间最短的进程，将处理机分配给它，使它立出一个估计运行时

58、间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。时再重新调度。时再重新调度。时再重新调度。 和和和和FCFSFCFS调度算法进行比较调度算法进行比较调度算法进行比较调度算法进行比较第三章处理机调度与死锁 SJ(P)FSJ(P)FSJ(P)FSJ(P)F调度算法缺点：调度算法缺点：调度算法缺点：调度算法缺点：(1) (1) (1) (1) 该算法对长作业不利，可能出现饥饿现象该算

59、法对长作业不利，可能出现饥饿现象该算法对长作业不利，可能出现饥饿现象该算法对长作业不利，可能出现饥饿现象(2) (2) (2) (2) 因因因因而而而而不不不不能能能能保保保保证证证证紧紧紧紧迫迫迫迫性性性性作作作作业业业业( ( ( (进进进进程程程程) ) ) )会会会会被被被被及及及及时时时时处理。处理。处理。处理。(3) (3) (3) (3) 不一定能真正做到短作业优先调度。不一定能真正做到短作业优先调度。不一定能真正做到短作业优先调度。不一定能真正做到短作业优先调度。 第三章处理机调度与死锁 作业作业提交时间提交时间执行时间执行时间开始时间开始时间完成时间完成时间周转时间周转时间带

60、权带权周转周转时间时间18.002.0028.500.5039.000.1049.500.20平均周转时间平均周转时间t=平均带权周转时间平均带权周转时间w=FCFSFCFS、SJFSJF算法填表（单位：小时，并以十算法填表（单位：小时，并以十算法填表（单位：小时，并以十算法填表（单位：小时，并以十进制计）进制计）进制计）进制计）第三章处理机调度与死锁 3.3.23.3.23.3.23.3.2高优先权优先调度算法高优先权优先调度算法高优先权优先调度算法高优先权优先调度算法1 1 1 1优先权调度算法的类型优先权调度算法的类型优先权调度算法的类型优先权调度算法的类型n n 为了照顾紧迫型作业为了

61、照顾紧迫型作业为了照顾紧迫型作业为了照顾紧迫型作业/ / / /进程，使之在进入系统后便获得进程，使之在进入系统后便获得进程，使之在进入系统后便获得进程，使之在进入系统后便获得优先处理，引入了最高优先权优先优先处理，引入了最高优先权优先优先处理，引入了最高优先权优先优先处理，引入了最高优先权优先(FPF(FPF(FPF(FPF、HPF=highestHPF=highestpriority firstpriority first ) ) ) )调度算法。调度算法。调度算法。调度算法。n n 作为作业调度算法（作为作业调度算法（作为作业调度算法（作为作业调度算法（批处理批处理批处理批处理）n n

62、作为进程调度算法（作为进程调度算法（作为进程调度算法（作为进程调度算法（分时、实时分时、实时分时、实时分时、实时）n n 用于作业调度时，系统将从后备队列中选择若干个优用于作业调度时，系统将从后备队列中选择若干个优用于作业调度时，系统将从后备队列中选择若干个优用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。先权最高的作业装入内存。先权最高的作业装入内存。先权最高的作业装入内存。n n 用于进程调度时，把处理机分配给就绪队列中优先权用于进程调度时，把处理机分配给就绪队列中优先权用于进程调度时，把处理机分配给就绪队列中优先权用于进程调度时，把处理机分配给就绪队列中优先权最高的

63、进程。最高的进程。最高的进程。最高的进程。第三章处理机调度与死锁 n n 作为进程调度算法作为进程调度算法作为进程调度算法作为进程调度算法1) 1) 1) 1) 非抢占式优先权算法非抢占式优先权算法非抢占式优先权算法非抢占式优先权算法在这种方式下，系统一旦把处理机分配给就绪队列中优在这种方式下，系统一旦把处理机分配给就绪队列中优在这种方式下，系统一旦把处理机分配给就绪队列中优在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或先权最高的进程后，该进程便一直执行下去，直至完成；或先权最高的进程后，该进程便一直执行下去，直至完成；或先权最高的进程后，

64、该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机因发生某事件使该进程放弃处理机时，系统方可再将处理机因发生某事件使该进程放弃处理机时，系统方可再将处理机因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。重新分配给另一优先权最高的进程。重新分配给另一优先权最高的进程。重新分配给另一优先权最高的进程。 主要用于主要用于主要用于主要用于批处理系统进程调度批处理系统进程调度批处理系统进程调度批处理系统进程调度中；也可用于某些对实时性中；也可用于某些对实时性中；也可用于某些对实时性中；也可用于某些对实时性要求不严的实时系统中。要求不

65、严的实时系统中。要求不严的实时系统中。要求不严的实时系统中。 第三章处理机调度与死锁 2) 2) 2) 2) 抢占式优先权调度算法抢占式优先权调度算法抢占式优先权调度算法抢占式优先权调度算法系统把处理机分配给优先权最高的进程，使之执行。但系统把处理机分配给优先权最高的进程，使之执行。但系统把处理机分配给优先权最高的进程，使之执行。但系统把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，在其执行期间，只要又出现了另一个其优先权更高的进程，在其执行期间，只要又出现了另一个其优先权更高的进程，在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程

66、序就进程调度程序就进程调度程序就进程调度程序就立即停止当前进程立即停止当前进程立即停止当前进程立即停止当前进程( ( ( (原优先权最高的进程原优先权最高的进程原优先权最高的进程原优先权最高的进程) ) ) )的的的的执行，重新将处理机分配给新到的优先权最高的进程。执行，重新将处理机分配给新到的优先权最高的进程。执行，重新将处理机分配给新到的优先权最高的进程。执行，重新将处理机分配给新到的优先权最高的进程。 这种抢占式的优先权调度算法能更好地满足紧迫作业的要这种抢占式的优先权调度算法能更好地满足紧迫作业的要这种抢占式的优先权调度算法能更好地满足紧迫作业的要这种抢占式的优先权调度算法能更好地满足

67、紧迫作业的要求，故而常用于要求比较严格的求，故而常用于要求比较严格的求，故而常用于要求比较严格的求，故而常用于要求比较严格的实时实时实时实时系统中，以及对性能要系统中，以及对性能要系统中，以及对性能要系统中，以及对性能要求较高的批处理和分时系统中。求较高的批处理和分时系统中。求较高的批处理和分时系统中。求较高的批处理和分时系统中。 第三章处理机调度与死锁 2 2 2 2优先权的类型优先权的类型优先权的类型优先权的类型 如何确定？如何确定？如何确定？如何确定？ 1) 1) 1) 1) 静态优先权静态优先权静态优先权静态优先权n作业的优先级确定原则作业的优先级确定原则作业的优先级确定原则作业的优先

68、级确定原则作业的紧急程度作业的紧急程度作业的紧急程度作业的紧急程度作业类型作业类型作业类型作业类型作业要求资源情况作业要求资源情况作业要求资源情况作业要求资源情况第三章处理机调度与死锁 n 进程的优先级确定原则进程的优先级确定原则进程的优先级确定原则进程的优先级确定原则 按进程的类型赋予不同的优先级按进程的类型赋予不同的优先级按进程的类型赋予不同的优先级按进程的类型赋予不同的优先级 用户进程类型：用户进程类型：用户进程类型：用户进程类型：I/O I/O I/O I/O 忙，忙，忙，忙，CPUCPUCPUCPU忙，忙，忙，忙， I/OI/OI/OI/O与与与与CPU CPU CPU CPU 均衡

69、均衡均衡均衡 系统进程类型：调度进程，系统进程类型：调度进程，系统进程类型：调度进程，系统进程类型：调度进程，I/O I/O I/O I/O 进程，中断进程，中断进程，中断进程，中断处理，存储各类等。处理，存储各类等。处理，存储各类等。处理，存储各类等。 进程对资源的要求进程对资源的要求进程对资源的要求进程对资源的要求 用户要求用户要求用户要求用户要求 将作业的静态优先级作为它所属进程的优将作业的静态优先级作为它所属进程的优将作业的静态优先级作为它所属进程的优将作业的静态优先级作为它所属进程的优先级。先级。先级。先级。 静态优先权静态优先权静态优先权静态优先权特点特点特点特点：简单易行，系统开

70、销小；不：简单易行，系统开销小；不：简单易行，系统开销小；不：简单易行，系统开销小；不够精确，可能出现优先级低的作业或进程，长期得够精确，可能出现优先级低的作业或进程，长期得够精确，可能出现优先级低的作业或进程，长期得够精确，可能出现优先级低的作业或进程，长期得不到调度。不到调度。不到调度。不到调度。第三章处理机调度与死锁 2) 2) 2) 2) 动态优先权动态优先权动态优先权动态优先权动态优先权是指在创建进程时所赋予的优先权，是可以动态优先权是指在创建进程时所赋予的优先权，是可以动态优先权是指在创建进程时所赋予的优先权，是可以动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其

71、等待时间的增加而改变的，以便获得更随进程的推进或随其等待时间的增加而改变的，以便获得更随进程的推进或随其等待时间的增加而改变的，以便获得更随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。好的调度性能。好的调度性能。好的调度性能。 改变进程优先级的方式：改变进程优先级的方式：改变进程优先级的方式：改变进程优先级的方式： 线形优先级调度策略线形优先级调度策略线形优先级调度策略线形优先级调度策略 新创建的进程按新创建的进程按新创建的进程按新创建的进程按FCFSFCFSFCFSFCFS方式排成就绪队列，优先级以方式排成就绪队列，优先级以方式排成就绪队列，优先级以方式排成就绪队列，优先

72、级以a a a a的速率的速率的速率的速率增加，正在执行的进程优先级以增加，正在执行的进程优先级以增加，正在执行的进程优先级以增加，正在执行的进程优先级以b b b b的速率下降。的速率下降。的速率下降。的速率下降。 非线形改变优先级规则非线形改变优先级规则非线形改变优先级规则非线形改变优先级规则第三章处理机调度与死锁 3 3 3 3高响应比优先调度算法高响应比优先调度算法高响应比优先调度算法高响应比优先调度算法（HRN） 先先先先来来来来先先先先服服服服务务务务和和和和短短短短作作作作业业业业优优优优先先先先算算算算法法法法都都都都有有有有其其其其片片片片面面面面性性性性，先先先先来来来来先

73、先先先服服服服务务务务调调调调度度度度算算算算法法法法只只只只考考考考虑虑虑虑作作作作业业业业的的的的等等等等待待待待时时时时间间间间，而而而而忽忽忽忽视视视视了了了了作作作作业业业业的的的的运运运运行行行行时时时时间间间间，短短短短作作作作业业业业优优优优先先先先算算算算法法法法则则则则相相相相反反反反，只只只只考考考考虑虑虑虑了了了了作作作作业业业业的的的的运运运运行行行行时时时时间间间间，而而而而忽忽忽忽视视视视了了了了作作作作业业业业的的的的等等等等待待待待时时时时间间间间。HRN （HighestHighest ResponseResponse-ratio-ratioNextNext

74、）是）是）是）是对对对对FCFSFCFS和和和和SJFSJF方式的一种综合平衡。方式的一种综合平衡。方式的一种综合平衡。方式的一种综合平衡。第三章处理机调度与死锁 由于等待时间与服务时间之和就是系统对该作业的响应由于等待时间与服务时间之和就是系统对该作业的响应由于等待时间与服务时间之和就是系统对该作业的响应由于等待时间与服务时间之和就是系统对该作业的响应时间，故时间，故时间，故时间，故响应比响应比响应比响应比R R R RP P P P = = = =优先权。据此，又可表示为：优先权。据此，又可表示为：优先权。据此，又可表示为：优先权。据此，又可表示为： 每当要进行调度时，系统计算每个作业的响

75、应比，每当要进行调度时，系统计算每个作业的响应比，每当要进行调度时，系统计算每个作业的响应比，每当要进行调度时，系统计算每个作业的响应比，选择其中选择其中选择其中选择其中R RP P最大者最大者最大者最大者投入执行。投入执行。投入执行。投入执行。第三章处理机调度与死锁 由上式可以看出：由上式可以看出：由上式可以看出：由上式可以看出：(1) (1) (1) (1) 如如如如果果果果作作作作业业业业的的的的等等等等待待待待时时时时间间间间相相相相同同同同，则则则则要要要要求求求求服服服服务务务务的的的的时时时时间间间间愈愈愈愈短短短短，其优先权愈高，因而该算法有利于短作业。其优先权愈高，因而该算法

76、有利于短作业。其优先权愈高，因而该算法有利于短作业。其优先权愈高，因而该算法有利于短作业。(2) (2) (2) (2) 当要求服务的时间相同时，作业的优先权决定于其当要求服务的时间相同时，作业的优先权决定于其当要求服务的时间相同时，作业的优先权决定于其当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是等待时间，等待时间愈长，其优先权愈高，因而它实现的是等待时间，等待时间愈长，其优先权愈高，因而它实现的是等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。先来先服务。先来先服务。先来先服务。 (3) (3) (3) (3) 对对对对于于

77、于于长长长长作作作作业业业业，作作作作业业业业的的的的优优优优先先先先级级级级可可可可以以以以随随随随等等等等待待待待时时时时间间间间的的的的增增增增加加加加而而而而提提提提高高高高，当当当当其其其其等等等等待待待待时时时时间间间间足足足足够够够够长长长长时时时时，其其其其优优优优先先先先级级级级便便便便可可可可升升升升到到到到很很很很高高高高，从而也可获得处理机。从而也可获得处理机。从而也可获得处理机。从而也可获得处理机。n n长短作业都得到照顾，但是增加系统开销。长短作业都得到照顾，但是增加系统开销。长短作业都得到照顾，但是增加系统开销。长短作业都得到照顾，但是增加系统开销。 第三章处理机

78、调度与死锁 n这样算法从这样算法从理论理论上讲是比较完备的，但上讲是比较完备的，但作业调度程序要统计作业的等待时间，作业调度程序要统计作业的等待时间，使用用户的估计的运行时间，并要作浮使用用户的估计的运行时间，并要作浮点运算（这是系统程序最忌讳的）浪费点运算（这是系统程序最忌讳的）浪费大量的计算时间，这是系统程序所不允大量的计算时间，这是系统程序所不允许的。许的。第三章处理机调度与死锁 3.3.33.3.33.3.33.3.3基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法基于时间片的轮转调度算法1 1 1 1时间片轮转法时间片轮转法时间片轮转法时间片轮转法1) 1)

79、1) 1) 基本原理基本原理基本原理基本原理将将将将CPU CPU CPU CPU 的处理时间分成固定大小的时间片，系统将所有就的处理时间分成固定大小的时间片，系统将所有就的处理时间分成固定大小的时间片，系统将所有就的处理时间分成固定大小的时间片，系统将所有就绪进程按先来先服务的原则排成队列。每次调度时，把绪进程按先来先服务的原则排成队列。每次调度时，把绪进程按先来先服务的原则排成队列。每次调度时，把绪进程按先来先服务的原则排成队列。每次调度时，把CPUCPUCPUCPU分分分分配给队首进程，令其执行一个时间片，时间片用完后，若进程配给队首进程，令其执行一个时间片，时间片用完后，若进程配给队首

80、进程，令其执行一个时间片，时间片用完后，若进程配给队首进程，令其执行一个时间片，时间片用完后，若进程未结束，则重新排入就绪队列尾部。未结束，则重新排入就绪队列尾部。未结束，则重新排入就绪队列尾部。未结束，则重新排入就绪队列尾部。 2 2 2 2）时间片的划分）时间片的划分）时间片的划分）时间片的划分简单循环轮转调度简单循环轮转调度简单循环轮转调度简单循环轮转调度时间片时间片时间片时间片 Q=R/Q=R/Q=R/Q=R/NmaxNmaxNmaxNmax R R R R：响应时间：响应时间：响应时间：响应时间 NmaxNmaxNmaxNmax：最大进程数：最大进程数：最大进程数：最大进程数 可变时

81、间片轮转调度可变时间片轮转调度可变时间片轮转调度可变时间片轮转调度时间片时间片时间片时间片 Q=R/N RQ=R/N RQ=R/N RQ=R/N R：响应时间：响应时间：响应时间：响应时间 N N N N：实际进程数：实际进程数：实际进程数：实际进程数第三章处理机调度与死锁 2) 2) 2) 2) 时间片大小的确定时间片大小的确定时间片大小的确定时间片大小的确定时时时时间间间间片片片片很很很很小小小小：将将将将有有有有利利利利于于于于短短短短作作作作业业业业，会会会会频频频频繁繁繁繁地地地地发发发发生生生生中中中中断断断断、进进进进程程程程上下文的切换，从而增加系统的开销；上下文的切换，从而增

82、加系统的开销；上下文的切换，从而增加系统的开销；上下文的切换，从而增加系统的开销； 时时时时间间间间片片片片太太太太长长长长，使使使使得得得得每每每每个个个个进进进进程程程程都都都都能能能能在在在在一一一一个个个个时时时时间间间间片片片片内内内内完完完完成成成成，时时时时间间间间片片片片轮轮轮轮转转转转算算算算法法法法便便便便退退退退化化化化为为为为FCFSFCFSFCFSFCFS算算算算法法法法，无无无无法法法法满满满满足足足足交交交交互互互互式式式式用用用用户户户户的的的的需需需需求求求求。若若若若取取取取时时时时间间间间片片片片略略略略大大大大于于于于一一一一次次次次典典典典型型型型的的

83、的的交交交交互互互互所所所所需需需需要要要要的的的的时时时时间间间间，这这这这样样样样可可可可使使使使大大大大多数进程在一个时间片内完成。多数进程在一个时间片内完成。多数进程在一个时间片内完成。多数进程在一个时间片内完成。图图图图3-53-5示出了时间片分别为示出了时间片分别为示出了时间片分别为示出了时间片分别为q q=1=1和和和和q q=4=4时，时，时，时，A A、B B、C C、D D、E E五个进程的运行情况，而图五个进程的运行情况，而图五个进程的运行情况，而图五个进程的运行情况，而图3-63-6为为为为q q=1=1和和和和q q=4=4时各进程的平均周时各进程的平均周时各进程的平

84、均周时各进程的平均周转时间和带权平均周转时间。图中的转时间和带权平均周转时间。图中的转时间和带权平均周转时间。图中的转时间和带权平均周转时间。图中的RRRR(RoundRobin)(RoundRobin)表示轮表示轮表示轮表示轮转调度算法。转调度算法。转调度算法。转调度算法。 第三章处理机调度与死锁 图3-5 q=1和q=4时的进程运行情况 A、B、C、D、E？A:4 B:3 C:4 D:2 E:4第三章处理机调度与死锁 图3-6 q=1和q=4时进程的周转时间 第三章处理机调度与死锁 2 2多级反馈队列调度算法多级反馈队列调度算法(1) (1) (1) (1) 设置多个就绪队列，并为各个队列

85、赋予不同的优先设置多个就绪队列，并为各个队列赋予不同的优先设置多个就绪队列，并为各个队列赋予不同的优先设置多个就绪队列，并为各个队列赋予不同的优先级。级。级。级。第一个队列的优先级最高，第二个队列次之，其余各队第一个队列的优先级最高，第二个队列次之，其余各队第一个队列的优先级最高，第二个队列次之，其余各队第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间列的优先权逐个降低。该算法赋予各个队列中进程执行时间列的优先权逐个降低。该算法赋予各个队列中进程执行时间列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，片的大小也各不相同

86、，片的大小也各不相同，片的大小也各不相同，在优先权愈高的队列中，为每个进程在优先权愈高的队列中，为每个进程在优先权愈高的队列中，为每个进程在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小所规定的执行时间片就愈小所规定的执行时间片就愈小所规定的执行时间片就愈小。例如，第二个队列的时间片要。例如，第二个队列的时间片要。例如，第二个队列的时间片要。例如，第二个队列的时间片要比第一个队列的时间比第一个队列的时间比第一个队列的时间比第一个队列的时间片长一倍片长一倍片长一倍片长一倍，第，第，第，第i+1i+1i+1i+1个队列的时间片个队列的时间片个队列的时间片个队列的时间片要比第要比第要比第要比

87、第i i i i个队列的时间片长一倍。图个队列的时间片长一倍。图个队列的时间片长一倍。图个队列的时间片长一倍。图3-73-73-73-7是多级反馈队列算法是多级反馈队列算法是多级反馈队列算法是多级反馈队列算法的示意。的示意。的示意。的示意。 第三章处理机调度与死锁 图 3-7多级反馈队列调度算法 第三章处理机调度与死锁 多级反馈轮转法多级反馈轮转法多级反馈轮转法多级反馈轮转法设置多个就绪队列设置多个就绪队列设置多个就绪队列设置多个就绪队列, , , ,每个队列赋予不同地优先级。队列每个队列赋予不同地优先级。队列每个队列赋予不同地优先级。队列每个队列赋予不同地优先级。队列按按按按FCFSFCFS

88、FCFSFCFS原则排列。原则排列。原则排列。原则排列。各队列时间片不同。各队列时间片不同。各队列时间片不同。各队列时间片不同。当一个新进程进入内存后，首先放在第一队列尾，按当一个新进程进入内存后，首先放在第一队列尾，按当一个新进程进入内存后，首先放在第一队列尾，按当一个新进程进入内存后，首先放在第一队列尾，按FCFSFCFSFCFSFCFS原则调度；如果该时间片内未结束，转入第二队列尾；原则调度；如果该时间片内未结束，转入第二队列尾；原则调度；如果该时间片内未结束，转入第二队列尾；原则调度；如果该时间片内未结束，转入第二队列尾；直到最后的第直到最后的第直到最后的第直到最后的第N N N N队

89、列，在第队列，在第队列，在第队列，在第N N N N队列中便采取按时间片轮转的队列中便采取按时间片轮转的队列中便采取按时间片轮转的队列中便采取按时间片轮转的方式执行（不在转下一个队列了，因为没有了）。方式执行（不在转下一个队列了，因为没有了）。方式执行（不在转下一个队列了，因为没有了）。方式执行（不在转下一个队列了，因为没有了）。仅当第仅当第仅当第仅当第i i i i队列空闲时，才调度第队列空闲时，才调度第队列空闲时，才调度第队列空闲时，才调度第i+1i+1i+1i+1队列。如有新进程进队列。如有新进程进队列。如有新进程进队列。如有新进程进入优先级较高的队列，则剥夺入优先级较高的队列，则剥夺入

90、优先级较高的队列，则剥夺入优先级较高的队列，则剥夺CPUCPUCPUCPU执行新进程，旧进程放执行新进程，旧进程放执行新进程，旧进程放执行新进程，旧进程放入原队列尾入原队列尾入原队列尾入原队列尾第三章处理机调度与死锁 3 3 3 3多级反馈队列调度多级反馈队列调度多级反馈队列调度多级反馈队列调度算法性能算法性能算法性能算法性能 终端型用户：在第一队列中完成，作业短，终端型用户：在第一队列中完成，作业短，终端型用户：在第一队列中完成，作业短，终端型用户：在第一队列中完成，作业短，交互型。交互型。交互型。交互型。 短批处理用户：周转时间较短，通常三个队短批处理用户：周转时间较短，通常三个队短批处理

91、用户：周转时间较短，通常三个队短批处理用户：周转时间较短，通常三个队列即可完成。列即可完成。列即可完成。列即可完成。 长批处理作业用户：依次在前长批处理作业用户：依次在前长批处理作业用户：依次在前长批处理作业用户：依次在前N-1N-1N-1N-1个队列中执个队列中执个队列中执个队列中执行，在第行，在第行，在第行，在第N N N N个队列中按轮转方式运行。个队列中按轮转方式运行。个队列中按轮转方式运行。个队列中按轮转方式运行。第三章处理机调度与死锁 思考：如下调度用的进程状态变迁图，调度算法思考：如下调度用的进程状态变迁图，调度算法和调度效果如何？和调度效果如何？ 运行运行低低优先就绪优先就绪高

92、高优先就优先就绪绪等待等待首先选择首先选择100ms其次选择其次选择500ms请求请求I/OI/O完成完成超超时间片时间片第三章处理机调度与死锁 队列结构队列结构队列结构队列结构 I/OI/O等待队列等待队列等待队列等待队列一个进程如果请求一个进程如果请求一个进程如果请求一个进程如果请求I/OI/O，则进入则进入则进入则进入I/OI/O等待队列。等待队列。等待队列。等待队列。 低优先就绪队低优先就绪队低优先就绪队低优先就绪队一个进程如果在运行中超过了它的时间量就进入低优先就一个进程如果在运行中超过了它的时间量就进入低优先就一个进程如果在运行中超过了它的时间量就进入低优先就一个进程如果在运行中超

93、过了它的时间量就进入低优先就绪队列。绪队列。绪队列。绪队列。 高优先就绪队列高优先就绪队列高优先就绪队列高优先就绪队列当进程从等待状态变为就绪状态时则进入高优先就绪队列。当进程从等待状态变为就绪状态时则进入高优先就绪队列。当进程从等待状态变为就绪状态时则进入高优先就绪队列。当进程从等待状态变为就绪状态时则进入高优先就绪队列。第三章处理机调度与死锁 进程调度算法进程调度算法进程调度算法进程调度算法优先调度与时间片调度相结合的调度策略：优先调度与时间片调度相结合的调度策略：优先调度与时间片调度相结合的调度策略：优先调度与时间片调度相结合的调度策略：(1)(1)当当当当CPUCPU空闲时，若高优先就

94、绪队列非空，则从高优先就空闲时，若高优先就绪队列非空，则从高优先就空闲时，若高优先就绪队列非空，则从高优先就空闲时，若高优先就绪队列非空，则从高优先就绪队列中选择一个进程运行，分配时间片为绪队列中选择一个进程运行，分配时间片为绪队列中选择一个进程运行，分配时间片为绪队列中选择一个进程运行，分配时间片为100ms100ms。(2)(2)当当当当CPUCPU空闲时，若高优先就绪队列为空，则从低优先就空闲时，若高优先就绪队列为空，则从低优先就空闲时，若高优先就绪队列为空，则从低优先就空闲时，若高优先就绪队列为空，则从低优先就绪队列中选择一个进程运行，分配时间片为绪队列中选择一个进程运行，分配时间片为

95、绪队列中选择一个进程运行，分配时间片为绪队列中选择一个进程运行，分配时间片为500ms500ms。调度效果调度效果调度效果调度效果优先照顾了优先照顾了优先照顾了优先照顾了IOIO量大的进程；量大的进程；量大的进程；量大的进程；适当照顾了计算量大的进程。适当照顾了计算量大的进程。适当照顾了计算量大的进程。适当照顾了计算量大的进程。第三章处理机调度与死锁 运行运行低低优先优先就绪就绪高高优优先就先就绪绪因盘或带因盘或带I/O而等而等待待进程调度进程调度500ms请求盘请求盘或带或带I/OI/O完成完成超超时间片时间片中优先中优先就绪就绪因因终端终端I/O而等而等待待因因页面页面I/O而等而等待待进

96、程调度进程调度100ms进程调度进程调度100msI/O完成完成I/O完成完成请求终请求终端端I/O缺页中断缺页中断调度算法、效果？调度算法、效果？调度算法、效果？调度算法、效果？第三章处理机调度与死锁 思考思考n若在操作系统的就绪进程队列中等待运若在操作系统的就绪进程队列中等待运行的共有三个进程行的共有三个进程P1、P2、P3，已知它，已知它们各自的运行时间为们各自的运行时间为a、b、c，且满足关，且满足关系系abc。请证明采用最短作业优先调。请证明采用最短作业优先调度算法能够获得最小平均周转时间。度算法能够获得最小平均周转时间。第三章处理机调度与死锁 3.4实实时时调调度度3.4.13.4

97、.13.4.13.4.1实现实时调度的基本条件实现实时调度的基本条件实现实时调度的基本条件实现实时调度的基本条件1 1提供必要的信息提供必要的信息(1) (1) 就绪时间。就绪时间。(2) (2) 开始截止时间和完成截止时间。开始截止时间和完成截止时间。(3) (3) 处理时间。处理时间。(4) (4) 资源要求。资源要求。(5) (5) 优先级。优先级。2系统处理能力强系统处理能力强3采用抢占式调度机制采用抢占式调度机制4具有快速切换机制具有快速切换机制第三章处理机调度与死锁 3.4.23.4.23.4.23.4.2实时调度算法的分类实时调度算法的分类实时调度算法的分类实时调度算法的分类1

98、1非抢占式调度算法非抢占式调度算法1) 1) 非抢占式轮转调度算法非抢占式轮转调度算法数秒至数十秒的响应时间，可用于要求不太严格的实时控制系统中。 2)非抢占式优先调度算法非抢占式优先调度算法获得仅为数秒至数百毫秒级的响应时间，因而可用于有一定要求的实时控制系统中。 第三章处理机调度与死锁 2 2抢占式调度算法抢占式调度算法在在要要求求较较严严格格的的( (响响应应时时间间为为数数十十毫毫秒秒以以下下) )的的实实时时系系统统中中，应应采采用用抢抢占占式式优优先先权权调调度度算算法法。可可根根据据抢抢占占发发生生时时间间的的不不同同而而进一步分成以下两种调度算法。进一步分成以下两种调度算法。1

99、) 1) 基于时钟中断的抢占式优先权调度算法基于时钟中断的抢占式优先权调度算法2) 2) 立即抢占立即抢占(Immediate Preemption)(Immediate Preemption)的优先权调度算法的优先权调度算法第三章处理机调度与死锁 图3-8 实时进程调度 实时进程加入队尾等待下一个时间片实时进程加入队尾等待下一个时间片实时进程加入队首实时进程加入队首阻塞第三章处理机调度与死锁 3.4.33.4.3常用的几种实时调度算法常用的几种实时调度算法1 1 最最 早早 截截 止止 时时 间间 优优 先先 即即 EDF(Earliest EDF(Earliest Deadline Dea

100、dline First)First)算法算法1) 非抢占式调度方式用于非周期实时任务图3-9示出了将该算法用于非抢占调度方式之例。该例中具有四个非周期任务，它们先后到达。系统首先调度任务1执行，在任务1执行期间，任务2、3又先后到达。由于任务3的开始截止时间早于任务2，故系统在任务1后将调度任务3执行。在此期间又到达作业4，其开始截止时间仍是早于任务2的，故在任务3执行完后，系统又调度任务4执行，最后才调度任务2执行。 第三章处理机调度与死锁 图 3-9EDF算法用于非抢占调度的调度方式到达到达到达到达到达到达第三章处理机调度与死锁 2) 抢占式调度方式用于周期实时任务图3-10示出了将最早截

101、止时间优先算法用于抢占调度方式之例。在该例中有两个周期性任务，任务A的周期时间为20 ms，每个周期的处理时间为10 ms；任务B的周期时间为50 ms，每个周期的处理时间为25 ms。图中的第一行示出了两个任务的到达时间、最后期限和执行时间图。其中任务A的到达时间为0、20、40、；任务A的最后期限为20、40、60、；任务B的到达时间为0、50、100、；任务B的最后期限为50、100、150、(注：单位皆为ms)。 第三章处理机调度与死锁 图3-10 最早截止时间优先算法用于抢占调度方式之例最早截止时间优先算法用于抢占调度方式之例 最早截至时间优先调度最早截至时间优先调度最后期限最后期限

102、A到达就执行到达就执行B到达就执行到达就执行第三章处理机调度与死锁 第四行是采用最早截止时间优先算法的时间图。在t = 0时，A1和B1同时到达，由于A1的截止时间比B1早，故调度A1执行；在t = 10时，A1完成，又调度B1执行；在t = 20时，A2A2到达到达到达到达，由于A2的截止时间比B2早，B1被中断而调度A2执行；在t = 30时，A2完成，又重新调度B1执行；在t = 40时，A3又到达，但B1的截止时间要比A3早，仍应让B1继续执行直到完成(t = 45)，然后再调度A3执行；在t = 55时，A3完成，又调度B2执行。在该例中利用最早截止时间优先算法可以满足系统的要求。

103、第三章处理机调度与死锁 2 2最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)LLF(Least Laxity First)算法算法该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。例如，一个任务在200 ms时必须完成，而它本身所需的运行时间就有100 ms，因此，调度程序必须在100 ms之前调度执行，该任务的紧急程度(松弛程度)为100 ms。又如，另一任务在400 ms时必须完成，它本身需要运行 150 ms，则其松弛程度为 250 ms。在实现该算法时要求系统中有一个按松弛度排序的

104、实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。 第三章处理机调度与死锁 该算法主要用于可抢占调度方式中。假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。由此可得知任务A和B每次必须完成的时间分别为：A1、A2、A3、和B1、B2、B3、，见图3-11。为保证不遗漏任何一次截止时间，应采用最低松弛度优先的抢占调度策略。 第三章处理机调度与死锁 图 3-11A和B任务每次必须完成的时间 第三章处理机调度与死锁 在刚开始时(t1=0)，A

105、1必须在20 ms时完成，而它本身运行又需 10 ms，可算出A1的松弛度为10 ms；B1必须在50 ms时完成，而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2=10 ms时，A2的松弛度可按下式算出： A A2 2的松弛度的松弛度的松弛度的松弛度 =必须完成时间必须完成时间必须完成时间必须完成时间 - - - - 其本身的运行时间其本身的运行时间其本身的运行时间其本身的运行时间 - - - - 当前时间当前时间当前时间当前时间=40ms=40ms- - - -10ms10ms- - - -10ms=20ms10ms=20ms 第三章处理机调度

106、与死锁 类似地，可算出B1的松弛度为15 ms，故调度程序应选择B2运行。在t3=30 ms时，A2的松弛度已减为0(即40-10-30)，而B1的松弛度为15 ms(即50-5-30)，于是调度程序应抢占B1的处理机而调度A2运行。在t4=40 ms时，A3的松弛度为10 ms(即60-10-40)，而B1的松弛度仅为5 ms(即50-5-40)，故又应重新调度B1执行。在t5=45 ms时，B1执行完成，而此时A3的松弛度已减为5 ms(即60-10-45)，而B2的松弛度为30 ms(即100-25-45)，于是又应调度A3执行。在t6=55 ms时，任务A尚未进入第4周期，而任务B已进

107、入第2周期，故再调度B2执行。在t7=70 ms时，A4的松弛度已减至0 ms(即80-10-70)，而B2的松弛度为20 ms(即100-10-70)，故此时调度又应抢占B2的处理机而调度A4执行。图3-12示出了具有两个周期性实时任务的调度情况。 第三章处理机调度与死锁 图 3-12利用LLF算法进行调度的情况 第三章处理机调度与死锁 小结n处理机调度的基本算法处理机调度的基本算法处理机调度的基本算法处理机调度的基本算法先来先服务先来先服务先来先服务先来先服务 （FCFSFCFS）短进程优先短进程优先短进程优先短进程优先 （SPFSPF）高优先权调度高优先权调度高优先权调度高优先权调度 （

108、FPFFPF）时间片轮转（时间片轮转（时间片轮转（时间片轮转（RRRR） 多级反馈队列调度多级反馈队列调度多级反馈队列调度多级反馈队列调度n作业调度算法作业调度算法作业调度算法作业调度算法先来先服务先来先服务先来先服务先来先服务 （FCFSFCFS） 短作业优先短作业优先短作业优先短作业优先 （SJFSJF） 高优先权调度（高优先权调度（高优先权调度（高优先权调度（FPFFPF）高响应比优先（高响应比优先（高响应比优先（高响应比优先（HRNHRN） 实时调度实时调度实时调度实时调度最低松弛度优先即最低松弛度优先即最低松弛度优先即最低松弛度优先即LLF(LeastLLF(LeastLaxityF

109、irst)LaxityFirst)算法算法算法算法 第三章处理机调度与死锁 综合实验综合实验n处理机调度模拟处理机调度模拟处理机调度模拟处理机调度模拟( (先来先服务先来先服务先来先服务先来先服务 （FCFSFCFS）、）、）、）、 短短短短进程优先进程优先进程优先进程优先 （SPFSPF）、高优先权调度）、高优先权调度）、高优先权调度）、高优先权调度 （FPFFPF）、）、）、）、时间片轮转（时间片轮转（时间片轮转（时间片轮转（RRRR）n主存空间和磁盘空间的分配和回收主存空间和磁盘空间的分配和回收n模拟文件系统模拟文件系统n模拟实现资源分配。同时要求编写和调试一个模拟实现资源分配。同时要求

110、编写和调试一个模拟实现资源分配。同时要求编写和调试一个模拟实现资源分配。同时要求编写和调试一个系统动态分配资源的简单模拟程序，观察死锁系统动态分配资源的简单模拟程序，观察死锁系统动态分配资源的简单模拟程序，观察死锁系统动态分配资源的简单模拟程序，观察死锁产生的条件，并使用适当的算法，有效的防止产生的条件，并使用适当的算法，有效的防止产生的条件，并使用适当的算法，有效的防止产生的条件，并使用适当的算法，有效的防止和避免死锁的发生。具体用银行家算法实现资和避免死锁的发生。具体用银行家算法实现资和避免死锁的发生。具体用银行家算法实现资和避免死锁的发生。具体用银行家算法实现资源分配。源分配。源分配。源

111、分配。第三章处理机调度与死锁 Deadlock possible 3.5产生死锁的原因和必要条件产生死锁的原因和必要条件 死锁的概念死锁的概念死锁的概念死锁的概念第三章处理机调度与死锁 Deadlock第三章处理机调度与死锁 n死锁（死锁（死锁（死锁（DeadlockDeadlock）定义）定义）定义）定义 指指指指多多多多个个个个进进进进程程程程因因因因竞竞竞竞争争争争共共共共享享享享资资资资源源源源而而而而造造造造成成成成的的的的一一一一种种种种僵僵僵僵局局局局，若若若若无无无无外外外外力力力力作作作作用用用用，这这这这些些些些进进进进程程程程都都都都将将将将永永永永远远远远不不不不能能能

112、能再再再再向向向向前前前前推进。推进。推进。推进。 即即即即：一一一一组组组组进进进进程程程程中中中中，每每每每个个个个进进进进程程程程都都都都无无无无限限限限等等等等待待待待被被被被该该该该组组组组进进进进程程程程中中中中另另另另一一一一进进进进程程程程所所所所占占占占有有有有的的的的资资资资源源源源，因因因因而而而而永永永永远远远远无无无无法法法法得得得得到到到到的的的的资资资资源源源源，这这这这种种种种现现现现象象象象称称称称为为为为进进进进程程程程死死死死锁锁锁锁，这这这这一一一一组组组组进进进进程程程程就就就就称为称为称为称为死锁进程死锁进程死锁进程死锁进程。第三章处理机调度与死锁

113、死锁死锁参与死锁的进程最少是两个参与死锁的进程最少是两个参与死锁的进程最少是两个参与死锁的进程最少是两个参与死锁的进程至少有两个已经占有资源参与死锁的进程至少有两个已经占有资源参与死锁的进程至少有两个已经占有资源参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源参与死锁的所有进程都在等待资源参与死锁的所有进程都在等待资源参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的参与死锁的进程是当前系统中所有进程的参与死锁的进程是当前系统中所有进程的参与死锁的进程是当前系统中所有进程的子集子集子集子集 注注注注：死锁的严重性：死锁的严重性：死锁的严重性：死锁的严重性：

114、如果死锁发生，会浪费大如果死锁发生，会浪费大如果死锁发生，会浪费大如果死锁发生，会浪费大量系统资源，不仅涉及到死锁的那些进程量系统资源，不仅涉及到死锁的那些进程量系统资源，不仅涉及到死锁的那些进程量系统资源，不仅涉及到死锁的那些进程无法执行，而且还妨碍其他进程的执行，无法执行，而且还妨碍其他进程的执行，无法执行，而且还妨碍其他进程的执行，无法执行，而且还妨碍其他进程的执行，甚至导致系统崩溃。甚至导致系统崩溃。甚至导致系统崩溃。甚至导致系统崩溃。第三章处理机调度与死锁 n最易理解的死锁：线程最易理解的死锁：线程A、B死锁！死锁！n两兄弟相依为命，靠打猎为生，家里面有两把枪，金两兄弟相依为命，靠打

115、猎为生，家里面有两把枪，金枪和银枪。一般的时候他们每人拿一把枪就好了，但是枪和银枪。一般的时候他们每人拿一把枪就好了，但是有特殊问题发生了！某天，由于猎物太强悍，他们只有有特殊问题发生了！某天，由于猎物太强悍，他们只有一人手上两把枪才搞得定！现在老大拿到了金枪，老二一人手上两把枪才搞得定！现在老大拿到了金枪，老二拿到了银枪，老大还要拿到银枪才出发，老二一样，要拿到了银枪，老大还要拿到银枪才出发，老二一样，要拿到金枪才出发（至于这两兄问什么这样？我们假设就拿到金枪才出发（至于这两兄问什么这样？我们假设就是这样了。）这时候，很显然两兄弟都出发不了。老大是这样了。）这时候，很显然两兄弟都出发不了。老

116、大始终拿不到银枪，老二页始终拿不到金枪，因为他们都始终拿不到银枪，老二页始终拿不到金枪，因为他们都想得到两把枪，所以不想放出手上的那把枪！现在这个想得到两把枪，所以不想放出手上的那把枪！现在这个猎就打不成了，两兄弟死锁了。（这是获取资源的死锁。）猎就打不成了，两兄弟死锁了。（这是获取资源的死锁。）女朋友生气了，心想：男朋友要是给我打了电话，我就女朋友生气了，心想：男朋友要是给我打了电话，我就给他回一个。男朋友也是这样想的，女朋友给我打了我给他回一个。男朋友也是这样想的，女朋友给我打了我才给他打！女朋友越来越生气，她一直没等到电话，因才给他打！女朋友越来越生气，她一直没等到电话，因为男朋友一直没

117、打给她，为什么不打！因为男朋友没有为男朋友一直没打给她，为什么不打！因为男朋友没有接到女朋友的电话！为什么女朋友不打？他一直没有接接到女朋友的电话！为什么女朋友不打？他一直没有接到男朋友的电话啊，两人死锁了。到男朋友的电话啊，两人死锁了。（这是事件通知的死锁）。（这是事件通知的死锁）第三章处理机调度与死锁 3.5.1产生死锁的原因产生死锁的原因n 死锁的起因死锁的起因死锁的起因死锁的起因竞争非剥夺性资源竞争非剥夺性资源竞争非剥夺性资源竞争非剥夺性资源例：有两个进程例：有两个进程例：有两个进程例：有两个进程P P、QQ，系统仅有一台磁带机，系统仅有一台磁带机，系统仅有一台磁带机，系统仅有一台磁带

118、机和打印机。和打印机。和打印机。和打印机。Pr1Pr1：P P进程申请打印机进程申请打印机进程申请打印机进程申请打印机AQr1AQr1：QQ进程申请磁带机进程申请磁带机进程申请磁带机进程申请磁带机B BPr2Pr2：P P进程申请磁带机进程申请磁带机进程申请磁带机进程申请磁带机BQr2BQr2：QQ进程申请打印机进程申请打印机进程申请打印机进程申请打印机A APr3Pr3：P P进程释放打印机进程释放打印机进程释放打印机进程释放打印机AQr3AQr3：QQ进程释放磁带机进程释放磁带机进程释放磁带机进程释放磁带机B BPr4Pr4：P P进程释放磁带机进程释放磁带机进程释放磁带机进程释放磁带机B

119、Qr4BQr4：QQ进程释放打印机进程释放打印机进程释放打印机进程释放打印机A A第三章处理机调度与死锁 图图3-13I/O设备共享时的死锁情况设备共享时的死锁情况 资源资源资源资源进程有向图进程有向图进程有向图进程有向图r1r2P1P2形成环路引起死锁形成环路引起死锁形成环路引起死锁形成环路引起死锁分分分分配配配配请求请求请求请求第三章处理机调度与死锁 n n死锁的起因死锁的起因死锁的起因死锁的起因竞争临时性资源竞争临时性资源竞争临时性资源竞争临时性资源 临临临临时时时时性性性性资资资资源源源源，这这这这是是是是指指指指由由由由一一一一个个个个进进进进程程程程产产产产生生生生，被被被被另另另

120、另一一一一进进进进程程程程使使使使用用用用一一一一短短短短暂暂暂暂时时时时间间间间后后后后便便便便无无无无用用用用的的的的资资资资源源源源，故故故故也也也也称称称称之之之之为为为为消消消消耗耗耗耗性性性性资资资资源源源源，它它它它也也也也可可可可能能能能引引引引起起起起死死死死锁锁锁锁。图图图图3-143-143-143-14示示示示出出出出了了了了在在在在进进进进程程程程之之之之间间间间通通通通信信信信时时时时形形形形成成成成死死死死锁锁锁锁的的的的情情情情况况况况。图图图图中中中中S S S S1 1 1 1、S S S S2 2 2 2和和和和S S S S3 3 3 3是是是是临临临临

121、时时时时性性性性资资资资源源源源。进进进进程程程程P P P P1 1 1 1产产产产生生生生消消消消息息息息S S S S1 1 1 1，又又又又要要要要求求求求从从从从P P P P3 3 3 3接接接接收收收收消消消消息息息息S S S S3 3 3 3；进进进进程程程程P P P P3 3 3 3产产产产生生生生消消消消息息息息S S S S3 3 3 3，又又又又要要要要求求求求从从从从进进进进程程程程P P P P2 2 2 2接接接接收收收收其其其其所所所所产产产产生生生生的的的的消消消消息息息息S S S S2 2 2 2；进进进进程程程程P P P P2 2 2 2产产产产生

122、生生生消消消消息息息息S S S S2 2 2 2，又又又又需需需需要要要要接接接接收收收收进进进进程程程程P P P P1 1 1 1所产生的消息所产生的消息所产生的消息所产生的消息S S S S1 1 1 1。如果消息通信按下述顺序进行：如果消息通信按下述顺序进行：如果消息通信按下述顺序进行：如果消息通信按下述顺序进行：P P P P1 1 1 1： Release(SRelease(SRelease(SRelease(S1 1 1 1) ) ) )； Request(SRequest(SRequest(SRequest(S3 3 3 3) ) ) )； P P P P2 2 2 2： R

123、elease(SRelease(SRelease(SRelease(S2 2 2 2) ) ) )； Request(SRequest(SRequest(SRequest(S1 1 1 1) ) ) )； P P P P3 3 3 3： Release(SRelease(SRelease(SRelease(S3 3 3 3) ) ) )； Request(SRequest(SRequest(SRequest(S2 2 2 2) ) ) )； 第三章处理机调度与死锁 并不可能发生死锁，但若改成下述的运行顺序：并不可能发生死锁，但若改成下述的运行顺序：并不可能发生死锁，但若改成下述的运行顺序：并不

124、可能发生死锁，但若改成下述的运行顺序：P P P P1 1 1 1： Request(SRequest(SRequest(SRequest(S3 3 3 3) ) ) )； Release(SRelease(SRelease(SRelease(S1 1 1 1) ) ) )； P P P P2 2 2 2： Request(SRequest(SRequest(SRequest(S1 1 1 1) ) ) )； Release(SRelease(SRelease(SRelease(S2 2 2 2) ) ) )； P P P P3 3 3 3： Request(SRequest(SRequest

125、(SRequest(S2 2 2 2) ) ) )； Release(SRelease(SRelease(SRelease(S3 3 3 3) ) ) )； 则可能发生死锁。则可能发生死锁。则可能发生死锁。则可能发生死锁。 第三章处理机调度与死锁 图3-14进程之间通信时的死锁 形成环路引起死锁形成环路引起死锁形成环路引起死锁形成环路引起死锁第三章处理机调度与死锁 n n 死锁的起因死锁的起因死锁的起因死锁的起因进程推进顺序不当引起死锁进程推进顺序不当引起死锁进程推进顺序不当引起死锁进程推进顺序不当引起死锁1)进程推进顺序合法进程推进顺序合法在进程P1和P2并发执行时，如果按下述两种顺序推进：

126、 A1:P1request(r1)A2:P2request(r2)B1:P1request(r2)B2:P2request(r1)C1:P1release(r1)C2:P2release(r2)D1:P1release(r2)D2:P2release(r1)则两个进程可顺利完成，若A1、A2或者A2、A1则可能发生死锁马儿光吃草,不快跑第三章处理机调度与死锁 危险区危险区NA1B1C1D1P1进展进展P2进进展展D2C2B2A2A1:P1request(r1)A2:P2request(r2)B1:P1request(r2)B2:P2request(r1)C1:P1release(r1)C2:P

127、2release(r2)D1:P1release(r2)D2:P2release(r1)产生死锁的产生死锁的产生死锁的产生死锁的根本原因根本原因根本原因根本原因是系统是系统是系统是系统能够提供的资源个数比要求能够提供的资源个数比要求能够提供的资源个数比要求能够提供的资源个数比要求的该资源的进程数少的该资源的进程数少的该资源的进程数少的该资源的进程数少。死锁点死锁点死锁点死锁点第三章处理机调度与死锁 3.5.23.5.23.5.23.5.2产生死锁的必要条件产生死锁的必要条件产生死锁的必要条件产生死锁的必要条件(1) (1) (1) (1) 互互互互斥斥斥斥条条条条件件件件：指指指指进进进进程程

128、程程对对对对所所所所分分分分配配配配到到到到的的的的资资资资源源源源进进进进行行行行排排排排它它它它性性性性使使使使用用用用，即即即即在在在在一一一一段段段段时时时时间间间间内内内内某某某某资资资资源源源源只只只只由由由由一一一一个个个个进进进进程程程程占占占占用用用用。如如如如果果果果此此此此时时时时还还还还有有有有其其其其它它它它进进进进程程程程请请请请求求求求该该该该资资资资源源源源，则则则则请请请请求求求求者者者者只只只只能能能能等等等等待待待待，直直直直至至至至占占占占有有有有该该该该资资资资源源源源的的的的进进进进程程程程用毕释放。（资源独占）用毕释放。（资源独占）用毕释放。（资源

129、独占）用毕释放。（资源独占）(2) (2) (2) (2) 请求和保持条件请求和保持条件请求和保持条件请求和保持条件：指进程已经保持了至少一个资源，：指进程已经保持了至少一个资源，：指进程已经保持了至少一个资源，：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此但又提出了新的资源请求，而该资源又已被其它进程占有，此但又提出了新的资源请求，而该资源又已被其它进程占有，此但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。时请求进程阻塞，但又对自己已获得的其它资源保持不放。时请求进程阻塞，但又对自己已获得的其

130、它资源保持不放。时请求进程阻塞，但又对自己已获得的其它资源保持不放。（部分分配，（部分分配，（部分分配，（部分分配，占有申请占有申请占有申请占有申请 ） 第三章处理机调度与死锁 (3) (3) (3) (3) 不不不不剥剥剥剥夺夺夺夺条条条条件件件件：指指指指进进进进程程程程已已已已获获获获得得得得的的的的资资资资源源源源，在在在在未未未未使使使使用用用用完完完完之之之之前，不能被剥夺，只能在使用完时由前，不能被剥夺，只能在使用完时由前，不能被剥夺，只能在使用完时由前，不能被剥夺，只能在使用完时由自己释放自己释放自己释放自己释放。（不可强占）。（不可强占）。（不可强占）。（不可强占）(4) (

131、4) (4) (4) 环路等待条件环路等待条件环路等待条件环路等待条件：指在发生死锁时，必然存在一个进：指在发生死锁时，必然存在一个进：指在发生死锁时，必然存在一个进：指在发生死锁时，必然存在一个进程程程程资源的环形链，即进程集合资源的环形链，即进程集合资源的环形链，即进程集合资源的环形链，即进程集合PPPP0 0 0 0，P P P P1 1 1 1，P P P P2 2 2 2，P P P Pn n n n 中的中的中的中的P P P P0 0 0 0正在等待一个正在等待一个正在等待一个正在等待一个P P P P1 1 1 1占用的资源；占用的资源；占用的资源；占用的资源； P P P P

132、1 1 1 1正在等待正在等待正在等待正在等待P P P P2 2 2 2占用的资源，占用的资源，占用的资源，占用的资源，P P P Pn n n n正在等待已被正在等待已被正在等待已被正在等待已被P P P P0 0 0 0占用的资源。占用的资源。占用的资源。占用的资源。 这这这这4 4个条件是必要条件而不是充分条件个条件是必要条件而不是充分条件个条件是必要条件而不是充分条件个条件是必要条件而不是充分条件 。只要死锁发生，则只要死锁发生，则只要死锁发生，则只要死锁发生，则四个条件都存在，有一个条件不存在，四个条件都存在，有一个条件不存在，四个条件都存在，有一个条件不存在，四个条件都存在，有一

133、个条件不存在，则一定无死锁发生，但四个条件都存在，不一定发生死锁。则一定无死锁发生，但四个条件都存在，不一定发生死锁。则一定无死锁发生，但四个条件都存在，不一定发生死锁。则一定无死锁发生，但四个条件都存在，不一定发生死锁。第三章处理机调度与死锁 3.5.3处理死锁的基本方法处理死锁的基本方法不考虑此问题：不考虑此问题：（鸵鸟政策）（鸵鸟政策）让死锁发生：让死锁发生：允许死锁发生，但能检测出死锁允许死锁发生，但能检测出死锁并实现修复。并实现修复。不让死锁发生：不让死锁发生：为了不发生死锁，必须设法破为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一坏产生死锁的四个必要条件之一第三章处理机调度

134、与死锁 3.5.33.5.33.5.33.5.3处理死锁的基本方法处理死锁的基本方法处理死锁的基本方法处理死锁的基本方法(1) 预防死锁预防死锁。这是一种较简单和直观的事先预防的方法。该方法是通过设置某些限制条件限制条件限制条件限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。预防死锁是一种较易实现的方法，已被广泛使用。但由于所施加的限制条件往往太严太严太严太严格格格格，因而可能会导致系统资源利用率和系统吞吐量降低。 第三章处理机调度与死锁 (2) (2) (2) (2) 避免死锁避免死锁避免死锁避免死锁。该方法同样是属于事先预防的。该方法同样是属于事先预防的。该方法同

135、样是属于事先预防的。该方法同样是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产策略，但它并不须事先采取各种限制措施去破坏产策略，但它并不须事先采取各种限制措施去破坏产策略，但它并不须事先采取各种限制措施去破坏产生死锁的四个必要条件，而是在资源的生死锁的四个必要条件，而是在资源的生死锁的四个必要条件，而是在资源的生死锁的四个必要条件，而是在资源的动态分配动态分配动态分配动态分配过过过过程中，用某种方法去防止系统进入不安全状态，从程中，用某种方法去防止系统进入不安全状态，从程中，用某种方法去防止系统进入不安全状态，从程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。这种方法只

136、需事先而避免发生死锁。这种方法只需事先而避免发生死锁。这种方法只需事先而避免发生死锁。这种方法只需事先施加较弱的限施加较弱的限施加较弱的限施加较弱的限制条件制条件制条件制条件，便可获得较高的资源利用率及系统吞吐量，便可获得较高的资源利用率及系统吞吐量，便可获得较高的资源利用率及系统吞吐量，便可获得较高的资源利用率及系统吞吐量，但在实现上有一定的难度。目前在较完善的系统中但在实现上有一定的难度。目前在较完善的系统中但在实现上有一定的难度。目前在较完善的系统中但在实现上有一定的难度。目前在较完善的系统中常用此方法来避免发生死锁。常用此方法来避免发生死锁。常用此方法来避免发生死锁。常用此方法来避免发

137、生死锁。 第三章处理机调度与死锁 (3) (3) (3) (3) 检测死锁检测死锁检测死锁检测死锁。这种方法并不须事先采取任何限制性措施，。这种方法并不须事先采取任何限制性措施，。这种方法并不须事先采取任何限制性措施，。这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，而是允许系统在运行也不必检查系统是否已经进入不安全区，而是允许系统在运行也不必检查系统是否已经进入不安全区，而是允许系统在运行也不必检查系统是否已经进入不安全区，而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检过程中发生死锁。但可通过系统所设置的检测机构，及时地检过程中发生死锁。但

138、可通过系统所设置的检测机构，及时地检过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；测出死锁的发生，并精确地确定与死锁有关的进程和资源；测出死锁的发生，并精确地确定与死锁有关的进程和资源；测出死锁的发生，并精确地确定与死锁有关的进程和资源； 然后，采取适当措施，从系统中将已发生的死锁清除掉。然后，采取适当措施，从系统中将已发生的死锁清除掉。然后，采取适当措施，从系统中将已发生的死锁清除掉。然后，采取适当措施，从系统中将已发生的死锁清除掉。 (4) (4) (4) (4) 解除死锁解除死锁解除死锁解除死锁。这是与检测死锁相配套的一种措施。

139、当。这是与检测死锁相配套的一种措施。当。这是与检测死锁相配套的一种措施。当。这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出检测到系统中已发生死锁时，须将进程从死锁状态中解脱出检测到系统中已发生死锁时，须将进程从死锁状态中解脱出检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤消或挂起一些进程，以便回收一些来。常用的实施方法是撤消或挂起一些进程，以便回收一些来。常用的实施方法是撤消或挂起一些进程，以便回收一些来。常用的实施方法是撤消或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转资源，再将这些资源分配

140、给已处于阻塞状态的进程，使之转资源，再将这些资源分配给已处于阻塞状态的进程，使之转资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁的检测和解除措施有可能使为就绪状态，以继续运行。死锁的检测和解除措施有可能使为就绪状态，以继续运行。死锁的检测和解除措施有可能使为就绪状态，以继续运行。死锁的检测和解除措施有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最系统获得较好的资源利用率和吞吐量，但在实现上难度也最系统获得较好的资源利用率和吞吐量，但在实现上难度也最系统获得较好的资源利用率和吞吐量，但在实现上难度也最大大大大。 第三章处理机调度与死锁 3.6预防、避

141、免死锁的方法预防、避免死锁的方法3.6.13.6.13.6.13.6.1预防死锁预防死锁预防死锁预防死锁1 1破坏破坏“互斥互斥”条件，很难，条件，很难，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备。2 2摒弃摒弃“请求和保持请求和保持”条件条件规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。可以避免发生死锁避免发生死锁避免发生死锁避免发生死锁。 第三章处理机调度与死锁 资源静态分配法资源静态分配法资源静态分配法资源静态分配法优点优点：简单：简单、易于实现且很安全易于实现且很安全。缺点缺点(1)(1)资源被严重浪费资源被严重浪费，因为

142、一个进程是一次性地获得其整个运行过程所需的全部资源的，且独占资源，其中可能有些资源很少使用，甚至在整个运行期间都未使用，这就严重地恶化了系统资源的利用率； (2)(2)(2)(2)使进程延迟运行使进程延迟运行使进程延迟运行使进程延迟运行，仅当进程在获得了其所需的全部资源后，才能开始运行，但可能因有些资源已长期被其它进程占用而致使等待该资源的进程迟迟不能运行。 第三章处理机调度与死锁 3 3摒弃摒弃“不剥夺不剥夺”条件条件在采用这种方法时系统规定，进程是逐个地提出对资源进程是逐个地提出对资源进程是逐个地提出对资源进程是逐个地提出对资源的要求的的要求的的要求的的要求的。当一个已经保持了某些资源的进

143、程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。这意味着某一进程已经占有的资源，在运行过程中会被暂时地释放掉，也可认为是被剥夺了，从而摒弃了“不剥夺”条件。 这种预防死锁的方法实现起来比较复杂且要付出很大的比较复杂且要付出很大的比较复杂且要付出很大的比较复杂且要付出很大的代价。代价。代价。代价。第三章处理机调度与死锁 4 4摒弃摒弃“环路等待环路等待”条件条件系统将所有资源按类型进行线性排队，并赋予不同的序系统将所有资源按类型进行线性排队，并赋予不同的序系统将所有资源按类型进行线性排队，并赋予不同的序系统将所有资源按类型进行线性排队，并赋予不

144、同的序号号号号。 资源顺序分配法资源顺序分配法资源顺序分配法资源顺序分配法 例如，令输入机的序号为1，打印机的序号为2，磁带机为3，磁盘为4。所有进程对资源的请求必须严格按照资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了“环路等待”条件。事实上，在采用这种策略时，总有一个进程占据了较高序号的资源，此后它继续申请的资源必然是空闲的，因而进程可以一直向前推进。 第三章处理机调度与死锁 这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量都有较明显的改善改善改善改善。但也存在下述严重问题：系系系系统统统统中中中中各各各各类类类类资资资资源源源源所所所所分分

145、分分配配配配( ( ( (确确确确定定定定) ) ) )的的的的序序序序号号号号必必必必须须须须相相相相对对对对稳稳稳稳定定定定，这这这这就限制了新类型设备的增加。就限制了新类型设备的增加。就限制了新类型设备的增加。就限制了新类型设备的增加。造成对资源的浪费造成对资源的浪费造成对资源的浪费造成对资源的浪费。为方便用户，系统对用户在编程时所施加的限制条件应尽量少。然而这种按规定次序申请的方法，必然会限制用必然会限制用必然会限制用必然会限制用户简单、自主地编程。户简单、自主地编程。户简单、自主地编程。户简单、自主地编程。 第三章处理机调度与死锁 3.6.23.6.2系统安全状态系统安全状态（避免死

146、锁）避免死锁）避免死锁）避免死锁）1 1安全状态安全状态在避免死锁避免死锁避免死锁避免死锁的方法中，允许进程动态动态动态动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。 第三章处理机调度与死锁 所所所所谓谓谓谓安安安安全全全全状状状状态态态态，是是是是指指指指系系系系统统统统能能能能按按按按某某某某种种种种进进进进程程程程顺顺顺顺序序序序(P(P(P(P1 1 1 1，P P P P2 2 2 2，P P P Pn n n n)()()()(称称称称P P P P1 1 1 1，P P P P2

147、 2 2 2，P P P Pn n n n序序序序列列列列为为为为安安安安全全全全序序序序列列列列) ) ) )，来来来来为为为为每每每每个个个个进进进进程程程程P P P Pi i i i分分分分配配配配其其其其所所所所需需需需资资资资源源源源，直直直直至至至至满满满满足足足足每每每每个个个个进进进进程程程程对对对对资资资资源源源源的的的的最最最最大大大大需需需需求求求求，使使使使每每每每个个个个进进进进程程程程都都都都可可可可顺顺顺顺利利利利地地地地完完完完成成成成。如如如如果果果果系系系系统统统统无无无无法法法法找找找找到到到到这这这这样样样样一一一一个个个个安安安安全序列，则称系统处于

148、不安全状态。全序列，则称系统处于不安全状态。全序列，则称系统处于不安全状态。全序列，则称系统处于不安全状态。安全序列安全序列安全序列安全序列：进程安全执行完的顺序：进程安全执行完的顺序：进程安全执行完的顺序：进程安全执行完的顺序 避免死锁的实质在于：系统在进行资源分配时，如何使避免死锁的实质在于：系统在进行资源分配时，如何使避免死锁的实质在于：系统在进行资源分配时，如何使避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。系统不进入不安全状态。系统不进入不安全状态。系统不进入不安全状态。 第三章处理机调度与死锁 2 2 2 2安全状态之例安全状态之例安全状态之例安全状态之例我

149、们通过一个例子来说明安全性。假定系统中有三个进我们通过一个例子来说明安全性。假定系统中有三个进我们通过一个例子来说明安全性。假定系统中有三个进我们通过一个例子来说明安全性。假定系统中有三个进程程程程P P P P1 1 1 1、P P P P2 2 2 2和和和和P P P P3 3 3 3，共有共有共有共有12121212台磁带机。进程台磁带机。进程台磁带机。进程台磁带机。进程P P P P1 1 1 1总共要求总共要求总共要求总共要求10101010台磁带机，台磁带机，台磁带机，台磁带机，P P P P2 2 2 2和和和和P P P P3 3 3 3分别要求分别要求分别要求分别要求4 4

150、 4 4台和台和台和台和9 9 9 9台。假设在台。假设在台。假设在台。假设在T T T T0 0 0 0时刻，进程时刻，进程时刻，进程时刻，进程P P P P1 1 1 1、P P P P2 2 2 2和和和和P P P P3 3 3 3已已已已分别获得分别获得分别获得分别获得5 5 5 5台、台、台、台、2 2 2 2台和台和台和台和2 2 2 2台磁带机，尚有台磁带机，尚有台磁带机，尚有台磁带机，尚有3 3 3 3台空闲未分配，如下台空闲未分配，如下台空闲未分配，如下台空闲未分配，如下表所示：表所示：表所示：表所示： 此时已分配此时已分配此时已分配此时已分配9 9 9 9台，安全序列：台

151、，安全序列：台，安全序列：台，安全序列：P2P2P2P2，P1P1P1P1，P3P3P3P3第三章处理机调度与死锁 3 3 3 3由安全状态向不安全状态的转换由安全状态向不安全状态的转换由安全状态向不安全状态的转换由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态如果不按照安全序列分配资源，则系统可能会由安全状态如果不按照安全序列分配资源，则系统可能会由安全状态如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在进入不安全状态。例如，在进入不安全状态。例如，在进入不安全状态。例如，在T T T T0 0 0 0时刻以后，时刻以后，时刻以后，时刻

152、以后，P P P P3 3 3 3又请求又请求又请求又请求1 1 1 1台磁带机，台磁带机，台磁带机，台磁带机，若此时系统把剩余若此时系统把剩余若此时系统把剩余若此时系统把剩余3 3 3 3台中的台中的台中的台中的1 1 1 1台分配给台分配给台分配给台分配给P P P P3 3 3 3，则系统便进入不安全则系统便进入不安全则系统便进入不安全则系统便进入不安全状态。因为此时也无法再找到一个安全序列，从给状态。因为此时也无法再找到一个安全序列，从给状态。因为此时也无法再找到一个安全序列，从给状态。因为此时也无法再找到一个安全序列，从给P P P P3 3 3 3分配了第分配了第分配了第分配了第3

153、 3 3 3台磁带机开始，系统便又进入了不安全状态。由此可见，在台磁带机开始，系统便又进入了不安全状态。由此可见，在台磁带机开始，系统便又进入了不安全状态。由此可见，在台磁带机开始，系统便又进入了不安全状态。由此可见，在P P P P3 3 3 3请求资源时，尽管系统中尚有可用的磁带机，但却不能分配请求资源时，尽管系统中尚有可用的磁带机，但却不能分配请求资源时，尽管系统中尚有可用的磁带机，但却不能分配请求资源时，尽管系统中尚有可用的磁带机，但却不能分配给它，必须让给它，必须让给它，必须让给它，必须让P P P P3 3 3 3一直等待到一直等待到一直等待到一直等待到P P P P1 1 1 1

154、和和和和P P P P2 2 2 2完成，释放出资源后再将足完成，释放出资源后再将足完成，释放出资源后再将足完成，释放出资源后再将足够的资源分配给够的资源分配给够的资源分配给够的资源分配给P P P P3 3 3 3，它才能顺利完成。它才能顺利完成。它才能顺利完成。它才能顺利完成。 存在安全状态，不代表不可能发生死锁，存在安全状态，不代表不可能发生死锁，表示的是有解决死锁的方法存在。表示的是有解决死锁的方法存在。第三章处理机调度与死锁 3.6.3利用银行家算法避免死锁利用银行家算法避免死锁n银行家算法：银行家算法：DijkstraDijkstra E.W E.W 于于19681968年提出。年

155、提出。银行家算法银行家算法银行家拥有一笔周转资金银行家拥有一笔周转资金客客户户要要求求分分期期贷贷款款，如如果果客客户户能能够够得得到到各各期期贷贷款款，就就一一定定能能够够归归还还贷贷款款，否否则则就就一一定定不不能能归归还贷款还贷款银行家应谨慎的贷款，防止出现坏帐银行家应谨慎的贷款，防止出现坏帐n用银行家算法避免死锁用银行家算法避免死锁操作系统（银行家）操作系统（银行家）操作系统管理的资源操作系统管理的资源( (周转资金周转资金) )进程（要求贷款的客户）进程（要求贷款的客户）第三章处理机调度与死锁 n银行家银行家算法思想：算法思想：该算法需要检查申请者对资源的最大需求量，该算法需要检查申

156、请者对资源的最大需求量，如果系统如果系统现存的各类资源现存的各类资源可以满足申请者的请可以满足申请者的请求，就满足申请者的请求。求，就满足申请者的请求。这样申请者就可很这样申请者就可很快完成其计算，然后释放它占用的资源，从而快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，所以可避保证了系统中的所有进程都能完成，所以可避免死锁的发生。免死锁的发生。第三章处理机调度与死锁 n n银行家算法中的数据结构银行家算法中的数据结构银行家算法中的数据结构银行家算法中的数据结构(1) (1) (1) (1) 可可可可利利利利用用用用资资资资源源源源向向向向量量量量AvailableAv

157、ailableAvailableAvailable。这这这这是是是是一一一一个个个个含含含含有有有有m m m m个个个个元元元元素素素素的的的的数数数数组组组组，其其其其中中中中的的的的每每每每一一一一个个个个元元元元素素素素代代代代表表表表一一一一类类类类可可可可利利利利用用用用的的的的资资资资源源源源数数数数目目目目，其其其其初初初初始始始始值值值值是是是是系系系系统统统统中中中中所所所所配配配配置置置置的的的的该该该该类类类类全全全全部部部部可可可可用用用用资资资资源源源源的的的的数数数数目目目目，其其其其数数数数值值值值随随随随 该该该该 类类类类 资资资资 源源源源 的的的的 分分

158、分分 配配配配 和和和和 回回回回 收收收收 而而而而 动动动动 态态态态 地地地地 改改改改 变变变变 。 如如如如 果果果果Availablej=KAvailablej=KAvailablej=KAvailablej=K，则表示系统中现有则表示系统中现有则表示系统中现有则表示系统中现有R R R Rj j j j类资源类资源类资源类资源K K K K个。个。个。个。(2) (2) (2) (2) 最最最最大大大大需需需需求求求求矩矩矩矩阵阵阵阵MaxMaxMaxMax。这这这这是是是是一一一一个个个个n n n n m m m m的的的的矩矩矩矩阵阵阵阵，它它它它定定定定义义义义了了了了系

159、系系系统统统统中中中中n n n n个个个个进进进进程程程程中中中中的的的的每每每每一一一一个个个个进进进进程程程程对对对对m m m m类类类类资资资资源源源源的的的的最最最最大大大大需需需需求求求求。如如如如果果果果Maxi,j=KMaxi,j=KMaxi,j=KMaxi,j=K，则表示进程则表示进程则表示进程则表示进程i i i i需要需要需要需要R R R Rj j j j类资源的最大数目类资源的最大数目类资源的最大数目类资源的最大数目为为为为K K K K。 第三章处理机调度与死锁 (3) (3) (3) (3) 分分分分配配配配矩矩矩矩阵阵阵阵AllocationAllocatio

160、nAllocationAllocation。这这这这也也也也是是是是一一一一个个个个n n n nm m m m的的的的矩矩矩矩阵阵阵阵，它它它它定定定定义义义义了了了了系系系系统统统统中中中中每每每每一一一一类类类类资资资资源源源源当当当当前前前前已已已已分分分分配配配配给给给给每每每每一一一一进进进进程程程程的的的的资资资资源源源源数数数数。如如如如果果果果Allocationi,j=KAllocationi,j=KAllocationi,j=KAllocationi,j=K，则则则则表表表表示示示示进进进进程程程程i i i i当当当当前前前前已已已已分分分分得得得得R R R R j

161、j j j类类类类资资资资源源源源的数目为的数目为的数目为的数目为K K K K。(4) (4) (4) (4) 需需需需求求求求矩矩矩矩阵阵阵阵NeedNeedNeedNeed。这这这这也也也也是是是是一一一一个个个个n n n nm m m m的的的的矩矩矩矩阵阵阵阵，用用用用以以以以表表表表示示示示每每每每一一一一个个个个进进进进程程程程尚尚尚尚需需需需的的的的各各各各类类类类资资资资源源源源数数数数。如如如如果果果果Needi,j=KNeedi,j=KNeedi,j=KNeedi,j=K，则则则则表表表表示示示示进进进进程程程程i i i i还需要还需要还需要还需要R R R R j

162、j j j类资源类资源类资源类资源K K K K个，方能完成其任务。个，方能完成其任务。个，方能完成其任务。个，方能完成其任务。上述三个矩阵间存在下述关系：上述三个矩阵间存在下述关系：上述三个矩阵间存在下述关系：上述三个矩阵间存在下述关系：Needi, j=Maxi, j-Allocationi, jNeedi, j=Maxi, j-Allocationi, jNeedi, j=Maxi, j-Allocationi, jNeedi, j=Maxi, j-Allocationi, j 第三章处理机调度与死锁 银行家算法避免死锁银行家算法避免死锁算法：开始申请量=尚需 量ynny申请量=系统剩余

163、安全性控制 分配进入下一步骤预分配作废阻塞安全首先为申请预分配资源错误预测ny第三章处理机调度与死锁 例.多项资源的安全序列（a）初始状态）初始状态Max Matrix第三章处理机调度与死锁 Max Matrix（a）P2运行完成运行完成第三章处理机调度与死锁 Max MatrixMax Matrix第三章处理机调度与死锁 例.进入不安全状态（a）初始状态）初始状态Max Matrix第三章处理机调度与死锁 例.进入不安全状态Max Matrix（b）P1申请申请1个个R1、1个个R3第三章处理机调度与死锁 2 2 2 2银行家算法银行家算法银行家算法银行家算法设设设设RequestReque

164、stRequestRequest i i i i是进程是进程是进程是进程P P P Pi i i i的请求向量，如果的请求向量，如果的请求向量，如果的请求向量，如果RequestRequestRequestRequest i i i ij=Kj=Kj=Kj=K，表示进程表示进程表示进程表示进程P P P P i i i i需要需要需要需要K K K K个个个个R R R R j j j j类型的资源。当类型的资源。当类型的资源。当类型的资源。当P P P P i i i i发出资源请求后，发出资源请求后，发出资源请求后，发出资源请求后，系统按下述步骤进行检查：系统按下述步骤进行检查：系统按下述

165、步骤进行检查：系统按下述步骤进行检查：(1) (1) (1) (1) 如果如果如果如果RequestRequestRequestRequest i i i ijNeedi,jjNeedi,jjNeedi,jjNeedi,j，便转向步骤便转向步骤便转向步骤便转向步骤(2)(2)(2)(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最否则认为出错，因为它所需要的资源数已超过它所宣布的最否则认为出错，因为它所需要的资源数已超过它所宣布的最否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。大值。大值。大值。(2) (2) (2) (2) 如果如果如果如果RequestRequestR

166、equestRequesti i i ijAvailablejjAvailablejjAvailablejjAvailablej ，便转向步骤便转向步骤便转向步骤便转向步骤(3)(3)(3)(3)；否则，表示尚无足够资源，；否则，表示尚无足够资源，；否则，表示尚无足够资源，；否则，表示尚无足够资源，P P P Pi i i i须等待。须等待。须等待。须等待。 第三章处理机调度与死锁 (3) (3) (3) (3) 系系系系统统统统试试试试探探探探着着着着把把把把资资资资源源源源分分分分配配配配给给给给进进进进程程程程P P P P i i i i，并并并并修修修修改改改改下下下下面面面面数数数

167、数据据据据结构中的数值：结构中的数值：结构中的数值：结构中的数值：Availablej:= Availablej:= Availablej:= Availablej:= Availablej-RequestAvailablej-RequestAvailablej-RequestAvailablej-Request i i i ijjjj；Allocationi,j:= Allocationi,j:= Allocationi,j:= Allocationi,j:= Allocationi,j+RequestAllocationi,j+RequestAllocationi,j+RequestAll

168、ocationi,j+Request i i i ijjjj；Needi,j:= Needi,j-RequestNeedi,j:= Needi,j-RequestNeedi,j:= Needi,j-RequestNeedi,j:= Needi,j-Request i i i ijjjj；(4) (4) (4) (4) 系统执行安全性算法系统执行安全性算法系统执行安全性算法系统执行安全性算法，检查此次资源分配后系统是，检查此次资源分配后系统是，检查此次资源分配后系统是，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程否处于安全状态。若安全，才正式将资源分配给进程否处于安全状

169、态。若安全，才正式将资源分配给进程否处于安全状态。若安全，才正式将资源分配给进程P P P Pi i i i，以以以以完成本次分配；否则，将本次的试探分配作废，恢复原来的完成本次分配；否则，将本次的试探分配作废，恢复原来的完成本次分配；否则，将本次的试探分配作废，恢复原来的完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程资源分配状态，让进程资源分配状态，让进程资源分配状态，让进程P P P Pi i i i等待。等待。等待。等待。 第三章处理机调度与死锁 3 3 3 3安全性算法安全性算法安全性算法安全性算法系统所执行的安全性算法可描述如下：系统所执行的安全性算法可描述

170、如下：系统所执行的安全性算法可描述如下：系统所执行的安全性算法可描述如下：(1) (1) (1) (1) 设置两个向量：设置两个向量：设置两个向量：设置两个向量： 工工工工作作作作向向向向量量量量WorkWorkWorkWork，它它它它表表表表示示示示系系系系统统统统可可可可提提提提供供供供给给给给进进进进程程程程继继继继续续续续运运运运行行行行所所所所需需需需的的的的各各各各类类类类资资资资源源源源数数数数目目目目，它它它它含含含含有有有有m m m m个个个个元元元元素素素素，在在在在执执执执行行行行安安安安全全全全算算算算法法法法开开开开始时，始时，始时，始时，Work:=Availa

171、bleWork:=AvailableWork:=AvailableWork:=Available。 FinishFinishFinishFinish，它表示系统是否有足够的资源分配给进程，它表示系统是否有足够的资源分配给进程，它表示系统是否有足够的资源分配给进程，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做使之运行完成。开始时先做使之运行完成。开始时先做使之运行完成。开始时先做Finishi:=falseFinishi:=falseFinishi:=falseFinishi:=false；当有足够资当有足够资当有足够资当有足够资源分配给进程时，再令源分配给进程时，再令源分配给

172、进程时，再令源分配给进程时，再令Finishi:=trueFinishi:=trueFinishi:=trueFinishi:=true。 第三章处理机调度与死锁 (2) (2) (2) (2) 从进程集合中找到一个能满足下述条件的进程：从进程集合中找到一个能满足下述条件的进程：从进程集合中找到一个能满足下述条件的进程：从进程集合中找到一个能满足下述条件的进程： Finishi=falseFinishi=falseFinishi=falseFinishi=false； Needi,jWorkjNeedi,jWorkjNeedi,jWorkjNeedi,jWorkj；若若若若找找找找到到到到，执

173、执执执行行行行步步步步骤骤骤骤(3)(3)(3)(3)，否否否否则则则则，执行步骤执行步骤执行步骤执行步骤(4)(4)(4)(4)。(3) (3) (3) (3) 当当当当进进进进程程程程PiPiPiPi获获获获得得得得资资资资源源源源后后后后，可可可可顺顺顺顺利利利利执执执执行行行行，直直直直至至至至完完完完成成成成，并并并并释放出分配给它的资源，故应执行：释放出分配给它的资源，故应执行：释放出分配给它的资源，故应执行：释放出分配给它的资源，故应执行：Workj:= Workj+Allocationi,jWorkj:= Workj+Allocationi,jWorkj:= Workj+All

174、ocationi,jWorkj:= Workj+Allocationi,j；Finishi:=trueFinishi:=trueFinishi:=trueFinishi:=true；go to step 2go to step 2go to step 2go to step 2； (4)(4)如果所有进程的如果所有进程的如果所有进程的如果所有进程的Finishi=trueFinishi=true都满足，则表示系统都满足，则表示系统都满足，则表示系统都满足，则表示系统处于安全状态；否则，系统处于不安全状态。处于安全状态；否则，系统处于不安全状态。处于安全状态；否则，系统处于不安全状态。处于安全状

175、态；否则，系统处于不安全状态。 第三章处理机调度与死锁 4 4 4 4银行家算法之例银行家算法之例银行家算法之例银行家算法之例假定系统中有五个进程假定系统中有五个进程假定系统中有五个进程假定系统中有五个进程PPPP0 0 0 0，P P P P1 1 1 1，P P P P2 2 2 2，P P P P3 3 3 3，P P P P4 4 4 4 和三类资源和三类资源和三类资源和三类资源AAAA，B B B B，CCCC，各种资源的数量分别为各种资源的数量分别为各种资源的数量分别为各种资源的数量分别为10101010、5 5 5 5、7 7 7 7，在，在，在，在T T T T0 0 0 0时

176、刻的资时刻的资时刻的资时刻的资源分配情况如图源分配情况如图源分配情况如图源分配情况如图3-163-163-163-16所示。所示。所示。所示。 第三章处理机调度与死锁 图3-16 T0时刻的资源分配表 第三章处理机调度与死锁 (1) T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析(见图 3-17所示)可知，在T0时刻存在着一个安全序列P1，P3，P4，P2，P0，故系统是安全的。 图3-17T0时刻的安全序列 P1P1，P3P3，P4P4，P2P2，P0P0是安全序列吗？是安全序列吗？第三章处理机调度与死锁 (2) P1请求资源：P1发出请求向量Request1(1，0，2)

177、，系统按银行家算法进行检查： Request1(1，0，2)Need1(1，2，2) Request1(1，0，2)Available1(3，3，2) 系统先假定可为P1分配资源，并修改Available，Allocation1和Need1向量，由此形成的资源变化情况如图3-16中的圆括号所示。 第三章处理机调度与死锁 再利用安全性算法检查此时系统是否安全。如图3-18所示。 图3-18P1申请资源时的安全性检查 第三章处理机调度与死锁 (3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： Request4(3，3，0)Need4(4，3，1)； R

178、equest4(3，3，0)Available(2，3，0)，让P4等待。(4) P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查： Request0(0，2，0)Need0(7，4，3)； Request0(0，2，0)Available(2，3，0)； 系统暂时先假定可为P0分配资源，并修改有关数据，如图3-19所示。 第三章处理机调度与死锁 图3-19为P0分配资源后的有关资源数据 第三章处理机调度与死锁 (5) (5) 进进行行安安全全性性检检查查：可可用用资资源源Available(2Available(2，1 1，0)0)已已不不能能满满足足任任

179、何何进进程程的的需需要要，故故系系统统进进入入不不安安全全状状态态，此此时时系系统不分配资源。统不分配资源。如果在银行家算法中，把如果在银行家算法中，把P0发出的请求向量改为发出的请求向量改为Request0(0，1，0)，系统是否能将资源分配给它？系统是否能将资源分配给它？第三章处理机调度与死锁 已分配的资源最大需求量 ABCABCP1010753P2200322P3302902P4211222P5002433剩余资源ABC 33 2在此基础上P2 申请（1，0，2）能否分配？为什么？P5 申请（3，3，0）能否分配？为什么？P1 申请（0，2，0）能否分配？为什么？第三章处理机调度与死锁

180、银行家算法优缺点银行家算法优缺点n 优点：优点：资源利用率比静态资源分配法高，又避免死锁。资源利用率比静态资源分配法高，又避免死锁。n 缺点：缺点：对资源分配过于保守；对资源分配过于保守；对资源分配过于保守；对资源分配过于保守；即考虑最坏情况每个进即考虑最坏情况每个进程可能请求最大需求量（类似银行提款）并在程可能请求最大需求量（类似银行提款）并在运行期中随时提出来运行期中随时提出来计算太多，并且需知道对资源的最大需求量，计算太多，并且需知道对资源的最大需求量，计算太多，并且需知道对资源的最大需求量，计算太多，并且需知道对资源的最大需求量，不太实际。不太实际。不太实际。不太实际。 要求系统资源与

181、用户数不变。要求系统资源与用户数不变。要求系统资源与用户数不变。要求系统资源与用户数不变。第三章处理机调度与死锁 3.7死锁的检测与解除死锁的检测与解除3.7.13.7.1死锁的检测死锁的检测当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此，系统必须做到：(1) 保存有关资源的请求和分配信息；(2) 提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。 第三章处理机调度与死锁 1资源分配图资源分配图(Resource Allocation Graph)系统死锁可利用资源分配图来描述。该图是由一组结点N和一组边E所组成的一个对偶G=(N1E)，它具有

182、下述形式的定义和限制：(1) 把N分为两个互斥的子集，即一组进程结点P=p1，p2，pn和一组资源结点R=r1，r2，rn，N=PR。在图3-20所示的例子中，P=p1，p2，R=r1，r2，N=r1，r2p1，p2。 第三章处理机调度与死锁 (2) 凡属于E中的一个边eE，都连接着P中的一个结点和R中的一个结点，e=pi，rj是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e=rj，pi是资源分配边，由资源rj指向进程pi，它表示把一个单位的资源rj分配给进程pi。图3-13中示出了两个请求边和两个分配边，即E=(p1，r2)，(r2，p2)，(p2，r1)，(r

183、1，p1)。我们用圆圈代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，我们用方框中的一个点代表一类资源中的一个资源。此时，请求边是由进程指向方框中的rj，而分配边则应始于方框中的一个点。图3-20示出了一个资源分配图。图中，p1进程已经分得了两个r1资源，并又请求一个r2资源；p2进程分得了一个r1和一个r2资源，并又请求r1资源。 第三章处理机调度与死锁 图3-20每类资源有多个时的情况 第三章处理机调度与死锁 2 2 2 2死锁定理死锁定理死锁定理死锁定理我我我我们们们们可可可可以以以以利利利利用用用用把把把把资资资资源源源源分分分分配配配配图图图图加加加加以以以以简简简简

184、化化化化的的的的方方方方法法法法( ( ( (图图图图3-21)3-21)3-21)3-21)，来检测当系统处于来检测当系统处于来检测当系统处于来检测当系统处于S S S S状态时是否为状态时是否为状态时是否为状态时是否为死锁状态死锁状态死锁状态死锁状态。简化方法如下：。简化方法如下：。简化方法如下：。简化方法如下：(1) (1) (1) (1) 在资源分配图中，找出一个既不阻塞又非独立的进在资源分配图中，找出一个既不阻塞又非独立的进在资源分配图中，找出一个既不阻塞又非独立的进在资源分配图中，找出一个既不阻塞又非独立的进程结点程结点程结点程结点PiPiPiPi。在顺利的情况下，在顺利的情况下，

185、在顺利的情况下，在顺利的情况下，P P P Pi i i i可获得所需资源而继续运行，可获得所需资源而继续运行，可获得所需资源而继续运行，可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去直至运行完毕，再释放其所占有的全部资源，这相当于消去直至运行完毕，再释放其所占有的全部资源，这相当于消去直至运行完毕，再释放其所占有的全部资源，这相当于消去pipipipi所求的请求边和分配边，使之成为孤立的结点。在图所求的请求边和分配边，使之成为孤立的结点。在图所求的请求边和分配边，使之成为孤立的结点。在图所求的请求边和分配边，使之成为孤立的结点。在图3-3-3-3-21(a)2

186、1(a)21(a)21(a)中，将中，将中，将中，将p1p1p1p1的两个分配边和一个请求边消去，便形成图的两个分配边和一个请求边消去，便形成图的两个分配边和一个请求边消去，便形成图的两个分配边和一个请求边消去，便形成图(b)(b)(b)(b)所示的情况。所示的情况。所示的情况。所示的情况。 第三章处理机调度与死锁 图3-21资源分配图的简化 第三章处理机调度与死锁 (2) (2) (2) (2) p p p p1 1 1 1释释释释放放放放资资资资源源源源后后后后，便便便便可可可可使使使使p2p2p2p2获获获获得得得得资资资资源源源源而而而而继继继继续续续续运运运运行行行行，直直直直至至至

187、至p p p p2 2 2 2完完完完成成成成后后后后又又又又释释释释放放放放出出出出它它它它所所所所占占占占有有有有的的的的全全全全部部部部资资资资源源源源，形形形形成成成成图图图图(c)(c)(c)(c)所所所所示示示示的的的的情况。情况。情况。情况。(3) (3) (3) (3) 在在在在进进进进行行行行一一一一系系系系列列列列的的的的简简简简化化化化后后后后，若若若若能能能能消消消消去去去去图图图图中中中中所所所所有有有有的的的的边边边边，使使使使所所所所有有有有的的的的进进进进程程程程结结结结点点点点都都都都成成成成为为为为孤孤孤孤立立立立结结结结点点点点，则则则则称称称称该该该该图

188、图图图是是是是可可可可完完完完全全全全简简简简化化化化的的的的；若若若若不不不不能能能能通通通通过过过过任任任任何何何何过过过过程程程程使使使使该该该该图图图图完完完完全全全全简简简简化化化化，则则则则称称称称该该该该图图图图是是是是不不不不可可可可完全简化的。完全简化的。完全简化的。完全简化的。对于较复杂的资源分配图，可能有多个既未阻塞，又非对于较复杂的资源分配图，可能有多个既未阻塞，又非对于较复杂的资源分配图，可能有多个既未阻塞，又非对于较复杂的资源分配图，可能有多个既未阻塞，又非孤立的进程结点，不同的简化顺序是否会得到不同的简化图孤立的进程结点，不同的简化顺序是否会得到不同的简化图孤立的

189、进程结点，不同的简化顺序是否会得到不同的简化图孤立的进程结点，不同的简化顺序是否会得到不同的简化图？有关文献已经证明，所有的简化顺序，都将得到相同的不？有关文献已经证明，所有的简化顺序，都将得到相同的不？有关文献已经证明，所有的简化顺序，都将得到相同的不？有关文献已经证明，所有的简化顺序，都将得到相同的不可简化图。同样可以证明：可简化图。同样可以证明：可简化图。同样可以证明：可简化图。同样可以证明： S S S S为死锁状态的充分条件是：当且仅当为死锁状态的充分条件是：当且仅当为死锁状态的充分条件是：当且仅当为死锁状态的充分条件是：当且仅当S S S S状态的资源分配状态的资源分配状态的资源分

190、配状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。图是不可完全简化的。该充分条件被称为死锁定理。图是不可完全简化的。该充分条件被称为死锁定理。图是不可完全简化的。该充分条件被称为死锁定理。 第三章处理机调度与死锁 3 3 3 3死锁检测中的数据结构死锁检测中的数据结构死锁检测中的数据结构死锁检测中的数据结构死锁检测中的数据结构类似于银行家算法中的数据结构：死锁检测中的数据结构类似于银行家算法中的数据结构：死锁检测中的数据结构类似于银行家算法中的数据结构：死锁检测中的数据结构类似于银行家算法中的数据结构：(1) (1) (1) (1) 可可可可利利利利用用用用资资资资源源源源向向向向

191、量量量量AvailableAvailableAvailableAvailable，它它它它表表表表示示示示了了了了m m m m类类类类资资资资源源源源中中中中每每每每一类资源的可用数目。一类资源的可用数目。一类资源的可用数目。一类资源的可用数目。(2) (2) (2) (2) 把把把把不不不不占占占占用用用用资资资资源源源源的的的的进进进进程程程程( ( ( (向向向向量量量量AllocationAllocationAllocationAllocationi i i i:=0):=0):=0):=0)记记记记入入入入L L L L表表表表中，即中，即中，即中，即L L L Li i i iL

192、LLL。(3) (3) (3) (3) 从从从从进进进进程程程程集集集集合合合合中中中中找找找找到到到到一一一一个个个个RequestRequestRequestRequesti i i iWorkWorkWorkWork的的的的进进进进程程程程，做做做做如如如如下处理：下处理：下处理：下处理： 将将将将其其其其资资资资源源源源分分分分配配配配图图图图简简简简化化化化，释释释释放放放放出出出出资资资资源源源源，增增增增加加加加工工工工作作作作向向向向量量量量Work:=Work + Allocation Work:=Work + Allocation Work:=Work + Allocati

193、on Work:=Work + Allocation i i i i。 将它记入将它记入将它记入将它记入L L L L表中。表中。表中。表中。第三章处理机调度与死锁 (4) 若不能把所有进程都记入L表中，便表明系统状态S的资源分配图是不可完全简化的。 因此，该系统状态将发生死锁。Work:=Available；L:=Li |Allocation i=0Request i=0for all Li L dobeginfor all Request iWork dobeginWork:=Work + Allocation i；LiL；endenddeadlock:=(L=p1，p2，pn)；第三章处

194、理机调度与死锁 3.7.23.7.2死锁的解除死锁的解除常采用解除死锁的两种方法是：(1) 剥剥剥剥夺夺夺夺资资资资源源源源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。(2) 撤撤消消进进程程。最简单的撤消进程的方法是使全部死锁进程都夭折掉；稍微温和一点的方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。第三章处理机调度与死锁 本章重点n 三级调度；n 单CPU的调度算法；n 实时调度；n 死锁 1. 定义 举例 2. 引起死锁的原因 3. 产生死锁的必要条件 4. 死锁预防n 银行家算法；第三章处理机调度与死锁 练习：练习：P P个进程共享个进程共享m

195、 m个同类资源，每一个资源在任一时个同类资源，每一个资源在任一时刻只能供一个进程使用，每一进程对任一资源都只能刻只能供一个进程使用，每一进程对任一资源都只能使用一有限时间，使用完便立即释放。并且每个进程使用一有限时间，使用完便立即释放。并且每个进程对该类资源的最大需求量小于该类资源的数目。设所对该类资源的最大需求量小于该类资源的数目。设所有进程对资源的最大需求数目之和小于有进程对资源的最大需求数目之和小于p+mp+m。试证：该试证：该系统中不会发生死锁。系统中不会发生死锁。解：设进程解：设进程i i所需资源数为所需资源数为riri，根据题意：根据题意： r1+ r2+r1+ r2+ + rpr

196、pp+m p+m 即即 (r1-1)+ ( r2 -1) +(r1-1)+ ( r2 -1) + ( + ( rprp -1) m -1) m 因此，在最坏的情况下也至少有一个进程能得因此，在最坏的情况下也至少有一个进程能得到它所需的所有资源，从而可以运行完毕，之后就到它所需的所有资源，从而可以运行完毕，之后就可以释放它所占有的资源，近而使所有进程运行完可以释放它所占有的资源，近而使所有进程运行完毕。毕。第三章处理机调度与死锁 AB运河运河弯道弯道河道河道公路公路100mhttp:/202.192.240.27/sfzx/xxxy/other/kj_623/3/02/cpu/PCP_JC_8.

197、SWF第三章处理机调度与死锁 Main() Main() PshipPship( ) ( ) PcarPcar( )( ) intint Sa= Sa=SbSb=1; p(Sa); =1; p(Sa); p(Snp(Sn); ); intint SnSn=n; =n; 船头船头过过A A桥；桥； p(Sbp(Sb););cobegincobegin p(Sbp(Sb); ); 过过B B桥；桥；PshipPship( ); ( ); 船头船头过过B B桥；桥； v(Sbv(Sb););PcarPcar( ); ( ); 船尾过船尾过A A桥；桥； 过弯道；过弯道；coendcoend v(Sa

198、); p(Sa); v(Sa); p(Sa); 船尾过船尾过B B桥；桥； v(Snv(Sn);); v(Sbv(Sb); ); 过过A A桥；桥； v(Sa); v(Sa); 第三章处理机调度与死锁 本章作业nP1158、18、22实验：第三章处理机调度与死锁 死锁部分例题死锁部分例题(1) (1) 在某一时刻，系统中既无执行态进程又无就绪态在某一时刻，系统中既无执行态进程又无就绪态进程，是否可能？若可能，在什么情况下会发生进程，是否可能？若可能，在什么情况下会发生？ 解答解答: : 可能。在系统死锁状态下，进程处于占有等可能。在系统死锁状态下，进程处于占有等待资源的状态，应当既不属于执行态

199、也不属于就绪待资源的状态，应当既不属于执行态也不属于就绪态。态。 第三章处理机调度与死锁 死锁部分例题死锁部分例题(2) (2) 一台计算机有八台磁带机。它们由一台计算机有八台磁带机。它们由N N个进程竞争个进程竞争使用，每个进程可能需要使用，每个进程可能需要3 3台磁带机。请问台磁带机。请问N N为多少为多少时，系统没有死锁危险，并说明其原因。时，系统没有死锁危险，并说明其原因。 第三章处理机调度与死锁 死锁部分例题死锁部分例题(2) (2) 一台计算机有八台磁带机。它们由一台计算机有八台磁带机。它们由N N个进程竞争个进程竞争使用，每个进程可能需要使用，每个进程可能需要3 3台磁带机。请问

200、台磁带机。请问N N为多少为多少时，系统没有死锁危险，并说明其原因。时，系统没有死锁危险，并说明其原因。 解答解答: :判断原则一：资源总数是否足够判断原则一：资源总数是否足够判断原则二：资源是否可以顺利被释放判断原则二：资源是否可以顺利被释放当当N N2 2的时候的时候 永远不会发生死锁永远不会发生死锁 第三章处理机调度与死锁 当当N N3 3，3 3个进程竞争个进程竞争8 8台设备台设备, ,也不会死锁也不会死锁当当N=4 P1 P2 P3 P4 8N=4 P1 P2 P3 P4 8台台 Max 3 3 3 3Max 3 3 3 3 Allocation 1 1 1 1 Allocatio

201、n 1 1 1 1 剩剩4 4台台 存在安全序列存在安全序列,按照安全序列推按照安全序列推进时不会死锁进时不会死锁, ,否则存在死锁危险否则存在死锁危险. .当当N=5 P1 P2 P3 P4 P5 8N=5 P1 P2 P3 P4 P5 8台台 Max 3 3 3 3 3Max 3 3 3 3 3 Allocation 1 1 1 1 1 Allocation 1 1 1 1 1 剩剩3 3台台第三章处理机调度与死锁 存在安全序列存在安全序列,按照安按照安全序列推进时不会死锁全序列推进时不会死锁, ,否则存在死锁危险否则存在死锁危险. .N N6 P1 P2 P3 P4 P5 P6 86 P

202、1 P2 P3 P4 P5 P6 8台台 Max 3 3 3 3 3 3Max 3 3 3 3 3 3 Allocation 1 1 1 1 1 1 Allocation 1 1 1 1 1 1 剩剩2 2台台 存在安全序列存在安全序列,按照按照安全序列推进时不会死锁安全序列推进时不会死锁, ,否则存在死锁危险否则存在死锁危险. .N N7 P1 P2 P3 P4 P5 P6 P7 87 P1 P2 P3 P4 P5 P6 P7 8台台 1 1 1 1 1 1 1 1 1 1 1 1 1 1 剩下剩下1 1台，台， 不存在安全序列不存在安全序列, ,会死锁会死锁第三章处理机调度与死锁 假设系统

203、处于下列状态，目前系统剩余资源数量为2。下列哪一个进程序列有可能发生死锁？进程 已占资源数 最大需求数 P1 1 2 P2 4 7 P3 3 5 P4 5 7 A）P1，P2，P3，P4B）P2，P3，P4，P1C）P3，P1，P2，P4D）P4，P3，P2，P1第三章处理机调度与死锁 (3) N个进程共享某种资源r，该资源共有m(mn)个可分配单位，每个进程每次一个地申请或释放资源单位，假设每个进程对该资源的最大需求量均小于m，且各进程的最大需求量之和小于m+n，试证明这个系统中不可能发生死锁。 第三章处理机调度与死锁 (3) N个进程共享某种资源r，该资源共有m(mn)个可分配单位，每个进

204、程每次一个地申请或释放资源单位，假设每个进程对该资源的最大需求量均小于m，且各进程的最大需求量之和小于m+n，试证明这个系统中不可能发生死锁。 解：设max（i）表示第I个进程的最大需求量，need（I）表示第I个进程还需要的资源量。Alloc（I）表示第I个进程已分配的资源量。由题中所给的已知条件可知：max(1)+max(n)=(need(1)+need(n)+(alloc(1)+alloc(n)m+n第三章处理机调度与死锁 如果在这个系统中发生了死锁，那么一方面m个资源应该全部分配出去，即： alloc(1)+alloc(n)=m 另一方面所有进程将陷入无限等待的状态。 由上述两式可得：

205、 need(1)+need(n)n 上式表示发生死锁后，n个进程还需要的最小资源量之和小于n,这意味着此刻至少存在着一个进程I，need（I）=0，即它已获得了所需的全部资源。既然该进程已获得了所需的全部资源，那么它就能执行完成并释放它所占有的全部资源，这与前面的假设矛盾，从而证明了这个系统中不可能发生死锁。第三章处理机调度与死锁 基本概念选择题基本概念选择题 (1)(1)在在为为多多道道程程序序所所提提供供的的可可共共享享的的系系统统资资源源不不足足时时，可可能能出出现现死死锁锁。但但是是不不适适当当的的_也也可可能产生死锁。能产生死锁。 A.A.进程优先权进程优先权 B.B.资源的线性分配

206、资源的线性分配 C.C.进程的推进顺序进程的推进顺序. D. D.分配队列优先权分配队列优先权 (2)(2)采采用用资资源源剥剥夺夺法法可可解解决决死死锁锁，还还可可以以采采用用_方法解决死锁。方法解决死锁。 A.A.执行并行操作执行并行操作 B.B.撤消进程撤消进程. . C. C.拒绝分派新资源拒绝分派新资源 D.D.修改信号量修改信号量第三章处理机调度与死锁 （3)死锁的四个必要条件是：互斥,_，循环等待和不剥夺。 A 请求与阻塞 B 请求与保持. C 请求与释放 D 释放与阻塞 (4)资源的按序分配策略可以破坏_条件。 A 互斥使用资源 B 占有且等待资源 C 非剥夺资源 D 循环等待资源. 第三章处理机调度与死锁 (5)检测发生死锁时，可以通过撤消一个进程解除死锁。上诉描述是_。 A 正确的 B 错误的.第三章处理机调度与死锁 本章完The End