Software Section Menu

A First-Come First-Served Readers/Writers Lock

This is a working implementation of a First-Come First-Served Readers/Writers lock for POSIX threads. It is well commented and documented so I believe it can also serve as a reference implementation for those who wish to implement such a mechanism for other platforms.

Licence

You may use this code under your choice of:

To the extent possible under law, Shlomi Fish has waived all copyright and related or neighbouring rights to First-Come First-Served Readers/Writers Lock. This work is published from Israel.
The MIT/Expat Licence

Todo List

Make an RPM SPEC/Debian Package etc.
Port to Win32, ZThreads, etc.

Questions and Answers

What is a Readers/Writers Lock?

A Readers/Writers Lock (or RWLock for short) is a mechanism that allows an arbitrary number of readers or alternatively one writer to access a resource at any given time. It is useful in case writing may temporarily harm the integrity of the resource.

What is a First-Come First-Served RWLock?

Many RWLock implementations arbitrate the various readers and writers in a manner that may cause starvation of either readers or writers. For instance, a readers/writers lock that prefers readers may cause a writer to starve (i.e: wait for a very long time or indefinitely) if there are two and more competing readers.

A First-Come First-Served (FCFS) RWLock solves this problem by making sure that the pending threads are served at the same order as the time of their arrival. Thus, starvation is eliminated assuming that a thread does not obtain the lock indefinitely (which in any case should not happen in a well-designed system).

How does it make sure that’s what going to happen?

By using a queue in which each element controls a pending thread. A detailed description of the algorithm can be found here and naturally, there are also the comments in the code. If there’s anything you don’t understand, don’t hesitate to contact me and ask.

Recently, the algorithm was modified to pack several readers or several writers on the same queue element, which results in saving of condition variables. The new scheme for it (which is a bit more complex) can be found here.