Trying to understand the Peterson’s Algorithm
我试图理解彼得森的算法，我遇到了这个问题。我追踪了代码并写下了我的观察结果。请检查我的观察，我在正确的Rails上吗？
教科书上的问题：假设只有两个进程，一个
|
1
2 3 4 5 6 7 8 9 10 11 12 |
while(True) { flag[pid] = 1 turn = 1–pid while( flag[1–pid] && turn == 1–pid ); // busy wait // critical section flag[pid] = 0 |
追溯代码：
|
1
2 3 4 5 6 7 8 9 10 11 |
———- Process 0: ———- | ———- Process 1: ———-
| pid = 0 | pid = 1 flag[0] = 1 | flag[1] = 1 turn = 1 – 0 = 1 | turn = 1 – 1 = 0 | while (flag[1 – 0] | while (flag[1 – 1] && turn == (1 – 0)) | && turn == (1 – 1)) | // –> while (flag [1] && true) | // –> while (flag [0] && true) // –> while (flag [1]) | // –> while (flag [0]) |
我的观察
永远。
它的 while 循环然后它可以将它的标志设置为
其他进程不运行。因此，进程
Peterson 的算法保证对两个进程的临界区的访问没有任何饥饿。
-
flag 表示希望输入critical section 。 -
turn 被一个进程用来允许另一个完成等待并继续到critical section 。 -
当一个进程在
critical section 完成它的工作时，它表示它的愿望已经消失(flag[pid] = False )。这允许另一个人进入该部分。但是，如果一个进程由于上下文切换而在另一进程没有注意到的情况下切换它的flag 开关，它仍然必须切换它的turn 标志。
概括
Peterson 算法之所以有效，是因为每个进程都有以下心态：
所以你看，最后一切都很好。没有饥饿，每个进程都在继续进行而不被卡住，并且两个进程一遍又一遍地访问临界区。
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/269274.html