处理器管理 (2)PPT讲稿.ppt

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