处理机调度与死锁课件

2019/5/28,第三章 处理机调度与死锁,1,第三章 处理机调度与死锁,在多道程序环境下，进程的数目往往多于处理器的数目，多个进程共享处理机资源就必然引起对处理机的竞争，这就要求操作系统采取一定的策略（调度算法），动态地将处理机分配给各个进程使之能够执行。 处理机调度算法对整个计算机系统的综合性能指标有重要影响,2019/5/28,第三章 处理机调度与死锁,2,调度策略考虑： 周转时间 吞吐率 响应时间 设备利用率 研究的内容有： 作业与进程的关系 作业调度策略与算法 进程调度策略与算法,处理机调度,2019/5/28,第三章 处理机调度与死锁,3,第三章 处理机调度与死锁,3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除,2019/5/28,第三章 处理机调度与死锁,4,可把处理机调度分成三个层次： 高级调度 中级调度 低级调度,3.1 处理机调度的层次,2019/5/28,第三章 处理机调度与死锁,5,作业的定义,2019/5/28,第三章 处理机调度与死锁,6,作业的定义,作业：是指在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作。 用户的观点：在一次业务处理过程中，从输入程序和数据到输出结果的全过程。 系统的观点（针对作业进行资源分配）：作业由程序及数据（作业体）和作业说明书（作业控制语言）组成。批处理系统以作业为单位把程序和数据输入内存以便执行。 作业由不同的顺序相连的作业步组成。 作业步：是在一个作业的处理过程中，计算机所做的相对独立的工作。,2019/5/28,第三章 处理机调度与死锁,7,每个作业步运行的结果产生下一个作业步所需要的文件。 一个作业步能否正确地执行，依赖于前一个作业步是否成功地完成。,作业步之间的关系,2019/5/28,第三章 处理机调度与死锁,8,作业组织,作业由程序、数据和作业说明书三部分组成。 程序和数据完成用户所要求的业务处理工作。 作业说明书则体现用户的控制意图。 用批处理控制方式组织的作业，在作业进入系统之前，程序员除了要准备好源程序和初始数据外，还必须用作业控制语言来书写一份作业控制说明书，系统通过作业说明书控制文件形式的程序和数据，使之执行和操作。 在批处理系统中，把一批作业依次放置在相应的输入设备上，在操作系统的控制下，依次将它们输入辅助存储器中，这样就形成了一个作业流，也称输入流。,2019/5/28,第三章 处理机调度与死锁,9,作业说明书,作业说明书包括作业基本情况、作业控制、作业资源要求的描述；它体现用户的控制意图。如：预计运行时间、要求的资源情况、执行优先级等。 作业基本情况描述：用户名、作业名、编程语言、最大处理时间等； 作业控制描述：作业控制方式、作业步的操作顺序、作业执行出错处理等； 作业资源要求描述：处理时间、优先级、内存空间、外设类型和数量、库函数或实用程序等；,2019/5/28,第三章 处理机调度与死锁,10,作业的建立,建立一个作业必须把该作业所包含的程序和数据输入到计算机的外部辅助存储设备上，而且还要由作业注册程序在系统中为该作业申请建立起一个相应的作业控制块。 即作业的建立过程包括两个子过程： 作业的输入； 作业控制块的建立。,2019/5/28,第三章 处理机调度与死锁,11,JCB 的建立,在系统把作业信息输入到外存输入井之后，还需要根据作业说明书中的说明及其它信息建立作业控制块(JCB)。只有在获得JCB表项和足够的输入井空间之后，一个作业才可能创建成功。 JCB是作业存在的唯一标志。作业进入系统时，则为之建立JCB，当作业退出系统时，则其JCB也被撤消。,2019/5/28,第三章 处理机调度与死锁,12,作业控制块,内容：作业名、作业类型、资源要求、当前状态、资源使用情况以及该作业的优先级等。 作业类型：计算型（要求CPU时间多）、管理型（要求输入/输出量大）和图形设计型（要求高速图形显示）等。 资源要求：该作业估计执行时间、要求最迟完成时间、要求的内存量和外存量、要求的外设类型及台数以及要求的软件支持工具库函数等。,2019/5/28,第三章 处理机调度与死锁,13,资源使用情况：作业进入系统时间、开始执行时间、已执行时间、内存地址、外设台数等。 作业进入系统时间：指作业的全部信息进入输入井，作业的状态成为后备状态的时间。 开始执行时间：指该作业被调度程序选中，其状态由后备状态变为执行状态的时间。 内存地址：指分配给该作业的内存区起始地址。 外设台数：指分配给该作业的外设实际台数。 优先级：用来决定该作业的调度次序。可以由用户给定，也可以由系统动态计算产生,作业控制块,2019/5/28,第三章 处理机调度与死锁,14,作业的状态,作业从提交给系统直到它完成后离开系统前的整个活动过程，要经历四种不同状态： 提交状态：一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态 后备状态（收容状态）：输入管理系统不断地将作业输入到外存对应部分（或称输入井），如果一个作业的全部信息已全部输入到输入井，在它还没有被调度去执行前，该作业处于后备状态。 运行状态：作业一旦被作业调度程序选中而被送入主存中投入运行，作业就处于执行状态。 完成状态：作业运行完毕，但它所占用的资源尚未被系统全部回收时，该作业处于完成状态,2019/5/28,第三章 处理机调度与死锁,15,作业状态及其转换,2019/5/28,第三章 处理机调度与死锁,16,作业是用户向计算机提交任务的任务实体。 进程是计算机为了完成用户任务实体而设置的执行实体。 计算机要完成一个任务实体，必须要有一个以上的执行实体，因此一个作业总是由一个以上的多个进程组成。,作业与进程的关系,2019/5/28,第三章 处理机调度与死锁,17,作业、作业步、进程的关系,2019/5/28,第三章 处理机调度与死锁,18,也称为作业调度、长程调度（Long-Term Scheduling）或宏观调度。 根据某种算法对外存输入井上的大量后备作业进行选择调入内存，并为它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上，准备执行。 一般在批处理系统中有作业调度。而在分时系统中，为了及时响应，用户通过键盘输入的命令或数据都是直接送入内存，因此无需配置作业调度机制，实时系统亦然。,高级调度,2019/5/28,第三章 处理机调度与死锁,19,高级调度 执行作业调度时应决定： 接纳多少个作业？ 接纳哪些作业？,取决于多道程序度。 取决于所采用的调度算法，如先来先服务调度算法、短作业优先调度算法、最高响应比法等。,2019/5/28,第三章 处理机调度与死锁,20,作业调度功能,1: 记录系统中各作业的状况 2：按某种算法从后备队列中挑选一个或一批作业调入内存，让它们投入执行。 3：为被选中作业做好执行前的准备工作。 4：在作业执行结束时做善后处理工作,2019/5/28,第三章 处理机调度与死锁,21, 按照某种调度算法从后备作业队列中选取作业。 为被选取的作业分配内存和外设资源（当系统为动态分配外设时，作业所申请的外设只作为调度的参考因素）。因此要用到内存分配程序和外设分配程序。 为选中的作业建立相应的进程。 为作业开始运行做好一切准备工作。如构造和读写作业运行时所需要的有关表格及建立负责其运行控制的作业运行控制程序。 在作业运行完毕或运行过程中因某种原因需要撤离时，作业调度程序还要完成作业的善后处理工作，如输出作业管理信息（执行时间），收回分配给该作业的全部资源，撤销与该作业有关的全部进程和该作业的作业控制块等,作业调度应完成如下几方面的工作,2019/5/28,第三章 处理机调度与死锁,22,作业从后备状态到执行状态,2019/5/28,第三章 处理机调度与死锁,23,作业从执行状态到完成状态,2019/5/28,第三章 处理机调度与死锁,24,作业调度目标与性能衡量,1)调度目标 对所有作业应该是公平合理 应使设备有高的利用率 执行尽可能多的作业 有快的响应时间,2019/5/28,第三章 处理机调度与死锁,25,2）在批处理系统中衡量作业调度算法优劣的性能量度 周转时间 其中某一作业进入“输入井”的时间为Tsi ，它被选中执行，运行结束时的时间为Tei n 个作业平均周转时间为：,作业调度目标与性能衡量,2019/5/28,第三章 处理机调度与死锁,26,作业调度目标与性能衡量,一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：一是等待时间；二为执行时间，即 带权周转时间 平均带权周转时间：,2019/5/28,第三章 处理机调度与死锁,27,又称中程调度(Medium-Term Scheduling)、交换调度。 引入中级调度的目的是为了提高内存的利用率和系统吞吐量。 将目前不在运行态的进程，包括其数据，从内存交换到外存（此时进程的状态为挂起状态），将新进程的代码、数据、栈等交换入内存。,中级调度,2019/5/28,第三章 处理机调度与死锁,28,也称微观调度、进程调度或短程调度（Short-Term Scheduling）。 用来决定就绪队列中的哪个进程应获得处理机，再由分派程序执行把处理机分配给该进程的具体操作。 从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态。由于低级调度算法的频繁使用，要求在实现时做到高效（算法不宜复杂） 任何OS都必须配置进程调度。,低级调度,2019/5/28,第三章 处理机调度与死锁,29,进程调度的两种方式,非抢占式(Non-preemptive Mode)：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。 抢占方式(Preemptive Mode)：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。 抢占原则：优先权原则、短作业（进程）优先原则、时间片原则。,2019/5/28,第三章 处理机调度与死锁,30,WHAT：按什么原则分配CPU 调度算法 WHEN：何时分配CPU 调度的时机 HOW： 如何分配CPU CPU调度过程（进程的上下文切换）,进程调度要解决的问题,2019/5/28,第三章 处理机调度与死锁,31,进程调度的功能,1、记录系统中所有进程的执行情况 作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的PCB表中。并且将各进程的PCB表排成相应的队列并进行动态队列转接。 2、选择占有处理机的进程 进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。 3、进行进程上下文切换 一个进程的执行是在其上下文中执行的。当正在执行的进程由于某种原因要让出处理机时，系统要做进程上下文切换，以使另一个进程得以执行。,2019/5/28,第三章 处理机调度与死锁,32,一个进程运行完毕，或因某种错误而终止运行 当一个进程在运行时变为等待状态（等待I/O） 分时系统中时间片到 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语） 在执行完系统调用，系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户进程执行。 当有一个优先级更高的进程就绪（可抢占式） 例：新创建一个进程；一个等待进程变成就绪,进程调度的时机,2019/5/28,第三章 处理机调度与死锁,33,处理机调度的层次,2019/5/28,第三章 处理机调度与死锁,34,调度队列模型,仅有进程调度的调度队列模型,主要适用于分时系统。,FIFO 队列,2019/5/28,第三章 处理机调度与死锁,35,具有高级和低级调度的调度队列模型 适用于批处理操作系统,调度队列模型,优先权队列,多个阻塞队列,2019/5/28,第三章 处理机调度与死锁,36,调度队列模型,同时具有三级调度的调度队列模型,2019/5/28,第三章 处理机调度与死锁,37,选择调度方式和调度算法的准则,面向用户的准则 周转时间短（批处理系统） 响应时间快（分时系统） 响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。 截止时间的保证（实时系统） 截止时间是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。 优先权准则（批处理、分时和实时系统）,2019/5/28,第三章 处理机调度与死锁,38,选择调度方式和调度算法的准则,面向系统的准则 系统吞吐量高（批处理系统） 吞吐量指在单位时间内系统所完成的作业数。 处理机利用率好 各类资源的平衡利用 公平,2019/5/28,第三章 处理机调度与死锁,39,3.3 调度算法,现有的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。,先来先服务调度算法(FCFS：First Come First Serve) 应用范围与含义 作业调度：选择一个或多个最先进入后备队列的作业，将它们调入内存，为它们分配资源、创建进程，并放入就绪队列。 进程调度：按照进程就绪的先后次序来调度进程，为之分配处理机。 当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。,2019/5/28,第三章 处理机调度与死锁,40,先来先服务调度算法,在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。最简单的算法。 特点 比较有利于长作业，而不利于短作业。 有利于CPU繁忙的作业，而不利于I/O繁忙的作业。,例1：在单道环境下，某批处理系统有四道作业，已知它们的进入系统的时刻、估计运算时间如下：,2019/5/28,第三章 处理机调度与死锁,41,先来先服务调度算法,用FCFS算法计算作业的运行情况、平均周转时间和平均带权周转时间,2019/5/28,第三章 处理机调度与死锁,42,例1：,2019/5/28,第三章 处理机调度与死锁,43,作业名 进入时间 运行时间（分） 需内存量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，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用FCFS算法,例2：,2019/5/28,第三章 处理机调度与死锁,44,100K,作业名 进入时间 运行时间（分） 需内存量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,T=72 W=3.55,2019/5/28,第三章 处理机调度与死锁,45,2 时间片轮转算法(RRRound Robin),把CPU划分成若干时间片。 将系统中所有的就绪进程按照FCFS原则，排成一个队列。 每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。 在一个时间片结束时，发生时钟中断。 调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。 进程可以未使用完一个时间片，就出让CPU（如阻塞）。,2019/5/28,第三章 处理机调度与死锁,46,时间片长度的确定,时间片轮转策略特别适合于分时系统中使用 在轮转法中，时间片长度的选取非常重要，时间片长度的选择会直接影响系统开销和响应时间 过长退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。 过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，系统开销大。 最佳的时间片量值应能使分时用户得到好的响应时间,2019/5/28,第三章 处理机调度与死锁,47,时间片长度 SR/Nmax R：响应时间 Nmax：最大进程数 时间片长度的影响因素： 就绪进程的数目：数目越多，时间片越小（当响应时间一定时） 系统的处理能力：通常应当让用户输入能在一个时间片内能处理完，否则会使响应时间，平均周转时间和平均带权周转时间延长。,时间片长度的确定,2019/5/28,第三章 处理机调度与死锁,48,设有5个任务A、B、C、D、E，它们几乎同时到达，预计它们的运行时间为10、6、2、4、8min。若采用时间片为2min的时间片轮转调度算法，则各个任务的执行情况是：,第一轮：（A、B、C、D、E） 10min 第二轮：（A、B、D、E） 8min 第三轮：（A、B、E） 6min 第四轮：（A、E） 4min 第五轮：（A） 2min,例：,2019/5/28,第三章 处理机调度与死锁,49,例：,它们的周转时间为： TA30min，TB22min，TC6min，TD16min、TE28min 所以进程的平均周转时间为： T（302261628）/520.4min 从上面的计算中，可以看出A的周转时间最长，假设A第一轮从0分钟开始，则第二轮从10分钟开始，第三轮从18分钟开始，第四轮从24分钟开始，第五轮从28分钟开始，一共占用5轮的时间片。,2019/5/28,第三章 处理机调度与死锁,50,3 多级反馈轮转法 (round robin with multiple feedback),系统中设置多个就绪队列 每个就绪队列赋予不同的优先级和时间片，第一个队列的优先级最高，时间片最小，随着队列优先级的降低，时间片加大 各个队列按照先进先出原则排队等待调度,第n级队列（最低一级）中的进程采用时间片轮转算法进行调度。 一个新进程就绪后进入第一级队列末尾 进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾 当第一级队列空时，就去调度第二级队列，如此类推 当时间片到后，进程放弃CPU，回到下一级队列末尾,2019/5/28,第三章 处理机调度与死锁,51,3 多级反馈轮转法 (round robin with multiple feedback),2019/5/28,第三章 处理机调度与死锁,52,多级反馈队列调度算法的性能能较好满足各种类型用户的需要。 终端型用户：短作业，通常在第1级队列可以执行完成 短批处理作业用户：较短作业，通常在第1、2和3级队列就可以执行完成 长批处理作业用户：会依次在第1，2n个队列中运行，然后再按轮转方式运行，不会导致长作业等死,3 多级反馈轮转法 (round robin with multiple feedback),2019/5/28,第三章 处理机调度与死锁,53,4 优先级法 ( HPF：Highest Priority First),本算法适用于作业调度和进程调度 优先权调度算法的类型（进程调度时） 非抢占式优先权算法 主要用于批处理系统中，也可用于对实时性要求不高的实时系统。 抢占式优先权算法 能较好满足紧迫作业的要求，常用于要求比较严格的实时系统，以及性能要求较高的分时和批处理系统。,2019/5/28,第三章 处理机调度与死锁,54,优先权的类型 静态优先权 在作业或进程创建时指定优先数，在运行时优先数不变。 动态优先权 在作业或进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。,4 优先级法 ( HPF：Highest Priority First),2019/5/28,第三章 处理机调度与死锁,55,静态优先级,确定作业的静态优先数的原则： 由用户自己根据作业的紧急程度输入一个适当的优先级。 由系统或操作员根据作业类型指定优先级。 可以将作业分为：I/O繁忙的作业、CPU繁忙的作业、I/O与CPU均衡的作业、一般作业等。 系统或操作员给每类作业指定不同的优先级。 系统根据作业要求资源情况确定优先级 例如根据估计所需处理机时间、内存量大小、I/O设备类型及数量等，确定作业的优先级。,2019/5/28,第三章 处理机调度与死锁,56,静态优先级,确定进程的静态优先数的原则： 按进程的类型给予不同的优先级 有的系统，将进程划分为：系统进程与用户进程，系统进程享有比用户进程高的优先级。 用户进程可分为：I/O 繁忙的进程、CPU繁忙的进程、I/O与CPU均衡的进程、其它进程。 对系统进程也可以根据其所要完成的功能划分为不同的类型。如调度进程、I/O进程、中断处理进程、存储进程等。这些进程还可进一步划分为不同类型和赋予不同的优先级。 将作业的静态优先级作为它所属进程的优先级。,2019/5/28,第三章 处理机调度与死锁,57,动态优先级,虽然基于静态优先数的调度算法比较简单，系统开销小，但毕竟不够精确。因为进程的优先数在它执行前就已算好，且在整个执行期间都保持不变，随着进程的推进，计算优先数所依赖的特征很多都将随之改变，因此静态优先数并非自始至终都能准确地反映出这些特性，如果能在进程运行中，不断的随着特性的改变而修改其优先数，显然可以实现更精确的调度，从而获得更好的调度性能，这对分时系统显得格外重要. 在现代操作系统中，如果使用优先级调度的话，大多数采用动态优先级的调度策略。,2019/5/28,第三章 处理机调度与死锁,58,动态优先级,进程的动态优先级一般根据以下原则确定： （1）根据进程占有CPU时间的长短来决定。一个进程占有处理机的时间越长，则在被阻塞之后再次获得调度的优先级就越低，反之，其获得调度的可能性就越大。 （2）根据就绪进程等待CPU的时间长短来决定。一个进程在就绪队列中等待的时间越长，则它获得调度选中的优先级就越高。,2019/5/28,第三章 处理机调度与死锁,59,线性优先级调度算法 (SRR, Selfish Round Robin),本算法是优先级算法的一个实例，它通过进程优先级的递增来改进长执行时间进程的周转时间特征。,就绪进程队列分成两个： 新创建进程队列：按FCFS方式排成；进程优先级按速率 a 增加； 享受服务队列：已得到过时间片服务的进程按FCFS方式排成；进程优先级按速率 b 增加； 新创建进程等待时间的确定：当新创建进程队列的队首进程的优先级与享受服务队列中最后一个进程优先级相同时，队首进程转入享受服务队列 当享受服务进程队列为空时，新创建进程队列的队首进程也将移入享受服务进程队列。,2019/5/28,第三章 处理机调度与死锁,60,线性优先级调度算法 (SRR, Selfish Round Robin),SRR算法的优先级变化,2019/5/28,第三章 处理机调度与死锁,61,线性优先级调度算法 (SRR, Selfish Round Robin),SRR算法与FCFS算法和时间片轮转算法的关系,当ba0时，享受服务队列中永远只有一个进程；SRR算法退化成FCFS算法； 当ab=0时，SRR算法就是时间片轮转算法；,事实上，线性优先级调度策略是一种介于轮转法和FCFS方式之间的调度策略。,2019/5/28,第三章 处理机调度与死锁,62,5 最短作业优先法 (SJF, Shortest Job First),又称为“短进程优先” ( SPJ，Shortest Process First)；这是对FCFS算法的改进，其目标是减少平均周转时间。,对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。,2019/5/28,第三章 处理机调度与死锁,63,SJF的特点,优点： 比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间； 提高系统的吞吐量； 缺点： 对长作业非常不利，可能长时间得不到执行； 未能依据作业的紧迫程度来划分执行的优先级； 难以准确估计作业（进程）的执行时间，从而影响调度性能。,2019/5/28,第三章 处理机调度与死锁,64,设有5道作业，它们的提交时间和运行时间如表,例1,2019/5/28,第三章 处理机调度与死锁,65,执行的顺序为：P1-P2-P5-P4-P3 T0.68小时,例1,2019/5/28,第三章 处理机调度与死锁,66,例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，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用SJF算法,2019/5/28,第三章 处理机调度与死锁,67,作业名 进入时间 运行时间（分） 需内存量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,T=64.8 W=2.74,100K,2019/5/28,第三章 处理机调度与死锁,68,6 高响应比优先调度算法 （HRN：Highest Response-Ratio Next）,是FCFS和SJF的折衷,2019/5/28,第三章 处理机调度与死锁,69,6 高响应比优先调度算法 （HRN：Highest Response-Ratio Next）,响应比R = 1 +（作业等待时间 / 作业执行时间） 如作业等待时间相同，则执行时间越短，响应比越高，有利于短作业。 对于长作业，随等待时间增加，响应比增高，最后同样可获得处理机。 如执行时间相同，等待时间越长，响应比越高，实现的是先来先服务。,2019/5/28,第三章 处理机调度与死锁,70,例,设有4个作业P1、P2、P3、P4，它们到达时间和计算时间如表,2019/5/28,第三章 处理机调度与死锁,71,若这四个作业在一台处理机上按单道方式运行，采用最高响应比优先调度算法，则第一次计算响应比在8：00，此时只有P1作业提交，其相应比Rp11；在作业P1结束后，第二次计算各作业的响应比为： Rp2(1.5+1)/12.5 Rp3（1+0.25）/0.25 = 5 Rp4（0.5+0.5）/0.52 此时，选择作业P3调入内存，P3执行结束时，第三次计算剩余各作业的响应比为： Rp2（1.75+1）/12.75 Rp4（0.75+0.5）/0.52.5 此时，选择作业P2调入内存，P2执行结束时，调入P4。 所以它们的调入内存顺序为：P1、P3、P2、P4。,例,2019/5/28,第三章 处理机调度与死锁,72,各种调度算法性能对比,2019/5/28,第三章 处理机调度与死锁,73,例题,有一个多道批处理系统，作业调度采用“短作业优先”调度算法；进程调度采用“优先数抢占式”调度算法，且优先数越小优先级越高。若系统拥有打印机一台，采用静态方法分配，忽略系统的调度开销。现有如下作业序列到达系统：,2019/5/28,第三章 处理机调度与死锁,74,请给出作业运行结束的次序； 作业的平均周转时间和平均带权周转时间是多少？（要有中间计算步骤）,2019/5/28,第三章 处理机调度与死锁,75,补充习题,在单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都能并行工作，Job1优先级最高，Job2次之，Job3优先级最低，优先级高的作业可以抢占优先级低的作业的CPU但不抢占I1和I2。试求： 1、3个作业从投入到完成分别需要的时间。 2、从投入到完成的CPU利用率。 3、输入输出设备利用率。,2019/5/28,第三章 处理机调度与死锁,76,3.5 死锁问题,在多道程序系统中，多个进程并发运行，共享资源，从而提高了资源的利用率。但是若对资源的管理和使用不当，在一定条件下会导致系统发生一种随机性故障死锁。这时，若无外力协助，每个进程都不能继续执行下去。 在一些系统中，比如实时控制系统，系统一旦发生死锁将导致灾难性的后果。,2019/5/28,第三章 处理机调度与死锁,77,资源的概念,OS是计算机系统中资源的管理者，而进程是竞争资源的基本单位，故对系统中所有进程的资源分配工作，都由OS完成。 研究资源分配时，我们必须搞清该资源是可以被几个进程同时使用，还是只能为一个进程使用，资源的不同使用性质正是引起系统死锁的原因。,2019/5/28,第三章 处理机调度与死锁,78,根据资源性质：可剥夺（抢占）和不可剥夺（抢占）资源。 可抢占资源指资源占有进程虽然需要使用该资源，但另一个进程却强行把资源从占有者进程处抢来。 不可抢占资源指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。,资源的分类,2019/5/28,第三章 处理机调度与死锁,79,根据使用方式：共享资源和独占资源。 根据使用期限；永久资源和临时性资源。 永久资源：可顺序重复使用的资源，如所有的硬件资源和可再入的纯代码过程 临时性资源：由一个进程产生，被另外一个进程使用短暂时间之后便无用的资源，如在进程同步和通信中出现的消息、信号和数据,2019/5/28,第三章 处理机调度与死锁,80,死锁举例,例1： 进程A：获得CD-ROM使用权，申请打印机 进程B：获得打印机使用权，申请CD-ROM 死锁：此时进程A、B均被阻塞，无法运行,2019/5/28,第三章 处理机调度与死锁,81,死锁举例,例2： 在生产者-消费者问题中将生产者进程的两个P操作颠倒时会发生死锁。 将消费者进程的两个P操作颠倒时也会发生死锁。,2019/5/28,第三章 处理机调度与死锁,82,死锁的定义,死锁Deadlock：是计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象（僵局），如无外力作用，这些进程将永远不能再向前推进。 陷入死锁状态的进程称为死锁进程，所占用的资源或者需要它们进行某种合作的其它进程就会相继陷入死锁，最终可能导致整个系统处于瘫痪状态。,2019/5/28,第三章 处理机调度与死锁,83,产生死锁的原因,1 竞争资源。当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁； 2 进程推进的顺序不当 。进程在运行过程中，请求和释放资源的顺序不当，导致进程的死锁。,2019/5/28,第三章 处理机调度与死锁,84,竞争资源,竞争不可剥夺资源,竞争临时性资源(进程通信),2019/5/28,第三章 处理机调度与死锁,85,进程推进顺序不当引起死锁,曲线4将进入不安全区域（进程推进顺序非法）,2019/5/28,第三章 处理机调度与死锁,86,关于死锁的一些结论,参与死锁的进程最少是两个 （两个以上进程才会出现死锁） 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至 导致系统崩溃。,2019/5/28,第三章 处理机调度与死锁,87,产生死锁的必要条件,互斥条件：涉及的资源是非共享的。 不剥夺条件：不能强行剥夺进程拥有的资源。 请求和保持条件：进程在等待一新资源时继续占有已分配的资源。 环路条件：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。,2019/5/28,第三章 处理机调度与死锁,88,3.5.2 死锁的排除方法,1 鸵鸟方法 2 预防死锁 3 避免死锁 4 检测和解除死锁,2019/5/28,第三章 处理机调度与死锁,89,核心思想：忽略死锁问题 原因：死锁问题的发生是小概率事件 策略分析 方便性与正确性之间的选择 平均情况与最坏情况的选择 以UNIX系统为例，它潜在地存在死锁，但它并不花功夫去检测和解除死锁，而是忽略不去理它。,鸵鸟方法（置之不理）,2019/5/28,第三章 处理机调度与死锁,90,UNIX系统允许创建的进程总数是由进程表中包含的PCB个数决定的。如果由于进程表中已经无空闲的PCB而使创建子进程操作(FORK)失败，则执行FORK操作的程序可以等待一段时间之后再试。 假定UNIX系统有100个PCB项，10个进程正在运行，每个需要创建12个子进程。 在每个进程已经创建9个进程后，原来的10个进程和新创建的90个子进程已用完了进程表。这样，原来的10个进程现在都处于创建子进程的无限循环中死锁。出现这种情况的可能性是非常小的，但还是有可能发生的。一旦出现，只要忽略原进程已运行情况的现场，重新启动机器让它们重新运行即可。,2019/5/28,第三章 处理机调度与死锁,91,核心思想：对进程加以限制防止死锁发生 设计思路：设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。,死锁预防(deadlock prevention),具体解决方法 1、互斥条件：使用Spooling技术来管理设备,较易实现，广泛使用。 由于所施加的限制往往太严格，可能导致系统资源利用率和系统吞吐量的降低。,2019/5/28,第三章 处理机调度与死锁,92,采用的策略：一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请。 实现比较复杂，且要付出很大代价；此外，还因为反复地申请和释放资源，而使进程的执行无限地推迟，延长了周转时间，增加了系统的开销，降低了系统吞吐量。（例如打印机打印的结果不连续）,2：防止“不剥夺”条件的出现,2019/5/28,第三章 处理机调度与死锁,93,系统要求任一进程必须预先申请它所需的全部资源，而且仅当该进程的全部资源要求能得到满足时，系统才能给予一次性分配，然后启动该进程运行，但是在分配时只要有一种资源不满足，系统就不会给进程分配资源。进程运行期间，不会再请求新的资源，所以，再分配就不会发生（摒弃了部分分配）。 特点：简单、易于实现且安全 资源严重浪费 进程延迟进行,3:防止部分分配（摒弃请求和保持条件）,2019/5/28,第三章 处理机调度与死锁,94,采用资源顺序使用法，基本思想是：把系统中所有资源类型线性排队，并按递增规则赋予每类资源以唯一的编号。例如输入机1，打印机2，磁带机3，磁盘4等等。进程申请资源时，必须严格按资源编号的递增顺序进行，否则系统不予分配。 优点：资源利用率和系统吞吐量与另两种方法相比有较明显的改善。 缺点： 1 为系统中各种类型的资源所分配的序号必须相对稳定，这就限制了新设备类型的增加 2 作业实际使用资源的顺序与系统规定的顺序不同而造成资源的浪费；,4：防止“环路等待”条件的出现,2019/5/28,第三章 处理机调度与死锁,95,不事先采取限制去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。（如银行家算法）,避免死锁(deadlock avoidance),事先只需要较弱的限制条件，可获得较高的资源利用率和系统吞吐量。 实现较难。,2019/5/28,第三章 处理机调度与死锁,96,系统安全性和银行家算法,银行家算法的思路 系统安全状态 银行家算法,2019/5/28,第三章 处理机调度与死锁,97,银行家算法的思路,【问题】一个银行家拥有一千万资金，有10家工厂筹建，且每家工厂需要200万方可建成。如何合理分配资金问题？,2019/5/28,第三章 处理机调度与死锁,98,银行家算法的思路,【分析】如果将一千万均分给10家，则每个工厂都无法建成，也不能还贷，也即这10家工厂将“死锁”。若给其中的三个工厂200万，另4家工厂100万，这样，虽然有3家工厂未开工，但有3家可以建成投产，这3家工厂获得的利润可以给银行还贷，银行家再利用还贷的资金继续给其它工厂投入，直至最终10家工厂都建成投产。,2019/5/28,第三章 处理机调度与死锁,99,银行家算法的思路,银行家可以把一定数量的资金供多个用户使用，为保证资金的安全银行家规定四个条件： （1）当一个用户对资金的最大需求量不超过银行家现有资金时就可接纳该用户；（Request = Available ） （2）用户可以分期贷款，但贷款的总数不能超过最大需求量；（Request=Need）,2019/5/28,第三章 处理机调度与死锁,100,银行家算法的思路,（3）当银行家现有的资金不能满足用户的尚需贷款数时，对用户的贷款可推迟支付，但总能在用户有限的时间里得到贷款； （不符合“安全性条件”暂时不给贷款） （4）当用户得到所需的全部资金后，一定能在有限的时间里归还所有的资金。,2019/5/28,第三章 处理机调度与死锁,101,死锁避免定义,在系统运行过程中，对进程提出的每一个（系统能够满足的）资源申请进行动态检查（安全性检查），并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。,2019/5/28,第三章 处理机调度与死锁,102,安全状态：存在某种资源调度顺序，保证所有进程正常运行完成，则称该状态为安全状态 不安全状态：不存在可满足所有进程正常运行的资源调度顺序，则称该状态为不安全状态,虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质是如何使系统不进入不安全状态。 安全与不安全都是对静态进行的评价,安全状态,2019/5/28,第三章 处理机调度与死锁,103,例：假定系统有三个进程P1、P2、P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和九台。设在T0时刻，进程P1、P2和P3已经获得5台、2台和2台，还有3台空闲没有分配。,在T0时刻，系统是安全的。因为存在一个安全序列,安全状态举例,2019/5/28,第三章 处理机调度与死锁,104,如果不按安全序列分配资源，则系统可能会由安全状态进入不安全状态。 如在T0以后，P3要求1台磁带机，若系统分给它一台，则系统进入不安全状态。因为其余2台分给P2，P2完成后，只能释放4台，这既不能满足P1（5台），也不能满足P3（6台），将导致死锁。可见当P3申请资源时，尽管系统中有资源也不能分给它。,由安全状态向不安全状态的转换,2019/5/28,第三章 处理机调度与死锁,105,系统进入不安全状态,2019/5/28,第三章 处理机调度与死锁,106,银行家算法于1965年发表，该算法由Dijkstra提出。 1、银行家算法中的数据结构 可利用资源向量Available。它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目。 如：,利用银行家算法避免死锁,2019/5/28,第三章 处理机调度与死锁,107,最大需求矩阵Max。n*m矩阵，表示n个进程的每一个对m类资源的最大需求。,2019/5/28,第三章 处理机调度与死锁,108,分配矩阵Allocation 。n*m矩阵，表示每个进程已分配的每类资源的数目。,2019/5/28,第三章 处理机调度与死锁,109,需求矩阵Need 。n*m矩阵，表示每个进程还需要各类资源数。,Needi,j= Maxi,j- Allocationi,j,2019/5/28,第三章 处理机调度与死锁,110,当进程Pi提出资源申请时，系统执行下列步骤： （1）若RequestijNeedi,j【请求小于需求】,转（2）；否则错误返回 （2）若Requestij Availablej 【请求小于库存】, 转（3）；否则进程等待,银行家算法描述,2019/5/28,第三章 处理机调度与死锁,111,（3）假设系统分配了资源【试分配】，则有： 【库存】 Available j :=Available j -Requestij; 【获取】 Allocationi,j:=Allocationi,j+Requestij; 【需求】 Needi,j:=Needi,j-Requestij （4）执行安全性算法，若系统新状态是安全的，则分配完成，若系统新状态是不安全的，则恢复原状态，进程等待,银行家算法描述,2019/5/28,第三章 处理机调度与死锁,112,为进行安全性检查，定义数据结构： Work:ARRAY0m-1 of integer;【动态可分配资源】 Finish:ARRAY0n-1 of Boolean;【标识符】 m代表资源种类数，n代表进程的数量,安全性算法,2019/5/28,第三章 处理机调度与死锁,113,安全性算法步骤,(1) Workj:=Availablej; Finishi:=false; (2) 寻找满足下列条件的i： a). Finishi=false; b). Needi,jWorkj;【需求小于动态可分配资源】 如果不存在，则转(4),2019/5/28,第三章 处理机调度与死锁,114,(3) 进程i获取资源，然后执行完毕，并释放资源： Workj :=Workj+Allocationi,j; Finishi:=true; 转(2) (4) 若对所有i,Finishi=true,则系统处于安全状态，否则处于不安全状态,安全性算法步骤,2019/5/28,第三章 处理机调度与死锁,115,例：设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如图,2019/5/28,第三章 处理机调度与死锁,116,T0时刻的安全性检查 T0时刻可以找到一个安全序列，系统是安全的。,2019/5/28,第三章 处理机调度与死锁,117,T0时刻P1请求资源 P1发出请求Request(1,0,2)，执行银行家算法,2019/5/28,第三章 处理机调度与死锁,118,执行安全性算法 可以找到一个安全序列P1,P3,P4,P0,P2，系统是安全的，可以将P1请求资源分配给它。,2019/5/28,第三章 处理机调度与死锁,119,P4发出请求Request(3,3,0), 执行银行家算法 Availa