Re: [Threads-devel] read/write locks and pthreads

From: Anthony Williams (anthony_at_[hidden])
Date: 2007-04-15 17:31:49

> I wonder if you have a commented version of the source code for your
> read/write mutex implementation, or even just a high level description
> of how it works? I'm sure it's not that difficult to figure it out, but
> it would be much quicker to have an overall description of the
> implementation.

No, I don't have a commented version. I promised Roland a description a
while back, so here goes.

Basically, there are four states:

* Unlocked
* Shareable locked by N threads
* Shareable locked by N threads and upgradeable locked by 1 thread
* Exclusive locked by 1 thread

When a thread tries to acquire a shareable lock, if the mutex is unlocked,
it acquires it. If the mutex is locked for shareable access, and no thread
is *blocked* waiting for exclusive access, it acquires it. Else the thread
blocks on the "shared" cond var.

When a thread tries to acquire an exclusive lock, if the mutex is
unlocked, it acquires it. Otherwise, it marks itself as *blocked* and
blocks on the "exclusive" cond var.

When a thread tries to acquire an upgradeable lock, if the mutex is
unlocked, it acquires it. If the mutex is locked for shareable access, and
no thread is *blocked* waiting for exclusive access, and no other thread
has upgradeable access, it acquires it. Else the thread blocks on the
"shared" cond var.

When a thread with exclusive access unlocks, it clears the exclusive flag,
and releases all waiters.

When a thread with upgradeable access unlocks, it clears the upgradeable
flag, decrements the shared count, and releases all waiters if it's the
last shared access thread.

When a thread with shared access unlocks, it decrements the shared count.
If it's the last shared access thread then it checks the upgradeable flag.
If set, then another thread is waiting for this one to go so it can
upgrade, in which case the "upgradeable" cond var is notified, else all
waiters are released.

If a thread with upgradeable access tries to upgrade, then it decrements
the shared count, but leaves the upgradeable flag set. If it was the only
shared access thread, it changes the flag to exclusive, and returns.
Otherwise, it blocks on the "upgradeable" cond var, waiting for the other
readers to exit.

"release waiters" clears the *blocked* flag, broadcasts the "shared" cond
var, and signals the "exclusive" cond var. This means that all waiting
shareable/upgradeable threads and one waiting exclusive thread become
"ready". These will then compete as if they've just entered their lock
function. This makes it "fair" --- the writers compete with the readers
whenever the mutex is completely free, but a waiting writer will prevent
new readers from adding to the existing reading set, thus preventing both
reader starvation and writer starvation.

The win32 version is basically the same, but uses Semaphores rather than
cond vars, and has to keep track of the threads waiting for shared access
so it knows how many times to signal the semaphore, as there's nothing
equivalent to a cond var broadcast.

Hope that helps.

Anthony
-- 
Anthony Williams
Just Software Solutions Ltd - http://www.justsoftwaresolutions.co.uk
Registered in England, Company Number 5478976.
Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL