O Problema do Leitores e Escritores (com mutex e semáforos)

Outro problema famoso é o caso dos leitores e escritores, que modela o acesso a uma base de dados.
Imagine, por exemplo, um sistema de reserva de linhas aéreas, com muitos processos em competição, querendo ler e escrever. É aceitável que múltiplos processos leiam a base de dados ao mesmo tempo, mas, se um processo estiver atualizando (escrevendo) na base de dados, nenhum outro processo pode ter acesso ao banco de dados, nem mesmo os leitores. A questão é: como programar os leitores e os escritores?

Na solução apresentada abaixo, para obter o acesso à base de dados, o primeiro leitor faz um down no semáforo db. Os leitores subsequentes meramente incrementam um contador, rc. Conforme saem, os leitores decrescem o contador de um e o último leitor a sair faz um up no semáforo, permitindo que um eventual escritor bloqueado entre.

Tal solução contém implicitamente uma decisão sutil que vale a pena ser comentada. Suponha que, enquanto um leitor está usando a base de dados, um outro leitor chegue. Como ter dois leitores ao mesmo tempo não é um problema, o segundo leitor é admitido. Um terceiro leitor e outros subsequentes podem também ser admitidos se chegarem.
Agora, imagine que chegue um escritor. O escritor não pode ser admitido na base de dados, pois escritores devem ter acesso exclusivo. O escritor é então suspenso. Leitores adicionais chegam. Enquanto houver pelo menos um leitor ativo, leitores subsequentes serão admitidos. Como consequência dessa estratégia, enquanto houver um fluxo estável de leitores chegando, todos entrarão assim que chegarem. O escritor permanecerá suspenso até que nenhum leitor esteja presente. Se um novo leitor chegar - digamos, a cada dois segundos - e cada leitor levar cinco segundos para fazer seu trabalho, o escritor nunca entrará.
O programa poderia ser escrito de um modo um pouco diferente: se um leitor chegar quando um escritor estiver esperando, o leitor será suspenso logo depois do escritor, em vez de ser admitido de imediato. Dessa maneira, um escritor, para terminar, precisa esperar por leitores que estavam ativos quando ele chegou, mas não por leitores que chegaram depois dele. A desvantagem dessa solução é que se consegue menos concorrência e, portanto, um desempenho menor.

A implementação da solução descrita está exemplificada abaixo para o caso de 3 leitores e 2 escritores.

Figura1: Saída do Programa
(clique na figura para melhor visualização)

Código:

#include "stdio.h"
#include "unistd.h"
#include "stdlib.h"
#include "pthread.h"
#include "semaphore.h"

#define TRUE 1

sem_t mutex;                    /* controla o acesso a 'rc' */
sem_t db;                       /* controla o acesso a base de dados */
int rc = 0;                     /* número de processos lendo ou querendo ler */

void* reader(void *arg);
void* writer(void *arg);
void read_data_base();
void use_data_read();
void think_up_data();
void write_data_base();

int main() {
sem_init(&mutex, 0, 1);
sem_init(&db, 0, 1);

pthread_t r[3], w[2];

int i;

    /* criando leitores */
    for (i = 0; i < 3 ; i++) {
 pthread_create(&r[i], NULL, reader, (void*) &i);
}

    /* criando escritores */
    for (i = 0; i< 2; i++) {
 pthread_create(&w[i], NULL, writer, (void*) &i);
}

while(TRUE);
return 0;
}

void* reader(void *arg) {
int i = *((int *) arg);

while(TRUE) {               /* repere para sempre */
 sem_wait(&mutex);       /* obtém acesso exclusivo à 'rc' */
 rc = rc + 1;            /* um leitor a mais agora */

 if (rc == 1) {          /* se este for o primeiro leitor... */
     sem_wait(&db);   
 }

 sem_post(&mutex);       /* libera o acesso exclusivo a 'rc' */
 read_data_base(i);       /* acesso aos dados */
 sem_wait(&mutex);       /* obtém acesso exclusivo a 'rc' */
 rc = rc - 1;            /* um leitor a menos agora */

 if (rc == 0) {          /* se este for o último leitor */   
     sem_post(&db);
 }

 sem_post(&mutex);       /* libera o acesso exclusivo a 'rc' */
 use_data_read(i);        /* região não crítica */
}
}

void* writer(void *arg) {
int i = *((int *) arg);

while(TRUE) {               /* repete para sempre */
 think_up_data(i);        /* região não crítica */
 sem_wait(&db);          /* obtém acesso exclusivo */
 write_data_base(i);      /* atualiza os dados */
 sem_post(&db);          /* libera o acesso exclusivo */
}
}

void read_data_base(int i) {
printf("Reader %d estah lendo os dados!\n", i);
sleep( rand() % 5);
}

void use_data_read(int i) {
printf("Reader %d estah usando os dados lidos!\n", i);
sleep(rand() % 5);
}

void think_up_data(int i) {
printf("Writer %d estah pensando no que escrever!\n", i);
sleep(rand() % 5);
}

void write_data_base(int i) {
printf("Writer %d estah escrevendo os dados!\n", i);
sleep( rand() % 5);
}

Fontes:

http://en.wikipedia.org/wiki/Readers-writers_problem
Sistemas Operacionais Modernos, 2a ed - A.S.Tanenbaum