第10讲-处理器管理优秀PPT.ppt

第第1页页/89教学内容教学内容 （一）基本概念 特权指令 管态 目态 P129 进程、程序的关系和区分 进程的类型、性质和状态 进程调度的策略和常用算法 静、动态优先数法、轮转法、分级调度法 进程的限制与管理 进程限制块PCB （二）进程的同步与互斥 （三）死锁 (四)作业管理与限制第第2页页/89教学内容及本单元涉及的章节教学内容及本单元涉及的章节l3.3处理器管理处理器管理l3.6操作系统的用户接口操作系统的用户接口第第3页页/89一、基本概念一、基本概念l程序l单道程序、多道程序、依次程序、并发程序l依次程序与并发程序的特征l进程l进程的特征、性质、状态及转换l进程限制l进程调度第第4页页/891、程序的有关概念、程序的有关概念程序（Program）是为解决某个问题用计算机语言或吩咐设计、编写的一系列指令的有序集合。程序的依次执行 一个程序通常分为若干个具有确定独立性的程序段，这些程序段是按逻辑步骤编排的，只有当当前程序段执行完成后，才将限制权转交到下一个程序段并执行下一个程序段。第第5页页/89程序依次执行举例一程序依次执行举例一设有一个程序有三个程序段，分别执行 I（输入）、C（计算）和P（输出）操作。执行依次为：I C P 只有输入了数据 ，才能计算这些数据，也只有计算产生了结果，才能输出它们。这些逻辑关系（依次）是不能随意变更的。结果结果 数据数据第第6页页/89程序依次执行举例二程序依次执行举例二假设有n个作业，每个作业都由三个程序段：输入段Ii、计算段Ci、输出段Pi。在早期单道程序系统中，作业执行流为：作业1 I1 C1 P1 作业2 I2 C2 P2 作业n In Cn Pn作作业业执执行行顺顺序序第第7页页/89单道程序处理及特性单道程序处理及特性l一次只处理一个程序。该程序独享系统资源。l单个程序的特性：l1、依次性 操作按程序规定的依次执行。l2、封闭性 程序在执行过程中独享系统资源，不受外界因素的干扰和影响。l3、可再现性 只要初始条件相同，无论以何种方式、速度、重复执行多少次，结果是相同的。第第8页页/89多道程序处理及特性多道程序处理及特性l同时将多个程序装入内存，并同时处理它们，整个系统资源为多个程序共享。l由于多道程序具有并发并发的特点，在任一时刻，系统内部（内存）同时运行着多个程序；受系统资源的制约，每个程序处理过程的行为是不确定的（系统内部状态因此而不同）。输输入入计计算算计计算算计计算算打打印印计计算算打打印印A(优先级高）优先级高）CA1A2B1B2B3C1C2多多 道道 程程 序序 并并 行行 运运 行行 示示 意意 图图A1输输入入B1C1打打印印OSB2OSB3打打印印A2CPUOSCPUC2CPUCPUCPUCPUCPUB 程序并发执行举例程序并发执行举例第第10页页/89单道和多道程序处理的区分单道和多道程序处理的区分l在单道程序处理环境下，各逻辑步骤之间的关系是确定的、不受外界影响而变更的。l在多道程序处理环境下，并发处理机制中必定存在着干脆或间接的相互依靠和相互制约的关系，从而使被处理的多道程序失去了程序固有的特性：封闭性、可再现性。第第11页页/89程序并发处理特征程序并发处理特征1、失去了程序的封闭性，请分析下列程序 begin 用 cobegin和 coend表示程 N:integer 序能并发执行。N：=0 cobegin begin begin L1：program A L2：program B N:=N+1 print N goto L1 N:=0 end goto L2 coend end end 并发程序段并发程序段A并发程序段并发程序段B加1打印清零第第12页页/89程序并发处理特征程序并发处理特征失去了程序的封闭性失去了程序的封闭性分析：若先执行程序A，N值大于0；再执行程序B时，先输出一个大于0的N值，然后，N值变为0。若先执行程序B，N值等于0，先输出一个 0的N值；再执行程序A时，N值变为1。由于程序A和程序B都是以各自独立的速度运行，则因速度不同而结果不同。所以并发执行程序失去了依次程序的封闭性。第第13页页/89程序并发处理特征程序并发处理特征程序与计算结果不再一一对应程序与计算结果不再一一对应l程序在依次执行时，程序与“计算”间有着一一对应的关系。l在并发执行时，一个共享程序可为多个用户作业调度，而使程序处于多个执行中，从而形成了多个“计算”。因此，程序和计算间一一对应的关系不复存在。l如何表示并发程序的特性？第第14页页/892 2、进程及有关概念、进程及有关概念进程（Process）就是程序的一次执行过程，是系统进行资源安排和调度的一个独立单位。“进程”这个概念是1966年美国麻省理工学院的J.H.Sallexer提出的。处理器（CPU）管理又称处理器调度。处理器是计算机系统中的重要资源，所以它管理的好坏在很大程度上干脆影响系统的效率。处理器管理又分两级：作业调度和进程调度。进程管理是由程序管理进化而来，是和程序管理密不行分的。作业调度作业调度见本见本PPT87第第15页页/89进程的性质进程的性质1）动态性）动态性 进程有自己的生命周期。2）并发性）并发性 在系统中可以同时存在多个进程；OS同时接受和处理多个进程。3）异步性）异步性 不同进程在逻辑上相互独立，有各自的运行“轨迹”。4）制约性）制约性 由于计算机资源是有限的，不同进程 共享CPU和I/O通道及设备，因此相 互制约。第第16页页/89进程与程序的区分进程与程序的区分进程是动态概念，程序是静止概念。进程是动态概念，程序是静止概念。进程的存在是短暂的，程序的存在是永久的。进程的存在是短暂的，程序的存在是永久的。假如程序是剧本，那么表演过程就是进程；假如程序是假如程序是剧本，那么表演过程就是进程；假如程序是菜谱，那么烹调过程就是进程菜谱，那么烹调过程就是进程；电影胶片呢；电影胶片呢通过多次执行，一个程序可对应多个进程；通过调用关通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序系，一个进程可包括多个程序(父进程和子进程）父进程和子进程）进程在结构上是由程序、数据集、进程限制块（进程在结构上是由程序、数据集、进程限制块（PCB）三部分组成的。三部分组成的。PCB程程序序数数据据第第17页页/89进程的状态进程的状态l进程在其存在的过程中，它们的状态是不断发生变更的。一般来说，进程有三种基本状态：就绪状态、运行状态、等待状态。l就绪状态 已经获得投入运行所必需的一切资源，一旦安排到CPU，就可以马上执行。这是一种逻辑上可运行状态（“万事俱备，只欠东风”）。l运行状态 进程获得了CPU及其它一切所需资源，正在CPU上运行着,也是唯一在运行的。l堵塞状态 由于资源得不到满足，进程运行受阻，处于暂停状态，等待资源安排后，再投入运行。第第18页页/89进程状态转换示意图进程状态转换示意图运行状态运行状态堵塞状态堵塞状态 就绪状态就绪状态 进程调度进程调度 等待资源等待资源时间用完时间用完获得资源获得资源 进程调度进程调度程序程序 来自作业来自作业调度调度 交作业交作业管理管理进程在整个生存周期中，由进程调度程序限制，在这进程在整个生存周期中，由进程调度程序限制，在这三种状态之间进行转换。三种状态之间进行转换。第第19页页/893、进程管理、进程管理l进程管理的核心是进程的限制和调度。进程自投入运行时起，即交由进程调度程序管理。l依据什么标准选择怎样的进程投入运行？如何管理不同类型进程的资源？l 接受什么策略进行安排资源？l 。l这些都是进程管理的问题。第第20页页/89进程限制进程限制l进程限制的职责是对系统中全部进程实进程限制的职责是对系统中全部进程实行有效的管理；它应当具有创建进程、行有效的管理；它应当具有创建进程、撤消进程、变更进程状态的实力。撤消进程、变更进程状态的实力。l为便于对进程进行管理，进程具有特殊为便于对进程进行管理，进程具有特殊的构成形式。的构成形式。PCB程程序序数数据据进程进程名名优先优先数数当前状态当前状态寄存器内容寄存器内容指向下一个指向下一个PCBPCB说明信息说明信息保留信息保留信息第第21页页/89进程的组成进程的组成l进程是程序在一个数据集合上的运行过程，它由三部分组成：l 程序 l 它主要用于描述进程所要完成的功能。l 数据集合 l 它包括程序执行时所须要的数据和工作区。l 进程限制块（PCBProcess Control Block)l 它记录进程限制信息，是进程动态特性的反映。第第22页页/89进程限制块进程限制块PCBl进程限制块PCB是进程的唯一标识。当创建一个新进程时，系统就建立一个PCB；它记录和描述该进程的运行变更过程及参数变更。事实上，系统是通过PCB对进程进行实际限制和管理的。通过感知PCB，感知进程的存在。l PCB中包括：l 进程名 进程唯一的代号l 进程优先级 标明该进程要求CPU的迫切程度l 进程当前状态 记录进程当前状态l 寄存器内容 记录中断现场信息，以备复原用第第23页页/89进程限制块进程限制块PCB的组织形式的组织形式为了便于对进程调度管理，必需对进程进行合理为了便于对进程调度管理，必需对进程进行合理的组织。进程限制块的组织。进程限制块PCB是定长记录（类似于是定长记录（类似于UNIX中的中的i索引结点表），接受两种组织方式。索引结点表），接受两种组织方式。线性表结构线性表结构PCB组织形式组织形式链表结构链表结构第第24页页/89PCB链表结构链表结构 运行队列运行队列 就绪队列就绪队列 堵塞队列PCBr队头队头指针指针PCBsPCBs+1PCBs+2PCBtPCBt+1PCBt+2唯一在运行的第第25页页/89进程限制的实现进程限制的实现通过进程限制原语原语由若干条机器指令构成的，用以完成某一特定功能的一段程序。原语在执行期间是不行分割的。（1）创建原语：按进程调用者供应的参数，形成 PCB。（2）挂起（堵塞）原语：将某进程置于堵塞状态。（3）激活（唤醒）原语：将某进程置为就绪状态，等待 CPU。（4）撤消原语：撤消进程，释放所占用的全部资源，删除该程序的PCB。第第26页页/894.进程调度的任务及功能进程调度的任务及功能l进程调度任务 l按确定的算法，动态地将处理器（CPU）安排给就绪队列中的某个进程，使之执行。l进程调度功能l记录系统中全部进程的状态、优先数和所用资源的状况。l当CPU空闲时，按确定的算法将CPU安排给某一进程、并确定CPU时间片的长度。l动态地调度进程、修改进程的状态、以及修改相应的排队队列。第第27页页/89进程调度方式进程调度方式剥夺方式 当“重要”或“系统”的进程出现时，便暂停正在执行的进程，马上将CPU安排给“重要”或“系统”的进程。非剥夺方式 让正在执行的进程接着执行，直到该进程完成或发生其它事务，而变更为其它状态后，才移交CPU限制权。第第28页页/89进程调度算法进程调度算法l考虑进程调度算法的因素有：l 1、尽量提高资源利用率，削减CPU空闲时间；l 2、对一般作业接受较合理的平均响应时间；l 3、应避开有的作业长期得不到响应的状况。l进程调度算法：l优先数法l轮转调度法l分级调度法第第29页页/89常用的算法是把CPU安排给具有最高优先数的进程。静态优先数法进程优先数是在系统创建进程时确定的，一经确定，在进程运行期间就不再变更。动态优先数法进程优先数在进程运行中，随进程特性的变更不断修改进程的优先数，实现更精确的调度。优先数法优先数法第第30页页/89轮转调度法（动态法）轮转调度法（动态法）l先将就绪态进程按FIFO规则排成一个队列，将CPU划分为等长的时间片，安排给队列中的每个进程。l进程在运行了一个时间片q后，排至队尾，如此循环。l时间片q 的取值为：l q 过小，系统开销增加；l q 过大，又退化为FIFO法。l 一般来说，q 值取为：q=100ms 为宜。第第31页页/89分级调度法（动态法）分级调度法（动态法）结合优先数法和轮转调度法分为具有较高优先数的前台队列和较低优先数的后台队列进程调度以固定的时间片把处理器安排给前台队列中的进程，仅当前台队列中的进程已全部完成或等待I/O操作时，才把处理器安排给后台进程。第第32页页/89临界资源：一次仅允许一个进程运用的资源临界资源：一次仅允许一个进程运用的资源。如打。如打印机、读卡机、缓冲区、变量等。印机、读卡机、缓冲区、变量等。临界区：进程中运用临界资源的那段程序。临界区：进程中运用临界资源的那段程序。各进程之间存在着相互制约、相互依靠的关系：各进程之间存在着相互制约、相互依靠的关系：同同 步步:两个事务的发生存在某种时序关系，假如系两个事务的发生存在某种时序关系，假如系统中若干个进程要完成同一个任务，则进程之间要统中若干个进程要完成同一个任务，则进程之间要协调其推动的速度，以便正确完成作业运行，此即协调其推动的速度，以便正确完成作业运行，此即同步。请看两个例子同步。请看两个例子 互互 斥：对于某一临界资源，一组进程不能同时进入斥：对于某一临界资源，一组进程不能同时进入临界区去运用它。一个进入，其他必需等待。请看临界区去运用它。一个进入，其他必需等待。请看两个例子两个例子进程同步和互斥的实现方法进程同步和互斥的实现方法二、进程的同步与互斥二、进程的同步与互斥例例1：进程同步的例子进程同步的例子电子邮件信箱电子邮件信箱发送进程发送进程A接收进程接收进程B当信箱满时，发送进程只有等待接收进程取走信件，当信箱满时，发送进程只有等待接收进程取走信件，当信箱空时，接收进程必需等待发送进程发送信件。当信箱空时，接收进程必需等待发送进程发送信件。1 2n34例例2:X=fun1(y)*fun2(Z)计算计算fun1(y)进程进程P2算完算完fun2(Z)?取用取用P2计算结果计算结果计算计算fun2(Z)设置计算完成标记设置计算完成标记终终止止YN进程进程P1进程进程P2两个协同工作进程的同步两个协同工作进程的同步35例例1:公共地段交通十字路口的限制：公共地段互斥交通十字路口的限制：公共地段互斥36例例2:X=COUNTX=X+1COUNT=XY=COUNTY=Y+1COUNT=Y临界区临界区临界区临界区进进程程A进进程程B进程进程A与与B对公共变量对公共变量COUNT进行互斥操作，最终实现进行互斥操作，最终实现COUNT增增加加2。若。若A与与B按下面依次推动，结果按下面依次推动，结果COUNT只实现增加只实现增加1。A:X=COUNT；A:X=X+1;COUNT=X；B:Y=COUNT；B:Y=Y+1;COUNT=Y；用用P-V原语对进程中信号量进行操作的方法（简称原语对进程中信号量进行操作的方法（简称P-V操作）。操作）。原语：由若干条机器指令构成，完成某一特定功能的一段程序。原语：由若干条机器指令构成，完成某一特定功能的一段程序。P原语操作过程：原语操作过程：P操作记为操作记为P（S），其中），其中S为一信号量，其执行依次完成以下为一信号量，其执行依次完成以下两个动作：两个动作：（1）S：=S 1，表示申请运用一个资源；，表示申请运用一个资源；（2）若若S 0，表示系统中有资源可用，现进程可接着执行。，表示系统中有资源可用，现进程可接着执行。（3）若若S 0，表示系统中没有可用资源，则置该进程堵塞状，表示系统中没有可用资源，则置该进程堵塞状态，到态，到S信号量信号量的队列中去等待，直到其他进程在的队列中去等待，直到其他进程在S上上执行执行V操作释放它为止。操作释放它为止。信号量的概念和信号量的概念和P、V原语是荷兰科学家提出的。把交通原语是荷兰科学家提出的。把交通管理的信号灯方法搬到了操作系统中。管理的信号灯方法搬到了操作系统中。所谓信号量是一个与队列有关的整型变量，表示系统中某类所谓信号量是一个与队列有关的整型变量，表示系统中某类资源的数量。当其值大于资源的数量。当其值大于0时，表示系统中尚有可用资源；当时，表示系统中尚有可用资源；当其值为负时，其确定值表示还欠缺的资源数。信号量的值仅其值为负时，其确定值表示还欠缺的资源数。信号量的值仅能由能由P操作和操作和V操作来变更，操作系统利用它的状态对进程和操作来变更，操作系统利用它的状态对进程和资源进行管理。资源进行管理。进程的同步与互斥的实现方法进程的同步与互斥的实现方法V原语操作过程：原语操作过程：V操作记为操作记为V（S），其中），其中S为一信号量，其执行依次完成以为一信号量，其执行依次完成以下两个动作：下两个动作：（1）S：=S+1，表示释放一个资源；，表示释放一个资源；（2）若若S 0，表示系统中没有等待该资源的进程，现进程，表示系统中没有等待该资源的进程，现进程可接着执行（走）。可接着执行（走）。（3）若若S 0，表示系统中有等待该资源的进程，则唤醒，表示系统中有等待该资源的进程，则唤醒S信信号量队列中的第一个进程，使其插入到就绪队列，现号量队列中的第一个进程，使其插入到就绪队列，现进程接着执行。进程接着执行。39第第39页页/89（1）实现进程同步（）实现进程同步（a）非对称制约）非对称制约（2）实现进程同步（）实现进程同步（b）双向制约）双向制约生产者与消费者问题生产者与消费者问题（3）实现进程互斥）实现进程互斥 (1)干脆通信（消息缓冲区）(2)信箱通信 (3)基于共享数据结构或共享存储区通信P-V操作的应用操作的应用进程通信进程通信S=0把把 P-V P-V 操操 作作 用用 于于 进进 程程 同同 步步进程进程AC:P(S)同步点同步点同步条件同步条件进程进程BV(S)假定进程假定进程A前进到前进到C点时，必需等到进程点时，必需等到进程B执行完同步条件才能接着前进。执行完同步条件才能接着前进。为了实现进程为了实现进程A与进程与进程B在在C点同步，设置信号量点同步，设置信号量S初始值为初始值为0。在进程。在进程A的的C点处设置点处设置P操作，在进程操作，在进程B设置设置V操作。假定操作。假定A先于先于B到达到达C点，它要在点，它要在S上执行上执行P操作，使操作，使S=-10表示表示有数据有数据；S2表示缓冲区中的数据是否被取走，表示缓冲区中的数据是否被取走，S20表示已取走，表示已取走，有有空空的缓冲的缓冲区区；初初值值：S1=0，S2=0；查询进程查询进程S把查询结果把查询结果写到缓冲区写到缓冲区V(S1)P(S2)打印进程打印进程PP(S1)把缓冲区内把缓冲区内容打印输出容打印输出V(S2)42生产者进程生产者进程L1:生产物品生产物品P(S1)缓冲区缓冲区物品物品V(S2)消费者进程消费者进程C1:P(S2)从缓冲区取物品从缓冲区取物品V(S1)消费物品消费物品S1=1;S2=0;43为使这段操作能互斥进行，设置为使这段操作能互斥进行，设置S1初值为初值为1，S2初值为初值为0。其中：其中：S1缓冲区中是否有空，缓冲区中是否有空，S10 有空有空缓冲缓冲区区；S2 缓冲区中是否有物品可供消费，缓冲区中是否有物品可供消费，S20有物品有物品。则无论在何处中断，均能进行协调工作。则无论在何处中断，均能进行协调工作。S=1进程进程A的的临界区临界区P(S)进程进程AV(S)进程进程B的的临界区临界区P(S)进程进程BV(S)为使这段操作能互斥进行，设置一个信号量为使这段操作能互斥进行，设置一个信号量S初值为初值为1，在每个地段的入口处，支，在每个地段的入口处，支配对配对S的的P操作，出口处做操作，出口处做V操作。谁先对操作。谁先对S做做P操作，就会使操作，就会使S的值由的值由1变为变为0，且，且自己获准进入临界区。另一进程再对自己获准进入临界区。另一进程再对S进行进行P操作，试图进入自己的临界地段，就操作，试图进入自己的临界地段，就会因为会因为S的值由的值由0变为变为-1而受到阻挡。只有等到在临界地段内的进程退出临界地段而受到阻挡。只有等到在临界地段内的进程退出临界地段时对时对S做做V操作，使操作，使S的值由的值由-1变为变为0，才会解除这一阻挡而放行，从而实现进程，才会解除这一阻挡而放行，从而实现进程的互斥。的互斥。44Y=COUNTY=Y+1COUNT=Y临界区临界区V(S)P(S)进程进程BX=COUNTX=X+1COUNT=X临界区临界区V(S)P(S)进程进程A设置设置S，初值为，初值为145dA发发送送区区senddBReceive接接收收区区1A进程进程B进程进程PCBB进程进程 直直接接通通信信P136.Send(B,dA).B5Hello第一个消息缓冲区第一个消息缓冲区A5HelloNptrH-ptrA5Hello.Receive(A,dB)46mutexssmSendP(sml)申请格子申请格子把信件从信件发送把信件从信件发送区读到信箱格子中区读到信箱格子中V(sm2)ReceiveP(sm2)限制是否有信件限制是否有信件把第一个格子中的信把第一个格子中的信件读到信件接收区件读到信件接收区V(sm1)申请格子由信号量申请格子由信号量sm1限制（有格子）限制（有格子）Sm2限制格子里限制格子里是否有信件是否有信件47信信箱箱通通信信初值初值Sm1=1，Sm2=0、死锁产生的缘由（四个必要条件）、死锁产生的缘由（四个必要条件）（）资源不能共享（资源独占性）。（）资源不能共享（资源独占性）。（）资资源源接接受受动动态态安安排排原原则则：资资源源在在等等待待新新资资源源时时，接着占接着占有已安排到的资源。有已安排到的资源。（C）资资源源的的不不行行剥剥夺夺性性：一一个个进进程程占占有有的的资资源源不不能能被别的进被别的进程强行抢占。程强行抢占。（D）允允许许进进程程间间非非法法交交叉叉推推动动依依次次的的存存在在：导导致致循循环等待资环等待资 源，无法前进。源，无法前进。48三、死三、死锁锁死锁：每个进程所要求的资源都已被另一个进程占用，死锁：每个进程所要求的资源都已被另一个进程占用，出现没有一个进程能接着运行，这种状况称出现没有一个进程能接着运行，这种状况称“死锁死锁”。打印机打印机进程进程A进程进程B读卡机读卡机进程进程A申请到打印机申请到打印机进程进程A须要读卡机须要读卡机进程进程B申请到读卡机申请到读卡机进程进程B须要打印机须要打印机49例如：进程例如：进程A和和B以下面的推动速度前进，导致死锁。以下面的推动速度前进，导致死锁。A：申请打印机：申请打印机2.B：申请读卡机：申请读卡机3.A：申请读卡机：申请读卡机4.B：申请打印机：申请打印机第第49页页/89*死死锁锁的的检检测测与与复复原原允允许许死死锁锁产产生生，当当死死锁锁发发生生时时能能检检测测出出来来，并并且且有有实实力力处处理，理，进进行复原。行复原。关于资源独占性：接受可以使非共享设备变为共享关于资源独占性：接受可以使非共享设备变为共享设备。设备。解决死锁的方法解决死锁的方法*死锁的预防死锁的预防破坏产生死锁的破坏产生死锁的4个必要条件中的任何一个。个必要条件中的任何一个。破坏破坏“资源的不行剥夺性资源的不行剥夺性”（申请不到资源时，释放（申请不到资源时，释放原先已占有的，进入等待，以后再一起申请）。原先已占有的，进入等待，以后再一起申请）。破坏对资源接受动态的部分安排原则（每个进程必需破坏对资源接受动态的部分安排原则（每个进程必需提出它所须要的全部资源，只有完全满足时，才能启动）。提出它所须要的全部资源，只有完全满足时，才能启动）。破坏循环等待。破坏循环等待。*死死锁锁的避开的避开躲躲避死避死锁锁的的发发生。生。接受虚拟技术，使非共享设备变成共享设备，以避开死锁。接受虚拟技术，使非共享设备变成共享设备，以避开死锁。用户用户1用户用户2用户用户3输出输出输出输出输出输出打印打印打印机打印机主主机机51破坏资源独占性破坏资源独占性假脱机技术（教材假脱机技术（教材P153）系统资源进行统一编号。进程申请运用资源时，系统资源进行统一编号。进程申请运用资源时，必需严格依据编号的升序进行。必需严格依据编号的升序进行。进进程程资资源源ABC1、卡片输入机卡片输入机（3台）台）2、行式打印机行式打印机（2台）台）*3、磁带机、磁带机（1台）台）*52破坏循环等待破坏循环等待打破环路条件：将全部资源编号，申请时按依次打破环路条件：将全部资源编号，申请时按依次申请，先申请小号，再申请大号，这样，能保证申请，先申请小号，再申请大号，这样，能保证申请到最大号者，确定运行完成。申请到最大号者，确定运行完成。第第52页页/89例：三个进程例：三个进程P1,P2,和和P3,所须要磁带机分别为所须要磁带机分别为10，4，9台，系统中共台，系统中共12台。台。T0时刻时刻最大需求最大需求P110P24P39T0时刻存在一个平安序列时刻存在一个平安序列所以系统平安。所以系统平安。假如假如P3恳求恳求1台台,状态发生变更状态发生变更.已安排已安排522可用可用3还需还需527找不到一个平安序列找不到一个平安序列.状态担忧全状态担忧全.恳求不能满足。恳求不能满足。假如假如P1恳求恳求1台台,状态发生变更状态发生变更.结果如何结果如何？假如假如P2恳求恳求1台台,状态发生变更状态发生变更.结果又如何？结果又如何？若把题中的若把题中的12改为改为11，则，则T0时刻系统是担忧全的，因为这时时刻系统是担忧全的，因为这时系统中虽有系统中虽有2台可用设备，但不存在平安序列。当然，若不台可用设备，但不存在平安序列。当然，若不依据平安序列安排资源，平安状态可能变为担忧全状态。依据平安序列安排资源，平安状态可能变为担忧全状态。第第53页页/89死锁的避开 l死死锁锁的的避避开开是是这这样样一一种种应应付付死死锁锁的的方方法法：系系统统在在运运行行过过程程中中实实行行动动态态的的资资源源安安排排策策略略，保保证证系系统统不不进进入入可可能能导导致致系系统统陷陷入入死死锁锁状状态态的的所所谓谓担担忧忧全全状状态态，以以避避开开死锁发生。死锁发生。l常常用用的的避避开开死死锁锁的的算算法法是是“银银行行家家算算法法”，系系统统接接受受此此法法给给进进程程安安排排资资源源时时，需需先先推推断断“假假如如安安排排，系系统统状态是否平安状态是否平安”，这很像银行家放贷前的思索过程。，这很像银行家放贷前的思索过程。第第54页页/89(1)(1)平安状态与平安序列平安状态与平安序列 l1)1)平安状平安状态态l 若若在在某某一一时时刻刻，系系统统能能按按某某种种进进程程依依次次，如如，来来为为每每个个进进程程安安排排其其所所需需的的资资源源，直直至至最最大大需需求求，使使每每个个进进程程均均可可顺顺当当完完成成。则则称称此此时时系系统统的的状状态态为为平平安安状状态态，称称这这样样的的一一个个进进程程序序列列为为平平安安序列。序列。l2)2)担担忧忧全状全状态态l 若在某若在某时时刻，系刻，系统统无法找到一个平安序列，无法找到一个平安序列，则则称系称系统处统处于担于担忧忧全状全状态态。第第55页页/89留意：留意：（1 1）系统在某一时刻的平安序列可能不唯一，但这不）系统在某一时刻的平安序列可能不唯一，但这不影响对系统平安性的推断。影响对系统平安性的推断。（2 2）平安状态是非死锁状态，而担忧全状态并不确定）平安状态是非死锁状态，而担忧全状态并不确定是死锁状态。即系统处于平安状态确定可以避开死锁，是死锁状态。即系统处于平安状态确定可以避开死锁，而系统处于担忧全状态则仅仅有可能进入死锁状态。而系统处于担忧全状态则仅仅有可能进入死锁状态。平安状态平安状态担忧全状态担忧全状态死锁状态死锁状态第第56页页/89l银行家算法银行家算法l银行家拥有一笔周转资金银行家拥有一笔周转资金l客客户户要要求求分分期期贷贷款款，假假如如客客户户能能够够得得到到各各期期贷贷款款，就确定能够归还贷款，否则就确定不能归还贷款就确定能够归还贷款，否则就确定不能归还贷款l银行家应谨慎的贷款，防止出现坏帐银行家应谨慎的贷款，防止出现坏帐l用银行家算法避开死锁用银行家算法避开死锁l操作系统操作系统比作（银行家）比作（银行家）l操作系统管理的资源操作系统管理的资源比作比作(周转资金周转资金)l进程进程比作（要求贷款的客户）比作（要求贷款的客户）为了避开死锁的发生，系统对进程提出的每一个资源恳为了避开死锁的发生，系统对进程提出的每一个资源恳求，先不是真正去安排，而是依据当时资源的运用状况，按求，先不是真正去安排，而是依据当时资源的运用状况，按确定的算法去进行模拟安排后的结果。只有当探测结果不会确定的算法去进行模拟安排后的结果。只有当探测结果不会导致死锁，才真正接收进程提出的这一恳求。类似下棋导致死锁，才真正接收进程提出的这一恳求。类似下棋常用的算法是常用的算法是“银行家算法银行家算法”（1965年提出）。年提出）。银行家算法的思想银行家算法的思想:（假定在单类资源的安排上实行这一算法）。（假定在单类资源的安排上实行这一算法）。死锁的避开死锁的避开每个用户必需预先申请它所需的贷款总数，且此数值不能超过银每个用户必需预先申请它所需的贷款总数，且此数值不能超过银行资金总数；行资金总数；每个用户每次只能向银行申请一个单位贷款数；每个用户每次只能向银行申请一个单位贷款数；银行依据当时的资金状况，可能马上满足用户申请，或者须要用银行依据当时的资金状况，可能马上满足用户申请，或者须要用户等待一段时间；户等待一段时间；当用户贷款总数达到申请数后，必需在有限时间内一次归还全部当用户贷款总数达到申请数后，必需在有限时间内一次归还全部贷款。贷款。第第58页页/89 假如全部进程的“能执行完”均为1，表示接受这次恳求是平安的；否则短暂不能接受进程的这次资源恳求。假如找到了，就假设它获得了最大资源数，并运行结束。于是把它的“能执行完”标记置为1。这样就能假定收回它运用的全部资源，使系统剩余资源数增加。在这一假设下，检查每个进程对资源的还须要数。看能否找到一个进程，其还需数目小于系统剩余资源数。假如找不到，那么系统就有可能死锁，因为任何进程都无法运行结束。在平安状态下，系统接到进程的资源恳求后，先假定接受这一恳求，把须要的资源安排给这个进程。单种资源银行家算法的基本思想单种资源银行家算法的基本思想单种资源银行家算法：单种资源银行家算法：将全部进程的“能执行完”标记清0假定接受该恳求,把资源安排给进程将系统当前全部剩余资源与”能执行完”标记为0的进程还需资源数比较,找出一个能满足其全部需求的进程找到了吗？将该进程的”能执行完”标记置为1,系统收回它所要求的全部资源数YN检查全部进程的“能执行完”标记还有”能执行完”标记为0的进程吗？这一恳求担忧全,短暂不予接受YN这一恳求是安全的,可以安排.在“能执行完”标记为0的进程中重复以上两步，直到找不到资源还需数小于系统剩余资源数的进程时为止。进程已分配数还需要数A13B42C53系统剩余2进程已分配数 还需要数A22B42C53系统剩余1例例1：假定某系统有：假定某系统有12台磁带机，台磁带机，A最大须要量最大须要量4B最大须要量最大须要量6C最大须要量最大须要量8单种资源单种资源银行家算法实例银行家算法实例(a)(b)经过若干次申请、安经过若干次申请、安排，系统的状态排，系统的状态（a）状态时，若进程）状态时，若进程A提出提出申请申请1台磁带机后，接受银行台磁带机后，接受银行家算法系统假定安排后的状家算法系统假定安排后的状态态一个平安序列一个平安序列BAC状态担忧全.恳求不能满足第第60页页/89例例2 42 4个客户每个都有一个贷款额度个客户每个都有一个贷款额度单种资源单种资源银行家算法的基本思想银行家算法的基本思想已运用：已安排；最大：一共需求已运用：已安排；最大：一共需求（b）一个平安序列）一个平安序列MBAS（c)在（在（b）状态下答应）状态下答应BARBARA的申请，将担忧全的申请，将担忧全第第61页页/89l对对每每个个恳恳求求进进行行检检查查，是是否否会会导导致致担担忧忧全全状状态态。若是，则不满足该恳求；否则便满足若是，则不满足该恳求；否则便满足l检检查查状状态态是是否否平平安安的的方方法法：是是看看它它是是否否有有足足够够的的资资源源满满足足一一个个距距最最大大需需求求最最近近的的客客户户，如如此此反反复复下下去去。假假如如全全部部投投资资最最终终都都被被收收回回，则则该该状态是平安的，最初的恳求可以批准。状态是平安的，最初的恳求可以批准。系统拥有某类资源系统拥有某类资源10个个进程进程已有资源数已有资源数还要申请资源数还要申请资源数P44Q22R27a a、单项资源的银行家算法、单项资源的银行家算法第第62页页/89 假如存在这种进程，那么假定它已获得须要的全部资源，并完成工作，把它的“能执行完”标记设置成1。收回它占用的资源，更新向量V。检查还需资源表中是否有一个进程的行向量小于或等于向量V。假如没有，那么系统就可能会死锁，因为现在任何进程都无法完成了。多种资源银行家算法的执行步骤多种资源银行家算法的执行步骤 系统设两张表：“安排资源表”，记录已安排给各进程的资源数；“还需资源表”，记录各进程还须要的资源数。设3个向量：R记录各种资源的总数，A记录各种资源已安排数，V记录各种资源的剩余数。进程 磁带机 绘图仪 打印机 CD-ROMA3011B0100C1110D1101E0000进程 磁带机 绘图仪 打印机 CD-ROMA1100B0112C3100D0010E2110已安排资源表还需资源表R 6 3 4 2(资源总数)A 5 3 2 2(已安排数)V 1 0 2 0(剩余数).假定接受一个进程提出的资源恳求，修改向量A和V。.重复以上两步，直至再也找不到行向量小于或等于向量V的进程。检查全部进程的“能执行完”标记。若这个标记都是1，则表示都能顺当地完成。因此，接受资源分配后导致的新状态是平安的；假如仍存在“能执行完”标志为0的进程，则说明这一恳求所导致的状态是担忧全的，应短暂拒绝该恳求。多类资源的安排多类资源的安排（Habermann算法算法P140）第第63页页/89b b、多项资源的银行家算法、多项资源的银行家算法先定义几个向量：Resource=(R1,R2,Rm):系统各类资源的总数；aVailable=(V1,V2,Vm):系统未安排的资源数量V向量第第64页页/89l最最大大需需求求矩矩阵阵-每每个个进进程程对对每每类类资资源源的的最最大大需需求求量量,C,Cijij表示进程表示进程P Pi i需需R Rj j类资源最大数类资源最大数Claim=C11C12C1mC11C11C11Cn1 Cn1Cnm第第65页页/89安排矩阵安排矩阵表示进程当前已分得的资源数表示进程当前已分得的资源数,Aij,Aij表示进程表示进程PiPi已已分到分到RjRj类资源的个数类资源的个数Allocation=A11A12A1mA21A21A21An1 An1Anm第第66页页/89下列关系式确保成立下列关系式确保成立Ri=Vi+Aki对对i=1,.,m,k=1,.,n;表表示示全全部部资资源源要么已被安排、要么尚可安排要么已被安排、要么尚可安排CkiRj对对i=1,.,m,k=1,.,n;表表示示进进程程申申请请资资源源数数不能超过系统拥有的资源总数不能超过系统拥有的资源总数AkiCki对对i=1,.,m,k=1,.,n;表表示示进进程程申申请请任任何何类类资源数不能超过声明的最大资源需求数资源数不能超过声明的最大资源需求数第第67页页/89汇总向量汇总向量R-R-总的资源、总的资源、A-A-已安排资源、已安排资源、V-V-剩余资源剩余资源RAVPPT63状态下平安推断，平安序列？状态下平安推断，平安序列？SEE 教材P144例题 留意F向量第第68页页/89总的资源总的资源R R、已安排资源、已安排资源A A、剩余资源、剩余资源V V 图示为平安状态，平安序列（图示为平安状态，平安序列（D D，A A，E E，B B，C C）RAV第第69页页/89.系统中有AG共7个进程，6个同类资源rw，当前的资源所属关