操作系统第三章调度与死锁ppt课件

1、第三章 进程调度是实现多道程序系统的关键，直接影响到操作系统的性能，是本章讨论的主要问题。3.1 调度的根本概念调度的根本概念 (一一 作业从进入系统到完成，能够要阅历三级调度过程：作业从进入系统到完成，能够要阅历三级调度过程：1、高级调度、高级调度 又称为作业调度，它决议将哪些在外存上处于又称为作业调度，它决议将哪些在外存上处于后备形状的作业调入主机内存，预备执行。因此，有时把它后备形状的作业调入主机内存，预备执行。因此，有时把它称为接纳调度。称为接纳调度。2、低级调度、低级调度 又称为进程调度，它决议就绪队列中哪个进程又称为进程调度，它决议就绪队列中哪个进程将获得处置机，并实践执行将处置机

2、分配给进程的操作。执将获得处置机，并实践执行将处置机分配给进程的操作。执行分配处置机的程序称为分派程序。行分配处置机的程序称为分派程序。3、中级调度、中级调度 中级调度的主要作用是在内存和外存之间进展中级调度的主要作用是在内存和外存之间进展进程交换，以处理内存紧张的问题。如它将内存中处于等待进程交换，以处理内存紧张的问题。如它将内存中处于等待形状的某些进程调至外存对换区，以腾出内存空间，而将外形状的某些进程调至外存对换区，以腾出内存空间，而将外存对换区上已具备运转条件的进程重新调入内存，预备运转存对换区上已具备运转条件的进程重新调入内存，预备运转。故又称为交换调度。故又称为交换调度。 阻塞形状

3、就绪就绪形状形状执行执行形状形状调度调度I/O恳求恳求进程进程释放释放时间时间片到片到后备作业队列后备作业队列CPU就绪队列就绪队列内存内存外存外存阻塞队列阻塞队列作业调度作业调度等待事件等待事件中级调度中级调度即交换调度即交换调度交换文件交换文件就绪队列就绪队列阻塞队列阻塞队列三级调度的模型三级调度的模型3.1 调度的根本概念调度的根本概念 (三三作业调度是确定哪些作业可以被调入内存。作业调度是确定哪些作业可以被调入内存。进程调度是确定哪个进程可以占有进程调度是确定哪个进程可以占有CPUCPU并执行。并执行。作业调度是进程调度的根底，作业被调入内存后，作业调度是进程调度的根底，作业被调入内存

4、后，是以进程的方式执行的。是以进程的方式执行的。在一个在一个OSOS中进程调度与作业调度的算法是一致的。中进程调度与作业调度的算法是一致的。？问题？问题？各级调度间的关系各级调度间的关系3.1 调度的根本概念调度的根本概念 (四四 作业步作业步 将一个作业划分为假设干个顺序处置的步骤，将一个作业划分为假设干个顺序处置的步骤，作作 业步相互独立又相互关联。业步相互独立又相互关联。 作业作业 是用户恳求计算机系统执行的一次独立的上机任是用户恳求计算机系统执行的一次独立的上机任 务，是可以共享公共资源区域的一族有关进程家族。务，是可以共享公共资源区域的一族有关进程家族。 从静态观念看，作业由从静态观

5、念看，作业由 控制命令系列、程序集、数据控制命令系列、程序集、数据 集三部分构成。集三部分构成。补充：关于作业的概念补充：关于作业的概念作业控制块作业控制块 JCBJob Control Block用于描画作业。用于描画作业。 定义为记录类型作业名、优先级、建立时间、形状外定义为记录类型作业名、优先级、建立时间、形状外 存地址、大小等。存地址、大小等。 作业形状作业形状 作业在其生命期中，共有四种形状：作业在其生命期中，共有四种形状：关于作业的形状关于作业的形状 作业形状作业形状 作业在其生命期中，共有四种形状：作业在其生命期中，共有四种形状： 进入、后备、运转、完成进入、后备、运转、完成完成

6、完成执行执行就绪就绪阻塞阻塞进入进入后备后备运转运转提交提交作业作业调度调度完成完成问题：引起进程调度的缘由有哪些？问题：引起进程调度的缘由有哪些？3.1 调度的根本概念调度的根本概念 (五五 非抢占式非剥夺式非抢占式非剥夺式 进程进程 一旦被调度一旦被调度 ，就不断占有，就不断占有CPUCPU，直到完成或，直到完成或因发生某事件而被阻塞因发生某事件而被阻塞I/OI/O恳求。恳求。 抢占式剥夺式抢占式剥夺式 进程未执行完，可由调度程序剥夺其进程未执行完，可由调度程序剥夺其CPUCPU，另分配，另分配给别的进程。给别的进程。 抢占的缘由有：优先级、时间片、短进程等。抢占的缘由有：优先级、时间片、

7、短进程等。在在OSOS中，进程调度的方式分为两类。中，进程调度的方式分为两类。3.1 调度的根本概念调度的根本概念 (六六 记录系统中一切进程的执行情况记录系统中一切进程的执行情况 确定分配处置机的原那么调度算法确定分配处置机的原那么调度算法 分配处置机给进程分配处置机给进程 回收处置机、进展进程上下文切换回收处置机、进展进程上下文切换显然，进程调度的中心问题是调度算法。显然，进程调度的中心问题是调度算法。3.1 调度的根本概念调度的根本概念 (七七 1。周转时间短。周转时间短 周转时间周转时间TTTumaround Time 对作业对作业从作业提交到完成。从作业提交到完成。 对进程对进程第一

8、次进入就绪队列到运转终了。第一次进入就绪队列到运转终了。 平均周转时间平均周转时间ATTAverage Tumaround Time ATT= Ti 带权平均带权平均 W= 其中：其中： Ti 各进程的各进程的TT Tri 实践执行时间实践执行时间2. 2. 呼应时间快呼应时间快 呼应时间呼应时间RTRTResponse TimeResponse Time输入键盘命输入键盘命令到屏幕显示结果。令到屏幕显示结果。四四. 调度算法准那么调度算法准那么 调度算法应该尽能够提高资源利用率，减少调度算法应该尽能够提高资源利用率，减少CPU空闲空闲时间时间,公平效力。可从以下方面思索：公平效力。可从以下方

9、面思索：1ni=1nTiTrii=1n1 n3.2 3.2 调度算法调度算法 一一 先来先效力FCFS算法 最短CPU运转期优先SCBF算法 最高优先权HPF算法 时间片轮转RR算法 多级反响队列算法思索题思索题 1、各种调度算法的特点、性能如何？适宜于、各种调度算法的特点、性能如何？适宜于 哪类哪类 OS？ 2。最高优先权算法中，动态优先权有何实践。最高优先权算法中，动态优先权有何实践意义？意义？3.2 3.2 调度算法调度算法 二二 一一. .、先来先效力、先来先效力FCFSFCFS算法算法 FCFSFirst Come First Server 法，又称为先法，又称为先进先出进先出FIF

10、O算法，就绪进程按照进入的先后次序陈算法，就绪进程按照进入的先后次序陈列，调度程序总是选择队首的进程执行。列，调度程序总是选择队首的进程执行。 这是一种非剥夺式的调度算法，简单、易实现。这是一种非剥夺式的调度算法，简单、易实现。 对短进程易出现等待时间长，效力质量差。对短进程易出现等待时间长，效力质量差。 该算法有利于该算法有利于CPU忙碌型的进程，不利于忙碌型的进程，不利于I/O忙碌型的进忙碌型的进 程。程。1n 该算法只能用于辅助算法。该算法只能用于辅助算法。3.2 3.2 调度算法调度算法 二二二、二、 最短最短CPUCPU运转期优先运转期优先SCBFSCBF算法算法n+1nnt 该算法

11、优于该算法优于FCFS，但出息程等待时间长，估算误差较大。，但出息程等待时间长，估算误差较大。 SCBFShortest CPU Burst First ，即调度程序总，即调度程序总是选择是选择CPU运转时间最短的进程执行。运转时间最短的进程执行。其中其中 为估计的第为估计的第n个个CPU 周期。周期。tn 为实践值。为实践值。 为控制值，为控制值，0 1，常取，常取 0.5n 对最短对最短CPU运转期的估算，依赖于系统的下一个运转期的估算，依赖于系统的下一个CPU周周期中，实现较困难。进程的期中，实现较困难。进程的CPU时间时间 的估算公式：的估算公式：n+13.2 3.2 调度算法调度算法

12、 三三 三、三、 最高优先权最高优先权HPFHPF算法算法 调度程序每次都将调度程序每次都将CPU分配给就绪队列中具有最高优先级分配给就绪队列中具有最高优先级Highest Priority的进程。该算法的中心是优先级确实定。的进程。该算法的中心是优先级确实定。 调度方式分为剥夺调度方式分为剥夺式和非剥夺式。式和非剥夺式。 静态优先级静态优先级 在创建进程时根据进程的特性或者用户要求赋予，在进在创建进程时根据进程的特性或者用户要求赋予，在进程的整个生命期中不能改动。程的整个生命期中不能改动。 简单、易实现，但是调度性能不高，优先级低的进程能简单、易实现，但是调度性能不高，优先级低的进程能够长期

13、等待。够长期等待。 动态优先级动态优先级 在创建进程时为进程赋予一个根本优先级，在进程的执在创建进程时为进程赋予一个根本优先级，在进程的执行过程中可随进程的特性动态改动。行过程中可随进程的特性动态改动。 引起优先级改动的缘由：引起优先级改动的缘由： 进程等待进程等待CPU时间长短，执行所需时间长短，执行所需CPU时间长短等。时间长短等。 分两类优先级：分两类优先级：3.2 3.2 调度算法调度算法 四四三、最高优先权三、最高优先权HPFHPF算法算法确定进程优先级的普通原那么：确定进程优先级的普通原那么： 1. 进程的类型进程的类型 例如：例如： 系统进程高于用户进程；系统进程高于用户进程；

14、前台进程高于后台进程；前台进程高于后台进程； 实时进程高于普通进程。实时进程高于普通进程。 2. 对资源的需求量及类型对资源的需求量及类型 占用占用CPU时间少的，运用内存资源少的进程优时间少的，运用内存资源少的进程优先级高。先级高。 3. 按作业到达系统的时间顺序按作业到达系统的时间顺序 4. 按用户类型和要求按用户类型和要求 3.2 3.2 调度算法调度算法 五五 四、四、 时间片轮转时间片轮转RRRR算法算法 该算法主要用于分时系统，按照公平效力的原那么，该算法主要用于分时系统，按照公平效力的原那么，为进程分配为进程分配CPU时间片。是一种剥夺式的算法。时间片。是一种剥夺式的算法。 轮转

15、法的关键是时间片的选取：轮转法的关键是时间片的选取： 时间片太大，那么轮转法蜕化为时间片太大，那么轮转法蜕化为FCFS法。法。 时间片太小，那么添加时间片太小，那么添加CPU的额外开销。的额外开销。 影响时间片设置的主要要素：影响时间片设置的主要要素： 系统呼应时间系统呼应时间R、就绪进程数、就绪进程数N、计算机处置才干等。、计算机处置才干等。 时间片长度：时间片长度： q = R / N max3.2 3.2 调度算法调度算法 六六 五、高呼应比优先调度算法五、高呼应比优先调度算法HRNHRN HRNHighest Response ratio Next算法将短进算法将短进程优先与动态优先级

16、相结合。所谓高呼应是指进程获得程优先与动态优先级相结合。所谓高呼应是指进程获得调度的呼应，即优先数调度的呼应，即优先数R。 R =W+T/T = 1+W/T T 估计进程执行的时间。估计进程执行的时间。 W 进程等待的时间。进程等待的时间。 随着进程等待时间的添加，优先权动态添加。随着进程等待时间的添加，优先权动态添加。 对等待一样时间的短进程比出息程优先权添加得多。对等待一样时间的短进程比出息程优先权添加得多。 出息程随着等待时间添加也会被调度。出息程随着等待时间添加也会被调度。3.2 3.2 调度算法调度算法 七七 六、多级队列调度六、多级队列调度 根据作业性质不同分为假设干个就绪队列，根

17、据作业性质不同分为假设干个就绪队列，如：系统进程队列，交互进程队列，批处置队如：系统进程队列，交互进程队列，批处置队列等。对各队列采用不同的调度算法。列等。对各队列采用不同的调度算法。3.2 3.2 调度算法调度算法 八八 亦称多级反响轮转法亦称多级反响轮转法Round Robin with Multiple FeedbackRound Robin with Multiple Feedback实现根本思想：实现根本思想：1 1。按优先级分别设置。按优先级分别设置N N个就绪队列，优先级愈高的队列分配个就绪队列，优先级愈高的队列分配 的时间片愈小。的时间片愈小。2 2。系统总是先调度当前优先级最

18、高的队列中的进程，只需当。系统总是先调度当前优先级最高的队列中的进程，只需当 最高优先级队列为空时，才去调度低一优先级队列中的进最高优先级队列为空时，才去调度低一优先级队列中的进 程。程。3 3。进程被调度后，假设未执行完时间片到，那么优先级降低，进。进程被调度后，假设未执行完时间片到，那么优先级降低，进 程排入相应优先级队列的队尾。程排入相应优先级队列的队尾。4 4。同一优先级队列，按照。同一优先级队列，按照FCFSFCFS算法调度。算法调度。 多级反响队列是一种综合调度算法，对进程就绪队列进行动态调度和管理。七、多级反响队列七、多级反响队列3.2 3.2 调度算法调度算法 九九七、多级反响

19、队列七、多级反响队列3.3 3.3 进程调度实例进程调度实例 ( (一一一。一。VMSVMS进程调度进程调度 综合调度算法：以优先级为根底的多级反响队列。综合调度算法：以优先级为根底的多级反响队列。 VMS VMS中的优先级：中的优先级： 1 1。硬件优先级。硬件优先级IPLIPL中断优先级，存储在硬件中断优先级，存储在硬件PCBPCB中。中。 2 2。软件优先级。软件优先级 0 310 31级存储在软件级存储在软件PCBPCB中。中。 1631 1631 实时优先级静态优先级，用于实时实时优先级静态优先级，用于实时进程。进程。 不受时间片影响，进程一旦被调度，不受时间片影响，进程一旦被调度，

20、不断执行不断执行 到到 终了。终了。 0 15 0 15 正常优先级正常优先级 动态优先级，用于非实动态优先级，用于非实时进程，时进程， 为每个优先级队列设置不同的为每个优先级队列设置不同的 时间时间片。优先级片。优先级 愈高，时间片愈短。愈高，时间片愈短。 系统中的进程按照优先级排成系统中的进程按照优先级排成32个就绪队列，系统个就绪队列，系统总是按总是按FCFS算法先调度当前优先级最高的队列中的算法先调度当前优先级最高的队列中的进程。对实时进程。对实时 进程和正常进程采用不同的调度战略。进程和正常进程采用不同的调度战略。3.3 3.3 进程调度实例进程调度实例 ( (二二 正常优先级进程正

21、常优先级进程0 15在创建时，系统为其分配了在创建时，系统为其分配了 根本优先级：根本优先级： 交互进程为交互进程为4，批处置进程为，批处置进程为3。 优先级提升幅度的原那么：优先级提升幅度的原那么： 随着进程等待时间添加，优先级提升幅度添加。随着进程等待时间添加，优先级提升幅度添加。 因进程类型而定；受因进程类型而定；受 I/O 限制的进程提升幅度大于受限制的进程提升幅度大于受计算限制的进程。计算限制的进程。VMSVMS中进程优先级的动态提升中进程优先级的动态提升 在进程运转过程中，优先级会有不同幅度在进程运转过程中，优先级会有不同幅度0 6的提的提 升，使进程获得调度的能够性。升，使进程获

22、得调度的能够性。进程优先级下降进程优先级下降 ：当进程由于时间片到或者等待某事：当进程由于时间片到或者等待某事件发生而释放件发生而释放CPU时，优先级下降。时，优先级下降。优先级改动后的进程排到相应队列的队尾优先级改动后的进程排到相应队列的队尾 。优先级队列优先级队列31301516140静态优先级静态优先级动态优先级动态优先级CPU等等待待队队列列优优先先级级下下降降进程按照优先级排成进程按照优先级排成32个就绪队列。个就绪队列。每个就绪队列按照每个就绪队列按照FCFS算法排队。算法排队。优先级越高时间片越小。优先级越高时间片越小。3.3 3.3 进程调度实例进程调度实例 ( (三三 进程的

23、优先权分进程的优先权分31级级1 - 31，为动态优先级：在根，为动态优先级：在根本优先级的根底上动摇本优先级的根底上动摇 + 2级。级。 根本优先权设置根本优先权设置4组组 优先权等级优先权等级 优先权范围优先权范围 Idle 闲置闲置 1 6 Normal 规范规范 6 10 High 高级高级 11 15 Realtime实时实时 16 31 进程调度过程中优先权的动态提升有何实践意义？进程调度过程中优先权的动态提升有何实践意义？WINDOWS NT 的进程优先级的进程优先级问问 题题3.5 3.5 线程的根本概念线程的根本概念 一一 为了减少进程并发执行的开销，提高系统性能。将为了减少

24、进程并发执行的开销，提高系统性能。将资源分配与调度分开资源分配与调度分开引入线程。引入线程。3.5 3.5 线程的根本概念线程的根本概念 二二线程线程1 1的的TCBTCB线程线程2 2的的TCBTCB线程线程3 3的的TCBTCBTCBCPU 形状形状堆栈堆栈程序计数器程序计数器 . . .存放器存放器PCB进程标识进程标识资源清单资源清单 . . .TCB输入线程输入线程 主线程主线程 计算线程计算线程 输出线程输出线程 图图1图图2主线程主线程 创建线程创建线程 1 。 创建线程创建线程 n图图32. 线程线程 的并发性的并发性 同一进程同一进程 的多个线程具有并发执行的特性，线程之间的

25、多个线程具有并发执行的特性，线程之间相互约束，线程执行过程呈现延续性。线程也具有就绪、相互约束，线程执行过程呈现延续性。线程也具有就绪、 阻塞和执行三种根本形状。阻塞和执行三种根本形状。3. 线程资源 线程可以与其它同属一个进程的线程共同拥有该进程的资源。3.5 3.5 线程的根本概念线程的根本概念 三三4. 4. 线程的调度线程的调度 线程作为调度的根本单位，在线程作为调度的根本单位，在windows NT windows NT 等等3232位位OSOS 中，采用按优先级调度的战略。中，采用按优先级调度的战略。 线程的调度算法与进程类似，对线程的调度算法与进程类似，对CPUCPU的分配也分抢

26、的分配也分抢占占 式和非抢占式。式和非抢占式。3.5 3.5 线程的根本概念线程的根本概念 四四3.7 3.7 死锁的根本概念一死锁的根本概念一1、争夺资源引起死锁 例1：P1，P2两个进程争夺打印机和读卡机。P1P2打印机读卡机 P1曾经恳求到打印机， 又恳求读卡机。 P2曾经恳求到读卡机， 又恳求打印机。打印机和读卡机为打印机和读卡机为非剥夺性资源。非剥夺性资源。例例3 3、 P1 P1，P2P2，P3 P3 三个进程之间通讯：三个进程之间通讯： P1 P1产生音讯产生音讯S1S1，接纳，接纳P3P3产生的音讯产生的音讯S3S3； P2 P2产生音讯产生音讯S2S2，接纳，接纳P1P1产生

27、的音讯产生的音讯S1S1； P3 P3产生音讯产生音讯S3S3，接纳，接纳P2P2产生的音讯产生的音讯S2S2；按以下次序运转：按以下次序运转：P1：RequestS3；ReleaseS1P2：RequestS1；ReleaseS2P3：RequestS2；ReleaseS3P1P3P2S2S3S1P1P2P3按照以上的顺序执行会产生死锁吗？按照以上的顺序执行会产生死锁吗？问题？例例2 2、 在消费者在消费者消费者问题中假设交换两个消费者问题中假设交换两个P P操作操作 的次序，能够引起死锁。的次序，能够引起死锁。SiSi暂时性资暂时性资源源3.7 死锁的根本概念三死锁的根本概念三消费者进程：

28、消费者进程： 消费一个产品消费一个产品 m ； . . . Pempty； Pmutex； 将产品将产品 m放入缓冲区；放入缓冲区； in ：=in +1 mod n ； V mutex； V full； 消费者进程： P full； P mutex ； 从缓冲区取产品m； out ：=out+1 mod n ； V mutex； V empty；消费者消费者消费者问题算法：消费者问题算法：3.7 死锁的根本概念四死锁的根本概念四 由于由于 产生死锁的根本缘由是争夺共享资源，从而得产生死锁的根本缘由是争夺共享资源，从而得到产生死锁的必要条件是：到产生死锁的必要条件是： 互斥条件互斥条件 进程互

29、斥运用临界资源。进程互斥运用临界资源。 不剥夺条件不剥夺条件 资源只能由占有它的进程释放，不能资源只能由占有它的进程释放，不能 被其它进程剥夺。被其它进程剥夺。 非剥夺资源非剥夺资源 部分分配条件部分分配条件 进程在恳求新资源的同时，坚持对某进程在恳求新资源的同时，坚持对某 些资源的占有。些资源的占有。 环路等待条件环路等待条件 存在循环等待链，在链中每个进程都存在循环等待链，在链中每个进程都 在等待它的前一进程所持有的资源。在等待它的前一进程所持有的资源。3.7 死锁的根本概念五死锁的根本概念五 显然，假设出现死锁将对操作系统呵斥极大的危害，显然，假设出现死锁将对操作系统呵斥极大的危害，甚至使系统瘫痪，如何处理死锁是操作系统设计的重要甚至使系统瘫痪，如何处理死锁是操作系统设计的重要问题。问题。 限制并发进程对于资源的限制并发进程对于资源的需求，破坏产生死需求，破坏产生死 锁的必锁的必要条件。严厉限制死锁的要条件。严厉限制死锁的发生。发生。三。处理死锁的方法预防死锁预防死锁防止死锁防止死锁在资源的动