Problema de leitores e editores

O problema de leitores e escritores é um problema clássico da teoria da computação , que permite modelar o acesso a bancos de dados .

Foi afirmado desta forma por Edsger Dijkstra , que também está na origem do problema do jantar dos filósofos (problema relacionado em particular com a ordenação dos processos).

O problema

Suponha que um banco de dados tenha leitores e gravadores, e os leitores e gravadores desse banco de dados precisem ser programados.

As restrições são as seguintes:

• vários leitores devem ser capazes de ler o banco de dados ao mesmo tempo;
• se um editor está modificando o banco de dados, nenhum outro usuário (nem editor nem leitor) deve ser capaz de acessá-lo.

Soluções

É muito simples colocar o editor em espera enquanto ainda há leitores.

Mas essa solução apresenta grandes problemas, se o fluxo de leitores for regular: o editor pode ter que esperar um tempo infinito.

Existe, portanto, uma segunda solução, que consiste em colocar em espera todos os leitores que enviaram seu pedido de acesso após o de um editor.

Edsger Dijkstra , que formulou esse problema, se propõe a resolvê-lo por meio de semáforos .

Solução com uso de semáforos e prioridade aos leitores

A solução a seguir resolve o problema dos leitores e escritores priorizando os leitores. Esta solução requer três semáforos e uma variável, a saber:

• Um semáforo M_Lect , inicializado em 1, que permite que a variável seja protegida lect. Portanto, é um mutex .
• Um semáforo M_Red , inicializado em 1, que permite o bloqueio das tarefas de escrita (dando prioridade aos leitores). Portanto, é um mutex .
• Um semáforo vermelho , inicializado em 1, permite que as tarefas de leitura sejam bloqueadas se a escrita estiver em andamento.
• Uma variável lectque conta o número de leitores.

Esta solução usa os quatro métodos a seguir:

Comece a ler Commencer_Lire: P(M_Lect) SI (red) ALORS pbloque=true V(M_Lect) p(synch) FIN SI SINON lect++; V(M_Lect)

Este método aumenta o número de leitores; então, se este for o primeiro leitor a tentar entrar, ele só permitirá a entrada se não houver nenhuma escrita atual. Caso contrário, o método deve esperar até que o esboço seja concluído. A utilização de dois semáforos para os editores permite induzir a prioridade aos leitores.

Terminar uma leitura Finir_Lire: P(M_Lect) lect-- SI Lect==0 ALORS V(Red) FIN SI V(M_Lect)

Este método diminui o número de leitores. Então, se este for o último leitor a sair, permite que os editores entrem (se necessário).

Comece a escrever Commencer_Ecrire: P(M_Red) P(Red) SI (red or lect>0) ALORS pbloque=true V(Red) SINON red=true V(Red) V(M_Red)

Este método usando o semáforo M_Red torna possível garantir que a prioridade seja dada aos leitores no final de um gravador (na verdade, o final de um gravador libera o semáforo Vermelho - liberando assim um possível leitor - antes de liberar o semáforo M_Red).

Terminar uma escrita Finir_Ecrire: V(Red) V(M_Red)

Este método permite garantir que a prioridade seja dada aos leitores (de fato, liberar o semáforo vermelho libera um possível leitor antes de liberar um possível editor usando o semáforo M_Red).

Solução com cópia assíncrona da estrutura de dados

Suponha que o objetivo dos leitores seja ler dados de forma assíncrona. Todos os leitores têm as informações no momento em que sua solicitação (possivelmente de uma máquina remota) foi feita.

Ou um ponteiro DATA para uma estrutura de dados contendo todas as informações disponíveis. Os editores enviarão solicitações que serão armazenadas em uma fila FILE .

Um mutex M1 protege a seguinte estrutura:

Liste de DATA : PRECEDENT DATA : ACTUEL DATA : PROCHAIN booléen : MISAJOUR

Um mutex M2 protege a seguinte estrutura:

File de mises à jour : FILE Date de dernière modification : DERNIER Código executado pelo leitor verrouille M1: si MISAJOUR est vrai: enfile ACTUEL dans PRECEDENT pour chaque élément de PRECEDENT: effacer l'élément si son compteur de références est nul (1) fin pour ACTUEL := PROCHAIN (2) PROCHAIN := copie de ACTUEL MISAJOUR := faux fin si récupérer un pointeur P sur ACTUEL et incrémenter son compteur de références déverrouille M1 lire dans P ... décrémenter le compteur de références de P Código executado pelo escritor verrouille M2: enfiler les modifications dans FILE si DERNIER est dépassé de 10 secondes: verrouiller M1: effectuer toute modification de FILE dans PROCHAIN vider FILE MISAJOUR := vrai (3) déverrouille M1 fin si déverrouille M2 Observações

1. Quando a estrutura de dados é atualizada, sua versão anterior pode permanecer como um ponteiro em processos leves concorrentes. Uma boa maneira de evitar vazamentos de memória é, portanto, manter um contador de referência para apagar as áreas de memória apontadas quando nenhum processo estiver usando-o.
2. CURRENT e NEXT sendo ponteiros estáticos, copiar o segundo para o primeiro é equivalente a uma atribuição de ponteiro. Como dito no primeiro ponto, o ponteiro antigo permanece nos processos leves executados anteriormente. Por outro lado, na linha seguinte, realiza-se uma cópia completa dos dados apontados por CURRENT e aponta-se para PRÓXIMO da cópia.
3. Simplesmente definir este booleano como true permitirá que futuros leitores usem a versão correta dos dados.

Este modelo é adequado quando as atualizações não requerem gerenciamento de transações, que os bancos de dados devem fornecer .

Veja também

• Luigi Zaffalon e Pierre Breguet, Programação simultânea e em tempo real com ADA 95 , Presses polytechniques et universitaire romandes, Lausanne , 1999
• jantar dos filósofos