操作系统习题07546.docx
《操作系统习题07546.docx》由会员分享，可在线阅读，更多相关《操作系统习题07546.docx（28页珍藏版）》请在冰点文库上搜索。
操作系统习题07546
六、两个进程合作完成一个任务。
在并发执行中，一个进程要等待其合作伙伴发来消
息，或者建立某个条件后再向前执行，这种制约性合作关系被称为进程的＿＿＿＿。
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）：
吃苹果;
}
}
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操作使这两个进程能正确地并发执行。
分析：
爸爸和儿子两个进程相互制约，爸爸进程执行完即往盘中放入苹果后，儿子进程才能执行即吃苹果。
因此该问题为进程间的同步问题。
解：
semaphore S_PlateNum; //盘子容量，初值为1
semaphore S_AppleNum; //苹果数量，初值为0
void father（） //父亲进程
{
while
（1）
{
P（S_PlateNum）;
往盘子中放入一个苹果;
V（S_AppleNum）;
}
}
void son（） //儿子进程
{
while
（1）
{
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
semaphore S_BuffNum_Q1;
//Q2队列当中的空闲缓冲区个数，初值为m
semaphore S_BuffNum_Q2;
//Q1队列当中的消息数量，初值为n
semaphore S_MessageNum_Q1;
//Q2队列当中的消息数量，初值为0
semaphore S_MessageNum_Q2;
void PA（）
{
while
（1）
{
P（S_MessageNum_Q2）;
从Q2当中取出一条消息;
V（S_BuffNum_Q2）;
处理消息;
生成新的消息;
P（S_BuffNum_Q1）;
把该消息发送到Q1当中;
V（S_MessageNum_Q1）;
}
}
void PB（）
{
while
（1）
{
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操作解决上述问题中的同步和互斥关系。
解：
semaphore S_Door; //能否进出门，初值1
semaphore S_StudentReady; //学生是否到齐，初值为0
semaphore S_ExamBegin; //开始考试，初值为0
semaphore S_ExamOver; //考试结束，初值为0
int nStudentNum=0; //学生数目
semaphore S_Mutex1; //互斥信号量，初值为1
int nPaperNum=0; //已交的卷子数目
semaphore S_Mutex2; //互斥信号量，初值为1
void 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）;
P（S_Door）;
出门;
V（S_Door）;
}
void teacher（）
{
P（S_Door）;
进门;
V（S_Door）;
P（S_StudentReady）; //等待最后一个学生来唤醒
发卷子;
for（i=1;i<=N;i++）
V（S_ExamBegin）;
P（S_ExamOver）; //等待考试结束
封装试卷;
P（S_Door）;
出门;
V（S_Door）;
}
例5：
某商店有两种食品A和B，最大数量均为m个。
该商店将A、B两种食品搭配出售，每次各取一个。
为避免食品变质，遵循先到食品先出售的原则。
有两个食品公司分别不断地供应A、B两种食品（每次一个）。
为保证正常销售，当某种食品的数量比另一种的数量超过k（k
（1）问共需设置几个进程?
（2）用P、V操作解决上述问题中的同步互斥关系。
解：
semaphore S_BuffNum_A; //A的缓冲区个数,初值m
semaphore S_Num_A; //A的个数，初值为0
semaphore S_BuffNum_B; //B的缓冲区个数,初值m
semaphore S_Num_B; //B的个数，初值为0
void Shop（）
{
while
（1）
{
P（S_Num_A）;
P（S_Num_B）;
分别取出A、B食品各一个;
V（S_BuffNum_A）;
V（S_BuffNum_A）;
搭配地销售这一对食品;
}
}
//“A食品加1，而B食品不变”这种情形允许出现的次数（许可证的数量），其值等于//k-（A-B），初值为k
semaphore S_A_B;
//“B食品加1，而A食品不变”这种情形允许出现的次数（许可证的数量），其值等于//k-（B-A），初值为k
semaphore S_B_A;
void Producer_A（）
{
while
（1）
{
生产一个A食品;
P（S_BuffNum_A）;
P（S_A_B）;
向商店提供一个A食品;
V（S_Num_A）;
V（S_B_A）;
}
}
void Producer_B（）
{
while
（1）
{
生产一个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操作来实现这四个函数（初始状态：
浴室是空的）。
解：
信号量的定义：
semaphore S_mutex; //互斥信号量，初值均为1
semaphore S_boys; //男生等待队列，初值为0
semaphore S_girls; //女生等待队列，初值为0
普通变量的定义：
int boys_waiting=0; //正在等待的男生数；
int girls_waiting=0;//正在等待的女生数；
int using=0; //当前是否有人在使用浴室;
void boy_wants_to_use_bathroom（）
{
P（S_mutex）;
if（（using==0）&&（girls_waiting==0））
{
using = 1;
V（S_mutex）;
}
else
{
boys_waiting++;
V（S_mutex）;
P（S_boys）;
}
}
void boy_leaves_bathroom（）
{
P（S_mutex）;
if（girls_waiting > 0） //优先唤醒女生
{
girls_waiting--;
V（S_girls）;
}
else if（boys_waiting > 0）
{
boys_waiting--;
V（S_boys）;
}
else
using = 0; //无人在等待
V（S_mutex）;
}
void girl_wants_to_use_bathroom（）
{
P（S_mutex）;
if（using==0）
{
using = 1;
V（S_mutex）;
}
else
{
girls_waiting++;
V（S_mutex）;
P（S_girls）;
}
}
void girl_leaves_bathroom（）
{
P（S_mutex）;
if（girls_waiting > 0） //优先唤醒女生
{
girls_waiting--;
V（S_girls）;
}
else if（boys_waiting > 0）
升级会员 