CODEWITHSUNDEEP
javaalgorithmconcurrency
Federico Ponzi
Federico Ponzi

Reputation: 2775

Peterson lock/unlock java implementation

I'm trying to implement the algorithm in the title, but at the moment 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'm creating 100 threads, and all of them increase the test variable 5 times. So the expected value should be 500. This is the ouptut:

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 looks like that sometimes there are two threads that are inside their critical section. I've also tried to used AtomicIntegerArray instead:

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 have the same problem. I've also tried to use volatile for the various members, but still dosen't work.

Upvotes: 4

Views: 749

Answers (2)

maraca
maraca

Reputation: 8743

I did some adjustments. Worked every time. Seems you have a problem with index 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);
}

Upvotes: 1

Erwin Bolwidt
Erwin Bolwidt

Reputation: 31269

I'm afraid that the problem is that you haven't implemented Peterson's algorithm correctly.

Specifically, the outer loop in your lock method needs to start at zero, not at 1. And since zero is a valid value for thread number, you can't use it as "default" or "not in use value" for the levels array (I've renamed the FLAG and LAST arrays to the terms used in Wikipedia's description of Peterson's algorithm). Instead, I changed the code to use -1 for that purpose.

Most importantly though, your implementation of this part of Peterson's algorithm

while last_to_enter[ℓ] = i and there exists k ≠ i, such that level[k] ≥ ℓ
    wait

is incorrect. Your function doesn't test for existence with other_flags = other_flags && this.FLAG.get(k) >= l;, since if there is one element in the array for which k >= l is not true, you set your other_flags to false. But the logic should be the other way around.

I've refactored that part into a separate method and fixed it there.

With those changes, it works. The memory barrier is implied as AtomicInteger uses a volatile variable, and a lock always read from the the AtomicInteger that was modified by the previous unlock, so it creates it happens-before relationship in the terminology of the Java Memory Model.

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

Upvotes: 4

Related Questions