实现互斥算法伯恩斯和林奇在Java中：莫不是由于指令重新排序问题？指令、算法、伯恩斯、互斥
我发现了一个相当简单的正过程互斥4页上（836）在以下论文算法：＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP;＆NBSP; < A HREF =http://groups.csail.mit.edu/tds/papers/Lynch/allertonconf.pdf相对=nofollow>互斥使用不可分割的读取和写入伯恩斯和林奇
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
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.
我喜欢，因为它的最小内存使用它，并转到的应该让我的方法实现它 enterCriticalRegion（）返回一个布尔值，指示该进程是否成功在获取锁（即到达8号线），还是打的GOTO的一个，需要稍后重试，而不是忙等待。 （公平和饥饿是不是真的在我的情况令人担忧）
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)
我想实现这个Java和测试它通过让一束线程尝试在快速连续进入临界区（看起来很长，但它主要的意见）：
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):
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);
}
}
由于某些原因，互斥验证（通过的AtomicInteger）保持几秒钟后失败，并与该消息的程序退出两个进程填的关键部分！。
无论是算法和我的实现是如此简单，我有点困惑，为什么它不工作。
Both the algorithm and my implementation are so simple, that I'm a little perplexed why it's not working.
是不是有什么毛病烧伤/林奇的算法（怀疑）？还是我做了一些愚蠢的错误的地方，我只是没有看到？或者，这是造成一些Java指令重新排序？后者似乎有点不太可能，因为我每次作业后跟一个潜在的返回键，因此不应该与任何其他交换，不是吗？或者是Java数组访问不是线程安全的？
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?
快速旁白：的
A quick aside:
下面是我想象的伯恩斯和林奇的算法（可能有助于思考的问题）：
Here is how I visualize the Burns and Lynch algorithm (might help think about the issue):
我的过程中，我在一排与其他人（进程）站立的地方。当我想进入临界区，我做到以下几点：
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：我期待我的左边，让我的手后，只要有人存在都有他们的手。 5：如果没有人给我留下了自己的手，我把我的了 6：我再次检查，如果有人给我的左边也同时把自己的手。如果是这样，我把我的背下来，并重新开始。否则，我把我的手。 7：每个人在我右边先走，让我看看我的权利，等到我看不出有任何的手 8：当没有人在我右边有他们的手更多的，我可以进入临界区 1：当我做了，我把我的手回落好像坚实的给我...不知道为什么它不应该可靠地工作......
Seems solid to me... Not sure why it shouldn't work reliably...
推荐答案
在你没有保证写入F [I]将是可见的另一个线程后从中读取Java内存模型。
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.
有这种能见度问题的标准解决方案是将共享变量声明为挥发性的，但在这种情况下，F是一个阵列和写/读至F [I]不改变F值
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.
这是不可能的声明......挥发阵，而是一个可以声明˚F为AtomicIntegerArray并使用 compareAndSet进行原子地改变数组的内容，而不必担心线程的知名度。
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.
