信号量是荷兰的计算机科学家Dijkstra65年提出的.ppt
《信号量是荷兰的计算机科学家Dijkstra65年提出的.ppt》由会员分享,可在线阅读,更多相关《信号量是荷兰的计算机科学家Dijkstra65年提出的.ppt(36页珍藏版)》请在装配图网上搜索。
4.3信号量(P,V操作),1.信号量是荷兰的计算机科学家Dijkstra65年提出的,也是最早的同步方法。,所谓信号量:是一个仅能由同步原语对其进行操作的整型变量。,信号量,二元信号量:允许取值为“0”与“1”,主要用作互斥变量。,一般信号量:允许取值为非负整数,主要用于进程间的一般同步问题。,2.P,V操作,P,V操作是对信号量进行的原语操作。,Dijkstra对这两个原语操作定义如下:,P(S):当信号量S大于0时,将S值减1,否则进程等待,直到其它进程对S进行V操作V(S)。,V(S):将信号量S的值加1。,P,V操作的功能描述见下图:,入口,S1S,S0,入信号量等待队列,置“等待”状态,转进程调度,0,P,V操作可用软件(或固件)和硬件来执行。无论P操作和V操作,它们的执行都必须是一个不可被中断的整体。,注:(1)物理意义:,S0时,S为可用资源量;S=0时,可用资源量正好用完;S0立即可得,S0要排队,(2)P(S),Lock(S),S为二元信号量,V(S),unlock(S),对应,V(S):表示释放资源,本书原来使用P、V操作来称呼此两操作,但由于信号量和信号量上的同步原语以及后面要讨论的管程均已成为并行程序语言的组成部分,所以改用程序语言中的习惯称呼,以及国际上较流行的称呼为Wait和Signal操作。,3.当进程必须在信号量S上等待时,就将该进程的状态变为等待状态(或活动阻塞状态),并将该进程插入与此信号量有关的等待队列中,而后让出处理机给其它就绪进程。,两种等待方式下的wait和signal操作:,(1)“忙等待”执行方式:,wait(s):whileS0doskip;S:=S1;signal(s):S:=S+1;,这种形式的P,V操作,完全也可用硬件指令来形式。,(2)“阻塞等待”执行分式:,typeSemaphore=recordvalue:integer;L:pointertoPCBend,等待进程放入与此信号量S有关的阻塞队列,需要有该队列的头指针,因此要把信号量定义进一步进行扩充,其数据结构形式由“忙等待”方式中的整形变量,扩充成为记录形式:,wait(s):S.value:=S.value1;ifS.value0(说明S原0或0“计算下一数,进入缓冲区”V(SA);已有结果,可置标志,SA=SA+1foreverPP:repeatP(SA);已放入结果否?“从缓冲区中取数”receiveV(SB):置空标志,让CP释放下一数打印该数据outputforevercoendend,注记:(a)与P,V互斥比较,(i)互斥一次进一个入cs,但谁先谁后无关系,而同步,先后次序有关。,(ii)互斥:Lock,unlock同步:P,V,互发信号,(b)信号量的个数,SA数据SB空Buff,(c)初值:变化则程序也变化,取代上面CP程序段,若SB:=0;CP:repeat“放入Buff”V(SA);P(SB);forever,进程互斥:在OS中,当某一进程正在访问cs时,就不允许其它进程来读写(访问),否则就会发生后果无法估计的错误,进程之间的这种相互制约关系为进程互斥。,进程同步:并发进程在一些关键点上可能需要互相等待与互通消息,这种相互制约的等待与互通消息,称为进程同步。,进程同步与互斥关系:都反映了在异步环境下并发进程间的相互制约关系。可归于同步范畴,但互斥是同步问题的一个特例,互斥解决临界区的使用,同步是并发进程在一些关键点上需互相等待互发消息。,例3.生产者消费者问题:(producerConsumerProblem),问题:n个生产者(如计算进程)P1,P2Pnm个消费者(如打印)C1,C2Cm通过环形有界缓冲区联系,缓冲区存放产品。(缓冲区为共享资源)。,c,满,空,P1,P2,(i)Pi,Cii=1,2,m,n并行,(ii)缓冲区多个:指针的修改属互斥操作。avail:可用缓冲区数(剩余),初值i。full已占用缓冲区数(产品数),初值为0。mutex临界区互斥信号量,初值为“1”。,beginmutex:=1;avail:=i;full:=0cobeginproducteres(诸多生产者进程),以下以一为例repeat“生产下一产品”P(avail);P(mutex);“送入缓冲区,调查指针”csV(mutex);注:送取数据可放V(full);foreverconsumeres(诸多消费者进程)repeatP(full);P(mutex);“从缓冲区中取数,调整指针”csV(mutex);注:送取取取数据可放V(avail);“消耗产品”coendforeverend,若仅一个生产者,消费者则可删去。,4.5进程间的通讯,一、概念,1.进程之间的信息交换称为进程通讯(各进程为了保持联系而换信息)。,目前两种基本的进程通讯方法:,(1)共享存储器(sharedmemory),(2)消息系统(messagesystem),2.共享存储器方法的主要思想是:进程之间通过共享变量实现信息传送。,例如:信号量机构就属于这类通讯方法,前述的互斥,同步实际上均可看作是进程间通讯的一种方式,只不过交换的信息量较少,用户使用也不方便。我们称这类为低级通讯原语。(P,V操作),3.消息系统的主要思想是:系统提供发送消息Send(message)与接收消息Receive(message)两个操作,进程间则通过使用这两个操作进行通讯,无需共享任何变量。,我们称这种由操作系统实现的通讯方法为高级通讯原语(Send,Receive)。,高级通讯方法,直接通讯消息缓冲,间接通讯邮箱法,所谓“信息”通常由消息头和消息正文构成,typeMsg=recordmsgsender消息发送者msgnext下一个信息,链指针msgsize整个消息的字节数msgtext消息正文end,消息头,消息正文,直接通讯一个进程直接发送一个消息给接收者进程。,一个进程可发信息给多个进程,也可接收多个进程的信息(把发送给它的消息组成消息队列)。,用链式队列方法表示:,间接通讯进程不把消息直接发给接收者进程,而把消息放在某个双方共知的信箱中。,邮箱法:,4.通讯原语:,Send(P1,MSG)向进程P1发送一个信息,Receive(P2,MSG)接收来自进程P2的一个消息,直接通讯,Send(A,MSG),发送一个消息到信箱A,Receive(A,MSG),从信箱A接收一个消息,消息通信与消息队列在许多操作系统和软件开发环境(如WindowsNT)中得到广泛的应用。,- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信号量 荷兰 计算机 科学家 Dijkstra65 提出
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文