logo标签列表

彼得森锁定/解锁的Java实现

javaalgorithmconcurrency
4

我正试图实现标题中Peterson算法的算法，但目前还没有正确地运行：

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

看起来有时候会有两个线程在它们的关键部分（critical section）内部。我也尝试过使用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 修饰各个成员，但仍然无效。

你在锁方法中使用了AtomicInteger变量，但这并不足以使锁方法线程安全。你应该在那里进行更复杂的同步形式（我不确定具体是什么）。 - Guts
你好，感谢您的评论！您能否详细说明一下？我正在尝试实现Peterson算法进行锁定/解锁，所以我认为不必担心该方法不是线程安全的。不是吗？ - Federico Ponzi
循环不应该是 int l = 0; l < N-1 吗？另外，你不需要在第二个版本中显式地将数组设置为0。 - shmosel
@shmosel 感谢您指出这一点。第二次迭代是其他试验的结果，在第一段代码中我仍然有-1。即使在第二个版本中也有它，它仍以相同的方式工作。还要感谢您提供的初始化提示 :) - Federico Ponzi
抱歉，我以为你在谈论 N-1。不，l=1 的话应该没问题。 0级线程表示其不感兴趣获取锁。 - Federico Ponzi
显示剩余2条评论
2个回答
4
很抱歉，问题在于您没有正确实现Peterson算法。具体来说，您lock方法中的外部循环需要从零开始而不是从1开始。由于零是线程编号的有效值，因此您不能将其用作levels数组的“默认”或“未使用值”，我已经将FLAG和LAST数组重命名为维基百科Peterson's algorithm描述中使用的术语。相反，我将代码更改为使用-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);
    }
}
非常感谢！我没有使用维基百科上的伪代码，而是从一本书中获取，但我想我应该使用那个。我正在寻找这样的问题，因为如果没有锁定，代码仍然会输出类似的数字 :) 再次感谢你指出这一点。 - Federico Ponzi
1

我进行了一些调整。每次都起作用。看起来你在索引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 提供, 点击上面的
可以查看英文原文，
原文链接