操作系统PV操作习题Word下载.docx
《操作系统PV操作习题Word下载.docx》由会员分享，可在线阅读，更多相关《操作系统PV操作习题Word下载.docx（71页珍藏版）》请在冰点文库上搜索。
P5（）
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;
/*对有界缓冲区进行操作的互斥信号量*／
produceri（）;
/*i=1，2，┅，m;
j=l，2，┅，k*／
consumerj（）;
produceri（）/*i=1，2，┅，m*／
while（生产未完成）
{
┇
生产一个产品;
p（empty）;
p（mutex）;
送一个产品到有界缓冲区;
v（mutex）;
v（full）;
consumerj（）/*j=1，2，…，k*／
while（还要继续消费）
p（full）;
从有界缓冲区中取产品;
v（mutex）;
v（empty）;
消费一个产品;
}
三、在操作系统中，进程是一个具有一定独立功能的程序在某个数据集上的一次
＿＿＿＿＿＿＿＿＿＿。
A．等待活动B．运行活动
C．单独操作D．关联操作
答：
B
四、多道程序环境下，操作系统分配资源以＿＿＿＿＿＿＿为基本单位。
A．程序B．指令C进程D．作业
C
五、对于两个并发进程，设互斥信号量为mutex，若mutex=O，则＿＿＿＿＿。
A.表示没有进程进入临界区
B.表示有一个进程进入临界区
C.表示有一个进程进入临界区，另一个进程等待进入
D.表示有两个进程进入临界区
六、两个进程合作完成一个任务。
在并发执行中，一个进程要等待其合作伙伴发来消
息，或者建立某个条件后再向前执行，这种制约性合作关系被称为进程的＿＿＿＿。
A.同步B．互斥C.调度D．执行
A
七、为了进行进程协调，进程之间应当具有一定的联系，这种联系通常采用进程间交换数据的方式进行，这种方式称为＿＿＿＿＿＿。
A.进程互斥B．进程同步C进程制约D．进程通信
D
八、在测量控制系统中，数据采集任务把所采集的数据送入一单缓冲区;
计算任务从该单缓冲区中取出数据进行计算。
试写出利用信号量机制实现两者共享单缓冲区的同步算法。
P33
[分析及相关知识]在本题中采集任务与计算任务共用一个单缓冲区．当采集任务采集到一个数据后，只有当缓冲区为空时才能将数据送入缓冲区中存放，否则应等待缓冲区腾空;
当缓冲区中有数据时，计算任务才能从缓冲区中取出数据进行计算，否则也应等待。
本题实际上是一个生产者—消费者问题。
将生产者—消费者问题抽象出来，以另外一种形式描述是一种常见的试题形式．只要对生产者—消费者问题有了深入的理解，就不难解决此类试题。
解;
在本题中，应设置两个信号量Sf,Se，信号量Sf表示缓冲区中是否有可供打印的计算结果，其初值为0;
信号量Se用于表示缓冲区有无空位置存放新的信息，其初值为1。
本题的同步描述如下：
intSe=l;
intSf=0;
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是否可以开始执行*／
S1（）;
S2（）;
S3（）;
S4（）;
S1（）
┇
v（b2）;
v（b3）;
}
S2（）
p（b2）;
v（b4）;
S3（）
p（b3）：
v（b4）;
S4（）
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（）
father（）;
son（）;
daughter（）：
father（）
while
（1）
p（S）;
将水果放入盘中;
if（放入的是桔子）v（So）：
elsev（Sa）;
son（）
while
（1）
p（So）;
从盘中取出桔子;
v（S）;
吃桔子;
dau[shter（）
p（Sa）;
从盘中取出苹果;
v（S）：
吃苹果;
答
十一、（华中理工大学1999年试题）设公共汽车上，司机和售票员的活动分别是：
p41
司机的活动：
启动车辆：
正常行车;
到站停车;
售票员的活动：
关车门;
售票：
开车门;
在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系?
用信号量和P、
V操作实现它们的同步。
在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：
售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客上下车。
因此司机启动车辆的动作必须与售票员关车门的动作取得同步;
售票员开车门的动作也必须与司机停车取得同步。
在本题中，应设置两个信号量：
s1、s2，s1表示是否允许司机启动汽车，其初值为0;
s2表示是否允许售票员开门，其初值为0。
用P、V原语描述如下：
ints1=O;
ints2=O;
driver（）;
busman（）;
driver（）
p（s1）;
启动车辆;
正常行车;
到站停车;
v（s2）;
busman（）
关车门;
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;
PA（）;
PB（）;
PC（）;
PA（）
从磁盘读一个记录：
p（emptyl）;
将记录存入缓冲区1;
v（fulll）：
]
PB（）
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是否执行完*／
intf3=0：
intf4=O;
intf6=0;
intf7=0;
progl（）;
prog2（）;
prog3（）;
prog4（）;
prog5（）;
prog6（）;
prog7（）;
prog8（）;
coend
progl（）
v（f1）;
v（f1）;
prog2（）
v（f2）;
prog3（）
p（f1）;
p（f2）;
v（f3）;
prog4（）
v（f4）;
prog5（）
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产品数量）<
M。
其中，N和M是正整数。
试用P、V操作描述产品A与产品B韵入库过程。
[分析及相关知识]本题给出的第一个条件是临界资源的访问控制，可用一个互斥信号量解决该问题。
第二个条件可以分解为：
-N<
A产品数量一B产品数量
A产品数量一B产品数量<
M
也就是说，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的入库过程描述如下：
/*互斥信号量*／
intsa=M-1;
intsb=N-1;
取一个产品;
if（取的是A产品）
{
p（sa）;
p（mutex）;
将产品入库;
v（mutex）;
v（sb）：
}
else/*取的产品是B*／
p（sb）;
v（pa）;
从本题的解法可以看出，当有比较复杂条件出现时，可以把复杂条件分解成一组简单条件，这样就能很容易地写出对应的程序流程了。
十六、（南开大学1997年试题）在南开大学和天津大学之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但其中有一个小的安全岛M（同时允许两辆自行车停留），可供两辆自行车已从两端进入小路情况下错车使用，如图2．14所示。
试设计一个算法使来往的自行车均可顺利通过。
p53《
错
》
[分
升级会员 