Implementing Filter and Bakery Locks in Java

In order to understand how locks work, implementing custom locks is a good way. This post will show how to implement Filter and Bakery locks at Java (which are spin locks) and will compare their performances with Java's ReentrantLock. Filter and Bakery locks satisfies mutual exclusion and are starvation free algorithms also, Bakery lock is a first-come-first-served lock [1].

For performance testing, a counter value is incremented up to 10000000 with different lock types, different number of threads and different number of times. Test system configuration is: Intel Core I7 (has 8 cores – 4 of them are real), Ubuntu 14.04 LTS and Java 1.7.0_60.

Filter lock has n-1 levels which maybe considered as “waiting rooms”. A thread must traverse this waiting rooms before acquiring the lock. There are two important properties for levels [2]:

1) At least one thread trying to enter level l succeeds.
2) If more than one thread is trying to enter level l, then at least one is blocked (i.e., continues to wait at that level).

Filter lock is implemented as follows:

/**
 * @author Furkan KAMACI
 */
public class Filter extends AbstractDummyLock implements Lock {
    /* Due to Java Memory Model, int[] not used for level and victim variables.
     Java programming language does not guarantee linearizability, or even sequential consistency,
     when reading or writing fields of shared objects
     [The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.61.]
     */
    private AtomicInteger[] level;
    private AtomicInteger[] victim;

    private int n;

    /**
     * Constructor for Filter lock
     *
     * @param n thread count
     */
    public Filter(int n) {
        this.n = n;
        level = new AtomicInteger[n];
        victim = new AtomicInteger[n];
        for (int i = 0; i < n; i++) {
            level[i] = new AtomicInteger();
            victim[i] = new AtomicInteger();
        }
    }

    /**
     * Acquires the lock.
     */
    @Override
    public void lock() {
        int me = ConcurrencyUtils.getCurrentThreadId();
        for (int i = 1; i < n; i++) {
            level[me].set(i);
            victim[i].set(me);
            for (int k = 0; k < n; k++) {
                while ((k != me) && (level[k].get() >= i && victim[i].get() == me)) {
                    //spin wait
                }
            }
        }
    }

    /**
     * Releases the lock.
     */
    @Override
    public void unlock() {
        int me = ConcurrencyUtils.getCurrentThreadId();
        level[me].set(0);
    }
}

Bakery lock algorithm maintains the first-come-first-served property by using a distributed version of the number-dispensing machines often found in bakeries: each thread takes a number in the doorway, and then waits until no thread with an earlier number is trying to enter it [3].

Bakery lock is implemented as follows:

/**
 * @author Furkan KAMACI
 */
public class Bakery extends AbstractDummyLock implements Lock {
    /* Due to Java Memory Model, int[] not used for level and victim variables.
     Java programming language does not guarantee linearizability, or even sequential consistency,
     when reading or writing fields of shared objects
     [The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.61.]
     */
    private AtomicBoolean[] flag;
    private AtomicInteger[] label;

    private int n;

    /**
     * Constructor for Bakery lock
     *
     * @param n thread count
     */
    public Bakery(int n) {
        this.n = n;
        flag = new AtomicBoolean[n];
        label = new AtomicInteger[n];
        for (int i = 0; i < n; i++) {
            flag[i] = new AtomicBoolean();
            label[i] = new AtomicInteger();
        }
    }

    /**
     * Acquires the lock.
     */
    @Override
    public void lock() {
        int i = ConcurrencyUtils.getCurrentThreadId();
        flag[i].set(true);
        label[i].set(findMaximumElement(label) + 1);
        for (int k = 0; k < n; k++) {
            while ((k != i) && flag[k].get() && ((label[k].get() < label[i].get()) || ((label[k].get() == label[i].get()) && k < i))) {
                //spin wait
            }
        }
    }

    /**
     * Releases the lock.
     */
    @Override
    public void unlock() {
        flag[ConcurrencyUtils.getCurrentThreadId()].set(false);
    }

    /**
     * Finds maximum element within and {@link java.util.concurrent.atomic.AtomicInteger} array
     *
     * @param elementArray element array
     * @return maximum element
     */
    private int findMaximumElement(AtomicInteger[] elementArray) {
        int maxValue = Integer.MIN_VALUE;
        for (AtomicInteger element : elementArray) {
            if (element.get() > maxValue) {
                maxValue = element.get();
            }
        }
        return maxValue;
    }
}

For such kind of algorithms, it should be provided or used a thread id system which starts from 0 or 1 and increments one by one. Threads' names set appropriately for that purpose. It should also be considererd that: Java programming language does not guarantee linearizability, or even sequential consistency, when reading or writing fields of shared objects [4]. So, level and victim variables for Filter lock, flag and label variables for Bakery lock defined as atomic variables. For one, who wants to test effects of Java Memory Model can change that variables into int[] and boolean[] and run algorithm with more than 2 threads. Than, can see that algorithm will hang for either Filter or Bakery even threads are alive.

To test algorithm performances, a custom counter class implemented which has a getAndIncrement method as follows:

/**
 * gets and increments value up to a maximum number
 *
 * @return value before increment if it didn't exceed a defined maximum number. Otherwise returns maximum number.
 */
public long getAndIncrement() {
    long temp;
    lock.lock();
    try {
        if (value >= maxNumber) {
            return value;
        }
        temp = value;
        value = temp + 1;
    } finally {
        lock.unlock();
    }
    return temp;
}

There is a maximum number barrier to fairly test multiple application configurations. Consideration is that: there is a piece amount of work (incrementing a variable up to a desired number) and with
different number of threads how fast you can finish it. So, for comparison, there should be a “job” equality. This approach also tests unnecessary work load with that piece of code:

if (value >= maxNumber) {
    return value;
}

for multiple threads when it is compared an approach that calculating unit work performance of threads (i.e. does not putting a maximum barrier, iterating in a loop up to a maximum number and than dividing last value to thread number).

This configuration used for performance comparison:

First of all, when you run a block of code within Java several time, there is an internal optimization for codes. When algorithm is run multiple times and first output compared to second output this optimization's effect can be seen. First elapsed time mostly should be greater than second line because of that. For example:

currentTry = 0, threadCount = 1, maxNumber = 10000000, lockType = FILTER, elapsedTime = 500 (ms)
currentTry = 1, threadCount = 1, maxNumber = 10000000, lockType = FILTER, elapsedTime = 433 (ms)

Conclusion:

From the chart, it can bee seen that Bakery lock is faster than Filter Lock with a low standard error. Reason is Filter Lock's lock method. At Bakery Lock, as a faired approach threads runs one by one but at Filter Lock they computes with each other. Java's ReentrantLock has best when compared to others.

On the other hand Filter Lock gets worse linearly but Bakery and ReentrantLock are not (Filter lock may have a linear graphic when it run with much more threads). More thread count does not mean less elapsed time. 2 threads maybe worse than 1 thread because of thread creating and locking/unlocking. When thread count starts to increase, elapsed time gets better for Bakery and ReentrantLock. However when thread count keep going to increase than it gets worse. Reason is real core number of the test computer which runs algorithms.

Source code for implementing filter and bakery locks in Java can be downloaded from here: https://github.com/kamaci/filbak

[1] The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.31.-33.

[2] The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.28.

[3] The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.31.

[4] The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.61.