Left-Right: No Version variant

The Left-Right technique has several variants. This one was discovered by Andreia and we named it "No Version".

On this variant, there is no variable versionIndex, and each Reader has its own state.
The Reader's state can have one of four different values:
NOT_READING: This particular Reader is not doing or attempting a read operation;
READING: The Reader is starting a read operation but has not yet started;
READS_ON_LEFT: The Reader is currently doing its operation on the leftInstance;
READS_ON_RIGHT: The Reader is currently doing its operation on the rightInstance;

A depiction of the valid transitions between states is shown below:
 


The fact that each Reader needs its own state, means that this kind of technique can't be implemented with a readIndicator mechanism that uses counters. For this variant, we can use the same kind of technique we used for the ScalableRWLock we showed a long time ago.
A side note: it's funny, Andreia invented the "Left-Right No Version" several years ago, long before we invented the ScalableRWLock, but we showed the ScalableRWLock algorithm first... the LR really has been "in the making" for a really long time, I guess it's because most people that looked at it didn't understand it, or worse yet, got it completely wrong. Of all the people we showed the Left-Right to (before making it public a week ago) there were only a handful of people who "got it", and even when we submitted to a major conference on concurrent data structures a few months ago, only one of the four reviewers understood what it was about... ohhhh well, but I digress.

The main difference from the classical LR algorithm is that the Writer will wait if there are any Readers in state READING or in the state corresponding to the previous value of the leftRight variable: either READS_ON_LEFT if leftRight is LEFT, or READS_ON_RIGHT if leftRight is RIGHT. This means that theoretically, it could be possible for a Writer to be stuck indefinitely waiting for a Reader that finishes its operation and starts a new operation immediately afterwards, going temporarily into the READING state, but in practice this issue is unlikely to occur for more than a few iterations.


The algorithm for the "Left-Right No Version" variant is the following:
Reader:

1. Set the readIndicator to state READING
2. Read the current value of leftRight and if it is LEFT set the readIndicator to state READS_ON_LEFT, otherwise to state READS_ON_RIGHT
3. Execute the read operation on the appropriate instance
4. Set the readIndicator to state NOT_READING

Writer:

1. Acquire the writersMutex;
2. Read the current value of leftRight and if it is LEFT then execute the write operation on the rightInstance, and if it is RIGHT then execute on the leftInstance;
3. Toggle leftRight from LEFT to RIGHT or RIGHT to LEFT;
4. Wait until every Reader's state is no longer at READING nor at the leftRight state before the toggle in step 3;
5. Execute the write operation on the instance opposite to the one indicated in the current leftRight;
6. Release the writersMutex;

The easiest way to implement such a readIndicator is to have an array where each entry is dedicated to a particular thread (Reader) and then it is up to the Writer to scan the array and spin/yield on the ones that are READING or have the previous leftRight. This creates the problem of how to assign a unique entry of the array to each thread, which can be done in more than one way, but my favorite is to have a thread-local variable that is assigned at startup, or the first time the readIndicator is set.
Another possible implementation of this readIndicator is to use the same technique as on the ScalableRWLock, where each Reader (thread) will add an object containing the state to a ConcurrentLinkedQueue that the Writer will scan. This can be optimized if the Writer creates a new array from the CLQ every time there is a new state-object added or removed from the CLQ, thus improving the speed of scanning for the next Writer.
There are many details on the readIndicator itself, so much so that it is worthy of its own future post, and I'm sure that it is possible to come up with other readIndicators as well.


The Java source code for this variant can be obtained here:
http://sourceforge.net/projects/ccfreaks/files/papers/LeftRight/LRScalableTreeSetNV.java/download