以下是我们讲座中介绍的Peterson's solution:
//P0:
do {
flag[0] = TRUE; turn = 1;
while(flag[1] && turn == 1);
//Critical section
flag[0] = FALSE;
//remainder section
} while(1)
//P1:
do {
flag[1] = TRUE; turn = 0;
while(flag[0] && turn == 0);
//critical section
flag[1] = FALSE;
//remainder section
} while(1)
turn变量本身不是已经保证了临界区的要求吗?像这里的flag[]
似乎没有必要。
2条答案
按热度按时间xiozqbni1#
flag
数组为每个进程指定它当前是否对临界区感兴趣(即它当前是否希望进入临界区或已经在临界区中)。假设进程#0希望进入临界区,它必须知道进程#1当前是否也对临界区感兴趣,因为进程#0必须根据进程#1是否也对临界区感兴趣而不同地动作。
如果进程#1对临界区不感兴趣,则进程#0不应等待进程#1将
turn
设置为0
,因为它可能无限期地等待这一情况发生,这将违反“进度”和“有界等待”要求。如果进程#1**对临界段感兴趣,则进程#0应等待进程#1执行以下任一操作
flag[1]
设置为false
来指示临界区),或者turn
设置为0
来指示)的产量。否则,就会违反“相互排斥”的规定。
sdnqo3pr2#
虽然公认的答案很好地解释了Peterson的算法,并证明了为什么需要
turn
和flag
,但也可以通过尝试从算法中删除flag
变量,同时保留关键属性mutual exclusion, progress, and bounded waiting,以更“实际操作”的方式执行此分析。仅仅删除所有带有
flag
的语句会留下一个明显的问题,例如,如果P0设置了turn=1
并在turn==1
时开始等待,那么它将无限期地等待,除非P1设置了turn=0
,因此“progress”属性丢失。让我们尝试通过将
turn
设置为“my”值来修复它(对于P0为“0”,对于P1为“1”),并等待直到turn
具有“我的”值。这显然需要在退出临界区时将turn
设置为“其他”进程的值(否则,“其他”进程可能在其while
循环中无限期等待,从而丢失“有界等待”属性):但这并不能保证“互斥”属性:当例如P0在其临界区中时,P1可以愉快地设置
turn=1
并且前进到其临界区。所吸取的教训是:在并发性方面要非常小心。到处都有出错的机会,在编码时很难发现错误,而且以后更难排 debugging 误。只要有可能,就采用成熟的方法,如彼得森算法,这些方法经过多年的彻底分析和优化。