操作系统中的信号量机制PV操作,理发店问题和生产者消费者问题有何区别
占用S资源或是释放该资源。
在操作系统理论中有一个非常重要的概念叫做P,V原语。在我们研究进程间的互斥的时候经常会引入这个概念,将P,V操作方法与加锁的方法相比较,来解决进程间的互斥问题。实际上,他的应用范围很广,他不但可以解决进程管理当中的互斥问题,而且我们还可以利用此方法解决进程同步与进程通信的问题。
[一]P,V原语理论
阐述P,V原语的理论不得不提到的一个人便是赫赫有名的荷兰科学家E.W.Dijkstra。如果你对这位科学家没有什么印象的话,提起解决图论中最短路径问题的Dijkstra算法应当是我们再熟悉不过的了。P,V原语的概念以及P,V操作当中需要使用到的信号量的概念都是由他在1965年提出的。
信号量是最早出现的用来解决进程同步与互斥问题的机制,包括一个称为信号量的变量及对它进行的两个原语操作。信号量为一个整数,我们设这个信号量为:sem。很显然,我们规定在sem大于等于零的时候代表可供并发进程使用的资源实体数,sem小于零的时候,表示正在等待使用临界区的进程的个数。根据这个原则,在给信号量附初值的时候,我们显然就要设初值大于零。
p操作和v操作是不可中断的程序段,称为原语。P,V原语中P是荷兰语的Passeren,相当于英文的pass, V是荷兰语的Verhoog,相当于英文中的incremnet。
P原语操作的动作是:
(1) sem减1;
(2) 若sem减1后仍大于或等于零,则进程继续执行;
(3) 若sem减1后小于零,则该进程被阻塞后进入与该信号相对应的队列中,然后转进程调度。
V原语操作的动作是:
(1) sem加1;
(2) 若相加结果大于零,则进程继续执行;
(3) 若相加结果小于或等于零,则从该信号的等待队列中唤醒一等待进程,然后再返回原进程继续执行或转进程调度。
需要提醒大家一点就是P,V操作对于每一个进程来说,都只能进行一次。而且必须成对使用。且在P,V愿语执行期间不允许有中断的发生。
对于具体的实现,方法非常多,可以用硬件实现,也可以用软件实现。我们采用如下的定义:
procedure p(var s:samephore);
{
s.value=s.value-1;
if (s.value<0) asleep(s.queue);
}
procedure v(var s:samephore);
{
s.value=s.value+1;
if (s.value<=0) wakeup(s.queue);
}
其中用到两个标准过程:
asleep(s.queue);执行此操作的进程控制块进入s.queue尾部,进程变成等待状态
wakeup(s.queue);将s.queue头进程唤醒插入就绪队列
对于这个过程,s.value初值为1时,用来实现进程的互斥。
虽软说信号量机制毕加锁方法要好得多,但是也不是说它没有任何的缺陷。由此我们也可以清晰地看到,这种信号量机制必须有公共内存,不能用于分布式操作系统,这是它最大的弱点。
[二]P,V原语的应用
正如我们在文中最开始的时候提到的,P,V原语不但可以解决进程管理当中的互斥问题,而且我们还可以利用此方法解决进程同步与进程通信的问题。
(1)用P V原语实现进程互斥
把临界区置于P(sem) 和V(sem)之间。当一个进程想要进入临界区时,它必须先执行P原语操作以将信号量sem减1,在进程完成对临界区的操作后,它必须执行V原语操作以释放它所占用的临界区。从而就实现了进程的互斥:
具体的过程我们可以简单的描述如下:
PA:
P(sem)
;
V(sem)
PB:
P(sem)
;
V(sem)
(2) 用P V原语实现进程同步
进程同步问题的解决同样可以采用这种操作来解决,我们假设两个进程需要同步进行,一个进程是计算进程,另一个进程是打印进程,那么这个时候两个进程的定义可以表示为:
PC(表示计算进程)
A: local buf
repeat
buf=buf
until buf=空
计算
得到计算结果
buf=计算结果
goto A
PP:(表示打印进程)
B: local pri
repeat
pri=buf
until pri!=空
打印buf中的数据
清除buf中的数据
goto B
相应用P,V原语的实现过程为:
PA: deposit(data)
Begin local x
P(bufempty)
按FIFO方式选择一个空缓冲区buf(x)
buf(x)=data
buf(x)置满标记
V(buffull)
end
PB:remove(data)
Begin local x
P(buffull)
按FIFO方式选择一个装满
数据的缓冲区buf(x)
data=buf(x)
buf(x)置空标记
V(bufempty)
end
(3)用P V原语实现进程通信
我们以邮箱通信为例说明问题:
邮箱通信满足的条件是:
;发送进程发送消息的时候,邮箱中至少要有一个空格能存放该消息。
;接收进程接收消息时,邮箱中至少要有一个消息存在。
发送进程和接收进程我们可以进行如下的描述:
Deposit(m)为发送进程,接收进程是remove(m). Fromnum为发送进程的私用信号量,信箱空格数n。mesnum为接收进程的私用信号量,初值为0.
Deposit(m):
Begin local x
P(fromnum)
选择空格x
将消息m放入空格x中
置格x的标志为满
V(mesnum)
end
Remove(m)
Begin local x
P(mesnum)
选择满格x
把满格x中的消息取出放m中
置格x标志为空
V(fromnum)
end
不过如果是这个问题的话,跟生产者消费者完全没区别吧……理发师是消费者,顾客是生产者……
要求描述理发师和顾客的行为,因此需要两类进程Barber ()和Customer()分别描述理发师和顾客的行为。理发师和顾客之间是同步的关系,理发师和椅子是临界资源,所以顾客之间是互斥的关系。
引入3个信号量和一个控制变量:
1) 控制变量waiting也用于记录等候的顾客数,实际上是customers的一份拷贝。之所以使用waiting是因为无法读取信号量的当前值,初值均为0。
2)信号量customers用来记录等候理发的顾客数(不包括正在理发的顾客),并用作阻塞理发师进程,初值为0。
3)信号量barbers用来记录正在等候顾客的理发师数(为0或1),并用作阻塞顾客进程,初值为0。
4)信号量mutex用于互斥,初值为1。
进入理发店的顾客必须先看等候的顾客数,如果少于椅子数(n),他坐下来等,否则他就离开。
PV操作代码如下
int waiting=0 ; //等候理发的顾客数(还没理发的), 0~n
semaphore customers=0, barbers=0, mutex=1;
barber() {
while(TRUE) //理完一人,还有顾客吗?
{ P(customers); //若无顾客,理发师睡眠
P(mutex); //进程互斥
waiting := waiting – 1; //等候顾客数少一个
V(barbers); //理发师去为一个顾客理发
V(mutex); //开放临界区
cut-hair( ); //正在理发(非临界区操作)
}
}
customer() { //顾客进入理发店
P(mutex); //进程互斥
if (waiting < n)
{ //还有空位
waiting := waiting+1; //等候顾客数加1
V(customers); //有顾客了,如果理发师在睡则唤醒
V(mutex); //开放临界区
P(barbers); //无理发师, 顾客坐着养神
get-haircut( ); //一个顾客坐下等待理发/
}
else V(mutex); //顾客已满,离开
}
计算机操作系统的目录
2.3 进程的阻塞与唤醒2.3 进程的同步与互斥2.3.1 进程间的制约关系2.3.2 临界资源与临界区2.3.3 信号量机制2.3.4 用P、V操作实现进程的同步与互斥2.3.5 经典的同步与互斥问题2.3.6 管程的概念2.4 进程通信2.4.1 共享存储器系统2.4.2 管道通信2.4.3 消息传递系统2.5 线程2....
在操作系统中,P操作和V操作各自的动作是如何定义的?
①信号量的值减1,即S=S-1;②如果S≥0,则该进程继续执行;如果S<0,则把该进程的状态置为阻塞态,把相应的PCB连入该信号量队列的末尾,并放弃处理机,进行等待(直至其它进程在S上执行V操作,把它释放出来为止)。V操作顺序执行下述两个动作:①S值加1,即S=S+1;②如果S>0,则该进程继续...
有没有操作系统的试题啊?
1.以下著名的操作系统中,属于多用户、分时系统的是( )。 A.DOS系统 B.UNIX系统 C.Windows NT系统 D.OS\/2系统 2.在操作系统中,进程的最基本的特征是( )。 A.动态性和并发性 B.顺序性和可再现性 C.与程序的对应性 D.执行过程的封闭性 3.操作系统中利用信号量和P、V操作,( )。 A.只能实现进程的互...
信号量机制是谁提出来的?
剩下的车则必须在入口等待,此后来的车也都不得不在入口处等待。这时,有一辆车离开停车场,看门人得知后,打开车拦,放入外面的一辆进去,如果又离开两辆,则又可以放入两辆,如此往复。在这个停车场系统中,车位是公共资源,每辆车好比一个线程,看门人起的就是信号量的作用。...
Linux操作系统的知识点总结
例如,如果系统部署的Oracle数据库应用,那么就需要对系统共享内存段( kernel.shmmax, kenerl.shmmni, kernel.shmall)、 系统信号量( kernel.sem)、文件句柄( fs.file0max)等参数进行优化设置;如果部署的WEB应用,那么就需要根据web应用特性进行网络参数的优化,例如修改net.ipv4.ip_local_port_range、net.ipv4.tc_tw...
信号量linuxlinux信号量编程
如果需要在自旋锁和信号量中作选择,应该取决于锁被持有的时间长短。理想情况是所有的锁都应该尽可能短的被持有,但是如果锁的持有时间较长的话,使用信号量是更好的选择。另外,信号量不同于自旋锁,它不会关闭内核抢占,所以持有信号量的代码可以被抢占。这意味者信号量不会对影响调度反应时间带来负面...
操作系统课程地位
操作系统是最重要的计算机学科之一,是需要一定的计算机组成原理,数据结构知识作铺垫,但关系不大。认真读书,一定要读进去! 主要理解进程管理中的进程同步,掌握信号量机制,熟悉几个经典进程的同步问题,理解线程的概念,仔细研究处理机调度算法(最好能背下来),知道预防死锁的方法,了解存储器管理的方式和算法。 理论和实际...
计算机考研——操作系统重点总结(上)!建议收藏!
也称为命名管道,去除了管道只能在父子进程中使用的限制。相比于 FIFO,消息队列具有以下优点:它是一个计数器,用于为多个进程提供对共享数据对象的访问。允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制,所以这是最快的一种 IPC。需要使用信号量用来同步对共享存储的访问。与其它通信...
一文搞懂六大进程通信机制原理(全网最详细)
初学操作系统时,常感困惑于进程同步与互斥机制中的信号量与进程通信中同样使用信号量。其实,这些机制虽名字相似,但应用场景与作用大相径庭。本文旨在清晰阐述进程通信的原理及各种机制,帮助理解进程间的协作与信息交换。首先,进程通信(InterProcess Communication,IPC)是进程之间信息交换的基础。在某些情况...
操作系统题目
1,D 2,B 3,C 4,C 5,B 1,p,v操作是信号量的原子操作,是指wait(),signal()操作,具有不可再分性,是信号量的原语操作 .因此选D.2,信号量的值为1,表示开始系统有两个可用的资源,现在变成-1,则表示有一个资源正在等待,因此选B。4,人们把在每个进程中访问临界资源的那段...
费翟血脂:[答案] 1962年,狄克斯特拉离开数学中心进入位于荷兰南部的艾恩德霍芬技术大学(Eindhoven Technical University)任数学教授.在这里,他参加了X8计算机的开发,设计与实现了具有多道程序运行能力的操作系统——THE Multiprogramming System.THE...
户县13284043279: PV操作的原理是什么? ?
费翟血脂: PV原理原则1、互斥的信号量的PV操作在一个进程中出现这里的Sn是互斥的,所以P(Sn)V(Sn)都在顾客进程里面
户县13284043279: pv的OS的PV原理 - ?
费翟血脂: PV原理是用来解决操作系统(OS)进程之间的同步和互斥的.同步:异步环境下的一组进程因相互制约而发送消息,进行互相合作互相等待.使各个进程按照一定的速度执行.互斥:一组进程因为共享一个公共资源,必需保证同一时刻只有...
户县13284043279: 【求助】用PV操作实现进程同步,信号量的初值为? - ?
费翟血脂: 用PV操作实现进程同步,信号量的初值为0. PV操作属于典型的同步机制之一.用一个信号量与一个消息联系起来,当信号量的值为0时,表示期望的消息尚未产生;当信号量的值非0时,表示期望的消息已经存在.用PV操作实现进程同步时,...
户县13284043279: 如何理解生产者消费者模式在实际开发中的应用场景及注意的问题 - ?
费翟血脂: 一、明确定义 要理解生产消费者问题,首先应弄清PV操作的含义:PV操作是由P操作原语和V操作原语组成(原语是不可中断的过程),对信号量进行操作,具体定义如下: P(S):①将信号量S的值减1,即S=S-1; ②如果S³0,则该进程继续执行
户县13284043279: 操作系统中进程互斥的方式之一,信号量机制,理解不了啊,求大神举例说明 - ?
费翟血脂: 其实很简单呢,信号量就是一个资源计数器,对信号量有两个操作来达到互斥,分别是P和V操作. 一般情况是这样进行临界访问或互斥访问的: 设信号量值为1, 当一个进程1运行时,使用资源,进行P操作,即对信号量值减1,也就是资源数...
户县13284043279: 为什么在操作系统中引入信号量及P、V操作? - ?
费翟血脂: 在操作系统理论中有一个非常重要的概念叫做P,V原语.在我们研究进程间的互斥的时候经常会引入这个概念,将P,V操作方法与加锁的方法相比较,来解决进程间的互斥问题.实际上,他的应用范围很广,他不但可以解决进程管理当中的互斥...
户县13284043279: P、V操作相关计算 - ?
费翟血脂: 1个 s=2时,两个进程调用p操作后,s=0 s=0时,进程调用p操作后, s=-1, 同时因为s 实际上,s的初值等于允许并发的进程数,这里就是2个进程.当s
户县13284043279: 信号量机制可以总结为三个要素,应该是哪些 - ?
费翟血脂: 《Operating Systems Design and Implementation》中Andrew S. Tanenbaum对信号量的描述和以前看过的教材有区别.但其核心思想是类似的.以前的书上(包括网上不少帖子)是这么叙述的:―――――――――――――――――...