All geek questions in one place

Peterson locks / unlocks Java implementation

I am trying to implement the algorithm in title , but at the moment it is not working correctly:

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);
    }
}

This is the main class:

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);
        }
    }

}

As you can see, I create 100 threads, and all of them increase the variable test5 times. Thus, the expected value should be 500. This is the output:

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

It seems that sometimes there are two threads in their critical section. Instead, I tried using 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);
    }
}

But still the same problem. I also tried to use volatilefor different participants, but did not work.

+4
source share
2 answers

I'm afraid that the problem is that you did not correctly implement the Peterson algorithm.

, lock , 1. , " " " " " ( FLAG LAST , ). -1 .

,

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 volatile, AtomicInteger, unlock, , 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);
    }
}
+4

. . , 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);
}
+1

Source: https://habr.com/ru/post/1694688/

More articles:


All Articles