![进程的同步与通信,进程死锁[详细]_第1页](http://file1.renrendoc.com/fileroot_temp2/2020-10/15/4c2dc2ab-4aa0-44b1-9203-7b884575bd6b/4c2dc2ab-4aa0-44b1-9203-7b884575bd6b1.gif)
![进程的同步与通信,进程死锁[详细]_第2页](http://file1.renrendoc.com/fileroot_temp2/2020-10/15/4c2dc2ab-4aa0-44b1-9203-7b884575bd6b/4c2dc2ab-4aa0-44b1-9203-7b884575bd6b2.gif)
![进程的同步与通信,进程死锁[详细]_第3页](http://file1.renrendoc.com/fileroot_temp2/2020-10/15/4c2dc2ab-4aa0-44b1-9203-7b884575bd6b/4c2dc2ab-4aa0-44b1-9203-7b884575bd6b3.gif)
![进程的同步与通信,进程死锁[详细]_第4页](http://file1.renrendoc.com/fileroot_temp2/2020-10/15/4c2dc2ab-4aa0-44b1-9203-7b884575bd6b/4c2dc2ab-4aa0-44b1-9203-7b884575bd6b4.gif)
![进程的同步与通信,进程死锁[详细]_第5页](http://file1.renrendoc.com/fileroot_temp2/2020-10/15/4c2dc2ab-4aa0-44b1-9203-7b884575bd6b/4c2dc2ab-4aa0-44b1-9203-7b884575bd6b5.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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);/测试是否停车 开车门; 乘客上下车;
17、,43,首先要分析清楚进程间的同步关系,即它们之间交换信息的位置以及个数,每一个同步关系用一个信号量来表示。 其次是要注意信号量的初值以及意义。 1)P操作用来测试等待的信息是否到达; 2)V操作来向其它需要同步的进程发送信息。,解决进程同步问题时关键:,44,一般地,定义n个信号量来描述有n条边的前趋图,初值都设为0。例如:右图的前趋关系可描述如下:,5.利用信号量描述前趋关系,semaphore 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
18、() P(d); P(e); S4;,45,4.2.4进程同步与互斥举例,三个经典的进程同步问题: 1、有限缓冲区问题(生产者-消费者问题); (The Producer-Consumer Problem) 2、读者-写者问题; (The Read/Write Problem) 3、哲学家就餐问题; (The Dining Philosophers Problem),46,1.有限缓冲区问题 有限缓冲区的生产者/消费者问题(生产者和消费者共享一个产品缓冲池)。,说明: 将缓冲池看做是共享数据,对缓冲区的操作必须是互斥操作。 如果n个缓冲区全满,生产者进程必须等待。 如果缓冲区全空,消费者进程必
19、须等待。,47,解:设置以下信号量 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,
20、 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个座位)和理发间(一个理发椅)构成。无顾客时,理发师睡觉;当顾客
21、进入理发店发现理发师睡觉时,则唤醒理发师。 请写出模拟理发师和顾客的算法。,51,理发师睡觉问题算法,Semphore seatempty=N,seatfull=0,chair=1,mutex=1;,Conmuser() do P(seatempty); P(mutex); find a seat; V(mutex); V(seatfull); while(1); ,Server() do P(seatfull); P(chair); enter into room V(seatempty); cutting; V(chair); while(1); ,补充作业,52,课堂作业:,假设有三个并
22、发进程P、Q、R。其中P负责从输入设备上读入信息并传给Q;Q将信息加工后传给R;R则负责将信息打印输出。 设:P、Q共享1个缓冲区,Q、R共享另一个缓冲区; 若一个缓冲区可保存一个数据信息,请写出P、Q、R的并发算法。,53,若存在一共享数据A,那些对它进行读访问者叫Reader,对它进行写访问者叫做Writer。 Reader/ Writer问题:保证任何一个Writer进程与其他进程互斥访问共享数据。 第一类Reader/ Writer问题: Reader和Writer争夺访问共享数据A时,Reader有较高优先权。,2. Readers/Writers问题,54,该问题可具体描述为: 1
23、. 如果当前无进程访问数据,则Reader/ Writer欲访问即可访问。 2. 如果已存在一个Reader正在访问数据,其他欲访问Reader可马上访问;而欲访问的Writer无条件等待。 3. 若某个Writer正访问数据,则欲访问的Reader或 Writer都必须等待。 4. 当最后一个结束访问数据的Reader发现有Writer正在等待时,则将其中一个唤醒。 5. 当某个Writer结束访问时,若只有Writer在等待,则唤醒某个Writer,若既有Writer也有Reader;则按FIFO或某它原则唤醒一个Writer或所有Reader。,55,mutex,wrt为信号量,初值为1
24、; readcount用于记录当前有多少个Reader正在访问数据,初始值为0。 Reader的一般结构为: P(mutex); readcount:=readcount+1; if readcount=1 P(wrt); V(mutex); 读数据A P(mutex); readcount:= readcount-1; if readcount=0 V(wrt); V(mutex); Writer的一般结构为: P(wrt); 写数据A V(wrt);,56,3. 哲学家就餐问题 问题描述:,吃饭程序是:先取左边筷子,后取右边筷子,再吃饭,再放筷子。,57,实现方法:为每个筷子设一把锁(信号
25、量,初值为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,用以下几种方法来解决上面的死锁问题: 至多只允许有四位哲学家同时去拿左边的筷子; 仅当哲学家的左、右两支筷子均可用时,才允许他拿起筷子进餐; 规定奇数号哲学家先拿他左边的筷子,然后再去拿
26、右边的筷子;而偶数号哲学家则相反。,59,用第一种方法来实现没有死锁的哲学家问题: 至多只允许有四位哲学家同时去拿左边的筷子,最终能保证至少有一位哲学家能够进餐,并在用毕时能放下他用过的两支筷子,从而使其他的哲学家能够进餐。 在实现时只需增加一个限定就餐人数的信号量num,其初值设为4。任何哲学家拿筷子前先检测num,算法如下:,60,semaphore 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 ); ,61,4.3 消息传递原理 三种基本进程通信方法: 1.共享存储(Shared-memory),通信方式,p1,p2,p3,p4,共享存储区,需要解决两个问题: 1)怎样提供共享内存 2)共享内存的读写互斥,62,2 管道通信,管道通信是一种重要的通信方式。 特点: 同步与互斥都由系统自动进行,对用户是透明的。 具有传送数据量大的优点,但通信速度较慢。 3.消息传递(message-pas
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年南宁市滨江路幼儿园招聘考试笔试试卷附答案
- 2024年湖南省桂阳县邮政公开招聘工作人员试题带答案详解
- 二房东房屋租赁中介服务合同样本
- 生态农业园区设计合同执行细则
- 2024年河南省宁陵县邮政公开招聘工作人员试题带答案详解
- 租赁买卖车辆协议书范本
- 房间纱窗购买协议书范本
- 承诺金协议书范本
- 退出装修合同协议书范本
- 会员分红协议书范本
- 老旧住宅小区综合整治装饰装修工程施工方案
- 基于单元主题的小学英语跨学科学习活动的实践与研究
- 实验室生物安全手册
- 全新退换货协议模板
- 危重患者的早期识别与处理
- (正式版)JBT 14449-2024 起重机械焊接工艺评定
- 商务礼仪之座次及用餐
- SEO谷歌推广方案
- 注塑标准成型条件表电子表格模板
- 企业数字化管理
- 道闸系统施工方案
评论
0/150
提交评论