教学课件PPT 同步、通信与死锁

1第第3 3章章 同步、通信与死锁同步、通信与死锁 主要内容主要内容0并发进程并发进程0临界区管理临界区管理0信号量与信号量与PVPV操作操作0管程（删）管程（删）0进程通信进程通信0死锁死锁0LinuxLinux同步机制和通信机制同步机制和通信机制0Windows2003Windows2003同步机制和通信同步机制和通信23.1 3.1 并发进程并发进程3.1.1 3.1.1 顺序程序设计顺序程序设计 3.1.2 3.1.2 进程的并发性进程的并发性 3.1.3 3.1.3 进程的交互：协作和竞争进程的交互：协作和竞争 33.1.1 3.1.1 顺序程序设计顺序程序设计进程的顺序性进程的顺序性 一个进程在顺序处理器上的执行是严格按一个进程在顺序处理器上的执行是严格按序的，一个进程只有当一个操作结束后，序的，一个进程只有当一个操作结束后，才能开始后继操作。才能开始后继操作。顺序程序设计是把一个程序设计成一个顺顺序程序设计是把一个程序设计成一个顺序执行的程序模块，顺序的含义不但指一序执行的程序模块，顺序的含义不但指一个程序模块内部，也指两个程序模块之间个程序模块内部，也指两个程序模块之间。4顺序程序设计的特性顺序程序设计的特性 程序执行的顺序性程序执行的顺序性 程序环境的封闭性程序环境的封闭性 程序执行结果的确定性程序执行结果的确定性 计算过程的可再现性计算过程的可再现性l顺序程序设计的缺点顺序程序设计的缺点计算机系统效率不高。计算机系统效率不高。53.1.2 3.1.2 进程的并发性进程的并发性1 1、并发程序设计、并发程序设计 进程执行的并发性：一组进程的执行在时间上是进程执行的并发性：一组进程的执行在时间上是重叠的。重叠的。并发性举例：有两个进程并发性举例：有两个进程A(a1A(a1、a2a2、a3)a3)和和B(b1B(b1、b2b2、b3)b3)并发执行。并发执行。0 a1a1、a2a2、a3a3、b1b1、b2b2、b3 b3 顺序执行顺序执行0 a1a1、b1b1、a2a2、b2b2、a3a3、b3 b3 并发执行并发执行 从宏观上看，一个时间段中几个进程都在同一处从宏观上看，一个时间段中几个进程都在同一处理器上，处于运行还未运行结束状态。理器上，处于运行还未运行结束状态。从微观上看，任一时刻仅有一个进程在处理器上从微观上看，任一时刻仅有一个进程在处理器上运行。运行。6串行工作图示串行工作图示i1p1o1i2p2o27并行工作图示并行工作图示进程进程i1i1p1p1 i i p p o oo1o1i2i2p2p2o2o2i3i3p3p3o3o3t1t1t2t2t3t3时间时间并行工作并行工作i4i4t4t4i5i5P4P4t5t58并发的实质并发的实质 并发的实质是一个处理器在几个进程之间并发的实质是一个处理器在几个进程之间的多路复用，并发是对有限的物理资源强的多路复用，并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。的互等现象，以提高系统资源利用率。92 2、并发进程的特性、并发进程的特性 无关的并发进程无关的并发进程0一组并发进程分别在不同的变量集合上操作，一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关。一个进程的执行与其他并发进程的进展无关。x并发进程的无关性是进程的执行与时间无关的并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为一个充分条件，又称为BernsteinBernstein条件条件。交互的并发进程交互的并发进程0一组并发进程共享某些变量，一个进程的执行一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果。可能影响其他并发进程的结果。10BernsteinBernstein条件条件 R(piR(pi)=a1,a2,)=a1,a2,anan，程序，程序pipi在执行期间引用的在执行期间引用的变量集变量集W(piW(pi)=b1,b2,)=b1,b2,bmbm，程序，程序pipi在执行期间改变的在执行期间改变的变量集变量集若两个程序的变量集交集之和为空集若两个程序的变量集交集之和为空集：R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)=R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)=则并发进程的执行与时间无关。则并发进程的执行与时间无关。11BernsteinBernstein条件举例条件举例例如，有如下四条语句：例如，有如下四条语句：S1:a:=x+y S2:b:=z+1S1:a:=x+y S2:b:=z+1 S3:c:=a b S4:w:=c+1 S3:c:=a b S4:w:=c+1于是有于是有：R(S1)=x,y,R(S2)=zR(S1)=x,y,R(S2)=z，R(S3)=a,bR(S3)=a,b，R(S4)=cR(S4)=c；W(S1)=a,W(S1)=a,W(S2)=bW(S2)=b，W(S3)=cW(S3)=c，W(S4)=wW(S4)=w。S1S1和和S2S2可并发执行，满足可并发执行，满足BernsteinBernstein条件条件。其他语句并发执行可能会产生与时间有。其他语句并发执行可能会产生与时间有关的错误。关的错误。12并发程序设计的优点并发程序设计的优点l对于单处理器系统对于单处理器系统,可让处理器和各可让处理器和各I/OI/O设设备同时工作备同时工作,发挥硬部件的并行能力。发挥硬部件的并行能力。l对于多处理器系统对于多处理器系统,可让各进程在不同处可让各进程在不同处理器上物理地并行，加快计算速度。理器上物理地并行，加快计算速度。l简化了程序设计任务。简化了程序设计任务。13采用并发程序设计的目的采用并发程序设计的目的 充分发挥硬件的并行性，提高系统效率。充分发挥硬件的并行性，提高系统效率。硬件能并行工作仅有了提高效率的可能性硬件能并行工作仅有了提高效率的可能性，硬部件并行性的实现需要软件技术去利，硬部件并行性的实现需要软件技术去利用和发挥，这种软件技术就是并发程序设用和发挥，这种软件技术就是并发程序设计。计。并发程序设计是多道程序设计的基础，多并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到道程序的实质就是把并发程序设计引入到系统中。系统中。143 3、与时间有关的错误、与时间有关的错误 对于一组交互的并发进程，执行的相对速对于一组交互的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误度无法相互控制，各种与时间有关的错误就可能出现。就可能出现。与时间有关错误的表现形式：与时间有关错误的表现形式：0结果不唯一结果不唯一0永远等待永远等待15（结果不唯一）机票问题（结果不唯一）机票问题/飞机票售票问题飞机票售票问题 void T1()void T2()void T1()void T2()按旅客订票要求找到按旅客订票要求找到AjAj;按旅客订票要求找到按旅客订票要求找到AjAj;int X1=Aj;int X2=Aj int X1=Aj;int X2=Aj;if(X1=1)if(X2=1)if(X1=1)if(X2=1)X1-;X2-;X1-;X2-;Aj=X1;Aj Aj=X1;Aj=X2;=X2;输出一张票输出一张票;输出一张票输出一张票;else elseelse else 输出信息输出信息 票已售完票已售完;输出信息输出信息 票已售完票已售完;16T1T1、T2T2并发执行，可能出现如下交叉情况：并发执行，可能出现如下交叉情况：T1:X1=AjT1:X1=Aj;/X1=m;/X1=mT2:X2=AjT2:X2=Aj;/X2=m;/X2=mT2:X2-;Aj=X2;T2:X2-;Aj=X2;输出一张票输出一张票;/Aj;/Aj=m-1=m-1T1:X1-;Aj=X1;T1:X1-;Aj=X1;输出一张票输出一张票;/Aj;/Aj=m-1=m-1同一张票卖给两位旅客（若只有一张余票）或者余同一张票卖给两位旅客（若只有一张余票）或者余票数不正确（若有多张余票）。票数不正确（若有多张余票）。17（永远等待）主存管理问题（永远等待）主存管理问题申请和归还主存资源问题申请和归还主存资源问题 intint X=memory;/memory X=memory;/memory为初始主存容量为初始主存容量 voidvoid borrow(int B)void return(intborrow(int B)void return(int B)B)while(B while(BX)X=X+B;X)X=X+B;进程进入等待主存资源队列进程进入等待主存资源队列;修改主存分配表修改主存分配表;X=X-B;X=X-B;释放等主存资源进程释放等主存资源进程;修改主存分配表，修改主存分配表，进程获得主存资源进程获得主存资源;18若对若对borrowborrow和和returnreturn的并发执行不加限制将会导致的并发执行不加限制将会导致错误，例如：错误，例如：Borrow:while(BBorrow:while(BX);X);Return:XReturn:X=X+B;=X+B;修改主存分配表修改主存分配表;释放等待主存释放等待主存资源的进程资源的进程；此时，因为此时，因为borrowborrow还没有进入等待队列，因此，还没有进入等待队列，因此，returnreturn的释放操作是空操作，当的释放操作是空操作，当borrowborrow进入等待队进入等待队列时，可能没有进程再来归还，处于永远等待状态列时，可能没有进程再来归还，处于永远等待状态。193.1.3 3.1.3 进程的交互：竞争与协作进程的交互：竞争与协作(1)(1)第一种是竞争关系第一种是竞争关系 系统中的多个进程之间彼此无关系统中的多个进程之间彼此无关 系统中的多个进程之间彼此相关系统中的多个进程之间彼此相关 l资源竞争的两个控制问题：资源竞争的两个控制问题：l 一个是死锁一个是死锁(Deadlock)(Deadlock)问题，问题，l 一个是饥饿一个是饥饿(Starvation)(Starvation)问题问题l 既要解决饥饿问题，又要解决死锁问题。既要解决饥饿问题，又要解决死锁问题。l进程互斥是指若干个进程因相互争夺独占型资源进程互斥是指若干个进程因相互争夺独占型资源时所产生的竞争制约关系。时所产生的竞争制约关系。20进程的交往：竞争与协作进程的交往：竞争与协作(2)(2)第二种是协作关系第二种是协作关系l某些进程为完成同一任务需要分工协作。某些进程为完成同一任务需要分工协作。l进程进程同步同步指为完成共同任务的并发进程基于某个指为完成共同任务的并发进程基于某个条件来协调它们的活动，因为需要在某些位置上条件来协调它们的活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系。产生的协作制约关系。l进程同步指两个以上进程基于某个条件来协调它们的进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。时需等待，直到消息或信号到达才被唤醒。进程进程互斥互斥关系是一种特殊的进程同步关系，即逐关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上次使用互斥共享资源，是对进程使用资源次序上的一种协调。的一种协调。213.2 3.2 临界区管理临界区管理3.2.1 3.2.1 互斥与临界区互斥与临界区3.2.2 3.2.2 实现临界区管理的几种尝试实现临界区管理的几种尝试3.2.3 3.2.3 实现临界区管理的软件方法实现临界区管理的软件方法3.2.4 3.2.4 实现临界区管理的硬件设施实现临界区管理的硬件设施223.2.1 3.2.1 互斥与临界区互斥与临界区(1)(1)并发进程中与共享变量有关的程序段叫并发进程中与共享变量有关的程序段叫“临临界区界区”，共享变量代表的资源叫共享变量代表的资源叫“临界资临界资源源”。与同一变量有关的临界区分散在各进程的程与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知。序段中，而各进程的执行速度不可预知。如果保证进程在临界区执行时，不让另一个如果保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误问是互斥的，就不会造成与时间有关的错误。23互斥与临界区互斥与临界区(2)(2)临界区调度原则：临界区调度原则：0一次至多一个进程能够进入临界区内执行；一次至多一个进程能够进入临界区内执行；0如果已有进程在临界区，其他试图进入的进程应等待；如果已有进程在临界区，其他试图进入的进程应等待；0进入临界区内的进程应在有限时间内退出，以便让等待进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入。进程中的一个进入。临界区调度原则总结：临界区调度原则总结：0互斥使用，有空让进；互斥使用，有空让进；0忙则等待，有限等待；忙则等待，有限等待；0择一而入，算法可行。择一而入，算法可行。243.2.2 3.2.2 临界区管理的尝试临界区管理的尝试 (1)(1)bool inside1=false;/P1bool inside1=false;/P1不在其临界区内不在其临界区内 boolbool inside2=false;/P2 inside2=false;/P2不在其临界区内不在其临界区内 cobegin/cobegin/*cobegincobegin和和coendcoend表示括号中的进程是一组并表示括号中的进程是一组并发进程发进程*/process P1()process P2()process P1()process P2()while(inside2);/while(inside2);/等待等待 while(inside1);/while(inside1);/等待等待 inside1=true;inside2=true;inside1=true;inside2=true;临界区临界区;临界区临界区;inside1=false;inside2=false;inside1=false;inside2=false;coendcoend可能不满足互斥条件可能不满足互斥条件25临界区管理的尝试临界区管理的尝试 (2)(2)bool inside1=false;/P1bool inside1=false;/P1不在其临界区内不在其临界区内 boolbool inside2=false;/P2 inside2=false;/P2不在其临界区内不在其临界区内 cobegincobegin process P1()process P2()process P1()process P2()inside1=true;inside2=true;inside1=true;inside2=true;while(inside2);/while(inside2);/等待等待 while(inside1);/while(inside1);/等待等待 临界区临界区;临界区临界区;inside1=false;inside2=false;inside1=false;inside2=false;coendcoend可能出现死循环可能出现死循环263.2.33.2.3实现临界区的软件算法实现临界区的软件算法PetersonPeterson算法算法(1)(1)bool inside2;bool inside2;inside0=false;inside0=false;inside1=false;inside1=false;enumenum 0,1 turn;0,1 turn;27PetersonPeterson算法算法(2)(2)cobegincobegin process P0()process P0()inside0=true;inside0=true;turn=1;turn=1;while(inside1&turn=1);while(inside1&turn=1);临界区临界区;inside0=false;inside0=false;28PetersonPeterson算法算法(3)(3)process P1()process P1()inside1=true;inside1=true;turn=0;turn=0;while(inside0&turn=0);while(inside0&turn=0);临界区临界区;inside1=false;inside1=false;coendcoend293.2.4 3.2.4 实现临界区管理的硬件设施实现临界区管理的硬件设施 关中断关中断 测试并建立指令（删）测试并建立指令（删）对换指令（删）对换指令（删）30关中断关中断 实现互斥的最简单方法实现互斥的最简单方法 关中断适用场合关中断适用场合0简单有效，对操作系统自身有用，可在更新共享变量简单有效，对操作系统自身有用，可在更新共享变量或列表的几条指令期间禁止中断。或列表的几条指令期间禁止中断。关中断方法的缺点关中断方法的缺点0不适合作为通用的互斥机制，关中断时间过长会影响不适合作为通用的互斥机制，关中断时间过长会影响性能和系统效率；性能和系统效率；0不适应于多处理器计算机系统，因为一个处理器关中不适应于多处理器计算机系统，因为一个处理器关中断，并不能防止进程在其它处理器上执行相同的临界断，并不能防止进程在其它处理器上执行相同的临界段代码；段代码；0若将这项权力赋予用户会存在危险，若用户未开中断若将这项权力赋予用户会存在危险，若用户未开中断，则系统可能因此而终止。，则系统可能因此而终止。313.3 3.3 信号量信号量与与PVPV操作操作3.3.1 3.3.1 同步与同步机制同步与同步机制3.3.2 3.3.2 信号量与信号量与PVPV操作操作3.3.3 3.3.3 信号量实现互斥信号量实现互斥3.3.4 3.3.4 五个哲学家吃通心面问题五个哲学家吃通心面问题3.3.5 3.3.5 生产者生产者-消费者问题消费者问题3.3.6 3.3.6 读者读者-写者问题写者问题3.3.7 3.3.7 理发师问题理发师问题323.3.1 3.3.1 同步和同步机制同步和同步机制 著名的生产者著名的生产者-消费者问题是计算机操作系统中消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同并发进程内在关系的一种抽象，是典型的进程同步问题。步问题。在操作系统中，生产者进程可以是计算进程、发在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进送进程；而消费者进程可以是打印进程、接收进程等等。程等等。解决好生产者解决好生产者-消费者问题就解决好了一类并发消费者问题就解决好了一类并发进程的同步问题。进程的同步问题。33生产者生产者-消费者问题表述消费者问题表述有界缓冲问题有界缓冲问题 有有n n个生产者和个生产者和m m个消费者，连接在一个有个消费者，连接在一个有k k个单位缓冲区的有界缓冲上。其中个单位缓冲区的有界缓冲上。其中，pipi和和cjcj都是并发进程，只要缓冲区未满，生产都是并发进程，只要缓冲区未满，生产者者pipi生产的产品就可投入缓冲区；只要缓生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程冲区不空，消费者进程cjcj就可从缓冲区取就可从缓冲区取走并消耗产品。走并消耗产品。34生产者生产者-消费者问题算法描述消费者问题算法描述(1)(1)intint k;k;typedef anyitemtypedef anyitem item;/item item;/item类型类型 item bufferkitem bufferk;intint in=0,out=0,counter=0;in=0,out=0,counter=0;35生产者生产者-消费者问题算法描述消费者问题算法描述(2)(2)process producer(voidprocess producer(void)while(true)/while(true)/无限循环无限循环 produce an item in nextpproduce an item in nextp;/;/生产一个产品生产一个产品 if(counter=k)/if(counter=k)/缓冲满时，生产者睡眠缓冲满时，生产者睡眠 sleep(producersleep(producer););bufferin=nextp bufferin=nextp;/;/将一个产品放入缓冲区将一个产品放入缓冲区 in=(in+1)%k;/in=(in+1)%k;/指针推进指针推进 counter+;/counter+;/缓冲内产品数加缓冲内产品数加1 1 if(counter if(counter=1)/=1)/缓冲为空，加进一件产品缓冲为空，加进一件产品 wakeup(consumerwakeup(consumer););/并唤醒消费者并唤醒消费者 36生产者生产者-消费者问题算法描述消费者问题算法描述(3)(3)process consumer(voidprocess consumer(void)while(true)/while(true)/无限循环无限循环if(counter=0)/if(counter=0)/缓冲区空，消费者睡眠缓冲区空，消费者睡眠 sleep(consumersleep(consumer););nextc=bufferout nextc=bufferout;/;/取一个产品到取一个产品到nextcnextc out=(out+1)%k;/out=(out+1)%k;/指针推进指针推进 counter-;/counter-;/取走一个产品，计数减取走一个产品，计数减1 1if(counterif(counter=k-1)/=k-1)/缓冲满了，取走一件产品并唤缓冲满了，取走一件产品并唤 wakeup(producerwakeup(producer););/醒生产者醒生产者consume the item in nextcconsume the item in nextc;/;/消耗产品消耗产品 37生产者生产者-消费者问题的算法描述消费者问题的算法描述(4)(4)生产者和消费者进程对生产者和消费者进程对countercounter的交替执行的交替执行会使其结果不唯一。会使其结果不唯一。生产者和消费者进程的交替执行会导致进生产者和消费者进程的交替执行会导致进程永远等待。程永远等待。383.3.2 3.3.2 信号量与信号量与PVPV操作操作(1)(1)前节种种方法解决临界区调度问题的缺点前节种种方法解决临界区调度问题的缺点:1)1)对不能进入临界区的进程，采用忙式等待测试对不能进入临界区的进程，采用忙式等待测试法，浪费法，浪费CPUCPU时间。时间。2)2)将测试能否进入临界区的责任推给各个竞争的将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担进程会削弱系统的可靠性，加重了用户编程负担。19651965年年E.W.DijkstraE.W.Dijkstra提出了新的同步工具提出了新的同步工具-信号信号量和量和P P、V V操作。操作。39信号量与信号量与PVPV操作操作(2)(2)信号量：一种软件资源信号量：一种软件资源 原语：内核中执行时不可被中断的过程原语：内核中执行时不可被中断的过程 P P操作原语和操作原语和V V操作操作原语原语 一个进程在某一特殊点上被迫停止执行直到接收一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信到一个对应的特殊变量值，这种特殊变量就是信号量号量(semaphore)(semaphore)，复杂的进程合作需求都可以，复杂的进程合作需求都可以通过适当的信号结构得到满足。通过适当的信号结构得到满足。40信号量与信号量与PVPV操作操作(3)(3)操作系统中，信号量表示物理资源的实体，它是操作系统中，信号量表示物理资源的实体，它是一个与队列有关的整型变量。一个与队列有关的整型变量。实现时，信号量是一种记录型数据结构，有两个实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列分量：一个是信号量的值，另一个是信号量队列的队列指针。的队列指针。信号量的值信号量的值(-2)(-2)信号量队列指针信号量队列指针41信号量分类信号量分类信号量按其用途分为信号量按其用途分为公用信号量：用户实现进程互斥，初值为公用信号量：用户实现进程互斥，初值为1 1，相，相关进程均可在此信号量上执行关进程均可在此信号量上执行PVPV操作；操作；私有信号量：多用于并发进程同步，初值为私有信号量：多用于并发进程同步，初值为0 0或或正整数，仅允许此信号量所拥有的进程执行正整数，仅允许此信号量所拥有的进程执行P P操操作，而其它相关进程可执行作，而其它相关进程可执行V V操作。操作。信号量按其取值分为信号量按其取值分为二元信号量二元信号量：仅允许取值为：仅允许取值为0 0或或1 1，主要用于解，主要用于解决互斥问题；决互斥问题；一般信号量：允许取大于一般信号量：允许取大于1 1的整型值，主要用于的整型值，主要用于解决同步问题。解决同步问题。42一般信号量一般信号量(1)(1)设设s s为一个记录型数据结构为一个记录型数据结构,一个分量为整一个分量为整形量形量value,value,另一个为信号量队列另一个为信号量队列queue,Pqueue,P和和V V操作原语定义：操作原语定义：P(s)P(s)；将信号量；将信号量s s减去减去l l，若结果小于，若结果小于0 0，则调用则调用P(s)P(s)的进程被置成等待信号量的进程被置成等待信号量s s的状的状态。态。V(s)V(s)：将信号量：将信号量s s加加1 1，若结果不大于，若结果不大于0 0，则释放一个等待信号量则释放一个等待信号量s s的进程。的进程。43一般信号量一般信号量(2)(2)typedef structtypedef struct semaphore semaphore intint value;/value;/信号量值信号量值struct pcbstruct pcb *list;/list;/信号量队列指针信号量队列指针 ;void P(semaphorevoid P(semaphore&s)&s)s.value s.value-;-;if(s.value if(s.value0)0)W(s.list W(s.list););void V(semaphorevoid V(semaphore&s)&s)s.values.value+;+;if(s.value if(s.value=0)=0)R(s.list R(s.list););44一般信号量一般信号量(3)(3)推论推论1 1：若信号量：若信号量s s为正值，则该值等于在封锁进为正值，则该值等于在封锁进程之前对信号量程之前对信号量s s可施行的可施行的P P操作数、亦等于操作数、亦等于s s所所代表的实际还可以使用的物理资源数代表的实际还可以使用的物理资源数 推论推论2 2：若信号量：若信号量s s为负值，则其绝对值等于登记为负值，则其绝对值等于登记排列在该信号量排列在该信号量s s队列之中等待的进程个数、亦队列之中等待的进程个数、亦即恰好等于对信号量即恰好等于对信号量s s实施实施P P操作而被封锁起来并操作而被封锁起来并进入信号量进入信号量s s队列的进程数队列的进程数 推论推论3 3：通常，：通常，P P操作意味着请求一个资源，操作意味着请求一个资源，V V操操作意味着释放一个资源。在一定条件下，作意味着释放一个资源。在一定条件下，P P操作操作代表挂起进程操作，而代表挂起进程操作，而V V操作代表唤醒被挂起进操作代表唤醒被挂起进程的操作程的操作453.3.3 3.3.3 信号量实现互斥信号量实现互斥 semaphore mutexsemaphore mutex;mutex mutex=1;=1;cobegin cobegin process Pi()/i=1,process Pi()/i=1,n,n P(mutexP(mutex););临界区临界区;V(mutexV(mutex););coend coend463.3.4 3.3.4 信号量解决五个哲学家吃通心面问题信号量解决五个哲学家吃通心面问题(1)(1)有五个哲学家围坐在一圆桌旁，桌中央有一盘通有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘子，每两人之间放一心面，每人面前有一只空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。每人只能直接从自己左边或右边去取叉子。47 信号量解决五个哲学家吃通心面问题信号量解决五个哲学家吃通心面问题(2)(2)48哲学哲学家吃家吃通通心心面问面问题题(3)(3)semaphore fork5;semaphore fork5;for(intfor(int i=0;i5;i+)i=0;i5;i+)forkiforki=1;=1;cobegincobeginprocess philosopher_iprocess philosopher_i()()/i=0,1,2,3,4 /i=0,1,2,3,4while(truewhile(true)think();think();P(forkiP(forki););P(fork(i+1)%5);P(fork(i+1)%5);eat();eat();V(forkiV(forki););V(fork(i+1)%5);V(fork(i+1)%5);coendcoend可能死锁！可能死锁！49有若干种办法可避免这类死有若干种办法可避免这类死锁锁l上述解法可能出现永远等待，有若干种办上述解法可能出现永远等待，有若干种办法可避免死法可避免死锁：锁：l至多允许四个哲学家同时吃；至多允许四个哲学家同时吃；l奇数号先取左手边的叉子，偶数号先取右手边奇数号先取左手边的叉子，偶数号先取右手边的叉子；的叉子；l每个哲学家取到手边的两把叉子才吃，否则一每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。把叉子也不取。503.3.5 3.3.5 信号量解决生产者消费者问题信号量解决生产者消费者问题一个生产者、一个消费者共享一个缓冲区一个生产者、一个消费者共享一个缓冲区一个生产者、一个消费者共享多个缓冲区一个生产者、一个消费者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区51一个生产者、一个消费者共享一个缓冲区的解一个生产者、一个消费者共享一个缓冲区的解 intint B;B;semaphore empty;/semaphore empty;/可以使用的空缓冲区数可以使用的空缓冲区数 semaphore full;/semaphore full;/缓冲区内可以使用的产品数缓冲区内可以使用的产品数 empty=1;/empty=1;/缓冲区内允许放入一件产品缓冲区内允许放入一件产品 full=0;/full=0;/缓冲区内没有产品缓冲区内没有产品52 cobegincobegin process producer()process consumer()process producer()process consumer()while(true while(true)while(true)while(true)produce();produce();P(fullP(full););P(empty);P(empty);take()from B;take()from B;append()to B;append()to B;V(emptyV(empty););V(full);V(full);consume();consume();coendcoend53多个生产者多个生产者/消费者、共享多个缓冲区的解消费者、共享多个缓冲区的解 item Bkitem Bk;semaphore empty;semaphore empty;empty=k;empty=k;/可以使用的空缓冲区数可以使用的空缓冲区数 semaphore full;full=0;semaphore full;full=0;/缓冲区内可以使用的产品数缓冲区内可以使用的产品数 semaphore mutex;semaphore mutex;mutexmutex=1;/=1;/互斥信号量互斥信号量 intint in=0;in=0;/放入缓冲区指针放入缓冲区指针 intint out=0;/out=0;/取出缓冲区指针取出缓冲区指针54cobegincobeginprocess producer_i()process consumer_j()process producer_i()process consumer_j()while(true while(true)while(true)while(true)produce();produce();P(fullP(full););P(emptyP(empty););P(mutexP(mutex););P(mutexP(mutex););take()from Bout take()from Bout;append to Bin append to Bin;out=(out+1)%k;out=(out+1)%k;in=(in+1)%k;in=(in+1)%k;V(mutexV(mutex););V(mutexV(mutex););V(emptyV(empty););V(fullV(full););consume();consume();coendcoend553.3.6 3.3.6 信号量解决读者信号量解决读者-写者问题写者问题(1)(1)有两组并发进程：读者和写者，共享一个文件有两组并发进程：读者和写者，共享一个文件F F，要求：，要求：允许多个读者同时执行读操作允许多个读者同时执行读操作 任一写者在完成写操作之前不允许其它读者或写任一写者在完成写操作之前不允许其它读者或写者工作者工作 写者执行写操作前，应让已有的写者和读者全部写者执行写操作前，应让已有的写者和读者全部退出退出56信号量解决读者写者问题信号量解决读者写者问题(2)(2)int readcountint readcount=0;/=0;/读进程计数读进程计数 semaphore semaphore writeblock,mutexwriteblock,mutex;writeblockwriteblock=1;mutex=1;=1;mutex=1;57信号量解决读者写者问题信号量解决读者写者问题(3)(3)cobegincobeginprocess reader_iprocess reader_i()()process writer_jprocess writer_j()()P(mutexP(mutex););P(writeblockP(writeblock););readcountreadcount+;+;写文件写文件;if(readcount if(readcount=1)=1)V(writeblockV(writeblock););P(writeblockP(writeblock););V(mutexV(mutex););读文件读文件;P(mutexP(mutex););readcountreadcount-;-;if(readcountif(readcount=0)=0)V(writeblockV(writeblock););V(mutex V(mutex););coendcoend583.3.7 3.3.7 信号量解决理发师问题信号量解决理发师问题(1)(1)理发店里有一位理发师、一把理发椅和理发店里有一位理发师、一把理发椅和n n把供等把供等候理发的顾客坐的椅子候理发的顾客坐的椅子 如果没有顾客，理发师便在理发椅上睡觉如果没有顾客，理发师便在理发椅上睡觉 一个顾客到来时，它必须叫醒理发师一个顾客到来时，它必须叫醒理发师 如果理发师正在理发时又有顾客来到，则如果有如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开空椅子可坐，就坐下来等待，否则就离开59信号量解决理发师问题信号量解决理发师问题(2)(2)intint waiting=0;/waiting=0;/等候理发顾客坐的椅子等候理发顾客坐的椅子数数 intint CHAIRS=N;/CHAIRS=N;/为顾客准备的椅子数为顾客准备的椅子数 semaphore customers,barbers,mutexsemaphore customers,barbers,mutex;customers=0;barbers=0;mutex=1;customers=0;barbers=0;mutex=1;60信号量解决理发师问题信号量解决理发师问题(3)(3)cobegincobegin process barber()process barber()while(true while(true)P(customersP(customers););/有顾客吗？若无顾客，理发师睡眠有顾客吗？若无顾客，理发师睡眠 P(mutexP(mutex););/若有顾客时，进入临界区若有顾客时，进入临界区waiting-;/waiting-;/等候顾客数少一个等候顾客数少一个 V(barbersV(barbers););/理发师准备为顾客理发理发师准备为顾客理发 V(mutexV(mutex););/退出临界区退出临界区cut_haircut_hair();/();/理发师正在理发理发师正在理发(非临界区非临界区)61process customer_iprocess customer_i()()P(mutexP(mutex););/进入临界区进入临界区 if(waitingif(waitingCHAIRS)/CHAIRS)/有空椅子吗有空椅子吗waiting+;/waiting+;/等候顾客数加等候顾客数加1 1 V(customersV(customers););/唤醒理发师唤醒理发师 V(mutexV(mutex););/退出临界区退出临界区 P(barbersP(barbers););/理发师忙，顾客坐下等待理发师忙，顾客坐下等待get_haircutget_haircut();/();/否则顾客坐下理发否则顾客坐下理发 else else V(mutexV(mutex););/人满了，走吧！人满了，走吧！coendcoend62总结补充总结补充 信号量小结信号量小结 P P、V V操作小结操作小结 针对信号量问题的补充练习针对信号量问题的补充练习631 1、信号量小结、信号量小结v 一个信号量可用于一个信号量可用于n n个进程的同步互斥；且只能由个进程的同步互斥；且只能由P P、V V操操作修改。作修改。用于互斥时，用于互斥时，S S初值为初值为1 1，取值为，取值为1-(n-1)1-(n-1)（相当于临界区的通行证，实际上也是资源个数）（相当于临界区的通行证，实际上也是资源个数）S=1S=1：临界区可用：临界区可用 S=0S=0：已有一进程进入临界区：已有一进程进入临界区 S0S=0=0 S=0:S=0:表示可用资源个数表示可用资源个数 S0:S0:表示该资源的等待队列长度表示该资源的等待队列长度642 2、P P、V V操作小结操作小结P(S)P(S)：请求分配一个资源。：请求分配一个资源。V(S)V(S)：释放一个资源。：释放一个资源。P P、V V操作必须成对出现。操作必须成对出现。用于互斥时，位于同一进程内；用于互斥时，位于同一进程内；用于同步时，交错出现于两个合作进程内。用于同步时，交错出现于两个合作进程内。多个多个P P操作的次序不能颠倒，否则可能导致死锁。操作的次序不能颠倒，否则可能导致死锁。多个多个V V操作的次序可任意。操作的次序可任意。653 3、针对信号量问题的补充练习、针对信号量问题的补充练习1)1)桌子上有一个盘子，可以存放一个水果。父亲总桌子上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中是放苹果到盘子中，而母亲总是放香蕉到盘子中；儿子专等吃盘中的香蕉，而女儿专等吃盘中的；儿子专等吃盘中的香蕉，而女儿专等吃盘中的苹果。苹果。分析：生产者消费者问题的一种变形，生产者、消费分析：生产者消费者问题的一种变形，生产者、消费者以及放入缓冲区的产品都有两类，但每类消费者只消者以及放入缓冲区的产品都有两类，但每类消费者只消费其中固定的一种产品。费其中固定的一种产品。数据结构：数据结构：semaphore dishsemaphore dish，apple apple，banana;banana;dishdish：表示盘子是否为空，初值为：表示盘子是否为空，初值为1 1 appleapple：表示盘中是否有苹果，初值为：表示盘中是否有苹果，初值为0 0 bananabanana：表示盘中是否有香蕉，初值为：表示盘中是否有香蕉，初值为0 066cobegincobeginprocess father()process father()P(dish P(dish););将苹果放到盘中；将苹果放到盘中；V(appleV(apple););process mother()process mother()P(dish P(dish););将香蕉放到盘中；将香蕉放到盘中；V(bananaV(banana););process son()process son()P(banana P(banana););从盘中取出香蕉；从盘中取出香蕉；V(dishV(dish););process daughter()process daughter()P(apple P(apple););从盘中取出苹果；从盘中取出苹果；V(dishV(dish););coendcoend.672)哲学家甲请哲学家乙、丙、丁到某处讨论问题，约定全哲学家甲请哲学家乙、丙、丁到某处讨论问题，约定全体到齐后开始讨论；在讨论的间隙四位哲学家进餐，每体到齐后开始讨论；在讨论的间隙四位哲学家进餐，每人进餐时都需使用刀、叉各一把，餐桌上的布置如下图人进餐时都需使用刀、叉各一把，餐桌上的布置如下图所示。用信号量机制说明四位哲学家的同步互斥过程。所示。用信号量机制说明四位哲学家的同步互斥过程。食品食品乙乙丙丙丁丁甲甲刀刀2叉叉1刀刀1叉叉268 分析分析 标准的哲学家进餐问题，只是哲学家人数和标准的哲学家进餐问题，只是哲学家人数和餐具及分布与经典哲学家进餐问题略有不同餐具及分布与经典哲学家进餐问题略有不同 数据结构数据结构 semaphore fork1,fork2,knife1,knife2;semaphore fork1,fork2,knife1,knife2;frokfrok表示叉，表示叉，knifeknife表示刀，初值均为表示刀，初值均为1 169cobegincobeginprocess pa()process pa()/哲学家甲哲学家甲 P(knife1);P(knife1);P(fork1);P(fork1);进餐；进餐；V(knife1);V(knife1);V(fork1);V(fork1);讨论问题；讨论问题；process pb()/哲学家乙哲学家乙 P(knife2);P(knife2);P(fork1);P(fork1);进餐；进餐；V(knife2);V(knife2);V(fork1);V(fork1);讨论问题；讨论问题；70process pc()/哲学家丙哲学家丙 P(knife2);P(knife2);P(fork2);P(fork2);进餐；进餐；V(knife2);V(knife2);V(fork2);V(fork2);讨论问题；讨论问题；process pd()/哲学家丁哲学家丁 P(knife1);P(knife1);P(fork2);P(fork2);进餐；进餐；V(knife1);V(knife1);V(fork2);V(fork2);讨论问题；讨论问题；coend.713)3)有一个阅览室，读者进入时必须先在一张登记有一个阅览室，读者进入时必须先在一张登记表上登记，此表为每个座位列出一个表目，包表上登记，此表为每个座位列出一个表目，包括座位号、姓名，读者离开时要注意注销登记括座位号、姓名，读者离开时要注意注销登记信息；假如阅览室共有信息；假如阅览室共有100100个座位，请用信号量个座位，请用信号量和和P P、V V操作实现用户进程的同步算法。操作实现用户进程的同步算法。72 分析：实际上是一个非常简单的同步分析：实际上是一个非常简单的同步-互斥问题，不要互斥问题，不要想复杂了想复杂了 数据结构：数据结构：structcharstructchar name10;name10;int int number;number;A100;A100;semaphore mutex,seatcountsemaphore mutex,seatcount;mutexmutex：用来互斥，初值为：用来互斥，初值为1 1 seatcountseatcount：对空座位计数，初值为：对空座位计数，初值为100100 for(intfor(int i=0;i100;i+)i=0;i100;i+)Ai.number=i;Ai.name Ai.number=i;Ai.name=null;=null;73cobegincobeginprocess readeri(char readernameprocess readeri(char readername)P(seatcount P(seatcount););P(mutex P(mutex)；for(intfor(int i=0;i100;i+)i=0;i100;i+)if(Ai.name=null)Ai.name=readername if(Ai.name=null)Ai.name=readername;reader get the seat number=i;reader get the seat number=i;V(mutex V(mutex););进入阅览室，在座位号进入阅览室，在座位号i i处坐下读书；处坐下读书；P(mutexP(mutex););Ai.name Ai.name=null;=null;V(mutexV(mutex););V(seatcount V(seatcount););离开阅览室；离开阅览室；coendcoend;744)4)在一个盒子里，混装了数量相等的黑白围棋子。现在用在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系统有两个进自动分拣系统把黑子、白子分开，设分拣系统有两个进程程P1P1和和P2P2，其中，其中P1P1拣白子，拣白子，P2P2拣黑子。规定每个进程每拣黑子。规定每个进程每次拣一子，当一个进程在拣时，不允许另一个进程去拣次拣一子，当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试；当一个进程拣了一子时，必须让另一个进程去拣。试用信号量和用信号量和P P、V V操作协调两个进程的并发执行。操作协调两个进程的并发执行。分析：分析：实际上就是两个进程的同步问题。实际上就是两个进程的同步问题。数据结构：数据结构：semaphore S1semapho