[27]. Considere o problema dos leitores e escritores, onde existem diversos processos que eventualmente fazem acessos de leitura a uma base de dados e diversos processos que eventualmente fazem acessos de escrita à mesma base. Vários acessos de leitura podem ocorrer simultaneamente, mas um acesso de escrita não pode ocorrer simultaneamente com acessos de nenhum tipo. Considere o código a seguir para os processos de leitura e de escrita.
Suponha que todos os semáforos ( \mathrm{R}, \mathrm{M}, \mathrm{W} ) são iniciados com valor 1 :
leitor: escritor:
1 while(1) { 1 while(1) {
2 down(R); 2 ...produz
3 down(M); 3 down(R);
4 rc++; 4 down(W);
5 if ( \mathrm{rc}==1 ) down(W); 5 ESCREVE;
6 up(M) ; 6 up(W) ;
7 up(R) ; 7 up(R);
8 }
8 LE;
9 down(M);
10 rc--;
11 if ( \mathrm{rc}==0 ) up(W);
12 \operatorname{up}(\mathrm{M});
13 ... consome
}
a) Essa solução pode levar a starvation de escritores? (pode acontecer de um escritor nunca conseguir o acesso à base devido à seguida chegada de novos leitores?) Explique sua resposta, usando os números das linhas de código para se referir aos passos do programa.
b) Explique o papel do semáforo M . Dê um exemplo de problema que poderia ocorrer caso as operações sobre ele fossem retiradas.

Passo 1

Vou deixar claro o que o enunciado pede e quais informações ele dá (vou referir-me às linhas do código pelo número que aparece no enunciado, usando os nomes dos semáforos exatamente como dados).
O enunciado pede:
  • (a) Determinar se a solução apresentada pode causar starvation de escritores (isto é, se é possível que um escritor nunca consiga acesso por causa da chegada contínua de leitores). Pedirão uma explicação usando os números das linhas do programa.
  • (b) Explicar o papel do semáforo M e dar um exemplo de problema que ocorreria caso as operações sobre M fossem removidas.
Informações relevantes dadas pelo exercício (peguei estas informações do enunciado):
  • Existem três semáforos: R, M e W, todos iniciados com valor 1.
  • Código do leitor (trecho relevante, com linhas numeradas no enunciado):
    • linha 2: down( R);
    • linha 3: down( M);
    • linha 4: \mathrm{rc}++;
    • linha 5: if ( \mathrm{rc}==1) down( W);
    • linha 6: up( M);
    • linha 7: up( R);
    • linha 8: LE; (leitura)
    • linhas de saída: linha 9: down( M); linha 10: \mathrm{rc}--; linha 11: if ( \mathrm{rc}==0) up( W); linha 12: up( M).
  • Código do escritor (trecho relevante):
    • linha 3 do escritor: down( R);
    • linha 4 do escritor: down( W);
    • linha 5 do escritor: ESCREVE;
    • linha 6: up( W);
    • linha 7: up( R).
Observações (apenas identificação do que foi dado, nada resolvido ainda):
  • Leitores tomam R por pouco tempo (linhas 2 a 7): eles usam R para proteger uma pequena seção de entrada (onde atualizam \mathrm{rc} via M também) e liberam R antes de realizar a leitura efetiva (linha 8).
  • O escritor faz down( R) antes de tentar down( W); se um escritor obtiver R ele impede novos leitores de passar por linha 2 enquanto mantiver R.

Passo 2

Entendimento do mecanismo de coordenação dos semáforos (explicação didática curta para usar depois nas interleavings):
  • Semáforo W protege o recurso de escrita; quando W está tomado (valor 0), ninguém mais pode escrever nem o primeiro leitor pode obter o exclusivo para leitores.
  • Variável \mathrm{rc} conta quantos leitores estão lendo. A política usada é: o primeiro leitor que entra faz down( W) (linha 5 quando \mathrm{rc}==1) para impedir escritores; o último leitor a sair faz up( W) (linha 11 quando \mathrm{rc}==0).
  • M é um mutex para proteger acessos a \mathrm{rc} (linhas 3, 6 para entrada; linhas 9, 12 para saída) garantindo que incrementos, decrementos e as checagens de \mathrm{rc} sejam atômicas.
  • R é um “turnstile” curto que leitores e escritores usam ao entrar: leitores fazem down( R)/up( R) em torno da subida de contador e da primeira tomada de W; escritores fazem down( R) antes de tentar down( W) e só liberam R após escrever (portanto, se um escritor obtém R, ele impede novos leitores de entrar na região de entrada).

Passo 3

Responder (a): análise de possibilidade de starvation de escritores com um exemplo de interleaving explícito e intuitivo.
Intuição: para um escritor conseguir escrever ele precisa, entre outras coisas, obter down( R) (linha 3 do escritor). Se leitores em número arbitrário continuarem a executar a sequência de entrada que começa em linha 2 (down( R)) e concluírem rapidamente até a linha 7 (up( R)), então pode acontecer que o escritor nunca consiga executar seu down( R) porque sempre que um leitor libera R outro leitor imediato toma R antes do escritor ser escalonado — isto é, leitores “passam pela catraca” continuamente. Como os semáforos em si não asseguram que um processador esperando será atendido imediatamente (não garantem fairness estrita), existe a possibilidade prática de que o escritor seja continuamente preterido. Vou mostrar um esquema de interleaving que ilustra isso.
Exemplo de interleaving (cronologia simplificada usando leitores L_1,L_2,\dots e escritor W_1):
  1. Suponha que L_1 entrou e está lendo (já passou de linha 7, está em linha 8 ou lendo). Assim \mathrm{rc}\ge1 e W está tomado (down( W) já foi feito pelo primeiro leitor).
  2. O escritor W_1 tenta escrever: executa linha 3 (down( R)) — mas nesse instante talvez L_1 ainda tem R ou o escalonador não permitiu a W_1 prosseguir; em geral W_1 ficará esperando para obter R se algum leitor estiver com R naquele instante.
  3. Logo após L_1 fazer up( R) (linha 7), outro leitor L_2 imediatamente faz down( R) (linha 2) e entra — isto é totalmente possível se L_2 é escalonado antes de W_1.
  4. L_2 faz a sequência: down( M) (linha 3 do leitor), \mathrm{rc}++ (linha 4), possivelmente if( \mathrm{rc}==1) down( W) (linha 5) — mas se já havia leitores, essa condição pode ser falsa; em qualquer caso L_2 libera R em linha 7.
  5. Depois L_2 termina a entrada e lê. Acontece que sempre que L_i faz up( R) outro L_{i+1} pode executar down( R) antes do escritor W_1 ser escalonado. Se isto ocorre repetidas vezes, W_1 fica sempre atrás na fila e nunca chega a executar down( R).
  6. Enquanto isso W_1 está bloqueado tentando down( R) e não consegue progredir; como leitores continuam a “bater no portão” e serem escalonados primeiro, W_1 pode ficar indefinidamente bloqueado — isto é starvation.
Comentário sobre fairness: se a implementação de semáforo e o escalonador do sistema forem estritamente justos (por exemplo, FIFO entre aguardantes), então quando W_1 chega à espera por R ele será atendido em ordem e leitores subsequentes não irão ultrapassá‑lo — nesse caso a starvation não ocorre. Mas em modelos gerais de semáforos e escalonamento não se pode garantir essa justiça, logo a solução dada pode sim sofrer starvation de escritores na prática.
Conclusão deste passo (resumindo a razão): a razão da possível starvation é que leitores pegam R apenas por um curto intervalo e rapidamente liberam; se leituras chegam continuamente e sempre são escalonadas antes do escritor que está esperando por R, o escritor nunca chega a obter R e, portanto, nunca chega a down( W) para escrever.

Passo 4

Responder (b): papel do semáforo M — explicação didática do porquê ele é necessário.
Função de M (explicação clara e passo a passo):
  • M é um mutex que serializa as operações sobre a variável compartilhada \mathrm{rc} (contador de leitores).
  • Operações que precisam ser atômicas em relação a \mathrm{rc}: o incremento \mathrm{rc}++ (linha 4), a checagem if( \mathrm{rc}==1) seguida do possível down( W) (linha 5), o decremento \mathrm{rc}-- (linha 10), e a checagem if( \mathrm{rc}==0) seguida do possível up( W) (linha 11).
  • Sem M, duas ou mais threads leitoras poderiam executar essas operações de maneira intercalada (race) produzindo contagens erradas ou decisões erradas sobre tomar ou liberar W.

Passo 5

Exemplo concreto do problema que ocorre se removermos M — cenário com perda de atualização que pode violar exclusão mútua (este exemplo é simples de raciocinar na prova e evidencia o perigo):
Considere situação inicial com \mathrm{rc}=1 (um leitor já está lendo). Dois leitores adicionais L_a e L_b tentam entrar praticamente ao mesmo tempo e o código não usa M. Sequência de passos possíveis sem M:
  1. L_a \mathrm{rc} (veja linha 4) = 1.
  2. L_b também lê \mathrm{rc} = 1 (leitura concorrente, sem proteção).
  3. L_a escreve \mathrm{rc} \leftarrow 2.
  4. L_b escreve \mathrm{rc} \leftarrow 2. (a atualização de L_a foi “perdida”; deveria ficar 3, mas ficou 2)
  5. Nenhum dos dois detectou corretamente a condição de “primeiro leitor” (dependendo do caso), mas o ponto crítico é: agora efetivamente há três leitores dentro (o original + L_a + L_b) enquanto \mathrm{rc}=2 incorretamente.
  6. Quando os leitores saírem, após duas saídas \mathrm{rc} poderá ficar 0 (segundo o contador errado) e o último que observar \mathrm{rc}==0 fará up( W) (linha 11), liberando o semáforo W.
  7. Porém ainda resta um leitor real dentro (porque a contagem estava errada). Com W liberado, um escritor pode conseguir down( W) e começar a escrever enquanto esse leitor remanescente ainda está na seção de leitura — violação direta da exclusão mútua entre leitores e escritores.
Esse exemplo mostra claramente que sem M a contagem de leitores ( \mathrm{rc}) pode ficar inconsistente (lost updates), levando a situações em que o semáforo W é liberado prematuramente e um escritor entra enquanto ainda existe leitor ativo — isso quebra a correção do protocolo.

Passo 6

Outro tipo de problema sem M (comentar para total compreensão):
  • Além da perda de atualização, pode ocorrer que duas threads criam simultaneamente a condição \mathrm{rc}==1 e tentem fazer down( W) ambas; a segunda tentativa de down( W) ficará bloqueada dentro da seção de entrada do leitor — isto deixa um leitor bloqueado em estado de entrada, podendo confundir contagens e causar deadlocks em algumas interações com escritores. Em resumo: sem M o protocolo deixa de garantir as propriedades essenciais (contagem correta de leitores e a execução exatamente uma vez de down( W) ao entrar do primeiro leitor e up( W) ao sair do último leitor).

Passo 7

Resumo final das respostas objetivas (vou colocá‑las aqui de forma direta para conferência).

Resposta

(a) Sim. Pode ocorrer starvation de escritores: se leitores chegarem continuamente e forem sempre escalonados antes do escritor, eles repetidamente executam down( R) (linha 2) e liberam R (linha 7) antes que o escritor consiga executar down( R) (linha 3 do escritor), fazendo com que o escritor não consiga obter R nem depois down( W), e assim seja indefinidamente adiado.
(b) M é o mutex que protege a variável compartilhada \mathrm{rc} (serializa os incrementos, decrementos e as checagens if( \mathrm{rc}==1) / if( \mathrm{rc}==0)). Sem M ocorrem race conditions (por exemplo, lost updates em \mathrm{rc}) que podem levar a liberação prematura de W e, consequentemente, a escritores entrando enquanto ainda há leitores ativos — isto viola a exclusão mútua e quebra a correção do protocolo.

Exercícios relacionados