处理机调度与死锁课件

1、处理机调度与死锁PPT课件处理机调度与死锁PPT课件调度策略考虑：周转时间 吞吐率响应时间 设备利用率研究的内容有：作业与进程的关系 作业调度策略与算法进程调度策略与算法 处理机调度10/6/20222第三章 处理机调度与死锁调度策略考虑：处理机调度10/2/20222第三章 处理机调第三章 处理机调度与死锁3.1 处理机调度的层次3.2 调度队列模型和调度准则3.3 调度算法3.4 实时调度3.5 产生死锁的原因和必要条件3.6 预防死锁的方法3.7 死锁的检测与解除10/6/20223第三章 处理机调度与死锁第三章 处理机调度与死锁3.1 处理机调度的层次10/2/2处理机调度与死锁课件处

2、理机调度与死锁课件作业的定义 作业：是指在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作。用户的观点：在一次业务处理过程中，从输入程序和数据到输出结果的全过程。系统的观点（针对作业进行资源分配）：作业由程序及数据（作业体）和作业说明书（作业控制语言）组成。批处理系统以作业为单位把程序和数据输入内存以便执行。 作业由不同的顺序相连的作业步组成。 作业步：是在一个作业的处理过程中，计算机所做的相对独立的工作。10/6/20226第三章 处理机调度与死锁作业的定义 作业：是指在一次应用业务处理过程中，从输入开始到 每个作业步运行的结果产生下一个作业步所需

3、要的文件。 一个作业步能否正确地执行，依赖于前一个作业步是否成功地完成。作业步之间的关系10/6/20227第三章 处理机调度与死锁 每个作业步运行的结果产生下一个作业步所需要的文件。作业步之作业组织 作业由程序、数据和作业说明书三部分组成。 程序和数据完成用户所要求的业务处理工作。 作业说明书则体现用户的控制意图。 用批处理控制方式组织的作业，在作业进入系统之前，程序员除了要准备好源程序和初始数据外，还必须用作业控制语言来书写一份作业控制说明书，系统通过作业说明书控制文件形式的程序和数据，使之执行和操作。 在批处理系统中，把一批作业依次放置在相应的输入设备上，在操作系统的控制下，依次将它们输

4、入辅助存储器中，这样就形成了一个作业流，也称输入流。 10/6/20228第三章 处理机调度与死锁作业组织 作业由程序、数据和作业说明书三部分组成。10/2/作业说明书 作业说明书包括作业基本情况、作业控制、作业资源要求的描述；它体现用户的控制意图。如：预计运行时间、要求的资源情况、执行优先级等。作业基本情况描述：用户名、作业名、编程语言、最大处理时间等；作业控制描述：作业控制方式、作业步的操作顺序、作业执行出错处理等；作业资源要求描述：处理时间、优先级、内存空间、外设类型和数量、库函数或实用程序等；10/6/20229第三章 处理机调度与死锁作业说明书 作业说明书包括作业基本情况、作业控制、

5、作业资源要作业的建立 建立一个作业必须把该作业所包含的程序和数据输入到计算机的外部辅助存储设备上，而且还要由作业注册程序在系统中为该作业申请建立起一个相应的作业控制块。即作业的建立过程包括两个子过程： 作业的输入； 作业控制块的建立。10/6/202210第三章 处理机调度与死锁作业的建立 建立一个作业必须把该作业所包含的程序和数据输入到JCB 的建立 在系统把作业信息输入到外存输入井之后，还需要根据作业说明书中的说明及其它信息建立作业控制块(JCB)。只有在获得JCB表项和足够的输入井空间之后，一个作业才可能创建成功。 JCB是作业存在的唯一标志。作业进入系统时，则为之建立JCB，当作业退出

6、系统时，则其JCB也被撤消。10/6/202211第三章 处理机调度与死锁JCB 的建立 在系统把作业信息输入到外存输入井之后，还需要作业控制块 内容：作业名、作业类型、资源要求、当前状态、资源使用情况以及该作业的优先级等。 作业类型：计算型（要求CPU时间多）、管理型（要求输入/输出量大）和图形设计型（要求高速图形显示）等。 资源要求：该作业估计执行时间、要求最迟完成时间、要求的内存量和外存量、要求的外设类型及台数以及要求的软件支持工具库函数等。10/6/202212第三章 处理机调度与死锁作业控制块 内容：作业名、作业类型、资源要求、当前状态、资源 资源使用情况：作业进入系统时间、开始执行

7、时间、已执行时间、内存地址、外设台数等。作业进入系统时间：指作业的全部信息进入输入井，作业的状态成为后备状态的时间。开始执行时间：指该作业被调度程序选中，其状态由后备状态变为执行状态的时间。内存地址：指分配给该作业的内存区起始地址。外设台数：指分配给该作业的外设实际台数。 优先级：用来决定该作业的调度次序。可以由用户给定，也可以由系统动态计算产生作业名作业类型资源要求资源使用情况 优先级当前状态其它作业控制块10/6/202213第三章 处理机调度与死锁 资源使用情况：作业进入系统时间、开始执行时间、已执行时间、作业的状态作业从提交给系统直到它完成后离开系统前的整个活动过程，要经历四种不同状态

8、：提交状态：一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态后备状态（收容状态）：输入管理系统不断地将作业输入到外存对应部分（或称输入井），如果一个作业的全部信息已全部输入到输入井，在它还没有被调度去执行前，该作业处于后备状态。运行状态：作业一旦被作业调度程序选中而被送入主存中投入运行，作业就处于执行状态。完成状态：作业运行完毕，但它所占用的资源尚未被系统全部回收时，该作业处于完成状态10/6/202214第三章 处理机调度与死锁作业的状态作业从提交给系统直到它完成后离开系统前的整个活动过作业状态及其转换数据提交状态完成状态后备状态执行状态作业控制进程 输入设备数据源程序输出设备作

9、业说明书输入井运行等待就绪输出井输入程序作业调度10/6/202215第三章 处理机调度与死锁作业状态及其转换数据提交状态完成状态后备状态执行状态作业控制作业是用户向计算机提交任务的任务实体。进程是计算机为了完成用户任务实体而设置的执行实体。计算机要完成一个任务实体，必须要有一个以上的执行实体，因此一个作业总是由一个以上的多个进程组成。作业与进程的关系10/6/202216第三章 处理机调度与死锁作业是用户向计算机提交任务的任务实体。作业与进程的关系10/作业、作业步、进程的关系用户作业作业步进程作业步进程线程线程由用户创建由用户指定由系统创建10/6/202217第三章 处理机调度与死锁作业

10、、作业步、进程的关系用户作业作业步进程作业步进程线程线程也称为作业调度、长程调度（Long-Term Scheduling）或宏观调度。根据某种算法对外存输入井上的大量后备作业进行选择调入内存，并为它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上，准备执行。 一般在批处理系统中有作业调度。而在分时系统中，为了及时响应，用户通过键盘输入的命令或数据都是直接送入内存，因此无需配置作业调度机制，实时系统亦然。高级调度10/6/202218第三章 处理机调度与死锁也称为作业调度、长程调度（Long-Term Schedul 高级调度执行作业调度时应决定：接纳多少个作业？ 接纳哪些作业？ 取

11、决于多道程序度。取决于所采用的调度算法，如先来先服务调度算法、短作业优先调度算法、最高响应比法等。10/6/202219第三章 处理机调度与死锁 高级调度取决于多道程序度。10/2/202219第三章 处作业调度功能 1: 记录系统中各作业的状况 2：按某种算法从后备队列中挑选一个或一批作业调入内存，让它们投入执行。 3：为被选中作业做好执行前的准备工作。 4：在作业执行结束时做善后处理工作10/6/202220第三章 处理机调度与死锁作业调度功能 1: 记录系统中各作业的状况10/2/202 按照某种调度算法从后备作业队列中选取作业。 为被选取的作业分配内存和外设资源（当系统为动态分配外设时

12、，作业所申请的外设只作为调度的参考因素）。因此要用到内存分配程序和外设分配程序。 为选中的作业建立相应的进程。 为作业开始运行做好一切准备工作。如构造和读写作业运行时所需要的有关表格及建立负责其运行控制的作业运行控制程序。 在作业运行完毕或运行过程中因某种原因需要撤离时，作业调度程序还要完成作业的善后处理工作，如输出作业管理信息（执行时间），收回分配给该作业的全部资源，撤销与该作业有关的全部进程和该作业的作业控制块等作业调度应完成如下几方面的工作10/6/202221第三章 处理机调度与死锁 按照某种调度算法从后备作业队列中选取作业。作业调度应完成作业从后备状态到执行状态后备作业队列空按调度算

13、法从作业中选出一作业调用存储、设备管理程序，审核资源要求资源要求能满足？放弃该作业否分配资源调用进程管理程序建立进程进程调度否是出口10/6/202222第三章 处理机调度与死锁作业从后备状态到执行状态后备作业队列空按调度算法从作调用存储作业从执行状态到完成状态撤销该作业的所有进程及作业的JCB调用存储管理，设备管理回收分配给该作业的全部资源调用会计程序，计算该作业的执行费用调度下一个作业10/6/202223第三章 处理机调度与死锁作业从执行状态到完成状态撤销该作业的所有进程及作业的JCB调作业调度目标与性能衡量1)调度目标 对所有作业应该是公平合理 应使设备有高的利用率 执行尽可能多的作业

14、 有快的响应时间10/6/202224第三章 处理机调度与死锁作业调度目标与性能衡量1)调度目标10/2/202224第2）在批处理系统中衡量作业调度算法优劣的性能量度周转时间 其中某一作业进入“输入井”的时间为Tsi ，它被选中执行，运行结束时的时间为Tei n 个作业平均周转时间为： 作业调度目标与性能衡量10/6/202225第三章 处理机调度与死锁2）在批处理系统中衡量作业调度算法优劣的性能量度作业调度目标作业调度目标与性能衡量 一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：一是等待时间；二为执行时间，即带权周转时间 平均带权周转时间：10/6/202226第三章 处理

15、机调度与死锁作业调度目标与性能衡量 一个作业的周转时间说明了该作业在系统又称中程调度(Medium-Term Scheduling)、交换调度。引入中级调度的目的是为了提高内存的利用率和系统吞吐量。将目前不在运行态的进程，包括其数据，从内存交换到外存（此时进程的状态为挂起状态），将新进程的代码、数据、栈等交换入内存。中级调度10/6/202227第三章 处理机调度与死锁又称中程调度(Medium-Term Scheduling)也称微观调度、进程调度或短程调度（Short-Term Scheduling）。用来决定就绪队列中的哪个进程应获得处理机，再由分派程序执行把处理机分配给该进程的具体操作

16、。 从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态。由于低级调度算法的频繁使用，要求在实现时做到高效（算法不宜复杂）任何OS都必须配置进程调度。低级调度10/6/202228第三章 处理机调度与死锁也称微观调度、进程调度或短程调度（Short-Term Sc进程调度的两种方式非抢占式(Non-preemptive Mode)：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。抢占方式(Preemptive Mode)：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程

17、。抢占原则：优先权原则、短作业（进程）优先原则、时间片原则。10/6/202229第三章 处理机调度与死锁进程调度的两种方式非抢占式(Non-preemptive MWHAT：按什么原则分配CPU 调度算法WHEN：何时分配CPU 调度的时机HOW： 如何分配CPU CPU调度过程（进程的上下文切换）进程调度要解决的问题10/6/202230第三章 处理机调度与死锁WHAT：按什么原则分配CPU进程调度要解决的问题10/2/进程调度的功能1、记录系统中所有进程的执行情况 作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的PCB表中。并且将各进程的PCB表排成相

18、应的队列并进行动态队列转接。2、选择占有处理机的进程 进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。3、进行进程上下文切换 一个进程的执行是在其上下文中执行的。当正在执行的进程由于某种原因要让出处理机时，系统要做进程上下文切换，以使另一个进程得以执行。10/6/202231第三章 处理机调度与死锁进程调度的功能1、记录系统中所有进程的执行情况10/2/20 一个进程运行完毕，或因某种错误而终止运行 当一个进程在运行时变为等待状态（等待I/O） 分时系统中时间片到 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语） 在执行完系统调用，系统程序返回

19、用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户进程执行。 当有一个优先级更高的进程就绪（可抢占式） 例：新创建一个进程；一个等待进程变成就绪进程调度的时机10/6/202232第三章 处理机调度与死锁 一个进程运行完毕，或因某种错误而终止运行进程调度的时机10处理机调度的层次10/6/202233第三章 处理机调度与死锁处理机调度的层次10/2/202233第三章 处理机调度与死调度队列模型 仅有进程调度的调度队列模型主要适用于分时系统。CPU就 绪 队 列阻 塞 队 列时间片完进程调度等待事件进程完成交互用户事件出现FIFO 队列10/6/202234第三章 处理机调度与死锁调

20、度队列模型 仅有进程调度的调度队列模型主要适用于分时系统。 具有高级和低级调度的调度队列模型 适用于批处理操作系统 进程完成CPU就 绪 队 列阻 塞 队 列时间片完进程调度等待事件1作业调度事件1出现阻 塞 队 列等待事件n事件n出现后 备队 列调度队列模型优先权队列多个阻塞队列10/6/202235第三章 处理机调度与死锁 具有高级和低级调度的调度队列模型进程完成CPU就 绪 队调度队列模型 同时具有三级调度的调度队列模型10/6/202236第三章 处理机调度与死锁调度队列模型 同时具有三级调度的调度队列模型10/2/202选择调度方式和调度算法的准则面向用户的准则周转时间短（批处理系统

21、）响应时间快（分时系统） 响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。截止时间的保证（实时系统） 截止时间是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。优先权准则（批处理、分时和实时系统）10/6/202237第三章 处理机调度与死锁选择调度方式和调度算法的准则面向用户的准则10/2/2022选择调度方式和调度算法的准则面向系统的准则系统吞吐量高（批处理系统） 吞吐量指在单位时间内系统所完成的作业数。处理机利用率好各类资源的平衡利用公平 10/6/202238第三章 处理机调度与死锁选择调度方式和调度算法的准则面向系统的准则10/2/20223.3 调度

22、算法 现有的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。先来先服务调度算法(FCFS：First Come First Serve)应用范围与含义作业调度：选择一个或多个最先进入后备队列的作业，将它们调入内存，为它们分配资源、创建进程，并放入就绪队列。进程调度：按照进程就绪的先后次序来调度进程，为之分配处理机。当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。10/6/202239第三章 处理机调度与死锁3.3 调度算法 现有的多种调度算法中，有的算法适用于作业先来先服务调度算法 在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通

23、常等到当前作业或进程出让CPU。最简单的算法。 特点 比较有利于长作业，而不利于短作业。 有利于CPU繁忙的作业，而不利于I/O繁忙的作业。 例1：在单道环境下，某批处理系统有四道作业，已知它们的进入系统的时刻、估计运算时间如下：10/6/202240第三章 处理机调度与死锁先来先服务调度算法 在作业或进程唤醒后（如I/O完成），并不先来先服务调度算法作业进入时刻(h)运行时间(h)12348.008.509.009.502.000.500.100.20用FCFS算法计算作业的运行情况、平均周转时间和平均带权周转时间10/6/202241第三章 处理机调度与死锁先来先服务调度算法作业进入时刻(

24、h)运行时间(h)12348例1：作业进入时刻运行时间开始时刻完成时刻周转时间带权周转12348.008.509.009.502.000.500.100.208.0010.0010.5010.6010.0010.5010.6010.802.002.001.601.301.004.0016.006.50平均周转时间T1.725（h）平均带权周转时间W6.875（h）10/6/202242第三章 处理机调度与死锁例1：作业进入时刻运行时间开始时刻完成时刻周转时间带权周转1作业名 进入时间 运行时间（分） 需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D

25、 8:36 24 10 E 8:42 12 20 有用户空间100KB，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用FCFS算法例2：10/6/202243第三章 处理机调度与死锁作业名 进入时间 运行时间（分） 需内存量KB例2：10名装入内存时间开始时间结束时间周转时间带权周转时间A8:068:068:484242/42B8:188:489:186060/30D8:369:189:426666/24C9:189:4210:069696/24E9:1810:0610:189696/1215K60K10K15K100K作业名 进入时间 运行时间（分） 需内存量KB A 8

26、:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 1220T=72W=3.5510/6/202244第三章 处理机调度与死锁名装入内存时间开始时间结束时间周转时间带权周转时间A8:062 时间片轮转算法(RRRound Robin) 把CPU划分成若干时间片。 将系统中所有的就绪进程按照FCFS原则，排成一个队列。 每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。 在一个时间片结束时，发生时钟中断。 调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。

27、进程可以未使用完一个时间片，就出让CPU（如阻塞）。10/6/202245第三章 处理机调度与死锁2 时间片轮转算法(RRRound Robin) 把CP时间片长度的确定 时间片轮转策略特别适合于分时系统中使用 在轮转法中，时间片长度的选取非常重要，时间片长度的选择会直接影响系统开销和响应时间 过长退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。 过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，系统开销大。 最佳的时间片量值应能使分时用户得到好的响应时间10/6/202246第三章 处理机调度与死锁时间片长度的确定 时间片轮转策略特别适合于分时系统中使用10 时间片

28、长度 SR/Nmax R：响应时间 Nmax：最大进程数 时间片长度的影响因素： 就绪进程的数目：数目越多，时间片越小（当响应时间一定时） 系统的处理能力：通常应当让用户输入能在一个时间片内能处理完，否则会使响应时间，平均周转时间和平均带权周转时间延长。时间片长度的确定10/6/202247第三章 处理机调度与死锁 时间片长度 SR/Nmax 时间片长度的确定10/2设有5个任务A、B、C、D、E，它们几乎同时到达，预计它们的运行时间为10、6、2、4、8min。若采用时间片为2min的时间片轮转调度算法，则各个任务的执行情况是： 第一轮：（A、B、C、D、E） 10min第二轮：（A、B、D

29、、E） 8min第三轮：（A、B、E） 6min第四轮：（A、E） 4min第五轮：（A） 2min例：10/6/202248第三章 处理机调度与死锁设有5个任务A、B、C、D、E，它们几乎同时到达，预计它们的例：它们的周转时间为：TA30min，TB22min，TC6min，TD16min、TE28min所以进程的平均周转时间为：T（302261628）/520.4min从上面的计算中，可以看出A的周转时间最长，假设A第一轮从0分钟开始，则第二轮从10分钟开始，第三轮从18分钟开始，第四轮从24分钟开始，第五轮从28分钟开始，一共占用5轮的时间片。 10/6/202249第三章 处理机调度与

30、死锁例：它们的周转时间为：10/2/202249第三章 处理机调3 多级反馈轮转法(round robin with multiple feedback)系统中设置多个就绪队列每个就绪队列赋予不同的优先级和时间片，第一个队列的优先级最高，时间片最小，随着队列优先级的降低，时间片加大各个队列按照先进先出原则排队等待调度,第n级队列（最低一级）中的进程采用时间片轮转算法进行调度。一个新进程就绪后进入第一级队列末尾进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾当第一级队列空时，就去调

31、度第二级队列，如此类推当时间片到后，进程放弃CPU，回到下一级队列末尾10/6/202250第三章 处理机调度与死锁3 多级反馈轮转法系统中设置多个就绪队列10/2/202253 多级反馈轮转法(round robin with multiple feedback)就绪队列 1就绪队列 2就绪队列 3就绪队列 nS1S2S3至CPU至CPU至CPU至CPU时间片：S1S2a0时，享受服务队列中永远只有一个进程；SRR算法退化成FCFS算法；当ab=0时，SRR算法就是时间片轮转算法； 事实上，线性优先级调度策略是一种介于轮转法和FCFS方式之间的调度策略。10/6/202261第三章 处理机调

32、度与死锁线性优先级调度算法(SRR, Selfish Round 5 最短作业优先法(SJF, Shortest Job First) 又称为“短进程优先” ( SPJ，Shortest Process First)；这是对FCFS算法的改进，其目标是减少平均周转时间。 对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。10/6/202262第三章 处理机调度与死锁5 最短作业优先法(SJF, Shortest Job FSJF的特点优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量；缺点：对长作业非常不利，可能长时间得不

33、到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。10/6/202263第三章 处理机调度与死锁SJF的特点优点：10/2/202263第三章 处理机调度与作业名提交时间运行时间P110.1时0.3小时P210.3时0.5小时P310.5时0.4小时P410.6时0.3小时P510.7时0.2小时设有5道作业，它们的提交时间和运行时间如表 例110/6/202264第三章 处理机调度与死锁作业名提交时间运行时间P110.1时0.3小时P210.3时作业名提交时间运行时间开始运行时间完成时间P110.1时0.3小时10.1小时10.4小时P2

34、10.3时0.5小时10.4小时10.9小时P310.5时0.4小时11.4小时11.8小时P410.6时0.3小时11.1小时11.4小时P510.7时0.2小时10.9小时11.1小时执行的顺序为：P1-P2-P5-P4-P3T0.68小时 例110/6/202265第三章 处理机调度与死锁作业名提交时间运行时间开始运行时间完成时间P110.1时0.例2作业名 进入时间 运行时间（分） 需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20 有用户空间100KB，并规定作业相应程序装入内存连续区域，并不

35、能被移动，作业与进程均采用SJF算法10/6/202266第三章 处理机调度与死锁例2作业名 进入时间 运行时间（分） 需内存量KB10/作业名 进入时间 运行时间（分） 需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 1220名装入内存时间开始时间结束时间周转时间带权周转时间A8:068:068:484242/42D8:368:489:123636/24E9:129:129:244242/12B8:189:249:549696/30C9:429:5410:18108108/24T=64.8W=2.7415K6

36、0K10K15K100K10/6/202267第三章 处理机调度与死锁作业名 进入时间 运行时间（分） 需内存量KB名装入内存6 高响应比优先调度算法（HRN：Highest Response-Ratio Next）响应比R = 作业周转时间 / 作业执行时间 =（作业执行时间+作业等待时间） / 作业执行时间 = 1 +（作业等待时间 / 作业执行时间） = 1 + W/T是FCFS和SJF的折衷10/6/202268第三章 处理机调度与死锁6 高响应比优先调度算法响应比R = 作业周转时间 / 作业6 高响应比优先调度算法（HRN：Highest Response-Ratio Next）响

37、应比R = 1 +（作业等待时间 / 作业执行时间）如作业等待时间相同，则执行时间越短，响应比越高，有利于短作业。对于长作业，随等待时间增加，响应比增高，最后同样可获得处理机。如执行时间相同，等待时间越长，响应比越高，实现的是先来先服务。10/6/202269第三章 处理机调度与死锁6 高响应比优先调度算法响应比R = 1 +（作业等待时间 例作业名提交时间计算时间(小时)P18:002P28:301P39:000.25P49:300.5 设有4个作业P1、P2、P3、P4，它们到达时间和计算时间如表 10/6/202270第三章 处理机调度与死锁例作业名提交时间计算时间(小时)P18:002

38、P28:301若这四个作业在一台处理机上按单道方式运行，采用最高响应比优先调度算法，则第一次计算响应比在8：00，此时只有P1作业提交，其相应比Rp11；在作业P1结束后，第二次计算各作业的响应比为：Rp2(1.5+1)/12.5Rp3（1+0.25）/0.25 = 5Rp4（0.5+0.5）/0.52此时，选择作业P3调入内存，P3执行结束时，第三次计算剩余各作业的响应比为：Rp2（1.75+1）/12.75Rp4（0.75+0.5）/0.52.5此时，选择作业P2调入内存，P2执行结束时，调入P4。所以它们的调入内存顺序为：P1、P3、P2、P4。 例10/6/202271第三章 处理机调

39、度与死锁若这四个作业在一台处理机上按单道方式运行，采用最高响应比优先调度算法调度方式吞吐量响应时间系统开销对进程的影响FCFS非剥夺不定可能很高，尤其是进程执行时间变化很大时最小对倾向于I/O的进程不利SJF非剥夺高对短进程提供好的响应时间可能高对长进程不利HRN非剥夺高提供较好的响应时间可能高平衡性好RR剥夺时间片很小时，吞吐量可能很低对短进程提供好的响应时间低公平对待HPF剥夺高提供较好的响应时间可能高对长进程不利多级反馈队列剥夺不定不定可能高有利于倾向I/O的进程各种调度算法性能对比10/6/202272第三章 处理机调度与死锁调度算法调度方式吞吐量响应时间系统开销对进程的影响FCFS非

40、例题有一个多道批处理系统，作业调度采用“短作业优先”调度算法；进程调度采用“优先数抢占式”调度算法，且优先数越小优先级越高。若系统拥有打印机一台，采用静态方法分配，忽略系统的调度开销。现有如下作业序列到达系统： 作业名到达系统时间Cpu运行时间打印机需求优先数J114：0040min14J214：2030min02J314：3050min13J414：5020min05J515：0010min1110/6/202273第三章 处理机调度与死锁例题有一个多道批处理系统，作业调度采用“短作业优先”调度算法请给出作业运行结束的次序；作业的平均周转时间和平均带权周转时间是多少？（要有中间计算步骤） 1

41、0/6/202274第三章 处理机调度与死锁请给出作业运行结束的次序；10/2/202274第三章 处理补充习题在单CPU和两台输入输出设备（I1，I2）的多道程序设计环境下，同时投入3个作业Job1、Job2、Job3运行。这3个作业对CPU和输入输出设备的使用顺序和时间如下所示：Job1:I2(30ms); CPU(10ms); I1(30ms); CPU(10ms); I2(20ms)Job2:I1(20ms); CPU(20ms); I2(40ms); Job3:CPU(30ms); I1(20ms); CPU(10ms); I1(10ms) 假定CPU、I1、I2都能并行工作，Job

42、1优先级最高，Job2次之，Job3优先级最低，优先级高的作业可以抢占优先级低的作业的CPU但不抢占I1和I2。试求：1、3个作业从投入到完成分别需要的时间。2、从投入到完成的CPU利用率。3、输入输出设备利用率。10/6/202275第三章 处理机调度与死锁补充习题在单CPU和两台输入输出设备（I1，I2）的多道程序3.5 死锁问题 在多道程序系统中，多个进程并发运行，共享资源，从而提高了资源的利用率。但是若对资源的管理和使用不当，在一定条件下会导致系统发生一种随机性故障死锁。这时，若无外力协助，每个进程都不能继续执行下去。 在一些系统中，比如实时控制系统，系统一旦发生死锁将导致灾难性的后果

43、。10/6/202276第三章 处理机调度与死锁3.5 死锁问题 在多道程序系统中，多个进程并发运行，共享资资源的概念OS是计算机系统中资源的管理者，而进程是竞争资源的基本单位，故对系统中所有进程的资源分配工作，都由OS完成。研究资源分配时，我们必须搞清该资源是可以被几个进程同时使用，还是只能为一个进程使用，资源的不同使用性质正是引起系统死锁的原因。 10/6/202277第三章 处理机调度与死锁资源的概念OS是计算机系统中资源的管理者，而进程是竞争资源的根据资源性质：可剥夺（抢占）和不可剥夺（抢占）资源。可抢占资源指资源占有进程虽然需要使用该资源，但另一个进程却强行把资源从占有者进程处抢来。

44、不可抢占资源指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。资源的分类10/6/202278第三章 处理机调度与死锁根据资源性质：可剥夺（抢占）和不可剥夺（抢占）资源。资源的分资源CPU、主存、硬盘，该类资源可为几个进程共同使用（可抢占）打印机，读卡机，磁带驱动器，可为某个进程独享（不可抢占） 根据使用方式：共享资源和独占资源。 根据使用期限；永久资源和临时性资源。 永久资源：可顺序重复使用的资源，如所有的硬件资源和可再入的纯代码过程 临时性资源：由一个进程产生，被另外一个进程使用短暂时间之后便无用的资源，如在进程同步和通信中出现的消息、信号

45、和数据10/6/202279第三章 处理机调度与死锁资源CPU、主存、硬盘，该类资源可为几个进程共同使用（可抢占死锁举例例1：进程A：获得CD-ROM使用权，申请打印机进程B：获得打印机使用权，申请CD-ROM死锁：此时进程A、B均被阻塞，无法运行进程A进程B打印机CD-ROM10/6/202280第三章 处理机调度与死锁死锁举例例1：进程A进程B打印机CD-ROM10/2/202死锁举例例2： 在生产者-消费者问题中将生产者进程的两个P操作颠倒时会发生死锁。 将消费者进程的两个P操作颠倒时也会发生死锁。10/6/202281第三章 处理机调度与死锁死锁举例例2：10/2/202281第三章

46、处理机调度与死锁死锁的定义死锁Deadlock：是计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象（僵局），如无外力作用，这些进程将永远不能再向前推进。陷入死锁状态的进程称为死锁进程，所占用的资源或者需要它们进行某种合作的其它进程就会相继陷入死锁，最终可能导致整个系统处于瘫痪状态。 10/6/202282第三章 处理机调度与死锁死锁的定义死锁Deadlock：是计算机系统中多道程序并发执产生死锁的原因1 竞争资源。当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁；2 进程推进的顺序不当 。进程在运行过程中，请求

47、和释放资源的顺序不当，导致进程的死锁。 10/6/202283第三章 处理机调度与死锁产生死锁的原因1 竞争资源。当系统中供多个进程所共享的资源竞争资源 竞争不可剥夺资源R1R2P1P2 竞争临时性资源(进程通信)10/6/202284第三章 处理机调度与死锁竞争资源 竞争不可剥夺资源R1R2P1P2 竞争临时性资源(进程推进顺序不当引起死锁DP2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)曲线4将进入不安全区域（进程推进顺序非法）10/6/202285第三章 处理机调度与死锁进程推进顺序不当引起死

48、锁DP2Rel(R1)P2Rel(R2关于死锁的一些结论参与死锁的进程最少是两个 （两个以上进程才会出现死锁）参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至 导致系统崩溃。10/6/202286第三章 处理机调度与死锁关于死锁的一些结论参与死锁的进程最少是两个10/2/2022产生死锁的必要条件互斥条件：涉及的资源是非共享的。不剥夺条件：不能强行剥夺进程拥有的资源。请求和保持条件：进程在等待一新资源时继续占有已分配的资源。环路条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的

49、下一个进程所请求。R1R2P1P210/6/202287第三章 处理机调度与死锁产生死锁的必要条件R1R2P1P210/2/202287第三3.5.2 死锁的排除方法1 鸵鸟方法2 预防死锁3 避免死锁4 检测和解除死锁10/6/202288第三章 处理机调度与死锁3.5.2 死锁的排除方法1 鸵鸟方法10/2/202288核心思想：忽略死锁问题原因：死锁问题的发生是小概率事件策略分析方便性与正确性之间的选择平均情况与最坏情况的选择 以UNIX系统为例，它潜在地存在死锁，但它并不花功夫去检测和解除死锁，而是忽略不去理它。鸵鸟方法（置之不理）10/6/202289第三章 处理机调度与死锁核心思想

50、：忽略死锁问题鸵鸟方法（置之不理）10/2/2022 UNIX系统允许创建的进程总数是由进程表中包含的PCB个数决定的。如果由于进程表中已经无空闲的PCB而使创建子进程操作(FORK)失败，则执行FORK操作的程序可以等待一段时间之后再试。 假定UNIX系统有100个PCB项，10个进程正在运行，每个需要创建12个子进程。 在每个进程已经创建9个进程后，原来的10个进程和新创建的90个子进程已用完了进程表。这样，原来的10个进程现在都处于创建子进程的无限循环中死锁。出现这种情况的可能性是非常小的，但还是有可能发生的。一旦出现，只要忽略原进程已运行情况的现场，重新启动机器让它们重新运行即可。10

51、/6/202290第三章 处理机调度与死锁 UNIX系统允许创建的进程总数是由进程表中包含的PCB个数核心思想：对进程加以限制防止死锁发生 设计思路：设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。死锁预防(deadlock prevention) 具体解决方法 1、互斥条件：使用Spooling技术来管理设备 较易实现，广泛使用。 由于所施加的限制往往太严格，可能导致系统资源利用率和系统吞吐量的降低。10/6/202291第三章 处理机调度与死锁核心思想：对进程加以限制防止死锁发生死锁预防(deadloc 采用的策略：一个已经保持了某些资源的进程，当它再提出新的资源要求而

52、不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请。实现比较复杂，且要付出很大代价；此外，还因为反复地申请和释放资源，而使进程的执行无限地推迟，延长了周转时间，增加了系统的开销，降低了系统吞吐量。（例如打印机打印的结果不连续）2：防止“不剥夺”条件的出现10/6/202292第三章 处理机调度与死锁 采用的策略：一个已经保持了某些资源的进程，当它再提出新的资 系统要求任一进程必须预先申请它所需的全部资源，而且仅当该进程的全部资源要求能得到满足时，系统才能给予一次性分配，然后启动该进程运行，但是在分配时只要有一种资源不满足，系统就不会给进程分配资源。进程运行期间，不会再请求

53、新的资源，所以，再分配就不会发生（摒弃了部分分配）。特点：简单、易于实现且安全 资源严重浪费 进程延迟进行3:防止部分分配（摒弃请求和保持条件）10/6/202293第三章 处理机调度与死锁 系统要求任一进程必须预先申请它所需的全部资源，而且仅 采用资源顺序使用法，基本思想是：把系统中所有资源类型线性排队，并按递增规则赋予每类资源以唯一的编号。例如输入机1，打印机2，磁带机3，磁盘4等等。进程申请资源时，必须严格按资源编号的递增顺序进行，否则系统不予分配。优点：资源利用率和系统吞吐量与另两种方法相比有较明显的改善。缺点： 1 为系统中各种类型的资源所分配的序号必须相对稳定，这就限制了新设备类型

54、的增加 2 作业实际使用资源的顺序与系统规定的顺序不同而造成资源的浪费； 4：防止“环路等待”条件的出现10/6/202294第三章 处理机调度与死锁 采用资源顺序使用法，基本思想是：把系统中所有资源类型线性 不事先采取限制去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。（如银行家算法）避免死锁(deadlock avoidance)事先只需要较弱的限制条件，可获得较高的资源利用率和系统吞吐量。 实现较难。10/6/202295第三章 处理机调度与死锁 不事先采取限制去破坏产生死锁的条件，而是在资源的动态系统安全性和银行家算法银行家算法

55、的思路系统安全状态银行家算法10/6/202296第三章 处理机调度与死锁系统安全性和银行家算法银行家算法的思路10/2/202296银行家算法的思路【问题】一个银行家拥有一千万资金，有10家工厂筹建，且每家工厂需要200万方可建成。如何合理分配资金问题？10/6/202297第三章 处理机调度与死锁银行家算法的思路【问题】一个银行家拥有一千万资金，有10家工银行家算法的思路【分析】如果将一千万均分给10家，则每个工厂都无法建成，也不能还贷，也即这10家工厂将“死锁”。若给其中的三个工厂200万，另4家工厂100万，这样，虽然有3家工厂未开工，但有3家可以建成投产，这3家工厂获得的利润可以给银

56、行还贷，银行家再利用还贷的资金继续给其它工厂投入，直至最终10家工厂都建成投产。10/6/202298第三章 处理机调度与死锁银行家算法的思路【分析】如果将一千万均分给10家，则每个工厂银行家算法的思路银行家可以把一定数量的资金供多个用户使用，为保证资金的安全银行家规定四个条件：（1）当一个用户对资金的最大需求量不超过银行家现有资金时就可接纳该用户；（Request = Available ）（2）用户可以分期贷款，但贷款的总数不能超过最大需求量；（Request=Need）10/6/202299第三章 处理机调度与死锁银行家算法的思路银行家可以把一定数量的资金供多个用户使用，为银行家算法的思

57、路（3）当银行家现有的资金不能满足用户的尚需贷款数时，对用户的贷款可推迟支付，但总能在用户有限的时间里得到贷款；（不符合“安全性条件”暂时不给贷款）（4）当用户得到所需的全部资金后，一定能在有限的时间里归还所有的资金。10/6/2022100第三章 处理机调度与死锁银行家算法的思路（3）当银行家现有的资金不能满足用户的尚需贷死锁避免定义 在系统运行过程中，对进程提出的每一个（系统能够满足的）资源申请进行动态检查（安全性检查），并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。10/6/2022101第三章 处理机调度与死锁死锁避免定义10/2/2022101第

58、三章 处理机调度与死锁 安全状态：存在某种资源调度顺序，保证所有进程正常运行完成，则称该状态为安全状态 不安全状态：不存在可满足所有进程正常运行的资源调度顺序，则称该状态为不安全状态 虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质是如何使系统不进入不安全状态。安全与不安全都是对静态进行的评价安全状态10/6/2022102第三章 处理机调度与死锁 安全状态：存在某种资源调度顺序，保证所有进程正常运行完成，例：假定系统有三个进程P1、P2、P3，共有12台磁带机。进程P1总共要求10台磁

59、带机，P2和P3分别要求4台和九台。设在T0时刻，进程P1、P2和P3已经获得5台、2台和2台，还有3台空闲没有分配。进程最大需求已分配还需可用P110553P2422P3927在T0时刻，系统是安全的。因为存在一个安全序列安全状态举例10/6/2022103第三章 处理机调度与死锁例：假定系统有三个进程P1、P2、P3，共有12台磁带机。进 如果不按安全序列分配资源，则系统可能会由安全状态进入不安全状态。如在T0以后，P3要求1台磁带机，若系统分给它一台，则系统进入不安全状态。因为其余2台分给P2，P2完成后，只能释放4台，这既不能满足P1（5台），也不能满足P3（6台），将导致死锁。可见当

60、P3申请资源时，尽管系统中有资源也不能分给它。由安全状态向不安全状态的转换10/6/2022104第三章 处理机调度与死锁 如果不按安全序列分配资源，则系统可能会由安全状态进入系统进入不安全状态进程最大需求已分配还需可用P110552P2422P393610/6/2022105第三章 处理机调度与死锁系统进入不安全状态进程最大需求已分配还需可用P110552P银行家算法于1965年发表，该算法由Dijkstra提出。1、银行家算法中的数据结构可利用资源向量Available。它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目。如： 利用银行家算法避免死锁R1R2R352310/6