Sunday, January 12, 2014

Left-Right: No Version (revisited)

We talked before about the "No Version" variant of the Left-Right but there is something that I want to add regarding this variant.

One of the (theoretical) disadvantages of this variant is that the Writer may be indefinitely blocked waiting for a Reader that arrives/departs and set the state to READING.
Although this issue is unlikely to occur for more than a few iterations,  it is possible to overcome it by creating a fifth state WRITER_WAITING which only the Writer can change to, by using a compareAndSet(READING, WRITER_WAITING).

Regardless of whether the CAS operation fails or succeeds, the Writer will have to wait at most for the next state if it is still for the instance that it wants to write into: LEFT or RIGHT.
As soon as the Reader is seen in another state, even if it is READING, the Writer no longer needs to wait and can proceed with its write operation, because the Reader is guaranteed to see the updated leftRight.

No comments:

Post a Comment