计算机操作系统第四版-汤小丹-教案第三章

西安电子科技大学出版社高等学校计算机类“十二五”规划教材部级优秀教材计算机操作系统汤小丹梁红兵哲凤屏汤子瀛(第四版)编著2第三章处理机调度与死锁第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.2作业与作业调度3.3进程调度3.4实时调度3.5死锁概述3.6预防死锁3.7避免死锁3.8死锁的检测与解除习题3第三章处理机调度与死锁 3.1处理机调度的层次和调度算法的目标在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。在多道批处理系统中，一个作业从提交到获得处理机执行，直至作业运行完毕，可能需要经历多级处理机调度，下面先来了解处理机调度的层次。4第三章处理机调度与死锁3.1.1处理机调度的层次1.高级调度(HighLevelScheduling)2.低级调度(LowLevelScheduling)3.中级调度(IntermediateScheduling)5第三章处理机调度与死锁3.1.2处理机调度算法的目标1.处理机调度算法的共同目标(1)资源利用率。为提高系统的资源利用率，应使系统中的处理机和其它所有资源都尽可能地保持忙碌状态，其中最重要的处理机利用率可用以下方法计算：CPU的利用率=空闲等待时间有效工作时间有效工作时间CPUCPUCPU6第三章处理机调度与死锁(2)公平性。公平性是指应使诸进程都获得合理的CPU时间，不会发生进程饥饿现象。公平性是相对的，对相同类型的进程应获得相同的服务；但对于不同类型的进程，由于其紧急程度或重要性的不同，则应提供不同的服务。(3)平衡性。由于在系统中可能具有多种类型的进程，有的属于计算型作业，有的属于I/O型。为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。(4)策略强制执行。对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。7第三章处理机调度与死锁2.批处理系统的目标(1)平均周转时间短。对每个用户而言，都希望自己作业的周转时间最短。但作为计算机系统的管理者，则总是希望能使平均周转时间最短，这不仅会有效地提高系统资源的利用率，而且还可使大多数用户都感到满意。应使作业周转时间和作业的平均周转时间尽可能短。否则，会使许多用户的等待时间过长，这将会引起用户特别是短作业用户的不满。可把平均周转时间描述为：]T[n1Tn1ii8第三章处理机调度与死锁为了进一步反映调度的性能，更清晰地描述各进程在其周转时间中，等待和执行时间的具体分配状况，往往使用带权周转时间，即作业的周转时间T与系统为它提供服务的时间Ts之比，即W = T/Ts。而平均带权周转时间则可表示为：n1isiTTn1W9第三章处理机调度与死锁(2)系统吞吐量高。由于吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度有关。事实上，如果单纯是为了获得高的系统吞吐量，就应尽量多地选择短作业运行。(3)处理机利用率高。对于大、中型计算机，CPU价格十分昂贵，致使处理机的利用率成为衡量系统性能的十分重要的指标；而调度方式和算法又对处理机的利用率起着十分重要的作用。如果单纯是为使处理机利用率高，应尽量多地选择计算量大的作业运行。由上所述可以看出，这些要求之间是存在着一定矛盾的。10第三章处理机调度与死锁3.分时系统的目标(1)响应时间快。(2)均衡性。11第三章处理机调度与死锁4.实时系统的目标(1)截止时间的保证。(2)可预测性。12第三章处理机调度与死锁3.2作业与作业调度在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。操作员把用户提交的作业通过相应的输入设备输入到磁盘存储器，并保存在一个后备作业队列中。再由作业调度程序将其从外存调入内存。13第三章处理机调度与死锁3.2.1批处理系统中的作业1.作业和作业步(1)作业(Job)。(2)作业步(JobStep)。14第三章处理机调度与死锁2.作业控制块(JobControlBlock，JCB)为了管理和调度作业，在多道批处理系统中，为每个作业设置了一个作业控制块JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。通常在JCB中包含的内容有：作业标识、用户名称、用户账号、作业类型(CPU繁忙型、I/O繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业运行时间)、资源需求(预计运行时间、要求内存大小等)、资源使用情况等。15第三章处理机调度与死锁3.作业运行的三个阶段和三种状态作业从进入系统到运行结束，通常需要经历收容、运行和完成三个阶段。相应的作业也就有“后备状态”、“运行状态”和“完成状态”。(1)收容阶段。(2)运行阶段。(3)完成阶段。16第三章处理机调度与死锁3.2.2作业调度的主要任务作业调度的主要任务是，根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度。因此，也把作业调度称为接纳调度(AdmissionScheduling)。在每次执行作业调度时，都需做出以下两个决定。1.接纳多少个作业2.接纳哪些作业17第三章处理机调度与死锁3.2.3先来先服务(FCFS)和短作业优先(SJF)调度算法1.先来先服务(first-comefirst-served，FCFS)调度算法FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。18第三章处理机调度与死锁2.短作业优先(shortjobfirst，SJF)的调度算法由于在实际情况中，短作业(进程)占有很大比例，为了能使它们能比长作业优先执行，而产生了短作业优先调度算法。1)短作业优先算法SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业调度和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。19第三章处理机调度与死锁2)短作业优先算法的缺点SJF调度算法较之FCFS算法有了明显的改进，但仍然存在不容忽视的缺点：(1)必须预知作业的运行时间。在采用这种算法时，要先知道每个作业的运行时间。即使是程序员也很难准确估计作业的运行时间，如果估计过低，系统就可能按估计的时间终止作业的运行，但此时作业并未完成，故一般都会偏长估计。(2)对长作业非常不利，长作业的周转时间会明显地增长。更严重的是，该算法完全忽视作业的等待时间，可能使作业等待时间过长，出现饥饿现象。20第三章处理机调度与死锁(3)在采用FCFS算法时，人—机无法实现交互。(4)该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理。21第三章处理机调度与死锁3.2.4优先级调度算法和高响应比优先调度算法1.优先级调度算法(priority-schedulingalgorithm，PSA)我们可以这样来看作业的优先级，对于先来先服务调度算法，作业的等待时间就是作业的优先级，等待时间越长，其优先级越高。对于短作业优先调度算法，作业的长短就是作业的优先级，作业所需运行的时间越短，其优先级越高。但上述两种优先级都不能反映作业的紧迫程度。22第三章处理机调度与死锁2.高响应比优先调度算法(HighestResponseRatioNext，HRRN)在批处理系统中，FCFS算法所考虑的只是作业的等待时间，而忽视了作业的运行时间。而SJF算法正好与之相反，只考虑作业的运行时间，而忽视了作业的等待时间。高响应比优先调度算法则是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。23第三章处理机调度与死锁高响应比优先算法是如何实现的呢?如果我们能为每个作业引入一个动态优先级，即优先级是可以改变的，令它随等待时间延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可描述为：要求服务时间要求服务时间等待时间优先权24第三章处理机调度与死锁由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先级又相当于响应比RP。据此，优先又可表示为：要求服务时间响应时间要求服务时间要求服务时间等待时间PR25第三章处理机调度与死锁 3.3进程调度进程调度是OS中必不可少的一种调度。因此在三种类型的OS中，都无一例外地配置了进程调度。此外它也是对系统性能影响最大的一种处理机调度，相应的，有关进程调度的算法也较多。26第三章处理机调度与死锁3.3.1进程调度的任务、机制和方式1.进程调度的任务进程调度的任务主要有三：(1)保存处理机的现场信息。(2)按某种算法选取进程。(3)把处理器分配给进程。27第三章处理机调度与死锁2.进程调度机制为了实现进程调度，在进程调度机制中，应具有如下三个基本部分，如图3-1所示。(1)排队器。(2)分派器。(3)上下文切换器。28第三章处理机调度与死锁图3-1进程调度机制29第三章处理机调度与死锁3.进程调度方式1)非抢占方式(NonpreemptiveMode)在采用这种调度方式时，一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程。30第三章处理机调度与死锁2)抢占方式(PreemptiveMode)这种调度方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。在现代OS中广泛采用抢占方式，这是因为：对于批处理机系统，可以防止一个长进程长时间地占用处理机，以确保处理机能为所有进程提供更为公平的服务。在分时系统中，只有采用抢占方式才有可能实现人—机交互。在实时系统中，抢占方式能满足实时任务的需求。但抢占方式比较复杂，所需付出的系统开销也较大。31第三章处理机调度与死锁3.3.2轮转调度算法1.轮转法的基本原理在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。系统可设置每隔一定时间(如30 ms)便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。这样，就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。32第三章处理机调度与死锁2.进程切换时机在RR调度算法中，应在何时进行进程的切换，可分为两种情况：①若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。②在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。33第三章处理机调度与死锁3.时间片大小的确定在轮转算法中，时间片的大小对系统性能有很大的影响。图3-2示出了时间片大小对响应时间的影响，其中图(a)是时间片略大于典型交互的时间，而图(b)是时间片小于典型交互的时间。图3-3示出了时间片分别为q = 1和q = 4时对平均周转时间的影响。34第三章处理机调度与死锁图3-2时间片大小对响应时间的影响35第三章处理机调度与死锁图3-3q = 1和q = 4时进程的周转时间进程名ABCDE平均到达