操作系统原理-处理机管理-第二章.ppt

第2章处理机管理,处理机调度调度算法、调度时机、调度过程进程管理进程概念、进程互斥、进程同步、进程通信、死锁及死锁的处理,在多道程序系统中，处理机管理的主要任务是如何安排多任务使用处理机，即如何把处理机分配给多任务用。,（本课程重点、难点）,2.1多道程序设计,单道程序系统内存中只保留一个作业，独占资源资源利用率低多道程序系统多个作业并发执行，共享资源提高系统资源利用率新的问题：进程互斥与同步,前驱（趋）图,可用于描述程序间执行的时序关系（前趋后续关系）的DAG（DirectedAcyclicGraph，有向无循环图）,2.2.1程序的顺序执行,顺序性严格按照程序的顺序执行封闭性程序运行时独占系统资源，只有程序本身才能改变系统资源的状态。可再现性只要初始条件相同，运行结果也一样。,例：初始条件a=0P1：a=a+1；P2：a=a+1;顺序执行：P1-P2,2.2.1程序的并发执行,I1C1P1顺序执行，在第一个任务进行计算的时候，可输入第二个任务，即I1完成后才能进行I2。,程序并发执行时的特征,间断性由于共享资源，或者需要相互合作，致使相互间产生了制约关系，呈“走走停停、停停走走”的间断执行特征；失去封闭性系统资源可能由多个程序改变失去可再现性计算结果与其执行速度有关，结果不可再现。,例：初始条件a=0P1：a=a+1；P2：a=a+1;并发执行可能结果：1或2,2.1.3程序并发的条件,定义读集：程序Pi在执行期间引用的变量ai的集合。R(Pi)=a1,a2,a3,am写集：程序Pi在执行期间改变的变量bj的集合。W(Pj)=b1,b2,b3,bm,Bernstein条件,定理如果两个程序P1和P2满足下述条件，它们便能并发执行，否则不能。R(P1)W(P2)R(P2)W(P1)W(P1)W(P2)=即当两个程序的读集与写集的交集以及写集与写集的交集都为空集时，它们可以并发执行，否则不行。操作系统中许多任务不满足Bernstein条件，它们不能并发执行吗？怎么办？,异地售票例子,需要操作系统采取措施，是在计算机系统中运行的任务能安全地并发，保持结果的可再现性。,2.2进程的描述,操作系统要解决程序并发运行带来的新特征：要记录程序运行的现场信息，以使程序间断（被剥夺时间片、等待资源时阻塞等）后能够恢复现场继续运行（当运行条件满足时）要控制和协调多个程序协同完成任务，使其保持封闭性和可再现性传统的“程序”概念不足以解决这些问题为使程序能并发执行，且为了对并发执行的程序加以描述和控制，引入了“进程”的概念,进程的特性,结构特性为使程序（数据）能独立运行，为每个进程配置一个数据结构：进程控制块（ProcessControlBlock，PCB）进程实体由程序、数据段和PCB三部分构成动态性进程的实质是程序的一次执行过程具有一定的生命周期，由创建而生、由调度而执行，由撤销而消亡,进程的特性(续),并发性多个进程实体同在内存中，且能在一段时间内同时运行独立性传统OS中，进程是独立运行、独立分配资源的基本单位引入线程后，进程仍是独立分配资源的基本单位，但独立运行的单位变成了线程异步性各个进程以各自独立的、不可预知的速度向前推进,进程的概念,能反映进程实质的定义：进程是程序的一次执行进程是可以和其他计算并发执行的计算进程是一个程序及其数据在处理机上顺序执行时发生的活动。进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。进程是进程实体的一次活动。AprocessistheactivityofexecutingaprogramonaCPU.Also,calleda“task.”,进程的概念,MicrosoftWindowsInternals4thedition：进程是一个容器，其中包含了当执行一个程序的特定实例时所用到的各种资源。从最高层次的抽象来看，一个Windows进程是由以下元素构成的：1）一个私有的地址空间2）一个可执行的程序3）一个已打开句柄的列表4）一个访问令牌5）一个进程ID6）至少一个执行线程,进程的概念,1978年庐山会议：进程是一个具有一定的独立功能的程序关于某个数据集合的一次运行活动。,进程与程序的区别,从定义上看，进程是程序处理数据的过程（动态概念），而程序是一组指令的有序集合（静态概念）；进程具有动态性、并发性、独立性和异步性等，而程序不具有这些特性；从进程结构特性上看，它包含程序（以及数据和PCB）；进程和程序并非一一对应。,2.2.3进程的基本状态及其转换,进程执行时的间断性决定了进程可能具有多种状态：,参考：引入挂起功能系统中的状态,挂起：强迫进程临时换出内存，以缓解资源紧张状况,18,调度,切换,2.2.4PCB,PCB（ProcessControlBlock，进程控制块）是系统中用于存放进程的描述和控制信息的数据结构PCB的作用进程存在于系统的唯一标志为系统提供可并发执行的独立单位为系统控制和管理进程提供所需的一切信息,PCB（续）,PCB中的信息进程标识符：标识进程的唯一编号进程当前状态：执行、就绪、阻塞处理机现场保留区：进程运行时CPU现场信息进程相应的程序和数据地址进程资源清单：如打开的文件、拥有的I/O设备等进程优先级：进程调度的主要依据支持进程同步和消息机制所需要的信息进程所在的PCB的链接字，用于形成进程队列,2.2.5进程的队列,将相同状态的进程组织成一个队列，实际上就是PCB链。有多种组织形式一般线性表链接表（多队列）索引表,PCB链接队列示意图：,2.3进程控制,进程控制的主要任务是对进程生命周期进程控制，即要负责进程的创建、撤消以及实现进程的状态转换和进程通信等功能。这是系统的基本功能，由内核中相应的原语完成。原语(primitiveoratomicaction)：是OS内核中由若干多机器指令构成的完成某种特定功能的一段程序，其执行具有不可分割性，即原子特征。单处理机系统中的实现方式之一：屏蔽中断。多处理机系统中依靠硬件支持来实现，如test/上锁break;return;,开锁原语：UNLOCK（W）,置W=0返回,voidunlock(intW)W=0;/开锁return;,当进程使用完资源后，它必须将锁位置成“0”,2.4.3用开关锁原语实现进程互斥,在相关进程的程序里由上锁和开锁原语紧夹着临界区，就能保证这些进程互斥地进入各自的临界区。进入临界区之前，先执行上锁原语，如上锁原语顺利通过，则可进入临界区使用完临界资源，执行开锁原语，释放临界资源注意：上锁原语和开锁原语必须在临界区代码前后成对使用。,例：甲、乙两进程要访问同一类临界资源,甲进程：其他代码；LOCK（W）；甲进程的临界区；UNLOCK（W）；其他代码；,乙进程：其他代码；LOCK（W）；乙进程的临界区；UNLOCK（W）；其他代码；,用上锁用上锁原语和开锁原语来实现进程的互斥的确很简单，但处理机效率不高，因为上锁原语中的条件测试操作可能引起CPU“忙等”，并不符合“等则让权”的临界区使用原则。,售票的例子,互斥使用不当，易造成死锁,进程A:LOCK(W1);dosomethingLOCK(W2);dosomethingUNLOCK(W2)UNLOCK(W1),进程B:LOCK(W2);dosomethingLOCK(W1);dosomethingUNLOCK(W1)UNLOCK(W2),2.5信号量机制,信号量（Semaphore）：一种广泛使用的进程同步互斥工具。荷兰科学家Dijkstra于1965年提出，借鉴于红绿灯机制两个或多个进程可以利用彼此间收发的简单的信号来实现“正确的”并发执行，一个进程在收到一个指定信号前，会被迫在一个确定的或者需要的地方停下来，从而保持同步或互斥。,几种类型的信号量,经典的整型信号量：类似于互斥，“CPU忙等”，若使用不当，可能造成死锁记录型信号量：避免“CPU忙等”，若使用不当，可能造成死锁AND型信号量：基本机制同记录型信号量，但使用前一次申请所有资源，用完毕，放弃获得的所有资源，以避免死锁信号量集：对一个资源可一次申请多个，设置不同参数，可演化前两种信号量,2.5.1（记录型）信号量的概念,数据结构：一个二元组S：非负初值的整型变量S=0：某种资源的可用数量S=0，则正常返回（3）若S.S0，则正常返回（3）若S.S=1,V(S1,S2,Sn)for(i=1;i0)V(waiting);V(mutex);,该解法中，理发师与顾客，顾客与顾客之间都有同步关系，而只有顾客访问顾客计数器变量时需互斥。,理发师问题解法（三）：by谢青松,semaphorecustomers,barber_chair,chairs=0,0,n+1;voidbarber()while(TRUE)P(customers);V(barber_chair);Givehaircut();,voidcustomer()P(chairs);/comein/takeachairV(customers);P(barber_chair);ReceiveHaircut();V(chairs);/goout;,该解法中，把顾客进入理发店、理发、出理发店的过程看做顾客进程的临界区，相应互斥信号量chairs初值为n+1,表示最多允许n+1个顾客同时进店。顾客与理发师之间有同步关系。,注意：该解法假设不能进店的顾客都在店外等候,某小型超级市场，可容纳50人同时购物。入口处有篮子，每个购物者可拿一只篮子入内购物。出口处结帐，并归还篮子（出、入口禁止多人同时通过）。试用信号量和P、V操作写出购物者的同步算法。,分析：这是个典型的进程互斥问题，超市内部及其出入口是临界资源，需要使用信号量加以保护。,例2.7超市购物（P46，选讲）,问题解答:设置信号量,所用信号量设置如下：信号量S：初值为50，用以保证最多可以有50个购物者同时进入超市。（防止超市人过多）互斥信号量mutex：初值为1，保护篮子。保证同时只能有一个购物者进程进入出入口拿起篮子或者结帐后放下篮子。,购物者i进程（解法一）：,P（S）；P（S）；P（mutex）；P（mutex1）；从入口处进超市，并取一只篮子；同左；V（mutex）；V（mutex1）；进超市内选购商品；同左；P（mutex）；P（mutex2）；到出口结帐，并归还篮子；同左；V（mutex）；V（mutex2）；从出口离开超市；同左；V（S）；V（S）；,购物者i进程（解法二）：,桌上有个只能盛得下一个水果的空盘子。爸爸不断向盘中放苹果或桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定：当盘子空时，一次只能放入一个水果供吃者取用。试用信号量和P、V操作实现爸爸、儿子和女儿这三个循环进程之间的同步。,例2.8吃水果（P48，选讲）,问题分析,分析：本题属于生产者/消费者问题的变形，相当于一个能生产两种产品的生产者（爸爸）向两个消费者（儿子和女儿）提供产品的同步问题。因此，可参考生产者与消费者问题的解法。注意：这里未把盘子看作临界资源。而南京大学2000年的一道考研题则是此例的变形，其答案把盘子看作了临界资源，变形部分是：盘子能盛2水果，爸爸放苹果，妈妈放桔子，要求实现4个进程的同步互斥关系。,问题解答：设置信号量,同步信号量empty，初值为1，表示盘子是空的，即儿子或女儿已把盘中的水果取走。同步信号量orange，初值为0，表示爸爸尚未把桔子放入盘中。同步信号量apple，初值为0，表示爸爸尚未把苹果放入盘中。,算法描述,爸爸进程：儿子进程：女儿进程：P（empty）；P（orange）；P（apple）；将水果放入盘中；从盘中取出桔子；从盘中取出苹果；若放入的是桔子，V（empty）；V（empty）；则V（orange）；吃桔子；吃苹果；否则，V（apple）；,例2.9单行车道自动管理系统（P48，选讲）,设A、B两点之间是一段东西向的单行车道，现在要设计一个AB路段自动管理系统，管理规则如下：当AB间有车辆在行驶时，同方向的车可以同时驶入AB段，但另一方向的车必须在AB段外等待；当AB段之间无车辆行驶时，到达AB段的任一方向的车都可进入AB段，但不能从两个方向同时驶入，即只能有一个方向的车驶入；当某方向在AB段行驶的车辆驶出了AB段且暂无车辆进入AB段时，应让另一方向等待的车辆进入AB段行驶。试用信号量和P、V操作管理AB路段车辆的行驶。,问题分析,本题属于读者写者问题的变形，相当于两组读者（即两个方向的车辆）使用同一个共享文件（即AB路段）的互斥问题。因此，可参考读者写者问题的解法：AB方向：第一辆驶入AB后，不允许BA方向驶入，最后一辆驶出AB后，才允许BA方向车辆竞争道路使用权BA方向：同AB方向策略因此，需要设置2个计数器变量，分别用于计数从某个方向进入的车辆数,问题解答：设置信号量,整型变量Car_A、Car_B：初值均为0，用于对从A点及B点驶入车道的车辆进行记数。互斥信号量ma、mb：初值均为1，分别用于两个方向的车互斥地访问计数器变量Car_A及Car_B。互斥信号量mutex：初值为1，用于实现不同方向的第一辆车互斥驶入AB路段。,算法,P（mb）；若Car_B=0则P（mutex）；Car_B加1；V（mb）；车辆从B点通过AB路段到达A点；P（mb）；Car_B减1；Car_B=0则V（mutex）；V（mb）；,P（ma）；若Car_A=0则P（mutex）；Car_A加1；V（ma）；车辆从A点通过AB路段到达B点；P（ma）；Car_A减1；若Car_A=0则V（mutex）；V（ma）；,东西向(即AB向)行驶的车辆i,西东向(即BA向)行驶的车辆j,2.7进程通信,进程之间的信息交换称为进程通信。包括高、低级两种通信方式,低级通信方式：进程间交换少量信息的通信方式。如信号量机制高级通信方式：进程间以较高速率交换大量信息的通信方式。如共享内存、消息传递系统以及管道通信系统,2.7.2发送和接收原语,操作系统提供发送和接收原语，用户直接使用这些通信原语，一次就能发送成千上万的信息。发送原语：如send（接收者进程名，发送区首地址）接收原语：如receive（接收区首地址）发送原语和接收原语隐藏了进程通信的细节，连发送与接收的同步问题都在其内部用信号量机制解决了。,2.7.3消息缓冲通信方式,消息缓冲通信方式：以消息为传送单位，借助内存缓冲区，进程间利用发送及接收原语进行消息传递的通信方式。消息一般包括：消息头（控制信息）和消息体（数据信息）,Buffern,进程B,PCB(B),一种消息缓冲通信示意图,2.7.4信箱通信方式,信箱头：信箱控制信息，如格子数、互斥信号量、同步信号量等格子：一个信息,信箱由接收者创建，发送者按信箱地址发送信息，接收者从信箱接收信息。其实现方式类似于Unix的管道（采用共享文件传递信息）,发送原语与接收原语,2.8死锁问题,死锁的概念产生死锁的原因产生死锁的必要条件解决死锁问题的基本方法,1死锁的定义“你不让，我也不让”,死锁概念的提出1965年，Dijkstra研究银行家算法时提出，以后又由Havender、Lyach等人研究并发展。死锁（Deadlock，P55）：是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。称此时系统处于死锁状态或系统产生了死锁，称这些永远在互相等待的进程为死锁进程。生产者消费者问题解法中若颠倒消费者中P操作顺序会导致死锁；经典IPC问题哲学家进餐问题的一个错误解法也会导致死锁。,例2.7(3.0)用信号量机制解决哲学家进餐问题（P55，经典IPC问题之一，Dijkstra,1965）,问题描述：5位哲学家围在餐桌旁，要么思考，要么饿了时拿起左右两把叉子吃通心粉(足够用的)。要求为每位哲学家写一段程序来描述其行为，但不能出现饿死现象（死锁或饥饿）。,问题分析：相邻哲学家之间因竞争一把叉子而存在互斥关系。故需5个互斥信号量。,一个关于第i号哲学家进餐过程的不正确的算法：,思考；P(Si);拿起左边的叉子；P(S(i1)mod5)；拿起右边的叉子；吃通心粉；放下左边的叉子；V(Si);放下右边的叉子；V(S(i1)mod5)；,哲学家i进程（i0，1，2，3，4），左边筷子i，右边筷子（i+1）mod5,问题及解决方案,五位哲学家可能同时拿起左边的叉子，则他们都拿不到右边的叉子，于是发生死锁，他们将饿死。解决的办法如下：1.至多只允许四位哲学家同时去拿左边的叉子（P57）；2.仅当哲学家左右两边的叉子均可用时才允许他拿起叉子；(这更适于用AND型信号量集求解)3.规定奇数号哲学家先拿起他左边的叉子，而偶数号哲学家先拿起他右边的叉子。,（1）竞争临界资源（即系统资源不足）当系统中供多个进程共享的临界资源（如打印机、公用队列等）的数目不能满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。这个原因在多道程序系统中是无法解除的。（2）进程推进顺序不当进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁的产生。这个原因在多道程序系统中是可以解除的。,2产生死锁的原因（P57）,思考题：（北大95研）,一个OS有20个进程，竞争使用65个同类资源，申请方式是逐个进行的，一旦某个进程获得它所需要的全部资源，则立即归还所有资源。每个进程最多使用三个资源。若仅考虑这类资源，该系统有无可能产生死锁，为什么？,答：不可能产生死锁。因为死锁产生的原因有两点：系统资源不足或进程推进顺序不当，在本题中，进程所需的最大资源数为60，而系统共有该类资源65个，其资源数已足够系统内各进程使用。,3产生死锁的必要条件Coffman,1971(P57),互斥条件(mutualexclusion)指进程排他性地使用所获资源，即一个资源一次只能被一个进程使用。占有并请求条件(Holdandwait)指进程保留已经得到的资源，还要求其它的资源。不可剥夺条件(Nopreemption)指进程已获得的资源，在未使用完之前，不能被其它进程强行抢占，只能在使用完时由自己释放。循环等待条件(Circularwait)指发生死锁时，资源分配图(resourceallocationgraph)中存在有向封闭环路。如下图所示。,死锁必要条件的逆否命题预防死锁的方法。即只要死锁发生的四个必要条件之一不成立，则死锁一定不会发生。产生死锁的四个必要条件中：“互斥条件”由资源的固有特性所决定的，不仅不能改变，相反还应加以保证。实际上，“不剥夺条件”也很难破坏；故具体的预防死锁办法主要是通过破坏“占有并请求条件”和“循环等待条件”来实现的。,死锁的必要条件的理论意义,4处理死锁的基本方法,预防死锁避免死锁（银行家算法）检测与解除死锁置之不理（鸵鸟算法）,预防死锁,预防死锁：通过在资源分配中设置某些限定条件，破坏产生死锁的四个必要条件之一来实现。但“互斥条件”和“不可剥夺条件”往往由资源的性质决定，很难破坏。所以，具体的预防死锁的方法主要有两种，分别是通过破坏“占有并保持”条件以及“循环等待”条件实现的。,静态资源分配法,进程在运行前，必须一次性申请其所需的全部资源。如不能全申请到，则一个资源也不分配（AND型信号量）摒弃了“占有并请求条件”优缺点：优点：简单、安全、易实现；缺点：资源被严重浪费,有序资源使用法,所有资源都被赋予一个唯一的编号，每个进程只能按编号的升序申请资源。即对同一个进程而言，它一旦申请了一个编号为i的资源，就不允许再申请编号比i小的资源了。摒弃了“环路等待条件”。优点：安全且资源利用率比静态资源分配法有所提高，实际是一种半动态的资源分配方法。缺点：实现较困难，不实用。很难给出合适的资源编号，不便于系统增添新设备不便于用户编程，且仍有一定的资源浪费现象。,死锁的避免,死锁的避免是这样一种对付死锁的办法：系统在运行过程中采取动态的资源分配策略，保证系统不进入可能导致系统陷入死锁状态的所谓不安全状态，以避免死锁发生。常用的避免死锁的算法是“银行家算法”，系统采用此法给进程分配资源时，需先判断“如果分配，系统状态是否安全”，这很像银行家放贷前的思考过程。,(1)安全状态与安全序列,1)安全状态若在某一时刻，系统能按某种进程顺序，如，来为每个进程分配其所需的资源，直至最大需求，使每个进程均可顺利完成。则称此时系统的状态为安全状态，称这样的一个进程序列为安全序列。2)不安全状态若在某时刻，系统无法找到一个安全序列，则称系统处于“不安全状态”。,安全序列实质,安全序列的实质：序列中的每个进程Pi（i=1,2,n）到运行完成尚需要的资源量不超过系统当前剩余的资源量与所有在序列中排在它前面的进程当前所占有的资源量之和。举例：假设当前剩余资源量为S，进程序列（P1、P2），P1总共需要Tp1个资源，已经分配Ap1个资源，P2总共需要Tp2个资源，已经分配Ap2个资源：如果S=Tp1Ap1，则P1可以安全完成；当为P1分配其所需要的资源后，系统剩余资源S1=S-（Tp1Ap1）当P1完成，释放其所占的所有资源Tp1，系统剩下资源：S1+Tp1=S-（Tp1Ap1）+Tp1=S+Ap1如果S+Ap1=Tp2Ap2，则说明P2也能顺利完成。（P1，P2）就是一个安全序列。,安全状态的例子：,例2.8假定系统中三个进程P1、P2和P3共享12台磁带机。P1总共要求10台，P2要4台，P3要9台。设在T0时刻，进程P1、P2和P3已经获得5台、2台和2台，还有3台空闲没有分配(如下图所示)。问T0时刻安全吗？,1）可用资源为3，满足P2要求（需要4-2=2）2）P2完成后，释放资源，系统剩余资源为3+2=53）可用资源为5，满足P1要求（仍需要10-5=5）4）P1完成后，释放资源，系统剩余资源为3+2+5=105）可用资源为10，满足P3要求（仍需要9-2=7）因此存在一个安全序列（P2，P1，P3），系统是安全的。,假定系统中三个进程P1、P2和P3共享11台磁带机。T0时刻安全吗？,假设仍有12台磁带机，但T1时刻为P3分配1台磁带机（不按照安全序列分配资源），T1时刻安全吗？,解：经分析可知，不存在安全序列，T0时刻系统是不安全的。,解：经分析可知，不存在安全序列，T1时刻系统是不安全的。,注意：,（1）系统在某一时刻的安全序列可能不唯一，但这不影响对系统安全性的判断。（2）安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定可以避免死锁，而系统处于不安全状态则仅仅有可能进入死锁状态。,(2)银行家算法,银行家算法是最有代表性的避免死锁算法，是Dijkstra(1965)提出的。其模型基于一个小城镇的银行家的放贷行为。该银行家准备向N个客户贷款，他拥有的资金足以满足任一客户的最大资金需求，但不能同时满足所有客户的最大需求。他要求每个客贷款前必须说明自己所要的最大资金量，并且每次提出部分或全部（但不能所有客户同时提出全部）资金量申请。他只给有信誉和能力并承诺到期还本付息的客户贷款。这里，可将客户比作进程，银行家比作操作系统。银行家算法就是动态地对每个客户进程每次的资源请求进行检查，看一下如果满足它是否会引起不安全状态。假如是，则不满足该请求；否则就满足它。该算法已扩充为多资源的银行家算法。,1)可用资源向量Available1m系统中各类资源（m类资源）的当前可用数目。2)最大需求矩阵Maxnm每个进程（n个进程）对各类资源（m类）的最大需求量。3)分配矩阵Allocationnm记录系统给每个进程（n个）分配的各类（m类）资源数目。4)需求矩阵Neednm记录每个进程（n个）尚需要的各类（m类）资源数目。显然，Need=MaxAllocation。5)请求向量Request1m记录某个进程当前对各类（m类）资源的申请量。,银行家算法所用的主要数据结构,当Pi发出资源请求Requesti后，系统按下述步骤进行检查：step1.如果RequestiNeedi,则出错。step2.如果RequestiAvailable,则Pi阻塞；step3.系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Availablei=Availablei-Requesti;Allocationi=Allocationi+Requesti;Needi=Needi-Requesti;step4.系统执行安全性检测子算法，检查如果实施此次资源分配后，系统是否会处于安全状态。若安全，则完成此次试分配，成功返回；否则，将撤消此次试分配，恢复step3中改过的数据，让进程Pi等待。,银行家算法描述(P60),安全性检测子算法描述(P60)此法与死锁检测算法很相似，可对照理解,(1)初始化：work=available；/*work是available的影子变量*/finish=false；/*finish是进程可完成标志向量*/(2)若按进程编号顺序找到了一个可加入安全序列的进程，即：满足条件finishi=false且neediwork的进程Pi，则假设该进程不久将完成任务归还资源，于是置work=work+allocationi；finishi=true；重复执行这一步，直至找不到一个这样的进程为止；(3)若所有进程的可完成标志finish为真，则返回逻辑真值（表示系统将处于安全状态）；否则，返回逻辑假值（表示不安全）。,银行家算法之例一（P60）,假定系统中有四个进程P1、P2、P3、P4和三种类型的资源R1，R2，R3，资源的数量分别为9、3、6，在T0时刻的资源分配情况如图:,资源情况,进程,MaxR1R2R3,AllocationR1R2R3,NeedR1R2R3,AvailableR1R2R3,P1322100222112P2613511102P3314211103P4422002420,T0时刻是否安全？,资源情况,进程,WorkR1R2R3,NeedR1R2R3,AllocaR1R2R3,WorkR1R2R3,P2112102511623TRUEP1623222100723TRUEP3723103211934TRUEP4934420002936TRUE,Finish,（二）P2发出请求向量request2（1,0,1），系统按银行家算法进行检查：request2（1,0,1）need2（1,0,2）；request2（1,0,1）available（1,1,2）；系统先假定可为P2分配资源，并修改available、allocation2和need2向量，如下表所示：,为P2试分配资源后的有关资源数据,再利用安全性检测子算法检查系统的安全性。如下表所示。,FinishTrueTrueTrueTrue,因为存在安全序列p2,p1,p3,p4，故系统安全，系统可将资源分配给进程p2。,（三）P2申请资源后，如P1发出的资源请求request1(1,0,1)，系统能否将资源分配给它？request1（1,0,1）available（0,1,1）；不能将资源分配给它，P1阻塞。,P2分配资源后的有关资源数据,（四）P1申请资源后，如P3发出的资源请求request3(0,0,1)，系统能否将资源分配给它？available（0,1,0）不能满足任何进程的要求；不能将资源分配给它，P3阻塞，此次试分配撤销。,P3试分配资源后的有关资源数据,银行家算法之例二,例2.9假定系统中有五个进程P1、P2、P3、P4、P5和三类资源A，B，C，资源的数量分别为10、5、7，在T0时刻的资源分配情况如下图所示:,1.T0时刻是否安全?2.Request1(1,0,2)能否响应?3.Request4(3,3,0)能否响应?4.Request0(0,2,0)能否响应?,P1332122200532true,P3532011211743true,P4743431002745true,P0745743010755true,P27556003021057true,解：1.,由安检子算法知T0时刻存在安全序列：P1,P3,P4,P0,P2，故系统是安全的。,P1发出资源请求request1（1,0,2），系统按银行家算法进行检查：request1（1,0,2）need1（1,2,2）；request1（1,0,2）available（3,3,2）；系统先假定可为P1分配资源，并修改available、allocation1和need1向量，结果资源试分配情况如下表所示：,2.,再利用安全性检测子算法检查此时系统是否安全，如下表所示：,P1230020302532true,P3532011211743true,P4743431002745true,P0745743010755true,P27556003021057true,可知此时存在安全序列：P1,P3,P4,P0,P2，故系统是安全的，可立即将P1所申请的资源分配给它。当然P1,P3,P4,P2,P0也是一个安全序列。,P0发出资源请求request0（0,2,0），系统按银行家算法进行检查：request0（0,2,0）need0（7,4,3）；request0（0,2,0）available（2,3,0）；系统先假定可为P0分配资源，并修改available、allocation0和need0向量，结果资源试分配情况如下表所示：,4.,系统进行安全性检测，找不到一个安全序列，故系统将进入不安全状态。由此决定不给P0分配资源。若request0=(0,1,0)呢？,例2.10某系统有同类互斥资源m个，供n个进程共享使用。如果每个进程最多申请x个资源（1xm），试证明：当n(x-1)+1m时，系统不会发生死锁。,证明：因为每个进程最多申请x个资源，所以最坏情况是每个进程都得到了（x-1）个资源，并且现在均需申请最后一个资源。此时，系统剩余资源数为m-n(x-1)，于是只要系统中至少还有一个资源可供使用，就可以使这n个进程中某个进程得到其所需要的全部资源，并能够继续执行到完成，归还资源可供其他进程使用。因而不会发生死锁。即只要m-n(x-1)1时，系统就一定不会发生死锁。亦即当n(x-1)+1m时，系统不会发生死锁。,从理论上讲，银行家算法能有效地避免死锁，而且还不需要死锁预防法中加上的种种限制，如重新运行进程或有序申请资源。但实际上，它缺乏实用价值。因为银行家算法的执行有个前提条件，即要求进程预先提出自己的最大资源请求，并且假设系统拥有的资源总量和支持的进程个数是固定的，而且进程之间是“无关”的。但很少有进程在运行前就知道其所需资源的最大量，而且进程数也不是固定的，而是不断变化（如新用户登录或退出），况且原本可用的资源也可能突然间变成不可用（如磁带机可能坏掉）。另外，不少进程间有同步要求。总之，死锁预防法过于严格，而死锁避免法更不实用。,(3)银行家算法性能评价,死锁的检测与解除,当系统为进程分配资源时，如果不采取任何限制性措施，则系统必须提供死锁的检测与解除的手段。(1)死锁的检测检查死锁的办法是由软件定时检查系统的资源分配图中是否存在无法化简的有向环路。若是，则此时发生了死锁，且环路中的进程是死锁进程；否则不存在死锁。其理论依据是死锁定理(即死锁的充分条件)。,例：资源分配图的简化,系统处于死锁状态的充分条件：当且仅当当前状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。,死锁检测算法,死锁检测算法中的数据结构类似于银行家算法中的数据结构：（1）系统中各种可利用资源使用向量Avaliable表示（2）把不占用资源的进程Pi（Allocationi=0）计入L表中，即L=LPi（3）从进程集合中找到一个RequestiWork的进程Pi，做如下处理：化简其资源分配图，释放其资源，Work=Work+AllocationiL=LPi循环以上步骤，直到找不到RequestiWork的进程（4）若不能把所有进程均计入L表中，则表明系统状态S的资源分配图是不可完全简化的