计算机操作系统第四章

第4章调度与死锁主讲：王斯锋2023/2/51大学课件本章主要目录4.1调度的类型和模型4.2调度的算法4.3实时系统中的调度4.4多处理机调度4.6死锁的基本概念4.7死锁的预防和避免4.8死锁的检测和解除本章基础要点作业课后练习题及参考答案实战练习2023/2/52大学课件4.1调度的类型和模型4.1.1调度的类型一、高级调度二、低级调度三、中级调度4.1.2调度队列模型一、仅有进程调度的调度队列模型二、具有高级和低级调度的调度队列模型三、同时具有三级调度的调度队列模型4.1.3选择调度方式和算法的若干准则一、面向用户的准则二、面向系统的准则4.1.4进程调度的进一步理解4.1.5进程调度的功能2023/2/53大学课件多道程序环境下，进程数目往往多于处理机数目，致使它们争用处理机，这就要求系统能按某种算法动态地把处理机分配给就绪队列中的一个进程，使之执行进程。在多道程序系统中，一个作业从提交到执行，一般都经历多级调度。2023/2/54大学课件作业与作业管理1、作业与作业步作业：是用户要求计算机系统所做的一个计算问题或一次事务处理的完整过程。任何一个作业都要经过若干个步骤之后，才能得到结果，称每一个加工步骤为一个“作业步”。一个作业的各个作业步之间是有联系的，上一个作业步的输出是下一下作业步的输入。2、作业控制块创建一个进程时，要开辟一个进程控制块PCB，随时记录进程的信息。把一个作业提交给系统时，也要开辟一个作业控制块JCB，随时记录作业的信息。2023/2/55大学课件作业控制块的内容用户名作业名作业类别作业现行状态内存需求量作业优先数外设类型与需求数量作业提交时间作业运行时间(估计)作业控制块JCB指针其他2023/2/56大学课件作业从提交给系统直到它完成后离开系统前的整个活动常划分为若干个阶段。作业在每一阶段中所处的状况称为作业的状态。系统中的作业通常分为四种状态：2023/2/57大学课件(1)提交状态：进入外存，作业的一个暂时性的状态，其信息还没有全部进入系统，也没有建立JCB，感知不到它的存在。(2)后备状态(收容状态)：系统收到其全部信息，为其建立JCB，形成后备作业队列，系统能感知到它的存在。2023/2/58大学课件(3)运行状态：由作业调度进入了进程调度阶段。(4)完成状态：作业运行结束后的一个状态，是一个暂时性状态。2023/2/59大学课件Windows2000/XP中的作业是共享一组配额限度和安全性限制的进程集合；进程是内存资源分配和打开文件个数的基本单位；线程是操作系统调度处理器的执行单位。一个作业可以包含一个或多个进程，一个进程可以包含一个或多个线程。一个进程只能属于一个作业，一个线程只能属于一个进程。2023/2/510大学课件系统的运行性能，如：吞吐量的大小、周转时间的长短、响应的及时性等，很大程度上都取决于调度。调度成为多道系统的关键。分配处理机的任务是由进程调度程序Scheduler完成的。2023/2/511大学课件4.1调度的类型和模型从不同的角度进行分类，常用分类方法是按调度的层次，把调度分为高级、中级和低级调度；另一种分类是按OS的类型分类，调度分为批处理调度、分时调度和实时调度及多处理机调度。4.1.1调度类型作业从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，要经历下述三级调度。2023/2/512大学课件一、高级调度，又称作业调度或长程调度或宏观调度。常用于批处理系统，分时和实时都没有作业：是用户向计算机提交任务的任务实体。进程：是计算机为了完成任务实体而设置的执行实体，是系统分配资源的基本单位。一个作业总是由一个以上的多个进程组成的。2023/2/513大学课件执行作业调度时，需解决两个问题：1、接纳多少个作业作业调度接纳多少个作业进入内存，取决于多道程序度，即允许有多少个作业同时在内存中运行。2023/2/514大学课件2、接纳哪些作业2023/2/515大学课件二、低级调度，又称进程调度、短程调度、微观调度。最基本的调度，三种类型的操作系统中必须都配置。2023/2/516大学课件后备队列就绪队列I/O阻塞队列高级调度CPU低级调度I/Oend2023/2/517大学课件1、非抢占方式(非剥夺方式)nonpreemptive2、抢占方式(剥夺方式)preemptive,又称抢夺、抢用、强抢、抢先、剥夺。2023/2/518大学课件(1)时间片原则。(2)优先权原则。(3)短作业(进程)优先原则。3、完全可抢先fullypreemptive是指任何时间，不管进程处于用户态还是核心态，都可以随时被更高优先级的进程抢用CPU。2023/2/519大学课件(1)完全不可抢先或用户态不可抢先：当前进程不论在用户态或核心态时，都不可以被抢用CPU，这种操作系统称为不可抢先式的操作系统。如：windows98和windows95(2)内核完全不可抢先：当前进程在用户态时可以被抢占，但当在核心态时不可被抢占。如：传统的UNIX3或4.3BSDUNIX、windowsNT2023/2/520大学课件(3)内核的部分可抢先：用户态时可被抢占，核心态时大部分时间不可抢占，而只在某些时刻点(可抢先点，preemptionpoint)时可被抢占。UNIXSVR4(4)完全可抢先或内核完全可抢先：无论任何状态都可以被抢占。如SUN公司的Solaris2023/2/521大学课件三、中级调度，又称中程调度、交换调度。分时系统中常用，主要任务是将内存处于阻塞状态的某些进程调到外存。

2023/2/522大学课件引入中级调度的目的是，为提高内存的利用率和系统吞吐量。中级调度实质上是存储器管理中的对换功能。2023/2/523大学课件三种调度，进程调度的运行频率最高，其调度算法不能太复杂，以免占用太多的CPU时间。作业调度发生在一个作业运行完毕，退出系统时又要重新调入一个作业进入内存时，调度的周期长，其调度算法花费较多的时间。中级调度的运行频率介于两种之间。2023/2/524大学课件***4.1.2调度队列模型在上述的三种调度中，都涉及进程队列，形成了三种类型的调度队列模型。一、仅有进程调度的调度队列模型分时系统中仅有进程调度。用户的命令直接送入内存，OS对每个命令命令建立一个进程，按时间片轮转运行。2023/2/525大学课件每个进程执行时，可能出现三种情况：(1)该任务在该时间片内已经完成，该进程释放处理机后进入完成状态。(2)任务在本次其对应的时间片内尚未完成，OS将该任务放在就绪队列的后面。(3)在执行期间，进程因某事件而被阻塞后，OS将它放入阻塞队列。其调度队列模型如图：2023/2/526大学课件列队绪就列队塞阻CPU等待事件进程调度进程完成交互用户时间片完事件出现内存2023/2/527大学课件二、具有高级和低级调度的调度队列模型如图示：具有高级和低级调度的调度队列模型，它与上一模型的区别：(1)OS中既引入了进程调度，又引入了作业调度。后者从外存的后备队列选择一批作业调入内存，并创建进程，然后，送入就绪队列。(2)OS中设置多个阻塞队列。每个队列对应一种引起进程阻塞的事件。2023/2/528大学课件列队绪就CPU等待事件1等待事件n等待事件2进程调度时间片完事件1出现事件2出现事件n出现作业调度后备队列2023/2/529大学课件三、同时具有三级调度的调度队列模型

OS引入中级调度后，可把进程的就绪状态分为内存就绪状态(表示进程在内存中就绪即活动就绪)、外存就绪状态(进程在外存中就绪即静止就绪)。也可把阻塞状态分成内存阻塞(活动阻塞)和外存阻塞(静止阻塞)。

2023/2/530大学课件三级调度的调度队列模型如图示：2023/2/531大学课件CPU阻塞队列阻塞，挂起队列就绪，挂起队列就绪队列时间片完后备队列作业调度批量作业交互型作业中级调度事件出现挂起等待事件进程完成进程调度事件出现2023/2/532大学课件4.1.3选择调度方式和算法的若干准则(面向用户和面向系统)选择调度方式和算法，取决于OS的类型和目标，选择调度方式和算法的准则，有的是面向用户的，有的是面向系统的。2023/2/533大学课件一、面向用户的准则1、周转时间短，批处理系统中。所谓周转时间，指从作业提交给系统开始，到作业完成为止的时间间隔，又称作业周转时间。包括：2023/2/534大学课件(1)作业在外存后备队列上等待(作业)调度的时间(2)进程在就绪队列上等待进程调度的时间。(3)进程在CPU上执行的时间。(4)等待I/O操作完成的时间。

2023/2/535大学课件作业周转时间与系统为它提供的实际服务时间Ts之比，称为带权周转时间。W=T/Ts，平均带权时间表示为：2、响应时间快，分时系统中。用于评价分时系统的性能，是选择分时系统中进程调度算法的重要准则。2023/2/536大学课件响应时间，是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或说直到在屏幕上显示出结果为止的一段时间间隔。包括：2023/2/537大学课件(1)从键盘输入的请求信息传送到处理机的时间。(2)处理机对请求信息进行处理的时间。(3)将所形成的响应回送到终端显示器的时间。2023/2/538大学课件3、截止时间的保证，实时系统中。所谓截止时间，是指某任务必须开始执行的最迟时间（截止开始），或必须完成的最迟时间（截止结束）。2023/2/539大学课件4、优先权准则批处理、分时和实时系统中，都可引用优先权准则，让某些紧急的作业，得到及时的处理。严格的场合，还可选择抢占调度方式。二、面向系统的准则2023/2/540大学课件1、系统吞吐量高用于评价批处理系统性能的重要指标。吞吐量是指在单位时间内所完成的作业数。它与作业的平均长度有密切关系。作业的调度方式和算法，对吞吐量的大小也产生影响。2023/2/541大学课件2、处理机利用率好实际系统中，CPU的利用率在40%到90%之间。对大、中型多用户系统，处理机的利用率成为衡量性能的重要指标。2023/2/542大学课件3、各类资源的平衡利用选择适当的调度方式和算法，能保持系统中各类资源都处于忙碌状态。如：内存、外存、I/O设备等。2023/2/543大学课件进程调度的进一步理解作业调度程序在挑选作业进入主存运行时，要为该作业建立相应的进程。在作业完成后要撤消该作业的全部进程。因此作业调度程序要调用操作系统内核所提供的有关的进程管理原语，如“建立进程”原语和“撤消进程”等原语2023/2/544大学课件由于进程只能由其父进程建立，所以在一般系统中，作业调度程序都以进程的形式在系统中存在和活动，称为作业调度进程。作业调度进程可以说是系统中的祖先进程，由它完成作业调度的诸功能。2023/2/545大学课件进程调度的功能是从就绪队列中挑选一个进程到处理机上运行。负责进程调度功能的内核程序称为进程调度程序。2023/2/546大学课件读者往往不易分清作业调度程序挑选作业进入主存运行和进程调度程序挑选一个进程到处理机上运行，这两种运行之间有何区别。2023/2/547大学课件所谓作业调度程序挑选作业进主存运行是个宏观的概念，实际上被选进主存运行的作业只是具有了竞争处理机的机会(将来真正在处理机上运行的是该作业的一个进程)。而进程调度程序才是真正让某个就绪进程到处理机上运行。2023/2/548大学课件由于进程调度程序负责在就绪进程间转接对处理机的控制，所以对它的调用相当频繁，每秒要执行很多次。它是操作系统核心(常称为内核)的重要组成部分。进程调度程序在系统中以原语形式存在，它是为进程在系统内的活动提供支持。2023/2/549大学课件进程调度的功能进程调度程序的具体功能如下：1、记录系统中所有进程的有关情况及状态特征。为了实现进程调度，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的PCB中，同时还应根据各进程的状态特征和资源需求等信息将进程的PCB组织成相应的队列，并依据运行情况将进程的PCB在不同状态队列之间转换。进程调度模块通过PCB的变化来掌握系统中所有进程的执行情况和状态特征。2023/2/550大学课件2、选择获得处理机的进程按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。根据不同的系统设计目标，有各种各样的选择策略。例如先来先服务调度算法、时间片轮转调度算法等。这些选择策略决定了调度算法的性能。2023/2/551大学课件3、处理机分配当正在运行进程由于某种原因要放弃处理机时，进程调度程序应保护当前运行进程的CPU现场，将其状态由运行变成就绪或阻塞，并插入到相应队列中去，同时调度程序还应根据一定原则从就绪队列中挑选出一个进程，把该进程从就绪队列中移出，恢复其CPU现场，并将其状态改变为运行。2023/2/552大学课件引起进程调度的原因有以下几种：(1)当前运行进程运行结束。因任务完成而正常结束，或者因出现错误而异常结束。(2)当前运行进程因某种原因，比如I/O请求，从运行状态进入阻塞状态。(3)当前运行进程执行某种原语操作，如P操作、阻塞原语等，进入阻塞状态。2023/2/553大学课件(4)执行完系统调用等系统程序后返回用户进程，这时可以看作系统进程执行完毕，从而可以调度一个新的用户进程。(5)在采用剥夺调度方式的系统中，一个具有更高优先级的进程要求使用处理机，则使当前运行进程进入就绪队列(这与调度方式有关)。(6)在分时系统中，分配给该进程的时间片已用完(这与系统类型有关，多用于分时系统中)。2023/2/554大学课件选择调度算法时应考虑的问题在设计系统的调度程序时，首先要决定选择何种调度算法，依据此算法来编制相应的调度程序。而调度算法实际上就是系统所采取的调度策略，选择时所要考虑的因素很多。如：系统各类资源的均衡使用，对用户公平并使用户满意，用户作业到达系统的时间，作业的优先数，对主存和外设的要求，以及整个系统的效率等。2023/2/555大学课件但这些因素之间往往相互矛盾，很难兼顾。所以设计时应将那些对系统运行影响较大的关键因素作为调度算法考虑的主要依据。通常应考虑以下因素：2023/2/556大学课件(1)设计目标：系统的设计目标是选择算法的主要依据，目标不同，系统的设计要求自然不同。2023/2/557大学课件如：批处理系统所追求的是充分发挥和提高计算机的效率；实时系统所关心的是不要丢失实时信息并及时给以处理；分时系统则侧重于保证用户的请求及时给予响应，计算中心要求系统吞吐量要大等等。2023/2/558大学课件(2)资源利用率：这是评价系统性能优劣的重要指标。因此在确定算法时，在考虑设计目标的前提下应充分发挥各种资源的效能，最大限度地使它们忙碌。2023/2/559大学课件如：将科学计算型(CPU型)作业和数据处理型(输入输出型)作业搭配运行就是一种方法。为了充分提高资源利用率还应注意照顾正在使用关键资源的进程，使之优先运行。2023/2/560大学课件(3)均衡地处理系统和用户的要求：由于系统和用户的要求往往是矛盾的，确定算法时也要设法给予缓和。2023/2/561大学课件一般说来，用户本能地希望尽快获得运行结果。但系统有时却不能立即满足用户要求。如：个别用户可能要求使用系统中的几乎全部外设，却只要求很少的主存。系统若满足这类用户的愿望，势必影响主存利用率，从而降低系统效率，所以一般都不得不推迟这种作业的运行时间，等到有要求内存多而外设少的作业与之搭配运行。2023/2/562大学课件但是我们选择的算法也不应使一个作业的运行被无限制地推迟。这是用户无法忍受的。解决的办法是使进程优先数随等待时间而增加。2023/2/563大学课件(4)在使用优先级的系统中，每个进程都有一个优先数(或优先级)，调度算法应优先运行高优先级进程。2023/2/564大学课件(5)在使用优先数的系统中，调度策略还分为“可抢占”和“不可抢占”两种方式。所谓“不可抢占”是指一旦某个进程分得处理机后，除非它因等待某事件发生或已完成其任务而主动让出处理机外，不得将处理机从该进程抢走给其它进程使用。2023/2/565大学课件所谓“可抢占”是指可以将处理机从该进程抢占给其它进程使用，即使该进程仍然需要处理机。抢占策略通常适用于需要迅速响应高优先级进程的系统中。但抢占策略要增加系统两个方面的开销：2023/2/566大学课件首先是增加了处理机在进程间转接的次数，消耗处理机机时。其次系统为提高抢占工作的效率，在主存中要存放多个作业(进程)，以保证抢占后，该进程可立即投入运行，这又增加了不运行进程占用主存的开销。2023/2/567大学课件4.2调度算法4.2.1先来先服务调度算法一、调度算法

二、FCFS实例4.2.2短作业(进程)优先调度算法4.2.3时间片轮转调度算法一、基本原理

二、时间片大小的确定4.2.4优先权调度算法一、优先权调度算法的类型二、优先权的类型2023/2/568大学课件4.2.5高响应比优先调度算法4.2.6最短剩余时间优先调度算法练习4.2.7多级队列调度4.2.8多级反馈队列调度算法一、调度算法二、多级反馈队列算法的性能4.2.9彩票调度算法LotteryScheduling4.2.10进程调度的实现2023/2/569大学课件

OS调度实质是一种资源分配。调度算法是指，根据系统的资源分配策略所规定的资源分配算法。系统采用一种调度算法，意味着作业的运行对应着一种调度顺序。了解每一种算法的思想、特点和适应范围。2023/2/570大学课件4.2.1先来先服务调度算法FCFS或FIFO(先进先出)(非剥夺式)

一、调度算法基本思想是按照进程进入就绪队列的先后次序来分配处理机。非剥夺的调度方式。2023/2/571大学课件从表面上看，先来先服务算法对于所有作业是公平的，即按照它们到来的先后次序进行服务。但：短作业在系统中的驻留平均时间与长作业的驻留平均时间相同。2023/2/572大学课件很少被用作主要调度策略，常作为一种辅助调度算法使用。如例表：2023/2/573大学课件111001.991100100199110110220201101102110011000123ABCD带权周转时间周转时间完成时间开始执行时间服务时间到达时间进程名2023/2/574大学课件从表知：短作业C的带权周转时间(周转时间(完成时间-到达时间)/应服务时间)高达100，是不可容忍的。长作业D的带权时间为1.992023/2/575大学课件FCFS有利于CPU繁忙型（科学计算型）的作业，不利于I/O繁忙型（数据处理型）的作业(进程)。

CPU约束的CPU-bound:编译程序、科技计算程序、算法程序等。I/O约束的I/O-bound：编辑排版程序、游戏程序等。2023/2/576大学课件二、FCFS实例如图示：有五个进程A、B、C、D和E。2023/2/577大学课件调度算法作业情况2.12.251.53.22.671带权周转时间8931684周转时间1361894完成时间2.83.55.5221带权周转时间914111064周转时间18141274完成时间42534服务时间43210到达时间平均EDCBA进程名FCFS(a)SJF(b)2023/2/578大学课件4.2.2短作业(进程)优先调度算法SJ(P)F，又称最短CPU运行期优先SCBF（shortestCPUburstfirst）

从就绪队列中选出下一个“CPU执行期”最短的进程。主要用于作业调度。非抢占式的策略。2023/2/579大学课件SJF算法用于作业调度。

SPF算法进程调度。2023/2/580大学课件和FCFS算法相比较，平均周转时间及平均带权周转时间有明显的改善，尤其对短作业，所以，SJF能有效地降低作业的平均等待时间和提高系统的吞吐量。2023/2/581大学课件其缺点：(1)该算法对长作业非常不利。严重的会导致长作业得不到调度。所以不适合于分时系统。它不能保证对用户及时响应。饥饿或饿死现象。2023/2/582大学课件(2)该算法完全未考虑作业的紧迫程度，不能保证紧迫性作业(进程)会得到及时处理。(3)作业(进程)的长短是根据用户提供的估计执行时间而定的，不一定能真正做到短作业优先调度。2023/2/583大学课件练习：若在后备作业队列中等待运行的同时有三个作业1、2、3，已知它们各自的运行时间为a,b,c，且满足关系a<b<c，试证明采用短作业优先算法能获得最小平均周转时间。2023/2/584大学课件解：由于短作业优先调度算法总是在后备作业队列中选择运行时间最短的作业作为调度对象，所以，对短作业优先调度算法而言，这三个作业的总周转时间为：T1＝a+(a+b)+(a+b+c)=3a+2b+c(一)若不按短作业优先调度算法来调度这三个作业，不失一般性，假定调度顺序为2、1、3，则其总周转时间为：T2＝b+(b+a)+(b+a+c)=3b+2a+c(二)由（二）-（一）得：T2－T1＝b-a>0由此可见：短作业优先调度算法能获得最小平均周转时间2023/2/585大学课件反例：考虑5个作业，从A到E，运行时间分别是2,4,1,1和1。它们的到达时间是0,0,3,3和3。开始只能选择A或B，因为其他的作业还没有到达。使用最短作业优先，将按照A，B，C，D，E的顺序运行作业，其平均等待时间是4.6。但是，按照B，C，D，E，A的顺序运行作业，其平均等待的时间是4.4。2023/2/586大学课件4.2.3时间片轮转调度算法，分时系统中采用，用于进程调度。抢占式策略。一、基本原理RR或TRR（RoundRobin）

基本思想：让每个进程在就绪队列中的等待时间与享受服务的时间成比例。2023/2/587大学课件将CPU的处理时间分成固定大小的时间片。时间片的大小从几ms到几百ms，早期默认100ms，现在一般在50ms或25ms。2023/2/588大学课件保证了就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。2023/2/589大学课件就绪队列I/O阻塞队列I/O时间片用完进程结束高级调度因I/O请求而阻塞CPU简单轮转法的调度模型2023/2/590大学课件二、时间片大小的确定时间片的大小对系统的性能有很大影响。太大时，则成了FCFS。太小时，切换过于频繁，影响响应时间。所以，时间片要适当。2023/2/591大学课件时间片长度的选择是根据系统对响应时间的要求R和就绪队列中所允许的最大进程数N。

q=R/N2023/2/592大学课件如图示：各进程的平均周转时间和带权平均周转时间。2023/2/593大学课件时间片作业情况2.53.3352.2521带权周转时间8.41310964周转时间17131174完成时间3.463.3333.53.673.75带权周转时间11.8136141115周转时间179161215完成时间42434服务时间43210到达时间平均EDCBA进程名RRq=1RRq=42023/2/594大学课件＊＊一、进程调度算法计算题（华师大2002年试题）＊＊假定有进程，它们的提交时间、运行时间如下：作业号到达时间运行时间开始时间结束时间103224342464要求：1、采用先来先服务算法，分别计算这批进程的平均轮转时间、平均带权轮转时间2、采用时间片轮转算法（时间片Q=2），分别计算这批进程的平均轮转时间、平均带权轮转时间。2023/2/595大学课件练习有5个批任务几乎同时到达，其预计的运行时间A,B,C,D,E分别为6，10，2，8，4分，计算其在时间片轮转算法下的平均进程周转时间。（进程切换开销可以忽略）2023/2/596大学课件这里并没有明确地给出时间片的大小，在这种情况下，一般默认时间片很小（操作系统中一般时间片为0.1秒）。

然后，在本题中，显然任务C先执行完，在任务C执行完的时候，任务D,E只跟C相差很小的时间，可以近似的认为A,B,C,D,E都执行了2分钟。那么，C的周转时间就是10分钟。接着，A,B,D,E再都执行2分钟，E任务结束，所以，E的周转时间是18分钟。

依次类推，A的周转时间为24分钟，D的周转时间为28分钟，B为30分钟。2023/2/597大学课件多级反馈轮转法轮转法中有三种进程：（1）时间片用完，但未结束。（2）运行期间被阻塞。（3）新进程。不同进程给予不同的优先级和时间片。2023/2/598大学课件4.2.4最高优先权优先调度算法（FPF）最常用的一种算法。一、最高优先权调度算法的类型“急事先办，要事先办”。作业调度和进程调度。2023/2/599大学课件1、非抢占式优先权算法

主要用于批处理系统中，也可用于对实时性要求不高的实时系统中。2023/2/5100大学课件2、抢占式优先权调度算法任一时刻运行的是优先级最高的进程。2023/2/5101大学课件该算法更好地满足了紧迫作业的要求，常用于要求比较严格的实时系统中，以及对性能要求高的批处理和分时系统中。该算法的关键是如何确定进程的优先权，方法如下两种：2023/2/5102大学课件二、优先权的类型1、静态优先权静态优先权是在创建进程时确定的，在进程的整个运行期间保持不变。一般利用某一范围内一个整数表示，该整数称为优先数。如：0~7或0~255。2023/2/5103大学课件确定进程优先权的依据：(1)进程类型。系统进程高于用户进程,联机用户于脱机用户进程的优先权。(2)进程对资源的要求。执行时间及内存需要量少的进程，有较高的优先权。2023/2/5104大学课件(3)根据用户要求。由用户进程的紧迫程度及用户所付费用的多少来确定进程的优先权。2023/2/5105大学课件2、动态优先权，是基于某种原则，使进程的优先权随时间而改变。是指在创建进程时，根据系统资源的使用情况和进程的当前特点所赋予的优先权，可随进程的推进而改变，以获得更好的调度性能。2023/2/5106大学课件具有相同的优先权初值，最先进入就绪队列的进程，将先获得处理机。即FCFS。具有互不相同的优先权初值，优先权初值低的进程，等待足够时间后，其优先权会升为最高，从而获得处理机执行。练习2023/2/5107大学课件4.2.5高响应比优先调度算法（HighestResponse_ratio

Next）HRN(Hansen)

是对FCFS和SJF的综合平衡。FCFS只考虑等待时间而未考虑执行时间的长短。SJF只考虑执行时间未考虑等待时间的长短。2023/2/5108大学课件为每个作业引入动态优先权机制，并使之以速率a增加，则长作业等待一定的时间后，会有机会分配到处理机。优先权的变化：优先权＝(等待时间＋要求服务时间)/要求服务时间2023/2/5109大学课件等待时间加上要求服务时间，即该作业的响应时间。所以，优先权又称为响应比Rp:

Rp=优先权＝响应时间/要求服务时间由此看出：（1）若作业的等待时间相同，则要求服务的时间愈短，优先权愈高，则该算法有利于短作业。2023/2/5110大学课件（2）若要求服务的时间相同，作业的优先权取决其等待时间，实现了先来先服务。（3）对长作业，其等待时间足够长时，其优先权会升到很高，从而可获得处理机。2023/2/5111大学课件所以，该算法既有利于短作业，又考虑了作业到达的先后顺序，使长作业也能得到服务。不过，利用该算法时，在调度前，要先进行响应比的计算，有一定的开销。练习2023/2/5112大学课件4.2.6最短剩余时间优先调度算法(SRTF,ShortestRemainingTimeFirst)最短剩余时间优先调度算法是把最短作业优先算法使用于分时环境中的变型。其基本思想是让运行到作业完成时所需的运行时间最短的进程优先得到处理，其中包括新进入系统的进程。2023/2/5113大学课件在最短作业优先策略中，一个作业一旦得到处理机就一直运行到完成(或等待事件)而不能被抢占(除非主动让出处理机)。而最短剩余时间优先策略是可以被一个新进入系统，并且其运行时间少于当前运行进程的剩余运行时间的进程所抢占。2023/2/5114大学课件本策略的优点是可以用于分时系统，保证及时响应用户要求。缺点是系统开销增加，首先要保存进程的运行情况记录，以比较其剩余时间大小。其次，抢占本身也要消耗处理机时间。毫无疑问，这个策略使短作业一进入系统就能立即得到服务，从而降低作业的平均等待时间。2023/2/5115大学课件假设有一个系统中有5个进程，它们的到达时间和服务时间如表所示，忽略I/O以及其他开销时间，若分别按高响应比优先、非抢占及抢占的短进程优先调度算法进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间2023/2/5116大学课件进程到达时间服务时间A03B26C44D65E822023/2/5117大学课件线性优先级调度策略

(SRR)selfishroundrobin新创建的进程按FCFS排成就绪队列A，而其他已得到过时间片服务的进程也按FCFS排成另一个就绪队列或称享受服务队列B。

对两个不同队列中的进程，设置不同的优先级P。A中的优先级以a的速率增加：

P＝a*t(a>0)B中的优先级以b的速率增加：

P＝b*t(a>b>0)2023/2/5118大学课件所以，某一进程在t1被创建，在t时刻,该进程的优先级为

P(t)=a*(t-t1)若该进程在t2时刻转入B队列中，则在时刻t，该进程的优先级为

P(t)=a*(t2-t1)+b*(t-t2)2023/2/5119大学课件当A队列中的第一个进程优先级和B队列中最后一个进程的优先级相等时，A中的第一个进程可以转入B队列。或当B队列为空时，A中的第一个进程可转入B队列。2023/2/5120大学课件显然，a>b>0的条件是必要的。若b>a>0时，两个队列中优先级永远不会相等，B中永远只有一个进程，转化成了FCFS算法。若a>b=0时，则转化为RR法。2023/2/5121大学课件练习一、设有四道作业，它们的提交时间及执行时间如下：

作业号提交时间执行时间123410.010.210.410.52.01.00.50.32023/2/5122大学课件试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法进的平均周转时间和平均带权周转时间，并指出它们的调度顺序。（时间单位：小时，以十进制进行计算）2023/2/5123大学课件练习解：采用先来先服务调度算法，则其调度顺序为1、2、3、4。作业号提交时间执行时间开始时间完成时间周转时间带权周转时间123410.010.210.410.52.01.00.50.310.012.013.013.512.013.013.513.82.02.83.13.31.02.86.211.02023/2/5124大学课件平均周转时间：T=(2.0+2.8+3.1+3.3)/4=2.8平均带权周转时间：W=(1+2.8+6.2+11)/4=5.25采用短作业优先调度算法自己练习T=2.45,W=3.85。2023/2/5125大学课件二、下表给出作业1、2、3的到达时间和运行时间。采用短作业优先调度算法和先来先服务调度算法，试问平均周转时间各为多少？是否还有更好的调度策略存在？（时间单位：小时，以十进制进行计算）。练习2023/2/5126大学课件作业号到达时间运行时间1230.00.41.08.04.01.02023/2/5127大学课件练习采用先来先服务调度算法：平均周转时间T=10.53采用短作业优先调度策略，顺序：1、3、2平均周转时间T=9.53存在缩短平均周转时间的策略，即还有两个短作业，等所有作业都到达后，再按短作业优先调度算法调度，顺序：3、2、1，平均周转时间T=6.872023/2/5128大学课件练习三、假设有四个作业，它们的提交、执行时间如下表所示。若采用响应比高者优先调度算法，试问平均周转时间和平均带权周转时间为多少？作业号到达时间运行时间12348.08.38.59.02.00.50.10.4返回2023/2/5129大学课件练习解：调度顺序：1、3、2、4。T=1.975W=6.658点钟时，只有作业1到达，系统先1投入运行，运行2小时后即10点钟完成。剩下三个作业的响应比为：r2=1+(10.3-8.3)/0.5=4.4r3=1+(10.0-8.5)/0.1=16r4=1+(10.0-9.0)/0.4=3.5返回2023/2/5130大学课件所以，作业2的响应比最高，先让3运行，运行0.1小时完成，此时，2和4的响应比为：

r2=1+(10.1-8.3)/0.5=4.6r4=1+(10.1-9.0)/0.4=3.75

可知2的响应比高，先让2运行。返回2023/2/5131大学课件练习四、今有三个批处理作业。第一个作业10：00到达，需要执行2小时，第二个作业在10：10到达，需要执行1小时，第三个作业在10：25到达，需要执行25分钟。分别采用如下三种调度算法：（1）计算各调度算法下的作业平均周转时间(以小时为单位)（2）调度算法1、3分别是什么作业调度算法？2023/2/5132大学课件作业号到达时间开始执行时间执行结束时间1231010:1010:25101213121313:25调度算法12023/2/5133大学课件作业号到达时间开始执行时间执行结束时间1231010:1010:2511:5010:5010:2513:5011:5010:50调度算法22023/2/5134大学课件作业号到达时间开始执行时间执行结束时间1231010:1010:251012:25121213:2512:25调度算法32023/2/5135大学课件练习五、（北京大学95年试题）有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。在下表所示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。作业号到达时间估计运行时间（分钟）优先数ABCD1010:2010:3010:50403050205346返回2023/2/5136大学课件练习要求：（1）列出所有作业进入内存时间及结束时间（2）计算平均周转时间(以分钟计算)2023/2/5137大学课件练习解：本题中，每个作业的运行都将经历两级调度：作业调度和进程调度。只有当作业调度程序将作业装入内存后，才能参与进程调度。而系统是两道作业系统，每次只能有两道作业进入内存。2023/2/5138大学课件本题中的作业和进程推进顺序：10：00，A到达，作业调度程序先将A调入内存并排在就绪队列上，进程调度调度它运行。10：20，B到达，后备队列无其它作业，作业调度程序将B调入内存并排在就绪队列上，B的优先级高于A，进程调度程序停止A的运行，将A放入就绪队列，调度B运行，此时，已有两道作业在内存中，A已运行20分钟。2023/2/5139大学课件练习10：30，C到达，但只能在后备作业队列中等待作业调度，B已运行了10分钟，A已等待10分钟，还需运行20分钟才能完成。10：50，B运行结束，D到达，内存中只有A，后备队列中有C、D，按短作业优先的作业调度策略，作业D被优先调入内存，在内存中，A的优先级高于D，A运行，D在就绪队列中等待。此时，A已运行了20分钟，等待了30分钟，再运行20分钟，C已在后备队列中等待了20分钟。2023/2/5140大学课件11：10，A运行结束，内存只有D，作业调度将C调入内存，由于C优先级高于D，进程调度调度C运行，D继续等待。12：00，C结束运行，D调度运行。12：20，D结束运行。2023/2/5141大学课件4.2.7多级队列调度多队列调度是根据作业的性质和类型，将就绪队列分成多级独立子队列，各个作业固定的分属于一个队列。不同的队列采用不同的调度算法，各级队列之间的关系可采用优先权或按分配CPU的时间比例进行调度。2023/2/5142大学课件4.2.8多级反馈队列调度算法(多重队列法.MLFQ,Multi-LevelFeedbackQueue,反馈循环队列)多级反馈队列调度算法，不必事先知道各种进程所需的执行时间，还可以满足各种类型进程的需要，是比较好的一种进程调度算法。UNIX和OS/2中都采用了类似的调度算法。Solaris和Windows2000/NT也都采用它。2023/2/5143大学课件一、调度算法多级反馈队列调度算法的实施过程：(1)系统中有多个进程就绪队列，每个就绪队列对应一个调度级别，各级具有不同的运行优先级。第一级队列的优先级最高，以下各级队列的优先级逐次降低。2023/2/5144大学课件(2)各级就绪队列中的进程具有不同的时间片。优先级最高的第1级队列中的进程的时间片最小，随着队列的级别增加其进程的优先级降低了，但时间片却增加了。一般提高一级其时间片增加一倍。2023/2/5145大学课件(3)各级队列均按先来先服务原则排序。(4)调度方法：当一个新进程进入系统后，它被放入第1级就绪队列的末尾。该队列中的进程按先来先服务原则分给处理机，并运行一个相应于该队列的时间片。2023/2/5146大学课件假如进程在这个时间片中完成了其全部工作或因等待事件或等待输入输出而主动放弃了处理机，于是该进程或撤离系统(任务完成)或进入相应的等待队列，从而离开了就绪队列。2023/2/5147大学课件若进程使用完了整个时间片后，其运行任务并未完成仍然要求运行(也没能产生输入输出要求)。于是该进程被抢占处理机，同时将它放入下一级就绪队列的末尾。2023/2/5148大学课件(5)当第一级进程就绪队列为空后，调度程序才去调度第2级就绪队列中的进程。其调度方法同前。当第1，第2队列皆为空时才去调度第3级队列中进程……。当前面各级队列皆为空时，才去调度最后第n级队列中的进程。第n级(最低级)队列中的进程是采用时间片轮转方法进行调度。2023/2/5149大学课件(6)当比运行进程更高级别的队列中到来一个新的进程时，它将抢占运行进程的处理机，而被抢占的进程回到原队列的末尾。2023/2/5150大学课件多级反馈队列的调度操作已大致描述如上，它是根据进程执行情况的反馈信息而对进程队列进行组织并调度进程，故而得名。2023/2/5151大学课件二、多级反馈队列调度算法的性能：能满足各种类型用户的需要1、终端型作业用户2、短批处理作业用户3、长批处理作业用户使用多级反馈队列调度算法的例子是著名的WindowsNT操作系统的调度算法。2023/2/5152大学课件进程名ABCD到达时间0123服务时间10482第一队列Q=4完成时间481214第二队列Q=8完成时间2024第n队列完成时间2023/2/5153大学课件4.2.9彩票调度算法LotteryScheduling系统为每种资源发放不同数量的彩票给不同的进程。调度程序对某种资源做出调度决策时，随机选择一张彩票，彩票的持有者将获得相应的系统资源。协作进程可以交换彩票，客户进程给服务器进程发送消息后而阻塞，客户进程可以把彩票全部交给服务器进程。服务器进程完成服务后，又把彩票还给客户进程。2023/2/5154大学课件10、策略驱动法：11、最晚时间限调度deadlinescheduling：保证在每个进程必须完成的最晚时间限前运行完该进程。12、二级调度法：后备队列和就绪队列。Linux中CPU调度算法可由用户通过宏定义来选择，可选的算法有：先进先出、时间片轮转、动态优先级等2023/2/5155大学课件总结作业调度的目标：尽量做到公平合理，能执行尽可能多的作业，尽快地响应时间以及高的设备利用率等。调度算法有：FCFS系统开销小，且对每个作业按其到达的顺序依次调度，不利于短作业。SJF可得到最大的系统吞吐量，但会使长作业可能长期得不到调度。HRN介于FCFS和SJF之间。2023/2/5156大学课件进程调度的主要任务是选择一个合适的进程占据处理机。调度算法：RR轮转法，FCFS法,优先级法和SRR线性优先级法RR主要用于分时系统。有较好的响应时间，对每个进程有较好的公平性。FCFS不利于执行时间短的进程。SRR介于FCFS和RR之间。2023/2/5157大学课件适用于作业调度的算法先来先服务算法：计算时间短的作业优先算法：

响应比高者优先算法优先数调度算法均衡调度算法仅适用于作业调度的算法：响应比高者优先算法仅适用于进程调度的算法：时间片轮转2023/2/5158大学课件进程调度的实现在设计进程调度程序时，应考虑这样三个问题：（1）确定引起进程调度的因素（2）调度算法的选择和设计（3）就绪队列的组织一、确定引起进程调度的因素归纳起来，大致可有：（1）进程执行完毕或因发生某事件而不能继续执行2023/2/5159大学课件（2）因提出I/O请求而暂停（3）执行了某种原语操作，如：p操作或block原语等。（4）在可剥夺式调度中，有一个比当前进程优先级更高的进程进入就绪队列（5）在时间片轮转法，时间片用完。二、就绪队列的组织2023/2/5160大学课件进程调度的实现系统可以把就绪队列组织成栈、或队列的形式，采用哪种形式与调度算法有关。如：轮转法中，就绪进程常组织成FIFO队列形式在最高优先权优先调度算法中，常采用优先级队列形式，进程在进入就绪队列时，按其优先级的高低，插入到相应的位置上。2023/2/5161大学课件调度程序总把CPU分配给队首进程。最高优先级优先调度算法中，也可采用无序链表方式，即每当进程进入就绪队列时，总是被放在末尾，而调度程序每次调度时，依次比较队列中每个进程的优先级，从中找出最高的，把CPU分配给它。2023/2/5162大学课件三、分派程序分派程序首先将正在执行进程的CPU状态保存到该进程PCB的保留区中，再从被调度程序选中的进程PCB的处理机状态字保留区中，取出CPU状态信息来重新布置CPU现场。CPU状态信息包括：程序状态寄存器，若干个通用寄存器及程序计数器的内容。

这样，被调度到的进程可继续执行。2023/2/5163大学课件进程调度的实现分派程序在将处理机分配给进程时的具体操作，可描述如下：我们假定就绪队列中的诸进程，已经按其优先级的大小排队，并允许剥夺调度，当就绪队列的队首出现优先权比当前正在执行进程j的优先级最高的进程时，应立即停止j的执行，并将它按其优先级的大小，插入到就绪队列的适当位置上，然后用进程i的PCB中保留的CPU现场信息去恢复CPU现场。2023/2/5164大学课件进程调度的实现采用最高优先级优先的调度算法可描述如下：

proceduredispatcherbeginifRQ=0thenifEP=0thenidlerelsecontinue;remove(RQ,i);ifEQ=0thengotoL;j:=EP;2023/2/5165大学课件ifi.priority>j.prioritythenbeginstop(j);

save(j.CPUstatus);j.status:=ready;j.data:=RQ;

insertp(RQ,j);2023/2/5166大学课件L:I.status:=“executing”;EP:=i;

restore(I.CPUstatus);endelsecontinue;end.2023/2/5167大学课件4.3实时系统中的调度4.3.1对实时系统的要求4.3.2实时调度算法4.3.3实时调度实例一、具有开始截止时间的非周期实时任务的调度二、具有完成截止时间的周期性实时任务的调度2023/2/5168大学课件实时系统中，都存在着若干个实时进程或任务，用来反应或控制某个（些）外部事件，带有某种程度的紧迫性。所以实时系统的调度有一定特殊性，前述调度算法，不能满足实时系统的需要。4.3.1对实时系统的要求2023/2/5169大学课件1、提供必要的调度信息由于实时系统中，无论是硬实时任务，还是软实时任务，都联系着一个截止时间，要保证系统的正常运行，实时调度必须能满足实时任务对截止时间的要求。实时调度算法大多根据任务的截止时间进行调度的，系统向调度程序提供有关任务的一些信息：2023/2/5170大学课件（1）就绪时间。是该任务成为就绪任务状态的起始时间，周期任务情况中，它是事先预知的一串时间序列，非周期任务情况中，也可预知。（2）开始截止时间和完成截止时间。典型的实时应用只需知道开始截止时间，或完成截止时间。2023/2/5171大学课件（3）处理时间。是指一个任务从开始执行到完成所需的时间，某些情况下，可由系统提供。（4）资源要求。任务执行时所需的一组资源。2023/2/5172大学课件（5）优先级。若任务对开始截止时间要求严格（硬任务）时，赋予“绝对”优先级，若对时间不甚严格，可赋予“相对”优先级。2023/2/5173大学课件2、调度方式一般对要求严格的实时系统，采用抢占调度方式，既具有较大的灵活性，又有极小的调度延迟，但这种方式比较复杂。2023/2/5174大学课件在小的实时系统中，能预知任务的开始截止时间，实时任务的调度采用非剥夺调度方式，简化调度程序和任务调度所花费的开销。3、具有快速响应外部中断的能力当紧迫的外部事件请求中断时，系统能及时响应。要求系统具有快速硬件中断机构，使禁止中断的时间间隔尽量短。2023/2/5175大学课件4、快速任务分派完成任务调度后，立即进行任务切换，系统中的每个运行功能单位适当地小，减少任务切换的时间开销。2023/2/5176大学课件4.3.2实时调度算法1、时间片轮转调度算法，常用于分时系统中。当一个实时任务到达时，被挂在轮转队列的末尾，等待属于自己的时间片。这种调度算法仅能获得秒级的响应时间，只适于一般实时信息处理系统，不能用于要求严格的实时控制系统。2023/2/5177大学课件2、非抢占优先权调度算法，常用于多道批处理系统中。当一个优先级高的实时任务到达时，被安排在就绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行。这种算法可获得数秒至数百毫秒级的响应时间，可用于要求不太严格的实时控制系统。2023/2/5178大学课件3、基于时钟中断抢占的优先权调度算法。若某实时任务到达时，若该任务的优先级高于当前任务的优先级，在时钟中断到来时，调度程序剥夺当前任务的执行，将处理机分配给高优先权任务，这种算法能获得几十毫秒至几毫秒的调度延迟。这种算法用于大多数实时系统。2023/2/5179大学课件4、立即抢占的优先权调度要求系统具有快速响应外部事件中断的能力，一旦出现外部中断，只要当前任务未处于临界区，便立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。其延迟时间可到几毫秒至100微秒，甚至更低。如图示：P111。2023/2/5180大学课件4.3.3实时调度实例******一、具有开始截止时间的非周期实时任务的调度事先知道各实时任务的开始截止时间，且对调度延迟要求不严格的情况下，可采用最早截止时间优先的非剥夺调度策略。例：四个具有开始截止时间的非周期任务的调度情况。2023/2/5181大学课件系统首先调度任务1执行，在任务1执行期间，任务2、3先后到达。由于任务3的开始截止时间早于任务2，所以系统在1后将调度3执行，在此期间又来了4，其开始截止时间也早于2，所以执行完3后，系统又调度执行4，最后才调度执行2。2023/2/5182大学课件二、具有完成截止时间的周期性实时任务的调度基有两个周期性实时任务A和B，A每20ms执行一次，执行时间为10ms，B每50ms执行一次，执行时间为25ms。

所以，A和B每次的开始截止时间为：A1,A2,A3,…和B1,B2,B3,…。

为保证不遗漏一次截止时间，采用最早截止时间优先的剥夺调度策略。如图示：243113421234t开始截止时间执行任务任务到达2023/2/5183大学课件2023/2/5184大学课件又例：在时间为0ms时，A1离截止时间只有10ms，B1离截止时间有25ms,所以，调度程序将调度A1执行。在10ms时，A2离截止时间有20ms，B1离截止时间还有15ms，此时调度B1执行。在30ms时，A2到了开始截止时间，B1离开始截止时间还有15ms，此时要剥夺B1的运行，而调度A2。

2023/2/5185大学课件在40ms时，A3离开始截止时间有10ms，B1还有5ms，又重新调度B1执行。在45ms时，B1完成，而A3离开始截止时间有5ms，而B是30ms，先调度A3执行。在55ms时，A尚未进入第4周期，而B进入了第2周期，所以调度B2执行。2023/2/5186大学课件10A1(10)B1(25)A1210A2(20)B1(15)B1330A2(0)B1(15)A2440A3(10)B1(5)B1545A3(5)B2(30)A3655A4(15)B2(20)B2770A4(0)B2(20)A4...............时间(ms)A截止时间B截止时间调度对象2023/2/5187大学课件4.4多处理机调度4.4.1进程调度一、同构型多处理机系统中的进程调度二、异构型多处理机系统中的进程调度4.4.2自调度4.4.3成组调度4.4.4专用处理机分配前面所述的是单处理机环境下的进程调度，当有多台处理机时，要保持多台处理机尽量处于忙状态，涉及到多处理机的调度，由于，系统中引入线程后，调度的基本单位已是线程，目前大多数OS都采用线程机制，所以本节主要介绍对线程的调度问题2023/2/5188大学课件4.4.1进程调度多处理机系统中，进程调度与系统结构有关。同构型中，对某一进程，可将其分配到任一处理机上运行。异构型中，对某一进程只能将其分配到适合于他运行的处理机上执行。多处理机系统中的进程调度，还与OS的工作模式有关。2023/2/5189大学课件一、同构型多处理机系统中的进程调度1、静态分配(staticassignment)

指一个进程从开始执行直至完成，被固定地分配到一台处理机上去执行。此时，要为每一台处理机设置一专用的就绪进程队列，该队列中的诸进程被先后分配到该台处理机上执行。2023/2/5190大学课件进程被阻塞后，再次就绪时，仍被挂在原来这个就绪队列中，下次仍然在此处理机上执行。该方式与单处理机环境的进程调度一样，优点：调度开销小，缺点：各处理机的忙、闲不均。2023/2/5191大学课件2、动态分配(dynamicassignment)

系统中设置一个公共的就绪队列，所有的就绪进程都被放在该队列中。分配处理机时，对某一进程，可分配到任意一台处理机。对一个进程的整个运行过程，在每次被调度执行时，是随机被分配到一台空闲的处理机上去执行。2023/2/5192大学课件其优点：消除了处理机忙闲不均的现象，但调度的开销大。3、自调度(self-scheduling)

系统只设置一个公共就绪队列，所有的就绪进程都被挂在该队列上。2023/2/5193大学课件自调度是指由每个处理机自己去查看公共就绪队列，从中选择一个进程令其执行。要求系统中设置同步机制，用于保证诸处理机互斥地访问就绪队列，避免多个处理机同时选择一个进程，也不会出现某个进程从就绪队列中丢失。2023/2/5194大学课件二、异构型多处理机系统中的进程调度异构型多处理系统，大多采用主-从式OS，即OS的核心部分驻留在主机上，从机只执行用户程序，进程调度由主机执行。当从机空闲时，向主机发送一要求进程的信号，然后，等待主机为之分配进程。