Abuse of read/write lock

A more fine-grained alternative to mutex lock is the read/write lock (rwlock). Mutex disallows two threads to access the same variable at the same time regardless whether the access is a read or write. With rwlock, the basic principle is simple: two readers can read from a variable (memory location) simultaneously without stepping on each other's toes. However, two writers cannot both write to the same variable, nor can one writer and one reader try to access the variable at the same time; both lead to inconsistent results.

There is one useful way to correctly abuse rwlock. Before we introduce the idea, let's talk a bit about lock-free stack implementation using singly linked list. Using compare and swap instruction, stack push can be implemented in the lock-free (and wait-free) manner. The compare and swap instruction provides a sufficient one-word transactional memory mechanism to allow changes made by another thread to be detected. This works because the node to be pushed to the stack is supposedly private. But stack pop suffers the complication of the ABA problem because the node to be popped is shared, so while thread 1 is in the middle of popping node A—let's say its successor is X at the moment—thread 2 pops node A, pushes node B, and pushes node A back. Now, A's successor is B instead of X. Thread 1 may mistakenly put reference to X as the top of the stack when it finishes popping node A.

With the singly linked list stack with push and pop implemented using compare and swap, we have the following access granting relationship. Two threads can safely push at the same time (guarded by compare and swap), but no two threads may pop at the same time, nor one thread to push and another thread to pop at the same time. This is exactly like a rwlock!

For this particular data structure, we could use rwlock to protect access. It is not exactly lock-free wait-free anymore, but maybe there are cases where the compromise, which is much easier to implement, is acceptable and useful.