Saturday, February 16, 2013

Flowcharts for the 2-states Scalable RW-Lock

As mentioned on a previous post, it is possible to implement a 2-state Scalable-Read-Write-Lock thanks to Andreia  :)
Here is what the flowchart for the read-lock (shared) operation:

and this is the write-lock (exclusive) operation:

If you want to understand better how the linearizability works in the 2-state algorithm, then here is again the Reader's flowchart, this time with some indications of what happens when the Writer changes the write-lock from 0 to 1 at each point of the flowchart:

A: The Reader’s state will still be temporarily set to 1 which may (or may not) prevent the Writer from progressing, but immediately after the sate of the Writer will be read and the Reader’s state will go to 0
B: Same as A
C: The Reader’s state has already been set to 1 long before, which means that the Writer is guaranteed to read the state as 1, which means it will yield() and wait for this Reader to complete.
D: The Reader will proceed the as shown in the flowchart and will yield() until the Writer’s state goes back to 0
 This is obvioulsy not a proof of the Linearizability but it gives some good indications on the correctness of the algorithm.

No comments:

Post a Comment