FIFO read/write lock – another home-made design

1) A writer-friendly rwlock says each writer is assigned an auto-increment queue-num (qnum), and all readers — early-birds or late-comers — all get qnum = -1, which is behind all writers. [[pthreads]] covers this kind of rwlock.

2) A strict FIFO rwlock says each writer is assigned a queue-number (qnum), and between 2 writers, any readers all get the same qnum.

Note all rwlock implementations are based entirely on mutex and condition objects. Nothing else needed.

Naive design 1: everyone waits on the same condition. Last release will notifyAll. The head the queue is self-aware [1] and proceeds. Everyone else goes back to wait. This is inefficient IF too many waiters.
[1] How? The rwlock knows (via a private field) the qnum of the head node. Alternatively, we can use a linked list.

Design 2 (notify only the head node): have the head thread(s) wait on a head-condition; everyone else in the everyone-condition. Whoever sends notify would notifyALL on the head condition, yield, and notifyAll on the everyone-condition. Everyone wakes up but only the next thread(s) in the linked list proceeds to wait in the head condition. However, before they enter, better check if the rwlock is free — it’s possible by the time they  wake up the lock is free.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s