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

1第三章处理机调度与死锁第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.2作业与作业调度3.3进程调度3.4实时调度3.5死锁概述3.6预防死锁3.7避免死锁3.8死锁的检测与解除习题2第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标调度：是一种资源分配。处理机调度：对处理机资源进行分配。处理机调度算法：根据处理机分配策略所规定的处理机分配算法。处理机调度的层次：一个作业从提交到获得处理机执行，直至作业运行完毕，需要经历多级处理机调度。3第三章处理机调度与死锁如图所示作业调度中级调度运行就绪阻塞进程调度挂起阻塞挂起就绪创建退出4第三章处理机调度与死锁3.1.1处理机调度的层次1.高级调度(HighLevelScheduling)（1）从外存后备队列中选择作业进入就绪队列。（2）在批处理系统中,大多配有作业调度,但在分时系统及实时系统中,一般不配置。（3）作业调度执行频率很低,通常为几分钟一次,甚至更久。5第三章处理机调度与死锁3.1.1处理机调度的层次2.低级调度(LowLevelScheduling)（1）从就绪队列中选择一个进程来执行并分配处理机。（2）是OS中最基本的调度。（3）在多道批处理、分时和实时三种系统中都配置。（4）调度频率非常高，一般几十毫秒一次。6第三章处理机调度与死锁3.1.1处理机调度的层次3.中级调度(IntermediateScheduling)在内存和外存对换区之间按照给定的原则和策略选择进程对换，以解决内存紧张问题，从而提高内存的利用率和系统吞吐量，常用于分时系统或具有虚拟存储器的系统中。7第三章处理机调度与死锁3.1.2处理机调度算法的目标1.处理机调度算法的共同目标(1)资源利用率。为提高系统的资源利用率，应使系统中的处理机和其它所有资源都尽可能地保持忙碌状态，其中最重要的处理机利用率可用以下方法计算：CPU的利用率=空闲等待时间有效工作时间有效工作时间CPUCPUCPU8第三章处理机调度与死锁(2)公平性。公平性是指应使诸进程都获得合理的CPU时间，不会发生进程饥饿现象。公平性是相对的，对相同类型的进程应获得相同的服务；但对于不同类型的进程，由于其紧急程度或重要性的不同，则应提供不同的服务。(3)平衡性。由于在系统中可能具有多种类型的进程，有的属于计算型作业，有的属于I/O型。为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。(4)策略强制执行。对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。9第三章处理机调度与死锁2.批处理系统的目标(1)平均周转时间短。周转时间是评价批处理系统性能的重要指标。周转时间：作业从被提交给系统开始，到作业完成为止的这段时间间隔（称为作业周转时间）。包括四部分的时间：作业在外存后备对列上等待调度的时间；进程在就绪队列上等待进程调度的时间。进程在CPU上执行的时间进程等待I/O操作完成的时间。10第三章处理机调度与死锁n1isiTTn1W带权周转时间：周转时间T与系统为它提供服务的时间TS之比]T[n1Tn1ii11第三章处理机调度与死锁(2)系统吞吐量高。吞吐量：单位时间内系统所完成的作业数。系统吞吐量与批处理作业的平均长度有关。(3)处理机利用率高。要求之间是存在着一定矛盾的。12第三章处理机调度与死锁3.分时系统的目标(1)响应时间快。(2)均衡性：系统响应时间的快慢与用户请求服务的复杂性有关响应时间：从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说，直到屏幕上显示出结果为止的一段时间间隔。包括三部分时间：从键盘输入的请求信息传送到处理机的时间；处理机对请求信息进处理的时间，将所形成的响应信息回送到终端显示器的时间。用来评价分时系统的性能，选择分时系统中进程调度算法的重要准则之一。13第三章处理机调度与死锁4.实时系统的目标(1)截止时间的保证。截止时间：是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。是评价实时系统性能的重要指标，因而是选择实时调度算法的重要准则(2)可预测性。14第三章处理机调度与死锁3.2作业与作业调度在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。操作员把用户提交的作业通过相应的输入设备输入到磁盘存储器，并保存在一个后备作业队列中。再由作业调度程序将其从外存调入内存。15第三章处理机调度与死锁3.2.1批处理系统中的作业1.作业和作业步(1)作业(Job)：用户要求计算机处理的一个问题。包括程序、数据和作业说明书(2)作业步(JobStep)：作业的每一个加工步骤16第三章处理机调度与死锁2.作业控制块(JobControlBlock，JCB)JCB作业在系统中存在的标志。JCB中包含的内容有：作业标识、用户名称、用户账号、作业类型(CPU繁忙型、I/O繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业运行时间)、资源需求(预计运行时间、要求内存大小等)、资源使用情况等。17第三章处理机调度与死锁3.作业运行的三个阶段和三种状态(1)收容阶段：作业到达硬盘，建立JCB，放入后备队列，称为后备状态。(2)运行阶段。作业被作业调度程序选中，而被送入主存中投入运行的状态。(3)完成阶段。作业完成其全部运行，释放出其所占用的全部资源，准备退出系统时状态。18第三章处理机调度与死锁3.2.2作业调度的主要任务作业调度程序完成以下工作：1.按照某种调度算法从后备作业队列中挑选作业；2.为选中的作业分配主存和外设资源；3.为选中的作业建立相应的进程，作业调度程序以进程的形式存在（祖先进程）；4.构造和填写作业运行时所需的有关表格；5.作业结束时完成该作业的善后工作，如收回资源，输出必要的信息，撤消该作业的全部进程PCB和JCB。作业调度考虑的问题1.决定接纳多少个作业、2.决定接纳哪些作业19第三章处理机调度与死锁3.2.3先来先服务和短作业优先调度算法1.先来先服务调度算法20第三章处理机调度与死锁1.先来先服务调度算法适用类型：最简单，适用于作业调度和进程调度；常作为辅助算法特点：该算法比较有利于长作业（进程），而不利于短作业（进程）该算法有利于CPU繁忙型作业，而不利于I/O繁忙型的作业。缺点：（1）不利于短作业（2）不利于IO繁忙型作业（3）完全未考虑作业的紧迫程度，因而不能保证紧迫性作业21第三章处理机调度与死锁图3-4FCFS和SJF调度算法的性能22第三章处理机调度与死锁2.短作业(进程)优先调度算法短作业(进程)优先调度算法：是指对短作业或短进程优先调度的算法。适用类型：可以分别用于作业调度和进程调度。优点：能有效的降低作业的平均等待时间，提高系统吞吐量缺点：该算法对长作业不利：如果调度程序总是挑选那些短作业，将导致长作业长期不被调度。该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会被及时处理。由于作业（进程）的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意缩短其作业的估计运行23第三章处理机调度与死锁3.2.4优先级调度算法和高响应比优先调度算法1.优先级调度算法(priority-schedulingalgorithm，PSA)问题：FCFS和SJF算法都不能反映作业的紧迫程度。解决方法：由外部赋予作业相应的优先级,可以保证紧迫型作业优先24第三章处理机调度与死锁2.高响应比优先调度算法(HighestResponseRatioNext，HRRN)FCFS算法：所考虑的只是作业的等待时间，而忽视了作业的运行时间。SJF算法：只考虑作业的运行时间，而忽视了作业的等待时间。25第三章处理机调度与死锁高响应比优先算法的实现：为每个作业引入一个动态优先级，令它随等待时间延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可描述为：要求服务时间要求服务时间等待时间优先权26第三章处理机调度与死锁由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先级又相当于响应比RP。要求服务时间响应时间要求服务时间要求服务时间等待时间PR27第三章处理机调度与死锁结论：（1）如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。(2）当要求服务的时间相同时，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。（3）对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。优缺点：既照顾了短作业，又考虑了作业到达的先后次序，又不会使作业长期得不到服务，很好的折中。每次要进行调度之前，都须先做响应比的计算，会增加系统开销。28第三章处理机调度与死锁作业提交时间运行时间/H18．001．028．500．539．000．249．100．1试计算以下3种作业调度算法的平均周转时间和平均带权周转时间。先来先服务，短作业优先，响应比高优先29第三章处理机调度与死锁 3.3进程调度3.3.1进程调度的任务、机制和方式1.进程调度的任务(1)保存处理机的现场信息。(2)按某种算法选取进程。(3)把处理器分配给进程。30第三章处理机调度与死锁2.进程调度机制为了实现进程调度，在进程调度机制中，应具有如下三个基本部分，如图3-1所示。(1)排队器。(2)分派器。(3)上下文切换器。31第三章处理机调度与死锁图3-1进程调度机制32第三章处理机调度与死锁3.进程调度方式1)非抢占方式(NonpreemptiveMode)一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程。33第三章处理机调度与死锁2)抢占方式(PreemptiveMode)允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。优点：（1）对于批处理机系统，可以防止一个长进程长时间地占用处理机，以确保处理机能为所有进程提供更为公平的服务。（2）在分时系统中，只有采用抢占方式才有可能实现人—机交互。（3）在实时系统中，抢占方式能满足实时任务的需求。缺点：抢占方式比较复杂，所需付出的系统开销也较大。34第三章处理机调度与死锁3.3.2轮转调度算法1.轮转法的基本原理系统将所有的就绪进程按FCFS策略排成一个就绪队列。系统可设置每隔一定时间(如30 ms)便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。35第三章处理机调度与死锁2.进程切换时机①若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，再调度就绪队列中队首的进程运行，并启动一个新的时间片。②在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。36第三章处理机调度与死锁3.时间片大小的确定时间片：规定进程一次使用处理器的最长时间。时间片的大小：可以相同，也可以不同。时间片越大，系统效率越高。时间片越小，交互能力就越强。优点：这样可以保证在系统给定的时间内响应所有的用户。缺点：时间片的选择很重要时间片过大，该算法退化为先来先服务。时间片过小，切换次数增加，增加了系统开销。37第三章处理机调度与死锁图3-2时间片大小对响应时间的影响38第三章处理机调度与死锁39第三章处理机调度与死锁3.3.3优先级调度算法1.优先级调度算法的类型优先级进程调度算法，是把处理机分配给就绪队列中优先级最高的进程。(1)非抢占式优先级调度算法。(2)抢占式优先级调度算法。40第三章处理机调度与死锁2.优先级的类型1)静态优先级静态优先级：创建进程时确定，整个运行期间保持不变。优先级是利用某一范围内的一个整