ALGORITMOS: Os Leitores e os Escritores

Este problema é o segundo da nossa série de estudos em programação concorrente. Ele é uma alegoria dos problemas que os processos concorrentes enfrentam ao acessar uma área de memória compartilhada. Consiste no seguinte:

Há uma praça pública em Atenas onde, no meio da qual, os escribas anotam em uma placa pendurada num pilar as resoluções tomadas pela Assembléia do Povo. Essa placa pode ser lida por todo o povo, desde que haja o que ler; mas somente um escriba pode escrevê-la por vez. Outrossim, para que os escribas possam realizar o seu trabalho, é necessário que a aglomeração do povo ao redor da placa não os impeça de acessá-la.

Podemos então extrair os requisitos do problema, fazer algumas considerações e propor um algoritmo.

a) Um escriba por vez pode escrever na placa.

b) Cada plebeu pode lê-la simultaneamente, contanto que haja algo a ler.

c) Quando um escriba desejar escrever a placa, não estando ela sendo escrita, o povo ao redor deve afastar-se.

Como os escribas apenas recebem resoluções da Assembléia e as escrevem na placa, não precisamos nos preocupar se há um outro escriba no conjunto que tenha algo a escrever inadvertidamente. Assim, podemos imaginar os escribas organizados em uma fila. Se há uma resolução tomada, a Assembléia manda o escriba detentor da vez escrever algo. Em sequência, o escriba dá lugar a todos os outros para que possam escrever, cada um a sua vez, por ordem. É necessário perceber também que há um conjunto fixo de escribas para a Assembléia. A Assembléia, que é organizada, não haverá de contratar novos escribas no meio do processo legislativo.

Terminado o trabalho do escriba, a Assembléia convoca o povo e este lê. Com uma nova resolução a ser escrita, o povo é disperso e reconvocado depois. Repare que não precisamos nos preocupar imediatamente na leitura por cada cidadão, pois estes estão abstraídos em “povo.” O objeto “Povo” é dispersado e convocado. Este objeto é o que tratará da dispersão e convocação de cada um de seus membros.

Cada plebeu lê a placa pelo tempo que achar necessário. Isso não é um dado relevante para ser tratado.

Assim, nós temos o algoritmo seguinte em pseudocódigo orientado a objeto que segue abaixo. Repare que o método de execução paralela é Plebeu.iniciar.

1. Programa Principal

 

   enquanto Assembleia.emSessao ( )
   {
      Se Assembleia.novaResolucao ( )
      {
         Se (Povo.leitores ( ) > 0)
         {
            Povo.dispersar ( )
         }
         e = Escribas.dequeue ( )
         e.escrever ( )
         Escribas.enqueue (e)        
         Povo.convocar ( )     
      }
   }

 
2. Povo.convocar ( )

   n = 1
   enquanto (n <= quantidade ( ))
   {
      Plebeu = dequeue ( )
     
Plebeu.iniciar ( )
      enqueue (Plebeu)
      n = n + 1
   }

   enquanto (leitores ( ) < quantidade ( )) {  }

 

3. Povo.dispersar ( )

   n = 1
   enquanto (n <= quantidade ( ))
   {
      Plebeu = dequeue ( )
      Se Plebeu.lendo ( )
      {
         Plebeu.sair ( )
      }
      enqueue (Plebeu)
      n = n + 1
   }

   enquanto (leitores ( ) > 0) {  }

 

4. Plebeu.ler ( )

   lendo (verdade)
   Povo.getMutex ( ).lock( )
   Povo.adicionarLeitor ( )
   Povo.getMutex ( ).unlock ( )   
   sair ( )

 
5. Plebeu.iniciar ( )
(Plebeu herda Thread)

ler ( )
 
6. Plebeu.sair ( )

   lendo (falso)
   Povo.getMutex ( ).lock( )
   Povo.subtrairLeitor ( )
   Povo.getMutex ( ).unlock ( )

Anúncios

Os comentários estão desativados.