计算机操作系统处置机调度和死锁专业知识讲座

第一节

处理机调度的层次高级调度低级调度中级调度1、高级调度（作业/长程/接纳调度）高级调度：根据某种算法，把外存上处于后备队列中的作业调入内存，并为它们创建进程、分配必要的资源，准备执行。多用于批处理系统每次调度时要考虑：

(1)接纳多少作业：取决于多道程序度(2)接纳哪些作业：取决于调度算法FCFS、SJF作业调度运行频率低，几分钟一次低级调度：决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。是最基本的调度，在三种类型的OS中都必须配置运行频率高，几十毫秒一次，算法不能太复杂进程调度采用两种方式：非抢占方式、抢占方式非抢占方式（非剥夺方式）：一旦进程获得处理机，则一直执行，直到该进程完成或被阻塞优点：简单、系统开销小，适合大多数批处理系统缺点：无法满足紧急任务的需要，不适合实时系统2、低级调度（进程/

短程调度）抢占方式（剥夺方式）

：允许调度程序根据某原则，暂停正在执行的进程，将处理机重新分配抢占原则：优先权原则就绪的高优先权进程有权抢占低优先权进程的CPU短作业优先原则就绪的短作业(进程)有权抢占长作业(进程)的CPU时间片原则一个时间片用完后，系统重新进行进程调度中级调度：按一定的算法将外存上已具备运行条件的挂起进程换入内存，挂到就绪队列上，准备执行；而将内存中处于阻塞状态的某些进程换出至外存。目的：为了解决内存紧张问题，常用于分时系统总结——引起进程调度的原因有：进程正常终止或异常终止正在执行的进程因某种原因而阻塞（I/O请求）分时系统中时间片用尽当有一个优先级更高的进程就绪（可抢占式）在进程通信或同步中，执行了某种原语操作，如P操作、Block原语、Wakeup原语等3、中级调度（中程调度）第二节

调度队列模型和调度准则调度队列模型调度方式和算法的选择准则1、调度队列模型就绪队列阻塞队列CPU时间片完交互用户进程调度进程完成等待事件事件发生仅具有进程调度的调度队列模型1、调度队列模型……就绪队列阻塞队列CPU时间片完作业调度进程调度进程完成等待事件1阻塞队列阻塞队列等待事件2等待事件n事件1发生事件2发生事件n发生后备队列具有高、低两级调度的调度队列模型1、调度队列模型就绪队列绪就、挂起队列CPU时间片完作业调度进程调度进程完成事件发生阻塞队列挂起等待事件中级调度事件发生后备队列塞阻、挂起队列挂起具有高、低、中三级调度的调度队列模型2、调度方式和算法的选择准则面向用户的准则周转时间短——评价批处理系统

周转时间：是指从作业被提交系统开始，到作业完成为止的这段时间间隔。包括四部分：等待作业调度时间、等待进程调度时间、执行时间、进程等待I/O操作完成时间。平均周转时间、带权周转时间响应时间快——评价分时系统

响应时间：从用户通过键盘提交一个请求开始直至系统首次产生响应为止。

包括三部分：从键盘输入的请求信息传送到处理机的时间、处理时间、响应信息回送终端的时间。截止时间的保证——评价实时系统截止时间：是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。优先权准则——三种系统中皆适用面向系统的准则系统吞吐量高——评价批处理系统处理机利用率好——针对大中型系统各类资源的平衡利用——对大中型系统第三节

调度算法先来先服务短作业（进程）优先高优先权优先调度时间片轮转多级反馈队列1、先来先服务（FCFS）可用于作业调度和进程调度用于作业调度：每次从后备作业队列中选择最先进入的作业，将它们调入内存，为它们分配资源、创建进程，然后挂到就绪进程队列上。用于进程调度：每次从就绪进程队列中选择最先进入的进程，为之分配处理机，使之投入运行。直到运行完成进程才会让出处理机--非抢占式。有利于长作业，而不利于短作业。进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99性能评价：周转时间=完成时间–到达时间带权周转时间=周转时间/服务（运行）时间2、短作业/进程优先（SJ/PF）短作业优先（SJF）从后备队列中选择估计运行时间最短的作业，调入内存运行。短进程优先（SPF）从就绪队列中选出估计运行时间最短的进程，将处理机分配给它，使它立即执行。直到运行完成进程才会让出处理机--非抢占式。缺点：对长作业不利，有可能长期不被调度；完全没考虑作业的紧迫程度（某些特殊的）；用户做出的估计时间带有很大的主观性。2.259133.5141844E3.116182101252C2.678926731B1.5365.5111423D2.11带权周转时间84周转时间4完成时间FJS2.81带权周转时间94周转时间4完成时间FCFS4服务时间0到达时间平均A进程名作调业度情算况法周转时间=完成时间–到达时间带权周转时间=周转时间/服务时间3、高优先权优先调度算法（HPF）既能用于作业调度，也可用于进程调度。作业调度：从后备队列中选择若干个优先权最高的作业装入内存。进程调度：把处理机分配给就绪队列中优先权最高的进程两种占用CPU的方式：非抢占式、抢占式非抢占式优先权算法：抢占式优先权算法：注：规定优先数越小，其优先权越高4/348334C15/81517482B119118D带权周转时间周转时间155完成时间2优先数非抢占式优先权算法5服务时间0到达时间A进程名作调业度情算况法平均6.251.3关键：优先权的确定优先权类型一：静态优先权在进程创建时确定的，在进程整个运行期间保持不变t(等待)优先权t(运行)优先权优先权类型二：动态优先权在进程创建时创立的优先权，可随进程的推进或等待时间的增加而改变。如等待时间长，优先权升高。高响应比优先调度算法(HRRN)为每个进程引入动态优先权，随着等待时间增加优先权提高。优点：等待时间相同，短作业优先权高(即SPF)要求服务时间相同，等待时间长，优先权高(即FCFS)对于长作业，在等待足够时间后，可获得处理机3.571528E2.2591344C1.177962B2.8142056D2.141带权周转时间83周转时间3完成时间3服务时间0到达时间平均A进程名作调业度情算况法RC＝1+(9-4)/4=2.25RD＝1+(9-6)/5=1.6RE＝1+(9-8)/2=1.5RD＝1+(13-6)/5=2.4RE＝1+(13-8)/2=3.5执行顺序：A－>B－>C－>E－>DHRRN（R大，优先权高）4、时间片轮转（RR）特别适用于分时系统的抢占方式调度算法。系统将所有的就绪进程按FIFO原则排成一个队列，将CPU分配给队首进程，执行一个时间片。在时间片内进程未完，则插入就绪队列末尾，CPU交给下一个进程。时间片选择问题：固定时间片、可变时间片与时间片大小有关的因素：系统响应时间、就绪进程个数、CPU能力5、多级反馈队列设置多个就绪队列，并为各个队列赋予不同的优先级和不同长度的时间片；新创建的进程挂到第一优先级的队列后，然后按FCFS原则排队等待调度。当轮到其执行时，如它能在时间片内完成，便撤离系统；如果不能完成，便被挂入第二级队列后，……，最后一级队列采用时间片轮转法；仅当第一级队列空闲时，调度程序才调度第二级队列中的进程运行，依次类推……；新进程可抢占低级进程的处理机。……多级反馈队列调度算法示意图CPU时间片完进程调度进程完成就绪队列一就绪队列二就绪队列三就绪队列n时间片完时间片完多级反馈队列调度算法的性能多级反馈队列调度算法能较好地满足各种类型用户（进程）的需要：终端（交互）型作业用户短批处理作业用户长批处理作业用户思考：有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。下表所示为作业序列（表中作业优先数即进程优先数，数值越小优先级越高）。(1)列出所有作业进入内存时间及结束时间；(2)计算平均周转时间。作业到达时间估计运行时间优先数A10:0040分钟5B10:2030分钟3C10:3050分钟4D10:5020分钟6第四节实时调度实现实时调度的基本概念和条件实时调度算法的分类常见的几种实时调度算法选学1.实时调度是为了完成实时处理任务而分配处理机的调度方法。硬实时任务要求计算机系统必须在用户给定的时限内完成软实时任务允许计算机系统在用户给定的时限左右处理完毕。2.实现实时调度的基本条件(1)提供详细的调度信息：就绪时间、开始截止时间或完成截止时间、处理时间、资源要求、优先级等；(2)系统处理能力强；(3)采用抢占式调度机制：含有硬实时任务的实时系统中，广泛采用基于优先级的抢占式调度策略(4)具有快速切换机制；实时调度算法分类：非抢占式轮转调度算法：只适用于一般实时信息处理系统非抢占式优先级调度算法：优先级最高的实时任务排在就绪队列队首，当前任务终止或完成后才被调度。

基于时钟中断抢占式优先级调度算法：新到的实时任务的优先级高于当前任务时，并不立即抢占CPU，而是等到时钟中断到来，才进行切换。用于大多数的实时系统中。

立即抢占的优先级调度算法：这种算法适用于实时要求比较严格的实时控制系统。常用的几种实时调度算法1、最早截止时间优先算法（EFD）该算法根据任务的开始截止时间来确定任务的优先级。截止时间越早，优先级越高。该算法要求实时任务的就绪队列按任务截止时间的早晚排序。调度程序总选择队首的任务执行。

该算法可用于抢占式和非抢占式调度。t任务到达任务执行开始截止时间134211224433非抢占式调度方式2、最低松弛度优先算法（LLF）该算法根据任务的松弛度来确定任务的优先级。松弛度越低，优先级越高。松弛度＝任务必须完成的时间－运行时间－当前时间该算法要求实时任务的就绪队列按松弛度排序。调度程序总选择队首的任务执行。该算法主要用于抢占式调度方式。松弛度＝任务必须完成的时间－运行时间－当前时间例：实时系统中有两个周期性实时任务A、B，任务A每20ms执行一次，执行时间10ms；任务B每50ms执行一次，执行时间25ms。采用抢占式LLF算法：t020406080100120140160A1A2A3A4A5A6A7A8B1B2B3任务AB每次必须完成的时间松弛度t010203040455055607080A1=10B1=25A2=20B1=15A2=0B1=15A3=10B1=5A3=5B2=30此时执行B2A4=0B2=20A4完B2=10第五节

产生死锁的原因和必要条件产生死锁的原因产生死锁的必要条件1、产生死锁的原因死锁（Deadlock）：是指两个或两个以上的进程在运行过程中，因争夺资源而造成的一种互相等待（谁也无法再继续推进）的现象，若无外力作用，它们都将无法推进下去。产生死锁的原因：竞争资源进程间推进顺序非法1、竞争资源引起进程死锁：可剥夺性资源：CPU、RAM等；非剥夺性资源：打印机、磁带机等；永久性资源：打印机临时性资源：进程通信中的消息、数据等竞争非剥夺性资源：系统中配备的非剥夺性资源的数量不能满足诸进程运行的需要时，会使进程因争夺资源而陷入僵局。竞争临时性资源：打印机P1磁带机P22、进程间推进顺序不当引起死锁进程推进顺序合法——不会导致死锁进程推进顺序非法——可能会导致死锁顺序合法消息1P1消息2P2P3消息3顺序非法消息1P1消息2P2P3消息3DP2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)④②①③2、产生死锁的必要条件互斥条件（资源独占）一个资源一次只能被一个进程使用。请求和保持条件（部分分配）保留已经得到的资源，还要求其它的资源。不可剥夺条件（不可抢占）资源只能被占有者释放，不能被其它进程强行抢占。环路等待条件（循环等待）系统中的进程形成了环形的资源请求链。3、处理死锁的基本方法预防死锁避免死锁检测死锁解除死锁第六节预防死锁的方法预防死锁避免死锁1、预防死锁预防：通过设置某些限制条件，破坏导致死锁的四个必要条件之一。“互斥条件”——由资源的性质决定。摒弃“请求和保持”条件在开始运行前（创建时），一次性分配给进程它所需的“全部”资源。简单易实现，安全性高；资源浪费，进程延迟进行。摒弃“不可剥夺”条件当进程有新的资源请求时，如果得不到满足，要先释放原先占有的资源，待以后重新申请。等价于此进程“被剥夺”了已经占有的资源。实现比较复杂，系统代价很高。摒弃“循环等待”条件把系统资源按类型排序，进程要按照资源的序号递增的次序提出资源申请。较上述两种方法的综合性能要好；但系统配置资源的序号要稳定，固定的访问顺序不一定合理，限制了新资源的增加。例如：

进程A占有3号资源，现在又申请5号资源——占有资源号小于申请资源号，此申请可以满足。进程B占有5号资源，现在又申请3号资源——由于5>3，所以此申请不能满足。进程B要想得到3号资源，必须先放弃5号以及所有编号比3大的资源。例：哲学家就餐——给哲学家和筷子编号0－4信号量定义：varchopstick[0,…,4]ofsemaphore;信号量初值均为1；

第i(i=0,1,2,3)位哲学家活动描述：第4位哲学家活动描述:while(true){while(true){P(chopstick[i]);P(chopstick[0]);P(chopstick[(i+1)]);P(chopstick[4]); …………eating;eating; …………V(chopstick[i]);V(chopstick[0]);V(chopstick[(i+1)]);V(chopstick[4]); …………thinking;thinking;}}2、避免死锁避免死锁的方法：在资源的动态分配过程中，用某种方法防止系统进入不安全状态。安全状态：系统能按某种进程顺序(P1,P2,…,Pn)，来为每个进程Pi分配其所需资源，直至最大需求，使每个进程都可以顺利完成。反之，则系统处于不安全状态—可能发生死锁。不安全状态不一定发生死锁，但死锁一定属于不安全状态。2、避免死锁安全状态进程最大需求已分配系统可用P1P2P310495223系统资源总数：12不32存在安全序列：（P2,P1,P3）利用银行家算法避免死锁银行家算法的实质就是要设法保证系统动态分配资源后仍然保持安全状态，从而避免死锁的发生。要求进程预先告知自己的最大资源需求，并且假设系统拥有固定的资源总量。数据结构：可用资源向量Available最大需求矩阵Max

分配矩阵Allocation需求矩阵NeedNeed[i,j]=Max[i,j]-Allocation[i,j]

资源请求向量Requesti安全性算法：工作向量Work；Finish当进程Pi提出资源申请时，系统执行下列步骤：（1）若Requesti[j]≤Need[i,j](请求小于需求),转(2)；否则错误返回（2）若Requesti[j]≤Available[j](请求小于库存),转（3）；否则进程等待（3）假设系统分配了资源(试分配)，则有：

【库存】Available[j]:=Available[j]-Requesti[j];

【获取】Allocation[i,j]:=Allocation[i,j]+Requesti[j];

【需求】Need[i,j]:=Need[i,j]-Requesti[j]（4）执行安全性算法，若系统新状态是安全的，则分配完成，若是不安全的，则恢复原状态，进程等待银行家算法描述(1)Work[j]:=Available[j];Finish[i]:=false;(2)寻找满足下列条件的i：a)Finish[i]=false;b)Need[i,j]≤Work[j];【需求小于动态可分配资源】.如果不存在，则转(4)(3)进程i获取资源，然后执行完毕，并释放资源：Work[j]:=Work[j]+Allocation[i,j];Finish[i]:=true.转(2)(4)若对所有i,Finish[i]=true,则系统处于安全状态，否则处于不安全状态安全性算法步骤MaxAllocationNeedAvailableABCABCABCABCP0P1P2P3P4753322902222433010200302211002743122600011431332资源总数1057进程资源某时刻资源分配情况53274374510471057ABCWork＋AllocationABCABCABCtruetruetruetruetrue2002110023020101220114316007433325327437451047P1P3P4P2P0FinishAllocationNeedWork进程资源安全序列302020230(2)若此时P1请求资源，发出请求向量Request1(1,0,2)系统按银行家算法进行检查：

Request1(1,0,2)<=Need1(1,2,2)

Request1(1,0,2)<=Available(3,3,2)

系统先假定可为P1分配资源，并修改向量的值。

再利用安全性算法检查此时系统是否安全。

5327437457551057ABCWork＋AllocationABCABCABCtruetruetruetruetrue302211002010302020011431743600230532743745755P1P3P4P0P2FinishAllocationNeedWork进程资源安全序列ABCABCABCABC332资源总数1057743122600011431010200302211002753322902222433P0P1P2P3P4AvailableNeedAllocationMax进程资源某时刻资源分配情况302020230（3）若此时P4请求资源，发出请求向量Request4(3,3,0)系统按银行家算法进行检查：

Request4(3,3,0)<=Need4(4,3,1)

Request4(3,3,0)>Available(2,3,0)

因此，让P4等待。ABCABCABCABC332资源总数105774