第4章处理机调度.

第三章处理机调度与死锁第4章处理机调度分级调度作业调度进程调度调度算法实时系统调度方法第三章处理机调度与死锁在计算机系统中，可能同时有数百个批处理作业存放在磁盘的作业队列中，或者有数百个终端与主机相连接，这样一来内存和处理器等资源便供不应求。如何从这些作业中挑选作业进入主存运行、如何在进程之间分配处理器时间，无疑是操作系统资源管理中的一个重要问题。处理器调度用来完成涉及处理器分配的工作。概述第三章处理机调度与死锁作业的状态及其转换一个作业从提交给计算机系统到执行结束退出系统，一般都要经历提交、收容、执行和完成等4个状态。（以前我们讲授过该部分内容）4.1分级调度第三章处理机调度与死锁图4.1作业的状态及其转换第三章处理机调度与死锁一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态。处于提交状态的作业，因其信息尚未全部进入系统，所以不能被调度程序选取。收容状态也称为后备状态。输入管理系统不断地将作业输入到外存中对应部分（或称输入井，即专门用来存放待处理作业信息的一组外存分区）。若一个作业的全部信息已全部被输入进输入井，那么，在它还未被调度去执行之前，该作业处于收容状态。4.1分级调度第三章处理机调度与死锁作业调度程序从后备作业中选取若干个作业到内存投入运行。它为被选中作业建立进程并分配必要的资源，这时，这些被选中的作业处于执行状态。当作业运行完毕，但它所占用的资源尚未全部被系统回收时，该作业处于完成状态。在这种状态下，系统需做诸如打印结果、回收资源等类的善后处理工作。4.1分级调度第三章处理机调度与死锁调度的层次一般来说，处理机调度可以分为三级：高级调度：又称作业调度或长程调度（Long-termScheduling）。其主要任务是按一定的原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、输入输出设备等必要的资源，并建立相应的进程，以使该作业的进程获得竞争处理机的权利。另外，当该作业执行完毕时，回收系统资源。4.1分级调度第三章处理机调度与死锁调度的层次中级调度：又称交换调度、平衡负载调度或中程调度（Medium-termScheduling）。中级调度根据存储资源量和进程的当前状态来决定辅存和主存中的进程的对换，它所使用的方法是通过把一些进程换出主存，从而，使之进入“挂起”状态，不参与低级调度，起到短期平滑和调整系统负荷的作用。交换调度主要涉及到内存管理与扩充。4.1分级调度第三章处理机调度与死锁调度的层次低级调度：又称进程调度（或线程调度）、短程调度（Short-termScheduling）。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。在确定了占用处理机的进程后，系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境。通常，我们所说的调度一般指进程调度。4.1分级调度第三章处理机调度与死锁关于不同级别调度的说明：在多道批处理系统中，存在着作业调度和进程调度；在分时系统和实时系统中，一般不存在作业调度，而只有进程调度、交换调度。因而，这些系统中没有作业提交状态和后备状态。它们的输入信息经过终端缓冲区为系统所接收，或者立即处理，或者经交换调度暂存外存中。现代操作系统偏向于后者。4.1分级调度第三章处理机调度与死锁选择调度算法的原则资源利用率—使得CPU或其他资源的使用率尽可能高且能够并行工作，CPU利用率=CPU有效工作时间/CPU总运行时间。响应时间—交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。使交互式用户的响应时间尽可能短，或尽快处理实时任务。分时系统和实时系统调度算法设计原则第三章处理机调度与死锁选择调度算法的原则周转时间—批处理用户从作业提交开始，到作业完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间尽可能短。批处理系统吞吐率—使单位时间内处理的作业数尽可能多。公平性—确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死情况。调度算法设计原则第三章处理机调度与死锁作业调度（批处理系统）作业调度主要是完成作业从后备状态到执行状态的转变，以及从执行状态到完成状态的转变。作业调度功能(1)记录系统中各作业的状况。系统为每个作业建立一个作业控制表JCB记录这些有关信息。系统通过JCB而感知作业的存在。JCB主要内容：作业名、作业类型、资源要求、当前状态、资源使用情况以及该作业的优先级等。4.2作业调度第三章处理机调度与死锁图4.2作业控制块JCB作业名作业类型资源要求资源使用情况优先级(数)当前状态其他4.2作业调度第三章处理机调度与死锁作业调度（批处理系统）作业调度功能(2)从后备队列中挑选出一部分作业投入执行。(3)为被选中作业做好执行前的准备工作。为选中作业建立相应进程，并分配系统资源。(4)在作业执行结束时做善后处理工作。主要是输出作业管理信息，回收该作业所占用的资源，撤消与该作业有关的全部进程和该作业的作业控制块等等。4.2作业调度第三章处理机调度与死锁作业调度算法设计原则周转时间与带权周转时间定义作业i的周转时间为;Ti=Tei-Tsi其中Tei为作业i的完成时间，Tsi为作业的提交时间。对于被测定作业流所含有的n（n=1）个作业来说，其平均周转时间为：nii=11T=Tn4.2作业调度第三章处理机调度与死锁作业调度算法设计原则周转时间与带权周转时间定义周转时间一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：等待时间；执行时间，即：Ti=Twi＋Tri这里，Twi主要指作业i由后备状态到执行状态的等待时间，它不包括作业进入执行状态后的等待时间。4.2作业调度第三章处理机调度与死锁作业调度算法设计原则周转时间与带权周转时间定义带权周转时间带权周转时间是作业周转时间与作业执行时间的比：Wi=Ti/Tri对于被测定作业流所含有的几个作业来说，其平均带权周转时间为：nii=11W=Wn4.2作业调度第三章处理机调度与死锁4.2作业调度•例：单道程序环境下，下面三个作业同时到达系统并立即进入调度，调度顺序为1、2、3：第三章处理机调度与死锁4.2作业调度假设系统中没有其他作业，那么，三个作业的周转时间分别为：28、37和40，因此，平均作业周转时间T=（28+37+40）/3=35若顺序改为2、1、3，则平均周转时间为约29；如顺序改为3、2、1，则平均周转时间为约18。第三章处理机调度与死锁进程调度无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数，这将导致用户进程互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。4.3进程调度第三章处理机调度与死锁进程调度进程调度的功能(1)记录系统中所有进程的执行情况：进程管理模块将进程的执行情况和状态记录在PCB中。进程调度模块根据PCB来控制进程的执行。(2)选择占有处理机的进程：进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。(3)进行进程上下文切换一个进程的执行是在进程的上下文中执行。当进程调度时，如果发生新进程被选中，系统要完成进程的切换。4.3进程调度第三章处理机调度与死锁进程上下文切换进程上下文由正文段、数据段、硬件寄存器的内容以及有关数据结构等组成。在发生进程调度时，系统要做进程上下文切换。进程上下文切换包括以下步骤：(1)决定是否做上下文切换以及是否允许做上下文切换。包括对进程调度原因的检查分析，以及当前执行进程的资格和CPU执行方式的检查等。4.3进程调度第三章处理机调度与死锁进程上下文切换(2)保存当前执行进程的上下文。(3)使用进程调度算法，选择一个处于就绪状态进程。(4)恢复或装配调度选中进程的上下文，将CPU控制权交给该进程。4.3进程调度第三章处理机调度与死锁进程调度的时机进程调度发生在什么时机呢？这与引起进程调度的原因以及进程调度的方式有关。引起进程调度的原因有以下几类：(1)正在执行的进程执行完毕；(2)进程执行了阻塞原语进入睡眠状态；(3)进程调用了PV操作，被阻塞或唤醒一进程；(4)进程提出I／O请求后被阻塞；4.3进程调度第三章处理机调度与死锁进程调度的时机(5)进程的时间片已经用完；(6)在执行完系统调用，调度选择新用户进程执行；(7)就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。4.3进程调度第三章处理机调度与死锁进程调度的时机进程调度的方式非剥夺式—一个作业一旦投入运行，除非进程本身自愿让出CPU，否则一直运行完成，调度算法不得剥夺其运行权。剥夺式—系统实时地根据调度原则，当某就绪进程满足条件时，立即将正在运行的进程中断，并切换到其进程。4.3进程调度第三章处理机调度与死锁4.3进程调度•进程调度性能评价进程调度性能的衡量方法分为定性和定量2种定性：调度的可靠性和简洁性定量：CPU的利用率评价和进程在就绪队列中的等待时间与执行之间之比第三章处理机调度与死锁先来先服务（FCFS，FirstComeFirstServe）算法该算法是按照作业进入系统的作业后备队列的先后次序来挑选作业，先进入系统的作业优先被挑选。这是一种非剥夺式算法，易实现，效率低，不利于短作业，但优待了长作业，可能使短作业周转时间变得很大。影响批作业的平均周转时间。该算法适用于作业调度和进程调度。4.4调度算法第三章处理机调度与死锁先来先服务（FCFS）在实际操作系统中，尽管很少单独使用FCFS算法，但和其他一些算法配合起来，FCFS算法还是使用得相当多的。例如基于优先级的调度算法就是对具有同样优先级的作业或进程采用的FCFS方式。4.4调度算法第三章处理机调度与死锁最短作业优先SJF（ShortestJobFirst）该算法是以进入系统的作业所要求的CPU时间长短为标准，总是选取估计计算时间最短的作业投入运行。这是一种非剥夺式调度算法，它克服了FCFS偏爱长作业的缺点，易于实现，但效率也不高。该算法适用于作业调度。4.4调度算法第三章处理机调度与死锁最短作业优先SJF（ShortestJobFirst）主要不足：一是预先估计作业计算时间很难精确；二是忽视了长作业的等待时间，长作业可能会出现饥饿现象；三是该算法由于属于非剥夺机制，对分时、实时处理不理想。4.4调度算法第三章处理机调度与死锁最短作业优先SJF（ShortestJobFirst）例：若有以下四个作业同时到达系统并立即进入调度：4.4调度算法第三章处理机调度与死锁最短作业优先SJF（ShortestJobFirst）现对它们实施SJF调度算法，这时的作业调度顺序为作业2、4、1、3，则：平均周转时间T=(4+12+21+31)/4=17平均带权周转时间W=(4/4+12/8+21/9+31/10)/4=1.98如果对它们施行FCFS调度算法，则：平均周转时间T=(9+13+23+31)/4=19平均带权周转时间W=(9/9+13/4+23/10+31/8)/4=2.514.4调度算法第三章处理机调度与死锁最短作业优先SJF（ShortestJobFirst）例：设有一组作业，它们的提交时间及运行时间如下表，在单道方式下，采用短作业优先调度算法，作业的执行顺序是___.作业号提交时间运行时间（分钟）19：007029：403039：5010410：1054.4调度算法第三章处理机调度与死锁最短作业优先SJF（ShortestJobFirst）SJF算法是非抢占式的，可以改进成抢占式的调度算法。当一个作业正在执行时，一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，抡占式短作业优先调度算法强行赶走当前正在执行的作业，这种方式叫最短剩余时间优先算法SRTF（ShortestRemainingTimeFirst）算法。此算法适用于作业调度和进程调度。4.4调