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

第三章处理机调度与死锁§3.1调度类型§3.2进程调度的算法及评价§3.3作业的调度§3.4调度算法§3.5死锁的基本概念§3.6产生死锁的必要条件和死锁预防§3.7死锁的避免（银行家算法）一、处理机的3级调度§3.1调度类型在大型通用系统中，可能有数百个批处理作业存放在磁盘的作业队列中，有数百个终端同主机相联接。因此如何从这些作业中挑选作业进入主存运行、如何在作业或进程间分配处理等，问题无疑是操作系统的资源管理功能中的一个重要问题。本章主要讨论处理机分配问题，或称处理机调度。§3.1调度类型一般来说，处理机调度可以分成三级：(1)高级调度：又称作业调度，其主要功能是按照某种原则从磁盘某些盘区的作业队列中选取作业进入主存，并为作业做好运行前的准备工作和作业完成后的善后工作。1)接纳多少个作业2)接纳哪些作业§3.1调度类型(2)中级调度：它决定哪些进程被允许参与竞争处理机资源。中级调度主要只是起到短期调整系统负荷的作用，以平顺系统的操作。其所使用的方法是通过“挂起”和“解除挂起”一些进程，来达到平顺系统操作的目的。(3)低级调度：又称进程调度，其主要功能是按照某种原则将处理机分配给就绪进程。执行低级调度功能的程序称为进程调度程序，由它实现处理机在进程间的转换。它必须常驻主存，是操作系统内核的主要部分。§3.1调度类型RUNreadyablockedareadysblokeds后备完成作业后备状态执行内存时间片到I/O请求I/O完成高级调度(作业调度)挂起解挂挂起解挂进程调度低级调度中级调度二、作业的状态与处理流程§3.1调度类型数据提交状态退出状态后备状态运行状态作业控制进程输入设备数据…源程序输出设备作业说明书输入井运行等待就绪输出井输入程序输出程序作业调度进程调度宏观上：作业调度微观上：进程调度作业和进程的状态转换图§3.1调度类型作业从提交给系统直到它完成后离开系统前的整个活动常划分为若干阶段。作业在每一阶段中所处的状况称为作业的状态。系统中的作业通常分为四种状态。§3.1调度类型1.提交状态当用户提交作业给系统管理员，将作业存入外存时，是一暂时性的状态。系统尚感知不到作业。2.后备状态收容状态。系统收到一作业的全部信息后，为其建立作业控制块JCB，将JCB排在后备队列中。此时，作业已具备进入运行状态的条件，等待作业调度。3.运行状态后备队列中作业被作业调度程序按一定算法选中，程序和数据被调入内存，OS为其建立PCB，一新进程建立。此时，系统管理由作业调度进入进程调度。4.完成状态作业运行结束，处于完成状态，是暂时性状态。系统为该作业做收尾工作。§3.1调度类型1.仅有进程调度的调度队列模型图3-1仅具有进程调度的调度队列模型就绪队列阻塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完§3.1调度类型2.具有高级和低级调度的调度队列模型图3-2具有高、低两级调度的调度队列模型就绪队列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现……等待事件n事件n出现后备队列……§3.2进程调度的算法及评价作业调度程序在挑选作业进入主存运行时，要为该作业建立相应的进程。在作业完成后要撤消该作业的全部进程。因此作业调度程序要调用操作系统内核所提供的有关的进程管理原语。由于进程只能由其父进程建立，所以在一般系统中，作业调度程序都以进程的形式在系统中存在和活动，称为作业调度进程。作业调度进程可以说是系统中的祖先进程，由它完成作业调度的诸多功能。§3.2进程调度的算法及评价一个进程被建立后，系统为了便于对进程的管理，将系统中的所有进程按其状态，将其组织成不同的进程队列。于是系统中有运行进程队列、就绪进程队列和各种事件的进程等待队列。进程调度的功能是从就绪队列中挑选一个进程到处理机上运行。负责进程调度功能的内核程序称为进程序调度程序。§3.2进程调度的算法及评价所谓作业调度程序挑选作业进主存运行是个宏观的概念，实际上被选进主存运行的作业只是具有了竞争处理机的机会(将来真正在处理机上运行的是该作业的一个进程)。而进程调度程序才是真正让某个就绪进程到处理机上运行。一、先来先服务调度算法§3.2进程调度的算法及评价基本思想：从就绪队列中选择一个最先进入该队列的进程，将CPU分配给该进程，进入执行状态，一直运行到完成或发生某事件而让出CPU。§3.2进程调度的算法及评价对“先来先服务”调度算法的评价：最简单的一种调度算法。有利于长进程，不利于短进程有利于CPU繁忙的作业（科学计算），不利于I/O繁忙的作业（事务处理）。若不因I/O中断，则可一直运行到结束。§3.2进程调度的算法及评价用进程周转时间来评价性能。进程周转时间：从进程进入就绪队列开始，到进程完成为止的时间间隔。平均周转时间：系统中多个进程的周转时间的平均值。用户期望自己的周转时间最短。系统管理员希望平均周转时间最短，则系统整体性能较好。§3.2进程调度的算法及评价例：3个进程A、B、C先后（几乎又是同时）进入就绪队列，其分别需运行24ms、3ms、3ms。左图显示了按“先来先服务”算法，各进程运行的先后及周转时间。可见：B等了24ms，而C等了27ms才得运行。平均周转时间：(24+27+30)/3=27ms若进程按B、C、A顺序来到就绪队列，参见右图。可见：平均周转时间：(3+6+30)/3=13ms。2427303036二、时间片轮转调度算法§3.2进程调度的算法及评价基本思想：使就绪队列中所有进程，在一给定的时间内，均能获得一个时间片的CPU执行时间。在使用完一个时间片后，即使进程还没有运行完毕，也要强迫它释放CPU，让给另一进程使用。而该进程回到就绪队列末尾，排队等待下一次调度的到来。§3.2进程调度的算法及评价时间片大小的确定，对机器性能有很大影响。系统响应时间：T=NqN—用户进程数，q—时间片首先要满足系统对响应时间的要求，不能太长，不然用户就会有等待的感觉（一般响应时间应在3秒以下）。N=T/q进程数一定，时间片长短与系统响应时间成正比。系统处理能力，应保证在1个时间片内，将用户键入的常用命令能处理完毕，否则无法得到满意的响应时间。该算法多用于分时操作系统。三、优先级调度算法§3.2进程调度的算法及评价基本思想：为系统中每一个进程规定一个优先级，就绪队列中具有高优先级的进程有优先获得CPU的权利；如果几个进程的优先级相同，则按先来先服务算法调度。§3.2进程调度的算法及评价确定优先级的一些因素：(1).按进程的类型。系统进程还是用户进程。(2).按程序的性质。CPU繁忙的进程影响系统整体效能，优先级较低，而I/O繁忙的进程则优先级较高。(3).按用户的请求。进程优先级可分动态和静态两类。静态优先级：在创建进程时确定，并在整个运行期间保持不变。动态优先级：在创建时赋予的优先.数权，随进程的推进而改变，以获得更好的调度性能。四、多级队列调度算法§3.2进程调度的算法及评价又称多级反馈队列调度算法。该算法是时间片算法与优先级算法的结合。系统安排情况：有多个就绪队列，每个就绪队列具有不同的优先权，可获得不同长度的时间片。参见图例：S1队列优先权最高，所获时间片最短。Sn队列优先权最低，所获时间片最长。§3.2进程调度的算法及评价§3.3作业的调度系统中往往有成百个作业被收容在磁盘输入井中，为了管理和调度作业，就必须记录已进入系统的各作业的情况。因此同进程中的情况类似，系统也为每个作业设置一个作业控制块(记为JCB)，它记录了作业的有关信息。不同系统的JCB所包含的信息有所不同，这取决系统对作业调度的要求。§3.3作业的调度JCB是在作业进入系统时由SPOOL系统为其建立的。其内容由作业控制卡中得到。同样JCB也是作业存在于系统的标志，作业进入系统时，则为之建立JCB。当作业退出系统时，则其JCB也被撤消。在磁盘输入井中的所有后备作业按作业类型将它们组成一个或多个后备作业队列。所谓后备作业队列是由作业控制块JCB用表格或链指针组成的队列。作业队列可按优先数大小和作业到达系统的时间顺序排列。一、作业控制块§3.3作业的调度根据系统内所有资源的使用情况，按照某种调度算法选择一个后备作业进入系统，并为其创造一个进程。为此，作业调度还要为选中的作业分配资源，作好作业支行前的准备。完成作业调度功能的程序称为作业调度程序。§3.3作业的调度作业调度程序要完成以下工作：(1)按照某种调度算法从后备作业队列中挑选作业。(2)为选中的作业分配主存和外设资源。(3)为选中的作业建立相应的进程。(4)构造和填写作业运行时所需的有关表格。(如作业表)(5)作业结束时完成该作业的善后处理工作，如收回资源，输出必要的信息，撤消该作业的全部进程(PCB)和作业控制块JCB。§3.3作业的调度每个作业进入系统时由系统为其建立一个作业控制块JCB（JobControlBlock)，它是存放作业控制和管理信息的数据结构，主要信息见右图。二、选择调度算法时应考虑问题§3.3作业的调度目前比较普遍使用的几种调度算法，对于作业调度和进程调度大致上都是适用的。在设计系统的调度程序时，首先要决定选择何种调度算法，依据此算法来编制相应的调度程序。而调度算法实际上就是系统所采取的调度策略，选择时所要考虑的因素很多。如系统各类资源的均衡使用；对用户公平并使用户满意；用户作业到达系统的时间；作业的优先数；对主存和外设的要求；以及整个系统的效率等。§3.3作业的调度设计时应将那些对系统运行影响较大的关键因素作为调度算法考虑的主要依据。(1)设计目标：目标不同，系统的设计要求自然不同。如批处理系统所追求的是充分发挥和提高计算机的效率；实时系统所关心的是不要丢失实时信息并及时给以处理；而分时系统则侧重于保证用户的请示及时给予响应；计算中心要求系统吞吐量在大等等。§3.3作业的调度(2)资源利用率：在考虑设计目标的前提下应充分发挥各种资源的效能，最大限度地使它们忙碌。科学计算型作业和数据处理型作业搭配运行就是一种方法。(3)均衡地处理系统和用户的要求：例如个别用户可能要求使用系统中的几乎全部外设，却只要求很少的主存。系统若满足这类用户的愿望，势必影响主存利用率，从而降低系统效率，所以一般都不得不推迟这种作业的运行时间，等到有要求内存多而外设少的作业与之搭配运行。但是我们选择的算法也不应使一个作业的运行被无限制地推迟。§3.3作业的调度(4)在使用优先级的系统中，每个进程都有一个优先数，调度算法应优先运行高优先级进程。(5)在使用优先数的系统中，调度策略还分为“可抢占”和“不可抢占”两种方式。抢占策略通常使用于需要迅速响应高优先级进程的系统中。§3.3作业的调度作业调度程序按一定的算法，负责挑选后备队列中的一些作业进入运行状态。确定作业调度算法时，考虑到以下一些因素：①公平对待后备队列中每一个作业，顾及各种类型作业的情况。②均衡使用系统资源，克服资源忙闲不均情况出现。③提高整个系统的吞吐能力。§3.3作业的调度在批处理系统中，系统吞吐能力是衡量算法的主要着眼点，通常用作业的“周转时间”来定量判断。周转时间：Ti=Wi-SiSi：作业i提交给系统的时间Wi：作业完成时间作业提交作业完成之间的时间平均周转时间：T=（T1+T2+...+Tn）/nn个作业的平均周转时间§3.4调度算法目标:•每天运行尽可能多的作业——选择短作业(吞吐量)•使处理机保持“忙”——选择大运输量(I/O少)•使I/O保持“忙”——选大I/O效率:•公平性——FCFS对所有进程公平一、先来先服务调度算法§3.4调度算法基本思想：以作业进入后备队列的先后为依据。→从后备队列选一个或多个最先进入队列的作业→将作业调入内存、分配资源、创建进程→放入进程就绪队列§3.4调度算法例：三个作业按表中顺序同时提交系统，采用先来先服务作业调度算法。求出每个作业的周转时间和它们的平均周转时间。分析：三作业同时提交系统，可看作到达时间都为0，Si=0解: