4进程的同步与通信,进程死锁.ppt

1第第4章章 进程的同步与通信、进程死锁进程的同步与通信、进程死锁 主要内容：主要内容：并发执行，临界段，信号量，经并发执行，临界段，信号量，经典进程同步问题，消息传递原理，死锁。典进程同步问题，消息传递原理，死锁。重点：重点：临界段、同步、互斥的概念；信号量临界段、同步、互斥的概念；信号量的概念和物理意义；消息传递的原理，死锁的概念和物理意义；消息传递的原理，死锁的概念。的概念。难点：难点：信号量解决进程同步与互斥的方法，信号量解决进程同步与互斥的方法，死锁防止、避免。死锁防止、避免。计算机操作系统前趋图：前趋图：用于描述一个程序的各部分用于描述一个程序的各部分（程序段或语句）间的执行顺序关系，（程序段或语句）间的执行顺序关系，或者是一个大的计算各子任务间的因果或者是一个大的计算各子任务间的因果关系。关系。1）是一个有向无循环图；）是一个有向无循环图；2）图的结点对应程序中的一条语句、）图的结点对应程序中的一条语句、一个程序段或一个进程；一个程序段或一个进程；3）结点间的有向边：表示两个结点之）结点间的有向边：表示两个结点之 间存在的偏序或前趋关系间存在的偏序或前趋关系“”；s1s3s2s5s4s7s61.程序的顺序执行程序的顺序执行计算机操作系统指各程序段按照某种先后次序执行，仅当前指各程序段按照某种先后次序执行，仅当前一个操作执行完后才能执行后继操作。一个操作执行完后才能执行后继操作。1.程序的顺序执行程序的顺序执行I1C1P1I2C2P2其中其中I、C、P分别表示输入分别表示输入、计算和打印操作计算和打印操作图图3-2 程序顺序执行时的前趋图程序顺序执行时的前趋图顺序执行的特点：顺序执行的特点：顺序性，封闭性，可再现性顺序性，封闭性，可再现性计算机操作系统概念：概念：若干个程序（或程序段）同时在系统中运行，这若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的，一个程些程序（或程序段）的执行在时间上是重叠的，一个程序（或程序段）的执行尚未结束，另一个程序（或程序序（或程序段）的执行尚未结束，另一个程序（或程序段）的执行已经开始。段）的执行已经开始。2.程序的并发执行程序的并发执行I1I2I3C1C2C3P1P2P3n 若顺序执行三个作若顺序执行三个作业共需要业共需要9（3*3）分钟）分钟n 并行执行三个作业并行执行三个作业只需要只需要5（5/3*3）分钟）分钟 计算机操作系统l 间断性：间断性：并发程序由于共享资源或为完成同一项任务而相并发程序由于共享资源或为完成同一项任务而相互合作，形成相互制约关系。互合作，形成相互制约关系。程序并发执行的特点：程序并发执行的特点：l 失去封闭性：失去封闭性：多个程序共享系统中的各种资源，资源的多个程序共享系统中的各种资源，资源的状态将由多个程序改变，失去封闭性。一个程序执行时，会受状态将由多个程序改变，失去封闭性。一个程序执行时，会受到其他程序的影响。到其他程序的影响。l 不可再现性（待续）不可再现性（待续）并发与共享的问题并发与共享的问题：并行程序访问共享数据：并行程序访问共享数据问题举例问题举例:(:(countcount为共享变量为共享变量初值初值=300)=300)Program A:N=count N=N+100 count=N Program B:M=count M=M-200 count=M 如果按以下次序占处理机运行如果按以下次序占处理机运行:N=count,N=N+100;N=count,N=N+100;M=count,M=M-200,count=M;M=count,M=M-200,count=M;count=N.count=N.结果结果count=400(count=400(应为应为200)*200)*7并发的需要并发的需要n操作系统应尽量支持用户态程序最大限度地并发执行。操作系统应尽量支持用户态程序最大限度地并发执行。n程序设计要利用程序设计要利用OSOS对并发运行的支持，安排事务并发对并发运行的支持，安排事务并发执行。执行。n操作系统核心程序也要尽可能地并发运行操作系统核心程序也要尽可能地并发运行4.1 4.1 并发执行实现并发执行实现 S1S2S3图图4.1 任务中子任务关系示意图任务中子任务关系示意图84.1.1 4.1.1 并发编程方法并发编程方法n传统的串行程序存在着并行成分：传统的串行程序存在着并行成分：Read(a)Read(a)；Read(b)Read(b)；c=a+bc=a+b；Write(c)Write(c)ReadRead（a a）和）和ReadRead（b b）两个语句可并行）两个语句可并行执行执行。9n识别程序中的并发成分有两种方法：识别程序中的并发成分有两种方法：u程序员写顺序程序，用识别工具识别程序员写顺序程序，用识别工具识别并发成分。再组织使用操作系统的并发并发成分。再组织使用操作系统的并发机制。机制。u由程序员识别并发成分由程序员识别并发成分:用并发程序设计语言设计并发程序，用并发程序设计语言设计并发程序，由编译系统安排并发；由编译系统安排并发；直接利用操作系统的系统调用。直接利用操作系统的系统调用。10n 并发程序设计语言并发程序设计语言 -并发语句并发语句n它是一种高级语言；它是一种高级语言；n语法形式：语法形式：Parbegin Parbegin S1S1；S2S2；SnSn；ParendParend；1 1）并发语句示例）并发语句示例 1 1ParbeginParbegin read read（a a）；）；readread（b b）；）；ParendParend；c=a+bc=a+b；writewrite（c c）；）；112）并发语句示例）并发语句示例2Var F,G:file of T;r,s:T;reset(F);read(F,r);while not eof(F)dos=r;Parbegin write(G,s);read(F,r);Parend;write(G,r);优点优点:并发语句的结构化特征非常好。并发语句的结构化特征非常好。缺点：缺点：存在着描述能力不强的缺点，即存在着描述能力不强的缺点，即存在着用存在着用Parbegin/ParendParbegin/Parend语句无语句无法描述的并发优先关系。法描述的并发优先关系。改进手段：改进手段：辅以其他手段，则并发语句可以辅以其他手段，则并发语句可以大大增加其描述并发的能力。大大增加其描述并发的能力。124.1.2并发执行的实现并发执行的实现n前面是对并发的高级语言描述，要真正实现并前面是对并发的高级语言描述，要真正实现并发执行，需要通过发执行，需要通过OSOS支持的进程机制。支持的进程机制。n实现的两种方法：实现的两种方法：1)OS1)OS提供进程创建，结束和同步的系统调用；提供进程创建，结束和同步的系统调用；2)2)由并行语言编译器将并发语言的语句转化由并行语言编译器将并发语言的语句转化为对为对OSOS的系统调用。的系统调用。13与进程相关的系统调用与进程相关的系统调用nUNIXUNIX操作系统利用进程支持并发执行；操作系统利用进程支持并发执行；n它提供了如下系统调用：它提供了如下系统调用：nforkfork（）：创建一个新进程。（）：创建一个新进程。(1)(1)该子进程继承了父进程的程序空间，复该子进程继承了父进程的程序空间，复制了父进程的数据段和栈段。制了父进程的数据段和栈段。也就是说不管也就是说不管是父进程还是子进程，在占有处理机后，都是父进程还是子进程，在占有处理机后，都从从forkfork（）调用的返回点开始运行（）调用的返回点开始运行;(2)(2)父进程父进程forkfork（）调用的返回值是子进程（）调用的返回值是子进程的进程标识的进程标识pidpid；(3)(3)子进程子进程forkfork（）调用的返回值是（）调用的返回值是0 0。14nexitexit（statusstatus）：进程结束。该系统调用发）：进程结束。该系统调用发出后，操作系统将从系统中删除调用出后，操作系统将从系统中删除调用exitexit的的进程，并将进程，并将statusstatus值传给等待它结束的父进值传给等待它结束的父进程。程。nwaitwait（&status&status）：等待子进程结束。）：等待子进程结束。(1)(1)当有多个子进程时，任一个子进程结束即当有多个子进程时，任一个子进程结束即将控制返回调用者，并将子进程调用将控制返回调用者，并将子进程调用exitexit（statusstatus）时的）时的statusstatus值送到值送到&status&status指针所指单元中。指针所指单元中。(2)(2)在控制返回调用者时，同时将所等到的子在控制返回调用者时，同时将所等到的子进程进程pidpid作为作为waitwait（）系统调用函数的返回（）系统调用函数的返回值。值。nwaitpidwaitpid（pidpid，）：等待）：等待pidpid所指定的进所指定的进程结束。程结束。15多进程实现前述的读写并发程序多进程实现前述的读写并发程序pid=fork（）；）；if pid=0 then read（b）；）；exit（0）；）；else read（a）；）；wait（&status）；）；c=a+b；write（c）；）；16n同步关系（直接制约）：同步关系（直接制约）：为了完成一个共同任务，相为了完成一个共同任务，相互协作的几个进程需要在某些确定点上协调他们的工互协作的几个进程需要在某些确定点上协调他们的工作，等待来自其它进程的信息，以调整它们的推进速作，等待来自其它进程的信息，以调整它们的推进速度，方可顺利执行完毕。度，方可顺利执行完毕。输入进程输入进程缓冲区缓冲区计算进程计算进程4.2 4.2 进程的进程的同步与互斥同步与互斥n n互斥关系（间接制约）：互斥关系（间接制约）：互斥关系（间接制约）：互斥关系（间接制约）：把并发进程间存在的因相互把并发进程间存在的因相互竞争使用独占资源（共享资源）而产生的制约关系。竞争使用独占资源（共享资源）而产生的制约关系。例如：例如：打印机，共享内存；打印机，共享内存；17例例1同步关系同步关系 S1S2S4S5S7S3S6进程进程P1依次运行依次运行S1，S2，S4，S5，S7；进程进程P2依次运行依次运行S3，S618n 临界资源临界资源临界资源：临界资源：一次仅允许一个进程使用的硬件或软一次仅允许一个进程使用的硬件或软件资源。件资源。一般包括：慢速设备，共享的变量、数据结构、一般包括：慢速设备，共享的变量、数据结构、缓冲区、表格、队列、栈、文件等。缓冲区、表格、队列、栈、文件等。注意：注意：对于临界资源，必须互斥访问，否则会导致执对于临界资源，必须互斥访问，否则会导致执行结果的不确定性。行结果的不确定性。4.2.1 4.2.1 同步与临界段问题同步与临界段问题19例：例：2个进程个进程P1，P2分别对共享变量分别对共享变量account执行加执行加1和加和加2的操作，的操作，account 初始值为初始值为 0，account的结果的结果为多少？为多少？P1，P2的执行顺序如下：的执行顺序如下：P1 M=account;M=M+1;account=M;P2 N=account;N=N+2;account=N;P1 M=account;M=M+1;account=M;P2 N=account;N=N+2;account=N;进程推进顺序进程推进顺序 按此顺序执行按此顺序执行account=2按此顺序执行按此顺序执行account=1两点说明：两点说明：两点说明：两点说明：u产生与时间有关的错误。产生与时间有关的错误。u对临界资源的互斥使用，应先申请、判断。对临界资源的互斥使用，应先申请、判断。20n 临界段临界段n定义：定义：指在进程中访问临界资源的那段代码。指在进程中访问临界资源的那段代码。n访问过程：访问过程：1）在进入临界段之前，写一段代码以检查可否进入临）在进入临界段之前，写一段代码以检查可否进入临界段，通常把这段代码称为界段，通常把这段代码称为进入区进入区(申请，判断申请，判断)。2）在退出临界段后，必须有一段代码来清除）在退出临界段后，必须有一段代码来清除“正在访正在访问临界段问临界段”标志，或发出本进程已经退出临界段的标志，或发出本进程已经退出临界段的信息，把这段代码称为信息，把这段代码称为退出区退出区（释放）。（释放）。21 一个访问临界资源的进程描述如下：一个访问临界资源的进程描述如下：While(1)entry code;/进入区进入区 critical code;/临界段临界段 exit code;/退出区退出区 remainder code;/剩余区剩余区；22例例2 2：P1,P2P1,P2两进程使用同一打印机。如果两进程使用同一打印机。如果不互斥使用会交叉输出。不互斥使用会交叉输出。Entry codeexit code使用打印机使用打印机P1Entry codeexit code使用打印机使用打印机P223例例3:3:对共享变量对共享变量countcount的互斥访问。的互斥访问。Parbegin P1:M:=count;M:=M+1;count:=M;P2:N:=count;N:=N+2;count:=N;Parend;Entry codeexit codeEntry codeexit code24如何实现进入区、退出区代码如何实现进入区、退出区代码同步机构同步机构n 同步机构：同步机构：指能实现进程同步的机制，该机制指能实现进程同步的机制，该机制能把其它进程需要的信息发送出去，也能测试自能把其它进程需要的信息发送出去，也能测试自己需要的信息是否到达。己需要的信息是否到达。n 同步机构应遵循同步机构应遵循4个准则：个准则：1、空闲让进；、空闲让进；2、忙则等待；、忙则等待；3、有限等待；、有限等待；4、让权等待；、让权等待；n实现方法实现方法软件方法软件方法硬件方法硬件方法254.2.2 4.2.2 实现临界段的硬件方法实现临界段的硬件方法与计算机体系结构有关与计算机体系结构有关1、屏蔽中断法、屏蔽中断法中断引起的并发会导致错误的结果中断引起的并发会导致错误的结果 进程进程1的程序的程序disableInterrupt();Balance=balance+amount;enableInterrupt();进程进程2的程序的程序disableInterrupt();Balance=balance-amount;enableInterrupt();两条命令：两条命令：enableInterrupt，disableInterrupt缺点：缺点：1）可能影响到）可能影响到I/O行为行为2）只能用于单处理机系）只能用于单处理机系统统262 2、“Test_and_SetTest_and_Set”指令指令该指令功能描述为：该指令功能描述为：boolean Test_and_Set（boolean&target）Boolean rv=target;Target=true；Return rv如果机器支持如果机器支持Test_and_Set，可用下列方法解决，可用下列方法解决：(Lock=false)do while（Test_and_Set(&lock)）;/进入区进入区 critical section;/临界区临界区 lock=false;/退出区退出区 non critical section;/其它部分其它部分while（1）;27二、二、“Swap”指令指令该指令功能描述为：该指令功能描述为：void Swap（boolean&a,boolean&b）boolean temp=a；a=b；b=temp；28设设LockLock为全局布尔变量（初值为为全局布尔变量（初值为falsefalse），），每个进程设一个局部布尔变量每个进程设一个局部布尔变量KeyKey。利用。利用SwapSwap指令，可实现对临界区的加锁与解锁。指令，可实现对临界区的加锁与解锁。do key=true;while(key=ture)Swap(Lock,key);critical section Lock=false;non-critical sectionwhile(1)294.2.3 4.2.3 信号量信号量(1965(1965年，年，DijkstraDijkstra提出提出)信号量机构：信号量机构：“信号量信号量”、“P P，V V操作操作”。信号量信号量S S为一整型变量：为一整型变量：P(S):While S0P(S):While S0；S=S-1S=S-1；V V（S S）：）：S=SS=S1 1；P,VP,V操作是两条原语，即保证操作是两条原语，即保证P P，V V操作对变量操作对变量S S的访问是互斥操作。的访问是互斥操作。301.1.原语概念与实现原语概念与实现 原语原语：指完成某种功能且不被分割或不被中断：指完成某种功能且不被分割或不被中断执行的操作序列执行的操作序列(又称原子操作又称原子操作)。实现临界段的元方法实现临界段的元方法:屏蔽中断屏蔽中断(只用于单机只用于单机)；加硬锁加硬锁,如如“Test_and_SetTest_and_Set”，“SwapSwap”硬指令。硬指令。P,VP,V操作的实现操作的实现31P(s)，V(s)的实现的实现P(s)disableIntrrupt();While(s0)enableIntrrupt();disableIntrrupt();s=s-1;enableIntrrupt();V(s)disableIntrrupt();s=s+1;enableIntrrupt();32实现信号量时与进程调度相结合，消除忙等待现实现信号量时与进程调度相结合，消除忙等待现象。象。基本思想是：基本思想是：在在P P操作循环等待的地方加入放弃处理机，进入操作循环等待的地方加入放弃处理机，进入等待队列动作；等待队列动作；在在V V操作时，从等待队列中摘取进程变为就绪态。操作时，从等待队列中摘取进程变为就绪态。2.信号量的具体实现331.信号量定义信号量定义 typedef struct int:value;一个数型变量一个数型变量 struct process*L;一个一个PCB队列队列 SemaphoreSemaphore S;2.P操作操作 P(S):S.Value=S.value1;if S.value0 then 保存现场，保存现场，将本进程挂入将本进程挂入S.L队列，等待重新调度。队列，等待重新调度。3.V操作操作 V(S):S.value:=value+1 if S.value0 then 从从S.L队列队列 取一进程，挂入就绪队列。取一进程，挂入就绪队列。4.P,V操作的优点：操作的优点：同步能力强同步能力强5.P,V操作的缺点：操作的缺点：程序结构差，易产生死锁。程序结构差，易产生死锁。34信号量的物理意义信号量的物理意义n P(s)操作：操作：请求分配一个请求分配一个S代表代表的资源，执行的资源，执行S.value-1；若若S.value0，表示系统已无该类资源，申请表示系统已无该类资源，申请者阻塞。此时，者阻塞。此时，|S.value|表示该信号量上阻塞表示该信号量上阻塞的进程数；的进程数；nV(s)操作：操作：进程释放一个进程释放一个S代表代表的资源，执行的资源，执行S.value+1；若若S.value=1)Xi=Xi-1;Ri=Xi;输出一张机票；输出一张机票；else 输出机票已售完；输出机票已售完；38n存在的问题：存在的问题：1）存在几个旅客几乎同时在不同的售票处要求订购同天同）存在几个旅客几乎同时在不同的售票处要求订购同天同一次航班的可能。一次航班的可能。2）几个进程都要访问票务中心的共享变量）几个进程都要访问票务中心的共享变量Ri，可能出现这，可能出现这样的执行顺序：样的执行顺序：第第i个售票处的售票进程个售票处的售票进程pi刚刚取出刚刚取出Ri，执行执行Xi=Ri；第第j个售票处的售票进程个售票处的售票进程pj马上执行马上执行Xj=Xj-1;Ri=Xj；pi再执行再执行Xi=Xi-1;Ri=Xi。产生的错误：产生的错误：pi，pj都售出了一张机票，但票务中心记录机票都售出了一张机票，但票务中心记录机票余额的变量余额的变量Ri却只减了却只减了1。39semaphore mutex;mutex=1;pi()接受旅客订票要求；接受旅客订票要求；P(mutex);Xi=Ri ;/将票务中心该次航班的余票将票务中心该次航班的余票Ri取出送该进取出送该进 /程工作单元程工作单元Xi if(Xi=1)Xi=Xi-1;Ri=Xi;V(mutex);输出一张机票输出一张机票;else V(mutex);输出机票已售完输出机票已售完;n解决办法解决办法40n同步模型：同步模型：假设有两个协作的并发进程假设有两个协作的并发进程P1，P2，S1是是P1中的一段代码，中的一段代码，S2是是P2中的一段代码，只有中的一段代码，只有P1中的中的S1执执行完后行完后P2中的中的S2才能开始执行才能开始执行n实现方法：实现方法：利用信号量的同步原语利用信号量的同步原语P可以实现可以实现P1向向P2发送发送消息，用消息，用V来测试来测试P1的消息是否到达。设的消息是否到达。设synch是实现同是实现同步的信号量，初值为步的信号量，初值为0，则两个进程的同步可以描述为：，则两个进程的同步可以描述为：4.4.利用信号量实现进程同步利用信号量实现进程同步Parbegin P2:P1:S1;V(synch);P(synch);S2;Parend;41启动汽车启动汽车正常开车正常开车到站停车到站停车开车门开车门乘客上下车乘客上下车关车门关车门司机和售票员同步示意图司机和售票员同步示意图 售车票售车票司机司机售票员售票员stopclose利用信号量实现进程同步的例子利用信号量实现进程同步的例子n 现实例子：现实例子：42设置信号量设置信号量closeclose表示车门是否关好，初值为表示车门是否关好，初值为0 0，表示门未关好，不允许司机启动汽车；设置信号表示门未关好，不允许司机启动汽车；设置信号量量stopstop表示汽车是否停稳，初值为表示汽车是否停稳，初值为0 0，表示未停，表示未停稳，售票员不能开车门。稳，售票员不能开车门。Semaphore stop=0,close=0;Semaphore stop=0,close=0;Driver()Driver()P(close);/P(close);/车门是否关好车门是否关好 启动汽车启动汽车 正常开车正常开车 到站停车到站停车 V(stop);/V(stop);/发送开门信息发送开门信息 n 实现方法：实现方法：busman()busman()关车门；关车门；V(close);/V(close);/发送已关门信息发送已关门信息售车票；售车票；P(stop);/P(stop);/测试是否停车测试是否停车开车门；开车门；乘客上下车；乘客上下车；43 首首先先要要分分析析清清楚楚进进程程间间的的同同步步关关系系，即即它它们们之之间间交交换换信信息息的的位位置置以以及及个个数数，每每一一个个同同步步关关系用一个信号量来表示。系用一个信号量来表示。其次是要注意信号量的初值以及意义。其次是要注意信号量的初值以及意义。1 1）P P操作用来测试等待的信息是否到达；操作用来测试等待的信息是否到达；2 2）V V操作来向其它需要同步的进程发送信息。操作来向其它需要同步的进程发送信息。解决进程同步问题时关键：解决进程同步问题时关键：44一般地，定义一般地，定义n个信号量来描述有个信号量来描述有n条条边的前趋图，边的前趋图，初值都设为初值都设为0。例如：右图的前趋关系可描述如下：。例如：右图的前趋关系可描述如下：5.5.利用信号量描述前趋关系利用信号量描述前趋关系S1S3S4S2aecbdsemaphore a=0,b=0,c=0,d=0,e=0;P1()S1;V(a);V(b);P2()P(a);S2;V(c);V(d);P3()P(b);P(c);S3;V(e);P4()P(d);P(e);S4;454.2.44.2.4进程同步与互斥举例进程同步与互斥举例三个经典的进程同步问题：三个经典的进程同步问题：1、有限缓冲区问题（生产者、有限缓冲区问题（生产者-消费者问题）；消费者问题）；(The Producer-Consumer Problem)2、读者、读者-写者问题；写者问题；(The Read/Write Problem)3、哲学家就餐问题；、哲学家就餐问题；(The Dining Philosophers Problem)461.1.有限缓冲区问题有限缓冲区问题 有限缓冲区的生产者有限缓冲区的生产者/消费者问题（生产者和消费者共享消费者问题（生产者和消费者共享一个产品缓冲池）。一个产品缓冲池）。说明：说明：将缓冲池看做是共享数据，对缓冲区的操作必须是互斥将缓冲池看做是共享数据，对缓冲区的操作必须是互斥操作。操作。如果如果n n个缓冲区全满，生产者进程必须等待。个缓冲区全满，生产者进程必须等待。如果缓冲区全空，消费者进程必须等待。如果缓冲区全空，消费者进程必须等待。共享共享n个缓冲区个缓冲区P1 P2 Pm 生生产产者者消消费费者者缓冲池缓冲池C1 C2 Cn47解：解：设置以下信号量设置以下信号量mutex,初值为初值为1，控制互斥访问缓冲池。，控制互斥访问缓冲池。full,初值为初值为0，表示当前缓冲池中满缓冲区，表示当前缓冲池中满缓冲区数，用于同步。数，用于同步。empty,初值为初值为n，表示当前缓冲池中空缓冲，表示当前缓冲池中空缓冲区数，用于同步。区数，用于同步。有限缓冲区生产者有限缓冲区生产者/消费者进程描述如下：消费者进程描述如下：typedef struct item;typedef struct struct item inst;Struct buffer*next;buffer;48 P(empty);P(mutex);add nextp to buffer;V(mutex);V(full);while(1);semaphor full,empty,mutex;struct item nextp,nextc;full:=0;empty:=n;mutex:=1;Producer:do produce an item in nextp;.互互斥斥49 consume the item in nextc;while(1);consumer:do P(full);P(mutex);remove an item from buffer to nextc 释放缓冲区释放缓冲区 V(mutex);V(empty);互互斥斥50补充：理发师睡觉问题补充：理发师睡觉问题 理发店由等待间（理发店由等待间（N个座位）和理发间个座位）和理发间（一个理发椅）构成。无顾客时，理发师睡觉；（一个理发椅）构成。无顾客时，理发师睡觉；当顾客进入理发店发现理发师睡觉时，则唤醒当顾客进入理发店发现理发师睡觉时，则唤醒理发师。理发师。请写出模拟理发师和顾客的算法。请写出模拟理发师和顾客的算法。N个座位个座位理发椅理发椅51理发师睡觉问题算法理发师睡觉问题算法Semphore seatempty=N,seatfull=0,chair=1,mutex=1;Conmuser()Conmuser()do P(seatempty);P(mutex);find a seat;V(mutex);V(seatfull);while(1);Server()Server()do P(seatfull);P(chair);enter into room V(seatempty);cutting;V(chair);while(1);补充作业补充作业52课堂作业：课堂作业：假设有三个并发进程假设有三个并发进程P、Q、R。其中。其中P负责从负责从输入设备上读入信息并传给输入设备上读入信息并传给Q；Q将信息加工后传将信息加工后传给给R；R则负责将信息打印输出。则负责将信息打印输出。设：设：P、Q共享共享1个缓冲区，个缓冲区，Q、R共享另一个缓冲共享另一个缓冲区；区；若一个缓冲区可保存一个数据信息，请写出若一个缓冲区可保存一个数据信息，请写出P、Q、R的并发算法。的并发算法。PQR53 若存在一共享数据若存在一共享数据A，那些对它进行读访问者，那些对它进行读访问者叫叫Reader，对它进行写访问者叫做，对它进行写访问者叫做Writer。Reader/Writer问题：问题：保证任何一个保证任何一个Writer进进程与其他进程互斥访问共享数据。程与其他进程互斥访问共享数据。第一类第一类Reader/Writer问题：问题：Reader和和Writer争夺访问共享数据争夺访问共享数据A时，时，Reader有较高优先权。有较高优先权。2.Readers/Writers问题问题数据数据54 该问题可具体描述为：该问题可具体描述为：1.如果当前无进程访问数据，则如果当前无进程访问数据，则Reader/Writer欲访问即可欲访问即可访问。访问。2.如果已存在一个如果已存在一个Reader正在访问数据，其他欲访问正在访问数据，其他欲访问Reader可马上访问；而欲访问的可马上访问；而欲访问的Writer无条件等待。无条件等待。3.若某个若某个Writer正访问数据，则欲访问的正访问数据，则欲访问的Reader或或 Writer都必须等待。都必须等待。4.当最后一个结束访问数据的当最后一个结束访问数据的Reader发现有发现有Writer正在等正在等待时，则将其中一个唤醒。待时，则将其中一个唤醒。5.当某个当某个Writer结束访问时，若只有结束访问时，若只有Writer在等待，则唤醒在等待，则唤醒某个某个Writer，若既有，若既有Writer也有也有Reader；则按；则按FIFO或某它或某它原则唤醒一个原则唤醒一个Writer或所有或所有Reader。55mutex，wrt为信号量，初值为为信号量，初值为1；readcount用于记录当前有多少个用于记录当前有多少个Reader正在访问数据，正在访问数据，初始值为初始值为0。Reader的一般结构为：的一般结构为：P(mutex)；readcount:=readcount+1;if readcount=1 P(wrt);V(mutex)；读数据读数据AP(mutex)；readcount:=readcount-1;if readcount=0 V(wrt);V(mutex);Writer的一般结构为：的一般结构为：P(wrt);写数据写数据AV(wrt);563.哲学家就餐问题哲学家就餐问题 问题描述：问题描述：吃饭程序是：先取左边筷子，后取右边筷子，再吃饭程序是：先取左边筷子，后取右边筷子，再吃饭，再放筷子。吃饭，再放筷子。57实现方法：实现方法：为每个筷子设一把锁（信号量，初值为每个筷子设一把锁（信号量，初值为为1）每个哲学家是一个进程。共享数据结构为：）每个哲学家是一个进程。共享数据结构为：semaphore Chopstick5;/初始值均为初始值均为1 第第i个进程描述为个进程描述为(i=0,4)do P(chopsticki);取左边筷子取左边筷子 P(chopstick(i+1)mod 5)；取右边筷子取右边筷子 吃吃 放左边筷子放左边筷子 V(chopsticki);放右边筷子放右边筷子 V(Chopstick(i+1)mod 5；思考思考 while(1);(这可能导致死锁这可能导致死锁)58用以下几种方法来解决上面的死锁问题：用以下几种方法来解决上面的死锁问题：(1)至至多多只只允允许许有有四四位位哲哲学学家家同同时时去去拿拿左左边边的筷子；的筷子；(2)仅仅当当哲哲学学家家的的左左、右右两两支支筷筷子子均均可可用用时时，才允许他拿起筷子进餐；才允许他拿起筷子进餐；(3)规规定定奇奇数数号号哲哲学学家家先先拿拿他他左左边边的的筷筷子子，然然后后再再去去拿拿右右边边的的筷筷子子；而而偶偶数数号号哲哲学学家则相反。家则相反。59 用用第第一一种种方方法法来来实实现现没没有有死死锁锁的的哲哲学学家家问题：问题：至至多多只只允允许许有有四四位位哲哲学学家家同同时时去去拿拿左左边边的的筷筷子子，最最终终能能保保证证至至少少有有一一位位哲哲学学家家能能够够进进餐餐，并并在在用用毕毕时时能能放放下下他他用用过过的的两两支支筷子，从而使其他的哲学家能够进餐。筷子，从而使其他的哲学家能够进餐。在在实实现现时时只只需需增增加加一一个个限限定定就就餐餐人人数数的的信信号号量量num，其其初初值值设设为为4。任任何何哲哲学学家家拿拿筷子前先检测筷子前先检测num，算法如下：，算法如下：60semaphore num=4,chopstick5=1，1，1，1，1；Philosopher i()do think;P(num);P(chopsticki);P(chopstick(i+1)%5);吃吃;V(num);V(chopsticki);V(chopstick(i+1)%5);while(1);614.3 4.3 消息传递原理消息传递原理 三种基本进程通信方法：三种基本进程通信方法：1.共享存储（共享存储（Shared-memory）通信方式通信方式p1p2p3p4共享存储区共享存储区n需要解决两个问题：需要解决两个问题：1 1）怎样提供共享内存）怎样提供共享内存2 2）共享内存的读写互斥）共享内存的读写互斥622 管道通信管道通信管道通信是一种重要的通信方式。管道通信是一种重要的通信方式。特点：特点：特点：特点：同步与互斥都由系统自动进行，对用户是透明的。同步与互斥都由系统自动进行，对用户是透明的。具有传送数据量大的优点，但通信速度较慢。具有传送数据量大的优点，但通信速度较慢。3.消息传递消息传递(message-passing)利用原语利用原语Send()和和Receive()进行数据交换进行数据交换管管 道道p1p2p3p463 消息传递原语的一般形式消息传递原语的一般形式:发送：发送：Send(destination,&message)接收：接收：Receive(source,&message)1.1.消息传递方法消息传递方法 1）直接通信法）直接通信法 基本思想：基本思想：进程在发送和接收消息时直接指明进程在发送和接收消息时直接指明接收者或发送者进程接收者或发送者进程ID。缺点：缺点：必须指定接收进程必须指定接收进程ID（UNIX的信号机制的信号机制类似这种形式）。类似这种形式）。4.3.1 4.3.1 消息传递通信原理消息传递通信原理64举例：（举例：（UNIX中两进程利用信号通信）。中两进程利用信号通信）。Process A kill(1040,SIGUSR1);#向向1040号进程发送号进程发送 一个一个SIGUSR1信号。信号。Process B Signal(SIGUSR1,func);#当收到当收到SIGUSR1信信 号时，就执行号时，就执行func(),如果如果SIGUSR1 信号未到，则系统登记信号未到，则系统登记func函数，函数，待其信号到时再调用执行。待其信号到时再调用执行。652 2）间接通信法）间接通信法基本思想：基本思想：系统为每个参与者设立一个逻辑实体，系统为每个参与者设立一个逻辑实体，如信箱，消息发送和接收都指向该信箱。如信箱，消息发送和接收都指向该信箱。特点特点：必须有一个通信双方共享的一个逻辑实体必须有一个通信双方共享的一个逻辑实体 逻辑实体是一个中介实体逻辑实体是一个中介实体 66 虚拟的通信链：虚拟的通信链：在通信发送者和接收者之间存在一条逻辑通信在通信发送者和接收者之间存在一条逻辑通信链，链，链的容量链的容量是指该链暂存消息的能力。是指该链暂存消息的能力。在接收