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

第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.2作业与作业调度3.3进程调度3.4实时调度3.5死锁概述3.6预防死锁3.7避免死锁3.8死锁的检测与解除3.1处理机调度的层次和调度算法的目标处理机调度的层次高级调度中级调度低级调度3.1处理机调度的层次和调度算法的目标高级调度（也称作业调度、长程调度）功能选择外存上处于后备队列中的一个或几个作业调入内存，并为它们创建进程，分配必要的资源，然后，再将新创建的进程排在就绪队列，准备执行。使用系统批处理系统分时系统和实时系统不需要执行频率分钟、小时或天3.1处理机调度的层次和调度算法的目标低级调度（也称进程调度、短程调度）功能从就绪队列中选择一个进程，然后，由分派程序将处理机分配给该进程。使用系统各种系统均需要执行频率毫秒3.1处理机调度的层次和调度算法的目标中级调度（也称中程调度）功能负责进程在内存和外存对换区之间换进/换出是内存对换功能的一部分目的提高内存利用率和系统吞吐量执行频率介于作业调度和进程调度之间3.1处理机调度的层次和调度算法的目标处理机调度算法的目标共同目标资源利用率公平性平衡性策略强制执行3.1处理机调度的层次和调度算法的目标批处理系统的目标平均周转时间短作业周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔，它包括四部分时间：作业在外存后备队列上等待作业调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU上执行的时间，以及进程等待I/O操作完成的时间平均周转时间可描述为平均带权周转时间则可描述为niiTnT11niiTTnW1s13.1处理机调度的层次和调度算法的目标系统吞吐量高处理机利用率高分时系统的目标响应时间快均衡性实时系统的目标截止时间的保证可预测性3.2作业与作业调度批处理系统中的作业作业和作业步作业（Job）所谓作业就是用户一次请求计算机系统为它完成任务所进行的工作总和作业＝程序＋数据＋作业说明书批处理系统中，以作业为基本单位从外存调入内存作业步（JobStep）一个作业是由若干作业步组成的作业步就是处理作业的各个独立的子任务系统可以创建若干进程完成各作业步的计算3.2作业与作业调度作业控制块JCB（JobControlBlock）是作业在系统中存在的唯一标志包含的内容作业标识、用户名称、用户帐户作业类型（CPU繁忙型、I/O繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业已运行时间）资源需求（预计运行时间、要求内存大小、要求I/O设备的类型和数量等）、资源使用情况进入系统时间、开始处理时间、作业完成时间、作业退出时间3.2作业与作业调度作业运行的三个阶段和三种状态用户作业录入提交收容完成运行就绪阻塞等待I/OI/O完成进程调度作业调度执行作业调度后备运行运行收容完成完成用户作业录入提交收容完成运行就绪阻塞等待I/OI/O完成进程调度作业调度执行作业调度3.2作业与作业调度作业调度的主要任务也称接纳调度作业调度时要决定一次接纳多少个作业：取决于多道程序度和资源使用情况接纳哪些作业：取决于作业调度算法和资源使用情况3.2作业与作业调度先来先服务（FCFS—FirstComeFirstServed）调度算法后备作业队列按FIFO排列，调度时选择处于队首的作业优点：简单、易于实现缺点有利于长作业，不利于短作业3.2作业与作业调度例作业名到达时间服务时间A04B15C22D34A04开始时间完成时间周转时间带权周转时间04414981.691194.51115123平均8.252.525D15B9C113.2作业与作业调度短作业优先（SJF-ShortestJobFirst）调度算法从后备作业队列中选择估计运行时间最短的作业优点：调度性能较好缺点：1）不利于长作业2）不考虑作业的紧迫程度3）估计运行时间很难准确获得3.2作业与作业调度例作业名到达时间服务时间A04B15C22D34开始时间完成时间周转时间带权周转时间04411015142.8464261071.75平均7.251.8875A04D10B15C63.2作业与作业调度优先级（PSA-PrioritySchedulingAlgorithm）调度算法选择优先级最高的后备作业提交作业时说明作业优先级优先级一般利用某一范围内的一个整数来表示3.2作业与作业调度例作业名到达时间服务时间优先级A0103B015C052D534BADC011114193.2作业与作业调度高响应比优先调度算法选择具有最高响应比的后备作业响应比要求服务时间要求服务时间等待时间要求服务时间响应时间PR−优点：既照顾了作业到来的先后，又考虑了要求服务时间的长短，是FCFS和SJF的很好的折衷。−缺点：算法较为复杂；每次调度时，均要重新计算响应比。3.2作业与作业调度例作业名J1J2J3到达时间8:008:309:30服务时间2小时1小时0.25小时三个作业在一台处理机上单道运行，9:40进行作业调度，问三个作业的执行次序？9:40调度时：J1：1+100/120=1+5/6J2：1+70/60=1+7/6J3：1+10/15=1+4/6选择J2作业调度10:40（J2完成）调度时：J1：1+160/120=1+4/3J3：1+70/15=1+14/3选择J3作业调度执行次序：J2、J3、J13.3进程调度进程调度的任务、机制和方式进程调度的功能从就绪队列中选择一个进程，然后，由分派程序将处理机分配给该进程进程调度时只决定选择哪个就绪进程：取决于进程调度算法要解决的问题When：何时分配CPU—进程调度的时机What：按什么原则分配CPU—进程调度算法How：如何分配CPU—CPU调度过程（进程的上下文切换）3.3进程调度进程调度的任务保存处理机的现场信息按某种进程调度算法选取一个就绪进程把处理器分配给该进程进程调度机制排队器分派器上下文切换器3.3进程调度进程调度的时机（When）当进程从执行态转换到阻塞态时（例如提出I/O请求、等待子进程结束、wait操作等）分时系统中时间片到当有一个优先级更高的进程就绪（例如新创建一个进程，一个进程由等待变成就绪）当一个进程运行完毕，或由于某种错误而终止运行3.3进程调度进程调度方式非抢占方式（NonpreemptiveMode）一旦把处理机分配给某个进程，便让该进程一直执行，直至该进程完成或发生某事件而阻塞时，才把处理机分配给其它进程。抢占方式（PreemptiveMode）允许调度程序根据某种原则，去停止某个正在执行的进程，将已分配给该进程的处理机，重新分配给另一进程。时间片原则抢占原则优先权原则短进程优先原则仅在情况1和4下，才进行调度在情况1、2、3、4时均可调度3.3进程调度先来先服务调度算法（FCFS—FirstComeFirstServed）非抢占方式就绪队列按FIFO排列，调度时选择队首进程优点：简单、易于实现缺点：有利于长进程，不利于短进程有利于CPU繁忙型进程，不利于I/O繁忙型进程3.3进程调度短进程优先（SPF－ShortestProcessFirst）调度算法非抢占式或抢占式均可从就绪队列中选择估计运行时间最短的进程优点：调度性能较好缺点：1）不利于长进程2）不考虑进程的紧迫程度3）估计运行时间很难准确获得3.3进程调度例进程名到达时间服务时间A03B05C03D04E83抢占方式1、基于最短服务时间抢占：ACDEDB0368111318ACDEB036101318非抢占方式2、基于最短剩余服务时间抢占：ACDEB0361013183.3进程调度时间片轮转调度算法（RR－RoundRobin）抢占方式主要为分时系统设计就绪队列按FIFO排列，调度时选择队首进程。但该进程占用CPU至多执行一个时间片，便放弃CPU进程切换时机时间片大小的确定3.3进程调度例：时间片=2进程名到达时间服务时间A04B05C02D04开始时间完成时间周转时间带权周转时间010102.52151534663614143.5ABCDABDB02468101214153.3进程调度优先级调度算法非抢占式或抢占式均可选择具有最高优先级的就绪进程优先级（优先权、优先数）利用某一范围内的一个整数来表示不同系统的具体用法各异确定进程优先权的依据进程类型进程对资源的需求用户要求3.3进程调度优先级的类型静态优先级创建进程时确定，在进程的整个运行期间保持不变简单易行，系统开销小，但不够精确仅在要求不高的系统中才使用动态优先级创建进程时确定初值，运行期间基于某种原则动态改变灵活，调度性能好，但系统开销大3.3进程调度例进程名到达时间服务时间优先级A0103B015C052D534BADC01111419非抢占方式BADAC01581419抢占方式3.3进程调度多队列调度算法按性质和类型将就绪队列分为若干子队列，每个就绪进程固定地分属于一个子队列，每个队列有自己的调度算法各队列间的调度方式或采用固定优先权抢占调度，或为各队列分配一定比例的CPU时间3.3进程调度多级反馈队列调度算法抢占方式就绪队列1（FCFS）s1CPU结束或阻塞就绪队列2（FCFS）s2CPU就绪队列n（RR）snCPU提交高优先级低（时间片s1s2sn且si+1=2si）结束或阻塞结束或阻塞3.4实时调度实现实时调度的基本条件提供必要的信息就绪时间开始截止时间和完成截止时间处理时间资源要求优先级系统处理能力强11miiiPC3.4实时调度采用抢占式调度机制大部分采用抢占式调度方式，具有较高的灵活性，较小的延迟，但算法复杂，开销比较大要求不太严格的系统中，也可以采用非剥夺调度方式，以简化系统具有快速切换机制对外部中断的快速响应能力快速的任务分派能力3.4实时调度实时调度算法的分类实时调度是计算机科学中最活跃的研究领域之一分类非抢占式调度算法非抢占式轮转调度算法非抢占式优先调度算法抢占式调度算法基于时钟中断的抢占式优先权调度算法立即抢占的优先权调度算法3.4实时调度非抢占式调度算法非抢占式轮转调度算法可获得数秒至数十秒的响应时间可用于要求不太严格的实时控制系统中3.4实时调度非抢占式优先调度算法可获得仅为数秒至数百毫秒级的响应时间可用于有一定要求的实时控制系统中3.4实时调度抢占式调度算法基于时钟中断的抢占式优先权调度算法调度延迟可降为几十至几毫秒，响应效果较好可用于大多数的实时系统中3.4实时调度立即抢占(ImmediatePreemption)的优先权调度算法能获得非常快的响应，可把调度延迟降低到几毫秒至100微秒，甚至更低。3.4实时调度最早截止时间优先（EDF－EarliestDeadlineFirst）算法根据任务的截止时间来确定任务的优先级，截止时间愈早，其优先级愈高可用于抢占式调度，也可用于非抢占式调度3.4实时调度非抢占式调度方式用于非周期实时任务例任务到达时间开始截止时间执行时间A024B2155C365D6104ACDB04913171342开始截止时间任务执行任务到达12341342t3.4实时调度抢占式调度方式用于周期实时任务在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25ms。进程到达时间执行时间完成截止时间A(1)01020A(2)201040A(3)401060A(4)601080A(5)8010100B(1)02550B(2)5025100开始截止时间103050709025753.4实时调度A1B1A2B1A3B2A4B2A5B1A2A