I found a fairly simple n-process mutual exclusion algorithm on page 4 (836) in the following paper:
"Mutual Exclusion Using Indivisible Reads and Writes" by Burns and Lynch
在下面的论文中，我在第4页(836页)找到了一个相当简单的n进程互斥算法:Burns and Lynch的《不可分割读写互斥》
program Process_i;
type flag = (down, up);
shared var F : array [1..N] of flag;
var j : 1..N;
begin
while true do begin
1: F[i] := down;
2: remainder; (* remainder region *)
3: F[i] := down;
4: for j := 1 to i-1 do
if F[j] = up then goto 3;
5: F[i] := up;
6: for j := 1 to i-1 do
if F[j] = up then goto 3;
7: for j := i+1 to N do
if F[j] = up then goto 7;
8: critical; (* critical region *)
end
end.
I like it, because of its minimal memory use and the goto's should allow me to implement it in a method enterCriticalRegion() that returns a boolean indicating whether the process succeeded in acquiring the lock (i.e. reached line 8) or whether it hit one of the goto's and needs to try again later rather than busy-waiting. (Fairness and starvation aren't really a concern in my case)
我喜欢它,因为它的最小内存使用goto的应该允许我在一个方法中实现它enterCriticalRegion()返回一个布尔值表示这个过程是否成功地获取了锁(即达到8号线)还是goto的和需要稍后再试,而不是忙等待。(公平和饥饿不是我真正关心的问题)
I tried to implement this in Java and test it out by having a bunch of threads try to enter the critical region in rapid succession (looks long, but it's mostly comments):
我尝试在Java中实现这一点，并通过让一些线程连续快速地进入关键区域进行测试(看起来很长，但主要是注释):
import java.util.concurrent.atomic.AtomicInteger;
public class BurnsME {
// Variable to count processes in critical section (for verification)
private static AtomicInteger criticalCount = new AtomicInteger(0);
// shared var F : array [1..N] of flag;
private static final boolean[] F = new boolean[10000];
// Some process-local variables
private final int processID;
private boolean atLine7;
public BurnsME(int processID) {
this.processID = processID;
this.atLine7 = false;
}
/**
* Try to enter critical region.
*
* @return T - success; F - failure, need to try again later
*/
public boolean enterCriticalRegion() {
// Burns Lynch Algorithm
// Mutual Exclusion Using Indivisible Reads and Writes, p. 836
if (!atLine7) {
// 3: F[i] down
F[processID] = false;
// 4: for j:=1 to i-1 do if F[j] = up goto 3
for (int process=0; process<processID; process++)
if (F[process]) return false;
// 5: F[i] = up
F[processID] = true;
// 6: for j:=1 to i-1 do if F[j] = up goto 3
for (int process=0; process<processID; process++)
if (F[process]) return false;
atLine7 = true;
}
// 7: for j:=i+1 to N do if F[j] = up goto 7
for (int process=processID+1; process<F.length; process++)
if (F[process]) return false;
// Verify mutual exclusion
if (criticalCount.incrementAndGet()>1) {
System.err.println("TWO PROCESSES ENTERED CRITICAL SECTION!");
System.exit(1);
}
// 8: critical region
return true;
}
/**
* Leave critical region and allow next process in
*/
public void leaveCriticalRegion() {
// Reset state
atLine7 = false;
criticalCount.decrementAndGet();
// Release critical region lock
// 1: F[i] = down
F[processID] = false;
}
//===============================================================================
// Test Code
private static final int THREADS = 50;
public static void main(String[] args) {
System.out.println("Launching "+THREADS+" threads...");
for (int i=0; i<THREADS; i++) {
final int threadID = i;
new Thread() {
@Override
public void run() {
BurnsME mutex = new BurnsME(threadID);
while (true) {
if (mutex.enterCriticalRegion()) {
System.out.println(threadID+" in critical region");
mutex.leaveCriticalRegion();
}
}
}
}.start();
}
while (true);
}
}
For some reason, the mutual exclusion verification (via the AtomicInteger) keeps failing after a few seconds and the program exits with the message TWO PROCESSES ENTERED CRITICAL SECTION!.
由于某些原因，互斥验证(通过AtomicInteger)在几秒钟后一直失败，程序退出消息两个进程进入临界段!
Both the algorithm and my implementation are so simple, that I'm a little perplexed why it's not working.
算法和实现都很简单，所以我有点困惑为什么它不能工作。
Is there something wrong with the Burns/Lynch algorithm (doubt it)? Or did I make some stupid mistake somewhere that I'm just not seeing? Or is this caused by some Java instruction reordering? The latter seems somewhat unlikely to me since each assignment is followed by a potential return and should thus not be swapped with any other, no? Or is array access in Java not thread safe?
Burns/Lynch算法有什么问题吗?还是我在某个地方犯了什么愚蠢的错误，只是我没看见而已?还是由Java指令重新排序引起的?对于我来说，后者似乎不大可能，因为每个任务都有一个潜在的回报，因此不应该与其他的交换交换，不是吗?或者在Java中数组访问不是线程安全的吗?
A quick aside:
一个快速的旁白:
Here is how I visualize the Burns and Lynch algorithm (might help think about the issue):
以下是我对Burns and Lynch算法的可视化(可能有助于思考这个问题):
I'm the process and I'm standing somewhere in a row with other people (processes). When I want to enter the critical section, I do the following:
我是过程，我和其他人(过程)站在一起。当我想进入关键部分时，我做以下事情:
- 3/4: I look to my left and keep my hand down as long as someone there has their hand up.
- 3/4:我向左边看，只要有人举手，我就把手放下。
- 5: If no-one to my left has their hand up, I put mine up
- 他说:如果我左手边没有人举手，我就举手
- 6: I check again if anyone to my left has meanwhile put their hand up. If so, I put mine back down and start over. Otherwise, I keep my hand up.
- 6:我再检查一下我左边的人有没有举手。如果是的话，我把我的重新放回去，重新开始。否则，我就把手举起来。
- 7: Everyone to my right goes first, so I look to my right and wait until I don't see any hands up.
- 7:我右边的人先走，所以我向右看，等我没看到有人举手。
- 8: Once no-one to my right has their hand up any more, I can enter the critical section.
- 8:一旦我的右边不再有人举手，我就可以进入关键部分了。
- 1: When I'm done, I put my hand back down.
- 当我完成时，我把手放下。
Seems solid to me... Not sure why it shouldn't work reliably...
在我看来固体……不确定为什么它不能可靠地工作……
1 个解决方案
#1
2
In the java memory model you have no guarantee that a write to F[i] will be visible to another Thread reading from it later.
在java内存模型中，您不能保证对F[i]的写入在以后读取它的另一个线程中是可见的。
The standard solution for this kind of visibility problem is to declare the shared variable as volatile, but in this case F is an array and write/reads to F[i] do not change the value of F.
对于这种可见性问题，标准的解决方案是将共享变量声明为volatile，但是在这种情况下，F是一个数组，对F[i]的写/读不会改变F的值。
It is not possible to declare an "array of volatiles ...", but one can declare F as AtomicIntegerArray and use compareAndSet to atomically change the array content without worrying about Thread-visibility.
不可能声明“挥发物的数组……”，但是可以将F声明为AtomicIntegerArray并使用compareAndSet原子地更改数组内容，而不必担心线程的可见性。
#1
2
In the java memory model you have no guarantee that a write to F[i] will be visible to another Thread reading from it later.
在java内存模型中，您不能保证对F[i]的写入在以后读取它的另一个线程中是可见的。
The standard solution for this kind of visibility problem is to declare the shared variable as volatile, but in this case F is an array and write/reads to F[i] do not change the value of F.
对于这种可见性问题，标准的解决方案是将共享变量声明为volatile，但是在这种情况下，F是一个数组，对F[i]的写/读不会改变F的值。
It is not possible to declare an "array of volatiles ...", but one can declare F as AtomicIntegerArray and use compareAndSet to atomically change the array content without worrying about Thread-visibility.
不可能声明“挥发物的数组……”，但是可以将F声明为AtomicIntegerArray并使用compareAndSet原子地更改数组内容，而不必担心线程的可见性。