操作系统精髓与设计原理-第5章 并发性 - 互斥和同步

第五章 并发性：互斥和同步

复习题：

5.1列出与并发相关的四种设计问题

答：进程间的交互，共享资源之间的竞争，多个进程的同步问题，对进程的处理器时间分配问题

5.2列出并发的三种上下文

答：多个应用程序，结构化应用程序，操作系统结构 5.3执行并发进程的最基本要求是什么？ 答：加强互斥的能力

5.4列出进程间的三种互相知道的程度，并简单地给出各自的定义。

答：进程间互相不知道对方：这是一些独立的进程，他们不会一起工作。进程间间接知道对方：这些进程并不需要知道对方的进程ID号，但他们共享访问某些对象，如一个I/O缓冲区。进程间直接知道对方：这些进程可以通过进程ID号互相通信，用于合作完成某些活动。 5.5竞争进程和合作进程进程间有什么区别。

答：竞争进程需要同时访问相同的资源，像磁盘，文件或打印机。合作进程要么共享访问一个共有的资源，像一个内存访问区，要么就与其他进程相互通信，在一些应用程序或活动上进行合作。

5.6列出与竞争进程相关的三种控制问题，并简单地给出各自的定义。

答：互斥：竞争进程仅可以访问一个临界资源（一次仅有一个进程可以访问临界资源），并发机制必须满足一次只有一个进程可以访问临界资源这个规则。死锁：如果竞争进程需要唯一的访问多于一个资源，并且当一个进程控制着一个进程，且在等待另一个进程，死锁可能发生。饥饿：一组进程的一个可能会无限期地拒绝进入到一个需要资源，因为其他 成员组成垄断这个资源。 5.7列出对互斥的要求。

答：1.必须强制实施互斥：在具有关于相同资源或共享对象的临界区的所有进程中，一次只允许一个进程进入临界区。2.一个在临界区停止的进程必须不干涉其他进程。3.绝不允许出现一个需要访问临界区的进程被无限延迟的情况，即不会饿死或饥饿。4.当没有进程在临界区中时，任何需要进入临界区的进程必须能够立即进入。5.对相关进程的速度和处理器的数目没有任何要求和限制。6.一个进程驻留在临界区中的时间是有限的。 5.8在信号量上可以执行什么操作。

答：1.一个信号量可以初始化成非负数。2.wait操作使信号量减1，如果值为负数，那么进程执行wait就会受阻。3signal操作使信号量增加1，如果小于或等于0，则被wait操作阻塞的进程被解除阻塞。

5.9.二元信号量与一般信号量有什么区别。

答：二元信号量只能取0或1，而一般信号量可以取任何整数。 5.10强信号量与弱信号量有什么区别。 答：强信号量要求在信号量上等待的进程按照先进先出的规则从队列中移出。弱信号量没有此规则。

5.11.什么是管程。

答：管程是由一个或多个过程，一个初始化序列和局部数据组成的软件模块。 5.12对于消息，有阻塞和无阻塞有什么区别？ 答：

5.13.通常与读者-写者问题相关联的有哪些条件？

答：1.任意多的读进程可以同时读这个文件，2.一次只有一个写进程可以往文件中写，3.如

果一个写进程正在往文件中写时，则禁止任何读进程读文件。

习题： 5.1 答：b.协同程序read读卡片，将字符赋给一个只有一个字大小的缓冲区rs然后在赋给squash协同程。协同程序Read在每副卡片图像的后面插入一个额外的空白。协同程序squash不需要知道任何关于输入的八十个字符的结构，它简单的查找成对出现的星号，然后将更改够的字符串经由只有一个字符大小的缓冲sp，传递给协同程序print。最后协同程序print简单的接受到来的字符串，并将他们打印在包含125个字符的行中。 5.2．考虑一个并发程序，它有两个进程p和q，定义如下。A.B.C.D和E是任意的原子语句。假设住程序执行两个进程的parbegin

Void p() void q() { A; { D; B; E; C; } }

答：ABCDE;ABDCE;ABDEC;ADBCE;ADBEC;ADEBC;DEABC;DAEBC;DABEC;DABCE; 5.3考虑下面的程序

const int n=50; int tally;

void total() { int count;

for(count =1;count <=n;count ++) {tally++; } }

void main() {

tally =0;

parbegin(total(),total(); write(tally);

}

答：a.随意一看,tally值的范围好像是落在[50,100]这个区间里,因为当没有互斥时可以从0直接增加到50.这一基本论点是当并发的运行这两进程时,我们不可能得到一个比连续执行单一某进程所得tally值还低的一个最终tally值.但是考虑下面由这两进程按交替顺序执行载入,增加,存储的情况,同时变更这个共享变量的取值:

1.进程A载入tally值,tally值加到1,在此时失去处理器(它已经增加寄存器的值到1,但是还没有存储这个值).

2.进程B载入tally值(仍然是0),然后运行完成49次增加操作,在它已经将49这个值存储给共享变量tally后,失去处理器控制权.

3.进程A重新获得处理器控制权去完成它的第一次存储操作(用1去代替先前的49这个tally值),此时被迫立即放弃处理器.

4.进程B重新开始,将1(当前的tally值)载入到它自己的寄存器中,但此时被迫放弃处理器(注意这是B的最后一次载入).

5.进程A被重新安排开始,但这次没有被中断,直到运行完成它剩余的49次载入,增加和存储操作,结果是此时tally值已经是50.

6.进程B在它终止前完成仅有的最后一次增加和存储操作.它的寄存器值增至2,同时存储这个值做为这个共享变量的最终结果.

一些认为会出现低于2这个值的结果,这种情况不会出现.这样tally值的正确范围是[2,100].

b.对一般有N个进程的情况下,tally值的最终范围是[2,N*50],因为对其他所有进程来说,从最初开始运行到在第五步完成.但最后都被进程B破坏掉它们的最终结果. 5.4.忙等待是否总是比阻塞等待效率低（根据处理器的使用时间）？请解释。 答：就一般情况来说是对的,因为忙等待消耗无用的指令周期.然而,有一种特殊情况,当进程执行到程序的某一点处,在此处要等待直到条件满足,而正好条件已满足,此时忙等待会立即有结果,然而阻塞等待会消耗操作系统资源在换出与换入进程上. 5.5考虑下面的程序

boolean blocked[2]; int rurn;

void P(int id) {

While (true) {

While(turn!=id); {

While(blocked[1-!id] /*do nothing*/; Turn =id; } }

Void main () {

Blocked[0]=false; Blocked[1]=false; Turn=0;

Parbegin(P(0),P(1)); }

这是【HYMA66】中提出的解决互斥问题的一种方法。请举出证明该方法不正确的一个反例。

答：考虑这种情况:此时turn=0,进程P(1)使布尔变量blocked[1]的值为true,在这时发现布尔变量blocked[0]的值为false,然后P(0)会将true值赋予blocked[0]

,此时turn=0,P(0)进入临界区,P(1)在将1赋值给turn后,也进入了临界区.

5.6解决互斥的另一种软件方法是lamport的面包店（bakery）算法，之所以起这个名字，是因为它的思想来自于面包店或其他商店中，每个顾客在到达时都得到一个有编号的票，并按票号依次得到服务，算法如下：

Boolean choosing[n]; Int number[n]; While (true)

{

Choosing[i]=true;

Number[i]=1+getmax(number[],n)； Choosing[i]=false; For(int j=0;j

While (choosing[j]) {}

While ((number[j]!=0)&&(number[j],j)<(number[i],i) {} }

/*critical section*/ Number[i]=0; /*remainder*/; }

数组choosing和number分别被初始化成false和0，每个数组的第i个元素可以由进程i读或写，但其他进程只能读。符号（a，b）<（c，d）被定义成 （a，c）或（a=c且b

答：a.当一个进程希望进入临界区时,它被分配一个票号.分配的票号是通过在目前那些等待进入临界区的进程所持票号和已经在临界区的进程所持票号比较,所得最大票号再加1得到的.有最小票号的进程有最高的优先级进入临界区.当有多个进程拥有同样的票号时,拥有最小数字号进入临界区.当一个进程退出临界区时,重新设置它的票号为0.

b.如果每个进程被分配唯一的一个进程号,那么总会有一个唯一的,严格的进程顺序.因此,死锁可以避免.

c.为了说明互斥,我们首先需要证明下面的定理:如果Pi在它的临界区,Pk已经计算出来它的number[k],并试图进入临界区,此时就有下面的关系式: ( number[i], i ) < ( number[k], k ).为证明定理,定义下面一些时间量:

Tw1:Pi最后一次读choosing[k], 当 j=k,在它的第一次等待时,因此我们在Tw1处有choosing[k] = false.

Tw2:Pi开始它的最后执行, 当j=k,在它的第二次while循环时,因此我们有Tw1 < Tw2.

Tk1:Pk在开始repeat循环时;Tk2:Pk完成number[k]的计算; Tk3: Pk设置choosing[k]为false时.我们有Tk1

因为在Tw1处,choosing[k]=false,我们要么有Tw1

5.7当按图5.2的形式使用一个专门机器指令提供互斥时，对进程在允许访问临界区之

前必须等待多久没有控制。设计一个使用testset指令的算法，且保证任何一个等待进入临界区的进程在n-1个turn内进入，n是要求访问临界区的进程数，turn是指一个进程离开临界区而另一个进程获准访问这个一个事件。

答：以下的程序由[SILB98]提供： var j: 0..n-1; key: boolean; repeat

waiting[i] := true; key := true;

while waiting[i] and key do key := testset(lock); waiting[i] := false; < critical section > j := i + 1 mod n;

while (j ≠ i) and (not waiting[j]) do j := j + 1 mod n; if j = i then lock := false else waiting := false; < remainder section > Until

这个算法用最普通的数据结构：var waiting: array [0..n – 1] of boolean Lock：boolean

这些数据结构被初始化成假的，当一个进程离开它的临界区，它就搜索waiting

的循环队列

5.8考虑下面关于信号量的定义： Void semWait(s) {

If (s.count>0) {

s.count--; } Else {

Place this process in s.queue; Block; } }

Void semSignal(s) {

If (there is at liast one process blocked on semaphore) {

Remove a process P from s.queue; Place process P on ready list; }

Else

本文来源：https://www.bwwdw.com/article/r0et.html