操作系统调度与死锁课件

《操作系统调度与死锁课件》由会员分享，可在线阅读，更多相关《操作系统调度与死锁课件（35页珍藏版）》请在金锄头文库上搜索。

1、进程调度的核心是调度算法。进程调度的核心是调度算法。进程调度的核心是调度算法。进程调度的核心是调度算法。 进程调度是实现多道程序系统的关键，直接影进程调度是实现多道程序系统的关键，直接影进程调度是实现多道程序系统的关键，直接影进程调度是实现多道程序系统的关键，直接影响到操作系统的性能，是本章讨论的主要问题。响到操作系统的性能，是本章讨论的主要问题。响到操作系统的性能，是本章讨论的主要问题。响到操作系统的性能，是本章讨论的主要问题。操作系统调度与死锁3.1 调度的基本概念调度的基本概念 (一）一） 作业从进入系统到完成作业从进入系统到完成，可能要经历三级调度过程：可能要经历三级调度过程：一、调度

2、的类型和模型一、调度的类型和模型一、调度的类型和模型一、调度的类型和模型1、高级调度、高级调度 又称为又称为作业调度作业调度，它决定将哪些在外存上处于，它决定将哪些在外存上处于后备状态的作业调入主机内存，准备执行。因此，有时把它后备状态的作业调入主机内存，准备执行。因此，有时把它称为接纳调度。称为接纳调度。2 2、低级调度、低级调度 又称为又称为进程调度进程调度，它决定就绪队列中哪个进程，它决定就绪队列中哪个进程将获得处理机，并实际执行将处理机分配给进程的操作。执将获得处理机，并实际执行将处理机分配给进程的操作。执行分配处理机的程序称为行分配处理机的程序称为分派程序分派程序。3、中级调度、中级

3、调度 中级调度的主要作用是在内存和外存之间进行中级调度的主要作用是在内存和外存之间进行进程交换，以解决内存紧张的问题。如它将内存中处于等待进程交换，以解决内存紧张的问题。如它将内存中处于等待状态的某些进程调至外存对换区，以腾出内存空间，而将外状态的某些进程调至外存对换区，以腾出内存空间，而将外存对换区上已具备运行条件的进程重新调入内存，准备运行。存对换区上已具备运行条件的进程重新调入内存，准备运行。故又称为故又称为交换调度交换调度。操作系统调度与死锁 阻塞阻塞状态状态就绪就绪状态状态执行执行状态状态调度调度I/O请求请求进程进程释放释放时间时间片到片到后备作业队列后备作业队列3.1 3.1 调

4、度的基本概念调度的基本概念调度的基本概念调度的基本概念 ( (二）二）二）二）CPU就就绪绪队队列列阻阻塞塞队队列列作业调度作业调度等待事件等待事件中级中级调度调度即交换调度即交换调度交换文件交换文件就绪队列就绪队列阻塞队列阻塞队列三级调度的模型三级调度的模型操作系统调度与死锁3.1 调度的基本概念调度的基本概念 (三）三）作业调度是确定作业调度是确定哪些作业哪些作业可以被可以被调入内存调入内存。进程调度是确定进程调度是确定哪哪个个进程进程可以可以占有占有CPUCPU并执行。并执行。作业调度是进程调度的基础，作业被作业调度是进程调度的基础，作业被调入内存调入内存后，后，是以是以进程的形式执行进

5、程的形式执行的。的。在一个在一个OSOS中进程调度与作业调度的算法是一致的。中进程调度与作业调度的算法是一致的。？问题？问题？1 1 1 1。进程调度与。进程调度与。进程调度与。进程调度与 作业调度之间（功能、调度算法）有作业调度之间（功能、调度算法）有作业调度之间（功能、调度算法）有作业调度之间（功能、调度算法）有 何区别和联系？何区别和联系？何区别和联系？何区别和联系？2 2 2 2。三级调度中，最核心的是那一级调度？为什么。三级调度中，最核心的是那一级调度？为什么。三级调度中，最核心的是那一级调度？为什么。三级调度中，最核心的是那一级调度？为什么？各级调度间的关系各级调度间的关系操作系统

6、调度与死锁3.1 调度的基本概念调度的基本概念 (四）四） 作业作业 是用户请求计算机系统执行的一次独立的上机任是用户请求计算机系统执行的一次独立的上机任 务，是能够共享公共资源区域的一族有关进程（家族）。务，是能够共享公共资源区域的一族有关进程（家族）。 从静态观点看，作业由从静态观点看，作业由 控制命令系列、程序集、数据控制命令系列、程序集、数据 集三部分构成。集三部分构成。补充：关于作业的概念补充：关于作业的概念作业控制块作业控制块 JCB（Job Control Block）用于描述作业。）用于描述作业。 定义为记录类型（作业名、优先级、建立时间、状态外定义为记录类型（作业名、优先级、

7、建立时间、状态外 存地址、大小等）。存地址、大小等）。 作业状态作业状态 作业在其生命期中，共有四种状态：作业在其生命期中，共有四种状态：操作系统调度与死锁关于作业的状态关于作业的状态 作业状态作业状态 作业在其生命期中，共有四种状态：作业在其生命期中，共有四种状态： 进入、后备、运行、完成进入、后备、运行、完成进入、后备、运行、完成进入、后备、运行、完成完成完成执行执行就绪就绪阻塞阻塞进入进入后备后备内存内存内存内存运行运行提交提交作业作业调度调度完成完成问题：引起进程调度的问题：引起进程调度的原因有哪些？原因有哪些？操作系统调度与死锁3.1 调度的基本概念调度的基本概念 (五）五）在在OS

8、OS中，进程调度的方式分为两类。中，进程调度的方式分为两类。二、进程调度的方式二、进程调度的方式二、进程调度的方式二、进程调度的方式操作系统调度与死锁3.1 调度的基本概念调度的基本概念 (六）六）三、进程调度的功能三、进程调度的功能三、进程调度的功能三、进程调度的功能操作系统调度与死锁3.1 调度的基本概念调度的基本概念 (七）七） 1。周转时间短。周转时间短 周转时间周转时间TT（Tumaround Time） 对作业对作业从作业提交到完成。从作业提交到完成。 对进程对进程第一次进入就绪队列到运行结束。第一次进入就绪队列到运行结束。 平均周转时间平均周转时间ATT（Average Tuma

9、round Time） ATT= Ti 带权平均带权平均 W= 其中：其中： Ti 各进程的各进程的TT TT T Tr ri i 实际执行时间实际执行时间2. 2. 响应时间快响应时间快 响应时间响应时间RTRT（Response TimeResponse Time）输入键盘命令到屏幕输入键盘命令到屏幕显示结果。显示结果。四四. 调度算法准则调度算法准则 调度算法应该尽可能调度算法应该尽可能提高资源利用率，减少提高资源利用率，减少提高资源利用率，减少提高资源利用率，减少CPUCPUCPUCPU空闲时空闲时空闲时空闲时间间间间, , , ,公平服务。公平服务。公平服务。公平服务。可从以下方面考

10、虑：可从以下方面考虑：1ni=1nTiTrii=1n1 n操作系统调度与死锁3.23.2 调度算法调度算法 （一）（一）思考题思考题 1、各种调度算法的特点、性能如何？适宜于各种调度算法的特点、性能如何？适宜于 哪类哪类 OS？ 2。最高优先权算法中，动态优先权有何实际意义？。最高优先权算法中，动态优先权有何实际意义？常用调度算法常用调度算法常用调度算法常用调度算法操作系统调度与死锁3.23.2 调度算法调度算法 （二）（二） FCFS（First Come First Server ）法，又称为先）法，又称为先进先出（进先出（FIFO）算法，就绪进程按照进入的先后次序排列，）算法，就绪进程按

11、照进入的先后次序排列，调度程序总是选择队首的进程执行。调度程序总是选择队首的进程执行。 该算法只能用于辅助算法。该算法只能用于辅助算法。操作系统调度与死锁3.23.2 调度算法调度算法 （二）（二）n+1nnt 该算法优于该算法优于FCFS，但长进程等待时间长，估算误差较大。，但长进程等待时间长，估算误差较大。 SCBF（Shortest CPU Burst First） ，即调度程序总，即调度程序总是选择是选择CPU运行时间最短的进程执行。运行时间最短的进程执行。其中其中 为估计的第为估计的第n个个CPU 周期。周期。tn 为实际值。为实际值。 为控制值，为控制值，0 1，常取常取 0.5n

12、 对对最短最短CPUCPU运行期的估算，依赖于系统的下一个运行期的估算，依赖于系统的下一个CPUCPU周周期中，实现较困难。进程的期中，实现较困难。进程的CPU时间时间 的估算公式：的估算公式：n+1操作系统调度与死锁3.23.2 调度算法调度算法 （三）（三） 调度程序每次都将调度程序每次都将CPU分配给就绪队列中具有最高优先分配给就绪队列中具有最高优先级（级（Highest Priority）的进程。该）的进程。该算法的核心是算法的核心是优先级的优先级的确定。确定。 调度方式分为调度方式分为剥夺式剥夺式和和非剥夺式非剥夺式。 静态优先级静态优先级 在创建进程时根据进程的特性或者用户要求赋予

13、，在进在创建进程时根据进程的特性或者用户要求赋予，在进程的整个生命期中程的整个生命期中不能改变不能改变。 简单、易实现，但是调度性能不高，优先级低的进程可简单、易实现，但是调度性能不高，优先级低的进程可能长期等待。能长期等待。 动态优先级动态优先级 在创建进程时为进程赋予一个在创建进程时为进程赋予一个基本优先级基本优先级，在进程的执，在进程的执行过程中可随进程的特性行过程中可随进程的特性动态改变动态改变。 引起优先级改变的原因：引起优先级改变的原因： 进程等待进程等待CPU时间长短，执行所需时间长短，执行所需CPU时间长短等。时间长短等。 分两类优先级：分两类优先级：操作系统调度与死锁3.23

14、.2 调度算法调度算法 （四）（四）确定进程优先级的一般原则：确定进程优先级的一般原则： 1. 进程的类型进程的类型 例如：例如： 系统进程高于用户进程；系统进程高于用户进程； 前台进程高于后台进程；前台进程高于后台进程； 实时进程高于一般进程。实时进程高于一般进程。 2. 对资源的需求量及类型对资源的需求量及类型 占用占用CPU时间少的，使用内存资源少的进程优时间少的，使用内存资源少的进程优先级高。先级高。 3. 按作业到达系统的时间顺序按作业到达系统的时间顺序 4. 按用户类型和要求按用户类型和要求操作系统调度与死锁 3.2 3.2 调度算法调度算法 （五）（五） 该该算法主要用于分时系统

15、，按照公平服务的原则，算法主要用于分时系统，按照公平服务的原则，为进程分配为进程分配CPUCPU时间片。是一种剥夺式的算法。时间片。是一种剥夺式的算法。 轮转法的关键是时间片的选取：轮转法的关键是时间片的选取： 时间片太大，则轮转法蜕化为时间片太大，则轮转法蜕化为FCFSFCFS法。法。 时间片太小，则增加时间片太小，则增加CPUCPU的额外开销。的额外开销。 影响时间片设置的主要因素：影响时间片设置的主要因素： 系统响应时间系统响应时间R R、就绪进程数、就绪进程数N N、计算机处理能力等。、计算机处理能力等。 时间片长度：时间片长度： q = R / N max操作系统调度与死锁3.23.

16、2 调度算法调度算法 （六）（六） HRN（Highest Response ratio Next）算法将短进算法将短进程优先与动态优先级相结合。所谓高响应是指进程获得程优先与动态优先级相结合。所谓高响应是指进程获得调度的响应，即优先数调度的响应，即优先数R R。 R =R =（W+TW+T）/T = 1+W/T/T = 1+W/T T T 估计进程执行的时间。估计进程执行的时间。 W W 进程等待的时间。进程等待的时间。 随着进程等待时间的增加，优先权动态增加。随着进程等待时间的增加，优先权动态增加。 对等待相同时间的短进程比长进程优先权增加得多。对等待相同时间的短进程比长进程优先权增加得多

17、。 长进程随着等待时间增加也会被调度。长进程随着等待时间增加也会被调度。操作系统调度与死锁3.23.2 调度算法调度算法 （七）（七） 根根据据作作业业性性质质不不同同分分为为若若干干个个就就绪绪队队列列，如如：系系统统进进程程队队列列，交交互互进进程程队队列列，批批处处理理队队列等。对各队列采用不同的调度算法。列等。对各队列采用不同的调度算法。操作系统调度与死锁3.23.2 调度算法调度算法 （八）（八） 多级反馈队列是一种多级反馈队列是一种综合调度算法综合调度算法，对进程就绪队列进，对进程就绪队列进行动态调度和管理。行动态调度和管理。操作系统调度与死锁3.23.2 调度算法调度算法 （九）

18、（九）七、多级反馈队列七、多级反馈队列操作系统调度与死锁3.3 3.3 进程调度实例进程调度实例 ( (一）一）一。一。VMSVMS进程调度进程调度 综合调度算法：综合调度算法：以优先级为基础的多级反馈队列。以优先级为基础的多级反馈队列。 VMS中的优先级：中的优先级： 1。硬件优先级（。硬件优先级（IPL）中断优先级，存储在硬件中断优先级，存储在硬件PCB中。中。 2。软件优先级。软件优先级 （0 31级）存储在软件级）存储在软件PCB中。中。 1631 实时优先级实时优先级（静态优先级静态优先级），用于实时进程。），用于实时进程。 不受时间片影响，进程一旦被调度，一直执行不受时间片影响，进

19、程一旦被调度，一直执行 到到 结束。结束。 0 15 正常正常优先级优先级 （动态优先级动态优先级），用于非实时进程，），用于非实时进程， 为每个优先级队列设置不同的为每个优先级队列设置不同的 时间片。优先级时间片。优先级 愈高，时间片愈短。愈高，时间片愈短。操作系统调度与死锁3.3 3.3 进程调度实例进程调度实例 ( (二）二） 正正常常优优先先级级进进程程（0 15）在在创创建建时时，系系统统为为其其分分配配了了 基本优先级基本优先级： 交互进程为交互进程为4，批处理进程为，批处理进程为3。 优先级提升优先级提升幅度的原则：幅度的原则： 随着进程等待时间增加，优先级提升幅度增加。随着进程

20、等待时间增加，优先级提升幅度增加。 因因进进程程类类型型而而定定；受受 I/O 限限制制的的进进程程提提升升幅幅度度大大于于受受计算限制的进程。计算限制的进程。VMSVMS中进程优先级的动态提升中进程优先级的动态提升 在进程运行过程中，优先级会有不同幅度（在进程运行过程中，优先级会有不同幅度（0 6）的提）的提 升，使进程获得调度的可能性。升，使进程获得调度的可能性。进进程程优优先先级级下下降降 ：当当进进程程因因为为时时间间片片到到或或者者等等待待某某事事件发生而释放件发生而释放CPU时，优先级下降。时，优先级下降。优先级改变后的进程排到相应队列的队尾优先级改变后的进程排到相应队列的队尾 。

21、操作系统调度与死锁优先级队列优先级队列31301516140静静态态优优先先级级动动态态优优先先级级CPU等等待待队队列列优优先先级级下下降降进程按照进程按照优先级优先级排成排成32个就绪队列。个就绪队列。每个每个就绪队列按照就绪队列按照FCFS算法排队。算法排队。优先级越高时间片越小。优先级越高时间片越小。操作系统调度与死锁3.3 3.3 进程调度实例进程调度实例 ( (三）三） 进程的优先权分进程的优先权分31级（级（1 - 31），为动态优先级：在基），为动态优先级：在基本优先级的基础上波动本优先级的基础上波动 + 2级。级。 基本优先权设置（基本优先权设置（4组）组） 优先权等级优先权

22、等级 优先权范围优先权范围 Idle Idle （闲置闲置） 1 6 1 6 Normal Normal （标准）标准） 6 10 6 10 High High （高级）高级） 11 15 11 15 Realtime Realtime（实时）实时） 16 3116 31 进程调度过程中优先权的动态提升有何实际意义？进程调度过程中优先权的动态提升有何实际意义？WINDOWS NT 的进程优先级的进程优先级问问 题题操作系统调度与死锁3.5 3.5 线程的基本概念线程的基本概念 （一）（一） 为了减少进程并发执行的开销，提高系统性能。将为了减少进程并发执行的开销，提高系统性能。将资源分配与调度分

23、开资源分配与调度分开引入线程。引入线程。1 1。构成构成构成构成 一个进程可由一个或者多个线程构成。其中一定有一一个进程可由一个或者多个线程构成。其中一定有一一个进程可由一个或者多个线程构成。其中一定有一一个进程可由一个或者多个线程构成。其中一定有一个主线程。个主线程。个主线程。个主线程。 进程是分配资源的基本单位，线程是可调度的基本单位。进程是分配资源的基本单位，线程是可调度的基本单位。进程是分配资源的基本单位，线程是可调度的基本单位。进程是分配资源的基本单位，线程是可调度的基本单位。 进程用进程用进程用进程用PCBPCB块描述，线程用块描述，线程用块描述，线程用块描述，线程用TCBTCB块

24、（块（块（块（Thread control Thread control BlockBlock）描述。）描述。）描述。）描述。 线程是进程内一个可调度的实体。具有独立的程序计数线程是进程内一个可调度的实体。具有独立的程序计数线程是进程内一个可调度的实体。具有独立的程序计数线程是进程内一个可调度的实体。具有独立的程序计数器。器。器。器。一。一。为什么引入线程为什么引入线程为什么引入线程为什么引入线程 （ThreadThread）二。二。线程与进程线程与进程线程与进程线程与进程操作系统调度与死锁3.5 3.5 线程的基本概念线程的基本概念 （二）（二）线程线程1 1的的TCBTCB线程线程2 2的

25、的TCBTCB线程线程3 3的的TCBTCBTCBCPU 状态状态堆栈堆栈程序计数器程序计数器 . . .寄存器寄存器PCB进程标识进程标识资源清单资源清单 . . .TCB输入线程输入线程 主线程主线程 计算线程计算线程 输出线程输出线程 图图1图图2主线程主线程 创建创建线线程程 1 。 创建创建线线程程 n图图3操作系统调度与死锁2. 线程线程 的并发性的并发性 同同一一进进程程 的的多多个个线线程程具具有有并并发发执执行行的的特特性性，线线程程之之间间相互约束，线程执行过程呈现间断性。线程也具有就绪、相互约束，线程执行过程呈现间断性。线程也具有就绪、 阻塞和执行三种基本状态。阻塞和执行

26、三种基本状态。3. 线程资源线程资源 线线程程可可以以与与其其它它同同属属一一个个进进程程的的线线程程共共同同拥拥有有该该进进程程的资源。的资源。3.5 3.5 线程的基本概念线程的基本概念 （三）（三）4 4. 线程的调度线程的调度 线程作为调度的基本单位，在线程作为调度的基本单位，在windows NT 等等32位位OS 中，采用按优先级调度的策略。中，采用按优先级调度的策略。 线程的调度算法与进程类似，对线程的调度算法与进程类似，对CPU的分配也分的分配也分抢占抢占 式式和和非抢占式。非抢占式。操作系统调度与死锁3.5 3.5 线程的基本概念线程的基本概念 （四）（四）5 5。系统开销。

27、系统开销。系统开销。系统开销 从以下方面比较进程与线程的开销。从以下方面比较进程与线程的开销。从以下方面比较进程与线程的开销。从以下方面比较进程与线程的开销。 创建创建创建创建创建创建撤消的撤消的撤消的撤消的撤消的撤消的开销开销开销开销开销开销 PCB PCB PCB PCB 比比比比 TCB TCB TCB TCB 复杂复杂复杂复杂 调度调度调度调度调度调度开销开销开销开销开销开销 同一进程内的线程切换的开销小于进程切换开销，同一进程内的线程切换的开销小于进程切换开销，同一进程内的线程切换的开销小于进程切换开销，同一进程内的线程切换的开销小于进程切换开销， 不会引起进程切换。不会引起进程切换

28、。不会引起进程切换。不会引起进程切换。 资源开销资源开销资源开销资源开销资源开销资源开销 线程一般不拥有资源，但可访问所属进程的资源。线程一般不拥有资源，但可访问所属进程的资源。线程一般不拥有资源，但可访问所属进程的资源。线程一般不拥有资源，但可访问所属进程的资源。 通信通信通信通信通信通信开销开销开销开销开销开销 进程通信进程通信进程通信进程通信具有独立的地址空间，通过共享文件等。具有独立的地址空间，通过共享文件等。具有独立的地址空间，通过共享文件等。具有独立的地址空间，通过共享文件等。 线程通信线程通信线程通信线程通信任务通信，开销小。任务通信，开销小。任务通信，开销小。任务通信，开销小。

29、操作系统调度与死锁3.7 3.7 死锁的基本概念（一）死锁的基本概念（一） 死锁（死锁（死锁（死锁（deadlockdeadlock） 是是是是OSOS的一种随机故障，的一种随机故障，的一种随机故障，的一种随机故障，是指两个或是指两个或是指两个或是指两个或 两个以上的进程都无限制的地等待永远不会出现的两个以上的进程都无限制的地等待永远不会出现的两个以上的进程都无限制的地等待永远不会出现的两个以上的进程都无限制的地等待永远不会出现的 事件而发生的状态。事件而发生的状态。事件而发生的状态。事件而发生的状态。1、争夺资源引起死锁争夺资源引起死锁 例例1：P1，P2两个进程争夺打印机和读卡机。两个进程

30、争夺打印机和读卡机。一、一、死锁的原因死锁的原因死锁的原因死锁的原因P1P2打印机读卡机 P1P1已经申请到打印机，已经申请到打印机， 又申请读卡机。又申请读卡机。 P2P2已经申请到读卡机，已经申请到读卡机， 又申请打印机。又申请打印机。打印机和读卡机为打印机和读卡机为非剥夺性资源。非剥夺性资源。操作系统调度与死锁例例3 3、 P1 P1，P2P2，P3 P3 三个进程之间通信：三个进程之间通信： P1 P1产生消息产生消息S1S1，接收，接收P3P3产生的消息产生的消息S3S3； P2 P2产生消息产生消息S2S2，接收，接收P1P1产生的消息产生的消息S1S1； P3 P3产生消息产生消

31、息S3S3，接收，接收P2P2产生的消息产生的消息S2S2；按以下次序运行：按以下次序运行：P1：Request（S3）；Release（ S1）P2：Request（S1）；Release（ S2）P3：Request（S2）；Release（ S3）3.7 3.7 死锁的基本概念死锁的基本概念死锁的基本概念死锁的基本概念（二）（二）（二）（二）2 2 2 2、进程推动顺序不当引起的死锁、进程推动顺序不当引起的死锁、进程推动顺序不当引起的死锁、进程推动顺序不当引起的死锁P1P3P2S2S3S1P1P2P3按照以上的顺序执行会产生死锁吗按照以上的顺序执行会产生死锁吗？例例2 2、 在生产者在生

32、产者消费者问题中如果交换两个消费者问题中如果交换两个P P操作操作 的次序，可能引起死锁。的次序，可能引起死锁。S Si i临时性资源临时性资源操作系统调度与死锁3.7 死锁的基本概念死锁的基本概念（三）（三）生产者生产者消费者问题算法：消费者问题算法：操作系统调度与死锁3.7 死锁的基本概念死锁的基本概念（四）（四） 由于由于 产生死锁的根本原因是争夺共享资源，从而得产生死锁的根本原因是争夺共享资源，从而得到产生到产生死锁的必要条件是死锁的必要条件是：二。二。二。二。死锁的必要条件死锁的必要条件死锁的必要条件死锁的必要条件操作系统调度与死锁3.7 死锁的基本概念死锁的基本概念（五）（五） 显

33、然，如果出现死锁将对操作系统造成极大的危害，显然，如果出现死锁将对操作系统造成极大的危害，甚至使系统瘫痪，如何解决死锁是操作系统设计的重要甚至使系统瘫痪，如何解决死锁是操作系统设计的重要问题。问题。 限制并发进程对于资源的限制并发进程对于资源的需求，破坏产生死需求，破坏产生死 锁的必锁的必要条件。严格限制死锁的要条件。严格限制死锁的发生。发生。预防死锁预防死锁避免死锁避免死锁在资源的在资源的动态分配动态分配过程中，过程中，采用某种算法防止系统进采用某种算法防止系统进入不安全状态，避免死锁入不安全状态，避免死锁发生。发生。检测与解除死锁检测与解除死锁对资源的分配不加限制，系统定时运行对资源的分配

34、不加限制，系统定时运行“死锁死锁 检测检测”程序，如检测到死锁，设法加以解除。程序，如检测到死锁，设法加以解除。操作系统调度与死锁3.7 死锁的基本概念死锁的基本概念（六）（六） 采用资源的静态分配策略，破坏采用资源的静态分配策略，破坏“部分分配部分分配”条件条件。 即只有当进程所需要的全部资源满足时，系统予以即只有当进程所需要的全部资源满足时，系统予以 一次分配。一次分配。 允许进程剥夺使用其他进程占有的资源，破坏允许进程剥夺使用其他进程占有的资源，破坏“不不 剥夺条件剥夺条件”。 进程动态申请资源，当进程申请不到新资源时，应立进程动态申请资源，当进程申请不到新资源时，应立即释放已占有的即释

35、放已占有的 所有资源。所有资源。 采用资源顺序分配法，破坏采用资源顺序分配法，破坏“环路等待环路等待”条件。条件。 将系统中的所有资源按类型线性排队，并赋予唯将系统中的所有资源按类型线性排队，并赋予唯一编号，进程申请资源时，严格按编号递增顺序分配。一编号，进程申请资源时，严格按编号递增顺序分配。预防死锁预防死锁操作系统调度与死锁3.7 死锁的基本概念死锁的基本概念（七）（七） 1）系统的安全状态）系统的安全状态 在分配资源时，分析计算系统的在分配资源时，分析计算系统的安全性安全性，避免系统，避免系统进入不安全状态，则可避免死锁。进入不安全状态，则可避免死锁。系统状态安全系统状态安全系统状态安全

36、系统状态安全存在一个进程序列存在一个进程序列 P1，P2，。，。Pn ，如果系统按此，如果系统按此顺序为每个进程分配它们所需的最大资源，而不造成顺序为每个进程分配它们所需的最大资源，而不造成死锁，则称系统状态死锁，则称系统状态S（t）安全。）安全。2 2）银行家算法）银行家算法 银行家算法是著名的银行家算法是著名的避免死锁的避免死锁的算法。其基本思算法。其基本思想是：想是： O SO S 银行家银行家 进程进程 借贷的客户借贷的客户 资源资源 可周转的借贷资金可周转的借贷资金避免死锁避免死锁操作系统调度与死锁解除死锁解除死锁解除死锁解除死锁 一旦检测到死锁，应立即消除，常用的方法有：一旦检测到

37、死锁，应立即消除，常用的方法有：一旦检测到死锁，应立即消除，常用的方法有：一旦检测到死锁，应立即消除，常用的方法有： 1 1、撤消进程法、撤消进程法、撤消进程法、撤消进程法 逐个撤消所有死锁进程，直到解除死锁为止。逐个撤消所有死锁进程，直到解除死锁为止。逐个撤消所有死锁进程，直到解除死锁为止。逐个撤消所有死锁进程，直到解除死锁为止。 撤消进程的策略：撤消进程的策略：撤消进程的策略：撤消进程的策略： 按优先级；按优先级；按优先级；按优先级； 最小代价原则最小代价原则最小代价原则最小代价原则撤消进程数最少、撤消路径最短。撤消进程数最少、撤消路径最短。撤消进程数最少、撤消路径最短。撤消进程数最少、撤消路径最短。2 2、挂起进程法挂起进程法挂起进程法挂起进程法 使用挂起使用挂起使用挂起使用挂起/ / / /激活机构挂起一些进程，剥夺它们所占有的激活机构挂起一些进程，剥夺它们所占有的激活机构挂起一些进程，剥夺它们所占有的激活机构挂起一些进程，剥夺它们所占有的资源以解除死锁。资源以解除死锁。资源以解除死锁。资源以解除死锁。问题问题 在解决死锁的几种方法中，你认为哪种方法既能够在解决死锁的几种方法中，你认为哪种方法既能够解决死锁问题，对系统效率牺牲也不大？解决死锁问题，对系统效率牺牲也不大？操作系统调度与死锁