问题描述

Consider the following program:var flag: array[0..1]of boolean;turn:0..1;procedure P(id:integer);beginrepeatflag[id]:=true;while turn<>id dobeginwhile flag[1-id] do {nothing}turn:=idend;<Critical section>flag[id]:=false;<Remainder>until falseend;beginflag[0]:=false;flag[1]:=false;turn:=0;parbeginP(0); P(1)parend;end.

This is a software solution to the mutual exclusion problem proposed by Hyman. Find a counter example to demonstrate that this solution is incorrect. It is interesting to note that even the Communication of the ACM was fooled on this one.

这个关于互斥的算法设计中有问题，请找出。

分析

问题出在等待对方退出和交换turn并不是原子性的。上述伪代码第10-12行。

while flag[1-id] do {nothing}turn:=id

如当turn=0，flag[0]=true，P(0)已经进入临界区时，P(1)时间片内需要在while处忙等，直到某一时刻P(0)退出临界区，此时跳出while循环。若刚好在此时P(1)时间片用完，则不会执行turn:=id，此时turn=0。当时间片分给再次P(0)时，P(0)直接进入临界区，若时间片用完P(0)并未退出临界区，且处理器又将时间片分给P(1)，P(1)执行turn=id后也将进入临界区。此时P(0)和P(1)同时进入临界区，不能满足互斥性。