操作系统--第三章调度与死锁2016-10资料

第三章进程调度的核心是调度算法。进程调度是实现多道程序系统的关键，直接影响到操作系统的性能，是本章讨论的主要问题。§3.1调度的基本概念(一）作业从进入系统到完成，可能要经历三级调度过程：一、调度的类型和模型1、高级调度又称为作业调度，它决定将哪些在外存上处于后备状态的作业调入主机内存，准备执行。因此，有时把它称为接纳调度。2、低级调度又称为进程调度，它决定就绪队列中哪个进程将获得处理机，并实际执行将处理机分配给进程的操作。执行分配处理机的程序称为分派程序。3、中级调度中级调度的主要作用是在内存和外存之间进行进程交换，以解决内存紧张的问题。如它将内存中处于等待状态的某些进程调至外存对换区，以腾出内存空间，而将外存对换区上已具备运行条件的进程重新调入内存，准备运行。故又称为交换调度。阻塞状态就绪状态执行状态调度I/O请求进程释放时间片到后备作业队列§3.1调度的基本概念(二）CPU就绪队列内存外存阻塞队列作业调度等待事件中级调度即交换调度交换文件就绪队列阻塞队列三级调度的模型调度队列模型1.仅有进程调度的调度队列模型图3-1仅具有进程调度的调度队列模型就绪队列阻塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完2.具有高级和低级调度的调度队列模型图3-2具有高、低两级调度的调度队列模型就绪队列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现……等待事件n事件n出现后备队列……(1)就绪队列的形式。(2)设置多个阻塞队列。图3-2示出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个方面。3.同时具有三级调度的调度队列模型图3-3具有三级调度时的调度队列模型就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现§3.1调度的基本概念(三）作业调度是确定哪些作业可以被调入内存。进程调度是确定哪个进程可以占有CPU并执行。作业调度是进程调度的基础，作业被调入内存后，是以进程的形式执行的。在一个OS中进程调度与作业调度的算法是一致的。？问题？1。进程调度与作业调度之间（功能、调度算法）有何区别和联系？2。三级调度中，最核心的是那一级调度？为什么？各级调度间的关系§3.1调度的基本概念(四）作业步—将一个作业划分为若干个顺序处理的步骤，作业步相互独立又相互关联。作业—是用户请求计算机系统执行的一次独立的上机任务，是能够共享公共资源区域的一族有关进程（家族）。从静态观点看，作业由控制命令系列、程序集、数据集三部分构成。补充：关于作业的概念作业控制块—JCB（JobControlBlock）用于描述作业。定义为记录类型（作业名、优先级、建立时间、状态外存地址、大小等）。作业状态—作业在其生命期中，共有四种状态：关于作业的状态作业状态—作业在其生命期中，共有四种状态：进入、后备、运行、完成完成执行就绪阻塞进入后备内存运行提交作业调度完成问题：引起进程调度的原因有哪些？§3.1调度的基本概念(五）非抢占式（非剥夺式）进程一旦被调度，就一直占有CPU，直到完成或因发生某事件而被阻塞（I/O请求）。抢占式（剥夺式）进程未执行完，可由调度程序剥夺其CPU，另分配给别的进程。抢占的原因有：优先级、时间片、短进程等。在OS中，进程调度的方式分为两类。二、进程调度的方式§3.1调度的基本概念(六）记录系统中所有进程的执行情况确定分配处理机的原则（调度算法）分配处理机给进程回收处理机、进行进程上下文切换三、进程调度的功能显然，进程调度的核心问题是调度算法。§3.1调度的基本概念(七）1。周转时间短周转时间TT（TumaroundTime）对作业—从作业提交到完成。对进程—第一次进入就绪队列到运行结束。平均周转时间ATT（AverageTumaroundTime）ATT=[∑Ti]带权平均W=[∑]其中：Ti各进程的TTTri实际执行时间2.响应时间快响应时间RT（ResponseTime）—输入键盘命令到屏幕显示结果。四.调度算法准则公平服务,提高资源利用率，减少CPU空闲时间。1ni=1nTiTrii=1n1n(2)响应时间快。(3)截止时间的保证。(4)优先权准则。1.面向用户的准则(1)周转时间短。2.面向系统的准则(1)系统吞吐量高。(2)处理机利用率好。(3)各类资源的平衡利用。四.调度算法准则公平服务,提高资源利用率，减少CPU空闲时间。§3.2调度算法（一）先来先服务（FCFS）算法最短CPU运行期优先（SCBF）算法最高优先权（HPF）算法时间片轮转（RR）算法多级反馈队列算法思考题1、各种调度算法的特点、性能如何？适宜于哪类OS？2。最高优先权算法中，动态优先权有何实际意义？常用调度算法§3.2调度算法（二）一.、先来先服务（FCFS）算法FCFS（FirstComeFirstServer）法，又称为先进先出（FIFO）算法，就绪进程按照进入的先后次序排列，调度程序总是选择队首的进程执行。这是一种非剥夺式的调度算法，简单、易实现。对短进程易出现等待时间长，服务质量差。该算法有利于CPU繁忙型的进程，不利于I/O繁忙型的进程。1n该算法只能用于辅助算法。先来先服务调度算法图3-4FCFS和SJF调度算法的性能§3.2调度算法（二）二、最短CPU运行期优先（SCBF）算法n+1nnt该算法优于FCFS，但长进程等待时间长，估算误差较大。SCBF（ShortestCPUBurstFirst），即调度程序总是选择CPU运行时间最短的进程执行。其中为估计的第n个CPU周期。tn为实际值。为控制值，0≤≤1，常取0.5n对最短CPU运行期的估算，依赖于系统的下一个CPU周期中，实现较困难。进程的CPU时间的估算公式：n+1§3.2调度算法（三）三、最高优先权（HPF）算法调度程序每次都将CPU分配给就绪队列中具有最高优先级（HighestPriority）的进程。该算法的核心是优先级的确定。调度方式分为剥夺式和非剥夺式。静态优先级在创建进程时根据进程的特性或者用户要求赋予，在进程的整个生命期中不能改变。简单、易实现，但是调度性能不高，优先级低的进程可能长期等待。动态优先级在创建进程时为进程赋予一个基本优先级，在进程的执行过程中可随进程的特性动态改变。引起优先级改变的原因：进程等待CPU时间长短，执行所需CPU时间长短等。分两类优先级：§3.2调度算法（四）三、最高优先权（HPF）算法确定进程优先级的一般原则：1.进程的类型例如：系统进程高于用户进程；前台进程高于后台进程；实时进程高于一般进程。2.对资源的需求量及类型占用CPU时间少的，使用内存资源少的进程优先级高。3.按作业到达系统的时间顺序4.按用户类型和要求§3.2调度算法（五）四、时间片轮转（RR）算法该算法主要用于分时系统，按照公平服务的原则，为进程分配CPU时间片。是一种剥夺式的算法。轮转法的关键是时间片的选取：时间片太大，则轮转法蜕化为FCFS法。时间片太小，则增加CPU的额外开销。影响时间片设置的主要因素：系统响应时间R、就绪进程数N、计算机处理能力等。时间片长度：q=R/Nmax§3.2调度算法（六）五、高响应比优先调度算法（HRN）HRN（HighestResponseratioNext）算法将短进程优先与动态优先级相结合。由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP①随着进程等待时间的增加，优先权动态增加。②对等待相同时间的短进程比长进程优先权增加得多。③长进程随着等待时间增加也会被调度。要求服务时间响应时间要求服务时间要求服务时间等待时间优先权§3.2调度算法（七）六、多级队列调度根据作业性质不同分为若干个就绪队列，如：系统进程队列，交互进程队列，批处理队列等。对各队列采用不同的调度算法。§3.2调度算法（八）亦称多级反馈轮转法（RoundRobinwithMultipleFeedback）实现基本思想：1。按优先级分别设置N个就绪队列，优先级愈高的队列分配的时间片愈小。2。系统总是先调度当前优先级最高的队列中的进程，只有当最高优先级队列为空时，才去调度低一优先级队列中的进程。3。进程被调度后，若未执行完时间片到，则优先级降低，进程排入相应优先级队列的队尾。4。同一优先级队列，按照FCFS算法调度。多级反馈队列是一种综合调度算法，对进程就绪队列进行动态调度和管理。七、多级反馈队列§3.2调度算法（九）七、多级反馈队列时间片：S1S2S3多级反馈队列调度算法的性能(1)终端型作业用户。(2)短批处理作业用户。(3)长批处理作业用户。3.3实时调度3.3.1实现实时调度的基本条件1.提供必要的信息(1)就绪时间。(2)开始截止时间和完成截止时间。(3)处理时间。(4)资源要求。(5)优先级。2.系统处理能力强假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：miiiPC11假如系统中有6个硬实时任务，它们的周期时间都是50ms，而每次的处理时间为10ms，则不难算出，此时是不能满足上式的，因而系统是不可调度的。解决的方法是提高系统的处理能力途径一:仍是采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；途径二:采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为：miiiNPC13.采用抢占式调度机制4.具有快速切换机制该机制应具有如下两方面的能力：(1)对外部中断的快速响应能力。要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)。(2)快速的任务分派能力。3.3.2实时调度算法的分类1.非抢占式调度算法(1)非抢占式轮转调度算法。(2)非抢占式优先调度算法。(1)基于时钟中断的抢占式优先权调度算法。(2)立即抢占(ImmediatePreemption)的优先权调度算法。2.抢占式调度算法(a)非抢占轮转调度当前进程实时进程实时进程请求调度实时进程枪占当前进程，并立即执行(d)立即抢占的优先权调度调度时间进程1进程2实时进程要求调度进程n实时进程调度实时进程运行(b)非抢占优先权调度当前进程实时进程实时进程请求调度当前进程运行完成调度时间当前进程实时进程请求调度时钟中断到来时调度时间(c)基于时钟中断抢占的优先权抢占调度调度时间实时进程图3-6实时进程调度3.3.3常用的几种实时调度算法1.最早截止时间优先即EDF(EarliestDeadlineFirst)算法图3-7EDF算法用于非抢占调度方式1342开始截止时间任务执行任务到达12341342t2.最低松弛度优先即LLF(LeastLaxityFirst)算法该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。例如:一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100ms之前调度执行，该任务的紧急程度(松弛程度)为100ms。又如，另一任务在400ms时必须完成，它本身需要运行150ms，则其松弛程度为250ms。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。该算法主要用于可抢占调度方式中。图3-8A和B任务每次必须完成的时间A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25ms。在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运行又需10ms，可算出A1的松弛度为10ms；B1必须在50ms时完成，而它本身运行就需25ms，可算出B1的松弛度