第3章 处理机调度与死锁(1-2)

第三章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除作业的状态及其转换批处理系统才有作业的概念，分时系统没有作业的概念；作业的状态分为：提交、后备、运行和完成；提交状态：作业再输入设备上并准备进入外存输入井前的状态。用户作业通常包括：程序、数据和作业说明书后备状态：由SPOOLing输入程序输入到外存输入井中，为其建立作业控制块（JCB），并将JCB插入到后备作业队列中的状态运行状态：作业被作业调度程序选中，由外存输入井调入到内存，为其分配了所需的资源并建立了进程，此时作业就进入到运行状态。完成状态：当作业正常结束或异常终止时，就进入完成状态。由作业调度程序做收尾工作：撤销JCB、回收分给该作业的系统资源等。3.1处理机调度的基本概念作业的状态及其转换提交后备运行就绪阻塞就绪阻塞完成SPOOLing程序作业调度程序进程调度程序中级调度外存外存输入井输入设备内存在多道批处理系统中，一个作业从提交到后备作业队列，再调入内从经运行到完成，可能需要经历三级调度：1.高级调度（HighScheduling)

高级调度又称为作业调度或宏观调度或长程调度，其主要功能是根据一定的算法，从后备作业队列（一批作业）中选出若干个作业调入内存，并为它们创建进程和分配必要的资源，然后将创建的新进程放入进程就绪队列中，使其处于就绪状态。当作业运行结束时，还要做一些善后工作（资源回收）3.1.1处理机调度的层次高级调度特点：1）多道批处理系统需要作业调度；分时系统和实时系统一般不需要高级调度。2）每次调度多少作业（程序）？需由系统规定的多道程序度而定；3）调度那些作业？由调度算法（策略）而定，如先来先服务，短作业优先调度，优先权调度算法等。2.中级调度(Intermediate-LevelScheduling)中级调度又称之为中程调度(Medium-TermScheduling)，中级调度主要任务是实施进程在内、外存间的交换；中级调度的主要功能是在内存使用紧张时，将一些暂时不能运行的进程从内存对换到外存上等待（此时的进程状态称为挂起状态或驻留外存状态）。以后，当外存有足够的空闲空间时，再将合适的进程重新换入内存，等待进程调度。引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。

3.低级调度(LowLevelScheduling)低级调度又称进程调度或微观调度或短程调度，其主要功能是根据一定的算法，将CPU分派给就绪进程队列中的某一进程。执行低级调度功能的程序称为进程调度程序，由它实现CPU在进程间的切换。进程调度是操作系统中最基本的一种调度，在一般操作系统（包括：多道批处理系统、分时系统和实时系统）中都必须有进程调度，而且它的策略的优劣直接影响整个系统的性能。4、进程调度方式

非抢占方式（Nonpreemptive）：在这种调度方式下，一旦一个进程被选中运行，它就一直运行下去，直到它运行结束并自愿放弃CPU，或者因等待某一事件而被阻塞或终止时为止，才把CPU出让给其他进程，即得到CPU的进程不管运行多长时间，都一直运行下去，不会因为当前进程以外的原因而被迫让出CPU。引起调度的原因：1）当前进程运行结束或发生某事件而终止；2）当前进程因提出I/O请求而阻塞；3）进程之间通信或同步而由于执行原语而等待。抢占方式（Preemptive）：抢占方式允许调度程序根据某种策略中止当前进程的执行，将其移入就绪队列，并将处理机分派给另一个进程使之投入运行。

抢占原则：1）优先权原则：允许高优先权进程抢占低优先权的CPU；2）短作业原则：允许短进程抢占长进程的处理机；3）时间片原则：分时系统中的当前进程，若时间片规定的时间用完，不管是否运行结束，都要立即中止放到就绪队列中，再将CPU分派给其它进程。3.1.2调度队列模型 不同OS对高级、中级和低级调度的选取形成了不同的调度队列模型，共有3种类型。1、仅有进程调度的调度队列模型

常在分时系统中设置仅有进程调度的调度队列模型。终端用户的登录注册以及交互命令的输入执行，系统都将为其建立进程，并放在FIFO就绪队列中，按照时间片轮转调度执行。进程的调度和变化过程如下图所示。图3-1仅具有进程调度的调度队列模型P1P2P42.具有高级和低级调度的调度队列模型在批处理系统中，不仅需要进程调度，而且还需要作业调度。若OS中仅包含高级调度和低级调度就形成了具有高级和低级调度的队列模型。进程调度常以最高优先权优先调度算法，就绪队列形式为优先权队列。阻塞队列按照不同事件排队就绪队列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现……等待事件n事件n出现后备队列……3.同时具有三级调度的调度队列模型作业CPU就绪挂起队列阻塞挂起队列阻塞队列就绪队列时间片到进程调度作业调度调入中级调度事件出现交互式用户等待事件进程完成挂起调出挂起调出事件出现

具有三级调度时的调度队列模型3.1.3选择调度方式和调度算法的若干准则1.面向用户的准则周转时间短：周转周期是指作业从提交给系统开始，到作业完成为止所消耗的时间。常用于衡量系统性能、作业调度算法的优劣的重要指标。可把平均周转时间描述为：作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为:响应时间快：分时系统性能的主要评价指标。响应时间指用户从键盘键入一个命令开始，到系统首次给出响应信息为止这段时间。截止时间的保证：评价实时系统性能的重要指标。截止时间是指系统为处理某事件/任务必须开始执行的最迟时间，或必须完成的最迟时间。优先权准则：批处理、分时和实时系统中的调度算法都应该遵循的原则。这种调度思想就是“急事急办”，优先权高者为急。2.面向系统的准则系统吞吐量高：评价批处理系统整体性能的重要指标。吞吐量是指单位时间内系统所完成的作业数。作业调度算法对系统吞吐量有直接影响，选择确定时应考虑这一准则。处理机利用率好：CPU的利用率是衡量大中型系统性能的重要指标。各类资源的平衡利用：选择适当调度算法，保证各种资源的利用都处于忙碌状态。3.2调度算法1、先来先服务（FCFS）调度算法适应范围：适应作业调度和进程调度；调度过程：FCFS用于作业（进程）调度时，从后备（就绪）队列中选择若干或一个先到来的作业（进程）投入运行。进程在分派到CPU进入运行过程中，只有当进程运行结束或因某事件发生而被阻塞才放弃CPU。算法特点：算法容易实现，但效率不高；只顾及作业等候时间，没考虑作业要求服务时间的长短，不利于短作业而优待了长作业；作业调度不分轻重缓急，人人平等；FCFS为非抢占式调度。先来先服务（FCFS）调度算法效率举例表注：周转时间=完成时间-到达时间；带权周转时间=周转时间/服务时间2、短作业/进程（SJF/SPF）优先调度算法适应范围：适应作业调度和进程调度。SJF/SPF算法以进入系统的作业/进程所要求的CPU时间为标准，总选取估计计算时间最短的作业/进程投入运行。算法特点：算法易于实现，效率不高；忽视长作业等待时间，会出现饥饿现象；不考虑紧迫作业/进程的需求；长短时间人为估计，不可靠，会出现以长乱短。SPF算法类型：抢占或非抢占式。抢占式SPF调度算法在新进程进入就绪队列时，将其运行时间与当前进程的剩余运行时间相比，若更短时，可抢占CPU；非抢占式SPF算法允许当前运行进程先执行直到释放CPU为止。可抢占SPF调度有时称为最短剩余时间优先（shortest-remaining-time-first）调度。

FCFS和SJF调度算法的性能分析

例题：假如5个就绪进程其到达系统和所需CPU时间如下表所示（单位：毫秒），如果忽略I/O以及其他开销，分别计算采用FCFS、非抢占式SPF和抢占式SPF调度算法进行CPU调度的平均周转时间和平均带权周转时间。进程到达和运行时间进程到达时间运行时间A03B26C44D65E82解答如下：（1）采用FCFS的调度顺序为：ABCDE039131820平均周转时间为：

T=((3-0)+(9-2)+(13-4)+(18-6)+(20-8))/5=8.6带权平均周转时间为：W=2.56（2）采用非抢占SJF的调度顺序为：ABECD039111520平均周转时间为：T=7.6带权平均周转时间为：W=1.84（3）采用抢占SJF的调度顺序为：平均周转时间为：T=7.2带权平均周转时间为：W=1.59AB1ECB2038101520D43、高优先权优先调度算法（priority-schedulingalgorithm）

1）优先权调度算法的类型非抢占式优先权算法：在此方式下，系统一旦把CPU分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给就绪队列中另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。抢占式优先权算法：在此方式下，系统把处理机分配给优先权最高的进程使之执行。但在其执行期间，只要又有更高优先权新进程进入就绪队列，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。适应较严格的实时系统、性能要求较高的批处理和分时系统。2）优先权的类型静态优先权静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，0~9中的某一整数，又把该整数称为优先数。

优先权的确定准则：系统进程者优先；资源需求少者优先；用户需求紧迫者优先。动态优先权：动态优先权是指在创建进程时所赋予的优先权，可以随进程的推进而改变的，以便获得更好的调度性能。（如等待时间与优先权成正比）4、高响应比优先调度算法动态优先权的变化规律可描述为：系统对作业的响应时间=等待时间+服务时间，故该优先权又相当于响应比RP。据此，优先权变化规律又可表示为：高响应比优先调度算法特点：如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业；当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务；对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机，避免了长作业饥饿现象。5、基于时间片的轮转调度算法

时间片调度算法适用于分时系统。划分为时间片轮转和多级反馈队列调度算法1）时间片轮转法轮转法调度做法是：系统将所有的就绪进程按FIFO原则排队，每次调度时，把CPU分配给队首进程，并令其执行一个时间片（如20ms）。当执行的时间片用完时，停止该进程的执行，并将它送往就绪队尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。如此反复和轮转，就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。FCBA

….CPUA

BC时间片轮转算法图示完成2）多级反馈队列调度算法多级反馈队列调度算法是目前公认的一种性能比较优良的调度算法，兼备了前述各种算法的优点。原理如下：设置多个就绪队列，并赋予不同的优先级和时间片：第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。图3-5是多级反馈队列算法的示意。多级反馈队列调度算法新进程进入（64ms）调度原则：当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。抢占原则：仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1~i队列均空时，才会调度第i+1队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。多级反馈队列调度算法的性能与特点终端型作业用户：短小作业及时完成，用户满意。(2)短批处理作业用户：短作业优先运行结束。(3)长批处理作业用户：不出现饥饿现象。作业3-1P101：1、4、6、73.3实时调度3.3.1实现实时调度的基本条件为了实现对实时进程进行有效调度，系统必须满足下述条件：1.提供必要的信息就绪时间：进程进入就绪状态的开始时间，有周期性和非周期性开始截止时间和完成截止时间：开始处理或完成任务的最迟时间处理时间：指一个进程从开始执行到完成需要的处理时间；资源要求：指处理一个任务时所需要的资源；优先级：用于标识一个任务得到处理的轻重缓急。实时调度：在实时操作系统中，实现实时进程或任务的调度。实时调度强调对实时进程或任务处理（响应）的及时性和紧迫性。2.系统处理能力强在实时系统中，通常都有多个实时任务（进程）等待计算机及时处理。处理机能力必须满足：假定系统中有m个周期性的硬实时任务，它们的处理时间分别Ci，周期时间分别为Pi，则在单处理机情况下，其处理能力必须满足条件：处理机满足此条件时，才是可调度的；否则，调度不过来。多处理机情况下，需要满足条件为：（N为处理机个数）3、采用抢占式调度机制当一个优先权更高的任务到达时，允许将当前任务暂时停止，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。4、具有快速切换机制对外部中断的快速响应能力：外部任务来到时能快速响应；快速的任务分派能力：在完成任务调度后，便应进行任务切换。3.3.2实时调度算法的分类1.非抢占式调度算法非抢占式轮转调度算法：控制多个相同对象；每对象一个实时进程；建立一个FIFO进程就绪队列，按照FCFS轮转调度。调度性能：实现数秒至数十秒响应时间，适应不严格的实时控制。非抢占式优先调度算法：就绪队列按优先级进队排序，调度始终先调度队首进程。调度性能：可能获得数秒至数百毫秒的响应时间，适应有一定要求的实时控制系统实时调度算法的分类方式较多：如按照任务性质分为硬实时调度和软实时调度；按照调度方式分为抢占方式和非抢占方式调度等2.抢占式调度算法基于时钟中断的抢占式优先权调度算法：如果有比当前进程优先级更高的进程到来，需等到时钟中断到来时抢占CPU。调度性能：响应达到几十毫秒至几毫秒，适应大多数控制系统。立即抢占(ImmediatePreemption)的优先权调度算法：如果有比当前进程优先级更高的进程到来，若当前进程不处在临界区，则立即抢占CPU。调度性能：调度延迟为几毫秒至100微秒。非抢占实时进程调度示意图(a)非抢占轮转调度调度时间进程

1进程

2实时进程要求调度进程

n实时进程调度实时进程运行(b)非抢占优先权调度当前进程实时进程实时进程请求调度当前进程运行完成调度时间抢占实时进程调度示意图当前进程实时进程实时进程请求调度实时进程枪占当前进程，并立即执行(d)立即抢占的优先权调度当前进程