Subject: A Schema for a First-Come First Served Readers/Writers Lock

From: Shlomi Fish <[email-masked]>
Date: Wed, 19 Dec 2001 18:01:18 +0200 (IST)

I'd like to code a first-come first served readers-writers lock (just for
fun). By first-come first-served I mean that a reader or a writer will be
accepted before all the readers or writers that registered before him and
after all the readers or writers that registered after him. (albeit it
would be possible to accept several pending readers almost
simultaneously).

I thought about this scheme to implement it in C. Can anybody detect a
possibility for a deadlock in it, because I'd like to know about it before
I implement it.

Regards,

	Shlomi Fish

====================================

The RWLock will use a queue. Each element of the queue will contain
a condition variable and a flag that indicates if it contains a reader
or a writer pending.

The RWLock will contain a counter that tells it how many readers are using
it at the moment (num_readers), and a flag that specifies if there's a
writer using the lock (is_writer). It also uses a common internal mutex
to protect against mutual exclusion (mymutex)

Algorithm:

accept_pending_items:
---------------------

Extracts the first element out of the queue. If it is a writer, it sets
is_writer to 1, and signals the condition variable of the element.

If it is a reader, it sets is_writer to 0, and polls+extracts
all the other items out of the queue that are readers.

get_write_access:
-----------------

locks mymutex.

Checks if is_writer is set or num_readers is greater than 0. If so,
it enqueues itself. (the mutex of the condition variable is mymutex)

If not it sets is_writer to 1.

Unlocks the mutex.

get_read_access:
----------------

locks mymutex.

If the queue is empty or is_writer is false it increments num_readers and unlock mutex.

Else it enqueues itself, while using mymutex for waiting on the condition variable. When the condition variable is signalled, num_readers is incremented by 1.

Unlocks mutex.

release_write_access:
---------------------

locks mutex

Sets is_writer to false. Then calls accept_pending_items.

unlocks mutex

release_read_access:
--------------------

locks mutex

Decrements num_readers. Then calls accept_pending_items.

unlocks mutex

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"