进程互斥

2024-10-08

进程互斥（共4篇）

进程互斥篇1

摘要：本论文中介绍了进程间的两种主要关系——同步与互斥, 并举了一些例子进行说明。

关键词：进程,信号量,P、V操作

对于一个操作系统而言, 进程的管理是一个极其重要的知识点。在进程管理中主要包含进程的描述与控制, 同步、互斥和通信等内容。本论文将主要介绍进程间的两种主要关系——同步与互斥。

进程同步是指多个相关进程在执行次序上的协调。这些进程相互合作, 在一些关健点上可能需要互相等待或互通消息。互斥是指在操作系统中, 当某一进程正访问某一存储区域时, 就不允许其他进程来读出或者修改存储区的内容, 否则, 就会发生后果无法估计的错误。进程之间的这种相互制约关系称为互斥。

互斥和同步都反映了在异步环境下并发进程间的相互制约关系, 都可归于同步范畴。互斥是同步问题的一个特例, 主要用以解决对临界区的使用问题。一次只允许一个进程使用的资源称为临界资源, 而把在每个进程中访问临界资源的程序段称为临界区或临界段 (—个临界资源可对应多个临界段) 。控制对临界资源的互斥使用是实现并行程序封闭性的关键。

进程同步和互斥的实现机制有四种:信号量、管程、会合、分布式系统。其中信号量出现最早, 应用较多。信号量机制基本原理为两个或多个进程通过简单的信号申请和释放来合作, 进程通过执行原语V (s) 来释放信号, 通过执行原语P (s) 来申请信号。如果某进程处在执行态, 但因未能申请到相应的信号而被挂起, 直至有相应信号的释放为止。这里, s即为信号量。

信号量 (semaphore) 是一个数据结构, 定义如下:

强调一点, 信号量必须被初始化且初始化值不能为负数。

下面举三个例子, 一个是结合临界区 (临界资源) 知识来论述进程互斥的必要性;另两个是论述如何利用信号量P、V操作来实现进程同步与互斥的问题, 以证上述。

第一个例子:互斥的必要性分析

下面是一个完成交换的函数, 其中temp被定义为全局

变量

程序员打算让Swap () 函数可以为任何任务所调用, 如果一个低优先级的任务正在执行Swap () 函数, 而此时中断发生了, 会发生什么事情呢?

图中表示中断发生时Temp已被赋值5, 中断服务子程序使更优先级的任务就绪, 当中断完成时, 操作系统内核使高优先级的那个任务得以运行, 高优先级的任务调用Swap () 函数使Temp赋值为4。这对该任务本身来说, 实现两个变量的交换是没有问题的, 交换后x的值是3, y的值是4。然后高优先级的任务释放了CPU的使用权, 低优先级任务得以继续运行。

注意, 此时Temp的值仍为4!在低优先级任务接着运行时, n的值被错误地赋为4, 而不是正确值5。

第二个例子:进程A通过一个缓冲区不断地向进程B、C、D发送信息, A每向缓冲区送入一个信息后, 必须等进程B、C、D都取走后才可以发送下一个信息, B、C、D对A送入的每一信息各取一次, 试用P、V操作实现它们之间的正确通讯。

此例需设6个信号量Sab Sac Sad SB SC SD

初始化:Sab=1;Sac=1;Sad =1;SB=0;SC=0;SD=0。

第三个例子:第二类读者写者问题 (写者优先)

条件:

(1) 多个读者可以同时进行读;

(2) 写者必须互斥 (只允许一个写者写, 也不能读者写者同时进行) ;

(3) 写者优先于读者 (一旦有写者, 则后续读者必须等待, 唤醒时优先考虑写者) 。强调当一个写进程声明想进行写操作时, 已在等待的读者及后继的读者必须等待写操作完成之后, 才能进行读操作。

在原来的读者优先的基础上, 加入一个初值为1的信号量

S, 使得当至少有一个写者准备访问共享对象时, 它可使后续的读者进程等待写完成。

参考文献

[1]http://www.huihoo.com/os/process/main.htm.

[2]http://www.eygle.com/unix/OS.Process.Lock.Latch.Semaphores.htm.

[3]《计算机专业研究生入学考试全真题解》操作系统分册/前沿考试研究室编著北京:人民邮电出版社, 2008.6.

[4]《操作系统学习指导与训练》徐雨明主编.一北京:中国水利水电出版社.2010.

进程互斥篇2

如今, 互联网上有大量的资源供用户使用, 这些资源很多都是临界资源。互联网上大量进程都要使用这些临界资源。由于临界资源共享时要互斥访问, 这就使得这些进程在访问临界资源时要互斥进入自己的临界区。

进程互斥进入临界区算法设计时要注意三点: (1) 互斥访问 (mutual exclusion) [1,2,3], 即是每次只能有一个进程进入自己的临界区, 同一时间不能两个或两个以上进程进入临界区。 (2) 空闲让进 (progress) , 即是当没有进程在临界区执行, 有一些进程要进入临界区时, 只有那些不在remainder section中执行的进程有权决定谁进入临界区, 并且这决定不能无限推迟。 (3) 有限等待 (bounded waiting) , 即是进程从申请进入临界区到进入临界区这段时间是一段有限的时间, 进程不能无限等待进入。

互联网上共享临界资源进程只有遵循以上三点, 进程执行的结果才不会出错。也只有在遵循以上三点的基础上, 互联网上的应用程序才能为用户提供可靠的资源访问。

目前, 对进程互斥分布式算法设计主要分为三类, 即 (1) permission-based (e.g.Lamport, Ricart-Agrawala, Singhal, Maekawa) , 思想是每一个进程在进入临界区之前要得到所有其他进程的准许。 (2) token-based (Suzuki-Kazami, Raymond, Naimi-Trehel, Neilsen-Mizuno, Chang, Singhal and Liu) , 思想是整个系统有一个token, 只有得到token的进程才能进入临界区。 (3) Quorum based, 思想是所有进程中, 部分进程决定某进程是否可以进入临界区。

2. bakery算法设计的思想

Bakery算法是一种简单的处理n个进程互斥进入临界区的算法。它基于面包店里普遍使用的一种算法。顾客进入面包店的时候首先得到一个服务号码, 得到最小号码的顾客首先得到服务。基于这一思想, bakery算法处理N个进程互斥时对共享变量的读写采用原子操作来实现, 每个进程都拥有一个属于自己的共享变量。这个共享变量指示本进程在等待进入临界区的位置, 只有当本变量指示等待队列的头部时, 本进程才优先进入临界区。只有本进程才可以对属于自己的共享变量读写, 别的进程只能读。Bakery算法代码如图1。

在本算法中, 不同顾客可能得到同一个号码。为此, 我们有定义1。

定义1:有二元组 (number[i], i) 和 (number[j], j) , 当number[i]

定义1的意思是:顾客i的服务号码number[i]<顾客j的服务号码number[j]时, 或者顾客i和顾客j的服务号码相等, 但i<时, 顾客i先服务。在图1中, Bakery算法满足下面三个申明。

申明 (1) (进程互斥)

申明 (2) (空闲让进)

申明 (3) (有限等待)

max (Time (i) boundwait) = (N-1) * (T1+T2) 其中Time (i) boundwait为进程i从申请进入临界区到进入临界区的等待时间。

T1为执行a2:num[i]=max (num[0], num[1], …, num[N-1]) +1所用时间;

T2为执行临界区代码所用时间。

3. 用快速算法对bakery算法的改进

bakery算法解决了n个进程互斥问题, 满足进程互斥时三要点。但bakery算法存在以下实际的缺点。

(1) 总是有进程在临界区时, 进程申请进入临界区的服务号将无限变大 (unbounded number) 。

(2) 使用的共享变量多, 两个共享数组有2N个共享变量, 在分布式环境下使得进程之间信息交换量增大。

(3) 程进入临界区之前要和N-1个进程的服务号进行比较, 不管是否有别的进程要进入临界区, 这无疑会使进程的运行速度变慢。

为此我们提出了进程互斥的快速算法 (fast for n processes) , 可以有效地解决以上bakery算法存在的问题。

为了引入快速算法, 先还是引入快速算法的简单情况, 两个进程的快速算法。可以把bakery算法分成六个部分:start, doorway, ticket assignment, wait section, critical section and final。Start即执行算法初始化代码, 进程i在doorway处即进程i执行完了choosing[i]=true, ticket即执行Number[i]=1+max (Number[1], ..., Number[N]) , wait section即互斥循环, critical section即临界区, final即出临界区善后代码。而快速算法的思想是设置gate1和gate2, 只有同时得到gate1和gate2进程优先进入临界区, 并且后得到者优先进入临界区。在快速算法中我们假定对共享变量的操作都是原子操作。图2是两个进程的快速算法。

断言1:┐ (csp∧csq) 是重言式 (进程互斥) 。

证明:反正法。假设 (csp∧csq) 为真。

由 (1) 、 (2) 得 ( (gate1=p) ∨ (waitq=false∧gate2=p) ) ∧ ( (gate1=q) ∨ (waitp=false∧gate2=q) ) 真, 得 ( (gate1=p) ∧ (gate1=q) ) ∨ ( (gate1=p) ∧ (waitp=false∧gate2=q) ) ∨ ( (gate1=q) ∧ (waitq=false∧gate2=p) ) ∨ ( (waitq=false∧gate2=p) ∧ (waitp=false∧gate2=q) ) ……分配律

(3) 为真。

式子 (3) 中用∨连接的每一项都是假。 (gate1=p) ∧ (gate1=q) 为假, 而 (gate1=p) ∧ (waitp=false∧gate2=q) 时csp和csq不能同时成立, 所以此式也为假, 同理 (gate1=q) ∧ (waitq=false∧gate2=p) 为假, 而 (waitq=false∧gate2=p) ∧ (waitp=false∧gate2=q) 也为假, 得到矛盾。

断言2:两个进程的快速算法满足空闲让进的原则。

证明: (1) 当p已经执行到临界区而q刚执行 (不同时执行算法时) , p进入临界区。

(2) 当p, q同时到达时, 记late (p, gate1) 为p后写gate1, 记late (q, gate1) 为q后写gate1, 记late (p, gate2) 为p后写gate2, 记late (q, gate2) 为q后写gate2。

(2.1) late (p, gate1) ∧late (p, gate2) 时, csp为真;

(2.2) late (p, gate1) ∧late (q, gate2) 时, csq为真;

(2.3) late (q, gate1) ∧late (q, gate2) 时, csq为真;

(2.4) late (q, gate1) ∧late (p, gate2) 时, csp为真, 证明完毕。

断言3:两个进程的快速算法满足有限等待的原则。

证明: (1) 当p已经执行到临界区而q刚执行 (不同时执行算法时) , p进入临界区。两进程直接进入临界区, 不用等待其他进程。

(2) 当p, q同时到达时,

(2.1) late (p, gate1) ∧late (p, gate2) 时, csp为真, p直接进入临界区;q阻塞在q4, 等待时间为p执行临界区的时间 (常数) 。

(2.2) late (p, gate1) ∧late (q, gate2) 时, csq为真, q等待常数时间;p阻塞在p2, 等待时间为q执行临界区的时间 (常数) 。

(2.3) late (q, gate1) ∧late (q, gate2) 时, csq为真, q直接进入临界区;q阻塞在q2, 等待时间为p执行临界区的时间 (常数) 。

(2.4) late (q, gate1) ∧late (p, gate2) 时, csp为真, p等待常数时间, q阻塞在q2, 等待时间为p执行临界区的时间 (常数) 。证明完毕。

快速算法n个进程情况只需对两个进程情况稍加修改, 引入数组wait[n], n个进程都竞争gate1, gate2。算法如图3。

显然, 快速算法n个进程情况跟快速两个进程的情况一样, 满足互斥、空闲让进、有限等待三要点, 显然有下面断言。

断言4:如果csi为真, 则坌j (1…N) j≠i, ┐csj是重言式 (进程互斥) 。

断言5:N个进程的快速算法满足空闲让进的原则。

证明: (1) 当N个进程两两不同时到达时, 各进程直接进入临界区。

(2) 当N个进程同时到达时, 最后写gate2的进程首先进入临界区, 剩下N-1个进程最后写gate2的进程首先进入临界区。

断言6:N个进程的快速算法满足有限等待的原则。

证明:各个进程的平均等待的时间为O (N2) , 满足有限等待。

4. 快速算法的性能和优势分析

我们对快速算法的性能和优势总结以下几点。

(1) 总是有进程在临界区时, 不会出现进程申请进入临界区的服务号将无限变大 (unbounded number) 的情况, 因为快速算法n个进程情况没有用到服务号。

(2) 使用的共享变量只有N个, 即wait[0…N-1], 比bakery算法的2N个共享变量少N个, 大大减少在分布式环境下进程之间信息交换量。

(3) bakery算法中, 当没有别的进程进入临界区时, 本进程进入临界区之前要和N-1个进程的服务号进行比较, 而快速算法此情况下本进程直接进入临界区, 提高了速度;当有N个进程竞争进入临界区时, 快速算法中各个进程少max (Number[1], ..., Number[N]) 操作, 同时少本进程同其他进程号比较操作, 大大提高了进程的执行速度。

5. 结论

对bakery算法进行改进后的快速算法克服了服务号将无限变大 (unbounded number) 的弊端, 同时减少了分布式环境进程之间的信息交换量, 提高了进程的执行速度, 而且满足进程互斥设计时的互斥, 空闲让进、有限等待三要点。快速算法的引入将大大提高互联网上的资源共享的效率, 提高互联网应用程序的运行效率。

摘要：本文简要地介绍了bakery算法进程互斥思想, 指出它存在的三个缺点。然后在满足进程互斥设计三要点的前提下, 提出快速互斥算法, 并且对它的性能和优点给出证明, 指出快速算法能够很好地解决bakery算法的缺点。

关键词：bakery算法,快速算法,进程互斥,空闲让进有限等待

参考文献

[1]Chen, Y, Welch, J.Self-Stabilizing Mutual Exclusion Us-ing Tokens in Mobile Ad Hoc Networks.Proceedings of the6th in-ternational workshop on Discrete Algorithms and methods for mo-bile computing and communications, 2002:34-42.

[2]Sujata Banerjee.A New Token Passing Distributed Mutual Exclusion Algorithm.Proceedings of the Intl.Conf.on Distributed Computing Systems (ICDCS) , 1996.

进程互斥篇3

1 同步与互斥

一组并发进程因直接制约而相互发送消息,进行相互合作,互相等待,使得各进程按一定的速度执行的过程,称为进程间同步 ;一组并发进程中一个或多个程序段,因共享某一公用资源而导致它们必须以一个不允许交叉执行的单位执行,称为互斥。系统中一次仅允许一个进程访问的系统资源叫临界资源,而在进程中对临界资源访问的程序段叫临界区。

2 信号量与 p,v 操作

信号量是表示资源的物理实体,是一个与队列有关的整型变量,其值仅能由P和V操作来改变。利用信号量的状态对进程和资源进行管理,信号量能方便地解决临界区问题。信号量的数据结构为一个值和一个指针,指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时,表示当前可用资源的数量 ;当它的值小于0时,其绝对值表示等待使用该资源的进程个数。

P,V操作由P操作原语和V操作原语组成(原语是不可中断的过程),对信号量进行操作,具体定义如下 :

P(S):1将信号量S的值减1,即S=S-1 ;

2如果S>=0,则该进程继续执行 ;否则该进程置为等待状态,排入等待队列。

V(S):1将信号量S的值加1,即S=S+1 ;

2如果S>0,则该进程继续执行 ;否则释放队列中第一个等待信号量的进程。

可以利用信号量及P,V操作来实现进程的同步和互斥。

一般来说,信号量S>=0时,S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源,因此S的值减1 ;当S<0时,表示已经没有可用资源,请求者必须等待别的进程释放该类资源,它才能运行下去。而执行一个V操作意味着释放一个单位资源,因此S的值加1 ;若S<0,表示有某些进程正在等待该资源,因此要唤醒一个等待状态的进程,使之运行下去。

3 P,V 操作模型

3.1 同步模型

P,V操作是典型的同步机制之一。用一个信号量与一个消息联系起来,当信号量的值为0时,表示期望的消息尚未产生 ;当信号量的值非0时,表示期望的消息已经存在。用P,V操作实现进程同步时,调用P操作测试消息是否到达,调用V操作发送消息。

使用P,V操作实现进程同步时应该注意的是 :

(1)分析进程间的制约关系,确定信号量种类。在保持进程间有正确的同步关系情况下,哪个进程先执行,哪些进程后执行,彼此间通过什么资源(信号量)进行协调,从而明确要设置哪些信号量。

(2)信号量的初值与相应资源的数量有关,也与P、V操作在程序代码中出现的位置有关。

(3)同一信号量的P、V操作要成对出现,但它们分别在不同的进程代码中。

3.2 互斥模型

利用信号量和P,V操作实现进程互斥的一般模型是 :

其中信号量S用于互斥,初值为1。

使用P,V操作实现进程互斥时应该注意的是 :

(1)每个程序中用户实现互斥的P,V操作必须成对出现,先做P操作,进临界区,后做V操作,出临界区。若有多个分支,要认真检查其成对性。

(2)P,V操作应分别紧靠临界区的头尾部,临界区的代码应尽可能短,不能有死循环。

(3)互斥信号量的初值一般为1。

4 P,V 操作实现同步与互斥

4.1 P,V 操作实现同步

例1桌上有一空盘,允许存放一只水果。爸爸可向盘中放苹果,也可向盘中放桔子,儿子专等吃盘中的桔子,女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用,请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。

分析 : 在本题中,爸爸、儿子、女儿共用一个盘子,盘中一次只能放一个水果。当盘子为空时,爸爸可将一个水果放入果盘中。若放入果盘中的是桔子,则允许儿子吃,女儿必须等待 ;若放入果盘中的是苹果,则允许女儿吃,儿子必须等待。本题实际上是生产者 - 消费者问题的一种变形。这里,生产者放入缓冲区的产品有两类,消费者也有两类,每类消费者只消费其中固定的一类产品。

设置三个信号量S、So、Sa,信号量S表示盘子是否为空,其初值为l ;信号量So表示盘中是否有桔子,其初值为0 ;信号量Sa表示盘中是否有苹果,其初值为0。

算法描述 :

4.2 P,V 操作实现同步与互斥

例2某寺院有小和尚、老和尚若干,有一水缸,由小和尚提水入缸供老和尚饮用。水缸可容10桶水,水取自同一水井。水井径窄,每次只能容一个桶取水。水桶总数为3个。每次入、取水仅为1桶,且不可同时进行。试给出有关取水、如水的算法描述。

分析 :首先应考虑本题需要几个进程。从井中取水后向缸中倒水为连续动作,可算同一进程,从缸中取水为另一进程。再考虑信号量问题。有关互斥的资源有水井(一次仅一个水桶进出),水缸(一次入、取水一桶),设置两个互斥信号量mutex1,mutex2进行互斥控制 ;同步问题分析 :三个水桶无论从井中取水还是入、出水缸都是一次一个,应为之设置同步信号量count, 控制入水量,水缸空时不可出水,设置同步信号量full,控制出水量。

算法描述 :

5 结束语

进程互斥篇4

1 信号量的含义

信号量被定义为含有整型数据项的结构变量,其整型值大于等于零代表可供并发进程使用的资源个数,小于零时其绝对值表示正在等待使用临界资源的进程数。其数据结构表示为:

由此可以看出信号量是一个结构变量,不是简单变量。

2 P、V原语的含义

信号量的值可以修改,但只能由P和V操作来访问,对信号量的操作由P、V操作原语来实现。P操作和V操作在执行时是不可中断的过程。

P操作P(s)

表示申请一个资源,将信号量s的整型值减去1,若结果小于0,则将调用P(s)的进程插入等待该资源的阻塞队列。

V操作V(s)

表示释放一个资源,将信号量s的整型值加上1,若结果不大于0,则从该资源的阻塞队列首部唤醒一个进程插入到就绪队列中。

P、V操作原语是一种阻塞等待的同步原语,若进程通过该原语的调用而不允许继续执行时,它将被阻塞或挂起,在此期间就没有机会获得CPU执行,直到它被唤醒为止。故可使得进程在等待进入临界区时,将CPU让给了其他就绪进程执行。而忙等待的临界区管理法,使得进程在等待进入临界区时,也和其他就绪进程一起分享CPU的服务。

3 P、V操作在进程同步中的意义

进程同步包括进程互斥和进程同步两个方面,进程互斥是同步的一种特例。用P、V操作解决进程同步问题时首先要分清哪些是互斥问题(互斥访问临界资源的),哪些是同步问题(具有前后执行顺序要求的)。

在互斥问题中,P操作的意义是申请资源,是否能进入临界区;V操作的意义是退出临界区,从而释放资源;通常只设置一个互斥信号量,且初值为1,代表一次只允许一个进程对临界资源进行访问。在同步问题中,P操作的意义是接受发来的信息、通知,表示可以执行;V操作的意义是发送消息、通知,告知对方。在设置同步信号量时,通常同步信号量的个数与参与同步的进程种类有关,即同步关系涉及几类进程,就有几个同步信号量。同步信号量表示该进程是否可以开始或该进程是否已经结束。

在每个进程中用于实现互斥的P、V操作必须成对出现;用于实现同步的P、V操作也必须成对出现,但可以分别出现在不同的进程中;在某个进程中如果同时存在互斥与同步的操作,则其顺序不能颠倒,必须先执行对同步信号量的P操作,再执行对互斥信号量的P操作,但V操作的顺序没有严格要求。

4 实现P、V操作的具体做法

1)确定进程间的关系以及进程的个数。这一环节非常重要,如果理解不准确,则之后的操作都将是错误的。进程间的关系主要指是进程同步还是进程互斥,它决定了P、V操作在进程中存在的意义。进程的个数主要看题目中需要P、V控制的事件有多少个,则进程个数就是几个。

2)信号量个数的设置,并给信号量赋初值。一般情况下,在进程互斥中,信号量都为一个;在同步中,要根据进程间的同步关系来设置信号量的个数,有一个也可能是多个。

3)画出进程的工作流程图。流程图时最好反映题意的一种方法,工作流程图越准确,最后的算法就越容易实现。

4)根据流程图使用一门语言来描述进程之间的关系。这步主要是看个人的编程基础,用不同的语言实现都可以,最好是用自己掌握较好的一门语言。

下面就一些典型例子做分析,在分析中理解P、V操作在进程同步中的实际运用:

4.1 用PV原语实现进程的互斥

为了正确地解决一组并行进程对临界资源的竞争使用,可以引入一个互斥信号量,对于互斥使用的资源,其信号量的初值就是系统中这个资源的数量。以哲学家进餐问题为例:

有四位哲学家围着一个圆桌在思考和进餐,每人思考时手中什么都不拿,当需要进餐时,每人需要用刀和叉各一把,餐桌上的布置如图1所示,共有两把刀和两把叉,每把刀或叉供相邻的两个人使用。请用信号量及PV操作说明四位哲学家的同步过程。

1)确定进程的个数及其工作内容。本例子涉及四个进程,每个哲学家为一个进程。因相邻的两个哲学家要竞争刀或叉,刀或叉就成为了临界资源,所以属于互斥关系。

2)第二步确定互斥信号量的个数、含义及PV操作。设置4个互斥信号量fork1,fork2,knife1,knife2,其初值均为“1”,分别表示叉1,叉2,刀1,刀2是可用的。

3)画工作流程图。一般情况下,进程互斥问题的工作流程基本相同,所以只要画出其中一个进程的流程图即可。

4)根据流程图写出相应算法。用类C语言描述互斥关系,互斥描述如下:

判断进程间是否互斥,关键是看进程间是否共享某一临界资源。在每个程序中用于实现互斥地P和V必须成对出现,即先做P操作,进入临界区,后做V操作,推出临界区。互斥信号量的初值是资源的个数,一般为1。

4.2 用P、V原语实现进程的同步

进程的同步是指相互合作的一组并行进程,各自以独立的、不可预知的速度向前推进,在前进过程中彼此之间需要相互协调步伐,才能更好地完成同一项任务。为了解决进程的同步,同样地也可引入信号量,称之为同步信号量。信号量的初值一般为0,同步信号量的P、V操作要“成对”出现,但是,它们分别出现在不同的进程代码中,应该注意P、V操作在程序代码中出现的位置。通过下面的例子来说明此问题:

桌上有一空盘子,只允许放一个水果。爸爸可以向盘中放苹果,也可以向盘中放桔子,儿子专等吃盘中的桔子,女儿专等吃盘中的苹果。规定当盘空时,一次只能放一个水果,请用P、V操作实现爸爸、儿子、女儿三个“并发进程”的同步。

1)确定进程间的关系。这是一个明显的同步问题,也称为生产者和消费真问题。爸爸可以向盘子中放入两类水果:桔子、苹果;然后儿子、女儿每人可以消费其中一种水果。爸爸是生产者,子女是消费者,也就是只有爸爸放入水果,子女才能消费水果;只有子女消费完水果,爸爸才能再次放入水果。所以爸爸与子女之间是一种同步关系。

2)设置三个同步信号量:Sp表示盘子是否为空,其初值为“1”,其含义是爸爸是否可以开始放入水果;So表示盘中是否有桔子,其含义是儿子是否可以开始取桔子,其初值为“0”表示不能取桔子;Sa表示盘中是否有苹果,其含义是女儿是否可以开始取苹果,其初值为“0”表示不能取苹果。

3)画出工作流程图,如图2所示。

4)根据流程图写出相应算法。

用类C语言描述同步关系:

4.3 用P、V原语实现进程的同步和互斥

有了上面的分析后,下面来考虑进程同步与互斥的混合问题就不难了。混合问题当中关键就是协调同步操作和互斥操作的先后。通过下面的例子来说明此问题:

设有一个具有N个信息元素的环形缓冲区,A进程顺序地把信息写进缓冲区,B进程依次地从缓冲区中读出信息,请用P、V操作表示A和B进程的同步算法。

1)确定进程间的关系。A和B两个进程对缓冲区的访问必须互斥,并且当缓冲区满时,A进程不能写入,必须等待;当缓冲区空时,B进程不能读,必须等待。所以这是一个同步加互斥的问题。

2)确定信号量及其值。可以设置3个信号量:互斥信号量S=1(表示对缓冲区的互斥使用);同步信号量Sw(代表缓冲区是否有空闲,即写进程能否写)、Sr(代表缓冲区是否有数据,即读进程能否读),假设初始时缓冲区没有任何数据,则Sw=N,Sr=0。

3)画出工作流程图,如图3所示。

4)根据流程图写出相应算法。在此就不再详述。

5 总结