教学课件ppt 同步通信与死锁_1

第3章 同步、通信与死锁 主要内容 0并发进程 0临界区管理 0信号量与PV操作 0管程（删） 0进程通信 0死锁 0Linux同步机制和通信机制 0Windows2003同步机制和通信 1 3.1 并发进程 3.1.1 顺序程序设计 3.1.2 进程的并发性 3.1.3 进程的交互：协作和竞争 2 3.1.1 顺序程序设计 进程的顺序性 一个进程在顺序处理器上的执行是严格按 序的，一个进程只有当一个操作结束后， 才能开始后继操作。 顺序程序设计是把一个程序设计成一个顺 序执行的程序模块，顺序的含义不但指一 个程序模块内部，也指两个程序模块之间 。 3 顺序程序设计的特性 程序执行的顺序性 程序环境的封闭性 程序执行结果的确定性 计算过程的可再现性 l顺序程序设计的缺点 计算机系统效率不高。 4 3.1.2 进程的并发性 1、并发程序设计 进程执行的并发性：一组进程的执行在时间上是 重叠的。 并发性举例：有两个进程A(a1、a2、a3)和B(b1 、b2、b3)并发执行。 0 a1、a2、a3、b1、b2、b3 顺序执行 0 a1、b1、a2、b2、a3、b3 并发执行 从宏观上看，一个时间段中几个进程都在同一处 理器上，处于运行还未运行结束状态。 从微观上看，任一时刻仅有一个进程在处理器上 运行。 5 串行工作图示 i1p1o1i2p2o2 6 并行工作图示 进程 i1 p1 i p o o1 i2 p2 o2 i3 p3 o3 t1 t2 t3 时间 并行工作 i4 t4 i5P4 t5 7 并发的实质 并发的实质是一个处理器在几个进程之间 的多路复用，并发是对有限的物理资源强 制行使多用户共享，消除计算机部件之间 的互等现象，以提高系统资源利用率。 8 2、并发进程的特性 无关的并发进程 0一组并发进程分别在不同的变量集合上操作 ，一个进程的执行与其他并发进程的进展无 关。 x并发进程的无关性是进程的执行与时间无关 的一个充分条件，又称为Bernstein条件。 交互的并发进程 0一组并发进程共享某些变量，一个进程的执 行可能影响其他并发进程的结果。 9 Bernstein条件 R(pi)=a1,a2,an，程序pi在执行期间引用的 变量集 W(pi)=b1,b2,bm，程序pi在执行期间改变的 变量集 若两个程序的变量集交集之和为空集： R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)= 则并发进程的执行与时间无关。 10 Bernstein条件举例 例如，有如下四条语句： S1: a := x + y S2: b := z + 1 S3: c := a b S4: w := c + 1 于是有：R(S1)=x,y ,R(S2)=z， R(S3)=a,b，R(S4)=c；W(S1)=a, W(S2)=b，W(S3)=c，W(S4)=w。 S1和S2可并发执行，满足Bernstein条件 。其他语句并发执行可能会产生与时间有 关的错误。 11 并发程序设计的优点 l对于单处理器系统,可让处理器和各I/O设 备同时工作,发挥硬部件的并行能力。 l对于多处理器系统,可让各进程在不同处 理器上物理地并行，加快计算速度。 l简化了程序设计任务。 12 采用并发程序设计的目的 充分发挥硬件的并行性，提高系统效率。 硬件能并行工作仅有了提高效率的可能性 ，硬部件并行性的实现需要软件技术去利 用和发挥，这种软件技术就是并发程序设 计。 并发程序设计是多道程序设计的基础，多 道程序的实质就是把并发程序设计引入到 系统中。 13 3、与时间有关的错误 对于一组交互的并发进程，执行的相对速 度无法相互控制，各种与时间有关的错误 就可能出现。 与时间有关错误的表现形式： 0结果不唯一 0永远等待 14 （结果不唯一）机票问题 /飞机票售票问题 void T1( ) void T2( ) 按旅客订票要求找到Aj; 按旅客订票要求找到 Aj; int X1=Aj; int X2=Aj; if(X1=1) if(X2=1) X1-; X2-; Aj=X1; Aj=X2; 输出一张票; 输出一张票; else else 输出信息“票已售完“; 输出信息“票已售完 “; 15 T1、T2并发执行，可能出现如下交叉情况： T1:X1=Aj; /X1=m T2:X2=Aj; /X2=m T2:X2-;Aj=X2;输出一张票; /Aj=m-1 T1:X1-;Aj=X1;输出一张票; /Aj=m-1 同一张票卖给两位旅客（若只有一张余票）或者余 票数不正确（若有多张余票）。 16 （永远等待）主存管理问题 申请和归还主存资源问题 int X=memory; /memory为初始主存容量 void borrow(int B) void return(int B) while(BX) X=X+B; 进程进入等待主存资源队列; 修改主存分配表; X=X-B ; 释放等主存资源进程; 修改主存分配表， 进程获得主存资源; 17 若对borrow和return的并发执行不加限制将会导致 错误，例如： Borrow:while(BX); Return:X=X+B;修改主存分配表;释放等待主存资 源的进程； 此时，因为borrow还没有进入等待队列，因此， return的释放操作是空操作，当borrow进入等待队 列时，可能没有进程再来归还，处于永远等待状态 。 18 3.1.3 进程的交互：竞争与协作(1) 第一种是竞争关系 系统中的多个进程之间彼此无关 系统中的多个进程之间彼此相关 l资源竞争的两个控制问题： l 一个是死锁(Deadlock)问题， l 一个是饥饿(Starvation) 问题 l 既要解决饥饿问题，又要解决死锁问题。 l进程互斥是指若干个进程因相互争夺独占型资 源时所产生的竞争制约关系。 19 进程的交往：竞争与协作(2) 第二种是协作关系 l某些进程为完成同一任务需要分工协作。 l进程同步指为完成共同任务的并发进程基于某 个条件来协调它们的活动，因为需要在某些位 置上排定执行的先后次序而等待、传递信号或 消息所产生的协作制约关系。 l进程同步指两个以上进程基于某个条件来协调它们 的活动。一个进程的执行依赖于协作进程的消息或 信号，当一个进程没有得到来自于协作进程的消息 或信号时需等待，直到消息或信号到达才被唤醒。 进程互斥关系是一种特殊的进程同步关系，即 逐次使用互斥共享资源，是对进程使用资源次 序上的一种协调。 20 3.2 临界区管理 3.2.1 互斥与临界区 3.2.2 实现临界区管理的几种尝试 3.2.3 实现临界区管理的软件方法 3.2.4 实现临界区管理的硬件设施 21 3.2.1 互斥与临界区(1) 并发进程中与共享变量有关的程序段叫“ 临界区”， 共享变量代表的资源叫“临界 资源”。 与同一变量有关的临界区分散在各进程的 程序段中，而各进程的执行速度不可预知 。 如果保证进程在临界区执行时，不让另一 个进程进入临界区，即各进程对共享变量 的访问是互斥的，就不会造成与时间有关 的错误。 22 互斥与临界区(2) 临界区调度原则： 0一次至多一个进程能够进入临界区内执行； 0如果已有进程在临界区，其他试图进入的进程应等待 ； 0进入临界区内的进程应在有限时间内退出，以便让等 待进程中的一个进入。 临界区调度原则总结： 0互斥使用，有空让进； 0忙则等待，有限等待； 0择一而入，算法可行。 23 3.2.2 临界区管理的尝试 (1) bool inside1=false; /P1不在其临界区内 bool inside2=false; /P2不在其临界区内 cobegin /*cobegin和coend表示括号中的进程是一组并 发进程*/ process P1( ) process P2( ) while(inside2);/等待 while(inside1);/等待 inside1=true; inside2=true; 临界区; 临界区; inside1=false; inside2=false; coend 可能不满足互斥条件 24 临界区管理的尝试 (2) bool inside1=false; /P1不在其临界区内 bool inside2=false; /P2不在其临界区内 cobegin process P1( ) process P2( ) inside1=true; inside2=true; while(inside2);/等待 while(inside1);/等待 临界区; 临界区; inside1=false; inside2=false; coend 可能出现死循环 25 3.2.3实现临界区的软件算法Peterson算法(1) bool inside2; inside0=false; inside1=false; enum 0,1 turn; 26 Peterson算法(2) cobegin process P0( ) inside0=true; turn=1; while(inside1 临界区; inside0=false; 27 Peterson算法(3) process P1( ) inside1=true; turn=0; while(inside0 临界区; inside1=false; coend 28 3.2.4 实现临界区管理的硬件设施 关中断 测试并建立指令（删） 对换指令（删） 29 关中断 实现互斥的最简单方法 关中断适用场合 0简单有效，对操作系统自身有用，可在更新共享变 量或列表的几条指令期间禁止中断。 关中断方法的缺点 0不适合作为通用的互斥机制，关中断时间过长会影 响性能和系统效率； 0不适应于多处理器计算机系统，因为一个处理器关 中断，并不能防止进程在其它处理器上执行相同的 临界段代码； 0若将这项权力赋予用户会存在危险，若用户未开中 断，则系统可能因此而终止。 30 3.3 信号量与PV操作 3.3.1 同步与同步机制 3.3.2 信号量与PV操作 3.3.3 信号量实现互斥 3.3.4 五个哲学家吃通心面问题 3.3.5 生产者-消费者问题 3.3.6 读者-写者问题 3.3.7 理发师问题 31 3.3.1 同步和同步机制 著名的生产者-消费者问题是计算机操作系统 中并发进程内在关系的一种抽象，是典型的进 程同步问题。 在操作系统中，生产者进程可以是计算进程、 发送进程；而消费者进程可以是打印进程、接 收进程等等。 解决好生产者-消费者问题就解决好了一类并 发进程的同步问题。 32 生产者-消费者问题表述 有界缓冲问题 有n个生产者和m个消费者，连接在一个有 k个单位缓冲区的有界缓冲上。其中，pi 和cj都是并发进程，只要缓冲区未满，生 产者pi生产的产品就可投入缓冲区；只要 缓冲区不空，消费者进程cj就可从缓冲区 取走并消耗产品。 33 生产者-消费者问题算法描述(1) int k; typedef anyitem item; /item类型 item bufferk; int in=0,out=0,counter=0; 34 生产者-消费者问题算法描述(2) process producer(void) while (true) /无限循环 produce an item in nextp;/生产一个产品 if (counter=k) /缓冲满时，生产者睡眠 sleep(producer); bufferin=nextp;/将一个产品放入缓冲区 in=(in+1)%k; /指针推进 counter+; /缓冲内产品数加1 if(counter=1) /缓冲为空，加进一件产品 wakeup(consumer); /并唤醒消费者 35 生产者-消费者问题算法描述(3) process consumer(void) while (true) /无限循环 if (counter=0) /缓冲区空，消费者睡眠 sleep(consumer); nextc=bufferout;/取一个产品到nextc out=(out+1)%k; /指针推进 counter-; /取走一个产品，计数减1 if(counter=k-1) /缓冲满了，取走一件产品并唤 wakeup(producer); /醒生产者 consume the item in nextc;/消耗产品 36 生产者-消费者问题的算法描述(4) 生产者和消费者进程对counter的交替执 行会使其结果不唯一。 生产者和消费者进程的交替执行会导致进 程永远等待。 37 3.3.2 信号量与PV操作(1) 前节种种方法解决临界区调度问题的缺点: 1)对不能进入临界区的进程，采用忙式等待测试 法，浪费CPU时间。 2)将测试能否进入临界区的责任推给各个竞争的 进程会削弱系统的可靠性，加重了用户编程负担 。 1965年E.W.Dijkstra提出了新的同步工具-信号 量和P、V操作。 38 信号量与PV操作(2) 信号量：一种软件资源 原语：内核中执行时不可被中断的过程 P操作原语和V操作原语 一个进程在某一特殊点上被迫停止执行直到接收 到一个对应的特殊变量值，这种特殊变量就是信 号量(semaphore)，复杂的进程合作需求都可以 通过适当的信号结构得到满足。 39 信号量与PV操作(3) 操作系统中，信号量表示物理资源的实体，它是 一个与队列有关的整型变量。 实现时，信号量是一种记录型数据结构，有两个 分量：一个是信号量的值，另一个是信号量队列 的队列指针。 信号量的值(-2) 信号量队列指针 40 信号量分类 信号量按其用途分为 公用信号量：用户实现进程互斥，初值为1，相 关进程均可在此信号量上执行PV操作； 私有信号量：多用于并发进程同步，初值为0或 正整数，仅允许此信号量所拥有的进程执行P操 作，而其它相关进程可执行V操作。 信号量按其取值分为 二元信号量：仅允许取值为0或1，主要用于解 决互斥问题； 一般信号量：允许取大于1的整型值，主要用于 解决同步问题。 41 一般信号量(1) 设s为一个记录型数据结构,一个分量为整 形量value,另一个为信号量队列queue, P 和V操作原语定义： P(s)；将信号量s减去l，若结果小于0， 则调用P(s)的进程被置成等待信号量s的 状态。 V(s)：将信号量s加1，若结果不大于0， 则释放一个等待信号量s的进程。 42 一般信号量(2) typedef struct semaphore int value; /信号量值 struct pcb *list; /信号量队列指针 ; void P(semaphore if(s.value=0 S=0:表示可用资源个数 S 105 死锁 不安全 安全 安全、不安全和死锁状态空间 结论： 安全状态不是死锁状态 死锁状态是不安全状态 不是所有不安全状态都是死锁 状态 106 2、银行家算法 数据结构 Available：Availablej=k 0资源类型Rj 现有k个实例 Max：Maxi,j=k 0进程Pi最多可申请k个Rj的实例 Allocation：Allocationi,j=k 0进程Pi现在已经分配了k个Rj的实例 Need：Needi,j=k 0进程Pi还可能申请k个Rj的实例 0Needi,j = Maxi,j - Allocationi,j 107 符号说明 X 0 1 0True 10 5 77 4 310 4 7P0 3 0 2True10 4 76 0 07 4 5P2 0 0 2True7 4 54 3 17 4 3P4 2 1 1True7 4 30 1 15 3 2P3 2 0 0True5 3 21 2 23 3 2P1 Allocation A B C finishWork+allocation A B C Need A B C Work A B C 114 1 Request（1，0，2） Request（1，0，2） 系统试探为P1分配资源后，资源情况是： 0 2 03 0 2 2 3 0 4 3 10 0 24 3 3P4 0 1 12 1 12 2 2P3 6 0 03 0 29 0 2P2 3 2 2P1 7 4 30 1 07 5 3P0 Available A B C Need A B C Allocation A B C Max A B C 4 执行安全性算法，得到安全序列 : Work A B C Need A B C Allocation A B C Work+allocation A B C finish P12 3 00 2 03 0 25 3 2True P35 3 20 1 12 1 17 4 3True P47 4 34 3 10 0 27 4 5True P07 4 57 4 30 1 07 5 5True P27 5 56 0 03 0 210 5 7True P1请求资源Request(1，0，2), 执行银行家算法: 115 P0请求资源Request（0，2，0） ,执行银行家算法: 1 Request（0，2，0） Request（0，2，0） 系统试探为P0分配资源后，资源情况是： Max A B C Allocation A B C Need A B C Available A B C P07 5 30 3 07 2 32 1 0 P13 2 23 0 20 2 0 P29 0 23 0 26 0 0 P32 2 22 1 10 1 1 P44 3 30 0 24 3 1 4 再进行安全性检查，Available(2, 1, 0)不能满足任何 进程，进入不安全状态，恢复旧数据结构， P0等待。 P4请求资源Request（3，3，0） ,执行银行家算法: 1 Request(3, 3, 0) Request(3, 3, 0) =Available(2, 3, 0), P4 等待. 116 练习 Allocation Max Available A B C A B C A B C P1 2 1 2 5 5 9 2 3 3 P2 4 0 2 5 3 6 P3 4 0 5 4 0 11 P4 2 0 4 4 2 5 P5 3 1 4 4 2 4 说明： v 5个进程P1P5， v 3种资源类型A、B、C，且实例个数分别为17、5、20 v T0时刻状态如图所示 117 问题： 1) T0时刻是否为安全状态？若是，给出安全序列 2) 若在T0时刻进程P2请求资源（0，3，4），是否能实施 分配？为什么？ 3) 在（2）的基础上，若进程P4请求资源（2，0，1）， 是否能实施分配？为什么？ 4) 在（3）的基础上，若进程P1请求资源（ 0，2，0）， 是否能实施分配？为什么？ 118 Max A B C Allocation A B C Need A B C Available A B C P15 5 92 1 23 4 72 3 3 P25 3 64 0 21 3 4 P3 4 0 114 0 50 0 6 P44 2 52 0 42 2 1 P54 2 43 1 41 1 0 转换（Need） 119 （1）T0时刻是安全的，存在安全序列 2 0 4True 17 5 202 2 115 5 16P4 4 0 5True15 5 160 0 611 5 11P3 4 0 2True11 5 111 3 47 5 9P2 2 1 2True7 5 93 4 75 4 7P1 3 1 4True5 4 71 1 02 3 3P5 Allocation A B C finishWork+allocation A B C Need A B C Work A B C 120 1 Request（0，3，4） Request（0，3，4）Available（2，3，3）； 没有可用资源，不能分配，需等待！ （2） P2请求资源Request(0，3，4), 执行银行家算法: 121 1 Request（2，0，1） Request（2，0，1） 系统试探为P4分配资源后，资源情况是： 1 3 44 0 2 0 3 2 1 1 03 1 44 2 4P5 0 2 04 0 54 2 5P4 0 0 64 0 5 4 0 11P3 5 3 6P2 3 4 72 1 25 5 9P1 Available A B C Need A B C Allocation A B C Max A B C 4 执行安全性算法，得到安全序列 : Work A B C Need A B C Allocation A B C Work+allocation A B C finish P40 3 20 2 04 0 54 3 7True P54 3 71 1 03 1 4 7 4 11True P1 7 4 113 4 72 1 2 9 5 13True P2 9 5 131 3 44 0 2 13 5 15True P313 5 150 0 64 0 5 17 5 20True （3）P4请求资源Request(2，0，1), 执行银行家算法: 122 （4）P1请求资源Request（0，2，0） ,执行银行家算法: 1 Request（0，2，0） Request（0，2，0） 系统试探为P1分配资源后，资源情况是： 4 再进行安全性检查，Available(0, 1, 2)不能满足任何 进程，进入不安全状态，恢复旧数据结构， P1等待。 1 3 44 0 2 0 1 2 1 1 03 1 44 2 4P5 0 2 04 0 54 2 5P4 0 0 64 0 5 4 0 11P3 5 3 6P2 3 2 72 3 25 5 9P1 Available A B C Need A B C Allocation A B C Max A B C 123 3.6.4 死锁检测和解除 资源分配图和死锁定理 解决死锁问题的一条途径是死锁检测和解 除，这种方法对资源的分配不加任何限制 ，也不采取死锁避免措施，但系统定时地 运行一个“死锁检测”程序，判断系统内 是否已出现死锁，如果检测到系统已发生 了死锁，再采取措施解除它。 124 进程-资源分配图 约定PiRj为请求边，表示进程Pi申请资源类Rj 中的一个资源得不到满足而处于等待Rj类资源的 状态，该有向边从进程开始指到方框的边缘，表 示进程Pi申请Rj类中的一个资源。 RjPi为分配边，表示Rj类中的一个资源已被进 程Pi占用，由于已把一个具体的资源分给了进程 Pi，故该有向边从方框内的某个黑圆点出发指向 进程。 125 资源分配图例 P1P2P3 R4 R3 R2 R1 126 简化进程-资源分配图检测系统是否处于死锁状态(1) 如果进程-资源分配图中无环路，则此时系统没 有发生死锁。 如果进程-资源分配图中有环路，且每个资源类 中仅有一个资源，则系统中发生了死锁，此时， 环路是系统发生死锁的充要条件，环路中的进程 便为死锁进程。 如果进程-资源分配图中有环路，且涉及的资源 类中有多个资源，则环路的存在只是产生死锁的 必要条件而不是充分条件。 127 P1P2P3 R4 R3 R2 R1 1、存在环存在死锁的资源分配图 128 2、存在环但无死锁的资源分配图 P1 P2 P3 R2 R1 P4 129 简化进程-资源分配图检测系统是否处于死锁状态(2) 如果能在进程-资源分配图中消去此进程的所有 请求边和分配边，成为孤立结点。经一系列简化 ，使所有进程成为孤立结点，则该图是可完全简 化的；否则则称该图是不可完全简化的。 系统为死锁状态的充分条件是：当且仅当该状态 的进程-资源分配图是不可完全简化的。该充分 条件称为死锁定理。 130 检测方法：1、每种资源类型只有单个实例 思想：将资源分配图转换成对应的等待图，看是否有环。 转换方法举例如下： P1P2 P4 P3 P5 R1R5 R4R3R2 P4 P5 P3P2P1 资源分配图对应的等待图 131 2、每种资源类型有多个实例 思想：类似于银行家算法，描述如下 设Work和Finish分别是长度为m和n的向量，初始化 Work:=Available，若 Allocationi不为0，则 Finishi = false，否则，Finishi = true (i=1,2,n) 查找 i 使其满足 Finishi = false Requesti 0 0 2True 7 2 60 0 27 2 4P4 2 0 0True7 2 42 0 25 2 4P1 2 1 1True5 2 41 0 03 1 3P3 3 0 3True3 1 30 0 00 1 0P2 0 1 0True0 1 00 0 00 0 0P0 Allocation A B C finishWork+allocation A B C Request A B C Work A B C 135 Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 1 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 （2）P2请求资源（0，0，1）后的新状态： Work A B C Request A B C Allocation A B C Work+allocation A B C finish P0 0 0 0 0 0 0 0 1 0 0 1 0 T 对于i=1,2,3,4，均有Requesti(0,1,0)，因此死锁！ 136 3、应用检测算法 何时调用检测算法所取决的因素 0死锁可能发生的频率 0当死锁发生时，受影响的进程数量 常用方式 0对于每个请求都调用死锁检测算法计算开销 0在一个不频繁的时间间隔里调用检测算法通常不能 确定死锁进程中