操作系统PV操作习题.docx

操作系统PV操作习题.docx

《操作系统PV操作习题.docx》由会员分享，可在线阅读，更多相关《操作系统PV操作习题.docx（70页珍藏版）》请在冰点文库上搜索。

操作系统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描述进程执行先后次序的前趋图

intf1=0;/*表示进程P1是否执行完成*／

intf2=0;/*表示进程P2是否执行完成*／

intf3=0;/*表示进程P3是否执行完成*／

intf4=0;/*表示进程P4是否执行完成*／

intf5=0;/*表示进程P5是否执行完成*／

main（）

{

cobegin

P1（）;

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所示。

假定这些生产者和消费者是互相等效的。

只要缓冲区未满，生产者就可以把产品送入缓冲区，类似地，只要缓冲区未空，消费者便可以从缓冲区中取走物品并消耗它。

生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品，也禁止消费者从空的缓冲区中提取物品。

图2．4生产者-消费者问题

为解决这一类生产者-消费者问题，应该设置两个同步信号量，一个说明空缓冲单元的

数目，用empty表示，其初值为有界缓冲区的大小n，另一个说明满缓冲单元的数目，用

full表示，其初值为0。

在本例中有P１、P２、…、Pm个生产者和C１、C２、…、Ck个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。

由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需设置一个互斥信号量mutex，其初值为1。

生产者-消费者问题的同步描述如下：

intfull=O;/*满缓冲单元的数目*／

intempty=n;/*空缓冲单元的数目*／

intmutex=1;/*对有界缓冲区进行操作的互斥信号量*／

main（）

{

cobegin

produceri（）;/*i=1，2，┅，m;j=l，2，┅，k*／

consumerj（）;

coend

}

produceri（）/*i=1，2，┅，m*／

{

while（生产未完成）

{

┇

生产一个产品;

p（empty）;

p（mutex）;

送一个产品到有界缓冲区;

v（mutex）;

v（full）;

）

}

consumerj（）/*j=1，2，…，k*／

{

while（还要继续消费）

{

p（full）;

p（mutex）;

从有界缓冲区中取产品;

v（mutex）;

v（empty）;

┇

消费一个产品;

}

}

三、在操作系统中，进程是一个具有一定独立功能的程序在某个数据集上的一次

＿＿＿＿＿＿＿＿＿＿。

A．等待活动B．运行活动

C．单独操作D．关联操作

答：

B

四、多道程序环境下，操作系统分配资源以＿＿＿＿＿＿＿为基本单位。

A．程序B．指令C进程D．作业

答：

C

五、对于两个并发进程，设互斥信号量为mutex，若mutex=O，则＿＿＿＿＿。

A.表示没有进程进入临界区

B.表示有一个进程进入临界区

C.表示有一个进程进入临界区，另一个进程等待进入

D.表示有两个进程进入临界区

答：

B

六、两个进程合作完成一个任务。

在并发执行中，一个进程要等待其合作伙伴发来消

息，或者建立某个条件后再向前执行，这种制约性合作关系被称为进程的＿＿＿＿。

A.同步B．互斥C.调度D．执行

答：

A

七、为了进行进程协调，进程之间应当具有一定的联系，这种联系通常采用进程间交换数据的方式进行，这种方式称为＿＿＿＿＿＿。

A.进程互斥B．进程同步C进程制约D．进程通信

答：

D

八、在测量控制系统中，数据采集任务把所采集的数据送入一单缓冲区;计算任务从该单缓冲区中取出数据进行计算。

试写出利用信号量机制实现两者共享单缓冲区的同步算法。

P33

[分析及相关知识]在本题中采集任务与计算任务共用一个单缓冲区．当采集任务采集到一个数据后，只有当缓冲区为空时才能将数据送入缓冲区中存放，否则应等待缓冲区腾空;当缓冲区中有数据时，计算任务才能从缓冲区中取出数据进行计算，否则也应等待。

本题实际上是一个生产者—消费者问题。

将生产者—消费者问题抽象出来，以另外一种形式描述是一种常见的试题形式．只要对生产者—消费者问题有了深入的理解，就不难解决此类试题。

解;在本题中，应设置两个信号量Sf,Se，信号量Sf表示缓冲区中是否有可供打印的计算结果，其初值为0;信号量Se用于表示缓冲区有无空位置存放新的信息，其初值为1。

本题的同步描述如下：

intSe=l;

intSf=0;

main（）

{

cobegin

get（）;

compute（）;

coend

}

get（）

{

while（采集工作未完成）

{

采集一个数据：

p（Se）;

将数据送入缓冲区中;

v（Sf）;

}

}

compute（）

{

while（计算工作未完成）

{

p（Sf）;

从缓冲区中取出数据;

v（Se）;

进行数据计算;

}

}

九、图2．7给出了四个进程合作完成某一任务的前趋图，试说明这四个进程间的同步关系，并用P、V操作描述它。

P35

图2．7四个合作进程的前趋图

解：

图2．7说明任务启动后S1先执行。

当S1结束后，S2、S3可以开始执行。

S2、S3

完成后，S4才能开始执行。

为了确保这一执行顺序，设三个同步信号量b2、b3、b4分别

表示进程S2、S3、S4是否可以开始执行，其初值均为0。

这四个进程的同步描述如下：

intb2=0;/*表示进程S2是否可以开始执行*／

intb3=0;/*表示进程S3是否可以开始执行*／

intb4=0;/*表示进程S4是否可以开始执行*／

main（）

{

cobegin

S1（）;

S2（）;

S3（）;

S4（）;

coend

}

S1（）

{

┇

v（b2）;

v（b3）;

}

S2（）

{

p（b2）;

┇

v（b4）;

}

S3（）

{

p（b3）：

┇

v（b4）;

}

S4（）

{

p（b4）;

p（b4）;/*因在S2及S3完成时均对b4做了v操作，因此这里要用两个p操作*／

┇

}

十、桌上有一空盘，允许存放一只水果。

爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。

规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。

P37

[分析及相关知识]在本题中，爸爸、儿子、女儿共用一个盘子，且盘中一次只能放一个水果．当盘子为空时，爸爸可将一个水果放入果盘中。

若放入果盘中的是桔子，则允许儿子吃，女儿必须等待;若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。

本题实际上是生产者—消费者问题的一种变形。

这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。

解：

在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值

为1;信号量So表示盘中是否有桔子，其初值为0;信号量Sa表示盘中是否有苹果，其初

值为0。

同步描述如下：

intS=1;

intSa=O：

intSo=O：

main（）

{

cobegin

father（）;

son（）;

daughter（）：

coend

}

father（）

{

while

（1）

{

p（S）;

将水果放入盘中;

if（放入的是桔子）v（So）：

elsev（Sa）;

}

）

son（）

{

while

（1）

{

p（So）;

从盘中取出桔子;

v（S）;

吃桔子;

}

}

dau[shter（）

{

while

（1）

{

p（Sa）;

从盘中取出苹果;

v（S）：

吃苹果;

}

}

答 

十一、（华中理工大学1999年试题）设公共汽车上，司机和售票员的活动分别是：

p41

司机的活动：

启动车辆：

正常行车;

到站停车;

售票员的活动：

关车门;

售票：

开车门;

在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系?

用信号量和P、

V操作实现它们的同步。

解;在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：

售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客上下车。

因此司机启动车辆的动作必须与售票员关车门的动作取得同步;售票员开车门的动作也必须与司机停车取得同步。

在本题中，应设置两个信号量：

s1、s2，s1表示是否允许司机启动汽车，其初值为0;s2表示是否允许售票员开门，其初值为0。

用P、V原语描述如下：

ints1=O;

ints2=O;

main（）

{

cobegin

driver（）;

busman（）;

coend

}

driver（）

{

while

（1）

{

p（s1）;

启动车辆;

正常行车;

到站停车;

v（s2）;

}

}

busman（）

{

while

（1）

{

关车门;

v（s1）;

售票;

p（s2）;

开车门;

上下乘客;

}

}

用P、V操作来控制现实生活中的操作流程是一类常见的试题。

这类试题要求解题者

能将生活中的控制流程用形式化的方式表达出来。

十二、设有一个发送者进程和一个接收者进程，其流程图如图2．10所示。

s是用于实现进程同步的信号量，mutex是用于实现进程互斥的信号量。

试问流程图中的A、B、C、D四框中应填写什么?

假定缓冲区有无限多个，s和mutex的初值应为多少?

p42

[分析及相关知识]由图2．10可以看出，发送者进程与接收者进程之间的同步关系是：

发送者进程生成的信息送入消息链中，接收者进程从消息链中接收信息;由于发送者进程产生一个消息并链入消息链后用V操作增加消息计数并唤醒接收者进程，这表示发送者进程和接收者进程是通过信号量s实现同步的，因此接收者进程应该在取信息之前先使用一个P操作来查看消息链上是否有消息，若无消．息则阻塞自己;另外，发送者和接收者对消息链的访问应使用信号量进行互斥，即在访问前使用P操作，在访问后使用V操作。

图2．10发送者及接收者工作流程图

解：

由上述分析可知，A、B、C、D四框应分别填入：

A框P（mutex）

B框V（mutex）

C框P（s）

D框P（mutex）

开始时，消息链上没有可供接收的信息，所以s的初值为0;互斥信号量mutex的初值应为1。

十三、（北京大学1990年试题）p46

①写出P、V操作的定义。

②有三个进程PA、PB和PC合作解决文件打印问题：

PA将文件记录从磁盘读入主存

的缓冲区1，每执行一次读一个记录;PB将缓冲区1的内容复制到缓冲区2，每执行一次

复制一个记录：

PC将缓冲区2的内容打印出来，每执行一次打印一个记录。

缓冲区的大小等于一个记录大小。

请用P、V操作来保证文件的正确打印。

[分析及相关知识]信号量是一个确定的二元组（s，q），其中s是一个具有非负初值的整型变量，q是一个与s相关联的初始状态为空的队列．整型变量s表示系统中某类资源的数目，当其值大于0时，表示系统中当前可用资源的数目;当其值小于0时，其绝对值表示系统中因请求谊类资源而被阻塞的进程数目．除信号量的初值外，信号量的值仅能由P操作和V操作改变。

解：

①P、V操作是两条原语，它们的定义如下：

P操作P操作记为P（S），其中S为一信号量，它执行时主要完成下述动作：

S=S-1

若S≥0，则进程继续运行。

若S<0，则该进程被阻塞，并将它插入该信号量的等待队列中。

V操作V操作记为V（S），S为一信号量，它执行时主要完成下述动作：

S=S+1

若S>0，则进程继续执行。

若S≤0，则从信号量等待队列中移出队首进程，使其变为就绪状态。

②在本题中，进程PA、PB、PC之间的关系为：

PA与pB共用一个单缓冲区，而PB

又与PC共用一个单缓冲区，其合作方式可用图2．12表示。

当缓冲区1为空时，进程PA可将一个记录读入其中;若缓冲区1中有数据且缓冲区2为空，则进程PB可将记录从缓冲区1复制到缓冲区2中;若缓冲区2中有数据，则进程PC可以打印记录。

在其他条件下，相应进程必须等待。

事实上，这是一个生产者-消费者问题。

图2．12进程间的合作方式

为遵循这一同步规则。

应设置四个信号量emptyl、empty2、full1、full2，信号量emptyl

及empty2分别表示缓冲区1及缓冲区2是否为空，其初值为1;信号量full1及full2分别表示缓冲区1及缓冲区2是否有记录可供处理，其初值为0。

其同步描述如下：

intemptyl=l;

intempty2=l;

intfulll=O;

intfull2=O;

main（）

{

cobegin

PA（）;

PB（）;

PC（）;

coend

}

PA（）

{

while

（1）

{

从磁盘读一个记录：

p（emptyl）;

将记录存入缓冲区1;

v（fulll）：

}

]

PB（）

{

while

（1）

{

p（fulll）;

从缓冲区1中取出记录;

v（emptyl）;

p（empty2）;

将记录存入缓冲区2;

v（full2）;

}

}

PC（）

{

while

（1）

{

p（full2）;

从缓冲区2中取出记录;

v（empty2）;

打印记录;

}

}

本题也是一个典型的生产者。

消费者问题。

其中的难点在于PB既是‘个生产者又是一个消费者。

十四、设有8个程序progl、prog2、…、prog8。

它们在并发系统中执行时有如图2．13所示的制约关系，试用P、V操作实现这些程序间的同步。

P48

解：

由图2．13表明开始时，progl及prog2先执行。

当progl和prog2都执行完后，prog3、

prog4、prog5才可以开始执行。

prog3完成后，prog6才能开始执行。

prog5完成后，prog7

才能开始执行。

prog6、prog4、prog7都结束后，prog8才可以开始执行。

为了确保这一执行顺序，设7个同步信号量f1、…、f7分别表示程序progl、…、prog7是否执行完，其初值均为0。

这8个进程的同步描述如下：

intfi=0;/*表示程序progl是否执行完*／

intf2=0;

intf3=0：

intf4=O;

intf5=0;

intf6=0;

intf7=0;

main（）

{

cobegin

progl（）;

prog2（）;

prog3（）;

prog4（）;

prog5（）;

prog6（）;

prog7（）;

prog8（）;

coend

}

progl（）

{

┇

v（f1）;

v（f1）;

v（f1）;

）

prog2（）

{

┇

v（f2）;

v（f2）;

v（f2）;

）

prog3（）

{

p（f1）;

p（f2）;

┇

v（f3）;

）

prog4（）

{

p（f1）;

p（f2）;

┇

v（f4）;

}

prog5（）

{

p（f1）;

p（f2）;

┇

v（f5）;

）

prog6（）

{

p（f3）;

┇

v（f6）;

}

prog7（）

{

p（f5）;

┇

v（f7）;

}

prog8（）

{

p（f4）;

p（f6）;

p（f7）;

┇

}

十五、（北京大学1991年试题）有一个仓库，可以存放A和B两种产品，但要求：

（1）每次只能存入一种产品（A或B）;p50

（2）-N<（A产品数量一B产品数量）

其中，N和M是正整数。

试用P、V操作描述产品A与产品B韵入库过程。

[分析及相关知识]本题给出的第一个条件是临界资源的访问控制，可用一个互斥信号量解决该问题。

第二个条件可以分解为：

-N

A产品数量一B产品数量

也就是说，A产品的数量不能比B产品的数量少N个以上，A产品的数量不能比B产品的数量多M个以上．

解;在本题中，我们可以设置两个信号量来控制A、B产品的存放数量，sa表示当前允许A产品比B产品多入库的数量，即在当前库存量和B产品不入库的情况下，还可以允许sa个A产品入库;sb表示当前允许B产品比A产品多入库的数量，即在当前库存量和A产品不入库的情况下，还可以允许sb个B产品入库。

初始时，sa为M一1，sb为N一1，

当往库中存放入一个A产品时，则允许存入B产品的数量也增加1;当往库中存放入一个B产品时，则允许存入A产品的数量也增加1。

产品A、B的入库过程描述如下：

intmutex=1;/*互斥信号量*／

intsa=M-1;

intsb=N-1;

main（）

{

while

（1）

{

取一个产品;

if（取的是A产品）

{

p（sa）;

p（mutex）;

将产品入库;

v（mutex）;

v（sb）：

}

else/*取的产品是B*／

{

p（sb）;

p（mutex）;

将产品入库;

v（mutex）;

v（pa）;

}

}

}

从本题的解法可以看出，当有比较复杂条件出现时，可以把复杂条件分解成一组简单条件，这样就能很容易地写出对应的程序流程了。

十六、（南开大学1997年试题）在南开大学和天津大学之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但其中有一个小的安全岛M（同时允许两辆自行车停留），可供两辆自行车已从两端进入小路情况下错车使用，如图2．14所示。

试设计一个算法使来往的自行车均可顺利通过。

p53《 错 》

[分