Saturday, December 20, 2014

Left-Right Distributed Counters No Version variant

For today's post, we have a new variant of Left-Right (yes, yet another, and yes, it's starting to get boring, but deal with it). This one is not really new in the sense that it is pretty much the same approach as the "Atomic Long No Version" shown on a previous post, only that we use distributed counters instead of a single variable containing the three counters.
There is however something interesting about it, and that is, that similarly to the variant "Reader's Version", this variant can approach the minimum number of fences (acquires and releases) needed to obtain pessimistic mutual exclusion. If this sounds confusing, then take a look at this post before you continue:
http://concurrencyfreaks.com/2014/06/minimum-number-of-barriers-for-lock.html
and if it sounds boring, well, then feel free to skip this entire post.

In this variant, when we do a read-only operation (one that is wrapped by an arrive()/depart()) on the arrive() we get the leftRight to figure out which instance to use, and this is returned by the atomic_fetch_add()/getAndAdd() done on the leftRightIngress. This atomic operation has an implicit acquire and an implicit release, to read the value and add one to it. When doing depart() we have in our implementation a distributed counter which also uses atomic_fetch_add()/getAndAdd(), but we can replace that with an array of counters where each entry has been pre-assigned to a thread, or alternatively, a ReadIndicator like the CLQ+Array+finalizers where each entry has its own counter, and in both cases we can increment the counter by doing a relaxed load followed by a store with release, and yes, we can use a relaxed load here because each thread has its own counter variable so it's always up-to-date.
This means that in the entire read-only operation, the only fences are the acquire and release done on the arrive() and then the store with release done on the depart(), thus resulting in the (theoretical) minimum number of fences needed to obtain mutual exclusion... it doesn't get any better than that!

So what does it look like?
Well, there are three counters:


// leftRight + ingress counter:
private transient final AtomicLong leftRightIngress = new AtomicLong(0);
// Egress counters
private transient final LongAdder leftEgress = new LongAdder();
private transient final LongAdder rightEgress = new LongAdder();

There is an arrive() that returns the current value of leftRight:


private int arrive() {
    return getLeftRight(leftRightIngress.getAndIncrement());
}

There is a depart() that takes the value of leftRight that has been used for arrive():


private void depart(int localLeftRight) {
    if (localLeftRight == READS_ON_LEFT) {
        leftEgress.increment();
    } else {
        rightEgress.increment();
    }
}

And there is a toggleVersionAndWait() which should be called toggleLeftRightandWait() because there is no versionIndex to toggle:


private void toggleVersionAndWait() {
    final int localLeftRight = getLeftRight(leftRightIngress.get());
    if (localLeftRight == READS_ON_LEFT) {
        rightEgress.reset();
        // Toggle leftRight and count the number of arrives()
        final long lri = leftRightIngress.getAndSet(Long.MIN_VALUE);
        // Wait for the corresponding readers that did arrive()
        while (lri != leftEgress.sum()) Thread.yield();
    } else {
        leftEgress.reset();
        final long lri = leftRightIngress.getAndSet(0);
        while (lri+Long.MIN_VALUE != rightEgress.sum()) Thread.yield();
    }
}


An example implementation in Java is available on github:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/Java/com/concurrencyfreaks/experimental/LRTreeSetDCNV.java

No comments:

Post a Comment