操作系统第三章处理机调度与死锁

第三章处理机调度与死锁2学习的目的和要求处理机调度，scheduling，也叫CPU调度，进程调度，讨论的是如何将处理机分给各个进程运行的问题。处理机调度（处理机管理）的工作是对CPU资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。它涉及到调度类型、调度方式、调度算法、调度时机和调度性能这样一些问题。死锁是操作系统中偶尔会出现的现象，它会使某些进程处于一种无法自我解脱的僵持状态，需要系统花费一定的时空开销来解除并恢复它们的运行。本章的学习目的主要是使学生理解和掌握处理机调度和死锁的基本概念3主要内容处理机调度的基本概念调度算法实时调度多处理机系统中的调度产生死锁的原因和必要条件预防死锁的方法死锁的检测与解除43.1处理机调度的基本概念3.1.1高级、中级和低级调度处理机（CPU）在进程之间的动态分配和切换，涉及到三种类型（或者说三个层次）的调度，即高级调度（也叫作业调度、长程调度）、中级调度（也叫进程对换）和低级调度（也叫处理机调度、CPU调度、进程调度）。低级调度是所有的系统都有的，但高、中级调度不是所有的系统都有。5调度类型高级调度：又称为“宏观调度”、“作业调度”、“长程调度”。对存放在辅存设备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立作业对应的进程，使其投入运行，时间上通常是分、小时、天。接纳的作业数采用的调度算法中级调度：又称为“交换调度”、“中程调度”。从存储器资源的角度。将进程的部分或全部换出到外存上，将当前所需部分换入到内存。指令和数据必须在内存里才能被CPU直接访问。6低级调度：又称为“微观调度”、“进程调度”、“短程调度”。对进入主存的所有进程，确定哪个进程在什么时候获得处理机，使用多长时间。时间上通常是毫秒。因为执行频繁，要求在实现时达到高效率。进程调度所追求的性能主要是响应时间短、周转时间快和对截止完成时间的保证。进程有两种基本的调度方式：即抢占式（或称剥夺式）和非抢占式（或称非剥夺式）。在抢占式方式下，操作系统有权按某种原则剥夺一个正在运行的进程的处理机；而在非抢占式方式下，除非进程主动放弃，否则操作系统不得剥夺一个正在运行的进程的处理机。调度的方式与调度算法密切相关。7调度类型（按照OS的分类）批处理调度：存在着作业调度和进程调度。应用场合——大中型主机集中计算，如工程计算、理论计算（流体力学）分时调度、实时调度：通常没有专门的作业调度，系统将用户提交的任务处理为进程，一个进程又可以创建多个子进程，形成可以并发执行的多进程。多处理机调度：关于如何将多个进程（任务）分配到多个处理机上运行83.1.2调度队列模型InputQueueServer9仅有进程调度的调度队列模型StartEventQueueExitTimeSlice10具有高级和低级调度的调度队列模型ReadyQueueI/OQueueI/ORequestTimeSliceExpiredForkaChildWaitforanInterruptInterruptOccursChildExecutesChildTerminatesCPUI/OStart113.1.3调度的性能准则我们可从不同的角度来判断处理机调度算法的性能，如用户的角度、处理机的角度和算法实现的角度。实际的处理机调度算法选择是一个综合的判断结果。12周转时间：作业从提交到完成（得到结果）所经历的时间。包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待。批处理。平均周转时间T平均带权周转时间（带权周转时间W是T(周转)/T(CPU执行)〕响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间。分时系统截止时间：开始截止时间和完成截止时间，与周转时间有些相似。实时系统公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。优先级：可以使关键任务达到更好的指标。1.面向用户的调度性能准则132.面向系统的调度性能准则吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系。批处理系统平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。如：在2小时内完成4个作业，而每个周转时间是1小时，则吞吐量是2个作业/小时处理机利用率：大中型主机各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配。大中型主机14作业的概念一个作业是指在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作。用户的观点：在一次业务处理过程中，从输入程序和数据到输出结果的全过程。作业步：形成中间结果文件；系统的观点（针对作业进行资源分配）：作业由程序及数据（作业体）和作业说明书（作业控制语言）构成。作业由不同的顺序相连的作业步组成。作业步是在一个作业的处理过程中，计算机所做的相对独立的工作。补充内容15作业与进程的关系作业可被看作是用户向计算机提交任务的任务实体，例如一次计算、一个控制过程等进程是计算机为了完成用户任务而设置的执行实体，是系统分配资源的基本单位。计算机要完成一个任务实体，必须有一个以上的执行实体，即一个作业总是由一个以上的多个进程组成作业的状态16作业的状态转换173.2调度算法调度算法的核心问题就是采用什么算法进行资源的分配。调度算法主要有，先来先服务（FCFS）算法、短作业（进程）优先（SJF/SPF）算法、高优先权优先（HPF）算法、高响应比优先调度（HRRN）算法、时间片轮转（RR）算法和多机反馈队列调度（FB）算法等。有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。183.2.1先来先服务调度算法(FCFS,FirstComeFirstService)这是最简单的调度算法，按先后顺序进行调度。FCFS算法：按照作业提交或进程变为就绪状态的先后次序，分派CPU；当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。最简单的算法。19FCFS的特点适用于作业调度和进程调度；比较有利于长作业，而不利于短作业；有利于CPU繁忙的作业，而不利于I/O繁忙的作业。例：进程名提交时间执行时间开始执行时间完成时间周转时间带权周转时间ABCD0123110011000110110211011022021100100199111001.9920CPUSchedulerExampleProcess1burstcomputesfor14timeunitsProcess2burstcomputesfor8timeunitsProcess3burstcomputesfor8timeunits21StartReadyQueueEventQueueEventExitTimeSliceCPU22StartReadyQueueEventQueueEventExitTimeSliceCPU23StartReadyQueueEventQueueEventExitTimeSliceCPU24StartReadyQueueEventQueueEventExitTimeSliceCPU25StartReadyQueueEventQueueEventExitTimeSliceCPU26StartReadyQueueEventQueueEventExitTimeSliceCPU27StartReadyQueueEventQueueEventExitTimeSliceCPU28StartReadyQueueEventQueueEventExitTimeSliceCPU29StartReadyQueueEventQueueEventExitTimeSliceCPU30StartReadyQueueEventQueueEventExitTimeSliceCPU31StartReadyQueueEventQueueEventExitTimeSliceCPU32StartReadyQueueEventQueueEventExitTimeSliceCPU33StartReadyQueueEventQueueEventExitTimeSliceCPU34StartReadyQueueEventQueueEventExitTimeSliceCPU353.2.2短作业优先(SJF,ShortestJobFirst)又称为“短进程优先”SPN(ShortestProcessNext)；这是对FCFS算法的改进，其目标是减少平均周转时间；可用于作业调度和进程调度。SJF算法：对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。36SJF的特点优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量。缺点：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。37例：进程名ABCDE平均提交时间01234执行时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398带权周转时间12.673.21.52.252.1383.2.3高优先权优先调度算法(PriorityScheduling)静态优先级动态优先级是指将处理机分配给就绪队列中优先权最高点进程的调度算法。本算法是多级队列算法的改进，平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢先式和非抢先式。用作作业调度和进程调度基于优先权的调度算法还可以按调度方式不同分为非剥夺优先权调度算法和可剥夺优先权调度算法。39静态优先级依据：作业或进程类型（系统进程优先级较高）对资源的需求（对CPU和内存需求较少的进程，优先级较高）用户要求（紧迫程度和付费多少）创建进程时就确定优先级，直到进程终止前都不改变。通常是一个整数。40动态优先级在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行；进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU。在创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能。如：41高优先权优先调度算法的关键是，它可以采用静态优先权和动态优先权。对于静态优先权调度有可能导致“饥饿”现象，即如果不断地出现优先权高的进程，则优先权低的进程就会“饥饿”。因此，必须采取措施，即可采取动态调整优先权的策略，使得随着进程在CPU上运行时间的增长，其优先权不断调整；对于动态优先权调度算法，需了解其根据哪些因素来调整运行进程的优先权。42响应比:R==是FCFS和SJF的折衷如果作业的等待时间相同，则要求执行的时间愈短，则响应比高，故有利于短作业；当要求执行的时间相同时，响应比决定于其等待时间，因而实现了先来先服务；对于长作业，当其等待时间足够长时，其响应比便可升到很高，也可获得处理机。最高响应比优先法(HRN,HighestResponse_ratioNext)要求执行时间要求执行时间等待时间要求执行时间响应时间433.2.4时间片轮转(RoundRobin)法前几种算法，都说明怎样选择一个进程或作业开始运行，开始运行后的作法都相同，即运行到结束或阻塞，阻塞结束时等待当前进程放弃CPU。本算法主要用于进程调度，说明怎样并发运行，即切换的方式；设计目标是提高资源利用率。其基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率；44时间片轮转算法将系统中所有的就绪进程按照FCFS原则，排成一个队列；每次调度时将CPU分派给队首进程，