精品课件教案ppt 第三章 处理机调度与死锁

计算机操作系统 第三章 处理机调度与死锁 第三章第三章 处理机调度与死锁处理机调度与死锁 计算机操作系统 第三章 处理机调度与死锁 3.1 3.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 3.1.1 高级、中级和低级调度高级、中级和低级调度 1. 1. 高级调度高级调度(High Scheduling) (High Scheduling) 又称作业调度、长程调度：决定把外存上处于后备又称作业调度、长程调度：决定把外存上处于后备 队列中的哪些作业调入内存，并为之创建进程、分配必队列中的哪些作业调入内存，并为之创建进程、分配必 要的资源，然后，再将新创建的进程排在就绪队列中。要的资源，然后，再将新创建的进程排在就绪队列中。 计算机操作系统 第三章 处理机调度与死锁 1. 1. 高级调度高级调度(High Scheduling) (High Scheduling) 批处理系统：需作业调度批处理系统：需作业调度 分时系统：无需作业调度分时系统：无需作业调度 实时系统：通常无需作业调度实时系统：通常无需作业调度 计算机操作系统 第三章 处理机调度与死锁 在每次执行作业调度时，都须做出以下两个决定：在每次执行作业调度时，都须做出以下两个决定： 1) 1) 接纳多少个作业接纳多少个作业 2) 2) 接纳哪些作业接纳哪些作业 1. 1. 高级调度高级调度(High Scheduling) (High Scheduling) 计算机操作系统 第三章 处理机调度与死锁 2. 2. 低级调度低级调度(Low Level Scheduling) (Low Level Scheduling) 进程调度、短程调度：决定就绪队列中哪个进程应进程调度、短程调度：决定就绪队列中哪个进程应 获得处理机，然后再由分派程序执行把处理机分配给该获得处理机，然后再由分派程序执行把处理机分配给该 进程的具体操作。进程的具体操作。 三种类型的三种类型的OSOS均需配置进程调度均需配置进程调度 计算机操作系统 第三章 处理机调度与死锁 2. 2. 低级调度低级调度(Low Level Scheduling) (Low Level Scheduling) 进程调度方式：进程调度方式： 1) 1) 非抢占方式非抢占方式(Non-preemptive Mode)(Non-preemptive Mode) 进程一旦获得进程一旦获得CPUCPU则一直执行，直至完成或被阻塞。则一直执行，直至完成或被阻塞。 采用非抢占方式，引起进程调度的因素：采用非抢占方式，引起进程调度的因素： 正在执行的进程执行完毕，正在执行的进程执行完毕， 或因发生某事件而不能或因发生某事件而不能 再继续执行；再继续执行； 执行中的进程因提出执行中的进程因提出I/OI/O请求而暂停执行；请求而暂停执行； 在进程通信或同步过程中执行了某种原语操作，如在进程通信或同步过程中执行了某种原语操作，如 P P操作操作(wait(wait操作操作) )、BlockBlock原语、原语、WakeupWakeup原语等。原语等。 计算机操作系统 第三章 处理机调度与死锁 2) 2) 抢占方式抢占方式(Preemptive Mode)(Preemptive Mode) 正在执行的进程可以被中途剥夺正在执行的进程可以被中途剥夺CPUCPU使用权使用权 进程调度方式进程调度方式 抢占的原则有：抢占的原则有： (1)(1) 优优先权原则。先权原则。 (2) (2) 短作业短作业( (进程进程) )优先原则优先原则 (3) (3) 时间片原则。时间片原则。 计算机操作系统 第三章 处理机调度与死锁 3. 3. 中级调度中级调度(Intermediate-Level Scheduling) (Intermediate-Level Scheduling) 中级调度又称中程调度中级调度又称中程调度(Medium-Term Scheduling)(Medium-Term Scheduling)。 引入的主要目的：是为了提高内存利用率和系统吞吐引入的主要目的：是为了提高内存利用率和系统吞吐 量（存储器管理的对换）量（存储器管理的对换） 中程调度：将那些暂时不能运行的进程不再占用宝贵中程调度：将那些暂时不能运行的进程不再占用宝贵 的内存资源，而将它们调至外存上去等待，把此时的进程的内存资源，而将它们调至外存上去等待，把此时的进程 状态称为就绪驻外存状态或挂起状态。当这些进程重又具状态称为就绪驻外存状态或挂起状态。当这些进程重又具 备运行条件、且内存又稍有空闲时，由中级调度来决定把备运行条件、且内存又稍有空闲时，由中级调度来决定把 外存上的哪些又具备运行条件的就绪进程，重新调入内存外存上的哪些又具备运行条件的就绪进程，重新调入内存 ，并修改其状态为就绪状态，挂在就绪队列上等待进程调，并修改其状态为就绪状态，挂在就绪队列上等待进程调 度。度。 计算机操作系统 第三章 处理机调度与死锁 3.1.2 3.1.2 调度队列模型调度队列模型 1. 1. 仅有进程调度的调度队列模型仅有进程调度的调度队列模型 计算机操作系统 第三章 处理机调度与死锁 2. 2. 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 计算机操作系统 第三章 处理机调度与死锁 (1) (1) 就绪队列的形式：优先权队列、无序链表等就绪队列的形式：优先权队列、无序链表等 (2) (2) 设置多个阻塞队列：每个队列对应于某一种进程阻塞设置多个阻塞队列：每个队列对应于某一种进程阻塞 事件事件 该模型与上一模型的主要区别在于如下两个方面：该模型与上一模型的主要区别在于如下两个方面： 2. 2. 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 计算机操作系统 第三章 处理机调度与死锁 3. 3. 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 计算机操作系统 第三章 处理机调度与死锁 3.1.3 3.1.3 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则 1. 1. 面向用户的准则面向用户的准则 (1) (1) 周转时间短。周转时间短。 周转时间的长短是评价批处理系统性能、选择作业调周转时间的长短是评价批处理系统性能、选择作业调 度方式与算法的重要准则之一度方式与算法的重要准则之一 计算机操作系统 第三章 处理机调度与死锁 周转时间：从作业提交给系统开始，到作业完成为之周转时间：从作业提交给系统开始，到作业完成为之 的这段时间间隔（作业周转时间）的这段时间间隔（作业周转时间） 作业在外存后备队列上等待（作业）调度的时间作业在外存后备队列上等待（作业）调度的时间 进程在就绪队列上等待进程调度的时间进程在就绪队列上等待进程调度的时间 进程在进程在CPUCPU上执行的时间上执行的时间 进程等待进程等待I/OI/O操作完成的时间操作完成的时间 (1) (1) 周转时间短。周转时间短。 计算机操作系统 第三章 处理机调度与死锁 平均周转时间：平均周转时间： 带权带权周转时间：周转时间： WW= =T/TT/T S S 平均带权周转时间平均带权周转时间: : (1) (1) 周转时间短。周转时间短。 计算机操作系统 第三章 处理机调度与死锁 (2) (2) 响应时间快响应时间快 响应时间的长短是评价分时系统性能、选择分时系响应时间的长短是评价分时系统性能、选择分时系 统中进程调度算法的重要准则之一统中进程调度算法的重要准则之一 响应时间：用户通过键盘提交一个请求开始，直至响应时间：用户通过键盘提交一个请求开始，直至 系统首次产生响应为止的时间，或者说直至屏幕上显示系统首次产生响应为止的时间，或者说直至屏幕上显示 出结果为止的一段时间间隔出结果为止的一段时间间隔 键盘输入的请求信息传送到处理机的时间键盘输入的请求信息传送到处理机的时间 处理机对请求信息进行处理的时间处理机对请求信息进行处理的时间 形成的响应信息回送到终端显示器的时间形成的响应信息回送到终端显示器的时间 计算机操作系统 第三章 处理机调度与死锁 (3) (3) 截止时间的保证截止时间的保证 截止时间是评价实时系统性能的重要指标，是选择截止时间是评价实时系统性能的重要指标，是选择 实时调度算法的重要准则实时调度算法的重要准则 截止时间：某任务必须开始执行的最迟时间或必须截止时间：某任务必须开始执行的最迟时间或必须 完成的最迟时间完成的最迟时间 计算机操作系统 第三章 处理机调度与死锁 (4) (4) 优先权准则优先权准则 三种系统均可应用本准则三种系统均可应用本准则 计算机操作系统 第三章 处理机调度与死锁 2. 2. 面向系统的准则面向系统的准则 (1) (1) 系统吞吐量高系统吞吐量高 评价批处理系统评价批处理系统 吞吐量：单位时间内所完成的作业数吞吐量：单位时间内所完成的作业数 (2) (2) 处理机利用率好处理机利用率好 大中型系统中要考虑大中型系统中要考虑 (3) (3) 各类资源的平衡利用各类资源的平衡利用 大中型系统中要考虑大中型系统中要考虑 计算机操作系统 第三章 处理机调度与死锁 3.2 3.2 调度算法调度算法 调度算法：根据系统的资源分配策略所规定的资源分配调度算法：根据系统的资源分配策略所规定的资源分配 算法算法 计算机操作系统 第三章 处理机调度与死锁 3.2.1 3.2.1 先来先服务和短作业先来先服务和短作业( (进程进程) )优先调度算法优先调度算法 1. 1. 先来先服务（先来先服务（FCFSFCFS）调度算法）调度算法 特点：可用于作业调度、也可用于进程调度特点：可用于作业调度、也可用于进程调度 利于长作业（进程）、不利于短作业（进程）利于长作业（进程）、不利于短作业（进程） 利于利于CPUCPU繁忙型作业，不利于繁忙型作业，不利于I/OI/O繁忙型的作业繁忙型的作业( ( 进程进程) ) FCFSFCFS实例实例 1. 1. 先来先服务调度算法先来先服务调度算法 平均周转平均周转 时间：时间： 平均带权平均带权 周转时间周转时间 计算机操作系统 第三章 处理机调度与死锁 2. 2. 短作业短作业( (进程进程) )优先调度算法优先调度算法 短作业优先短作业优先(SJF)(SJF)调度算法：从后备队列中选择一调度算法：从后备队列中选择一 个或若干个估计运行时间最短的作业，将它们调入内个或若干个估计运行时间最短的作业，将它们调入内 存运行。存运行。 短进程优先短进程优先(SPF)(SPF)调度算法：从就绪队列中选出一调度算法：从就绪队列中选出一 估计运行时间最短的进程，将处理机分配给它，使它估计运行时间最短的进程，将处理机分配给它，使它 立即执行并一直执行到完成，或发生某事件而被阻塞立即执行并一直执行到完成，或发生某事件而被阻塞 放弃处理机时，再重新调度。放弃处理机时，再重新调度。 平均周转时间：平均周转时间： 带权带权周转时间：周转时间： WW= =T/TT/T S S 平均带权周转时间平均带权周转时间: : 计算机操作系统 第三章 处理机调度与死锁 优点：有效的降低作业的平均等待时间，提高了系统优点：有效的降低作业的平均等待时间，提高了系统 的吞吐量。的吞吐量。 缺点：对长作业不利缺点：对长作业不利 完全未考虑作业的紧迫程度完全未考虑作业的紧迫程度 作业的运行时间不能准确获得作业的运行时间不能准确获得 2. 2. 短作业短作业( (进程进程) )优先调度算法优先调度算法 计算机操作系统 第三章 处理机调度与死锁 3.2.2 3.2.2 高优先权优先调度算法高优先权优先调度算法 1. 1. 优先权调度算法的类型优先权调度算法的类型 非抢占式优先权算法非抢占式优先权算法 主要用于批处理系统中；也可用于某些对实时性要求主要用于批处理系统中；也可用于某些对实时性要求 不严的实时系统中。不严的实时系统中。 计算机操作系统 第三章 处理机调度与死锁 这种抢占式的优先权调度算法，能更好地满足紧这种抢占式的优先权调度算法，能更好地满足紧 迫作业的要求，故而常用于要求比较严格的实时系统迫作业的要求，故而常用于要求比较严格的实时系统 中，中， 以及对性能要求较高的批处理和分时系统中。以及对性能要求较高的批处理和分时系统中。 1. 1. 优先权调度算法的类型优先权调度算法的类型 2) 2) 抢占式优先权调度算法抢占式优先权调度算法 计算机操作系统 第三章 处理机调度与死锁 2. 2. 优先权的类型优先权的类型 静态优先权是在创建进程时确定的，且在进程的整个静态优先权是在创建进程时确定的，且在进程的整个 运行期间保持不变。运行期间保持不变。 1) 1) 静态优先权静态优先权 计算机操作系统 第三章 处理机调度与死锁 确定进程优先权的依据有如下三个方面：确定进程优先权的依据有如下三个方面： (1) (1) 进程类型。进程类型。 (2) (2) 进程对资源的需求。进程对资源的需求。 (3) (3) 用户要求。用户要求。 1) 1) 静态优先权静态优先权 计算机操作系统 第三章 处理机调度与死锁 动态优先权是指，在创建进程时所赋予的优先权，动态优先权是指，在创建进程时所赋予的优先权， 是可以随进程的推进或随其等待时间的增加而改变的，是可以随进程的推进或随其等待时间的增加而改变的， 以便获得更好的调度性能。以便获得更好的调度性能。 2) 2) 动态优先权动态优先权 计算机操作系统 第三章 处理机调度与死锁 3. 3. 高响应比优先调度算法高响应比优先调度算法 优先权的变化规律可描述为：优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作由于等待时间与服务时间之和，就是系统对该作 业的响应时间，故该优先权又相当于响应比业的响应时间，故该优先权又相当于响应比R R P P 。据此，据此， 又可表示为：又可表示为： 计算机操作系统 第三章 处理机调度与死锁 (1) (1) 等待时间相同，则要求服务的时间愈短，其优等待时间相同，则要求服务的时间愈短，其优 先权愈高先权愈高有利于短作业有利于短作业 (2) (2) 当要求服务的时间相同时，则等待时间愈长，当要求服务的时间相同时，则等待时间愈长， 其优先权愈高其优先权愈高先来先服务先来先服务 (3) (3) 长作业只要等待时间足够长，其优先级便可升长作业只要等待时间足够长，其优先级便可升 到很高，到很高， 从而也可获得处理机从而也可获得处理机 (4) (4) 响应比的计算增加了系统开销响应比的计算增加了系统开销 3. 3. 高响应比优先调度算法高响应比优先调度算法 例：例： 单单单单道批道批处处处处理系理系统统统统中，一中，一组组组组作作业业业业的提交的提交时时时时刻和运行刻和运行时时时时 间间间间如表所示。采用高响如表所示。采用高响应应应应比比优优优优先先调调调调度算法度算法 表表1 1 作作业业业业提交提交时时时时刻和运行刻和运行时间时间时间时间 作作业业业业提交提交时时时时刻刻运行运行时间时间时间时间 1 1 8.08.01.01.0 2 2 8.58.50.50.5 3 3 9.09.00.20.2 4 4 9.19.10.10.1 作作业业业业1 1到达到达时时时时，没有其它作，没有其它作业业业业到达，故作到达，故作业业业业1 1执执执执行行 表表2 2 作作业业业业 执执执执行行 次序次序 提交提交 时时时时刻刻 运行运行 时间时间时间时间 等待等待 时间时间时间时间 开始开始 时时时时刻刻 完成完成 时时时时刻刻 周周转转转转 时间时间时间时间 带权带权带权带权 周周转转转转 时间时间时间时间 1 1 8.08.01.01.0 0 0 8.08.09.09.01.01.01.01.0 3 3 9.09.00.20.20.60.69.69.69.89.80.80.84.04.0 作作业业业业1 1执执执执行完成行完成时时时时刻刻为为为为9.09.0，作，作业业业业2 2、3 3均已到达，此均已到达，此 时时时时作作业业业业2 2、3 3的响的响应应应应比分比分别别别别是：作是：作业业业业2=1+0.5/0.5=22=1+0.5/0.5=2； 作作业业业业3=1+0/0.2=13=1+0/0.2=1；即；即选择选择选择选择 2 2运行运行 2 2 8.58.50.50.50.50.59.09.09.59.51.01.02.02.0 作作业业业业2 2执执执执行完成行完成时时时时刻刻为为为为9.59.5，作，作业业业业3 3、4 4均已到达，其均已到达，其 响响应应应应比分比分别别别别是：作是：作业业业业3=1+0.5/0.2=3.5 3=1+0.5/0.2=3.5 作作业业业业 4=1+0.4/0.1=54=1+0.4/0.1=5，即，即选择选择选择选择 作作业业业业4 4运行。运行。 4 4 9.19.10.10.10.40.49.59.59.69.60.50.55.05.0 最后只剩下作最后只剩下作业业业业3 3，执执执执行行 计算机操作系统 第三章 处理机调度与死锁 3.2.3 3.2.3 基于时间片的轮转调度算法基于时间片的轮转调度算法 时间片太大，每个进程均可在时间片内执行完毕时间片太大，每个进程均可在时间片内执行完毕 退化为退化为FCFSFCFS 1. 时间片轮转法 确定时间片大小的考虑因素：确定时间片大小的考虑因素： 1 1、系统对响应时间的要求、系统对响应时间的要求 2 2、就绪队列中进程的数目、就绪队列中进程的数目 3 3、系统的处理能力、系统的处理能力 计算机操作系统 第三章 处理机调度与死锁 2. 多级反馈队列调度算法 (1) (1) 应设置多个就绪队列应设置多个就绪队列 优先级优先级 计算机操作系统 第三章 处理机调度与死锁 (2) (2) 当一个新进程进入内存后，首先将它放入第一当一个新进程进入内存后，首先将它放入第一 队列的末尾，按时间片轮转法等待调度。当轮到该进程队列的末尾，按时间片轮转法等待调度。当轮到该进程 执行时，如它能在该时间片内完成，便可准备撤离系统执行时，如它能在该时间片内完成，便可准备撤离系统 ；如果它在一个时间片结束时尚未完成，调度程序便将；如果它在一个时间片结束时尚未完成，调度程序便将 该进程转入第二队列的末尾，再同样地按时间片轮转法该进程转入第二队列的末尾，再同样地按时间片轮转法 等待调度执行；如果它在第二队列中运行一个时间片后等待调度执行；如果它在第二队列中运行一个时间片后 仍未完成，再依次将它放入第三队列，仍未完成，再依次将它放入第三队列，如此下去，如此下去 ，当一个长作业，当一个长作业( (进程进程) )从第一队列依次降到第从第一队列依次降到第n n队列后队列后 ，在第，在第n n队列中便采取按时间片轮转的方式运行。队列中便采取按时间片轮转的方式运行。 2. 2. 多级反馈队列调度算法多级反馈队列调度算法 计算机操作系统 第三章 处理机调度与死锁 (3) (3) 仅当第一队列空闲时，调度程序才调度第二队列仅当第一队列空闲时，调度程序才调度第二队列 中的进程运行；中的进程运行； 仅当第仅当第1(i-1) 1(i-1) 队列均空时，才会调度队列均空时，才会调度 第第i i队列中的进程运行。如果处理机正在第队列中的进程运行。如果处理机正在第i i队列中为某队列中为某 进程服务时，又有新进程进入优先权较高的队列进程服务时，又有新进程进入优先权较高的队列( (第第1(i1(i -1)-1)中的任何一个队列中的任何一个队列) )，则此时新进程将抢占正在运行，则此时新进程将抢占正在运行 进程的处理机，即由调度程序把正在运行的进程放回到进程的处理机，即由调度程序把正在运行的进程放回到 第第i i队列的末尾，把处理机分配给新到的高优先权进程队列的末尾，把处理机分配给新到的高优先权进程 。 2. 2. 多级反馈队列调度算法多级反馈队列调度算法 计算机操作系统 第三章 处理机调度与死锁 3. 3. 多级反馈队列调度算法的性能多级反馈队列调度算法的性能 (1) (1) 终端型作业用户。终端型作业用户。 (2) (2) 短批处理作业用户。短批处理作业用户。 (3) (3) 长批处理作业用户。长批处理作业用户。 计算机操作系统 第三章 处理机调度与死锁 3.3 3.3 实时调度实时调度 实时系统实时系统 能及时响应外部事件的请求，在规定的时间内完能及时响应外部事件的请求，在规定的时间内完 成对该事件的处理，并控制所有实时任务协调一致地成对该事件的处理，并控制所有实时任务协调一致地 运行的计算机系统运行的计算机系统 分为实时控制系统和实时信息处理系统两类分为实时控制系统和实时信息处理系统两类 实时任务实时任务 周期性实时任务、非周期实时任务周期性实时任务、非周期实时任务 硬实时任务、软实时任务硬实时任务、软实时任务 计算机操作系统 第三章 处理机调度与死锁 3.3 3.3 实时调度实时调度 3.3.1 3.3.1 实现实时调度的基本条件实现实时调度的基本条件 1. 1. 提供必要的信息提供必要的信息 (1) (1) 就绪时间。就绪时间。 (2) (2) 开始截止时间和完成截止时间。开始截止时间和完成截止时间。 (3) (3) 处理时间。处理时间。 (4) (4) 资源要求。资源要求。 (5) (5) 优先级。优先级。 计算机操作系统 第三章 处理机调度与死锁 2. 2. 系统处理能力强系统处理能力强 假定系统中有假定系统中有mm个周期性的硬实时任务，它们的处个周期性的硬实时任务，它们的处 理时间为理时间为CiCi，周期时间为周期时间为PiPi，则在单处理机情况下，必则在单处理机情况下，必 须满足下面的限制条件：须满足下面的限制条件： 3.3.1 3.3.1 实现实时调度的基本条件实现实时调度的基本条件 计算机操作系统 第三章 处理机调度与死锁 提高系统处理能力的途径有二：提高系统处理能力的途径有二： 其一仍是采用单处理机系统，其一仍是采用单处理机系统， 但须增强其处理能力但须增强其处理能力 ， 以显著地减少对每一个任务的处理时间以显著地减少对每一个任务的处理时间 其二是采用多处理机系统。假定系统中的处理机数其二是采用多处理机系统。假定系统中的处理机数 为为N N，则应将上述的限制条件改为：则应将上述的限制条件改为： 2. 2. 系统处理能力强系统处理能力强 计算机操作系统 第三章 处理机调度与死锁 3. 3. 采用抢占式调度机制采用抢占式调度机制 抢占机制抢占机制 非抢占机制非抢占机制 3.3.1 3.3.1 实现实时调度的基本条件实现实时调度的基本条件 计算机操作系统 第三章 处理机调度与死锁 4. 4. 具有快速切换机制具有快速切换机制 该机制应具有如下两方面的能力：该机制应具有如下两方面的能力： (1) (1) 对外部中断的快速响应能力对外部中断的快速响应能力 (2) (2) 快速的任务分派能力快速的任务分派能力 3.3.1 3.3.1 实现实时调度的基本条件实现实时调度的基本条件 计算机操作系统 第三章 处理机调度与死锁 3.3.2 3.3.2 实时调度算法的分类实时调度算法的分类 1. 1. 非抢占式调度算法非抢占式调度算法 (1) (1) 非抢占式轮转调度算法非抢占式轮转调度算法 计算机操作系统 第三章 处理机调度与死锁 3.3.2 3.3.2 实时调度算法的分类实时调度算法的分类 1. 1. 非抢占式调度算法非抢占式调度算法 (2) (2) 非抢占式优先调度算法。非抢占式优先调度算法。 计算机操作系统 第三章 处理机调度与死锁 2. 2. 抢占式调度算法抢占式调度算法 (1) (1) 基于时钟中断的抢占式优先权调度算法基于时钟中断的抢占式优先权调度算法 3.3.2 3.3.2 实时调度算法的分类实时调度算法的分类 计算机操作系统 第三章 处理机调度与死锁 3.3.2 3.3.2 实时调度算法的分类实时调度算法的分类 (2) (2) 立即抢占立即抢占(Immediate Preemption)(Immediate Preemption)的优先权调度算法的优先权调度算法 2. 2. 抢占式调度算法抢占式调度算法 计算机操作系统 第三章 处理机调度与死锁 3.3.3 3.3.3 常用的几种实时调度算法常用的几种实时调度算法 1. 1. 最早截止时间优先即最早截止时间优先即EDF(Earliest Deadline First)EDF(Earliest Deadline First)算法算法 根据任务的开始截止时间来确定任务的优先级根据任务的开始截止时间来确定任务的优先级 即可用于抢占式调度、也可用于非抢占式调度即可用于抢占式调度、也可用于非抢占式调度 计算机操作系统 第三章 处理机调度与死锁 1. 1. 最早截止时间优先即最早截止时间优先即EDF(Earliest Deadline First)EDF(Earliest Deadline First)算法算法 计算机操作系统 第三章 处理机调度与死锁 1. 1. 最早截止时间优先即最早截止时间优先即EDF(Earliest Deadline First)EDF(Earliest Deadline First)算法算法 进进进进程程到达到达时间时间时间时间执执执执行行时间时间时间时间开始截至开始截至时间时间时间时间 A A 10102020110110 B B 202020202020 C C 404020205050 D D 505020209090 E E 606020207070 采用抢占式最早开始截至时间优先调度算法采用抢占式最早开始截至时间优先调度算法 0 0 1010 2020 3030 4040909070705050 60608080100100 110110 120120 A A B B C C E E D D A A 计算机操作系统 第三章 处理机调度与死锁 2. 2. 最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)LLF(Least Laxity First)算法算法 该算法是根据任务紧急该算法是根据任务紧急( (或松弛或松弛) )的程度，来确定任的程度，来确定任 务的优先级。任务的紧急程度愈高，为该任务所赋予的务的优先级。任务的紧急程度愈高，为该任务所赋予的 优先级就愈高，优先级就愈高， 以使之优先执行。以使之优先执行。 该算法主要用于可抢占调度方式中该算法主要用于可抢占调度方式中 2. 2. 最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)LLF(Least Laxity First)算法算法 周期性实时任务周期性实时任务A A、B B，A A要求每要求每20ms20ms执行一次，执行时执行一次，执行时 间间10ms10ms；B B要求每要求每50ms50ms执行一次，执行时间执行一次，执行时间25ms25ms 在刚开始时在刚开始时(t1=0)(t1=0)，A1A1必须在必须在20ms20ms时完成，而它本身运时完成，而它本身运 行又需行又需 10 ms10 ms，可算出可算出A1A1的松弛度为的松弛度为10ms10ms；B1B1必须在必须在50ms50ms 时完成，时完成， 而它本身运行就需而它本身运行就需25 ms25 ms，可算出可算出B1B1的松弛度为的松弛度为25 25 msms，故调度程序应先调度故调度程序应先调度A1A1执行。执行。 在在t2=10 mst2=10 ms时，时，A2A2的松弛度可按下式算出：的松弛度可按下式算出： A2A2的松弛度的松弛度= =必须完成时间必须完成时间- -其本身的运行时间其本身的运行时间- -当前时间当前时间 =40 ms-10 ms-10 ms=20 ms =40 ms-10 ms-10 ms=20 ms 类似地，可算出类似地，可算出B1B1的松弛度为的松弛度为15ms15ms 故调度程序应选择故调度程序应选择B1B1运行。运行。 在在t3=30 mst3=30 ms时，时，A2A2的松弛度为（的松弛度为（40-10-30)=0ms40-10-30)=0ms，而，而B1B1的松的松 弛度为弛度为15ms15ms。故抢占。故抢占B1B1处理机而调度处理机而调度A2A2运行运行 依次计算下去依次计算下去 计算机操作系统 第三章 处理机调度与死锁 3.4 3.4 多处理机系统中的调度多处理机系统中的调度 3.4.1 3.4.1 多处理器系统的类型多处理器系统的类型 (1) (1) 紧密耦合紧密耦合(Tightly Coupled) MPS(Tightly Coupled) MPS：共享主存储器：共享主存储器 系统和系统和I/OI/O设备设备 (2) (2) 松散耦合松散耦合(Loosely Coupled) MPS(Loosely Coupled) MPS：拥有独立的存：拥有独立的存 储器和储器和I/OI/O设备设备 计算机操作系统 第三章 处理机调度与死锁 (1) (1) 对称多处理器系统对称多处理器系统SMPS(Symmetric SMPS(Symmetric MultiProcessorMultiProcessor System)System) (2) (2) 非对称多处理器系统非对称多处理器系统 3.4.1 3.4.1 多处理器系统的类型多处理器系统的类型 计算机操作系统 第三章 处理机调度与死锁 3.4.2 3.4.2 进程分配方式进程分配方式 1. 1. 对称多处理器系统中的进程分配方式对称多处理器系统中的进程分配方式 在在SMPSMP系统中，所有的处理器都是相同的，因而可系统中，所有的处理器都是相同的，因而可 把所有的处理器作为一个处理器池把所有的处理器作为一个处理器池(Processor pool)(Processor pool)，由由 调度程序或基于处理器的请求，调度程序或基于处理器的请求， 将任何一个进程分配给将任何一个进程分配给 池中的任何一个处理器去处理。在进行进程分配时，可池中的任何一个处理器去处理。在进行进程分配时，可 采用以下两种方式之一。采用以下两种方式之一。 1) 1) 静态分配静态分配(Static Assignment)(Static Assignment)方式：忙闲不均方式：忙闲不均 2) 2) 动态分配动态分配(Dynamic Assignment)(Dynamic Assignment)方式方式 计算机操作系统 第三章 处理机调度与死锁 2. 2. 非对称非对称MPSMPS中的进程分配方式中的进程分配方式 对于非对称对于非对称MPSMPS， 其其OSOS大多采用主大多采用主从从(Master-(Master- Slave)Slave)式式OSOS， 即即OSOS的核心部分驻留在一台主机上的核心部分驻留在一台主机上(Master)(Master) ， 而从机而从机(Slave)(Slave)上只是用户程序，上只是用户程序， 进程调度只由主机执行进程调度只由主机执行 。 每当从机空闲时，每当从机空闲时， 便向主机发送一索求进程的信号，便向主机发送一索求进程的信号， 然然 后，后， 便等待主机为它分配进程。便等待主机为它分配进程。 在主机中保持有一个就绪在主机中保持有一个就绪 队列，队列， 只要就绪队列不空，只要就绪队列不空， 主机便从其队首摘下一进程分主机便从其队首摘下一进程分 配给请求的从机。从机接收到分配的进程后便运行该进程配给请求的从机。从机接收到分配的进程后便运行该进程 ， 该进程结束后从机又向主机发出请求。该进程结束后从机又向主机发出请求。 3.4.2 3.4.2 进程分配方式进程分配方式 计算机操作系统 第三章 处理机调度与死锁 3.4.3 3.4.3 进程进程( (线程线程) )调度方式调度方式 1. 1. 自调度自调度(Self-Scheduling)(Self-Scheduling)方式方式 1) 1) 自调度机制自调度机制 直接由单处理机环境下的调度方式演变而来的直接由单处理机环境下的调度方式演变而来的 维护一个公共的进程或线程就绪队列维护一个公共的进程或线程就绪队列 可采用在单处理机环境下所用的调度算法，如先来可采用在单处理机环境下所用的调度算法，如先来 先服务先服务( (FCFSFCFS) )调度算法、最高优先权优先调度算法、最高优先权优先(FPF)(FPF)调度算调度算 法和抢占式最高优先权优先调度算法等。法和抢占式最高优先权优先调度算法等。 计算机操作系统 第三章 处理机调度与死锁 2) 2) 自调度方式的优点自调度方式的优点 1 1、很容易将单处理机环境下的调度机制移植到多、很容易将单处理机环境下的调度机制移植到多 处理机系统中处理机系统中 2 2、不会出现处理机空闲的情况，也不会发生处理、不会出现处理机空闲的情况，也不会发生处理 器忙闲不均的现象器忙闲不均的现象有利于提高处理器的利用率。有利于提高处理器的利用率。 1. 自调度(Self-Scheduling)方式 计算机操作系统 第三章 处理机调度与死锁 3) 3) 自调度方式的缺点自调度方式的缺点 (1) (1) 瓶颈问题：共享就绪队列瓶颈问题：共享就绪队列 (2) (2) 低效性：高速缓存使用效率低低效性：高速缓存使用效率低 (3) (3) 线程切换频繁：合作型线程相互等待线程切换频繁：合作型线程相互等待 1. 自调度(Self-Scheduling)方式 计算机操作系统 第三章 处理机调度与死锁 2. 2. 成组调度成组调度(Gang Scheduling)(Gang Scheduling)方式方式 为解决自调度方式中线程被频繁切换的问题提出的为解决自调度方式中线程被频繁切换的问题提出的 计算机操作系统 第三章 处理机调度与死锁 2. 2. 成组调度成组调度(Gang Scheduling)(Gang Scheduling)方式方式 在成组调度时，为应用程序分配处理器时间的方式：在成组调度时，为应用程序分配处理器时间的方式： 1) 1) 面向所有应用程序平均分配处理器时间面向所有应用程序平均分配处理器时间 2) 2) 面向所有线程平均分配处理器时间面向所有线程平均分配处理器时间 计算机操作系统 第三章 处理机调度与死锁 2. 2. 成组调度成组调度(Gang Scheduling)(Gang Scheduling)方式方式 优点：优点： 相互合作型进程或线程，能并行执行，有效减少线相互合作型进程或线程，能并行执行，有效减少线 程（进程）阻塞的发生，从而减少线程切换，改善程（进程）阻塞的发生，从而减少线程切换，改善 系统性能系统性能 依次调度一组线程，显著减少调度频率，减小了调依次调度一组线程，显著减少调度频率，减小了调 度开销度开销 计算机操作系统 第三章 处理机调度与死锁 3. 3. 专用处理器分配专用处理器分配(Dedicated Processor (Dedicated Processor AssigementAssigement) )方式方式 在一个应用程序的执行期间，专门为该程序分配一在一个应用程序的执行期间，专门为该程序分配一 组处理器，每一个线程一个处理器。这组处理器仅供该组处理器，每一个线程一个处理器。这组处理器仅供该 应用程序专用，直至该应用程序完成应用程序专用，直至该应用程序完成 在同时加工的应用程序中，其线程数的总和，不应超在同时加工的应用程序中，其线程数的总和，不应超 过系统中处理机的数目过系统中处理机的数目 计算机操作系统 第三章 处理机调度与死锁 3.5 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 死锁：多个进程在运行过程中因争夺资源而造成的一种死锁：多个进程在运行过程中因争夺资源而造成的一种 僵局僵局 计算机操作系统 第三章 处理机调度与死锁 3.5.1 3.5.1 产生死锁的原因产生死锁的原因 1. 1. 竞争资源引起进程死锁竞争资源引起进程死锁 (1) (1) 可剥夺和非剥夺性资源可剥夺和非剥夺性资源 (2) (2) 竞争非剥夺性资源竞争非剥夺性资源 (3) (3) 竞争临时性资源竞争临时性资源 计算机操作系统 第三章 处理机调度与死锁 竞争非剥夺性资源竞争非剥夺性资源 1. 1. 竞争资源引起进程死锁竞争资源引起进程死锁 计算机操作系统 第三章 处理机调度与死锁 1. 1. 竞争资源引起进程死锁竞争资源引起进程死锁 竞争临时性资源竞争临时性资源 计算机操作系统 第三章 处理机调度与死锁 2. 2. 进程推进顺序不当引起死锁进程推进顺序不当引起死锁 1) 1) 进程推进顺序合法进程推进顺序合法 2) 2) 进程推进顺序非法进程推进顺序非法 计算机操作系统 第三章 处理机调度与死锁 3.5.2 3.5.2 产生死锁的必要条件产生死锁的必要条件 (1) (1) 互斥条件互斥条件 (2) (2) 请求和保持条件请求和保持条件 (3) (3) 不剥夺条件不剥夺条件 (4) (4) 环路等待条件环路等待条件 计算机操作系统 第三章 处理机调度与死锁 3.5.3 3.5.3 处理死锁的基本方法处理死锁的基本方法 (1) (1) 预防死锁。预防死锁。 (2) (2) 避免死锁。避免死锁。 (3) (3) 检测死锁。检测死锁。 (4) (4) 解除死锁。解除死锁。 计算机操作系统 第三章 处理机调度与死锁 3.6 3.6 预防死锁的方法预防死锁的方法 3.6.1 3.6.1 预防死锁预防死锁 (1) (1) 摒弃摒弃“ “请求和保持请求和保持” ”条件条件 资源分配方案：要么分配进程所需的所有资源，要么资源分配方案：要么分配进程所需的所有资源，要么 不分配资源不分配资源 优点：简单、易于实现、安全优点：简单、易于实现、安全 缺点：资源严重浪费、进程延迟执行缺点：资源严重浪费、进程延迟执行 计算机操作系统 第三章 处理机调度与死锁 3.6.1 3.6.1 预防死锁预防死锁 (2) (2) 摒弃摒弃“ “不剥夺不剥夺” ”条件条件 资源分配方案：需要时才请求资源，一旦不能资源分配方案：需要时才请求资源，一旦不能 获得需要的资源，则释放所有已保持的资源获得需要的资源，则释放所有已保持的资源 缺点：实现复杂、代价大缺点：实现复杂、代价大 延长了进程的周转时间延长了进程的周转时间 增加了系统开销，降低了系统吞吐量增加了系统开销，降低了系统吞吐量 计算机操作系统 第三章 处理机调度与死锁 3.6.1 3.6.1 预防死锁预防死锁 3. 3. 摒弃摒弃“ “环路等待环路等待” ”条件条件 将所有资源按类型进行线性排队，并赋予不同序号。将所有资源按类型进行线性排队，并赋予不同序号。 所有进程对资源的请求必须严格按照资源序号递增的次序所有进程对资源的请求必须严格按照资源序号递增的次序 提出。提出。 缺点：各类资源所分配的序号需相对稳定，从而限缺点：各类资源所分配的序号需相对稳定，从而限 制了新类型设备的增加制了新类型设备的增加 进程使用资源的顺序可能与系统规定的顺序不同进程使用资源的顺序可能与系统规定的顺序不同 限制了用户简单、自主的编程限制了用户简单、自主的编程 计算机操作系统 第三章 处理机调度与死锁 3.6.2 3.6.2 系统安全状态系统安全状态 1. 1. 安全状态安全状态 所谓安全状态，是指系统能按某种进程顺序所谓安全状态，是指系统能按某种进程顺序(P1, (P1, P2, P2, ，PnPn)( )(称称P1, P2, , P1, P2, , PnPn序列为安全序列序列为安全序列) )，来，来 为每个进程为每个进程PiPi分配其所需资源，直至满足每个进程对资分配其所需资源，直至满足每个进程对资 源的最大需求，使每个进程都可顺利地完成。如果系统源的最大需求，使每个进程都可顺利地完成。如果系统 无法找到这样一个安全序列，则称系统处于不安全状态无法找到这样一个安全序列，则称系统处于不安全状态 。 避免死锁的实质：在进行资源分配时，如何使系统避免死锁的实质：在进行资源分配时，如何使系统 不进入不安全状态。不进入不安全状态。 计算机操作系统 第三章 处理机调度与死锁 系统中有三个进程系统中有三个进程P1P1、 P2P2和和P3P3，共有共有1212台磁带机台磁带机 。进程。进程P1P1总共要求总共要求1010台磁带机，台磁带机，P2P2和和P3P3分别要求分别要求4 4台和台和9 9 台。假设在台。假设在T0T0时刻，进程时刻，进程P1P1、P2P2和和P3P3已分别获得已分别获得5 5台、台、 2 2台和台和2 2台磁带机，尚有台磁带机，尚有3 3台空闲未分配，如下表所示：台空闲未分配，如下表所示： 进 程 最 大 需 求 已 分 配 可 用 P1 P2 P3 10 4 9 5 2 2 3 2. 2. 安全状态之例安全状态之例 计算机操作系统 第三章 处理机调度与死锁 如果不按照安全序列分配资源，则系统可能会由安全如果不按照安全序列分配资源，则系统可能会由安全 状态进入不安全状态。状态进入不安全状态。 3. 3. 由安全状态向不安全状态的转换由安全状态向不安全状态的转换 计算机操作系统 第三章 处理机调度与死锁 3.6.3 3.6.3 利用银行家算法避免死锁利用银行家算法避免死锁 1. 银行家算法中的数据结构 (1) (1) 可利用资源向量可利用资源向量AvailableAvailable 这是一个含有这是一个含有mm个元素的数组，其中的每一个元素个元素的数组，其中的每一个元素 代表一类可利用的资源数目，其初始值是系统中所配置代表一类可利用的资源数目，其初始值是系统中所配置 的该类全部可用资源的数目，其数值随该类资源的分配的该类全部可用资源的数目，其数值随该类资源的分配 和回收而动态地改变。如果和回收而动态地改变。如果AvailableAvailablej j=K=K，则表示则表示 系统中现有系统中现有RjRj类资源类资源KK个。个。 计算机操作系统 第三章 处理机调度与死锁 (2) (2) 最大需求矩阵最大需求矩阵MaxMax 这是一个这是一个nmnm的矩阵，它定义了系统中的矩阵，它定义了系统中n n个进程中的每个进程中的每 一个进程对一个进程对mm类资源的最大需求。如果类资源的最大需求。