计算机操作系统-6并发-3进程通信、死锁 20150513

1、计算机操作系统6 并发程序设计 6.5 进程通信6.5.1 进程通信进程通信的概念 交往进程通过信号量操作实现进程互斥和同步，这是一种低级通信方式 进程有时还需要交换更多的信息（如把数据传送给另一个进程），可以引进高级通信方式进程通信机制， 实现进程间用信件来交换信息 进程通信扩充了并发进程的数据共享进程直接通信 发送或接收信件的进程指出信件发给谁或从谁那里接收信件send(P, 信件)：把信件发送给进程Preceive(Q, 信件)：从进程Q接收信件进程间接通信 发送或者接收信件通过一个信箱来进行，该信箱有唯一标识符 多个进程共享一个信箱send(A, 信件) : 把信件传送到信箱A rec

2、eive(A, 信件) : 从信箱A接收信件间接通信的信箱 信箱是存放信件的存储区域，每个信箱可以分成信箱特征和信箱体两部分 信箱特征指出信箱容量、信件格式、指针等 信箱体用来存放信件，信箱体分成若干个区，每个区可容纳发送信件原语的处理流程 若指定的信箱未满 则把信件送入信箱中指针所指示的位置，释放等待该信箱中信件的等待者 否则，发送信件者被置成等待信箱的状态接收信件原语的处理流程 若指定信箱中有信件 则取出待者件，释放等待信箱的等 否则，接收信件者被置成等待信箱中信件的状态计算机操作系统6 并发程序设计 6.5 进程通信6.5.2 高级进程通信机制基于流的进程通信 多个进程使用一个共享的消息

3、缓冲区（可称为管道、多路转接器、套接字） 一些进程往消息缓冲区中写入字符流（send/write） 一些进程从消息缓冲区中读出字符流（receive/read） 信息交换单位基于字符流，长度任意基于字符流的进程通信规约发送进程1接收进程1发送进程M管道/多路转接器/套接字接收进程Nread(字节流)write(字节流)read(字节流)write(字节流)远程过程调用RPC 采用客户/服务器计算模式 服务器进程提供一系列过程/服务，供客户进程调用 客户进程通过调用服务器进程提供的过程/服务获得服务 考虑到客户计算机和服务器计算机的硬件异构型，外部数据表示XDR被引入来转换每台计算机的特殊数据格

4、式为标准数据格式基于RPC/XDR的高级通信规约参数翻译参数翻译客户进程mcall 服务器.过程i客户进程1call 服务器.过程i服务器进程调用过程/服务1过程/服务2过程/服务N返回计算机操作系统6 并发程序设计 6.6 死锁6.6.1 死锁的产生死锁的产生 允许多个进程并发执行共享系统资源时，系统必须提供同步机制和进程通信机制 然而，对这种机制使用不当的话，可能会出现进程永远被阻塞的现象 例如，两个进程分别等待对方占有的一个资源，于是两者都不能执行而处于永远等待， 这种现象称为“死锁”死锁的定义 一组进程处于死锁状态是指：每一个进程都在等待被另一个进程所占有的、不能抢占的资源。例如， 存

5、在n个进程P1, P2, , Pn 进程Pi因为申请不到资源Ri而处于等待状态 而Ri又被Pi+1占有，Rn被P1占有 显然，这n个进程的等待状态永远不能结束， 这n个进程就处于死锁状态死锁的产生(例1) 例1 竞争资源产生死锁。设系统有打印机、读卡机各一台，它们被进程P和Q共享。两个进程并发执行，它们按下列次序请求和释放资源：进程P-请求读卡机请求打印机释放读卡机释放打印机进程Q-请求打印机请求读卡机释放读卡机释放打印机死锁的产生(例2) 例2 PV操作使用不当产生死锁进程Q1P(s1);P(s2);使用r1和r2;V(s1);V(s2);进程Q2P(s2);P(s1);使用r1和r2;V(

6、s2);V(s1);死锁的产生(例3) 例同类资源分配不当引起死锁 若系统中有m个资源被n个进程共享，当每个进程都要求个资源，而mn(K-1)+1时，如果分配不得当就可能引起死锁 例如，m=5，n=5，k=2，采用的分配策略是为每个进程轮流分配。首先，为每个进程轮流分配一个资源，这时，系统中的资源都已分配完了；于是第二轮分配时，各进程都处于等待状态，导致了死锁死锁的产生(例4) 例对临时性资源使用不加限制引起死锁 在进程通信时使用的信件可以看作是一种临时性资源，如果对信件的发送和接收不加限制的话，则可能引起死锁 比如，进程P1等待进程P3的信件S3来到后再向 进程P2发送信件S1；P2又要等待

7、P1的信件S1来 到后再向P3发送信件S2；而P3也要等待P2的信 件S2来到后才能发出信件S3。在这种情况下就形成了循环等待，永远结束不了，产生死锁解决死锁问题的三个方法 综合上面的例子，产生死锁的因素不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关 可从三个方面来解决死锁问题: 死锁防止 死锁避免 死锁检测和恢复计算机操作系统6 并发程序设计 6.6 死锁6.6.2 死锁的防止死锁产生的四个必要条件 互斥条件: 进程应互斥使用资源，任一时刻一个资源仅为一个进程独占 占有和等待条件: 一个进程请求资源得不到满足而等待时，不释放已占有的资源 不条

8、件: 任一进程不能从另一进程那里抢夺资源 循环等待条件: 存在一个循环等待链，每一个进程分别等待它前一个进程所持有的资源死锁的防止 破坏四个必要条件之一，死锁就可防止 破坏第一个条件，把独占型资源改造成共享 性资源，使资源可同时访问而不是互斥使用。这是一个简单的办法，但对许多资源往往是不能做到的 采用式调度方法可以破坏第三个条件，但式调度方法目前只适用于对主存资源和处理器资源的分配，而不适用于所有资源静态分配(预分配) 所谓静态分配是指一个进程必须在执行前就申请它所要的全部资源，并且直到它所要的资源都得到满足之后才开始执行 所有并发执行的进程要求的资源总和不超过系统拥有的资源数 采用静态分配后

9、，进程在执行中不再申请资源，因而不会出现占有了某些资源再等待另一些资源的情况，即破坏了第二个条件层次分配 这种分配策略将阻止第四个条件的出现 在层次分配策略下，资源被分成多个层次 一个进程得到某一层的一个资源后，它只能再申请在较高层的资源 当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源 当一个进程获得了某一层的一个资源后，它想再申请该层中的另一个资源，那么，必须先释放该层中的已占资源计算机操作系统6 并发程序设计 6.6 死锁6.6.3 死锁的避免死锁的避免 当不能防止死锁的产生时，如果能掌握并发进程中与每个进程有关的资源申请情况，仍然可以避免死锁的发生 只需在为申请者分配资

10、源前先测试系统状态，若把资源分配给申请者会产生死锁的话，则拒绝分配，否则接收申请，为它分配资源银行家算法 银行家算法：借钱给有偿还能力的客户 系统首先检查申请者对资源的最大需求量，如果现存的资源可以满足它的最大需求量时，就满足当前的申请 换言之，仅仅在申请者可能无条件地归还它所申请的全部资源时，才分配资源给它银行家算法(例) 为了进一步说明这种算法，考虑下面的例子。假设系统有三个进程P, Q, R，系统只有一类资源共10个，目前分配情况如下：进程已占资源还需要申请数P44Q22R27银行家算法(例)对P执行分配剩余资源1对R执行分配剩余资源1 P或者R再申请资源时，不能分配，因为现在只剩下2个

11、资源，不能满足它们的最大需求进程已占资源还需要申请数P44Q22R36进程已占资源还需要申请数P53Q22R27计算机操作系统6 并发程序设计 6.6 死锁6.6.4 死锁的检测死锁的检测 解决死锁问题的另一条途径是死锁检测方法 这种方法对资源的分配不加限制，但系统定时运行一个“死锁检测”程序，判断系统内是否已出现死锁，若检测到死锁则设法加以解除死锁的检测 检测的一种方法：可设置两张表格来记录进程使用资源的情况 等待资源表记录每个被阻塞进程等待的资源 占用资源表记录每个进程占有的资源 进程申请资源时，先查该资源是否为其它进程所占用；若资源空闲，则把该资源分配给申请者且登入占用资源表；否则，则登

12、入进程等待资源表死锁的检测进程等待资源P1r1P2r2P3r3资源占用进程r1P1r2P2r3P3r4P4r5P5死锁的检测 死锁检测程序定时检测这两张表，若有进程Pi等待资源rk，且rk被进程Pj占用，则说Pi 和Pj具有“等待占用关系”，记为W(Pi, Pj) 死锁检测程序反复检测这两张表，可以列出所有的“等待占用关系” 如果出现W(Pi, Pj), W(Pj, Pk), , W(Pm, Pn), W(Pn, Pi)时，显然，系统中存在一组循环等待资源的进程：Pi, Pj, Pk, , Pm, Pn， 也就是说出现了死锁死锁检测的数据结构 把两张表格中记录的进程使用和等待资源的情况 用一个矩阵A来表示当Pi等待被Pj占用的资源时当Pi与Pj不存在等待占用关系时10其中b=ij进程进程P1P2.PnP1b11b12.bn2P2b21b22.bn2.Pnbn1bn2.bn2死锁检测的算法 死锁检测程序可用Warshall的传递闭包算法检测是否有死锁发生，即对矩阵A构造传递闭包A*bij A*bij中的每个bij是对Abij执