同步互斥word文档良心出品.docx
《同步互斥word文档良心出品.docx》由会员分享，可在线阅读，更多相关《同步互斥word文档良心出品.docx（19页珍藏版）》请在冰点文库上搜索。
同步互斥word文档良心出品
同步与互斥
学习指导：
互斥与同步是操作系统与并发程序设计的核心问题，为此操作系统必须提供用于实现同步的机制。
从本质上来说，同步工具就是能用于进程（线程）等待或唤醒的机制，目前实现的同步机制各有特点。
学习这一部分不仅需要确切地理解并牢固地记住各种同步机制的定义，更重要的是学会使用各种同步机制去解决实际同步问题。
如何使用同步机制解决各种同步问题，需要通过典型例子分析和学习，并通过一定数量的练习提高解题技巧。
习题解答：
1.何谓与时间有关的错误?
举例说明之。
答：
并发进程的执行实际上是进程活动的某种交叉，某些交叉次序可能得到错误结果。
由于具体交叉的形成与进程的推进速度有关，而速度是时间的函数，因而将这种错误称为与时间有关的错误。
例如，两个并发进程的程序如下：
intn=0;
main（）{
创建进程A；
创建进程B；
}；
A（）{
while
（1）{
n++;
}
};
B（）{
while
（1）{
睡眠一段时间；
printf（“%d”,n）;
n=0;
}
};
假设进程A被部署在公园入口的终端上，用来记录一段时间内进入公园的人数，进程B被部署在公园的控制中心，用来输出一段时间内进入公园的总人数。
进程A和进程B共享全局变量n，n表示记录下的人数。
如果在进程B执行完打印语句后被进程A打断，进程A执行了若干次变量自增语句，之后进程B接着执行清0语句，那么进程A对n的累加丢失了，相当于进程B被打断的这段时间内进入公园的人没有被记录下来。
发生与时间有关的错误。
2.有人说，假设两个进程之间没有共享内存，则二者之间没有公共变量，这种说法准确吗?
说明原因。
答：
如果只从用户空间考虑，这种说法是正确的。
但从操作系统的角度来说并不准确。
两个没有公共内存的用户进程可能同时（宏观）进入操作系统，并访问操作系统空间中的公共变量。
3.何谓忙式等待?
是否还有其它方式的等待?
比较它们之间的联系和差别。
答：
不进入等待状态的等待称为忙式等待。
另一种等待方式是阻塞式等待，进程得不到共享资源时将进入阻塞状态，让出CPU给其他进程使用。
忙等待和阻塞式等待的相同之处在于进程都不具备继续向前推进的条件，不同之处在于处于忙等待的进程不主动放弃CPU，尽管CPU可能被剥夺，因而是低效的；而处于阻塞状态的进程主动放弃CPU，因而是高效的。
4.下列进程互斥方法哪些存在忙式等待问题?
（1）软件:
面包店算法
（2）硬件:
TS指令（3）关中断指令
答：
（1）、
（2）存在忙等待问题。
5.为何开关中断进程互斥方法仅在单CPU系统中是有效的？
答：
关中断方法不适用于多CPU系统，因为关中断只能保证CPU不由一个进程切换到另外一个进程，从而防止多个进程并发地进入公共临界区域。
但即使关中断后，不同进程仍可以在不同CPU上并行执行关于同一组共享变量的临界区代码。
6.在多处理机系统中，软件互斥方法是否有效？
为什么？
答：
依然有效。
多处理机并行与单处理并发之间的差别在于程序交叉的粒度，单处理机机环境中进程交叉发生在指令之间，多处理机环境中进程交叉发生在指令周期之间。
由于纯软件互斥算法并不依赖特殊的硬件指令（如test_and_set），指令之间的交叉与指令周期之间的交叉结果相同。
7.试分析临界区域的大小与系统并发性之间的关系。
答：
关于同一组变量的临界区域是不能并发执行的代码，临界区越大，并发性越差，因而编写并发程序应尽量缩小临界区域范围。
8.设CR1是关于一组共享变量SV1的临界区域，CR2是关于另外一组共享变量SV2的临界区域，当进程P1进入CR1时，进程P2是否可以进入CR2?
为什么?
答：
可以。
因为互斥是在变量级别上的，多个进程同时进入关于不同变量的临界区不会引起与时间有关的错误。
9.Lamport面包店互斥算法是否会出现饿死情况?
不会，该算法是公平的。
假定系统中共有n个进程，每个想要进入临界区域的进程（线程）在最坏的情况下需要等待其它n-1个进程进入并离开临界区域之后即可获得进入临界区域的机会，因而存在（忙式）等待的上界。
10.试用信号灯和PV操作实现临界区语句:
region<共享变量>do<语句>
变量类型<共享变量>
答：
semaphores=1;
P（s）;
<语句>
V（s）;
11.由V操作唤醒的进程是否一定能够直接进入运行状态?
举例说明之。
答：
否。
一般来说，唤醒是将进程状态由等待状态变成就绪状态，而就绪进程何时获得处理机则是由系统的处理机调度策略确定的。
如果采用抢占式优先级调度算法，并且被唤醒的进程是当前系统中优先级最高的进程，那么该进程将被调度执行，其状态变成运行态。
如果该进程不是系统中优先级最高的进程或系统采用其它调度算法，那么该进程不会被调度执行，其状态将维持在就绪态。
12.设S1和S2为两个信号灯变量，下列八组P、V操作哪些可以同时进行?
哪些不能同时进行?
为什么?
（1）P（S1），P（S2）
（2）P（S1），V（S2）
（3）V（S1），P（S2）（4）V（S1），V（S2）
（5）P（S1），P（S1）（6）P（S2），V（S2）
（7）V（S1），P（S1）（8）V（S2），V（S2）
答：
能同时进行的包括：
（1）、
（2）、（3）、（4）。
这些操作涉及不同信号灯变量，属于关于不同组共享变量的临界区。
不能同时进行的包括：
（5）、（6）、（7）、（8）。
这些操作涉及相同的信号灯变量，属于关于同一组共享变量的临界区。
13.对于生产者—消费者问题，假设缓冲区是无界的，试用信号灯与PV操作给出解法。
答：
由于是无界缓冲区，所以生产者不会因得不到缓冲区而被阻塞，不需要对空缓冲区进行管理，可以去掉在有界缓冲区中用来管理空缓冲区的信号量及其PV操作。
semaphoremutex_in=1;
semaphoremutex_out=1;
semaphoreempty=0;
intin=0，out=0;
生产者活动：
while
（1）{
producenextproduct;
P（mutex_in）;
addtheproducttobuffer[in];
in++;
v（mutex_in）;
V（empty）;
}
消费者活动：
while
（1）{
P（empty）;
P（mutex_out）;
taketheproductfrombuffer[out];
out++;
V（mutex_out）;
}
14.设有一个可以装A、B两种物品的仓库，其容量无限大，但要求仓库中A、B两种物品的数量满足下述不等式:
-M≤A物品数量－B物品数量≤N
其中M和N为正整数。
试用信号灯和PV操作描述A、B两种物品的入库过程。
答：
已知条件-M≤A物品数量－B物品数量≤N可以拆成两个不等式，即
A物品数量－B物品数量≤N，
B物品数量－A物品数量≤M。
这两个不等式的含义是：
仓库中A物品可以比B物品多，但不能超过N个；Ｂ物品可以比A物品多，但不能超过M个。
semaphorea=n;
semaphoreb=m;
voidmain（）{
createprocess（A,…）;
createprocess（B,…）;
}
A物品入库：
voidA（）{
while
（1）{
P（a）;
A物品入库;
V（b）;
}
}
B物品入库：
voidB（）{
while
（1）{
P（b）;
B物品入库;
V（a）;
}
}
15.试用信号灯与PV操作实现司机与售票员之间的同步问题。
设公共汽车上有一个司机和一个售票员，其活动如下图所示。
为了安全起见，显然要求:
（1）关车门后方能启动车辆；
（2）到站停车后方能开车门。
亦即“启动车辆”这一活动应当在“关车门”这一活动之后，“开车门”这一活动应当在“到站停车”这一活动之后。
解：
如果进程P2尚未推进到②处时，进程P1已经推进到①处，则P1应等待直到P2推进到②处为止；同样，如果进程P1尚未推进到③处时，进程P2已经推进到④处，则P2应等待直到P1推进到③处为止。
如果进程P1在①处发生了等待，则当进程P2执行到②处时应将P1唤醒；同样，如果进程P2在④处发生了等待，则当进程P2执行到③处时应将P1唤醒。
用信号量和P、V操作解决这一问题，需要定义两个信号量，一个信号量start表示是否允许司机启动车辆，另一个信号量open表示是否允许售票员开车门。
初始状态是车停在始发站，车门开着，等待乘客上车。
因此，两个信号量的初值都是0。
semaphorestart=0;
semaphoreopen=0;
司机的活动:
P1:
do{
P（start）;
启动车辆;
正常行车;
到站停车;
V（open）;
}while
（1）;
售票员的活动:
P2:
do{
关车门;
V（start）;
售票;
P（open）;
开车门;
}while
（1）;
16.设有A、B、C三组进程，它们互斥地使用某一独占型资源R，使用前申请，使用后释放。
资源分配原则如下:
（1）当只有一组申请进程时，该组申请进程依次获得R；
（2）当有两组申请进程时，各组申请进程交替获得R，组内申请进程依次获得R；
（3）当有三组申请进程时，各组申请进程轮流获得R，组内申请进程依次获得R。
试用信号灯和PV操作分别给出各组进程的申请活动程序段和释放活动程序段。
解：
intfree=1;//设备状态标志
semaphoremutex=1;
semaphoreqa=qb=qc=0;//各组等待队列
intcounta=countb=countc=0;//等待队列长度
A组申请：
P（mutex）;
if（free==1）{
free=0;
V（mutex）;
}
else{
counta++;
V（mutex）;
P（qa）;
}
A组释放：
P（mutex）;
if（countb>0）{
countb--;
V（qb）;
}else{
if（countc>0）{
countc--;
V（qc）;
}else{
if（counta>0）{
counta--
V（qa）;
}else{
free=1;
}
}
}
}
仿A组进程活动可以给出B组和C组进程活动。
17.设自行车生产线上有一只箱子，其中有N个位置（N≥3），每个位置可存放一个车架或一个车轮;又设有三个工人，其活动分别为:
工人1活动：
do{
加工一个车架;
车架放入箱中;
}while
（1）
工人2活动：
do{
加工一个车轮;
车轮放入箱中;
}while
（1）
工人3活动：
do{
箱中取一车架;
箱中取二车轮;
组装为一台车;
}while
（1）
试分别用信号灯与PV操作、管程、会合实现三个工人的合作，要求解中不含死锁。
解：
用信号灯与PV操作实现三个工人的合作，管程与会合解法可仿照给出。
首先不考虑死锁问题，工人1与工人3、工人2与工人3构成生产者与消费者关系，这两对生产/消费关系通过共同的缓冲区相联系。
从资源的角度来看，箱子中的空位置相当于工人1和工人2的资源，而车架和车轮相当于工人3的资源。
定义三个信号灯如下：
semaphoreempty=N;//空位置
semaphorewheel=0;//车轮
semaphoreframe=0;//车架
三位工人的活动分别为：
工人1活动：
do{
加工一个车架;
P（empty）;
车架放入箱中;
V（frame）;
}while
（1）
工人2活动：
do{
加工一个车轮;
P（empty）;
车轮放入箱中;
V（wheel）;
}while
（1）
工人3活动：
do{
P（frame）;
箱中取一车架;
V（empty）;
P（wheel）;
P（wheel）;
箱中取二车轮;
V（empty）;
V（empty）;
组装为一台车;
}while
（1）
分析上述解法易见，当工人1推进速度较快时，箱中空位置可能完全被车架占满或只留有一个存放车轮的位置，而当此时工人3同时取2个车轮时将无法得到，而工人2又无法将新加工的车轮放入箱中；当工人2推进速度较快时，箱中空位置可能完全被车轮占满，而当此时工人3取车架时将无法得到，而工人1又无法将新加工的车架放入箱中。
上述两种情况都意味着死锁。
为防止死锁的发生，箱中车架的数量不可超过N-2，车轮的数量不可超过N-1，这些限制可以用两个信号灯来表达。
semaphores1=N-2;
semaphores2=N-1;
如此，可以给出不含死锁的完整解法如下：
工人1活动：
do{
加工一个车架;
P（s1）;
P（empty）;
车架放入箱中;
V（frame）;
}while
（1）
工人2活动：
do{
加工一个车轮;
P（s2）;
P（empty）;
车轮放入箱中;
V（wheel）;
}while
（1）
工人3活动：
do{
P（frame）;
箱中取一车架;
V（empty）;
V（s1）;
P（wheel）;
P（wheel）;
箱中取二车轮;
V（empty）;
V（empty）;
V（s2）;
V（s2）;
组装为一台车;
}while
（1）
详细描述还应考虑对箱子单元的描述以及访问互斥问题。
建议车架放在箱子的一端，车轮放在箱子的另一端，车架与车轮都采用后进先出的管理方式。
18.一座小桥（最多只能承重两个人）横跨南北两岸，任意时刻同一方向只允许一人过桥，南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。
试用信号灯和PV操作写出南、北两岸过桥的同步算法。
解：
桥上可能没有人，也可能有一人，也可能有两人。
桥上有两人时的情形如下：
北岸
北岸
北岸
桥中间
南岸
南岸
南岸
（a）两人同时过桥（b）两人都到中间（c）南（北）来者到北（南）段
共需要三个信号量，load用来控制桥上人数，初值为2，表示桥上最多有2人；north用来控制北段桥的使用，初值为1，用于对北段桥互斥；south用来控制南段桥的使用，初值为1，用于对南段桥互斥。
semaphoreload=2;
semaphorenorth=1;
semaphoresouth=1;
tosouth（）{
P（load）;
P（north）;
过北段桥;
到桥中间;
V（north）;
P（south）;
过南段桥;
到达南岸
V（south）;
V（load）;
}
tonorth（）{
P（load）;
P（south）;
过南段桥;
到桥中间
V（south）;
P（north）;
过北段桥;
到达北岸
V（north）;
V（load）;
}
19.某寺庙，有小和尚、老和尚若干．庙内有一水缸，由小和尚提水入缸，供老和尚饮用。
水缸可容纳30桶水，每次入水、取水仅为1桶，不可同时进行。
水取自同一井中，水井径窄，每次只能容纳一个水桶取水。
设水桶个数为5个，试用信号灯和PV操作给出老和尚和小和尚的活动。
semaphoreempty=30;//表示缸中目前还能装多少桶水，初始时能装30桶水
semaphorefull=0;//表示缸中有多少桶水，初始时缸中没有水
semaphorebuckets=5;//表示有多少只空桶可用，初始时有5只桶可用
semaphoremutex_well=1;//用于实现对井的互斥操作
semaphoremutex_bigjar=1;//用于实现对缸的互斥操作
young_monk（）{
while
（1）{
P（empty）;
P（buckets）;
gotothewell;
P（mutex_well）;
getwater;
V（mutex_well）;
gotothetemple;
P（mutex_bigjar）;
purethewaterintothebigjar;
V（mutex_bigjar）;
V（buckets）;
V（full）;
}
}
old_monk（）{
while（）{
P（full）;
P（buckets）;
P（mutex_bigjar）;
getwater;
V（mutex_bigjar）;
drinkwater;
V（buckets）;
V（empty）;
}
}
20.设系统中有5台类型相同的打印机，依次编号为1～5。
又设系统中有n个使用打印机的进程，使用前申请，使用后释放。
每个进程有一个进程标识，用于区别不同的进程。
每个进程还有一个优先数，不同进程的优先数各异。
当有多个进程同时申请时，按照进程优先数由高到低的次序实施分配。
试用信号灯和PV操作实现对于打印机资源的管理，即要求编写如下函数和过程:
（1）函数require（pid，pri）:
申请一台打印机。
参数pid为进程标识，其值为1到n的整数;pri为进程优先数，其值为正整数;函数返回值为所申请到打印机的编号，其值为1到5的整数;
（2）过程return（prnt）:
释放一台打印机。
参数prnt为所释放打印机的编号，其值为1到5的整数。
解：
#defineN5
boolflag[N+1];//flag[0]表示可用打印机数,
//flag[i]表示第i号打印机的状态（1<=i<=N），0表示占用，1表示空闲
PCB*queue=NULL;//进程阻塞队列
semaphoremutex_flag=1;//用于对flag数组的互斥操作
semaphoremutex_queue=1;//用于对阻塞队列的互斥操作
process（inti,intpriority）{
intprint;
print=require（i,priority）;
useprint;
return（print）;
}
intrequire（intpid,intpriority）{
P（mutex_flag）;
if（flag[0]>0）{
flag[0]--;
for（inti=1;iif（flag[i]==1）{
flag[i]=0;
break;
}
V（mutex_flag）;
returni;
}
else{
V（mutex_flag）;
p（mutex_queue）;
将进程pid按其优先数插入到等待队列queue中；
V（mutex_queue）;
}
}
return（intprint）{
P（mutex_flag）;
if（queue==NULL）{
flag[0]++;
flag[print]=1;
V（mutex_flag）;
}
else{
V（mutex_flag）;
p（mutex_queue）;
将print分配给queue队首进程；
queue下移；
V（mutex_queue）;
}
}
21.试用管程实现单一资源的管理。
解：
TYPEsingle_resource=MONITOR;
Varstate:
（free,used）;//资源状态
q:
condition;//等待队列
definerequire,release;
PROCEDURErequire;
BEGIN
IFstate=usedTHEN
wait（q）;
state:
=used;
END;
PROCEDURErelease;
BEGIN
state:
=free;
signal（q）;
END;
BEGINstate:
=freeEND;
22.虽然管程是互斥进入的，但管程中定义的外部子程序必须是可再入的，试说明原因。
答：
管程互斥是在变量级别的，同一管程类型可以有多个实例，而管程内部子程序只在管程类型定义时生成一套代码，为保障对不同管程变量的操作具有相同语义，管程外部子程序必须是可再入的。
23.编写一个管程，使得调用进程能够等待若干指定时间单位（ticks）．可以假定有一个硬件实时钟，每隔一个tick时间单位调用该管程一次。
解：
两个外部过程：
sleep用于进程等待指定时间，tick用于时钟中断记数和唤醒等待进程。
TYPEsleep_interval=MONITOR;
Varcount:
integer;//tick计数
q:
condition;//等待队列
definesleep,tick;
PROCEDUREsleep（interval:
integer）;
BEGIN
count:
=interval
wait（q）;
END;
PROCEDUREtick;
BEGIN
count:
=count-1;
IFcount=0THEN
signal（q）;
END;
BEGINEND;
24.管程与会合这两种同步机制之间的主要差别何在?
答：
管程与会合都属于集中式结构化同步机制，但二者的实现机理完全不同。
管程是被动性语言成分，管程本身不能占有处理机，管程外部子程序是由调用进程占有处理机执行的。
会合是主动性语言成分，一个任务调用另一任务中的入口时，入口代码是由被调用任务自己占有处理机执行的。
25.试用会合给出读写问题的解法，要求写者优先．
解：
定义一个任务，包含如下四个入口：
start_read,finish_read,start_write,finish_write。
该问题的关键是：
strat_write的入口条件不应考虑当前读者情况，当会合发生后再判断当前是否有读者，并与其finish_read会合。
这里显然需要accept语句的嵌套。
taskreaders_and_writersis
start_read;
finish_read;
start_write;
finish_write;
endreaders_and_writers;
taskbodyreaders_and_writersis
read_count,write_count:
integer;
read_count:
=0;
write_count:
=0;
loop
select
whenwrite_count=0=>
acceptstart_readdo
read_count:
=read_count+1;
endstart_read
orwhenread_count>0=>
acceptfinish_re
升级会员 