Peterson锁/解锁java实现
Peterson锁/解锁java实现
提问于 2018-03-09 14:30:14
我正试图在标题中实现该算法，但目前还不能正常工作：
package me.fponzi.mutex;
import java.util.concurrent.atomic.AtomicInteger;
public class PetersonLockUnlock implements MutexInterface {
private AtomicInteger[] FLAG;
private AtomicInteger[] LAST;
private int N;
/**
* PetersonLockUnlock
*
* @param N number of processes.
*/
public PetersonLockUnlock(int N) {
this.N = N;
this.FLAG = new AtomicInteger[N];
this.LAST = new AtomicInteger[N];
for (int i = 0; i < N; i++) {
this.FLAG[i] = new AtomicInteger(0);
this.LAST[i] = new AtomicInteger(-1);
}
}
public void lock(int i) {
for (int l = 1; l < this.N-1; l++) {
this.FLAG[i].set(l);
this.LAST[l].set(i);
boolean other_flags = true;
while (other_flags && this.LAST[l].get() == i) {
for (int k = 0; k < this.N; k++) {
if (k == i) continue;
other_flags = other_flags && this.FLAG[k].get() >= l;
}
}
}
}
public void unlock(int i) {
this.FLAG[i].set(0);
}
}这是主要的课程：
import me.fponzi.mutex.MutexInterface;
import me.fponzi.mutex.PetersonLockUnlock;
public class Main {
static int test_value = 0;
public static class PrintThread implements Runnable{
private MutexInterface mutex;
PrintThread(MutexInterface m)
{
this.mutex = m;
}
@Override
public void run() {
String threadName = Thread.currentThread().getName();
int threadId = Integer.parseInt(threadName);
for (int i = 0; i < 5; i++)
{
mutex.lock(threadId);
test_value +=1;
mutex.unlock(threadId);
}
}
}
public static void main(String[] args) throws InterruptedException {
final int NTHREADS = 100;
PetersonLockUnlock p = new PetersonLockUnlock(NTHREADS);
Thread[] threads = new Thread[NTHREADS];
while (true) {
test_value = 0;
for (int i = 0; i < NTHREADS; i++) {
threads[i] = new Thread(new PrintThread(p), "" + i);
}
for (Thread t : threads) {
t.start();
}
for (Thread t : threads) {
t.join();
}
System.out.println("Result:" + test_value);
}
}
}如您所见，我正在创建100个线程，它们都会将test变量增加5倍。所以期望值应该是500。这是它的外型：
Result:499
Result:500
Result:500
Result:500
Result:498
Result:499
Result:500
Result:499
Result:499
Result:500
Result:500
Result:500
Result:498
Result:500
Result:499
Result:500
Result:500
Result:499
Result:500
Result:500
Result:500
Result:500
Result:500
Result:500
Result:500
Result:500
Result:500看起来，有时在它们的关键部分中有两个线程。我还尝试使用AtomicIntegerArray来代替：
public class PetersonLockUnlock implements MutexInterface {
private AtomicIntegerArray FLAG;
private AtomicIntegerArray LAST;
private int N;
/**
* PetersonLockUnlock
*
* @param N number of processes.
*/
public PetersonLockUnlock(int N) {
this.N = N;
this.FLAG = new AtomicIntegerArray(N);
this.LAST = new AtomicIntegerArray(N);
for (int i = 0; i < N-1; i++) {
this.FLAG.set(i, 0);
this.LAST.set(i, 0);
}
}
public void lock(int i) {
for (int l = 1; l < this.N; l++) {
this.FLAG.set(i, l);
this.LAST.set(l, i);
boolean other_flags = true;
while (other_flags && this.LAST.get(l) == i) {
for (int k = 0; k < this.N; k++) {
if (k == i) continue;
other_flags = other_flags && this.FLAG.get(k) >= l;
}
}
}
}
public void unlock(int i) {
this.FLAG.set(i,0);
}
}但仍然有同样的问题。我也尝试过对不同的成员使用volatile，但仍然不起作用。
回答 2
Stack Overflow用户
回答已采纳
发布于 2018-03-09 15:38:32
恐怕问题是您没有正确地实现Peterson的算法。
具体来说，lock方法中的外部循环需要从零开始，而不是从1开始。由于零是线程号的有效值，所以不能将其用作级别数组的“默认”或“不使用值”(我已将标志和最后一个数组重命名为维基百科对彼得森算法的描述中使用的术语)。相反，我将代码改为-1用于此目的。
最重要的是，您实现了Peterson算法的这一部分
while last_to_enter[ℓ] = i and there exists k ≠ i, such that level[k] ≥ ℓ
wait 是不正确的。您的函数不使用other_flags = other_flags && this.FLAG.get(k) >= l;测试是否存在，因为如果数组中有一个元素k >= l不为真，则将other_flags设置为false。但逻辑应该是相反的。
我已经将这个部分重构成一个单独的方法，并将其固定在那里。
有了这些变化，它就奏效了。内存屏障是隐含的，因为AtomicInteger使用一个易失性变量，并且锁总是从被前一个unlock修改的AtomicInteger中读取，所以它会创建它--在Java模型的术语中关系之前。
public class PetersonLockUnlock implements MutexInterface {
private AtomicInteger[] levels;
private AtomicInteger[] lastToEnter;
private int n;
public PetersonLockUnlock(int n) {
this.n = n;
this.levels = new AtomicInteger[n];
this.lastToEnter = new AtomicInteger[n];
for (int i = 0; i < n; i++) {
this.levels[i] = new AtomicInteger(-1);
this.lastToEnter[i] = new AtomicInteger(-1);
}
}
public void lock(int i) {
for (int l = 0; l < this.n - 1; l++) {
this.levels[i].set(l);
this.lastToEnter[l].set(i);
while (this.lastToEnter[l].get() == i && existsLevelGteL(l, i)) {
// busy-wait
}
}
}
private boolean existsLevelGteL(int l, int i) {
for (int k = 0; k < this.n; k++) {
if (k != i && this.levels[k].get() >= l) {
return true;
}
}
return false;
}
public void unlock(int i) {
this.levels[i].set(-1);
}
}Stack Overflow用户
发布于 2018-03-09 15:42:14
我做了些调整。每次都有用。好像你对索引0有问题。
public PetersonLockUnlock(int N) {
this.N = N;
this.FLAG = new AtomicInteger[N];
this.LAST = new AtomicInteger[N];
for (int i = 0; i < N; i++) {
this.FLAG[i] = new AtomicInteger(-1);
this.LAST[i] = new AtomicInteger(-1);
}
}
public void lock(int i) {
for (int l = 0; l < this.N-1; l++) {
this.FLAG[i].set(l);
this.LAST[l].set(i);
boolean other_flags = true;
while (other_flags && this.LAST[l].get() == i) {
other_flags = false;
for (int k = 0; k < this.N; k++) {
if (k == i) continue;
if (this.FLAG[k].get() >= l) {
other_flags = true;
break;
}
}
}
}
}
public void unlock(int i) {
this.FLAG[i].set(-1);
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/49195941
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号