3 第三章 处理机调度与死锁(第四版)模板

苏州大学应用技术学院徐云龙第三章处理机调度与死锁12020年2月19日©SUDA_徐云龙在多道程序环境下，内存中存在着多个进程，其数目往往多于处理机数目。要求系统按某种算法，动态地把处理机分配给处于就绪状态的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。对于大型系统运行时的性能，如系统吞吐量、资源利用率、作业周转时间或响应的及时性等，取决于处理机调度性能的好坏，因而，处理机调度便成为OS中至关重要的部分。绪论22020年2月19日©SUDA_徐云龙3.1处理机调度的层次和调度算法的目标3.2作业与作业调度3.3进程调度3.4实时调度3.5死锁概述3.6预防死锁3.7避免死锁3.8死锁的检测与解除contents32020年2月19日©SUDA_徐云龙在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。在多道批处理系统中，一个作业从提交到获得处理机执行，直到作业运行完毕，可能需要经历多级处理机调度。3.1处理机调度的层次和调度算法的目标42020年2月19日©SUDA_徐云龙作业调度与进程调度的层次关系作业流作业进入“输入井”等待执行作业被装入主存，作业进程“就绪”进程“运行”预输入作业调度进程调度52020年2月19日©SUDA_徐云龙1.高级调度（HighLevelScheduling、长程调度、作业调度）2.低级调度（LowLevelScheduling、短程调度、进程调度）3.中级调度（IntermediateScheduling、内存调度）3.1.1处理机调度的层次62020年2月19日©SUDA_徐云龙调度对象：作业主要功能：根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。用于多道批处理系统，在分时和实时系统中不设置高级调度。1.高级调度72020年2月19日©SUDA_徐云龙调度对象：进程（或内核级线程）主要功能：根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序dispatcher将处理机分配给被选中的进程。进程调度是最基本的调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。2.低级调度82020年2月19日©SUDA_徐云龙引入中级调度的主要目的：提高内存利用率和系统吞吐量。为此，应把那些暂时不能运行的进程，调到外存等待，此时进程的状态称为就绪驻外存状态（挂起状态）。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定，把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。3.中级调度（对换）92020年2月19日©SUDA_徐云龙1.处理机调度算法的共同目标2.批处理系统的目标3.分时系统的目标4.实时系统的目标3.1.2处理机调度算法的目标102020年2月19日©SUDA_徐云龙（1）资源利用率为提高系统的资源利用率，应使系统中的处理机和其它所有资源都尽可能地保持忙碌状态，其中最重要的处理机利用率可用以下方法计算：1.处理机调度算法的共同目标11空闲等待时间有效工作时间有效工作时间的利用率CPUCPUCPUCPU2020年2月19日©SUDA_徐云龙（2）公平性公平性是指应使诸进程都获得合理的CPU时间，不会发生进程饥饿现象。公平性是相对的，对相同类型的进程应获得相同的服务；但对于不同类型的进程，由于其紧急程度或重要性的不同，则应提供不同的服务。1.处理机调度算法的共同目标122020年2月19日©SUDA_徐云龙（3）平衡性由于在系统中可能具有多种类型的进程，有的属于计算型作业，有的属于I/O型。为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。1.处理机调度算法的共同目标132020年2月19日©SUDA_徐云龙（4）策略强制执行对所制定的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。1.处理机调度算法的共同目标142020年2月19日©SUDA_徐云龙（1）平均周转时间短（2）系统吞吐量高（3）处理机利用率高2.批处理系统的目标152020年2月19日©SUDA_徐云龙周转时间：从作业被提交给系统开始，到作业完成为止的这段时间（称为作业周转时间）。包括：作业在外存后备队列上等待（作业）调度的时间进程在就绪队列上等待进程调度的时间进程在CPU上执行的时间进程等待I/O操作完成的时间后三项在一个作业的整个处理过程中，可能发生多次。（1）平均周转时间短162020年2月19日©SUDA_徐云龙对每个用户而言，都希望自己作业的周转时间最短。但作为计算机系统的管理者，则总是希望能使平均周转时间最短，这不仅会有效地提高系统资源利用率，而且还可使大多数用户都感到满意。应使作业周转时间和作业平均周转时间尽可能短。否则，会使许多用户的等待时间过长，这将会引起用户特别是短作业用户的不满。平均周转时间（1）平均周转时间短17niiTnT112020年2月19日©SUDA_徐云龙为了进一步反映调度的性能，更清晰地描述各进程在其周转时间中，等待和执行时间的具体分配状况，往往使用带权周转时间，即作业的周转时间T与系统为它提供服务的时间Ts之比，即W=T/Ts。平均带权周转时间（1）平均周转时间短18nisiiTTnW112020年2月19日©SUDA_徐云龙吞吐量：在单位时间内系统所完成的作业数。与批处理作业的平均长度有关。事实上，如果单纯是为了获得高的系统吞吐量，就应尽量多地选择短作业运行。（2）系统吞吐量高192020年2月19日©SUDA_徐云龙对于大中型计算机，CPU价格昂贵，致使处理机的利用率成为衡量系统性能的十分重要的指标；而调度方式和算法又对处理机的利用率起着十分重要的作用。如果单纯是为使处理机利用率高，应尽量多地选择计算量大的作业运行。以上要求之间存在着一定矛盾！（3）处理机利用率高202020年2月19日©SUDA_徐云龙（1）响应时间快（2）均衡性3.分时系统的目标212020年2月19日©SUDA_徐云龙响应时间快是选择分时系统中进程调度算法的重要准则。响应时间：从用户通过键盘提交一个请求开始，直到屏幕上显示出处理结果为止的一段时间间隔。包括：请求信息从键盘输入开始，直到将其传送到处理机的时间处理机对请求信息进行处理的时间将所形成的响应信息回送到终端显示器的时间（1）响应时间快222020年2月19日©SUDA_徐云龙用户对响应时间的要求并非完全相同。通常用户对较复杂任务的响应时间允许较长，而对较简单任务的响应时间则要短。均衡性：系统响应时间的快慢应与用户所请求服务的复杂性相适应。（2）均衡性232020年2月19日©SUDA_徐云龙（1）截止时间的保证（2）可预测性4.实时系统的目标242020年2月19日©SUDA_徐云龙截止时间：某任务必须开始执行的最迟时间，或必须完成的最迟时间。对于严格的实时系统，其调度方式和调度算法必须能保证这一点，否则将可能造成难以预料的后果。对于实时系统而言，调度算法的一个主要目标是保证实时任务对截止时间的要求。对于HRT任务，其调度方式和调度算法必须确保对截止时间的要求，否则将可能造成难以预料的后果；对于SRT任务，其调度方式和调度算法也应基本上能保证对截止时间的要求。（1）截止时间的保证252020年2月19日©SUDA_徐云龙在实时系统中，可预测性显得非常重要。例如，在多媒体系统中，无论是电影还是电视剧都应是连续播放的，这就提供了请求的可预测性。如果系统中采用了双缓冲，则因为可实现第i帧的播放和第i+1帧的读取并行处理，进而可提高其实时性。（2）可预测性262020年2月19日©SUDA_徐云龙在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。操作员把用户提交的作业通过相应的输入设备输入到磁盘存储器，并保存在一个后备作业队列中。再由作业调度程序将其从外存调入内存。3.2作业与作业调度272020年2月19日©SUDA_徐云龙3.2.1批处理系统中的作业3.2.2作业调度的主要任务3.2作业与作业调度282020年2月19日©SUDA_徐云龙1.作业和作业步2.作业控制块（JobControlBlock，JCB）3.作业运行的三个阶段和三种状态3.2.1批处理系统中的作业292020年2月19日©SUDA_徐云龙（1）作业(Job)作业是一个比程序更为广泛的概念，不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。1.作业和作业步302020年2月19日©SUDA_徐云龙（2）作业步(JobStep)在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，把其中的每一个加工步骤称为一个作业步，各作业步之间存在着相互联系。1.作业和作业步312020年2月19日©SUDA_徐云龙（3）作业流若干个作业进入系统后，被依次存放在外存上，形成输入作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。1.作业和作业步322020年2月19日©SUDA_徐云龙“编译”作业步；“连接装配”作业步；“运行”作业步。典型作业的作业步332020年2月19日©SUDA_徐云龙为了管理和调度作业，在多道批处理系统中，为每个作业设置了一个作业控制块JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。JCB内容：作业标识、用户全称、用户账号、作业类型（CPU繁忙型、I/O繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业运行时间）、资源需求（预计运行时间、要求内存大小等）、资源使用情况等。2.作业控制块JCB342020年2月19日©SUDA_徐云龙一个作业进入系统，“作业注册”程序为该作业建立JCB，再根据作业类型，将它放到相应的作业后备队列中等待调度。调度程序依据一定的调度算法来调度它们，被调度到的作业将被装入内存。在作业运行期间，系统就按照JCB中的信息和作业说明书对作业进行控制。当一个作业执行结束进入完成状态时，系统负责回收已分配给它的资源，撤销该JCB。2.作业控制块JCB352020年2月19日©SUDA_徐云龙作业从进入系统到运行结束，通常需要经历收容、运行和完成三个阶段。相应的作业有“后备状态”、“运行状态”、“完成状态”。3.作业运行的三个阶段和三种状态362020年2月19日©SUDA_徐云龙收容阶段：操作员把用户提交的作业通过某种输入方式或SPOOLing系统输入到硬盘，再为该作业建立JCB，并把它放入作业后备队列。相应地，此时作业的状态为“后备状态”。运行阶段：当作业被作业调度选中后，便为它分配必要的资源和建立进程，并将它放入就绪队列。一个作业从第一次进入就绪状态开始，直到它运行结束前，在此期间都处于“运行状态”。完成阶段：当作业运行完成、或发生异常情况而提前结束时，作业便进入完成阶段，相应的作业状态为“完成状态”。此时系统中的“终止作业”程序将会回收已分配给该作业的JCB和所有资源，并将作业运行结果信息形成输出文件后输出。3.作业运行的三个阶段和三种状态372020年2月19日©SUDA_徐云龙作业调度的主要任务是，根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度。因此，也把作业调度称为接纳调度(AdmissionScheduling)。在每次执行作业调度时，都需做出以下2个决定。1.接纳多少个作业2.接