搜索
第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标3.2作业与作业调度3.3进程调度3.4实时调度3.5死锁概述3.6预防死锁3.7避免死锁3.8死锁的检测与解除第三章处理机调度与死锁3.1处理机调度的层次和调度算法的目标1.处理机调度的层次⑴高级调度又称长程调度或作业调度。根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。高级调度主要用于多道批处理系统中。作业调度的主要功能是：按照一定的算法，从外存的后备队列中选取某些作业调入内存;为它们创建进程、分配必要的资源;然后再将新创建的进程插入就绪队列⑵低级调度又称为进程调度或短程调度。根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序，将处理机分配给被选中的进程。进程调度是最基本的一种调度。⑶中级调度又称为内存调度。引入中级调度的主要目的是，提高内存利用率和系统吞吐量。把那些暂时不能运行的进程，调至外存等待，把外存上的那些已具备运行条件的就绪进程，再重新调入内存。中级调度实际上就是存储器管理中的对换功能。1.处理机调度的层次2.处理机调度算法的目标⑴处理机调度算法的共同目标①资源利用率：为提高系统的资源利用率，应使系统中的处理机和其他所有资源都尽可能地保持忙碌状态，其中最重要的、处理机的利用率可用以下方法计算：②公平性：指应使诸进程都获得合理的CPU时间，不会发生进程饥饿现象。③平衡性：使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。④策略强制执行：对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。2.处理机调度算法的目标⑵批处理系统的目标①平均周转时间短：使作业周转时间和作业的平均周转时间尽可能短。否则，会使许多用户的等待时间过长，这将会引起他们，特别是短作业用户的不满。可把平均周转时间描述为：作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间。而平均带权周转时间则可表示为：周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔作业在外存后备队列上的等待时间进程在就绪队列上等待进程调度的时间进程在CPU上执行的时间进程等待I/O操作完成的时间2.处理机调度算法的目标②系统吞吐量高：吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度有关。事实上，如果单纯是为了获得高的系统吞吐量，就应尽量多的选择短作业运行。③处理机利用率好：对于大、中型计算机，CPU价格十分昂贵，调度方式和算法又对处理机的利用率，起着十分重要的作用。如果单纯是为使处理机利用率高。应尽量多的选择计算量大的作业运行。由上所述可以看出，这些要求之间是存在着一定矛盾的。⑶分时系统的目标①响应时间快：②均衡性：所谓均衡性是指，系统响应时间的快慢应与用户所请求服务的复杂性相适应。返回2.处理机调度算法的目标响应时间：从用户通过键盘提交一个请求开始，到屏幕上显示出处理结果为止的这段时间间隔请求信息从键盘输入传送到处理机处理机对请求信息进行处理将所形成的响应信息送回到终端显示器返回2.处理机调度算法的目标⑷实时系统的目标①截止时间的保证：对于HRT任务，其调度方式和调度算法必须确保对截止时间的要求，否则将可能造成难以预料的后果；而对于SRT任务，其调度方式和调度算法也应基本上能保证对截止时间的要求。②可预测性：在实时系统中，可预测性显得非常重要。截止时间：某任务必须开始执行的最迟时间，或必须完成的最迟时间HRT：必须确保截止时间SRT：基本保证截止时间第三章处理机调度与死锁3.2作业与作业调度3.2.1批处理系统中的作业及调度1.作业和作业步⑴作业：作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位，从外存调入内存的。从系统角度看（作业的组织形式）作业：作业由程序、数据和作业说明书组成。程序和数据完成用户所要求的业务处理工作，作业说明书则体现用户的控制意图。从用户角度看在一次算题过程中或者一个事务处理过程中从输入程序和数据到输出结果，要求计算机系统所做工作的总和。3.2.1批处理系统中的作业及调度⑵作业步：在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。我们把其中的每一个加工步骤称一个作业步，各作业步之间存在着相互联系，往往是上一个作业步的输出作为下一个作业步的输入。例子：到ATM机取款（作业）验证卡的有效性查询余额输入提取金额退卡作业步：在作业的处理过程中，计算机所做的相对独立的步骤。一个作业就是由这些顺序相连的作业步组成的。3.2.1批处理系统中的作业及调度2.作业控制块JCB在多道批处理系统中，为每个作业设置了一个作业控制块JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。在作业运行期间，系统就按照JCB中的信息，和作业说明书对作业进行控制。当作业进入系统时，OS为其建立JCB：作业标识、用户名称、用户账号作业类型(CPU繁忙型、I/O繁忙型、批量型、终端型)作业状态、调度信息(优先级、作业运行时间)资源需求(预计运行时间、要求内存大小等)、资源使用情况3.作业运行的三个阶段和三种状态作业从进入系统到运行结束，通常需要经历收容、运行和完成三个阶段。相应的作业也就有“后备状态”、“运行状态”和“完成状态”。⑴收容阶段：操作员把用户提交的作业，通过某种输入方式或SPOOLing系统，输入到硬盘上，再为该作业建立JCB，并把它放入作业后备队列中，相应的，此时作业的状态为“后备状态”。⑵运行阶段：当作业被作业调度选中后，便为它分配必要的资源和建立进程，并将它放入就绪队列。一个作业从第一次进入就绪状态开始，直到它运行结束前，在此期间都处于“运行状态”。⑶完成阶段：当作业运行完成、或发生异常情况而提前结束时，作业便进入完成阶段，相应的作业状态为“完成状态”。此时系统中的“终止作业”程序，将会回收已分配给该作业的作业控制块和所有资源，并将作业运行结果信息形成输出文件后输出。3.2.1批处理系统中的作业及调度作业状态及其转换图spooling系统提交收容外存就绪等待运行就绪等待交换调度完成作业调度进程调度3.2.1批处理系统中的作业及调度⑷作业调度的主要任务也称为接纳调度，根据JCB中的信息，检查系统中的资源，能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中，选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程，排在就绪队列上等待调度。因此，也把作业调度（AdmissionScheduling）。★在每次执行作业调度时，都须做出以下两个决定①接纳多少个作业取决于多道程序度，即允许多少个作业同时在内存中运行。②接纳哪些作业取决于所采用的调度算法。3.2.1批处理系统中的作业及调度3.2.2先来先服务和短作业优先调度算法1.先来先服务FCFS（first-comefirst-served）调度算法该算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机。优点:实现简单。缺点:没考虑进程的优先级。作业名ABCD到达时间051015要求服务时间1025510先来先服务FCFS到达时间0开始时间0完成时间周转时间带权周转时间105/4=26.2511.7/4=2.92551035301.2103540306154050353.510101例：FCFS算法比较有利于长作业(进程)，而不利于短作业(进程)。下表列出了A、B、C、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，并计算出各自的周转时间和带权周转时间。3.2.2先来先服务和短作业优先调度算法2.短作业优先SJF（shortjobfirst）的调度算法该算法从就绪队列中选出“下一个CPU执行期”最短的进程，为之分配处理机。SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高作业的长短是以作业所要求的运行时间来衡量的。从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。缺点：①必须预知作业的运行时间；②对长作业非常不利；③在采用FCFS算法时，人—机无法实现交互；④该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理。作业名ABCD平均到达时间051015要求服务时间1025510先来先服务（FCFS）周转时间1030303526.25带权周转时间11.263.52.925短作业优先（SJF）周转时间104551017.5带权周转时间11.8111.2FCFS和SJF调度算法的性能比较3.2.3优先级调度算法和高响应比优先调度算法1.优先级调度算法(priority-schedulingalgorithm)基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法是根据该优先级进行调度的。这样就可以保证紧迫性作业优先运行。FCFS：等待时间越久，优先级越高SJF：作业所需运行时间越短，优先级越高返回作业名ABCD到达时间051015要求服务时间1025510优先级0132开始时间完成时间周转时间带权周转时间025101510501525104551011.8113.2.3优先级调度算法和高响应比优先调度算法2.高响应比优先调度算法高响应比优先调度算法则是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。★高响应比优先算法的实现优先级的变化规律可描述为：由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先级又相当于响应比RP。据此，又可表示为：返回第三章处理机调度与死锁3.3进程调度3.3.1进程调度的任务、机制和方式1.进程调度任务①保存处理机的现场信息：在进行调度时首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等。②按某种算法选取进程：调度程序按某种算法，从就绪队列中选取一个进程，将其状态改为运行状态，并准备把处理机分配给它。③把处理器分配给进程：由分派程序把处理器分配给该进程。此时需要将选中进程的进程控制块内有关处理机现场的信息，装入处理器相应的各个寄存器中，把处理器的控制权交予该进程，让它从上次的断点处恢复运行。3.3.1进程调度的任务、机制和方式2.进程调度机制⑴排队器：事先将系统中的所有就绪进程，按照一定的策略，排成一个或多个队列。以便调度程序能最快地找到它。以后每当有一个进程转变为就绪状态时，排队器便将它插入到相应的就绪队列。⑵分派器：依据进程调度程序所选定的进程，将其从就绪队列中取出，然后进行进程间的上下文切换，将处理机分配给新选出的进程。⑶上下文切换器：在对处理机进行切换时，会发生：①第一对上下文切换时，OS将保存当前进程的上下文，装入分派程序的上下文，以便分派程序运行；②第二对上下文切换是移出分派程序的上下文，装入新选进程上下文。3.3.1进程调度的任务、机制和方式3.进程调度方式⑴非抢占方式一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时钟中断，或任何其它原因，去抢占该正在运行进程的处理机，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程。采用这种方式时，可能引起进程调度的因素可归结为：①正在执行的进程运行完毕，或因发生某事件而使其无法再继续运行；②正在执行中的进程，因提出I/O请求而暂停执行；③在进程通信或同步过程中，执行了某种原语操作，如Block原语。优点：是实现简单、系统开销小，适用于大多数的批处理系统。缺点：但它不能用于分时系统和大多数实时系统。3.进程调度方式⑵抢占方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机，重新分配给