RW-lock is widely used synchronization technique. It allows multiply readers to go through the barrier if there is no writers and only one writer at one time.
This incredibly could speed up application if you expect more readers than writers and amount of readers is high(here should be some heuristic because if you have few readers and time of data lock in reader is small using rw-locks might be overhead).
You likely will find rw-lock mechanism in POSIX threads(pthread_rwlock_init, pthread_rwlock_rdlock, pthread_rwlock_wrlock, pthread_rwlock_unlock). As pthreads is a POSIX interface you will likely find it on any POSIX-compliant system.
When we are talking about process synchronization we'll more likely think about semaphores.
There is no such thing as rw-lock semaphore(some system have indeed).
Of course you still may set PTHREAD_PROCESS_SHARED on pthread rw-lock with pthread_rwlockattr_setpshared. But if you still want to use semaphores ...
Keeping in mind that rw-lock is operated by two types of tasks two semaphores are needed. One for writer. It will be binary semaphore. And one for readers. It will be counting semaphore.
When the reader tries to get the lock it checks if there is no writers. If nobody is writing, the reader increments counting semaphore and proceeds. On 'unlock' the reader just decrement the counting semaphore and that's all.
When the writer tries to 'lock' it takes(decrements) binary semaphore and wait until all readers finish their work. When there's no readers the writer proceeds. On 'unlock' the writer releases(increments) binary semaphore.
Look at the implementation below:
#include <semaphore.h>
#include <errno.h>
struct rwlock {
sem_t rlock;
sem_t wlock;
};
void init_rwlock(struct rwlock *rw);
void destroy_rwlock(struct rwlock *rw);
void rlock(struct rwlock *rw);
void runlock(struct rwlock *rw);
void wlock(struct rwlock *rw);
void wunlock(struct rwlock *rw);
void init_rwlock(struct rwlock *rw)
{
sem_init(&rw->rlock, 1, 0);
sem_init(&rw->wlock, 1, 1);
}
void destroy_rwlock(struct rwlock *rw)
{
wlock(rw);
sem_destroy(&rw->rlock);
sem_destroy(&rw->wlock);
}
void rlock(struct rwlock *rw)
{
sem_wait(&rw->wlock);
sem_post(&rw->rlock);
sem_post(&rw->wlock);
}
void wlock(struct rwlock *rw)
{
int readers = 0;
sem_wait(&rw->wlock);
do {
if (sem_getvalue(&rw->rlock, &readers) != -1) {
if (readers == 0) {
break;
}
}
usleep(1);
} while (1);
}
void runlock(struct rwlock *rw)
{
do {
if (sem_trywait(&rw->rlock) == -1) {
if (errno != EAGAIN) {
continue;
}
}
break;
} while (1);
}
void wunlock(struct rwlock *rw)
{
sem_post(&rw->wlock);
}This interface could be used by calling pairs rlock/runlock and wlock/wunlock. Check out next piece of code:#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <errno.h>
#include <sys/mman.h>
int *counter;
struct rwlock *rw;
void reader(void)
{
do {
rlock(rw);
printf(">>>>reader: counter %d\n", *counter), fflush(NULL);
if (*counter == 16777216) {
runlock(rw);
break;
}
usleep(1);
runlock(rw);
} while(1);
}
void writer(void)
{
do {
wlock(rw);
++*counter;
printf(">>>>writer: new counter %d\n", *counter), fflush(NULL);
if (*counter == 16777216) {
wunlock(rw);
break;
}
wunlock(rw);
} while (1);
}
int main(int argc, char **argv)
{
pid_t children[100];
int i;
counter = mmap(NULL, sizeof(int), PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, 0, 0);
rw = mmap(NULL, sizeof(struct rwlock), PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, 0, 0);
*counter = 0;
init_rwlock(rw);
for (i=0;i<100;++i) {
children[i] = fork();
if (children[i] == -1) {
printf("Problem with creating %d child: ''", i, strerror(errno)), fflush(NULL);
}else if (children[i] == 0) {
if (i%3 == 0) {
writer();
}else {
reader();
}
}
}
wait(NULL);
return 0;
}Here 100 processes have been started where 1/3 are writers. You likely see that here permitted any number of readers. This could be a bottleneck if writer has to wait too long. pthreads rw-lock suffers from the same disease.To make limitation on readers rlock function should be modified to check amount of readers that are currently holding the lock. With reader limitation rw-lock on semaphores will likely look like:
struct rwlock {
sem_t rlock;
sem_t wlock;
int readers;
};
void init_rwlock(struct rwlock *rw, int readers);
void destroy_rwlock(struct rwlock *rw);
void rlock(struct rwlock *rw);
void runlock(struct rwlock *rw);
void wlock(struct rwlock *rw);
void wunlock(struct rwlock *rw);
void init_rwlock(struct rwlock *rw, int readers)
{
sem_init(&rw->rlock, 1, 0);
sem_init(&rw->wlock, 1, 1);
rw->readers = readers;
}
void destroy_rwlock(struct rwlock *rw)
{
wlock(rw);
sem_destroy(&rw->rlock);
sem_destroy(&rw->wlock);
}
void rlock(struct rwlock *rw)
{
int readers;
do {
sem_wait(&rw->wlock);
if (sem_getvalue(&rw->rlock, &readers) != -1) {
if (readers < rw->readers) {
sem_post(&rw->rlock);
sem_post(&rw->wlock);
break;
}
}
sem_post(&rw->wlock);
usleep(1);
} while (1);
}
void wlock(struct rwlock *rw)
{
int readers = 0;
sem_wait(&rw->wlock);
do {
if (sem_getvalue(&rw->rlock, &readers) != -1) {
if (readers == 0) {
break;
}
}
usleep(1);
} while (1);
}
void runlock(struct rwlock *rw)
{
do {
if (sem_trywait(&rw->rlock) == -1) {
if (errno != EAGAIN) {
continue;
}
}
break;
} while (1);
}
void wunlock(struct rwlock *rw)
{
sem_post(&rw->wlock);
}The semaphores is really powerful tool for building different synchronization schemes.
