当前位置：文档之家 › 操作系统 信号量机制P、V操作习题全解

操作系统 信号量机制P、V操作习题全解

  • 格式：ppt
  • 大小：99.50 KB
  • 文档页数：32

下载文档原格式

  / 32

合集下载

信号量机制例题集2

信号量机制例题集2


爸爸,妈妈,儿子,女儿
Var mutex,apple,banana:Semaphore:=1,0,0;son() Main() { while (true) { cobegin { p(banana);从盘子取香蕉； v(mutex); Father();mother();son();daugher(); 吃香蕉；} Coend } } Father() { while (true) {p(mutex); 将苹果放入盘子；v(apple);} daugher() { while (true) } { p(apple);从盘子取苹果； v(mutex); Mother() 吃苹果；} { while (true) } { p(mutex);将香蕉放入盘子；v(banana);} } 返回
Use() { while(true) { p (full) ;
p(count) ; P(mutex2) ;
从缸中取水；
v (mutex2) ； v(empty) ； v (count) ；
} } 返回
信号量机制例题：理发师
• 理发店里有一位理发师，一把理发椅，n把 侯等待理发的顾客坐的椅子。如果没有顾 客，理发师便在理发椅上睡觉，当一个顾 客到来时，他必须叫醒理发师。如果理发 师正在理发时又有顾客来到，那么，如果 又有空椅子可坐，顾客就坐下等待，否则 就离开理发店。
Else { p(sb); p(mutex); 将产品入库； v(mutex); v(sa);
返回
信号量机制例题：阅览室
有一个阅览室，共有100个座位，读者进入 时必须在一张登记表上登记，该表为每一座 位列一表目，包括做好和读者姓名等，读者 离开时要削掉登记的信息。
阅览室
Semaphore mutex=1;seats=100;readers=0 getin() { while(true) { p(seats); p(mutex); 填写登记表； 进入阅览室读书； v(mutex); v(readers); } }
操作系统PV操作经典一百题

操作系统PV操作经典一百题

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
pv操作大题解题思路

pv操作大题解题思路

pv操作大题解题思路PV操作是指进程同步的一种经典方法，用于解决进程之间的互斥和同步问题。

在解题时，可以按照以下思路进行分析和回答：1. 什么是PV操作？PV操作是指通过对信号量进行P（Proberen）和V（Verhogen）操作来实现进程同步。

P操作用于申请资源，如果资源不可用，则进程进入等待状态；V操作用于释放资源，让等待的进程得以继续执行。

2. PV操作的作用是什么？PV操作用于解决进程之间的互斥和同步问题。

互斥是指同一时间只允许一个进程访问临界资源，而同步是指进程之间按照一定的顺序执行，避免出现竞态条件和死锁等问题。

3. PV操作的原理是什么？PV操作基于信号量（Semaphore）的概念。

信号量是一个计数器，用于控制对共享资源的访问。

P操作会将信号量的值减1，如果结果小于0，则进程进入等待状态；V操作会将信号量的值加1，如果结果小于等于0，则唤醒等待的进程。

4. PV操作的应用场景有哪些？PV操作常用于解决生产者-消费者问题、读者-写者问题、哲学家就餐问题等。

在这些场景中，通过合理使用PV操作可以实现进程之间的协调与同步，避免资源竞争和死锁。

5. PV操作有哪些特点和优势？PV操作具有以下特点和优势：互斥性，PV操作可以确保同一时间只有一个进程访问共享资源，避免数据的不一致性。

同步性，PV操作可以按照一定的顺序执行进程，避免竞态条件和死锁。

简单高效，PV操作是一种经典的进程同步方法，实现简单，高效可靠。

适用性广泛，PV操作可以应用于各种并发场景，解决不同类型的进程同步问题。

总结：PV操作是一种经典的进程同步方法，通过对信号量进行P和V 操作来实现互斥和同步。

它的应用场景广泛，可以解决生产者-消费者问题、读者-写者问题等。

PV操作具有互斥性、同步性、简单高效和适用性广泛等特点和优势。

在解题时，可以根据具体的问题场景，灵活运用PV操作，保证进程之间的协调与同步。

操作系统PV操作习题

操作系统PV操作习题

操作系统PV操作习题⼀、⽤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所⽰。

操作系统PV操作的作业参考答案

操作系统PV操作的作业参考答案

关于调度算法【例1】下表给出作业l，2，3的提交时间和运行时间。

采用先来先服务调度算法和短作业优先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进行计算。

）分析解这样的题关键是要根据系统采用的调度算法，弄清系统中各道作业随时间的推进情况。

我们用一个作业执行时间图来形象地表示作业的执行情况，帮助我们理解此题。

采用先来先服务调度算法，是按照作业提交的先后次序挑选作业，先进入的作业优先被挑选。

然后按照“排队买票”的办法，依次选择作业。

其作业执行时间图如下：采用短作业优先调度算法，作业调度时根据作业的运行时间，优先选择计算时间短且资源能得满足的作业。

其作业执行时间图如下：由于作业1，2，3是依次到来的，所以当开始时系统中只有作业1，于是作业1先被选中。

在8.0时刻，作业1运行完成，这时系统中有两道作业在等待调度，作业2和作业3，按照短作业优先调度算法，作业3只要运行1个时间单位，而作业2要运行4个时间单位，于是作业3被优先选中，所以作业3先运行。

待作业3运行完毕，最后运行作业2。

作业调度的次序是1，3，2。

另外，要记住以下公式：作业i的周转时间T i＝作业完成时间－作业提交时间系统中个作业的平均周转时间，其中Ti为作业i的周转时间。

解：采用先来先服务调度策略，则调度次序为l、2、3。

作业号提交时间运行时间开始时间完成时间周转时间1 0.0 8.0 0.0 8.0 8.02 0.4 4.0 8.0 12.0 11.63 1.0 1.0 12.0 13.0 12.0 平均周转时间T＝（8＋11.6＋12）/3＝10.53采用短作业优先调度策略，则调度次序为l、3、2。

作业号提交时间运行时间开始时间完成时间周转时间1 0.0 8.0 0.0 8.0 8.03 1.0 1.0 8.0 9.0 8.02 0.4 4.0 9.0 13.0 12.6 平均周转时间T＝（8＋8＋12.6）/3＝9.53思考题1请同学们判断这句话：作业一旦被作业调度程序选中，即占有了CPU。

信号量地PV操作(例题)

信号量地PV操作(例题)

？？？信号量的PV操作是如何定义的？试说明信号量的PV操作的物理意义。

参考答案：P（S）：将信号量S减1，若结果大于或等于0，则该进程继续执行；若结果小于0，则该进程被阻塞，并将其插入到该信号量的等待队列中，然后转去调度另一进程。

V（S）：将信号量S加1，若结果大于0，则该进程继续执行；若结果小于或等于0，则从该信号量的等待队列中移出一个进程，使其从阻塞状态变为就绪状态，并插入到就绪队列中，然后返回当前进程继续执行。

PV操作的物理含义：信号量S值的大小表示某类资源的数量。

当S>0时，其值表示当前可供分配的资源数目；当S<0时，其绝对值表示S信号量的等待队列中的进程数目。

每执行一次P操作，S值减1，表示请求分配一个资源，若S≥0，表示可以为进程分配资源，即允许进程进入其临界区；若S<0，表示已没有资源可供分配，申请资源的进程被阻塞，并插入S的等待队列中，S的绝对值表示等待队列中进程的数目，此时CPU将重新进行调度。

每执行一次V操作，S值加1，表示释放一个资源，若S>0，表示等待队列为空；若S≤0，则表示等待队列中有因申请不到相应资源而被阻塞的进程，于是唤醒其中一个进程，并将其插入就绪队列。

无论以上哪种情况，执行V操作的进程都可继续运行。

1、设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆；正常行车；到站停车；售票员的活动：关车门；售票；开车门；在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。

设两个信号量S和C，初值为S＝0；C＝0；司机： L1：正常行车售票员： L2：售票到站停车 P（S）V（S）开车门P（C）关车门启动开车 V（C）GO TO L1 GO TO L22、请用PV操作实现他们之间的同步关系：（1）桌上一个盘子，只能放一只水果。

爸爸放苹果，妈妈放桔子，儿子只吃桔子，女儿只吃苹果。

（2）桌上一个盘子，只能放一只水果。

P、V操作习题答案

P、V操作习题答案

信号量应用问题：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．桌上有一个可以容纳两个水果的盘子，每次只能放或取一个水果。

PV习题

PV习题

信号量与PV操作P操作：S=S-1若S>=0,则该进程继续运行若S<0,则进程被阻塞，并将它插入信号量S的等待队列中V操作S=S+1若S>0则进程继续运行若S<=0,则从信号量的等待队列中唤醒第一个进程，使其变为就绪状态，然后返回原进程继续执行。

信号量的应用互斥模型(S初值为1)进程P1 进程P2P(S) P(S)CS1 CS2V(S) V(S)同步模型（S初值设为0）进程P1 进程P2L1:P(S) L2:V(S)例一．在某展示厅设置一个自动计数系统，以计数器count表示在场的人数，count是动态变化的，若有一个人进入展示厅进程pin对计数器count加1，当有一个人退出展示厅时，进程pout实现计数器减1由于进、出所以展示厅的人是随机的，用P-V操作实现。

（并发进程之间的互斥问题）解：定义信号量：S：表示是否有进程进入临界区，初值为1.（表示没有进程进入临界区）begincount: Integer;S: semaphore;count:=0;S:=1;cobeginprocess Pin:beginP(S);count:=count+1;V(S);end;process Pout:beginP(S);count:=count-1;V(S);end;coend;例二．与生产者和消费过者相似的问题，把“A进程将记录送入缓冲器”看成生产者生产了一件物品且把物品存入缓冲器，把“B进程从缓冲器中取出记录并加工”看作是消费者从缓冲器取出物品去消费，缓冲器中只能放一个记录（一件物品），用P-V操作实现。

（并发进程之间的同步问题）解：定义两个信号量为：sp和sg。

sp:表示生产者是否右以把物品存入缓冲器。

由于缓冲器只能存放一个物品，因此sp的初值为1，即sp:=1。

sg：表示缓冲是否存有物品，它的初值应该为0，即sg：=0，表示缓冲器中还没有物品存在。

生产者和消费者两个进程并发执行时，可按以下的方式实现同步例三．如果一个生产者和一个消费共享缓冲器容量为可以存放n件物品时，生产者总可继续存入物品；同时当缓冲器的物品不为“0”时，消费者总可从缓冲器中取走物品，用P-V操作实现。

计算机操作系统PV操作例题

计算机操作系统PV操作例题

问题1 一个司机与售票员的例子在公共汽车上，为保证乘客的安全，司机和售票员应协调工作：停车后才能开门，关车门后才能行车。

用PV操作来实现他们之间的协调。

S1：是否允许司机启动汽车的变量S2：是否允许售票员开门的变量driver()//司机进程{while (1)//不停地循环{P(S1);//请求启动汽车启动汽车;正常行车；到站停车；V(S2); //释放开门变量，相当于通知售票员可以开门}}busman()//售票员进程{while(1){关车门;V(S1)；//释放开车变量，相当于通知司机可以开车售票P(S2)；//请求开门开车门；上下乘客；}}注意：busman() driver() 两个不停循环的函数问题2 图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。

要几个程序？有多少个进程？（答：一个程序；为每个读者设一个进程）（1）当图书馆中没有座位时，后到的读者在图书馆为等待（阻塞）（2）当图书馆中没有座位时，后到的读者不等待，立即回家。

解（1 )设信号量：S=100; MUTEX=1P(S)P(MUTEX)登记V(MUTEX)阅读P(MUTEX)注销V(MUTEX)V(S)解(2)设整型变量COUNT=100;信号量：MUTEX=1;P(MUTEX);IF (COUNT==0){ V(MUTEX);RETURN;}COUNT=COUNT-1;登记V(MUTEX);阅读P(MUTEX);COUNT=COUNT+1;V(MUTEX);RETURN;问题3 有一座东西方向的独木桥；用P,V操作实现：（1）每次只允许一个人过桥；（2）当独木桥上有行人时，同方向的行人可以同时过桥，相反方向的人必须等待。

（3）当独木桥上有自东向西的行人时，同方向的行人可以同时过桥，从西向东的方向，只允许一个人单独过桥。

（此问题和读者与写者问题相同,东向西的为读者，西向东的为写者）。

（1）解设信号量MUTEX=1P (MUTEX)过桥V (MUTEX)(2)解设信号量：MUTEX=1 (东西方互斥)MD=1 (东向西使用计数变量互斥)MX=1 (西向东使用计数变量互斥)设整型变量：CD=0 (东向西的已上桥人数)CX=0 (西向东的已上桥人数)从东向西：P (MD)IF (CD=0){P (MUTEX) }CD=CD+1V (MD)过桥P (MD)CD=CD-1IF (CD=0){V (MUTEX) }V (MD)从西向东：P (MX)IF (CX=0){P (MUTEX) }CX=CX+1V (MX)过桥P (MX)CX=CX-1IF (CX=0){V (MUTEX) }V (MX)(3) 解：从东向西的，和（2）相同；从西向东的和（1）相同。

计算机操作系统习题及答案

计算机操作系统习题及答案

第4章进程同步与通信1）选择题（1）在操作系统中，P 、V 操作是一种工（2）若信号量S 的初值为2,当前值为-1,则表示有.B —等待进程。

A. 0个B. l 个C. 2个D. 3个（3）在直接通信方式中，系统提供两条通信原语进行发送和接收，其中Send 原语中参数应是_C_。

A. sender ， messageB. sender ， mailboxC. receiver ， messageD. receiver ， mailbox（4）下述那个选项不是管程的组成部分A 。

A.管程外过程调用管程内数据结构的说明B.管程内对数据结构进行操作的一组过程C.局部于管程的共享数据说明D.对局部于管程的数据结构设置初值的语句（5）某通信方式通过共享存储区来实现，其属于D 。

A.消息通信B.低级通信C.管道通信D.高级通信（6）用P 、V 操作管理临界区时，信号量的初值应定义为C 。

A. -1B. 0C. 1D.任意值（7）临界区是B 。

A. 一个缓冲区B. 一段程序C. 一段共享数据区D. 一个互斥资源（8）信箱通信是一种D 通信方式。

A.直接通信B.信号量C.低级通信D.间接通信（9）对于两个并发进程，设互斥信号量为mutex ，若mutex=0则 A 。

A.表示有一个进程进入临界区B.表示没有进程进入临界区C.表示有一个进程进入临界区，另一个进程等待进入D.表示有两个进程进入临界区（10）对信号量S 执行V 操作后，下述选项正确的是C 。

A.当S 小于等于0时唤醒一个阻塞进程B.当S 小于0时唤醒一个阻塞进程C.当S 小于等于0时唤醒一个就绪进程D.当S 小于0时唤醒一个就绪进程（11）在消息缓冲通信中，消息队列属于A 资源。

A.机器指令C.作业控制命令 B.系统调用命令D.低级进程通信原语A.临界B.共享C.永久D.可剥夺（12）在消息缓冲通信机制中，使用的临界资源是_屋。

A.信箱B.消息队列中的某个缓冲区C.管道D.整个消息队列2)填空题(1)信号量的物理意义是：当信号量值大于0时表示可用资源的个数；当信号量值小于0 时，其绝对值为等待该信号量的进程数。

考研P、V操作习题

考研P、V操作习题

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

S1->S2, S1->S3, S2->S4, S2->S5 , S3->S6, S4->S7, S5->S7, S6->S72. 请用信号量实现4×100（4人，每人100米）接力赛的同步过程。

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

3．设公共汽车上，司机和售票员的活动分别是：司机：售票员：启动车辆上乘客正常行车关车门到站停车售票开车门下乘客在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？请用信号量机制实现他们的同步。

生产者消费者问题：1．桌上有一个可以容纳两个水果的盘子，每次只能放或取一个水果。

爸爸放苹果妈妈放橘子，两个儿子吃苹果，两个女儿吃橘子。

试用信号量和P、V操作，编写实现爸爸、妈妈、儿子和女儿的并发工作程序。

2、有一个仓库存放两种零件A和B，最大库容量各为m个。

有一车间不断地取A和B进行装配，每次各取一个。

为了避免零件锈蚀，遵循线入库者先出库的原则。

有两组供应商分别不断地供应A和B（每次一个），为保证齐套和合理库存，当某种零件的数量比另一种数量超过n（n<m）个时，暂停对数量大的零件的进货，集中补充数量少的零件。

试用P、V操作正确实现之。

3、有一个仓库，可以存放A和B两种产品，仓库的存储空间足够大，但要求：每次只能存入一种产品（X或Y）； -N<A产品数量-B产品数量<M。

其中，N和M时正整数。

试用“存放A”、“存放B”和P、V 操作描述产品A与产品B的入库过程。

A-B<M说明：如果只放A不放B，则A 最多可放M-1个，如果多放一个B，则可以多放一个A。

B-A<N说明：如果只放B不放A，则B 最多可放N-1个，如果多放一个A，则可以多放一个B。

V(Mutex);读者写者问题：1、多个进程共享一个文件，其中只读文件的程值为读者，其余只写文件的称为写者。

计算机操作系统P V操作


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 } 吃香蕉； 吃香蕉；}

信号量及P、V操


分析
通过分析可知，ＣＰ、ＩＯＰ必须遵守以下 同步规则： • 当ＣＰ进程把计算结果送入缓冲区时，IOP 进程才 能从缓冲区中取出结果去打印; • 当IOP进程把缓冲区中的数据取出打印后， ＣＰ进程才能把下一个计算结果送入缓冲 区
解
• 为此设有两个信号量Sa=0，Sb=1，Sa表示缓冲区 中有无数据，Sb表示缓冲区中有无空位置。 • 两个进程的同步可以描述如下：
总结 进程互斥： 进程互斥：在OS中，当某一进程正在访问cs时，就不 允许其它进程来读写(访问)，否则就会发 生后果无法估计的错误，进程之间的这种 相互制约关系为进程互斥。 进程同步： 进程同步： 并发进程在一些关键点上可能需要互相等 待与互通消息，这种相互制约的等待与互 通消息，称为进程同步。
进程同步与互斥关系： 进程同步与互斥关系 ： 都反映了在异步环境下并发 进程间的相互制约关系。可归于同步范 畴，但互斥是同步问题的一个特例，互 斥解决临界区的使用，同步是并发进程 在一些关键点上需互相等待互发消息。
解
（1）定义二个信号量S1、S2，初值均为1， 即：S1=1，S2=1。其中进程A和C使用 信号量S1，进程B和D使用信号量S2。 （2）从[1]到[8]分别为：P(S1) V(S1) P(S2) 2 [1] [8] P(S1) V(S2) P(S1) V(S1) P(S2) V(S2)
【思考题】
【思考题】
• 四个进程A、B、C、D都要读一个共享文件F， 系统允许多个进程同时读文件F。但限制是 进程A和进程C不能同时读文件F，进程B和 进程D也不能同时读文件F。为了使这四个进 程并发执行时能按系统要求使用文件，现用 PV操作进行管理，请回答下面的问题：
• (1)应定义的信号量及初值： • （2）在下列的程序中填上适当的P、V操作，以 保证它们能正确并发工作： • A() B() C() D() • { { { { • [1]; [3]; [5]; [7]; • read F; read F; read F; read F; • [2]; [4]; [6]; ，S2，初值均为0。 司机进程： 司机进程： while(1) { P(S1) 启动车辆 正常驾驶 到站停车 V(S2) }… 售票 员 进程 ： while(1) { 关门 V(S1) 售票 P(S2) 开门

操作系统题目与答案

. '. 某车站售票厅任何时刻最多可容纳20名购票者进入，当售票厅少于20名购票者时，则厅外的购票者可以立即进入，否则需要在外面等待。

若把一个购票者看作一个进程，请回答下列问题：（1）用P ，V 操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。

（2）根据所定义的信号量，把应该执行的P ，V 操作填入下述程序中，以保证进程能够正确地并发执行。

（3）若欲购票者最多为N 个大，写出信号量可能的变化范围（最大值和最小值）1）定义信号量S ，初值为20。

S>0，S 的值表示可继续进入售票厅的人数； S=0，表示售票厅已有20名购票者； S<0，|S|的值为等待进入售票厅的人数。

2、COBEGIN PROCESS PI （I=1，2，…） Begin 进入售票厅； 购票； 退出； End COEND 例题：某工厂有一个可以存放设备的仓库，总共可以存放8台设备。

生产部门生产的每一台设备都必须入库。

销售部门可以从仓库提出设备供应客户。

设备的入库和出库都必须借助运输工具。

现只有一套运输工具，每次只能运输一台设备。

请设计一个能协调工作的调度管理系统。

（1）定义信号量，说明各信号量的含义并赋初值：mutex ，full ，empty ：semaphore; mutex ：=1;运输工具是否空闲，初值为1 empty ：=8;仓库中尚可存放多少设备，初值为8 full ：＝0;仓库中的设备数，初值为0 （2）PV 操作实现如下begin mutex ，full ，empty ：semaphore; mutex ：=1;empty ：=8;full ：＝0; cobegin ． processor producer processor consumer begin begin 生产设备； P （full ）; P （empty ）; P （mutex ）; P （mutex ）; 将设备从仓库取出； 将设备送入仓库； V （mutex ）; V （mutex ）; V （empty ）; V （full ）; 把设备销售给用户； end; end; coend; end ． 例题：设在公共汽车上，司机和售票员的活动分别是：司机：启动车辆，正常行车，到站停车。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
get paper and tobacco; signal (done); }
smoker2 () /* has paper */ while(1) { wait (TobaccoMatch);
get tobacco and match; signal (done); } Smoker3 () /* has match */ while(1) { wait (PaperMatch); get paper and match; signal (done); }
•
• get process: while (1) {
read data; wait (empty1); wait (s1)
put data into buffer1 //因为是单缓，故无in指针，可写为 // buffer1=x; signal (s1) signal (full1) }
• Copy process: while (1) {
– 进程A专门拣黑子，进程B专门拣白子；
– 每个进程每次只拣一个子，当一个进程在拣 子时不允许另一个进程去拣子；
– 当一个进程拣了一个棋子（黑子或白子）以 后，必须让另一个进程拣一个棋子（黑子或 白子），并要求A进程首先开始。
• 定义两个同步信号量s1,s2;
• 因为要求进程A先开始，故S1初值为1；s2初 值为0；
• Put process: while(1) {
wait (full2) wait (s2)
get data from buffer2 // z=buffer2 signal (s2) signal (empty2)
print data on printer }
• 3.在一个箱子里混装有数量相等的黑色围棋子 和白色围棋子，现要用自动分拣系统把黑子和 白子分开，该系统由两个并发执行的进程组成， 功能如下：
Process 营业员 while(TRUE)
{ P(s1); V(service); // 叫号； 为顾客提供服务；
}
• 5. 三个进程P1、P2、P3互斥使用一个包含 N（N>0）个单元的缓冲区。P1每次用 produce()生成一个正整数并用put()送入 缓冲区某个空单元中；P2每次用getodd() 从该缓冲区中取出一个奇数并用countodd() 统计奇数个数；P3每次用geteven()从该缓 冲区中取出一个偶数并用counteven()统计 偶数个数。请用信号量描述三个进程的同步 与互斥活动，并说明定义信号量的含义。
• 对buffer的互斥信号mutex＝1
• P1生产，P2消费奇数，一对同步信号量 odd=0, empty=N；
• P1生产，P2消费偶数一对同步信号量 even=0, empty=N；
• P1进程： int num; while（1）{ num=produce(); P(empty); P(mutex); put(); V(mutex); if (num%2) V(odd); else V(even);
• Pro
• 等待叫号；
• 获得服务；
•}
• Process 营业员
• while(TRUE)
•{
•
叫号；
•
为顾客提供服务；
•}
• 请用P、V操作实现上述过程中的互斥与 同步。说明信号量的含义并赋初值。
• 两个互斥互斥关系： • 一台叫号机－－mutex＝1 • 10个座位－－ empty＝10
} •
P2进程： While（1）{
P(odd); P(mutex); getodd(); V(mutex); V(empty); Countodd(); }
• P3进程： • While（1）{ • P(even); • P(mutex); • geteven(); • V(mutex); • V(empty); • Counteven(); •}
put match and tobacco; signal (MatchTabacco);
}
else { put paper and match; signal (PaperMatch);
} Smaker1 () /* has match */ while(1) { wait (PaperTobacco);
• 要求说明每个信号量是用于解决什么互斥、 什么同步关系的。
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; 为一对
6. 在某餐馆里有一个收银员，且同时最多 允许有30个顾客就餐，我们可以将顾客 和收银员看成是两类不同的进程。
为了利用PV操作正确地协调这两类进程之 间的工作，设置了四个信号量S1、S2、 S3和Sn，且初值分别为1、0、0和30。
有三个同步关系： ①收银员忙，顾客等－－－S1 ②无人付款，收银员等－－S2 ③收银员收完钱，顾客可以离开－－－S3 一个互斥关系：30张餐桌－－－Sn
• 东边要过桥的车：
•
P(stop);
•
P(mutex1);
•
Count1++;
•
If (count1==1) P(wait);
•
V(mutex1);
•
V(stop);
•
{过桥}
•
P(mutex1);
•
Count1--
•
If (count1==0) V(wait);
•
V(mutex1);
• 西边要过桥的车
wait (empty); put data into buffer; //单缓，无in指针，可写为 buffer＝x
signal (full);}
• 计算进程: • While(1){
wait (full); get data from buffer;
// 单缓，无out指针，可写为 y=buffer signal (empty);
• 顾客进程： while (1) {
p(sn); eat;
v(sn); p(s1);
pay; v(s2); p(s3) leave; }
收银员进程： do { p(s2); get the money; v(s1); v(s3); } while(1);
7．独木桥问题：东西方向汽车过独木桥， 为了保证安全，只要桥上无车，则允许 一方的汽车过桥，待一方的汽车全部通 过后，另一方的汽车才允许过桥。但， 当另一方提出过桥时，要阻止对方未上 桥的后继车辆，待桥面上的汽车过完桥 后，另一方的汽车开始过桥。适用信号
• 进程A while（1）{ P(s1); 拣黑子；
V(s2); }
进程B： while（1）{
P(s2); 拣白子；
V(s1); }
• 4. 某银行提供一个服务窗口和10个等待的座 位。顾客到达银行时，若有空座位，则到取号 机上领取一个号，等待叫号。取号机每次允许 一位顾客使用。当营业员空闲时，通过叫号选 取一位顾客，并为其服务。顾客和营业员的活 动描述如下：
• 两个同步关系： • 有顾客营业员才叫号s1=0 • 营业员先叫号，顾客才能被服务service
＝0
• Process 顾客 i：
• { P (empty);
• P(mutex);
• 从取号机获取一个号码；
• V(mutex);
• V(s1);
• P(service); //等待叫号;
• V (empty); • 获得服务； •}
• 针对一个smoker与agent有两个同步关 系：
• 1）agent放了两样东西，smoker才能 抽烟－－－三个信号量
• 2）smoker把桌上东西拿走，agent才 能再放－－－信号量done，初值为1
semaphore PaperTobacco= 0; TobaccoMatch= 0; PaperMatch= 0; done =1;
• 1. 在测量控制系统中的数据采集任务时， 把采集的数据送一个单缓冲区；计算任务 从该缓冲区中取出数据进行计算。利用信 号量实现两者共享缓冲区的同步算法。
• 1. 是producer-consumer问题的简化版 • semphore empty=1, full=0 • 信号量初值必须说明 • 采集进程: • while(1){
wait (full1) wait (s1)
copy data from buffer1 //单缓,无out指针，可写y=buffer1 signal (s1) signal (empty1) wait (empty2) wait (s2)
put data into buffer2 // buffer2=y signal(s2) signal (full2) }
•}
• 2. 从读卡机上读进N张卡片，然后复制一份， 要求复制出来的卡片与读进的卡片完全一样。 该任务由三个进程get，copy和put及两个 缓冲区buffer1和buffer2完成。进程get的 功能是把一张卡片的信息从读卡机读入 buffer1；进程copy是把buffer1中的信息 复制到buffer2;进程put的功能是取出 buffer2中的信息并从打印机上打印。
量和P，V操作写出汽车过独木桥问题的 同步算法。并说明每个信号量的含义。
• Seamphore stop,wait,mutex1,mutex2; • Stop=1;mutex1=1;mutex2=1;wait=1; • Int counter1=0,counter2=0; • Mutex1互斥信号量，用于锁counter1。 • Mutex2互斥信号量，用于锁counter2。 • stop 用于提出过桥请求。 • wait用于排队过桥，即用于给桥加锁。