第三章 进程控制2

1、3.4 进程的互斥 你要，我也要,1、多道程序设计带来的问题 并发执行的多个进程可能产生互斥或同步的相互制约关系，不采取措施，可能导致结果的不可再现性。影响系统效率，而且还可以导致系统崩溃。,3.4.1 互斥的定义,1、进程互斥 指的是对某个系统资源，一个进程正在使用它，另外一个想用它的进程就必须等待，而不能同时使用 。,3.4.1 互斥的定义,2、进程互斥是一种间接制约关系 多道程序系统中进程间存在的一种源于资源共享的制约关系，主要是由被共享资源的独占使用性质所决定的。,并发进程之间( ),彼此无关,A,必须同步,B,必须互斥,C,提交,可能需要同步或互斥,D,3、临界资源 限定进程只能互斥

2、地访问的资源（指一次仅允许一个进程使用的资源 ）。 4、临界资源不能抢占，不可剥夺 在抢占式操作系统中，优先级别高的进程不能中途从低优先级进程手中把临界资源抢来使用。,一、 互斥的定义,在下面的叙述中,正确的是()。,临界资源是非共享资源,A,临界资源是任意共享资源,B,临界资源是互斥共享资源,C,临界资源是同时共享资源,D,提交,下列资源中,( ) 是临界资源。,打印机,A,非共享的资源,B,共享变量,C,共享缓冲区,D,提交,5、临界资源与非临界资源举例 （1）临界资源 打印机、共享变量 （2）可剥夺性使用的资源 CPU、内存和磁盘等。,一、 互斥的定义,下面列出的选项中,不属于可剥夺性资

3、源的有( )。,CPU,A,内存,B,磁盘,C,磁带机,D,提交,一、 互斥的定义,6、临界区 进程中访问临界资源的那段程序代码称为临界区或临界段。 7、同类临界区（相关临界区） 使用同一临界资源的不同进程中的临界区。,一、 互斥的定义,8、临界区互斥访问临界资源 使用同一临界资源的进程应互斥地进入各自的临界区。 9、临界区的使用原则 空则让进，忙则等待，等则有限，等则让权,一、 互斥的定义,对进程间互斥地使用临界资源,进程可以( ),互斥地进入临界区,A,互斥地进入各自的临界区,B,互斥地进入同一临界区,C,互斥地进入各自的同类资源的临界区,D,提交,3.4.2、 互斥机制,1、操作系统实现

4、进程的互斥、同步的机制形式 （1）上锁与开锁原语 （2）信号灯机制 （3）管程机制等,2、上锁与开锁机制,（1）特点 最简单的进程互斥机制 （2）互斥实现机制 使用锁变量W来表示某种临界资源的状态。 W=0表示资源空闲可用 W=1表示资源正被使用,3.4.2、 互斥机制,（3） 上锁原语：LOCK（W）,算法思想 L1：如果 W=1那 么转向L1; 否则W=1 返回,1.考察锁位的值； 2.如果原来的值为0，将锁位置1； 3.如果为1，则返回第一步再次考察,2、上锁与开锁机制,3.4.2、 互斥机制,算法伪代码 void lock(锁变量w) test: if (w 为1) goto test

5、 else w=1; /*上锁*/ /* lock(w) */,（3） 上锁原语：LOCK（W）,2、上锁与开锁机制,3.4.2、 互斥机制,W=0; 返回,void unlock(锁变量w) w=0; /* 开锁 */ /* unlock(w) */,当进程使用完资源后，它必须将锁位置成“0”，称为开锁操作。,（3） 开锁原语：UNLOCK（W）,2、上锁与开锁机制,3.4.2、 互斥机制,3、上锁与开锁原语实现进程互斥机制方法 （1）欲进入临界区的进程，必须先执行上锁原语； （2）若上锁原语顺利通过，则进程可进入临界区； （3）当完成对临界区资源的访问后再执行开锁原语，以释放该临界资源。,

6、3.4.2、 互斥机制,例如，甲、乙两进程要访问同一类临界资源,甲进程： 其他代码； LOCK（W）； 甲进程的临界区； UNLOCK（W）； 其他代码；,乙进程： 其他代码； LOCK（W）； 乙进程的临界区； UNLOCK（W）； 其他代码；,3.4.2、 互斥机制,4、上锁原语和开锁原语实现互斥优缺点 优点：简单 缺点：处理机效率不高 因为上锁原语中的条件测试操作可能引起CPU“忙等”。,3.4.2、 互斥机制,3.5 信号量机制,荷兰著名科学家，后来的计算机图灵奖获得者，E.W.Dijkstra于1965年提出了用作进程同步工具的信号量（semaphore）机制，这是一种卓有成效的进程

7、互斥同步工具，已被广泛应用于现代计算机系统中。,信号量机制的基本原理,两个或多个进程可以利用彼此间收发的简单的信号来实现“正确的”并发执行，一个进程在收到一个指定信号前，会被迫在一个确定的或者需要的地方停下来，从而保持同步或互斥。,3.5 信号量机制,3.5.1 信号量的概念,1、信号量，也叫信号灯，一般是由两个成员组成的结构体，是一个确定的二元组（S，Q） （1）S是个具有非负初值的整型变量，表示该信号量的值，且S的值只能由定义在信号量上的P操作原语和V操作原语来改变； （2）Q是个初始状态为空的队列。,2、信号量类型是个复合类型，其一个分量是个整型分量S，另一个分量是个等待队列指针Q （一

8、个是指向PCB的指针，当多个进程都等待同一信号量时，它们就排成一个队列，由信号量的指针项指出该队列的头。）,3.5.1 信号量的概念,3、信号量通常可以简单反映出相应资源的使用情况，它与P，V操作原语一起使用可实现进程的同步和互斥。,3.5.1 信号量的概念,4、信号量的整型分量S的值的物理含义,（1）当S0时，表示某类可用资源的数目，或者说表示可以执行P操作而不会被阻塞的进程的数目；,3.5.1 信号量的概念,（2）当S0时，其绝对值表示因等待信号量S被阻塞在阻塞队列中的进程数，即系统中因请求该类资源而被阻塞的进程的数目 （3）S的值只能由P、V操作来改变。,4、信号量的整型分量S的值的物理

9、含义,3.5.1 信号量的概念,3.5.2 P、V操作原语,1、P、V原语意思 （1）P代表荷兰语的proberen，意为“测试”； （2）V代表荷兰语的verhogen，意为“增加”。 现在很多国外的文献都使用wait和signal操作（或者down和up操作）代替P、V操作。,2、P（S）原语操作的算法描述,（1）S减1； （2）若S0，则调用P（S）的进程返回，继续执行； （3）若S0,A,0 ，则调用V（S）的进程继续执行， 返回；（说明没有等待该信号量的进程） （3）若S0,A,0）个单元的缓冲区。P1每次用produce（）生成一个正整数并用put（）送入缓冲区某一空单元中；P2每

10、次用getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。,作答,正常使用主观题需2.0以上版本雨课堂,可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本,定义资源信号量empty、even、odd，用于控制生产者与消费者之间的同步，其中，empty表示空缓冲区的数目，even表示缓冲区中偶数的个数，odd表示缓冲区中奇数的个数； 定义互斥信号量mut

11、ex，用于实现进程对缓冲区的互斥访问。 semahpore empty=N,even=0,odd=0,mutex=1;,答案解析,（1）相同点：P、V操作总是配对出现的。 （2）不同点 P、V在互斥问题中总是出现在同一个进程的代码中，且紧紧夹着临界区； 在同步问题中，却是分别出现在两个合作进程的代码中，需要等消息的一方用P操作，相应的对同一信号量的V操作则在发出此消息的另一方中。,2、进程同步与互斥在P、V形式上的异同,P、V原语实现进程同步与互斥的实现总结,互斥与同步习题和解决,1、有两个用户进程A和B，在运行过程中都要使用系统中的一台打印机输出计算结果。 试说明A、B两进程之间存在什么样的

12、制约关系？ 为保证这两个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。,解： (1) A、B两进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。,互斥与同步习题和解决,（2）mutex：用于互斥的信号量，初值为1。 进程A 进程B . P(mutex) P(mutex) 申请打印机 申请打印机 使用打印机 使用打印机 V(mutex) V(mutex) ,互斥与同步习题和解决,2、 有一个阅览室，共有100个座位，读者进入时必须先在一张登记表上登记，该表为每一座位列一表目，包括座

13、号和读者姓名等，读者离开时要消掉登记的信息，试问： （1） 为描述读者的动作，应编写几个程序，设置几个进程？ （2） 试用PV操作描述读者进程之间的同步关系。,互斥与同步例题,读者的动作都是一样的：登记进入阅览室，阅读，撤消登记离开阅览室，因此可写一个程序，设n(n100)个进程。,分析：,读者共享的资源有阅览室的座位和登记表，因此诸个读者进程之间有两种互斥制约关系，需设2个信号量来实现： seat：用于实现诸读者对阅览室的空闲座位的互斥竞争，初值为100； mutex：用于实现诸读者对登记表的互斥访问，初值为1。,分析：,解：(1)可写一个程序，设n(n100)个进程 (2)读者进程read

14、eri(i=1,2,3,)描述如下：,P（seat）; /*申请空座位*/ P（mutex）; /*申请登记*/ 登记； V（mutex） /*允许其他读者登记*/ 阅读； P（mutex）; /*申请撤消登记*/ 撤消登记； V（mutex）； /*允许其他读者撤消登记*/ V（seat）； /*释放座位，允许他人进入*/,互斥与同步例题,课堂作业,1、用P.V操作解决司机与售票员的问题,2、 用P.V操作解决下图之同步问题:,思考与作业,3、写出下列进程趋势图中各进程之间同步关系,3.7 进程通信(communication),3.7.1 进程通信方式 3.7.2 消息缓冲机制 3.7.3

15、 邮箱通信 3.7.4 进程通信实例管道,1、简介,（1）进程之间的信息交换称为进程通信。 （2）合作进程间所交换的信息量，少则是一个状态或数据，多则成千上万字节的。 （3）按通信所交换的数据量多少进程通信分为低级和高级两种方式。,3.7.1 进程通信方式,低级通信 高级通信,2、通信方式划分 （1）按照通信量大小划分,3.7.1 进程通信方式,低级通信：在进程间交换数据量少的进程通信方式。 一般只传送一个和几个字节的信息，达到控制进程执行速度的作用（例如进程的同步与互斥）。 信号量机制就是一种低级通信方式，它作为同步工具是卓有成效的，但作为通信工具则不够理想。,2、通信方式划分 （1）按照通

16、信量大小划分,3.7.1 进程通信方式,低级通信：在进程间交换数据量少的进程通信方式。 缺点： 传输效率低； 通信对用户不透明,2、通信方式划分 （1）按照通信量大小划分,3.7.1 进程通信方式,高级通信 用户可以直接利用操作系统所提供的一组通信命令，高效地传送大量数据的一种通信方式。 优点： 传输效率高。 通信过程对用户是透明的,2、通信方式划分 （1）按照通信量大小划分,3.7.1 进程通信方式,=共享存储器系统包括共享内存变量（如信号量机制）和共享内存区两种通信方式。 =消息传递系统包括消息缓冲和信箱两种通信方式。 =管道通信方式,2、通信方式划分 （2）根据通信实施的方式和数据存取的

17、方式,3.7.1 进程通信方式,3.7.2 高级通信方式,主从式 会话式 消息或邮箱机制 共享存储区方式,1、主从式通信方式,（1）特点： 主进程可以自由使用从进程资源或数据 从进程的动作受到主进程的控制 主进程和从进程的关系固定 （2）典型例子： 终端控制进程和终端进程,3.7.2 高级通信方式,2、会话式通信方式,定义：通信进程双方成为使用进程和服务进程，使用进程调用服务进程提供的服务 两进程在通信时有固定连接关系 典型案例 用户进程和磁盘管理进程通信,3.7.2 高级通信方式,3、消息或邮箱机制,（1）消息：表示通信进程之间大信息量的交换 （2）消息组成：发送进程名、接受进程名、数据和有

18、关数据操作,图3.16消息的组成,3.7.2 高级通信方式,（3）通信特点 只要存在空缓冲区或邮箱，发送进程就可以通信 发送进程与接收进程没有直接连接关系，接收进程可以接受多个发送进程消息,3、消息或邮箱机制,3.7.2 高级通信方式,（3）通信特点 发送和接收进程之间存在缓冲区或邮箱用来存放被传送消息,图3.17缓冲区或邮箱通信结构,3、消息或邮箱机制,3.7.2 高级通信方式,4、共享存储区通信,（1）特点 通信进程之间交互信息时通过对同一共享数据区的操作达到通信目的，共享区属于每一进程 在通信中不需要移动数据。,3.7.2 高级通信方式,3.7.3 消息缓冲机制,1、发送进程：在自己内存

19、空间设置发送缓冲区，把欲发送消息填入其中，最后使用发送进程将消息发送出去 2、接收进程：在自己的内存中设置相应的接收区，再调用接受进程接受消息,3.7.2 消息缓冲机制,3、特点： （1）发送进程和接收进程使用不同的缓冲区用来存放和发送消息 （2）发送进程建立消息存储区，接收进程建立消息接收区,3.7.3 消息缓冲机制,3、特点： （3）发送进程与接收进程不用共享数据缓冲区，因此不存在互斥问题，只要各自缓冲区有资源即可 （4）发送进程必须告诉接受进程消息已经发出，所以两者之间存在同步关系,3.7.3 消息缓冲机制（续）,4、消息缓冲机制正常通信条件 在发送进程把消息写入缓冲区和把缓冲区挂入消息

20、队列时，应禁止其他进程对该缓冲区消息队列的访问；同理，接收进程正从消息队列中取消息时，也应禁止其他进程对该队列的访问； 接收缓冲区消息队列无消息时，接收进程不能接受任何消息,5 消息缓冲通信模型,3.7.4 邮箱通信,1 定义：发送进程申请建立一与接收进程链接的邮箱,3.7.4 邮箱通信,2 特点 发送进程将消息发送给邮箱，接收进程取出邮箱中消息 邮箱作为发送进程和接收进程共有的私有数据结构，在互斥的条件下可以实现通信 问题：如何实现发送进程与接受进程的制约关系？,3.7.4 邮箱通信,3 进程之间正常通信应满足条件： 发送进程发送消息时，邮箱中至少有一个空格能存放消息 接收进程接收消息时，邮

21、箱中至少有一个消息存在,4 邮箱通信结构图,图3.18邮箱通信结构,3.7.4 邮箱通信,3.7.4 邮箱通信,3.7.5 管道(pipe),1、管道是一条在进程间以字节流方式传送的通信通道。 2、它由OS核心的缓冲区（通常几十KB）来实现，是单向的；常用于命令行所指定的输入输出重定向和管道命令。（先进先出的，一个进程写，一个进程读） 3、在使用管道前要建立相应的管道，然后才可使用。,4、管道机制中的同步与互斥,管道机制必须提供三方面的协调努力： 互斥：当一个进程正在对PIPE进行读写时，另一个必须等待（一次只有一个进程可以访问） 同步：当写进程把一定量的数据（如4KB）写入PIPE后（创建后

22、，大小是固定字节的），便睡眠等待，直到读进程取走数据后再唤醒它；当读进程读一个空PIPE时，也应睡眠等待，直到写进程将消息写入管道为止，才将它唤醒。,3.7.5 管道(pipe),4、管道机制中的同步与互斥,管道机制必须提供三方面的协调努力： 对方是否存在。只有已确定对方存在时，方能进行通信。,3.7.5 管道(pipe),5. UNIX管道,（1）通过pipe系统调用创建无名管道，得到两个文件描述符，分别用于写和读。 int pipe(int fildes2); 文件描述符fildes0为读端，fildes1为写端； 通过系统调用write和read进行管道的写和读；,3.7.5 管道(pi

23、pe),5. UNIX管道,通过pipe系统调用创建无名管道，得到两个文件描述符，分别用于写和读。 进程间双向通信，通常需要两个管道； 只适用于父子进程之间或父进程安排的各个子进程之间（只有相关进程可以共享无名管道）；,3.7.5 管道(pipe),命名管道服务器支持多客户：为每个管道实例建立单独线程或进程。 （1）CreateNamedPipe在服务器端创建并返回一个命名管道句柄； （2）ConnectNamedPipe在服务器端等待客户进程的请求；,6. Windows 管道,3.7.5 管道(pipe),（3）CallNamedPipe从管道客户进程建立与服务器的管道连接； （4）Rea

24、dFile、WriteFile（用于阻塞方式）、ReadFileEx、WriteFileEx（用于非阻塞方式）用于命名管道的读写；,6. Windows 管道,3.7.5 管道(pipe),图3.21管道通信,7. UNIX管道编程,3.7.5 管道(pipe),例1：用c语言编写一个程序，建立一个管道pipe，同时父进程生成一个子进程，子进程向pipe中写入一个字符串，父进程从pipe中读取该字符串,7. UNIX管道编程,7. UNIX管道编程,例2：编写一程序，建立一个管道。同时，父进程生成子进程P1，P2，这两个子进程分别向管道写入各自的字符串，父进程读出他们。,图3.22父进程和子进

25、程P1，P2通信例子,7. UNIX管道编程,3.8 死锁问题 你不让，我也不让,在多道程序系统中，多个进程并发运行，共享资源，从而提高了资源的利用率。但是若对资源的管理和使用不当，在一定条件下会导致系统发生一种随机性故障死锁。在一些系统中，比如实时控制系统，系统一旦发生死锁将导致灾难性的后果。 死锁问题是E.W.Dijkstra在1965年研究银行家算法时首次提出的，以后又由Havender、Lyach等人研究并发展。,3.8.1.死锁的定义,1、相关概念 （1）死锁（Deadlock）：是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推

26、进下去。称此时系统处于死锁状态或系统产生了死锁。,3.8.1.死锁的定义,1、概念 （2）死锁进程 这些永远在互相等待的进程为死锁进程。 （3）死锁后果 所占用的资源或者需要它们进行某种合作的其它进程就会相继陷入死锁，最终可能导致整个系统处于瘫痪状态。,2、死锁原因 计算机系统中，如果系统的资源分配策略不当，或者更常见的是程序员写的程序有错误等，则会导致进程因竞争资源不当（往往与进程的推进速度有关）而产生死锁的现象。,3.8.1.死锁的定义,3、死锁案例,（1）文件打印 将一个大文件由磁带拷贝至打印机，进程需要同时访问磁带驱动器和打印机，并且不允许其他进程这时访问它们。在只有一个进程的系统中，

27、该进程可以要求任何它所需要的资源，然后进行工作。但是，在一个多道程序系统中，就有可能出现严重的问题。,3.8.1.死锁的定义,A、B两个进程准备打印一个大的磁带文件,A,B,R1,R2,打印机,磁带机,3.8.1.死锁的定义,3、死锁案例 （1）文件打印,（2）哲学家就餐问题,有5个哲学家，围坐在圆桌旁，他们的生活方式是交替地进行思考和进餐；圆桌上间隔地摆放着5把叉子和5个装有通心粉的盘子，规定第i号哲学家固定坐在第i把椅子上（i=0,1,2,3,4），且每个哲学家必须两手分别拿起他左右两旁的那两把叉子，才能吃通心粉；假定通心粉的数量足够5个哲学家用的。,3、死锁案例,假设这5把叉子与椅子相应

28、也按逆时针方向从0开始连续编号，即第i号哲学家左边摆着第i号叉子，右边摆着第(i+1)mod 5)号叉子，这里的mod代表模运算，即整除取余。 显然，在这个问题中叉子是哲学家进餐竞争的临界资源，5把叉子应分别用一个初值为1的信号量表示，这5个信号量构成一个信号量数组S。,（2）哲学家就餐问题,3、死锁案例,则第i号哲学家的进餐过程描述如下,哲学家（i0，1，2，3，4） 思考； P(Si); 拿起左边的叉子； P(S(i1)mod5)； 拿起右边的叉子； 吃通心粉； 放下左边的叉子； V(Si); 放下右边的叉子； V(S(i1)mod5)； （该算法可能会死锁）,死锁经典案例哲学家就餐问题,

29、解决死锁方法1：使用互斥信号量,哲学家（i0，1，2，3，4） 思考； P(mutex); P(Si); 拿起左边的叉子； P(Si1mod5)； 拿起右边的叉子； 吃通心粉； 放下左边的叉子； V(Si); 放下右边的叉子； V(Si1mod5)； V(mutex),死锁经典案例哲学家就餐问题,有何缺点,解决死锁方法2： AND型信号量机制,AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，等到进程使用完毕后再一起释放。也就是说，对若干个临界资源的分配，采取原子操作的方式：要么全部分配给进程，要么一个也不分配。 由死锁理论可知，这样就可避免上述死锁情况

30、的发生。 联合型信号量机制就是采用临界资源的静态分配用于解决死锁问题。,哲学家（i0，1，2，3，4） 思考； P(Si and Si1mod5)； 拿起左边的叉子； 拿起右边的叉子； 吃通心粉； 放下左边的叉子； V(Si); 放下右边的叉子； V(Si1mod5)； /临界资源的全部分配,解决死锁方法2： AND型信号量机制,（1）竞争临界资源 当系统中供多个进程共享的临界资源（如打印机、公用队列等）的数目不能满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。这个问题在多道程序系统中是无法避免的。,3.8.2 产生死锁的原因,（2）进程推进顺序不当 进程在运行过程中，请求和释放临界资

31、源的顺序不当，也同样会导致死锁的产生。这个问题在多道程序系统中是可以解决的。（解决死锁主要围绕该问题展开）,3.8.2 产生死锁的原因,造成死锁的原因是( )。,内存容量太小,A,系统进程数量太多,系统资源分配不当,B,CPU速度太慢,C,进程推进顺序不合适,D,外存容量太小,E,提交,两个进程争夺同一个资源()。,一定死锁,A,不一定死锁,B,不死锁,C,以上说法都不对,D,提交,一、竞争资源引起死锁,1资源的分类：可剥夺和非剥夺性资源 可剥夺性资源： CPU和主存 不可剥夺性资源：磁带机、打印机等 当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放。,2竞争非剥夺性资

32、源 两个进程分别准备打印一个非常大的磁带文件（双方都拥有部分资源，同时在请求对方已占有的资源。）,打印机R1,磁带机R2,P1,P2,一、竞争资源引起死锁,二、进程推进顺序不当引起死锁,资源少也未必一定产生死锁。如两个人过独木桥，如果两个人都要先过，在独木桥上僵持不肯后退，必然会因竞争资源产生死锁；但是，如果两个人上桥前先看一看有无对方的人在桥上，当无对方的人在桥上时自己才上桥，那么问题就解决了。 所以，如果程序设计得不合理，造成进程推进的顺序不当，也会出现死锁。,思考题,1、一个OS有20个进程，竞争使用65个同类资源，申请方式是逐个进行的，一旦某个进程获得它所需要的全部资源，则立即归还所有

33、资源。每个进程最多使用三个资源。若仅考虑这类资源，该系统有无可能产生死锁，为什么？,思考题：,答：不可能。因为死锁产生的原因有两点：系统资源不足或推进顺序不当，在本题中，进程所需的最大资源数为60，而系统共有该类资源65个，其资源数已足够系统内各进程使用。,1互斥条件 多个并发进程只能互斥访问临界资源。为了保证并发执行的封闭性和正确性，互斥条件必须保持。 2占有并请求条件（部分分配） 已分配到了一些临界资源的进程可以申请新的资源。,3.8.3 产生死锁的必要条件,3不可剥夺条件 进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。

34、 4循环等待条件 链中的每一个进程都在等待相邻进程所占用的资源。,3.8.3 产生死锁的必要条件,如果发现系统有() 的进程队列就说明系统有可能发生死锁了。,互斥,A,可剥夺,B,循环等待,C,同步,D,提交,3.8.4 死锁的解决办法,1、死锁的预防（静态） 2、死锁的避免（动态） 3、 死锁的检测和恢复 4、 鸵鸟算法,这种办法是在系统运行之前就采取措施，即在系统设计时确定资源分配算法，消除发生死锁的任何可能性。 该方法虽然比较保守、资源利用率低，但因简单明了并且安全可靠，仍被广泛采用。,一、死锁的预防（防止）（静态法）,3.8.4 死锁的解决办法,产生死锁的四个必要条件中，互斥条件由临界

35、资源的互斥特性所决定的，不仅不能改变，相反还应加以保证，因此实际上只有三种方法。,一、死锁的预防（防止）（静态法）,1静态资源分配法（摒弃“占有并请求条件”）,系统规定每一个进程在开始运行前，都必须一次性地申请其在整个运行过程所需的全部资源。此时，若系统有足够的资源，便把进程想要的全部资源一次性地分配给它；若不能全部满足进程的资源请求，则一个资源也不分给它。这样，进程在运行过程中就不会再提出资源请求，从而破坏了占有与请求条件。,一、死锁的预防（防止）（静态法）,静态资源分配法的优缺点：,优点：简单、安全、易实现。 缺点： （1）资源被严重浪费 （2）进程延迟运行。,一、死锁的预防（防止）（静态

36、法）,2摒弃“不可剥夺条件”,进程在需要资源时必须得到满足，否则就放弃已经占有的资源。即：一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后再需要时再重新申请。,一、死锁的预防（防止）（静态法）,2摒弃“不可剥夺条件”,实现起来比较复杂，且要付出很大的代价。 进程的周转时间较长，系统开销大。,一、死锁的预防（防止）（静态法）,3有序资源使用法（摒弃“循环等待条件”）,系统中的所有资源按类都被赋予一个唯一的编号，每个进程只能按编号的升序申请资源。即对同一个进程而言，它一旦申请了一个编号为i的资源，就不允许再申请编号比i小的资源了，因此，

37、破坏了循环等待条件。,一、死锁的预防（防止）（静态法）,3有序资源使用法（摒弃“循环等待条件”）,（1）优点：安全且资源利用率比静态资源分配法有所提高，因为它实际是一种半动态的资源分配法。 （2）缺点：实现较困难，因为难给出合适的资源编号，不便于系统增添新设备，不便于用户编程，且仍有一定的资源浪费现象。,一、死锁的预防（防止）（静态法）,系统出现死锁时一定同时保持了四个必要条件。采用按序分配资源的策略可以破坏其中的(),互斥条件,A,占有条件,B,循环等待条件,C,非抢夺条件,D,提交,资源静态分配法可以预防死锁的发生,它们使死锁四个条件中的( )不成立。,互斥条件,A,请求和保持条件,B,不

38、可剥夺条件,C,环路等待条件,D,提交,二、 死锁的避免 （动态法）,1、特征 （1）多个进程在并发执行中采取动态的资源分配策略，保证系统不进入可能导致系统陷入死锁状态的所谓不安全状态，以避免死锁发生。,二、 死锁的避免 （动态法）,1、特征 （2）不对进程申请资源加任何限制，而是对进程提出的每一次资源请求进行动态检查，并根据检查结果决定是否分配资源以满足进程的请求。,二、 死锁的避免 （动态法）,2、优点 由于采用了动态的资源分配策略，所以资源利用率比死锁的防止办法高。,3、系统的状态,（1）安全状态 若在某一时刻，系统中存在某种进程序列，如，如果系统按此序列为每个进程分配其所需的资源，直至

39、最大需求，使每个进程均可顺利完成。则称此时系统的状态为安全状态，称这样的一个进程序列为安全序列。,二、 死锁的避免 （动态法）,3 、系统的状态,(1) 安全状态 安全序列的实质是：序列中的每一个进程Pi（i=1,2,n）到以后运行完成尚需要的资源量不超过系统当前剩余的资源量与所有在序列中排在它前面的进程当前所占有的资源量之和。,二、 死锁的避免 （动态法）,（2） 不安全状态,若在某一时刻，系统中不存在一个安全序列，则称系统处于不安全状态。,二、 死锁的避免 （动态法）,3 、系统的状态,4、安全状态的例子,例：假定系统有三个进程P1、P2、P3，共有12台磁带机。进程P1总共要求10台磁带

40、机，P2和P3分别要求4台和9台。设在T0时刻，进程P1、P2和P3已经获得5台、2台和2台，还有3台空闲没有分配。,进程,最大需求,已分配,可用,P1,10,5,3,P2,P3,4,2,2,9,T0时刻系统是安全的。这时存在一个安全序列,5、注意事项,（1）系统在某一时刻的安全状态可能不唯一，但这不影响对系统安全性的判断。 （2）安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定可以避免死锁，而系统处于不安全状态则仅仅可能进入死锁状态。,二、 死锁的避免 （动态法）,5、注意事项,二、 死锁的避免 （动态法）,6、银行家算法,(1) 作用 银行家算法是最有代表性的避

41、免死锁算法，是Dijkstra提出的。其模型基于一个小城镇的银行家，他向一群客户分别承诺了一定金额的贷款，而他知道不可能所有客户同时都需要最大的贷款额。在这里，我们可将客户比作进程，银行家比作操作系统。银行家算法就是对每一个客户的请求进行检查，检查如果满足它是否会引起不安全状态。假如是，那么不满足该请求；否，那么便满足。,二、 死锁的避免 （动态法）,6、银行家算法,（2）执行特征 要设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。 即：每当进程提出资源请求且系统的资源能够满足该请求时，系统将判断如果满足此次资源请求系统状态是否安全，如果判断结果为安全，则给该进程分配资源，否

42、则不分配资源，申请资源的进程将阻塞。,（3）银行家算法的执行条件 要求进程预先提出自己的最大资源请求，并且假设系统拥有固定的资源总量。,6、银行家算法,（4）银行家算法中所用的主要的数据结构 可利用资源向量Available 表示系统中各类资源的当前可利用数目。 如果Availablej=k，表示系统中现有Rj类资源k个。,6 银行家算法,（4）银行家算法中所用的主要的数据结构 最大需求矩阵Max 每个进程对各类资源的最大需求量 Allocation 已为每个进程分配的数量或者说每个进程对各类资源当前的占有量。,6 银行家算法,（4）银行家算法中所用的主要的数据结构 需求矩阵Need 某进程对

43、各类资源尚需要的数目。 Need=MaxAllocation,6 银行家算法,（4）银行家算法中所用的主要的数据结构 请求向量Request（通常等于Need） 它记录某个进程当前对各类资源的申请量，是银行家算法的入口参数。 在实际计算中一般不用该参数。,6 银行家算法,当Pi发出资源请求后，系统按下述步骤进行检查： 如果Requesti Needi ，则出错。 如果RequestiAvailable，则Pi 阻塞； 系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值：Availablei=Availablei-Requesti; Allocationi=Allocationi+R

44、equesti; Needi = Needi- Requesti;,6 银行家算法,银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need,下列选项正确的是( )。,Maxi,j=Allocationi,j+Needi,j,A,Needi,j= Allocationi,j+ Maxi,j,B,Maxi,j= Availablei,j+Needi,j,C,Needi,j= Availablei,j+ Maxi,j,D,提交,系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，正式将资源分配给进程Pi，以完

45、成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,(6) 银行家算法描述,（1）设置两个向量 （1）工作向量Work. 表示系统可提供给进程继续运行所需要的各类资源的数目，开始时，Work=Available。,7、银行家算法执行安全性描述,（1）设置两个向量 （2）Finish 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false；当有足够的资源分配给进程时，令Finishi=true.,7、银行家算法执行安全性描述,（2）执行过程的描述,1)初始化：work=available；finish=false； 2)若按进行编号顺序找

46、到了一个可加入安全序列的进程 即：满足条件finishi=false且 neediwork的进程Pi ，将其加入安全序列，进程Pi完成任务将会归还资源，设置 work=work+allocationi和finishi=true 重复执行第（2）步。,7、银行家算法执行安全性描述,2.执行过程的描述,3)若所有进程的可完成标志finish都为真，则返回逻辑真值（表示系统处于安全状态）； 4)否则，返回逻辑假值（表示不安全）；,7、银行家算法执行安全性描述,8、银行家算法分析,算法评价： 银行家算法从避免死锁的角度上说是非常有效的，但是，从某种意义上说，它缺乏实用价值，因为很少有进程能够在运行前就

47、知道其所需资源的最大值，而且进程数也不是固定的，往往在不断地变化（如新用户登录或退出），况且原本可用的资源也可能突然间变成不可用（如磁带机可能坏掉）。 因此，在实际中，如果有，也只有极少的系统使用银行家算法来避免死锁。,9 银行家算法案例,假定系统中有四个进程P1、P2、P3、P4和三种类型的资源R1，R2，R3，资源的数量分别为9、3、6，在T0时刻的资源分配情况如图:,资源情况,进程,Max R1 R2 R3,Allocation R1 R2 R3,Need R1 R2 R3,Available R1 R2 R3,P1 3 2 2 1 0 0 2 2 2 1 1 2 P2 6 1 3 5

48、1 1 1 0 2 P3 3 1 4 2 1 1 1 0 3 P4 4 2 2 0 0 2 4 2 0,T0时刻是否安全？,资源情况,进程,Work R1 R2 R3,Need R1 R2 R3,Allocation R1 R2 R3,Work R1 R2 R3,P2 1 1 2 1 0 2 5 1 1 6 2 3 P1 6 2 3 2 2 2 1 0 0 7 2 3 P3 7 2 3 1 0 3 2 1 1 9 3 4 P4 9 3 4 4 2 0 0 0 2 9 3 6,Finish True True True True,9 银行家算法案例,习题,例3.9 某系统有同类互斥资源m个，供n

49、个进程共享使用。如果每个进程最多申请x个资源（1xm），试证明：当n(x-1)+1m时，系统不会发生死锁。,9 银行家算法案例,证明：因为每个进程最多申请x个资源，所以最坏情况是每个进程都得到了（x-1）个资源，并且现在均需申请最后一个资源。此时，系统剩余资源数为m-n(x-1)，于是只要系统中至少还有一个资源可供使用，就可以使这n个进程中某个进程得到其所需要的全部资源，并能够继续执行到完成，归还资源可供其他进程使用。因而不会发生死锁。即只要m-n(x-1)1时，系统就一定不会发生死锁。亦即当n(x-1)+1m时，系统不会发生死锁。,9 银行家算法案例,某计算机系统中有8台打印机,有K个进程竞

50、争使用,每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是( )。,2,A,3,B,4,C,5,D,提交,三、死锁的检测和解除,死锁的检测和恢复技术是指定期启动一个软件检测系统的状态，若发现有死锁存在，则采取措施恢复之。,1、死锁的检测 检查死锁的办法就是由软件检查系统中由进程和资源构成的有向图是否构成一个或多个环路，若是，则存在死锁，否则不存在。,三、死锁的检测和解除,2死锁的解除,（1）撤消进程法 撤消全部死锁进程：代价太大，该做法很少用。 最小代价撤消法：首先计算死锁进程的撤消代价，然后依次选择撤消代价最小的进程，逐个地撤消死锁进程，回收资源给其他进程，直至死锁不复存在。,三

51、、死锁的检测和解除,（2）挂起进程法 （剥夺资源） 使用挂起/激活机构挂起一些进程，剥夺它们的资源以解除死锁，待条件满足时，再激活进程。 目前挂起法比较受到重视。,2死锁的解除,三、死锁的检测和解除,显然，无论哪一种解除死锁的方法，都需要很大的开销。但是死锁的检测与解除办法不对系统的资源分配等加任何限制，因此是对付死锁的诸办法中导致资源利用率最高的一种办法，在对安全性要求高的大型系统中常用。,三、死锁的检测和解除,3.9 管程(monitor),1、引入和实现机制 （1）用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。易发生死锁； （2）基本思想是把信号量及

52、其操作原语封装在一个对象内部； （3）与面向对象编程中的类相似。,2、作用 （1）管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。 （2）管程可以函数库的形式实现。相比之下，管程比信号量好控制。 （3）管程就是用类的机制实现并发进程的同步与互斥。,3.9 管程(monitor),3.管程的定义和实现,（1）管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。（进程定义区别） （2）管程是一个程序设计语言结构，提供了与信号量同样的功能，但更易于控制。在高级语言Java、C+中可以实现。,3.9 管程(monitor),5. 信号量

53、同步的缺点（与面向过程编程相似） （1）同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏） （2）易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序,3.9 管程(monitor),5. 信号量同步的缺点（与面向过程编程相似） （3）不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局 （4）正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误,3.9 管程(monitor),6.管程的例子读者、写者问题,3.9 管程(monitor),7.管程的实现要素,（1）管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部函数来间接地访问管程中的共享变量；,3.9 管程(monitor),7.管程的实现要素,（2）为了保证管程共享变量的数据完整性，规定管程互斥进入； （3）管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以