* Re: Need to implement
2003-09-08 12:13 Need to implement Harmeet Uppal
2003-09-08 15:08 ` Mariano Moreyra
@ 2003-09-10 20:53 ` Steven
1 sibling, 0 replies; 3+ messages in thread
From: Steven @ 2003-09-10 20:53 UTC (permalink / raw)
To: Harmeet Uppal; +Cc: linux-c-programming
[-- 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 --]
^ permalink raw reply [flat|nested] 3+ messages in thread