《{通信公司管理}4进程的同步与通信,进程死锁》由会员分享，可在线阅读，更多相关《{通信公司管理}4进程的同步与通信,进程死锁（73页珍藏版）》请在金锄头文库上搜索。
1、1,第4章 进程的同步与通信、进程死锁,主要内容：并发执行，临界段，信号量，经典进程同步问题，消息传递原理，死锁。 重点：临界段、同步、互斥的概念；信号量的概念和物理意义；消息传递的原理，死锁的概念。 难点：信号量解决进程同步与互斥的方法，死锁防止、避免。,计算机操作系统,前趋图：用于描述一个程序的各部分（程序段或语句）间的执行顺序关系，或者是一个大的计算各子任务间的因果关系。 1）是一个有向无循环图； 2）图的结点对应程序中的一条语句、 一个程序段或一个进程； 3）结点间的有向边：表示两个结点之 间存在的偏序或前趋关系 “”；,1. 程序的顺序执行,计算机操作系统,指各程序段按照某种先后次序
2、执行，仅当前一个操作执行完后才能执行后继操作。,1. 程序的顺序执行,其中I、C、P分别表示输入、计算和打印操作,图3-2 程序顺序执行时的前趋图,顺序执行的特点：顺序性，封闭性，可再现性,计算机操作系统,概念：若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的，一个程序（或程序段）的执行尚未结束，另一个程序（或程序段）的执行已经开始。,2. 程序的并发执行,若顺序执行三个作业共需要9（3*3）分钟 并行执行三个作业只需要5（5/3*3）分钟,计算机操作系统,间断性：并发程序由于共享资源或为完成同一项任务而相互合作，形成相互制约关系。,程序并发执行的特点：,失去
3、封闭性：多个程序共享系统中的各种资源，资源的状态将由多个程序改变，失去封闭性。一个程序执行时，会受到其他程序的影响。,不可再现性（待续）,并发与共享的问题：并行程序访问共享数据问题举例:(count为共享变量初值=300),Program A: N=count N=N+100 count=N ,Program B: M=count M=M-200 count=M ,如果按以下次序占处理机运行:,N=count,N=N+100; M=count,M=M-200,count=M; count=N. 结果count=400(应为200)*,7,并发的需要 操作系统应尽量支持用户态程序最大限度地并发执
4、行。 程序设计要利用OS对并发运行的支持，安排事务并发执行。 操作系统核心程序也要尽可能地并发运行,4.1 并发执行实现,S1,S2,S3,图4.1 任务中子任务关系示意图,8,4.1.1 并发编程方法,传统的串行程序存在着并行成分： Read (a)； Read (b)； c = a + b； Write (c),Read（a）和Read（b）两个语句可并行执行。,9,识别程序中的并发成分有两种方法： 程序员写顺序程序，用识别工具识别并发成分。再组织使用操作系统的并发机制。 由程序员识别并发成分: 用并发程序设计语言设计并发程序， 由编译系统安排并发； 直接利用操作系统的系统调用。,10,并
5、发程序设计语言 - 并发语句,它是一种高级语言； 语法形式： Parbegin S1；S2； Sn； Parend；,1）并发语句示例 1 Parbegin read（a）； read（b）； Parend； c= a+b； write（c）；,11,2）并发语句示例2 Var F,G:file of T; r,s:T; reset(F); read(F,r); while not eof(F) do s=r; Parbegin write(G,s); read(F,r); Parend; write(G,r); ,优点: 并发语句的结构化特征非常好。 缺点： 存在着描述能力不强的缺点，即存在
6、着用Parbegin/Parend语句无法描述的并发优先关系。 改进手段： 辅以其他手段，则并发语句可以大大增加其描述并发的能力。,12,4.1.2并发执行的实现,前面是对并发的高级语言描述，要真正实现并发执行，需要通过OS支持的进程机制。 实现的两种方法： 1) OS提供进程创建，结束和同步的系统调用； 2) 由并行语言编译器将并发语言的语句转化为对OS的系统调用。,13,与进程相关的系统调用,UNIX操作系统利用进程支持并发执行； 它提供了如下系统调用： fork（）：创建一个新进程。 (1) 该子进程继承了父进程的程序空间，复制了父进程的数据段和栈段。也就是说不管是父进程还是子进程，在占
7、有处理机后，都从fork（）调用的返回点开始运行; (2) 父进程fork（）调用的返回值是子进程的进程标识pid； (3) 子进程fork（）调用的返回值是0。,14,exit（status）：进程结束。该系统调用发出后，操作系统将从系统中删除调用exit的进程，并将status值传给等待它结束的父进程。 wait（ /进入区 critical code; /临界段 exit code; /退出区 remainder code;/剩余区 ；,22,例2： P1,P2两进程使用同一打印机。如果不互斥使用会交叉输出。,Entry code,exit code,使用打印机,P1,Entry cod
8、e,exit code,使用打印机,P2,23,例3: 对共享变量count的互斥访问。,Parbegin P1: M:=count; M:=M+1; count:= M; P2: N:=count; N:=N+2; count:=N; Parend;,Entry code,exit code,Entry code,exit code,24,如何实现进入区、退出区代码同步机构,同步机构：指能实现进程同步的机制，该机制能把其它进程需要的信息发送出去，也能测试自己需要的信息是否到达。 同步机构应遵循4个准则：,1、空闲让进；,2、忙则等待；,3、有限等待；,4、让权等待；,实现方法 软件方法 硬件
9、方法,25,4.2.2 实现临界段的硬件方法,与计算机体系结构有关,1、屏蔽中断法 中断引起的并发会导致错误的结果,进程1的程序 disableInterrupt(); Balance=balance+amount; enableInterrupt();,进程2的程序 disableInterrupt(); Balance=balance-amount; enableInterrupt();,两条命令：enableInterrupt，disableInterrupt,缺点： 1）可能影响到I/O行为 2）只能用于单处理机系统,26,2、“Test_and_Set”指令 该指令功能描述为： bo
10、olean Test_and_Set（boolean Target =true； Return rv,如果机器支持Test_and_Set，可用下列方法解决：(Lock=false) do while（Test_and_Set(,27,二、“Swap”指令 该指令功能描述为： void Swap（boolean While(s0) enableIntrrupt(); disableIntrrupt(); s=s-1; enableIntrrupt(); ,V(s) disableIntrrupt(); s=s+1; enableIntrrupt(); ,32,实现信号量时与进程调度相结合，消除
11、忙等待现象。 基本思想是： 在P操作循环等待的地方加入放弃处理机，进入等待队列动作； 在V操作时，从等待队列中摘取进程变为就绪态。,2. 信号量的具体实现,33,1. 信号量定义 typedef struct int:value; 一个数型变量 struct process *L;一个PCB队列 Semaphore Semaphore 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队列
12、取一进程，挂入就绪队列。 4. P,V操作的优点：同步能力强 5. P,V操作的缺点：程序结构差，易产生死锁。,34,信号量的物理意义,P(s)操作： 请求分配一个S代表的资源，执行S.value-1； 若S.value0，表示系统已无该类资源，申请者阻塞。此时， |S.value|表示该信号量上阻塞的进程数；,V(s)操作： 进程释放一个S代表的资源，执行S.value+1； 若S.value=0，表示尚有进程因等待S代表的资源而处于阻塞状态，所以应唤醒其中之一。,35,3. 利用信号量实现进程互斥,使用方法： 1）为每一个共享的临界资源设置一个互斥信号量，其初值为1。 2）各进程在进入临界
13、段前先对该信号量进行P操作，退出临界段后执行V操作，从而保证各进程互斥的进入相关临界段。 注意：对同一信号量操作的P与V操作在进程中必须成对出现。,36,进程 Pi : 信号量 mutex=1,P(mutex),V(mutex),临界段,非临界段,do,While(1),37,例子： 有一飞机机票售票系统，有m个售票处，各售票处通过计算机与该系统的票务中心连网，中心数据区中用Ri代表某天某次航班的余票数。进程pi为第i个售票处为旅客服务的进程，进程功能如下： pi() 接受旅客订票要求； Xi=Ri ; /将票务中心该次航班的余票 /取出送该进程工作单元Xi if (Xi=1) Xi= Xi-
14、1; Ri =Xi; 输出一张机票； else 输出机票已售完； ,38,存在的问题： 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。,39,semaphore mutex; mutex=1; pi() 接受旅客订票要求； P(mutex); Xi=
15、Ri ; /将票务中心该次航班的余票Ri取出送该进 /程工作单元Xi if (Xi=1) Xi= Xi-1; Ri =Xi; V(mutex); 输出一张机票; else V(mutex); 输出机票已售完; ,解决办法,40,同步模型：假设有两个协作的并发进程P1，P2，S1是P1中的一段代码，S2是P2中的一段代码，只有P1中的S1执行完后P2中的S2才能开始执行 实现方法：利用信号量的同步原语P可以实现P1向P2发送消息，用V来测试P1的消息是否到达。设synch是实现同步的信号量，初值为0，则两个进程的同步可以描述为：,4. 利用信号量实现进程同步,Parbegin,P2: ,P1:
16、,S1;,V(synch);,P(synch);,S2;,Parend;,41,利用信号量实现进程同步的例子,现实例子：,42,设置信号量close表示车门是否关好，初值为0，表示门未关好，不允许司机启动汽车；设置信号量stop表示汽车是否停稳，初值为0，表示未停稳，售票员不能开车门。,Semaphore stop=0,close=0; Driver() P(close);/车门是否关好 启动汽车 正常开车 到站停车 V(stop); /发送开门信息 ,实现方法：,busman() 关车门； V(close);/发送已关门信息 售车票； P(stop);/测试是否停车 开车门； 乘客上下车； ,43,首先要分析清楚进程间
