Re: Need to implement

["Steven" <sos22@cam.ac.uk>]

[-- Attachment #1: Type: text/plain, Size: 3689 bytes --]

> Any clues how to implement a Read-Write lock on Linux using write
> preference.
From memory, the standard implementation on top of mutexes and
condition variables goes a bit like this:

struct biassed_lock {
	mutex lock;                 /* Lock to protect the other
				       fields of this structure. */
	int num_writers_waiting;
	int num_readers_waiting;
	int num_readers_active;
	int num_writers_active;
	pthread_cond_t event_object;
};

void write_lock(struct biassed_lock *bl)
{
	lock(bl->lock);
	bl->num_writers_waiting++;
	while (bl->num_readers_active || bl->num_writers_active)
		pthread_cond_wait(bl->event_object, bl->lock);
	bl->num_writers_waiting--;
	bl->num_writers_active++;
	unlock(bl->lock);
}

void read_lock(struct biassed_lock *bl)
{
	lock(bl->lock);
	bl->num_readers_waiting++;
	while (bl->num_writers_active || bl->num_writers_waiting)
		pthread_cond_wait(bl->event_object, bl->lock);
	bl->num_readers_active++;
	bl->num_readers_waiting--;
	unlock(bl->lock);
}

void upgrade_lock(struct biassed_lock *bl)
{
	lock(bl->lock);
	bl->num_writers_waiting++;
	assert(bl->num_writers_active == 0);
	while (bl->num_readers_active > 1)
		pthread_cond_wait(bl->event_object, bl->lock);
	assert(bl->num_writers_active == 0);
	bl->num_writers_active++;
	bl->num_readers_active--;
	bl->num_readers_waiting--;
	unlock(bl->lock);
}

void write_unlock(struct biassed_lock *bl)
{
	lock(bl->lock);
	bl->num_writers_active--;
	pthread_cond_broadcast(bl->event_object);
	unlock(bl->lock);
}

void read_unlock(struct biassed_lock *bl)
{
	lock(bl->lock);
	bl->num_readers_active--;
	pthread_cond_broadcast(bl->event_object);
	unlock(bl->lock);
}

Internally, the behaviour is roughly this:

1) Unless bl->lock is held:
   a) bl->num_readers_active is the number of threads currently
   holding a read lock on bl.
   b) bl->num_readers_waiting is the number of threads currently
   waiting for a read lock on bl.
   c) bl->num_writers_active is the number of threads currently
   holding a write lock on bl (either 0 or 1).
   d) bl->num_writers_waiting is the number of threads currently
   waiting for a write lock on bl.
2) num_{readers,writers}_{active,waiting} are only ever modified with
   the lock held.
3) event_object is signalled whenever bl->num_writers_active or
   bl->num_readers_active decreases.

Externally, a biassed_lock behaves like this:

4) If a thread enters write_lock while a read lock is in place,
   it will block until the read lock is removed.
5) If a thread enters write_lock while a write lock is in place,
   it will block until the write lock is removed.
6) If a thread enters read_lock while a write lock is in place or
   while another thread is waiting for a write lock, it will
   block until those write locks have been acquired and released.
7) If a thread enters write_unlock with other threads blocked
   trying to acquire a write lock, it will unblock precisely one
   of those.  Otherwise, if there are threads trying to acquire
   a read lock, it will unblock all of those.  Otherwise, it
   just marks the lock as available.
8) If a thread enters read_unlock with other threads blocked
   trying to acquire a write lock, and it is the last thread to
   hold a read lock, it will unblock precisely one of the threads
   trying to get the write lock.
9) If a thread holds a read lock, then calling upgrade_lock(bl) is
   equivalent to calling read_unlock(bl); write_lock(bl);, except
   that it is atomic.


It's been a while since I've needed to do anything like this, though,
so test thoroughly...

Steven Smith,
sos22@cam.ac.uk.

[-- Attachment #2: Type: application/pgp-signature, Size: 187 bytes --]