计算机操作系统 第三版 第三章处理机调度

第三章处理机调度与死锁处理机管理的工作是对CPU资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。要解决的问题WHAT：按什么原则分配CPU

—进程调度算法WHEN：何时分配CPU

—进程调度的时机HOW：如何分配CPU

—CPU调度过程（进程的上下文切换）作业是任务实体，进程是完成任务的执行实体;没有作业任务，进程无事可干，没有进程，作业任务没法完成。一个作业可由多个进程组成，且必须至少有一个进程，但反过来不成立。作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。作业是用户向计算机提交任务的任务实体。进程是计算机为完成用户任务而设置的执行实体，是系统分配资源的基本单位。一个作业可由多个进程组成，且必须至少有一个进程，但反过来不成立。作业和进程的关系

处理机三级调度1.高级(Long-term)调度——作业调度

作业调度用于决定把外存井上处于作业后备队列上的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。在批处理系统中，作业是先驻留在外存的输入井上的，因此需要有作业调度；在分时系统中，通过键盘输入的命令和数据直接进入内存，无需作业调度。2.低级(Short-term)调度——进程调度

进程调度决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。进程调度是最基本的调度，任何操作系统都有进程调度。低级调度：最基本。各类0S必须具有的功能。中级调度：较完善的OS中，引入其来改善内存的利用率和提高作业的吞吐量。高级调度：批处理OS必须配置，纯粹的分时或实时OS中，通常无须配置。提交状态收容状态完成状态外存内存分级调度作业的状态及其转换就绪等待就绪等待执行输入管理系统交换调度线程调度进程调度作业调度提交状态：作业处于从输入设备进入外存的过程；收容状态：作业的全部信息被输入到输入井，尚未被调度执行；完成状态：作业运行完毕，所占资源尚未被收回。作业状态一个作业从提交给计算机系统到执行结束退出系统，一般都要经历提交、后备、执行和完成等4个状态。提交状态：一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态。后备状态：也称为收容状态。若一个作业的全部信息已全部被输入进输入井，则在它还未被调度去执行之前，该作业处于后备状态。执行状态：作业调度程序从后备作业中选取若干个作业到内存投入运行。它为被选中作业建立进程并分配必要的资源，这时，这些被选中的作业处于执行状态。完成状态：当作业运行完毕，但它所占用的资源尚未全部被系统回收时，该作业处于完成状态。调度的层次提交状态收容状态完成状态外存内存就绪等待就绪等待执行输入管理系统交换调度线程调度进程调度作业调度第1级：作业调度、宏观调度、高级调度对外存输入井上的大量作业进行选择，对选择的作业分配资源，建立相应进程。作业执行完毕时，回收资源。分级调度调度的层次提交状态收容状态完成状态外存内存就绪等待就绪等待执行输入管理系统交换调度线程调度进程调度作业调度第2级：交换调度、中级调度将处于外存交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换导外存交换区。分级调度调度的层次提交状态收容状态完成状态外存内存就绪等待就绪等待执行输入管理系统交换调度线程调度进程调度作业调度第3级：进程调度、微观调度、低级调度选取一个处于就绪状态的进程占用处理机，之后，进行上下文切换以便建立与占用处理机进程相适应的执行环境。分级调度调度的层次提交状态收容状态完成状态外存内存就绪等待就绪等待执行输入管理系统交换调度线程调度进程调度作业调度第4级：线程调度选取一个处于就绪状态的线程进入执行状态。分级调度3.1.3处理机调度模型分时间片完完成CPU交互型作业等待事件活动就绪队列静止就绪队列静止阻塞队列活动阻塞队列事件发生作业调度后备作业队列批量作业中级调度调入中级调度调出磁盘进程调度中级调度调出事件发生具有三级级调度的调度队列模型作业后备状态执行状态完成状态4.2.1作业调度的功能记录系统中各作业的状况系统为每个作业建立一个JCB记录作业信息，系统通过JCB感知作业的存在。作业名作业类型资源要求资源使用情况优先级（数）当前状态其它作业进入后备状态时，系统为其建立JCB；作业进入完成状态后，系统撤销其JCB。作业调度1作业调度的功能记录系统中各作业的状况从后备队列中选择一部分作业投入运行（涉及调度算法）为被选中的作业做好执行前的准备（建立进程、为进程们分配系统资源）作业执行结束时的后处理作业调度2作业调度目标目标公平性：对所有作业应该是公平的利用率：应使设备有高的利用率作业量：每天执行尽可能多的作业响应时间：有快的响应时间作业调度3作业调度性能衡量面向用户的调度性能准则周转时间：作业从提交到完成（得到结果）所经历的时间。周转时间Ti=作业完成时刻(Tei)-作业提交时刻(Tsi)=作业等待时间(Twi)+作业执行时间（Tri)平均周转时间作业调度3作业调度性能衡量面向用户的调度性能准则带权周转时间带权周转时间Wi=Ti/Tri平均带权周转时间响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间——分时系统作业调度3作业调度性能衡量面向系统的调度性能准则吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系——批处理系统处理机利用率：——大中型主机各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配——大中型主机作业调度1先来先服务按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。

FCFS算法当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）最简单的算法

FCFS特点比较有利于长作业，而不利于短作业有利于CPU繁忙的作业，而不利于I/O繁忙的作业调度算法2短作业／进程优先(SJF/SPF)调度算法

(SJF,ShortestJobFirst)

SJF算法对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业

SJF优点比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间提高系统的吞吐量调度算法2短作业优先

(SJF,ShortestJobFirst)

SJF缺点对长作业非常不利，可能长时间得不到执行未能依据作业的紧迫程度来划分执行的优先级难以准确估计作业（进程）的执行时间，从而影响调度性能调度算法先来先服务调度算法和短作业优先调度算法作业提交时间运行时间开始时间完成时间周转时间带权周转时间执行顺序18.002.0028.500.5039.000.1049.500.208.0010.0012110.0010.5022410.5010.6031.61610.6010.8041.36.58.0010.0012110.0010.1021.11110.1010.3030.8410.3010.8042.34.6先来先服务算法平均周转时间t=1.725带权平均周转时间w=6.875短作业优先算法平均周转时间t=1.55带权平均周转时间w=5.154时间片轮转算法

(RoundRobin)

说明前两种算法主要用于宏观调度，说明怎样选择一个进程或作业开始运行，开始运行后的作法都相同，即运行到结束或阻塞，阻塞结束时等待当前进程放弃CPU本算法主要用于微观调度，说明怎样并发运行，即切换的方式；设计目标是提高资源利用率其基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率调度算法4时间片轮转算法

(RoundRobin)RoundRobin算法将系统中所有的就绪进程按照FCFS原则，排成一个队列当执行的时间片用完时，调度程序便停止该进程的执行，并将它送就绪队列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片保证就绪队列中的所有进程，在一给定的时间内，均能获得一个时间片的处理机执行时间进程可以未使用完一个时间片，就出让CPU（如阻塞）F…DCBACPU阻塞完成超时调度算法4时间片轮转算法

(RoundRobin)

时间片长度的确定（时间片的长度从几个ms到几百ms）时间片长度变化的影响过长退化为FCFS算法，进程在一个时间片内都执行完，响应时间长过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长调度算法7多级反馈队列算法(RoundRobinwithMultipleFeedback)多级反馈队列算法（目前公认的较好的一种进程调度算法）设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长。新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成；仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果有新进程进入优先级较高的队列，则此时新进程将抢占正在运行进程的处理机，并把被抢先的进程投入原队列的末尾。（抢占式调度方式）调度算法多级反馈队列

在两道环境下有四个作业,已知它们进入系统的时间、估计运行时间,系统采用短作业优先作业调度算法，作业被调度运行后不再退出内存,当一新作业投入运行后，可按照作业运行时间长短调整作业执行的次序（可抢占式调度占用CPU）请给出这四个作业的执行时间序列，并计算出平均周转时间及带权平均周转时间调度算法应用举例最短作业优先算法执行结果最短作业优先算法执行分析过程10：00，JOB1进入，只有一作业，JOB1被调入执行，10：05，JOB2到达，最多允许两作业同时进入，所以JOB2也被调入内存中有两作业，哪一个执行？题目规定当一新作业运行后，可按作业运行时间长短调整执行次序即基于优先数可抢占式调度策略，优先数是根据作业估计运行时间大小来决定的，由于JOB2运行时间（20分）比JOB1少（到10：05，JOB1还需25分钟），所以JOB2运行，而JOB1等待调度算法应用举例最短作业优先算法执行分析过程10：10，JOB3到达输入井，内存已有两作业，JOB3不能马上进入内存；10：20，JOB4也不能进入内存，10：25，JOB2运行结束，退出，内存中剩下JOB1，输入井中有两作业JOB3和JOB4，如何调度？作业调度算法：最短作业优先，因此JOB3进入内存，比较JOB1和JOB3运行时间，JOB3运行时间短，故JOB3运行，同样，JOB3退出后，下一个是JOB4，JOB4结束后，JOB1才能继续运行。调度算法应用举例1.死琐概念死锁是指多个并发执行的进程因争夺资源而出现的一种彼此都不能继续推进的僵持局面。死锁（Deadlock）产生死锁的原因和必要条件2.产生死锁的原因竞争资源进程间推进顺序非法2.产生死锁的原因竞争资源资源分为可重用资源和临时性资源重用资源又分为可剥夺资源和非剥夺资源。可剥夺资源：CPU，存储器非剥夺资源：打印机竞争重用资源，且数量不能满足进程运行需要，就会陷入僵局。又如：200K的可用内存，

P1，P2都进行到第二步时，死锁发生。P1......Request80Kbytes;Request60Kbytes;P2......Request70Kbytes;Request80Kbytes;产生死锁的原因和必要条件2.产生死锁的原因进程间推进顺序非法（进程的异步性特征）

进程P进程QGetA GetB…… ……GetB GetA…… ……ReleaseAReleaseB…… ……ReleaseBReleaseA37正确模式

进程P进程QGetA GetB…………ReleaseAReleaseB…… ……GetB GetA…… ……ReleaseBReleaseA

进程在申请资源时，用完一个资源释放后再申请下一个资源。3.5产生死锁的原因和必要条件38正确模式

进程P进程QGetA GetA…… ……GetB GetB…… ……ReleaseAReleaseA…… ……ReleaseBReleaseB两个进程按照相同的顺序申请使用资源3.5产生死锁的原因和必要条件39产生死锁的原因和必要条件3.产生死锁的必要条件互斥条件Mutualexclusion一段时间内，某资源只能由一个进程占用。是临界资源本身的固有属性。请求和保持条件Hold-and-wait保持已经获得资源不放，继续提出新的资源需求。不剥夺条件Nopreemption进程已获得资源在未使用完前不能被剥夺。环路等待条件系统一定有两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待着相邻进程正占用着的资源产生死锁的原因和必要条件处理死锁的四种策略预防死锁通过破除死锁的四个必要条件之一，来防止死锁产生。避免死锁仔细地对资源进行动态分配，以避免死锁发生。检测与解除死锁检测系统中是否出现死锁，若出现则解除掉。忽略该问题允许系统发生死锁，然后解除假装死锁永不发生保证系统永远不会发生死锁预防和避免死锁的方法预防死锁如果能够保证四个必要条件中至少有一个不成立，那么死锁将不会产生。（Havender，1968）但其中的“互斥”条件不能破除。预防和避免死锁的方法摒弃“请求和保持”条件方法规定进程在执行前要一次性地申请运行所需全部资源。只有资源全部到手，进程方可运行，否则进程等待。优点简单、易于实现缺点资源利用率低进程运行被延迟预防和避免死锁的方法摒弃“不剥夺”条件方法保持资源的进程申请新资源失败时，在转为阻塞状态之前，必须释放其占用的全部资源。而该进程自身则必须等到重新获得原有资源及新资源后，才能重新运行。缺点实现复杂，代价大3.6预防和避免死锁的方法摒弃“环路等待”条件方法1保证每个进程在任何时候只能占用一个资源。要用第二个，必须先释放第一个。方法2对资源按类型线性排队编号，进程对资源的请求必须按照资源序号递增提出。缺点：1.找不出一种人人满意的编号顺序。

2.仍存在资源浪费。

3.用户编程受到限制。4.限制新类型设备增加预防和避免死锁的方法避免死锁思路允许进程动态的申请资源将系统状态分为安全状态：不会发生死锁不安全状态：可能发生死锁避免系统进入不安全状态！做法每次进行资源分配时，首先检测一下资源分配后系统处于何种状态，若处于安全状态，则正式实施本次分配；若处于不安全状态，则不予分配，申请资源的进程阻塞。46预防死锁的方法系统安全状态（用于避免死锁）安全状态：系统能按某种进程顺序(P1,P2,…，Pn)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。称(P1,P2,…,Pn)序列为安全序列预防和避免死锁的方法例，系统有三个进程P1、P2和P3，共用12台磁带机。在T0和T1时刻，系统的资源分配情况分别如下表a和b。进程最大需求已分配可用

P11053

P242P392进程最大需求已分配可用

P11052

P242P393ab预防和避免死锁的方法结果：T0时刻系统处于安全状态。（安全序列<P2

，P1，P3

>）P1P2P3可用5(5)2(2)2(7)35(5)4(0)2(7)15(5)2(7)510(0)2(7)02(7)109(0)312结果：T1时刻系统处于不安全状态。P1P2P3可用5(5)2(2)3(6)25(5)4(0)3(6)05(5)3(6)449利用银行家算法避免死锁避免死锁策略1.当前状态下，某进程申请资源；2.系统假设将资源分给该进程，满足它的需求；3.检查分配后的系统状态是否是安全的，如果是安全，就确认本次分配；如果系统是不安全的，就取消本次分配并阻塞该进程。（第三步又称安全算法）避免死锁策略也称作银行家算法。避免死锁实质：在进程资源分配时，如何使系统不进入不安全状态。预防和避免死锁的方法预防和避免死锁的方法利用银行家算法避免死锁数据结构—n个进程(P1,…,Pn)，m类资源(R1,…,Rm)可利用资源向量Available（m）Available[j]表示Rj

类资源的可用数目。最大需求矩阵Max（n×m）Max[i,j]表示进程Pi

对Rj

类资源的最大需求量。分配矩阵Allocation（n×m）Allocation[i,j]表示已分配给进程Pi

的Rj

类资源的数目。需求矩阵Need（n×m）Need[i,j]表示进程Pi

对Rj

类资源的剩余需求量Requesti

：进程Pi

的请求向量预防和避免死锁的方法银行家算法：进程Pi

发出资源请求RequestiRequestiNeedi?

执行安全性算法，检查分配后的系统状态正式分配安全状态Requesti

Available?是

试分配：Available:=AvailableRequestiAllocationi:=Allocationi+RequestiNeedi:=Needi

Requesti是将试分配作废；恢复原资源分配状态；进程Pi阻塞。不安全状态错误否否进程Pi阻塞3.6预防和避免死锁的方法安全性算法Work:=Available;Finish[i]:=false(i=1,2,…,n);找一满足下列条件的进程：Finish[i]=false且Needi

WorkWork:=Work+Allocationi;

Finish[i]:=true;找到

所有进程的Finish[i]=true？找不到是系统状态安全不是系统状态不安全预防和避免死锁的方法例：系统中有五个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C}，每类资源的数量分别为10、5、7，在T0时刻的资源分配情况如下表。问：P1发出请求向量Request1(1,0,2)，能否分配？ProcessMaxAllocationNeedAvailableABCABCABCABCP0753010743332P1 322200122P2 902302600P3222211011P4433002431ProcessMaxAllocationNeedAvailableP0753010743332P1 322200122P2 902302600P3222211011

P4433002431230020302结论：可以找到一个安全序列<p1,p3,p4,p2,p0>，所以安全，可以将P1申请的资源分配给它。Request1(1

,0

,2)试分配（结果见红字）安全性算法：Work={230}Finish=

falsefalsefalsefalsefalsetrue532743true745true1047true1057true死锁的检测与解除死锁的检测资源分配图RAG（ResourceAllo