操作系统习题50521Word下载.docx
《操作系统习题50521Word下载.docx》由会员分享，可在线阅读，更多相关《操作系统习题50521Word下载.docx（28页珍藏版）》请在冰点文库上搜索。
}
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）：
吃苹果;
PV原语操作详解
PV原语通过操作信号量来处理进程间的同步与互斥的问题。
其核心就是一段不可分割不可中断的程序。
信号量的概念1965年由著名的荷兰计算机科学家Dijkstra提出，其基本思路是用一种新的变量类型（semaphore）来记录当前可用资源的数量。
semaphore有两种实现方式：
1）semaphore的取值必须大于或等于0。
0表示当前已没有空闲资源，而正数表示当前空闲资源的数量；
2）semaphore的取值可正可负，负数的绝对值表示正在等待进入临界区的进程个数。
信号量是由操作系统来维护的，用户进程只能通过初始化和两个标准原语（P、V原语）来访问。
初始化可指定一个非负整数，即空闲资源总数。
P原语：
P是荷兰语Proberen（测试）的首字母。
为阻塞原语，负责把当前进程由运行状态转换为阻塞状态，直到另外一个进程唤醒它。
操作为：
申请一个空闲资源（把信号量减1），若成功，则退出；
若失败，则该进程被阻塞；
V原语：
V是荷兰语Verhogen（增加）的首字母。
为唤醒原语，负责把一个被阻塞的进程唤醒，它有一个参数表，存放着等待被唤醒的进程信息。
释放一个被占用的资源（把信号量加1），如果发现有被阻塞的进程，则选择一个唤醒之。
P原语操作的动作是：
（1）sem减1；
（2）若sem减1后仍大于或等于零，则进程继续执行；
（3）若sem减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。
V原语操作的动作是：
（1）sem加1；
（2）若相加结果大于零，则进程继续执行；
（3）若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。
PV操作对于每一个进程来说，都只能进行一次，而且必须成对使用。
在PV原语执行期间不允许有中断的发生。
---------------------------------------------
具体PV原语对信号量的操作可以分为三种情况：
1）把信号量视为一个加锁标志位，实现对一个共享变量的互斥访问。
实现过程：
P（mutex）;
//mutex的初始值为1访问该共享数据;
V（mutex）;
非临界区;
2）把信号量视为是某种类型的共享资源的剩余个数，实现对一类共享资源的访问。
P（resource）;
//resource的初始值为该资源的个数N使用该资源；
V（resource）;
3）把信号量作为进程间的同步工具
临界区C1;
P（S）;
V（S）;
临界区C2;
举例说明：
例1：
某超市门口为顾客准备了100辆手推车，每位顾客在进去买东西时取一辆推车，在买完东西结完帐以后再把推车还回去。
试用P、V操作正确实现顾客进程的同步互斥关系。
分析：
把手推车视为某种资源，每个顾客为一个要互斥访问该资源的进程。
因此这个例子为PV原语的第二种应用类型。
semaphore
S_CartNum;
//空闲的手推车数量，初值为100
void
consumer（void）
//顾客进程
{
P（S_CartNum）;
买东西;
结帐;
V（S_CartNum）;
}
例2：
桌子上有一个水果盘，每一次可以往里面放入一个水果。
爸爸专向盘子中放苹果，儿子专等吃盘子中的苹果。
把爸爸、儿子看作二个进程，试用P、V操作使这两个进程能正确地并发执行。
爸爸和儿子两个进程相互制约，爸爸进程执行完即往盘中放入苹果后，儿子进程才能执行即吃苹果。
因此该问题为进程间的同步问题。
S_PlateNum;
//盘子容量，初值为1
S_AppleNum;
//苹果数量，初值为0
father（）
//父亲进程
{
while
（1）
{
P（S_PlateNum）;
往盘子中放入一个苹果;
V（S_AppleNum）;
son（）
//儿子进程
P（S_AppleNum）;
从盘中取出苹果;
V（S_PlateNum）;
吃苹果；
另附用PV原语解决进程同步与互斥问题的例子:
例3：
两个进程PA、PB通过两个FIFO（先进先出）缓冲区队列连接（如图）
PA从Q2取消息，处理后往Q1发消息；
PB从Q1取消息，处理后往Q2发消息，每个缓冲区长度等于传送消息长度。
Q1队列长度为n，Q2队列长度为m.假设开始时Q1中装满了消息，试用P、V操作解决上述进程间通讯问题。
//Q1队列当中的空闲缓冲区个数，初值为0
S_BuffNum_Q1;
//Q2队列当中的空闲缓冲区个数，初值为m
S_BuffNum_Q2;
//Q1队列当中的消息数量，初值为n
S_MessageNum_Q1;
//Q2队列当中的消息数量，初值为0
S_MessageNum_Q2;
PA（）
P（S_MessageNum_Q2）;
从Q2当中取出一条消息;
V（S_BuffNum_Q2）;
处理消息;
生成新的消息;
P（S_BuffNum_Q1）;
把该消息发送到Q1当中;
V（S_MessageNum_Q1）;
PB（）
P（S_MessageNum_Q1）;
从Q1当中取出一条消息;
V（S_BuffNum_Q1）;
P（S_BuffNum_Q2）;
把该消息发送到Q2当中;
V（S_MessageNum_Q2）;
例4：
《操作系统》课程的期末考试即将举行，假设把学生和监考老师都看作进程，学生有N人，教师1人。
考场门口每次只能进出一个人，进考场的原则是先来先进。
当N个学生都进入了考场后，教师才能发卷子。
学生交卷后即可离开考场，而教师要等收上来全部卷子并封装卷子后才能离开考场。
（1）问共需设置几个进程?
（2）请用P、V操作解决上述问题中的同步和互斥关系。
S_Door;
//能否进出门，初值1
S_StudentReady;
//学生是否到齐，初值为0
S_ExamBegin;
//开始考试，初值为0
S_ExamOver;
//考试结束，初值为0
int
nStudentNum=0;
//学生数目
S_Mutex1;
//互斥信号量，初值为1
nPaperNum=0;
//已交的卷子数目
S_Mutex2;
student（）
P（S_Door）;
进门;
V（S_Door）;
P（S_Mutex1）；
nStudentNum++;
//增加学生的个数
if（nStudentNum==N）
V（S_StudentReady）;
V（S_Mutex1）;
P（S_ExamBegin）;
//等老师宣布考试开始
考试中…
交卷;
P（S_Mutex2）;
nPaperNum++;
//增加试卷的份数
if（nPaperNum==N）
V（S_ExamOver）;
V（S_Mutex2）;
出门;
teacher（）
P（S_StudentReady）;
//等待最后一个学生来唤醒
发卷子;
for（i=1;
i<
=N;
i++）
V（S_ExamBegin）;
P（S_ExamOver）;
//等待考试结束
封装试卷;
例5：
某商店有两种食品A和B，最大数量均为m个。
该商店将A、B两种食品搭配出售，每次各取一个。
为避免食品变质，遵循先到食品先出售的原则。
有两个食品公司分别不断地供应A、B两种食品（每次一个）。
为保证正常销售，当某种食品的数量比另一种的数量超过k（k<
m）个时，暂停对数量大的食品进货，补充数量少的食品。
（1）问共需设置几个进程?
（2）用P、V操作解决上述问题中的同步互斥关系。
S_BuffNum_A;
//A的缓冲区个数,初值m
S_Num_A;
//A的个数，初值为0
S_BuffNum_B;
//B的缓冲区个数,初值m
S_Num_B;
//B的个数，初值为0
Shop（）
P（S_Num_A）;
P（S_Num_B）;
分别取出A、B食品各一个;
V（S_BuffNum_A）;
搭配地销售这一对食品;
//“A食品加1，而B食品不变”这种情形允许出现的次数（许可证的数量），其值等于//k-（A-B），初值为k
S_A_B;
//“B食品加1，而A食品不变”这种情形允许出现的次数（许可证的数量），其值等于//k-（B-A），初值为k
S_B_A;
Producer_A（）
生产一个A食品;
P（S_BuffNum_A）;
P（S_A_B）;
向商店提供一个A食品;
V（S_Num_A）;
V（S_B_A）;
Producer_B（）
生产一个B食品;
P（S_BuffNum_B）;
P（S_B_A）;
向商店提供一个B食品;
V（S_Num_B）;
V（S_A_B）;
例6：
在一栋学生公寓里，只有一间浴室，而且这间浴室非常小，每一次只能容纳一个人。
公寓里既住着男生也住着女生，他们不得不分享这间浴室。
因此，楼长制定了以下的浴室使用规则：
（1）每一次只能有一个人在使用；
（2）女生的优先级要高于男生，即如果同时有男生和女生在等待使用浴室，则女生优先；
（3）对于相同性别的人来说，采用先来先使用的原则。
假设：
（1）当一个男生想要使用浴室时，他会去执行一个函数boy_wants_to_use_bathroom，当他离开浴室时，也会去执行另外一个函数boy_leaves_bathroom；
（2）当一个女生想要使用浴室时，会去执行函数girl_wants_to_use_bathroom，当她离开时,也会执行函数girl_leaves_bathroom;
问题：
请用信号量和P、V操作来实现这四个函数（初始状态：
浴室是空的）。
信号量的定义：
S_mutex;
//互斥信号量，初值均为1
S_boys;
//男生等待队列，初值为0
S_girls;
//女生等待队列，初值为0
普通变量的定义：
boys_waiting=0;
//正在等待的男生数；
girls_waiting=0;
//正在等待的女生数；
using=0;
//当前是否有人在使用浴室;
boy_wants_to_use_bathroom（）
P（S_mutex）;
if（（using==0）&
&
（girls_waiting==0））
using
=
1;
V（S_mutex）;
else
boys_waiting++;
P（S_boys）;
boy_leaves_bathroom（）
if（girls_waiting
>
0）
//优先唤醒女生
girls_waiting--;
V（S_girls）;
else
if（boys_waiting
0）
boys_waiting--;
V（S_boys）;
0;
//无人在等待
girl_wants_to_use_bathroom（）
if（using==0）
girls_waiting++;
P（S_girls）;
girl_leaves_bathroom（）
升级会员 