操作系统 信号量机制P、V操作习题全解共34页文档

信号量是一个被保护的变量，并且只能通过初始化和两个标准
的原子操作来访问.
1、整型信号量机制 2、记录型信号量机制 3、信号量集机制
5.1/28 2011
操作系统
1、整型信号量机制
1).整型信号量 是一个整数，表示空闲资源总数（又称为“资源信号量”） ----若为非负值表示当前的空闲资源数， ----为负值其绝对值表示当前等待临界区的进程数 ----初值应该大于零。
5.19/28
2011
操作系统
A.采用记录型信号量机制
Wmutex：互斥信号量：表示“允许写”，初值是1。 公共变量Readcount表示“正在读”的进程数，初值是0； Rmutex:互斥信号量：表示对Readcount的互斥操作，初值是1。
reader writer
Wait(Wmutex); Write; Signal(Wmutex); wait(Rmutex); if(Readcount=0) then wait(wmutex) Readcount=Readcount+1; Signal(Rmutex); //关闭写的同时允许读（无上限） read; Wait(Rmutex); Readcount:=Readcount-1; if Readcount=0 then signal(Wmutex); Signal(Rmutex); //适当的时候打开写
两个原子操作即: P,V操作。也常称为wait(s),singal(s)
（P、V分别是荷兰语的test(proberen)和increment(verhogen)） 即： P(s): Wait(s): while s<=0 do no_op s:=s-1; V(s): Singal(s): s:=s+1;

cobegin
procedure reader_i
begin // i=1,2,?.
P(rwmutex); //读者、写者互斥
P(rmutex);
V(rwmutex); // 释放读写互斥信号量，允许其它读、写进程访问资源
读数据；
V(rmutex);
end
procedure Writer_j
我们需要分两种情况实现该问题：
读优先： 要求指一个读者试图进行读操作时，如果这时正有其他读者在进行操作，他可直接开始读操作，而不需要等待。
写优先： 一个读者试图进行读操作时，如果有其他写者在等待进行写操作或正在进行写操作，他要等待该写者完成写操作后才开始读操作。
The P,V code Using Pascal
3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）
如果读者数是固定的，我们可采用下面的算法：
rwmutex：用于写者与其他读者/写者互斥的访问共享数据
rmutex： 该信号量初始值设为10，表示最多允许10个读者进程同时进行读操作
var rwmutex, rmutex ： semaphore := 1, 10 ；
操作系统P V题解
第一章 The P,V Theorem
在操作系统理论中有一个非常重要的概念叫做P,V原语。在我们研究进程间的互斥的时候经常会引入这个概念，将P,V操作方法与加锁的方法相比较，来解决进程间的互斥问题。实际上，他的应用范围很广，他不但可以解决进程管理当中的互斥问题，而且我们还可以利用此方法解决进程同步与进程通信的问题。
Figure 1.1: producer-consumer problem

【操作系统】信号量机制信号量机制基本概念信号量：信号量（Semaphores）的数据结构由⼀个值value和⼀个进程链表指针L组成，信号量的值代表了资源的数⽬，链表指针链接了所有等待访问该资源的进程。

PV操作：通过对信号量S进⾏两个标准的原⼦操作（不可中断的操作）wait(S)和signa(S)，可以实现进程的同步和互斥。

这两个操作⼜常被称为P、V操作，其定义如下： P(S)：①将信号量S的值减1，即S.value=S.value-1； ②如果S.value≥0，则该进程继续执⾏；否则该进程置为等待状态，排⼊等待队列。

V(S)：①将信号量S的值加1，即S.value=S.value+1； ②如果S.value>0，则该进程继续执⾏；否则释放S.L中第⼀个的等待进程。

说明：S.value代表可⽤的资源数⽬，当它的值⼤于0时，表⽰当前可⽤资源的数量；当它的值⼩于0时，其绝对值表⽰等待使⽤该资源的进程个数。

⼀次P操作意味着请求分配⼀个单位资源，因此S.value减1，当S.value<0时，表⽰已经没有可⽤资源，请求者必须等待别的进程释放该类资源，它才能运⾏下去。

⽽执⾏⼀次V操作意味着释放⼀个单位资源，因此S.value加1；若S≤0，表⽰有某些进程正在等待该资源，因此要唤醒⼀个等待状态的进程，使之运⾏下去。

利⽤信号量和PV操作实现进程互斥的⼀般模型是：信号量S⽤于互斥，S.value初值为1。

整型信号量 最初定义的信号量，信号量S就是⼀个于代表资源数⽬的整型量，该机制下⽆法实现“让权等待”的准则。

略（具体内容可参考《计算机操作系统》）。

记录型信号量　 基本概念中描述的就是记录型信号量，信号量S的两个数据项可描述为：type semaphore=recordvalue:integer;L:list of process;end 相应地，wait(S)和signa(S)操作（即PV操作）可描述为：procedure wait(S)var S:semaphore;beginS.value:=S.value-1;if S.value<0 then block(S,L) /*将进程排⼊等待队列S.L中*/Endprocedure signal(S)var S:semaphore;beginS.value:=S.value+1;if S.value≤0 then wakeup(S,L); /*唤醒S.L上的第⼀个等待进程*/endAND型信号量上⾯的机制仅适⽤于各进程间只共享⼀个临界资源的情况，当进程需要⼏个共享资源时，容易出现死锁现象（原因详见书籍）。

操作系统PV深度剖析PV操作的例题PV操作的例题一、线程是进程的一个组成部分，一个进程可以有多个线程，而且至少有一个可执行线程。

进程的多个线程都在进程的地址空间内活动。

资源是分给进程的，而不是分给线程的，线程需要资源时，系统从进程的资源配额中扣除并分配给它。

处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程。

线程在执行过程中，需要同步。

二、在计算机操作系统中，PV操作是进程管理中的难点。

首先应弄清PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：P（S）：①将信号量S的值减1，即S=S-1；②如果S>=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。

V（S）：①将信号量S的值加1，即S=S+1；②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。

PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。

PV操作属于进程的低级通信。

什么是信号量？信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。

信号量的值与相应资源的使用情况有关。

当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。

注意，信号量的值仅能由PV操作来改变。

一般来说，信号量S>=0时，S表示可用资源的数量。

执行一次P 操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。

而执行一个V操作意味着释放一个单位资源，因此S 的值加1；若S?0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。

利用信号量和PV操作实现进程互斥的一般模型是：进程P1 进程P2 ……进程Pn ………………P（S）；P（S）；P（S）；临界区；临界区；临界区；V（S）；V（S）；V（S）；……………………其中信号量S用于互斥，初值为1。

信号量应用问题：1．写出程序描述下列前趋关系。

S1->S2, S1->S3, S2->S4, S2->S5 , S3->S6, S4->S7, S5->S7, S6->S7Var s1,s2, s3,s4:semaphore:=0, 0, 0, 0;BeginParbeginP1: begin….;V(s1);V(s1);End;P2: beginP(s1);…;V(s2);V(s2);End;P3: beginP(s1)…V(s3)End;P4: beginP(s2);…V(s4);P5: beginP(s2);..;V(s4);End;P6: beginP(s3)..V(s4)End;P7:beginP(s4);P(s4);P(s4);…End;Parendend2. 请用信号量实现4×100（4人，每人100米）接力赛的同步过程。

提示：前趋图同步问题，可设4个进程，三个信号量，进程1只设V操作，进程4只设P操作，其余进程先做P 操作再做V操作。

Var s1,s2,s3:semaphore:=0, 0, 0; BeginParbeginAthlete1: beginRun 100m;V(s1);End;Athlete2: beginP(s1)Run 100m;V(s2);End;Athlete3: beginP(s2) ;Run 100m;V(s3);End;Athlete4: beginP(s3);Run 100m;End;Parendend3．设公共汽车上，司机和售票员的活动分别是：司机：售票员：启动车辆上乘客正常行车关车门到站停车售票开车门下乘客在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？请用信号量机制实现他们的同步。

/-假定初始状态为停车状态，引入信号量Stop和Run：BEGINsemaphore Stop,Run;Stop:=Run:=0;CoBeginDriver: BEGINRepea tWa it(Run);启动车辆；正常行驶；到站停车；Si gnal(Stop);Until False;END;Conductor:BEGINRepea t上乘客；关车门；Si gnal(Run);售票；Wa it(Stop);开车门；下乘客；Until False;END;CoEnd;END;生产者消费者问题：1．桌上有一个可以容纳两个水果的盘子，每次只能放或取一个水果。

• 要求说明每个信号量是用于解决什么互斥、 什么同步关系的。
Get

Copy
Put
A
B
卡片机
buffer1
C
D
buffer2
打印机
• 2. 互斥信号量 s1=1, s2=1; • (因为只有一个get、copy和put进程，故可不定
义互斥信号量） • 同步信号量4个： • full1=0, empty1=1; 为一对 • full2=0, empty2=1; 为一对
• 两个同步关系： • 有顾客营业员才叫号s1=0 • 营业员先叫号，顾客才能被服务service
＝0
• Process 顾客 i：
• { P (empty);
• P(mutex);
• 从取号机获取一个号码；
• V(mutex);
• V(s1);
• P(service); //等待叫号;
• V (empty); • 获得服务； •}
Agent() int rr, rr1=4; while (1) { do
rr = random (3); while (rr == rr1);
rr1=rr; wait (done); if (rr == 0) {
put paper and tobacco; signal (PaperTobacco ); } else if (rr == 1) {
put match and tobacco; signal (MatchTabacco);
}
else { put paper and match; signal (PaperMatch);
} Smaker1 () /* has match */ while(1) { wait (PaperTobacco);

从等待队列队尾取一个进程唤醒， 插入就绪队列
问题：（实现 4 个进程使用某一个需互斥使用的资源） 1）这样定义 P、V 操作是否有问题？
不合理：先进后出；可能“无限等待”
2）先考虑用这样的 P、V 操作实现 N 个进程竞争使用某一共享变量的互斥机制。 思路：令等待队列中始终只有一个进程。 将 “栈” 变成 “队列”
IF fork [i]=used THEN test_and_pick_up=false
ELSE BEGIN fork [i]:=used; test_and_pick_up:=true END
END;
PROCEDURE put_down(i:0..4); BEGIN fork [i]=free; signal (queue [i]); END;
Then V(buff[j].empty)； V(buff[j].mutex); j:=(j+1) mod k Until false; End
37.对 PV 操作定义做如下修改
P(s):
s:=s-1;
If s<0
Then 将本进程插入相应队列末尾等待；
V(s)：
s:=s+1; If s<=0 Then
} }
消费者： Void consumer (void); {
int item, I;
Message m; For (i=0;i<N; i++) send (producer, &m); While (TRUE){
Receive ( producer ,&m)； Extract_item( &m, &item); Send (producer ,&m); Consumer_item(item); } }

信号量p、v操作，利用信号量实现互斥的方法-概述说明以及解释1.引言1.1 概述信号量（Semaphore）是一种重要的同步工具，在并发编程中起到了关键的作用。

它是由荷兰计算机科学家艾兹赫尔·迪科斯彻兹于1965年提出的。

信号量可以用于控制对共享资源的访问，实现进程或线程之间的互斥和同步。

在计算机系统中，多个进程或线程可能需要同时访问某个共享资源，这时就会引发竞争条件（Race Condition）问题。

竞争条件会导致数据不一致性和程序错误，为了解决这个问题，需要引入互斥机制来保证共享资源在任意时刻只能被一个进程或线程访问。

信号量的引入能够有效地解决互斥问题。

它通过一个计数器来控制对共享资源的访问。

这个计数器被称为信号量的值，其可以是一个非负整数。

当信号量的值大于等于0时，表示共享资源可用，进程可以继续访问。

当信号量的值小于0时，表示共享资源不可用，进程需要等待其他进程释放该资源后才能继续访问。

信号量的实现依赖于两个操作：P（Proberen）和V（Verhogen）。

P操作用于申请共享资源，即进程想要对共享资源进行访问时，必须先进行P操作。

如果信号量的值大于等于1，即资源可用，那么P操作会将信号量的值减1，并允许进程继续访问共享资源。

如果信号量的值小于1，即资源不可用，那么进程就需要等待。

V操作用于释放共享资源，即进程访问完共享资源后，必须进行V操作，将信号量的值加1，以便其他进程可以访问该资源。

利用信号量实现互斥的方法，就是通过对共享资源进行P和V操作，来控制对资源的访问。

在访问共享资源之前，进程需要先执行P操作锁定资源，访问完毕后再执行V操作释放资源。

这样就能够保证在任意时刻只有一个进程能够访问共享资源，实现了互斥。

总结起来，信号量是一种重要的同步工具，通过P和V操作可以实现对共享资源的互斥访问。

利用信号量实现互斥的方法可以有效地解决竞争条件问题，保证数据的一致性和程序的正确性。

操作系统PV操作习题操作系统PV操作习题-----------------------------------------------------1、引言在操作系统中，PV操作（也称作P操作和V操作）是用于进程同步的一种常见机制。

P操作用于获取或申请资源，V操作用于释放资源。

本文将为您提供一些关于PV操作的习题，以帮助您巩固相关的概念和原理。

2、PV操作基本概念2.1 P操作描述P操作的基本概念和含义，以及在实际应用中的具体场景。

2.2 V操作解释V操作的基本概念和含义，并举例说明其在实际问题中的应用。

3、PV操作习题集3.1 习题一、生产者-消费者问题描述一个典型的生产者-消费者问题，并通过使用P操作和V操作对其进行解决。

3.2 习题二、读者-写者问题解释一个典型的读者-写者问题，并使用PV操作来实现对该问题的解决。

3.3 习题三、哲学家就餐问题描述哲学家就餐问题的场景，并说明如何采用PV操作来解决这一问题。

4、常见PV操作错误4.1 死锁解释什么是死锁以及为什么会发生死锁现象，同时提供一些避免死锁的方法。

4.2 饥饿描述什么是饥饿，以及一些可能导致饥饿的常见原因，并提供解决饥饿问题的一些策略。

5、附录本文档附带以下附件:- 习题的解答和详细说明- 相关的代码示例6、法律名词及注释在本文档中，涉及的法律名词及其注释如下：- PV操作：即P操作和V操作，用于进程同步的一种机制。

- 生产者-消费者问题：一种经典的并发控制问题，涉及到生产者和消费者之间的资源竞争。

- 读者-写者问题：一种并发控制问题，涉及到多个读者和写者对共享资源的访问。

- 哲学家就餐问题：一种经典的并发控制问题，涉及到多个哲学家通过共享的餐具进行就餐。

••信号量应用问题：End;Pare nd.写出程序描述下列前趋关系。

1 endS2->S4, S1->S3, S1->S2,S2->S5 , S3->S6, S4->S7,2•请用信号量实现4X 10(4人，每S5->S7, S6->S7人100Var s1,s2, s3,s4:semaphore:=0, 0米, )接力赛的同步过程。

提示：前趋图同步问题，可设0, 0; 4个进程，三个信号量，进程 1 只设BeginV操作，进程4只设ParbeginP操作，其余进程先做P操作再做V P1:begi n 操作。

Var s1,s2,s3:semaphore:=0, 0, 0;.; …Begin V(s1);Parbegin V(s1);Athlete1: begin End;Run 100m; P2: beginV(s1); P(s1);End; …;Athlete2: begin V(s2);P(s1) V(s2);Run 100m; End;V(s2); P3: beginEnd; P(s1)Athlete3: begin …P(s2) ;V(s3)P(s2);Athlete4: begin …P(s3);V(s4);P(s2);Parend ..;endV(s4);3．设公共汽车上，司机和售票员的活 End;动分别是： P6: begin司机：售票员： P(s3)启动车辆 ..xx 乘客V(s4)正常行车关车门到站停车售票 End;P7:begin 开车门P(s4);P(s4)下乘客P(s4)在汽车不断地到站、停车、行驶过 END;程中，这两个活动有什么同步关系？ CoEnd;END;请用信号量机制实现他们的同步。

假定初始状态为停车状态，引入信/- 生产者消费者问题：和 Run ：号量Stopl BEGIN．桌上有一个可以 xx 两个水果的Run 100m; End;V(s3); P4: beginEnd; Run 100m; P5: beginEnd;盘子，每次只能放或取一个水果爸semaphore Stop,Run;爸放苹果妈妈放橘子，两个儿子Stop:=Run:=0; 吃苹果，两个女儿吃橘子。

《操作系统》习题解答1. 进程管理1.1 概念题1.请简述进程和线程的区别。

进程是计算机中程序执行的基本单位，每个进程都有独立的内存空间和系统资源。

线程是进程内部的一个执行流程，线程共享进程的内存空间和系统资源。

进程和线程的主要区别在于资源占用和调度级别。

2.请解释什么是上下文切换，并说明上下文切换的原因。

上下文切换是指操作系统在多道程序设计环境中，为了在多个进程之间进行切换，需要保存和恢复进程的执行状态。

上下文切换的原因主要有以下几点：–进程调度：操作系统根据调度算法，为各个进程分配CPU时间。

–中断处理：硬件或软件中断发生时，操作系统需要保存当前进程的状态，并切换到中断处理程序。

–系统调用：进程执行系统调用时，需要切换到操作系统提供的服务程序。

3.请简述进程同步和互斥的区别。

进程同步是指进程之间按照一定的顺序执行，以完成某个任务。

互斥是指在同一时刻，只有一个进程能够访问共享资源。

进程同步和互斥的主要区别在于它们解决的问题不同。

进程同步解决的是进程之间的执行顺序问题，而互斥解决的是进程对共享资源的访问问题。

1.2 计算题1.有一个单核处理器，使用轮转调度算法进行进程调度。

现有A、B、C、D四个进程，它们的执行时间分别为2ms、3ms、5ms和8ms。

假设每个进程的到达时间都为0ms，请绘制这四个进程的调度顺序和平均等待时间。

调度顺序：A -> B -> C -> D平均等待时间：（2+3+5+8）/ 4 = 4.5ms2.有一个具有两个处理器的计算机系统，使用抢占式优先级调度算法进行进程调度。

现有A、B、C、D四个进程，它们的执行时间分别为2ms、3ms、5ms和8ms，优先级分别为1、2、3、4。

假设每个进程的到达时间都为0ms，请绘制这四个进程的调度顺序和平均等待时间。

调度顺序：A -> B -> C -> D平均等待时间：（2+3+5+8）/ 4 = 4.5ms2. 内存管理2.1 概念题1.请简述虚拟内存和物理内存的区别。

P、V操作 、 操作
入 口 S = S + 1 S ≤ ≥ 0 是 否 是 否 返 回
调用进程入等待队列 唤醒等待队列中的一个进程 转进程调度 返回或转进程调度
1、独木桥问题。某条河上只有一座独木桥，以便行人 独木桥问题。某条河上只有一座独木桥， 过桥， 现在河的两边都有人要过桥， 过桥 ， 现在河的两边都有人要过桥 ， 按照下面的规则 过桥，为了保证过桥安全，请用P 过桥 ， 为了保证过桥安全 ， 请用 P， V操作分别实现正 确的管理。 确的管理。 过桥的规则： 同一方向的可连续过桥， 过桥的规则 ： 同一方向的可连续过桥 ， 某方向有人过 桥时另一方向的人要等待。 桥时另一方向的人要等待。 2、桌上有一空盘，允许存放一只水果。爸爸可向盘中 桌上有一空盘，允许存放一只水果。 放苹果， 也可向盘中放桔子， 儿子专等吃盘中的香蕉， 放苹果 ， 也可向盘中放桔子 ， 儿子专等吃盘中的香蕉 ， 女儿专等吃盘中的苹果。 女儿专等吃盘中的苹果 。 规定当盘空时一次只能放一 原语实现爸爸、儿子、 只水果供吃者使用，请用P 只水果供吃者使用 ， 请用 P， V原语实现爸爸 、 儿子 、 女儿三个并发进程的同步。 女儿三个并发进程的同步。
}
Father() { while (true) daugher() {p(dish); 将苹果放入盘子；v(apple);} { while (true) 将苹果放入盘子； { p(apple);从盘子取苹果； p(apple);从盘子取苹果 从盘子取苹果； } Mother() } { while (true) { p(dish);将香蕉放入盘子；v(banana);} p(dish);将香蕉放入盘子 将香蕉放入盘子； }
桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，妈妈向 桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果， 盘中放香蕉，儿子专等吃盘中的香蕉，女儿专等吃盘中的苹果。 盘中放香蕉，儿子专等吃盘中的香蕉，女儿专等吃盘中的苹果。 //dish—互斥使用盘子；apple—盘中苹果数；banana— //dish—互斥使用盘子；apple—盘中苹果数；banana—盘中香蕉数 Var dish,apple,banana:Semaphore:=1,0,0; Main() son() { while (true) { cobegin { p(banana);从盘子取香蕉； p(banana);从盘子取香蕉 从盘子取香蕉； Father();mother();son();daugher(); v(dish); Coend } 吃香蕉； 吃香蕉；}

信号量应用问题：1．写出程序描述下列前趋关系。

S1->S2, S1->S3, S2->S4, S2->S5 , S3->S6, S4->S7, S5->S7, S6->S7Var s1,s2, s3,s4:semaphore:=0, 0, 0, 0;BeginParbeginP1: begin….;V(s1);V(s1);End;P2: beginP(s1);…;V(s2);V(s2);End;P3: beginP(s1)…V(s3)End;P4: beginP(s2);…V(s4);P5: beginP(s2);..;V(s4);End;P6: beginP(s3)..V(s4)End;P7:beginP(s4);P(s4);P(s4);…End;Parendend2. 请用信号量实现4×100（4人，每人100米）接力赛的同步过程。

提示：前趋图同步问题，可设4个进程，三个信号量，进程1只设V操作，进程4只设P操作，其余进程先做P 操作再做V操作。

Var s1,s2,s3:semaphore:=0, 0, 0; BeginParbeginAthlete1: beginRun 100m;V(s1);End;Athlete2: beginP(s1)Run 100m;V(s2);End;Athlete3: beginP(s2) ;Run 100m;V(s3);End;Athlete4: beginP(s3);Run 100m;End;Parendend3．设公共汽车上，司机和售票员的活动分别是：司机：售票员：启动车辆上乘客正常行车关车门到站停车售票开车门下乘客在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？请用信号量机制实现他们的同步。

/-假定初始状态为停车状态，引入信号量Stop和Run：BEGINsemaphore Stop,Run;Stop:=Run:=0;CoBeginDriver: BEGINRepea tWa it(Run);启动车辆；正常行驶；到站停车；Si gnal(Stop);Until False;END;Conductor:BEGINRepea t上乘客；关车门；Si gnal(Run);售票；Wa it(Stop);开车门；下乘客；Until False;END;CoEnd;END;生产者消费者问题：1．桌上有一个可以容纳两个水果的盘子，每次只能放或取一个水果。

一、用P、V操作描述前趋关系。

P1、P2、P3、P4、P5、P6为一组合作进程，其前趋图如图2．3所示，试用P、V 操作描述这6个进程的同步。

p23图2．3说明任务启动后P1先执行，当它结束后P2、P3可以开始执行，P2完成后P4、P5可以开始执行，仅当P3、P4、P5都执行完后，P6才能开始执行。

为了确保这一执行顺序，设置5个同步信号量n、摄、f3、f4、g分别表示进程P1、P2、P3、P4、P5是否执行完成，其初值均为0。

这6个进程的同步描述如下：图2．3 描述进程执行先后次序的前趋图int f1=0; /*表示进程P1是否执行完成*／int f2=0; /*表示进程P2是否执行完成*／int f3=0; /*表示进程P3是否执行完成*／int f4=0; /*表示进程P4是否执行完成*／int f5=0; /*表示进程P5是否执行完成*／main(){cobeginP1( );P2( );P3( );P4( );P5( );P6( );coend}P1 ( ){┇v(f1);v(f1)：}P2 ( ){p(f1);┇v(f2);v(f2);)P3 ( ){p(f1);┇v(f3);}P4( ){p(f2);┇v(f4);}P5 ( ){p(f2);┇v(f5);}P6( ){p(f3);p(f4);p(f5);┇}二、生产者-消费者问题p25生产者-消费者问题是最著名的进程同步问题。

它描述了一组生产者向一组消费者提供产品，它们共享一个有界缓冲区，生产者向其中投放产品，消费者从中取得产品。

生产者-消费者问题是许多相互合作进程的一种抽象。

例如，在输入时，输入进程是生产者，计算进程是消费者;在输出时，计算进程是生产者，打印进程是消费者。

因此，该问题具有很大实用价值。

我们把一个长度为n的有界缓冲区(n>0)与一群生产者进程P１、P２、…、Pm和一群消费者进程C１、C２、…、Ck 联系起来，如图2．4所示。

例1: 使用多个进程计算Y=F1(X)+F2 (X).解(1)确定并发和顺序操作在这个问题中，F1(X)和F2 (X)的计算是可以并行处理的，因此F1(X)和F2 (X)可以分别出现在两个进程中。

(2)确定互斥或同步的规则在F1(X)+F2 (X)中，必须在F1(X)和F2(X)计算完毕，才能进行加法运算，因此本问题是同步问题。

(3)同步的操作流程〈进程main〉创立进程p1来计算F1(X)；创立进程p2来计算F2(X)；F1(X)计算是否完成？没有，等待；①F2(X)计算是否完成？没有，等待；②进行加法运算。

〈进程p1〉y1= F1(X)；设置F1(X)计算完成标志；③〈进程p2〉y1= F2(X)；设置F2(X)计算完成标志。

④(4)确定信号量的个数和含义根据同步规则以及操作流程确定信号量的个数是2个，S1和S2：S1含义是F1(X)计算是否完成；S2含义是F2(X)计算是否完成。

(5)确定信号量的初值S1=0；S2=0。

(6) 确定P、V操作的位置上面①处是一个P操作，P(S1)；上面②处是一个P操作，P(S2)；上面③处是一个V操作，V(S1)；上面④处是一个V操作，V(S2)。

解法1Main ( )Public y, y1, y2,. P1, P2Semaphore S1,S2{S1=0;S2=0;P1=Creat(N-F1, F1,x,……);P2=Creat(N-F2, F2, x,……);P(S1);P(S2);y=y1+y2;{y1= 计算1;V(S1)；}Procedure F2(x){y2=计算2;V(S2)}解法2Main ( )Public y, y1, y2,. P1,xSemaphore S1{ inget(x);S1=0;P1=Creat(N-F1, F1,x,……);Y2=F2(x);P(S1);y=y1+y2;}Procedure F1(x){y1= 计算1;V(S1)}采用2个进程和1个信号量来实现Y=F1(X)+F2 (X)的时候，采用的方法是父进程创立子进程，F1(X)在子进程中计算，F2 (X)在父进程中计算，因此F1(X)和F2(X)计算仍然是并发进行的。

❖ void V(semaphore &s) {
❖ s.value++;
❖ if(s.value<=0)
❖ R(s.list);
❖}
一般信号量(3)
❖ 推论1：若信号量s为正值，则该值等于在封 锁进程之前对信号量s可施行的P操作数、亦 等于s所代表的实际还可以使用的物理资源数
❖ 推论2：若信号量s为负值，则其绝对值等于 登记排列在该信号量s队列之中等待的进程个 数、亦即恰好等于对信号量s实施P操作而被 封锁起来并进入信号量s队列的进程数
一般信号量(2)
❖ typedef struct semaphore {
❖ int value;
//信号量值
❖ struct pcb *list; //信号量队列指针
❖ };
❖ void P(semaphore &s) {
❖
s.value--;
❖
if(s.value<0)
❖
W(s.list);
❖}
❖ while (true) {
//无限循环
❖
{produce an item in nextp};//生产一个产品
❖
if (counter==k) //缓冲满时，生产者睡眠
❖
sleep(producer);
❖
buffer[in]=nextp; //将一个产品放入缓冲区
❖
in=(in+1)%k; //指针推进
生产者-消费者问题算法描述(3)
❖ process consumer(void) {
❖ while (true) { //无限循环
❖ if (counter==0) //缓冲区空，消费者睡眠