操作系统讲义第三章

第三章处理机调度与死锁2023/2/31操作系统讲义主要内容

3.1处理机调度的层次

3.2调度队列模型和调度准则

3.3几种调度算法

3.4实时调度

3.5产生死锁的原因和必要条件

3.6预防死锁的方法

3.7

死锁的检测和解除2023/2/32第二章进程管理3.1处理机调度的层次作业的基本概念1.高级调度（HighLevelScheduling）主要功能：根据某种算法，把外存中把处于后备队列中的那些作业调入内存，当作业完成时做善后处理。

作业（Job）：包含通常的程序和数据，并且配有作业说明书；作业步（JobStep）：“编译”

->“连接装配”->“运行”；作业流：若干个作业在系统外存形成的输入流。

作业控制块JCB（JobControlBlock）通常包含：作业标识、用户名称、用户账户、作业类型（CPU繁忙，I/O繁忙，批量型，终端型）、作业状态、调度信息（优先级，作业运行时间）、资源需求（运行时间，内存，I/O类型数量）、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况。2023/2/33第二章进程管理3.1处理机调度的层次1.高级调度（HighLevelScheduling）作业调度：是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存后备队列中选取某些作业调入内存，为它们创建进程、分配必要的资源，然后将进程插入就绪队列，准备执行。目的：提高内存利用率和系统吞吐量，使那些暂时不能运行的进程不再占用内存，把它们调至外存（存储管理中的对换功能）。

1）接收多少个作业到内存：取决于多道程序度

2）接收哪些作业：取决于调度算法最简单：先来先服务调度算法最常用：短作业优先调度算法较常用：优先级调度算法比较好：响应比高者优先调度算法2.中级调度（IntermediateLevelScheduling）2023/2/34第二章进程管理3.1处理机调度的层次3.低级调度（LowLevelScheduling）它所调度的对象是进程（或内核级线程），当CPU需要重新分配时，利用一定的算法把它分配给进程，它是最基本的调度。进程调度的功能

（1）保存处理机的现场信息；（2）按照某种算法选择进程（如优先数算法，轮转算法）

（3）把处理器分配给进程。进程调度的三个基本机制（1）排队器：事先将系统所有就绪进程排成一个或多个队列，方便调度程序最快找到它；（2）分派器（分派程序）：把进程调度程序选定的进程从就绪队列移出，切换上下文，然后把CPU分配给它；（3）上下文切换机制：保存当前程序的上下文，装入分派程序的上下文；移出分派程序，装入新选进程的CPU信息；2023/2/35第二章进程管理3.1处理机调度的层次进程调度方式

3.低级调度（LowLevelScheduling）非抢占方式：一旦处理机分配给某个进程，不管它要运行多长时间，都让它一直运行下去，决不会因为其它原因而抢占正在运行进程的处理机。这种方式下引起进程调度的因素包括：执行完毕或者发生某事件不能再执行执行进程提出I/O请求而暂停执行在进程通信或者同步过程中执行了某种原语操作，如P，Block等优点：实现简单，系统开销小，适用于大多数批处理系统；缺点：难以满足紧急任务要求，可能造成难以预料的后果。2023/2/36第二章进程管理3.1处理机调度的层次进程调度方式

3.低级调度（LowLevelScheduling）抢占方式：允许调度程序根据某种原则去暂停某个正在执行的进程，这些原则主要包括：优先权原则：优先权高的进程可以抢占当前优先权低的进程的CPU；短作业（进程）优先原则：短作业（进程）可以抢占当前较长作业（进程的）CPU；时间片原则：时间片轮转；优点：防止一个长进程长时间占用处理机，公平服务，适合实时任务的需求；缺点：需要付出较大的开销。2023/2/37第二章进程管理3.2

调度队列模型和调度准则仅有进程调度的调度队列模型通常在分时系统中只设置进程调度，每个用户建立一个进程，系统利用堆栈、树或者链表来管理就绪进程队列，就绪进程以FIFO队列形式组织。

1.调度队列模型进程执行时可能出现的三种情况：在给定时间片完成，释放处理机进入完成状态；本次时间片内未完成，放入就绪队列尾部；因为某事件被阻塞，放入阻塞队列。就绪队列CPU阻塞队列交互用户时间片完进程调度等待事件进程完成事件出现2023/2/38第二章进程管理3.2

调度队列模型和调度准则具有高级和低级调度的调度队列模型在批处理系统中，作业调度按照一定的算法从外存的后备队列选择一批作业调入内存，建立进程，送入就绪队列，然后按照一定的进程调度算法选择进程，分配CPU。

1.调度队列模型就绪队列CPU阻塞队列作业调度时间片完进程调度等待事件1进程完成事件1出现队列后备阻塞队列阻塞队列等待事件2等待事件n事件2出现事件n出现……队……2023/2/39第二章进程管理3.2

调度队列模型和调度准则

1.调度队列模型具有高级和低级调度的调度队列模型的特点：（1）采用优先权就绪队列，队首进程优先权最高，或者采用无序链表方式；（2）设置多个阻塞队列，每个队列对应于某一种进程阻塞事件；2023/2/310第二章进程管理3.2

调度队列模型和调度准则同时具有三级调度的调度队列模型可把进程的就绪状态分成内存就绪和外存就绪，类似地，阻塞状态也可进一步分成内存阻塞和外存阻塞，调出操作可使进程状态由内存就绪转为外存就绪，内存阻塞转为外存阻塞；中级调度可使外存就绪转为内存就绪。

1.调度队列模型就绪队列CPU绪挂起队列就作业调度时间片完进程调度进程完成事件出现队列后备塞挂队队列阻阻塞队列等待事件起批量作业挂起事件出现中级调度2023/2/311第二章进程管理3.2

调度队列模型和调度准则面向用户的准则

（1）周转时间短（批处理系统）

平均周转时间T的计算如下：平均带权周转时间W的计算如下：

（2）响应时间快（分时系统）：是指从用户通过键盘提交一个请求开始，直到系统首次响应为止的时间必须快；

（3）截止时间的保证（实时系统）：是指某任务必须开始执行的最迟时间，或必须完成的最迟时间必须有保证；

（4）优先权准则：遵循优先权准则让某些紧急的作业得到及时处理。2.选择调度方式和算法的若干准则2023/2/312第二章进程管理3.2

调度队列模型和调度准则面向系统的准则

2.选择调度方式和算法的若干准则（1）系统吞吐量高：这个是评价批处理系统性能的另一个重要指标，因此是选择批处理作业调度的重要准则。吞吐量是指单位时间内系统完成的作业数，它直接和作业的平均长度有关；（2）处理机利用率好：CPU价格昂贵，利用率成为衡量系统性能的重要指标；（3）各类资源的平衡利用：不仅要使处理机利用率高，还要有效地利用其它各类资源，如内存、外存和I/O设备，适当的调度方式和算法可以使系统中的各类资源处于忙碌状态。2023/2/313第二章进程管理3.3

调度算法是一种最简单的调度算法，适用于作业调度和进程调度，每次调度都是从后备队列中选择一个或者多个最先进入该队列的作业，将它们调入内存，分配资源，创建进程，然后放入就绪队列。

1.先来先服务调度算法FCFS（FirstComeFirstService）FCFS算法比较有利于长作业（进程），不利于短作业（进程）进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.992023/2/314第二章进程管理3.3

调度算法是指对短作业或者短进程优先调度的算法，适用于作业调度和进程调度，SJF算法就是从后备队列中选择一个运行时间最短的作业，然后把它们调入内存运行。

2.短作业优先调度算法SJF（ShortJobFirst）SJF的优点：能有效地降低作业的平均等待时间，提高系统吞吐量；进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A030331B145982C223531.5D35914112.2SJF的缺点：1）对长作业不利；2）未考虑作业的紧迫度；3）用户估计执行时间的不准确性。2023/2/315第二章进程管理3.3

调度算法

3.FCFS和SJF的性能比较算法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398带权周转时间12.673.21.52.252.12023/2/316第二章进程管理3.3

调度算法是为了照顾紧迫型作业，使之在进入系统后便获得优先处理，该算法会把处理机分配给优先级最高的作业（或者进程）。1）非抢占式优先权调度算法，适用于批处理系统或实时性要求不高的系统；

2）抢占式优先权调度算法，能更好地满足紧迫作业，适合于严格的实时系统或者对性能要求较高的批处理和分时系统中。

4.高优先权优先调度算法（PriorityJobFirst）2023/2/317第二章进程管理3.3

调度算法

4.高优先权优先调度算法（PriorityJobFirst）优先权的类型静态优先权：创建进程时确定，在整个运行期间保持不变；进程类型，系统进程要比用户进程优先级高；进程对资源的要求，要求少的优先级高；用户要求，用户进程的紧迫程度。优点：简单易行，系统开销小缺点：不够精确，可能使优先权低的作业（进程）长期得不到调度动态优先权：创建时赋予，可以随着进程的推进或随其等待时间的增加而改变，以便获得更好的调度性能。优点：使调度更加公平，调度性能高缺点：系统开销稍大2023/2/318第二章进程管理3.3

调度算法高响应比优先调度算法

每个作业的优先级动态计算，作业的优先级随等待时间的增加而不断提高。

4.高优先权优先调度算法（PriorityJobFirst）结论：如果作业等待时间相同，要求服务时间越短，优先级越高，该算法利于短作业；如果要求服务时间相同，那么等待时间越长，优先权越高，它实现的是先来先服务；对于长作业，作业的优先级随着等待时间的增加而提高，如果等待时间足够长也可以获得处理机。优点：既照顾了短作业，又考虑了作业的先后顺序，使长作业也可以得到服务；缺点：但优先级的计算增加了系统的开销。响应比RP=等待时间+要求服务时间要求服务时间=响应时间要求服务时间2023/2/319第二章进程管理3.3

调度算法基本原理系统将所有就绪进程按照先来先服务的原则排成一个队列，每次调度把CPU分配给队首进程，并令其执行一个时间片，当执行时间片用完，调度程序停止其执行，并把它送到队列尾部。

5.基于时间片的轮转调度算法（RoundRobin）时间片大小如果太小利于短作业，但是会频繁中断，进程上下文切换，增加系统开销；如果太大则每个进程都能在时间片内完成，则退化为FCFS算法，无法满足交互式用户的需求。2023/2/320第二章进程管理3.3

调度算法

5.基于时间片的轮转调度算法（RoundRobin）(a)q=1(b)q=4123456789101112131415161718ABACBDAECBDAECABCDEECECC2023/2/321第二章进程管理3.3

调度算法——队列（q=1）时间队列状态时间队列状态0A10DAECB完成1BA11AECD完成2ACB12ECA完成3CBDA13CE4BDAEC14EC5DAECB15CE6AECBD16EC7ECBDA17CE完成8CBDAE18C完成9BDAEC2023/2/322第二章进程管理3.3

调度算法——队列（q=4）时间队列状态0A4BCDEA完成7CDEB完成11DEC13ECD完成17CE完成18C完成2023/2/323第二章进程管理3.3

调度算法

5.时间片轮转法RR算法进程名ABCDE平均到达时间01234服务时间43524RRq=1完成时间1210181117周转时间1291681311.6带权周转时间333.243.253.29RRq=4完成时间47181317周转时间461610139.8带权周转时间123.253.252.892023/2/324第二章进程管理3.3

调度算法调度算法的实施过程设置多个就绪队列，赋予不同的优先级，各个队列优先级递减，时间片递增；新进程放入第一个队列尾部，FCFS原则排队调度，时间片内完成则撤离系统，如果没完则转入下个队列尾部，以此类推，在第n个队列采取时间片轮转调度；第一队列空闲，调度第二队列，以此类推，新进程如果优先级高，可抢占处理机。

6.多级反馈队列调度算法（RoundRobinWithMultipleFeedback）2023/2/325第二章进程管理3.3

调度算法

6.多级反馈队列调度算法（RoundRobinWithMultipleFeedback）算法的性能终端型作业用户，大多属于交互型作业，作业小；短批处理作业用户，周转时间短；长批处理用户，不用担心作业长期得不到处理。就绪队列1就绪队列2就绪队列3就绪队列4至CPU至CPU至CPU至CPUS1S2S3（时间片：S1<S2<

S3）新进程2023/2/326第二章进程管理3.4

实时调度提供必要的信息就绪时间，任务就绪的起始时间；开始截止时间和完成截止时间；处理时间，一个任务从开始执行直至完成所需的时间；资源要求，任务执行的时候需要的一组资源；优先级，对紧迫任务设置“绝对”优先级，松弛任务设置“相对”优先级。

1.实现实时调度的基本条件2023/2/327第二章进程管理3.4

实时调度

1.实现实时调度的基本条件具有快速切换机制对外部中断的快速响应能力；快速的任务分派能力。系统处理能力强采用抢占式调度机制采用单处理机系统，增强处理能力，减少每个任务处理时间；采用多处理机调度单处理机实时调度条件：2023/2/328第二章进程管理3.4

实时调度非抢占式调度算法非抢占式轮转调度算法；非抢占式优先级调度算法。抢占式调度算法基于时钟中断的抢占式优先权调度算法立即抢占的优先权调度算法

2.实时调度算法分类最早截止时间优先EDF（EarliestDeadlineFirst）算法

3.常用的几种实时调度算法最低松弛度优先级LLF（LeastLaxityFirst）算法

任务的松弛度=必须完成时间-其本身运行时间-当前时间

松弛度=0表示该任务必须马上执行，否则会造成严重后果。2023/2/329第二章进程管理3.5

产生死锁的原因和必要条件竞争资源：多个进程共享资源，资源数目不足所引起进程对资源的竞争；可剥夺资源和非剥夺性资源竞争非剥夺性资源竞争临时性资源

1.产生死锁的原因死锁（Deadlock）：是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程出现这种僵持状态时，若无外力作用，它们将无法再向前推进。2023/2/330第二章进程管理3.5

产生死锁的原因和必要条件

1.产生死锁的原因进程推进顺序非法：请求和释放资源顺序不当。1）进程推进顺序合法2）进程推进顺序非法P1：Request(R1);Request(R2);P1：Release(R1);Release(R2);P2：Request(R1);Request(R2);P2：Release(R1);Release(R2);P1：Request(R1);P2：Request(R2);P1：Request(R2);P2：Request(R1);P1P2R1R22023/2/331第二章进程管理3.5

产生死锁的原因和必要条件（1）互斥条件，一段时间内某资源只能由一个进程占用；（2）请求和保持条件，部分分配资源；（3）不剥夺条件，进程已获得资源不能被剥夺，直至使用完毕；（4）环路等待条件，发生死锁时必然存在进程-资源的环形链。

2.产生死锁的必要条件（1）预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，预防死锁的发生；（2）避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁；（3）检测死锁：通过系统所设置的检测机制，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；（4）解除死锁：与死锁检测配合，通过撤销和挂起一些进程，以便回收一些资源，再将这些资源分配给处于阻塞状态的进程，使之就绪，以继续运行。

3.处理死锁的基本方法2023/2/332第二章进程管理3.6

预防死锁的方法（1）摒弃“请求和保持”条件，要么全部分配，要么一个也不分配；（2）摒弃“不剥夺”条件，资源在进程运行过程中可被暂时释放；（3）摒弃“环路等待”条件，进程对资源的请求按照某种顺序依次进行。

1.预防死锁安全状态是指系统能按某种进程顺序（P1，P2，…，Pn），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都顺利执行。安全状态实例:假设系统中有三个进程P1，P2，P3，共12台磁带机。2.系统安全状态进程最大需求已分配可用P11053P242P3922023/2/333第二章进程管理3.6

预防死锁的方法数据结构

3.银行家算法（1）可利用资源向量Available（m个元素的数组），其中Available[j]=k，表示系统中Rj类资源有k个。（2）最大需求矩阵Max（n×m）的矩阵，Max[i,j]=k，表示进程Pi需要Rj类资源的最大数目是k个。（3）分配矩阵Allocation（n×m）的矩阵，Allocation[i,j]=k，表示Pi已经分得Rj类资源的数目是k个。（4）需求矩阵Need（n×m）的矩阵，Need[i,j]=k，表示Pi还需要Rj类资源的数目是k个。上述关系：Need[i,j]=Max[i,j]-Allocation[i,j]；2023/2/334第二章进程管理3.6

预防死锁的方法算法描述

3.银行家算法假设Requesti

是Pi的请求向量，Requesti[j]=k表示Pi请求k个Rj类资源，Pi申请后，系统进行检查：（1）如果Requesti[j]

≤Need

[i,j]

，则转（2），否则出错（需要资源超过它宣布的最大值）。（2）如果Requesti[j]

≤Available

[j]

，则转（3），否则尚无足够的资源，Pi必须等待。（3）系统为Pi分配资源（试探性的分配）：

Available[j]:=Available[j]-Requesti[j]

;Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j];（4）执行安全性算法，若安全则分配（为Pi），否则不分配，令Pi等待。2023/2/335第二章进程管理3.6

预防死锁的方法安全性算法

3.银行家算法（1）设置两个向量：工作向量Work，表示系统可提供给进程继续运行所需的各类资源数目，含有m个元素，初始work:=Available；向量Finish，表示系统是否有足够的资源分配给进程，使之运行完成，初始时Finish:=false，有足够资源分配时，Finish:=true；（2）在进程集合中找到一个能满足下述条件的进程：

a）Finish[i]=false;b）Need[i,j]≤Work[j]；如果找到则转（3），否则转（4）；（3）进程Pi获得资源可顺利完成，并释放资源，则执行

Work[j]:=Work[j]+Allocation[i,j];Finish[i]:=true;转（2）；（4）如果所有进程的Finish[i]=true都满足，表示系统处于安全状态，否则系统进入不安全状态。2023/2/336第二章进程管理3.6

预防死锁的方法假设系统中有五个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况下表：

4.银行家算法的实例进程/资源MaxAllocationNeedAvailableABCABCABCABCP0P1P2P3P4753322902222433010200(302)302211002743122(020)600011431332(230)2023/2/337第二章进程管理3.6

预防死锁的方法

4.银行家算法的实例进程/资源WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1P3P4P2P0332532743745104712201143160074320021100230201053274374510471057truetruetruetruetrue(1)T0时刻的安全性：存在安全序列{P1,P3,P4,P2,P0}。2023/2/338第二章进程管理3.6

预防死锁的方法

4.银行家算法的实例进程/资源WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1P3P4P0P2230532743745755020011431743600302211002010302

5327437457551057truetruetruetruetrue(2)P1请求资源，发出请求向量Request1(1,0,2)，进行检查Request1(1,0,2)≤

Need1(1,2,2);Request1(1,0,2)≤

Available1(3,3,2);存在安全序列{P1,P3,P4,P0,P2}。(3)P4请求资源，发出请求向量Request4(3,3,0)，检查Request4(3,3,0)≤

Need4(4,3,1);Request4(3,3,0)≤

Available4(2,3,0);让P4等待。2023/2/339第二章进程管理3.6

预防死锁的方法

4.银行家算法的实例进程/资源AllocationNeedAvailableABCABCABCP0P1P2P3P4030302302211002723020600011431210(4)P0请求资源，发出请求向量Request0(0,2,0)，进行检查Request0(0,2,0)≤

Need0(7,4,3);Request0(0,2,0)≤

Available0(2,3,0);假定为P0分配资源，修改相关数据如下。(5)进行安全性检查，Available(2,1,0)已不能满足任何进程需要，故系统进入不安全状态。2023/2/340第二章进程管理3.7

死锁的检测与解除资源分配图（ResourceAllocationGraph）RAG是由一组结点N和一组边E组成的一个对偶RAG=（N，E），对它的约定如下：

（1）P={p1,p2,…,pn}R={r1,r2,…,rn}P和R是两个互斥的子集，N=P∪R

（2）e∈E，它连接P中的一个结点和R中的一个结点

e=（pi,rj)–资源请求边（pi指向rj

）表示pi请求一个单位的rj

；

e=（rj,pi)–资源分配边（rj

指向pi

）表示pi分配到一个单位的rj

；

1.死锁的检测P1P2R1R22023/2/341第二章进程管理3.7

死锁的检测与解除资源分配图的简化

（1）从RAG中找出既不阻塞又不是孤点的进程Pi，消去由Pi出发的和指向Pi的所有边（请求边和分配边），这等价于Pi获得它所需的资源，不断向前推进，一直运行完毕，释放出它所占有的全部资源。（2）进程Pi所释放的资源可以唤醒某些阻塞于该资源的进程Pj，消去Pj所有的边，使之成为孤点。（3）如此下去，最后，若消去图中所有的边，则称该图是可完全化简的。（4）若有向图不能通过任何过程予以简化，则称该图是不可完全简化的。

1.死锁的检测死锁定理

引理：一个给定的进程资源分配图，对所有的简化顺序，将导致相同的结果（再也不能简化）。