计算机操作系统-进程同步与通信.ppt
《计算机操作系统-进程同步与通信.ppt》由会员分享,可在线阅读,更多相关《计算机操作系统-进程同步与通信.ppt(79页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、计算机操作系统计算机操作系统计算机操作系统计算机操作系统第三章第三章第三章第三章 进程同步与通信进程同步与通信进程同步与通信进程同步与通信计算机信息工程学院主讲教师主讲教师 王帅强王帅强http:/ 3.1 进程互斥和同步进程互斥和同步3.1.1 3.1.1 互斥算法互斥算法3.1.2 3.1.2 信号量信号量(semaphore)(semaphore)3.1.3 3.1.3 经典进程同步问题经典进程同步问题3.1.4 3.1.4 管程管程(monitor)(monitor)返回v在多道程序系统中,由于资源共享和进程合作,使各在多道程序系统中,由于资源共享和进程合作,使各进程之间存在两种类型的
2、制约关系:进程之间存在两种类型的制约关系:(1 1)间接制约关系(互斥)间接制约关系(互斥)(2 2)直接制约关系(同步)直接制约关系(同步)v进程同步指多个相关进程在执行次序上的协调,用于进程同步指多个相关进程在执行次序上的协调,用于保证这种关系的保证这种关系的 相应机制称为进程同步机制相应机制称为进程同步机制v互斥指进程之间竞争使用某种资源互斥指进程之间竞争使用某种资源进程同步与互斥进程同步与互斥 3.1.1 3.1.1 互斥算法互斥算法3.1.1.13.1.1.1临界资源临界资源3.1.1.23.1.1.2临界区的访问过程临界区的访问过程3.1.1.33.1.1.3同步机制应遵循的准则同
3、步机制应遵循的准则3.1.1.43.1.1.4进程互斥的硬件方法进程互斥的硬件方法3.1.1.13.1.1.1临界资源临界资源v进程间资源访问冲突进程间资源访问冲突共享变量的修改冲突操作顺序冲突v进程间的制约关系进程间的制约关系间接制约:进行竞争独占分配到的部分或全部共享资源,“互斥”直接制约:进行协作等待来自其他进程的信息,“同步”硬件或软件(如外设、共享代码段、共享数据结构),多个进硬件或软件(如外设、共享代码段、共享数据结构),多个进程在对其进行访问时(关键是进行写入或修改),必须互斥地程在对其进行访问时(关键是进行写入或修改),必须互斥地进行有些共享资源可以同时访问,如只读数据进行有些
4、共享资源可以同时访问,如只读数据多道程序环境多道程序环境 进程之间存在资源共享,进程的运行时间受影响进程之间存在资源共享,进程的运行时间受影响举例举例1 1:共享变量的修改冲突:共享变量的修改冲突举例举例2:竞争条件:竞争条件Race Conditionvcount+could be implemented as register1=count register1=register1+1 count=register1vcount-could be implemented as register2=count register2=register2-1 count=v假定初始状态下假定初始状态
5、下count=5 S0:producer execute register1=count register1=5S1:producer execute register1=register1+1 register1=6 S2:consumer execute register2=count register2=5 S3:consumer execute register2=register2-1 register2=4 S4:producer execute count=register1 count=6 S5:consumer execute count=register2 count=4c
6、ount-register2=count register2=register2-1 count=register2count+register1=count register1=register1+1 count=register1假设有两个进程假设有两个进程producer:producer:做做count+count+,进程,进程consumerconsumer做做countcount且两个进程并发执行。且两个进程并发执行。竞争条件竞争条件race conditionv多个进程并发访问和操作同一数据且执行结果与多个进程并发访问和操作同一数据且执行结果与特定访问顺序有关,称为竞争条件。特定
7、访问顺序有关,称为竞争条件。v如何防止出现竞争条件?如何防止出现竞争条件?同步同步举例举例3 操作顺序冲突操作顺序冲突有有3 3个进程:个进程:get,copyget,copy和和putput,它们对它们对4 4个存储区域个存储区域f f、s s、t t和和g g进行操作。进行操作。有有6 6种可能的操作顺序,只有一种结果是正确的。种可能的操作顺序,只有一种结果是正确的。进程的交互关系:可以按照相互感知的程度来分类进程的交互关系:可以按照相互感知的程度来分类互斥,指多个进程不能同时使用同一个资源;互斥,指多个进程不能同时使用同一个资源;死锁,指多个进程互不相让,都得不到足够的资源;死锁,指多个
8、进程互不相让,都得不到足够的资源;饥饿,指一个进程一直得不到资源(其他进程可能轮流占用资源)饥饿,指一个进程一直得不到资源(其他进程可能轮流占用资源)3.1.1.2 3.1.1.2 临界区的访问过程临界区的访问过程临界区v临界区临界区(critical section)(critical section):进程中访问临界资源的一段进程中访问临界资源的一段代码。代码。v进入区进入区(entry section)(entry section):在进入临界区之前,检查可否在进入临界区之前,检查可否进入临界区的一段代码。如果可以进入临界区,通常设置进入临界区的一段代码。如果可以进入临界区,通常设置相应
9、相应 正在访问临界区正在访问临界区 标志标志v退出区退出区(exit section)(exit section):用于将用于将 正在访问临界区正在访问临界区 标志清标志清除。除。v剩余区剩余区(remainder section)(remainder section):代码中的其余部分。代码中的其余部分。临界区临界区3.1.1.3 3.1.1.3 同步机制应遵循的准则同步机制应遵循的准则v空闲则入:其他进程均不处于临界区;空闲则入:其他进程均不处于临界区;v忙则等待:已有进程处于其临界区;忙则等待:已有进程处于其临界区;v有限等待:等待进入临界区的进程不能有限等待:等待进入临界区的进程不能死
10、等死等;v让权等待:不能进入临界区的进程,应释放让权等待:不能进入临界区的进程,应释放CPU(如转换到阻塞状态)如转换到阻塞状态)3.1.1.4 3.1.1.4 进程互斥的硬件方法进程互斥的硬件方法在许多机器中,都提供了专门的硬件指令在许多机器中,都提供了专门的硬件指令Test and Set,它可以用做解决它可以用做解决临界区问题。临界区问题。Test-and-Set指令指令该指令读出标志后设置为该指令读出标志后设置为TRUETRUEbooleanboolean TS(varTS(var lock lock boolean):booleanboolean):booleanbeginbegin
11、 tsts:=lock;:=lock;lock=TRUE;lock=TRUE;end endlocklock表示资源的两种状态:表示资源的两种状态:TRUETRUE表示正被占用,表示正被占用,FALSEFALSE表示空闲表示空闲利用利用TSTS实现进程互斥实现进程互斥v利用利用TSTS实现进程互斥:每个临界资源设置一个公共布尔变量实现进程互斥:每个临界资源设置一个公共布尔变量locklock,初值为初值为FALSEFALSEv在进入区利用在进入区利用TSTS进行检查:有进程在临界区时,重复检查;直到进行检查:有进程在临界区时,重复检查;直到其它进程退出时,检查通过;其它进程退出时,检查通过;W
12、hile TS(Lock)Do skip;Critical section;Lock:=false;Remainder section;Until v硬件方法的优点硬件方法的优点适用于任意数目的进程,在单处理器或多处理器上简单,容易验证其正确性可以支持进程内存在多个临界区,只需为每个临界区设立一个布尔变量v硬件方法的缺点硬件方法的缺点等待要耗费CPU时间,不能实现让权等待可能饥饿:从等待进程中随机选择一个进入临界区,有的进程可能一直选不上可能死锁3.1.1.43.1.1.4进程互斥的硬件方法进程互斥的硬件方法3.1.2 信号量信号量(semaphore)3.1.2.1 信号量和信号量和P、V原
13、语原语3.1.2.2 信号量集信号量集 前面的互斥算法是平等进程间的一种协商机制,前面的互斥算法是平等进程间的一种协商机制,OSOS可从进程管理者的角度来处理互斥的问题,信号量可从进程管理者的角度来处理互斥的问题,信号量就是就是OSOS提供的管理公有资源的有效手段。提供的管理公有资源的有效手段。信号量代表可用资源实体的数量。信号量代表可用资源实体的数量。3.1.2.1 信号量和信号量和P、V原语原语v1965年,由荷兰学者年,由荷兰学者Dijkstra提出是一种卓有成效的进程提出是一种卓有成效的进程同步机制。同步机制。v每个信号量每个信号量 s 除一个整数值除一个整数值s.value(计数)外
14、,还有一个计数)外,还有一个进程等待队列进程等待队列 s.queue,其中是阻塞在该信号量的各个进程其中是阻塞在该信号量的各个进程的标识的标识信号量只能通过初始化和两个标准的原语来访问作为OS核心代码执行,不受进程调度的打断初始化指定一个非负整数值,表示空闲资源总数(又称为资源信号量)若为非负值表示当前的空闲资源数,若为负值其绝对值表示当前等待临界区的进程数信号量数据结构的定义信号量数据结构的定义Type semaphore=record value:integer;L:list of process;end (类类pascal语言语言)或或typedef struct int value;s
15、truct process*;semaphore;(语言)(语言)1.P原语原语wait(s)Procedure wait(s)var s:semaphore;begin s.value:=s.value-1;/表示申请一个资源表示申请一个资源;if(s.value 0)then/表示没有空闲资源表示没有空闲资源;begin 调用进程进入等待队列调用进程进入等待队列s.;阻塞调用进程阻塞调用进程;end;2.V原语原语signal(s)Procedure signal(s)var s:semaphore;begin s.value:=s.value+1;/表示释放一个资源;表示释放一个资源;i
16、f(s.value=1 and S2=1 and and Sn=1)/满足资源要求时的处理;满足资源要求时的处理;for i=1 to n do Si=Si-1;/注:与注:与wait的处理不同,这里是在确信可满足的处理不同,这里是在确信可满足 /资源要求时,才进行减资源要求时,才进行减1操作;操作;endfor;else/某些资源不够时的处理;某些资源不够时的处理;调用进程进入第一个小于调用进程进入第一个小于1信号量的等待队列信号量的等待队列Sj.;阻塞调用进程阻塞调用进程; Ssignal(S1,S2,Sn)for i=1 to n do Si:=Si+1;/释放占用的资源;释放占用的资源
17、;for(each process P waiting in Si.)/检查每种资源的等待队列的所有进程;检查每种资源的等待队列的所有进程;从等待队列从等待队列Si.中取出进程中取出进程P;if(判断进程判断进程P是否通过是否通过Swait中的测试中的测试)/注:与注:与signal不同,这里要进行重新判断;不同,这里要进行重新判断;begin/通过检查(资源够用)时的处理;通过检查(资源够用)时的处理;进程进程P进入就绪队列进入就绪队列;end else /未通过检查(资源不够用)时的处理;未通过检查(资源不够用)时的处理;进程进程P进入某等待队列;进入某等待队列;endif endfore
18、ndfor 2.一般一般“信号量集信号量集”v一次需要一次需要N N个某类临界资源时,就要进行个某类临界资源时,就要进行N N次次waitwait操作低效又可能死锁操作低效又可能死锁v基本思想:在基本思想:在ANDAND型信号量集的基础上进行扩充:进程对信号量型信号量集的基础上进行扩充:进程对信号量SiSi的测试的测试值为值为titi(用于信号量的判断,即用于信号量的判断,即Si=Si=titi,表示资源数量低于表示资源数量低于titi时,便不时,便不予分配),占用值为予分配),占用值为didi(用于信号量的增减,即用于信号量的增减,即Si=Si=SiSi-didi和和Si=Si=SiSi +
19、didi)vSwait(S1,t1,d1;.;Swait(S1,t1,d1;.;SnSn,tntn,dndn););vSsignal(S1,d1;.;Ssignal(S1,d1;.;SnSn,dndn););一般信号量集用于同时需要多种资源、每种占用的数目不同、一般信号量集用于同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的处理;且可分配的资源还存在一个临界值时的处理;Swait(S1,t1,d1;.;Sn,tn,dn);/P原语;原语;if(S1=t1 and .Sn=tn)then/满足资源要求时的处理;满足资源要求时的处理;for i=1 to n do Si=S
20、i-di;endfor;else/某些资源不够时的处理;某些资源不够时的处理;调用进程进入第一个小于调用进程进入第一个小于tj信号量的等待队列信号量的等待队列Sj.queue;阻塞调用进程阻塞调用进程;Ssignal(S1,d1;.;Ssignal(S1,d1;.;SnSn,dndn););for i=1 to n dofor i=1 to n do Si:=Si+Si:=Si+didi;/释放占用的资源;释放占用的资源;for(each process P waiting in for(each process P waiting in Si.queueSi.queue)/检查每种资源的等待
21、队列的所有进程;检查每种资源的等待队列的所有进程;从等待队列从等待队列Si.LSi.L中取出进程中取出进程P;P;if(if(判断进程判断进程P P是否通过是否通过SwaitSwait中的测试中的测试)/注:与注:与signalsignal不同,这里要进行重新判断;不同,这里要进行重新判断;beginbegin/通过检查(资源够用)时的处理;通过检查(资源够用)时的处理;进程进程P P进入就绪队列进入就绪队列;end end else /else /未通过检查(资源不够用)时的处理;未通过检查(资源不够用)时的处理;进程进程P P进入某等待队列;进入某等待队列;endifendif endfo
22、rendforendforendfor 3.1.3 经典进程同步问题经典进程同步问题1.1.生产者消费者问题生产者消费者问题(the producer-consumer problem)(the producer-consumer problem)问题描述:若干进程通过有限的共享缓冲区交换数据。其中,问题描述:若干进程通过有限的共享缓冲区交换数据。其中,生产者生产者 进程不断写入,而进程不断写入,而 消费者消费者 进程不断读出;共享缓冲区进程不断读出;共享缓冲区共有共有N N个;任何时刻只能有一个进程可对共享缓冲区进行操作。个;任何时刻只能有一个进程可对共享缓冲区进行操作。v定义信号量:定义信
23、号量:full是 满缓冲区数目,初值为0,empty是空缓冲区数目,初值为N。实际上,full和empty是同一个含义:full+empty=Nmutex用于访问缓冲区时的互斥,初值是1 生产者生产者消费者问题消费者问题采用采用AND信号量集:信号量集:Swait(empty,mutex),Ssignal(full,mutex),生产者生产者消费者问题消费者问题读者写者问题读者写者问题v问题描述:对共享资源的读写操作,任一时刻问题描述:对共享资源的读写操作,任一时刻“写者写者”最多只允许一个,而最多只允许一个,而“读者读者”则允许多个则允许多个“读写”互斥,“写写”互斥,读读允许Wmutex表
24、示允许写,初值是1。公共变量Rcount表示“正在读”的进程数,初值是0;Rmutex表示对Rcount的互斥操作,初值是1。读者写者问题读者写者问题P(Rmutex);+Rcount;if(Rcount=1)P(Wmutex);V(Rmutex);read;P(Rmutex);-Rcount;if(Rcount=0)V(Wmutex);V(Rmutex);Reader:P(Wmutex);write;V(Wmutex);Writer:v采用一般采用一般 信号量集信号量集 机制:问题增加一个限制条件:同时读的机制:问题增加一个限制条件:同时读的 读者读者 最最多多R R个个Wmutex表示允许
25、写,初值是1Rcount表示允许读者数目,初值为R读者写者问题读者写者问题3.3.哲学家进餐问题哲学家进餐问题v问题描述:(由问题描述:(由Dijkstra首先提出并解决)首先提出并解决)5个哲学家个哲学家围绕一张圆桌而坐,桌子上放着围绕一张圆桌而坐,桌子上放着5支筷子,每两个哲学家支筷子,每两个哲学家之间放一支;哲学家的动作包括思考和进餐,进餐时需要之间放一支;哲学家的动作包括思考和进餐,进餐时需要同时拿起他左边和右边的两支筷子,思考时则同时将两支同时拿起他左边和右边的两支筷子,思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行?如:筷子放回原处。如何保证哲学家们的动作有序进行?
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 操作系统 进程 同步 通信
限制150内