[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 (
) 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 (
) 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 (
) up(W);
;
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.
Suponha que todos os semáforos (
| 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 (
|
5 ESCREVE; | |||||
| 6 up(M) ; | 6 up(W) ; | |||||
| 7 up(R) ; | 7 up(R); | |||||
| 8 } | ||||||
|
||||||
|
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
e dar um exemplo de problema que ocorreria caso as operações sobre fossem removidas.
Informações relevantes dadas pelo exercício (peguei estas informações do enunciado):
- Existem três semáforos:
, e , todos iniciados com valor . - Código do leitor (trecho relevante, com linhas numeradas no enunciado):
- linha
: down( ); - linha
: down( ); - linha
: ; - linha
: if ( ) down( ); - linha
: up( ); - linha
: up( ); - linha
: LE; (leitura) - linhas de saída: linha
: down( ); linha : ; linha : if ( ) up( ); linha : up( ).
- linha
- Código do escritor (trecho relevante):
- linha
do escritor: down( ); - linha
do escritor: down( ); - linha
do escritor: ESCREVE; - linha
: up( ); - linha
: up( ).
- linha
Observações (apenas identificação do que foi dado, nada resolvido ainda):
- Leitores tomam
por pouco tempo (linhas a ): eles usam para proteger uma pequena seção de entrada (onde atualizam via também) e liberam antes de realizar a leitura efetiva (linha ). - O escritor faz down(
) antes de tentar down( ); se um escritor obtiver ele impede novos leitores de passar por linha enquanto mantiver .
Passo 2
Entendimento do mecanismo de coordenação dos semáforos (explicação didática curta para usar depois nas interleavings):
- Semáforo
protege o recurso de escrita; quando está tomado (valor ), ninguém mais pode escrever nem o primeiro leitor pode obter o exclusivo para leitores. - Variável
conta quantos leitores estão lendo. A política usada é: o primeiro leitor que entra faz down( ) (linha quando ) para impedir escritores; o último leitor a sair faz up( ) (linha quando ). -
é um mutex para proteger acessos a (linhas , para entrada; linhas , para saída) garantindo que incrementos, decrementos e as checagens de sejam atômicas. -
é um “turnstile” curto que leitores e escritores usam ao entrar: leitores fazem down( )/up( ) em torno da subida de contador e da primeira tomada de ; escritores fazem down( ) antes de tentar down( ) e só liberam após escrever (portanto, se um escritor obtém , 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(
) (linha
do escritor). Se leitores em número arbitrário continuarem a executar a sequência de entrada que começa em linha
(down(
)) e concluírem rapidamente até a linha
(up(
)), então pode acontecer que o escritor nunca consiga executar seu down(
) porque sempre que um leitor libera
outro leitor imediato toma
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
e escritor
):
- Suponha que
entrou e está lendo (já passou de linha , está em linha ou lendo). Assim e está tomado (down( ) já foi feito pelo primeiro leitor). - O escritor
tenta escrever: executa linha (down( )) — mas nesse instante talvez ainda tem ou o escalonador não permitiu a prosseguir; em geral ficará esperando para obter se algum leitor estiver com naquele instante. - Logo após
fazer up( ) (linha ), outro leitor imediatamente faz down( ) (linha ) e entra — isto é totalmente possível se é escalonado antes de . -
faz a sequência: down( ) (linha do leitor), (linha ), possivelmente if( ) down( ) (linha ) — mas se já havia leitores, essa condição pode ser falsa; em qualquer caso libera em linha . - Depois
termina a entrada e lê. Acontece que sempre que faz up( ) outro pode executar down( ) antes do escritor ser escalonado. Se isto ocorre repetidas vezes, fica sempre atrás na fila e nunca chega a executar down( ). - Enquanto isso
está bloqueado tentando down( ) e não consegue progredir; como leitores continuam a “bater no portão” e serem escalonados primeiro, 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
chega à espera por
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
apenas por um curto intervalo e rapidamente liberam; se leituras chegam continuamente e sempre são escalonadas antes do escritor que está esperando por
, o escritor nunca chega a obter
e, portanto, nunca chega a down(
) para escrever.
Passo 4
Responder (b): papel do semáforo
— explicação didática do porquê ele é necessário.
Função de
(explicação clara e passo a passo):
-
é um mutex que serializa as operações sobre a variável compartilhada (contador de leitores). - Operações que precisam ser atômicas em relação a
: o incremento (linha ), a checagem if( ) seguida do possível down( ) (linha ), o decremento (linha ), e a checagem if( ) seguida do possível up( ) (linha ). - Sem
, 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 .
Passo 5
Exemplo concreto do problema que ocorre se removermos
— 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
(um leitor já está lendo). Dois leitores adicionais
e
tentam entrar praticamente ao mesmo tempo e o código não usa
. Sequência de passos possíveis sem
:
-
lê (veja linha ) = . -
também lê = (leitura concorrente, sem proteção). -
escreve . -
escreve . (a atualização de foi “perdida”; deveria ficar , mas ficou ) - 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 +
+ ) enquanto incorretamente. - Quando os leitores saírem, após duas saídas
poderá ficar (segundo o contador errado) e o último que observar fará up( ) (linha ), liberando o semáforo . - Porém ainda resta um leitor real dentro (porque a contagem estava errada). Com
liberado, um escritor pode conseguir down( ) 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
a contagem de leitores (
) pode ficar inconsistente (lost updates), levando a situações em que o semáforo
é 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
(comentar para total compreensão):
- Além da perda de atualização, pode ocorrer que duas threads criam simultaneamente a condição
e tentem fazer down( ) ambas; a segunda tentativa de down( ) 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 o protocolo deixa de garantir as propriedades essenciais (contagem correta de leitores e a execução exatamente uma vez de down( ) ao entrar do primeiro leitor e up( ) 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(
) (linha
) e liberam
(linha
) antes que o escritor consiga executar down(
) (linha
do escritor), fazendo com que o escritor não consiga obter
nem depois down(
), e assim seja indefinidamente adiado.
(b)
é o mutex que protege a variável compartilhada
(serializa os incrementos, decrementos e as checagens if(
) / if(
)). Sem
ocorrem race conditions (por exemplo, lost updates em
) que podem levar a liberação prematura de
e, consequentemente, a escritores entrando enquanto ainda há leitores ativos — isto viola a exclusão mútua e quebra a correção do protocolo.