rwlock and reader/writer starvation
pthread reader/writer lock is one of the few pthread synchronization and coordination primitives. It has the following features:
- it allows multiple readers owning the lock at the same time, but only one writer at a time.
Above is obvious. If only one owner at a time, then it has no difference from a mutex. This allow both coordination ( doing things in sequence one by one ), and synchronization ( several readers doing things at the same time, thus so called “sync” ). Note that mutex only help coordination.
- It allows a "named ownership".
A rwlock has a "named owner" associated with it. This is in contrast with semaphores, which has no owner and anybody can legally post on a semaphore with defined behaviors.
With ownership comes the responsibility. If a thread accidentally unlock a rwlock it does not own, the behavior is “undefined". ( unlock a mutex that one does not own will get an error, which is a defined behavior".
Posix states that unlocking a rwlock without owning it results “undefined” behavior ( which can be a SIGSEGV, or SIGBUS, or nothing ). This might be to alleviate the burden of the kernel to track multiple readers owning the lock at the same time. The owner tracking must be done inside kernel and it is easier to track one owner instead of tracking multiple owners.
http://pubs.opengroup.org/onlinepubs/007908799/xsh/pthread_rwlock_unlock.html
Take a look at the GNU implementation of rwlock below. Note that “__lock” is used to protect all other elements inside the structure. “__shared” is to share the rwlock at process level as well as thread level. Other elements inside the structure is to facilitate the individual implementation.
(gdb) ptype pthread_rwlock_t
type = union {
struct {
int __lock;
unsigned int __nr_readers;
unsigned int __readers_wakeup;
unsigned int __writer_wakeup;
unsigned int __nr_readers_queued;
unsigned int __nr_writers_queued;
int __writer;
int __shared;
long unsigned int __pad1;
long unsigned int __pad2;
unsigned int __flags;
} __data;
char __size[56];
long int __align;
}
what is writer starvation and reader starvation?
Rwlock allows several readers owning the lock at the same time but only one writer owning the rwlock at a time.
Consider the following scenarios:
1. the rwlock is owned by a writer, and a bunch of other writers and readers are waiting, when the owner unlock it, shall we wake up one writer? Or wake up all the readers?
POSIX did not clearly say what should be done in such scenario. If an implementation chooses to wake up a writer, in the case that new writers keeps on coming forever, none of the readers would get a chance to own the lock, no matter how long they have been waiting. This is so called reader starvation.
2. the rwlock is owned by a reader, and a bunch of writers are waiting, a new reader comes in, shall this new reader get the lock? Or wait behind the writers who came earlier?
POSIX again left this to implementation. If an implementation chooses to have the new reader to get the lock as well, new readers can keep on coming forever, thus none of the writers would get a chance to own. This is so called writer starvation.
From above, one can see that an implementation cannot avoid reader starvation as well as writer starvation. One has to make a choice. In some use cases, reader starvation is a bigger sin whereas in some use cases, the writer starvation is a bigger sin.
An implementation that choose to have “reader starvation” problem is called “writer heavy/preferred”.
An implementation that choose to have “writer starvation” problem is called “reader heavy/preferred”.
An implantation can also alternatively let the user to initialize the rwlock to be “writer heavy or reader heavy”. The “__flags” in the rwlock data structure is for that purpose.
following is code snippet:
#include <pthread.h>
#include <stdio.h>
void main(void)
{
pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER;
pthread_rwlockattr_t rwlock_attr;
int pref;
printf("default rwlock is reader heavy/preferred: %d\n", rwlock.__data.__flags);
pthread_rwlockattr_init(&rwlock_attr);
pthread_rwlockattr_getkind_np(&rwlock_attr, &pref);
printf("default rwlock attr is reader heavy/preferred: %d\n", pref);
pthread_rwlockattr_setkind_np(&rwlock_attr, PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
pthread_rwlockattr_getkind_np(&rwlock_attr, &pref);
printf("setting rwlock attr to writer heavy/preferred: %d\n", pref);
pthread_rwlock_init(&rwlock, &rwlock_attr);
printf("rwlock is writer heavy/preferred after init: %d\n", rwlock.__data.__flags);
}
output:
default rwlock is reader heavy/preferred: 0
default rwlock attr is reader heavy/preferred: 0
setting rwlock attr to writer heavy/preferred: 2
rwlock is writer heavy/preferrred after init: 1
Summary: An rwlock implementation will suffer either reader starvation or writer starvation. An implementation can allow users to choose which starvation they can tolerate based on the exact use cases.