[科普中国]-Szymanski算法

Szymanski算法是由计算机科学家Boleslaw Szymanski博士设计的互斥算法，它具有许多有利的性质，包括线性等待，和扩展解决了Leslie Lamport发布的开放问题是否存在每个过程具有恒定通信位数的算法，其满足Lamport所设想的每个合理的公平性和容错性要求（Lamport的解决方案使用n因子通信变量与Szymanski的5）。

算法该算法模拟在一个有入口和出口的候诊室。入口门最初打开，出口门关闭。 请求大致在同一时间进入临界区的所有过程进入候诊室; 最后一个关闭了入口门并打开了出口门。 然后，过程逐个进入临界区（如果临界区允许，则进入较大的组）。 离开关键部分的最后一个过程关闭出口门并重新打开入口门，因此下一批过程可能会进入。

实现包括每个进程都有一个标志变量，该变量由该进程写入并由所有其他进程读取（这种单写入器属性对于高效的高速缓存使用是合乎需要的）。 通过读取所有过程的标志来计算入口门的状态。 伪码如下：

#Entry protocolflag[self] ← 1 await(all flag[1..N] ∈ {0, 1, 2})flag[self] ← 3 #Standing in doorwayif any flag[1..N] = 1: flag[self] ← 2 #Waiting for other processes to enter await(any flag[1..N] = 4)flag[self] ← 4 #The door is closedawait(all flag[1..self-1] ∈ {0, 1}) await(all flag[self+1..N] ∈ {0, 1, 4}) #Ensure everyone in the waiting room has #realized that the door is supposed to be closedflag[self] ← 0请注意，“所有”和“任何”测试的顺序必须是统一的。

尽管有直观的解释，但该算法并不容易证明是正确的，但由于其有利的性质，需要证明其正确性，并且已经提出了多个证据。

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学