REA - Leitor e Redator

Introdução

Em grande parte das aplicações computacionais existe uma forma de armazenamento de dados, os quais podem ser acessados simultaneamente por diversos usuários, criando, assim, a necessidade de definir uma estratégia para administrar o controle de concorrência, de forma a garantir a segurança dos dados e a não interferência entre operações. O conceito de banco de dados, abordado neste trabalho, deve ser entendido como uma abstração das diversas formas de armazenamento, seja um banco de dados, propriamente dito, memória, HD, SSD, entre outros.

O problema do leitor e redator é uma abstração de acesso à uma base de dados compartilhada, ou seja, existe a partir do momento que duas entidades tentam manipular uma mesma informação de forma simultânea. Neste caso, as manipulações são descritas em duas classes, leitor e redator (escritor), os quais realizam as operações de leitura e escrita, respectivamente.

Antes de entender o problema, é interessante compreender o conceito de região crítica, ou seção crítica, onde vários processos compartilham um mesmo recurso e os seus estados são desconhecidos entre si. Assim, um processo pode alterar a informação que estava sendo compartilhada com outro processo. No contexto do problema, apenas a operação de escrita gera seção crítica, visto que esta operação precisa carregar o valor, alterar, e salvá-lo novamente, permitindo que, no intervalo das etapas, outro processo altere a informação. A operação de leitura, por sua vez, não gera seção crítica, visto que só realiza o carregamento da informação.

O Problema

O problema do escritor e redator, portanto, refere-se a utilização simultânea de uma única base de dados a partir de diversos processos, os quais podem realizar operações distintas, como leitura e escrita. Uma primeira possível solução seria a ideia de permitir que apenas um processo acesso os dados, onde cada um teria a sua vez para manipulação. Porém, como explicado anteriormente, a leitura não é uma operação que gera região crítica, permitindo que diversos processos a realizem ao mesmo tempo. Dessa forma, seria desperdício de tempo deixar processos de leitura em espera, visto que múltiplos desses podem ser executados simultaneamente.

Existem, em um primeiro momento, três abordagens diferentes para a solução do problema do leitor e redator. A solução por preferência do leitor define que, se a base de dados está aberta para leitura, todos os processos de leitura poderão ser executados, porém, a execução de um processo escritor deve excluir mutuamente todos os leitores. Dessa forma, essa solução define que nenhum leitor deve ficar em modo de espera se o recurso está em modo de leitura.

A solução com prioridade ao leitor consegue resolver o problema do leitor e redator de forma satisfatória, todavia, em determinados casos, pode gerar um fenômeno conhecido como starvation (inanição). Nele, um processo não consegue ser executado devido ao fato de sempre existirem processos de mais alta prioridade. No contexto da solução por reader-preference, isso pode acontecer se houver uma grande lista de leitores para serem executados, fazendo com que os escritores fiquem em espera por muito tempo.

Mesmo que um escritor esteja na fila, se um novo processo leitor chegar, este será executado antes, devido ao fato de que a base de dados está aberta para leitura. A segunda solução, denominada preferência ao escritor, é implementada a fim de impedir que este problema aconteça, determinando um tempo máximo de espera dos processos escritores.

A terceira solução, por fim, estabelece uma relação de igualdade em relação à prioridade dos processos de leitura e escrita. Nessa, é adicionado uma restrição de tempo limite para ambas operações, fazendo com que nenhuma delas sofra com o problema da inanição.

As próximas seções trazem uma abordagem prática sobre o problema do leitor e escritor através de código fonte escrito na linguagem Python. Porém, antes disso, é interessante entender o conceito de exclusão mútua através de semáforos. Inicialmente, um semáforo, propriamente dito, é utilizado para evitar condições de concorrência através do controle da fila de processos, sincronizando-os para o uso de um único recurso compartilhado. A exclusão mútua, por sua vez, é um mecanismo utilizado onde a execução de um processo deve excluir todos os outros, para que este possa ter acesso único à região crítica. No contexto do problema, um processo de escrita deve excluir todos leitores.

Código

Threads são linhas de execução concorrentes em um mesmo processo (no caso, o programa em Python), no sentido de que executam simultaneamente, mas cada um com a sua própria linha de execução (quase como se fossem programas diferentes). A distinção é que programas diferentes são de fato diferentes pois cada um tem sua própria área de memória e a comunicação entre eles não é tão simples (embora seja possível com técnicas como sockets, pipes, memória compartilhada, entre outras). Threads, por sua vez, executam dentro de um mesmo processo, podendo, dessa forma, compartilhar recursos em memória diretamente. Nesse ponto entra os cuidados que devem ser tomados, como utilizar semáforos para garantir a ordem de acesso aos dados e evitar que um thread escreva enquanto outro lê.

Em um computador com apenas uma CPU os threads não são executados (realmente) ao mesmo tempo. O sistema operacional utiliza técnicas para escalonar os threads e executá-los de forma parcelada, ou seja, permitindo que todos executem um pouco de cada vez. Assim, o SO deixa um thread A executar uma parcela da sua carga de trabalho, depois decide pará-lo e passar o controle para um thread B, e assim por diante. Esse é o motivo pelo qual compartilhar memória e usar semáforos requer alguns cuidados especiais, como com as situações de bloqueio (pode ser que o thread A fique em modo de espera até que o thread B libere um recurso, enquanto que o thread B está, da mesma forma, esperando o thread A liberar outro recurso, gerando um deadlock). Por outro lado, em um computador com mais do que uma CPU, os threads podem ser executados simultaneamente, uma em cada CPU disponível e livre. Os problemas de concorrência citados ainda podem existir, mas há um desempenho melhor porque o SO tem mais facilidade em realizar o escalonamento. O fato é que, independentemente de se ter um ou mais CPUs disponíveis, não há como garantir exatamente a ordem em que os threads serão escalonados, pois esta é uma tarefa do sistema operacional.

import threading import time class SharedResource: def __init__(self): self.value = 0 class RWControll: def __init__(self): self.readers = 0 self.mutex = threading.Semaphore(1) self.lock = threading.Semaphore(1) def read_acquire(self): self.mutex.acquire() self.readers += 1 if self.readers == 1: self.lock.acquire() self.mutex.release() def read_release(self): self.mutex.acquire() self.readers -= 1 if self.readers == 0: self.lock.release() self.mutex.release() def write_acquire(self): self.lock.acquire() def write_release(self): self.lock.release() def read(lock, res): lock.read_acquire() print(threading.current_thread().ident, "Reading:", res.value) time.sleep(1.5) lock.read_release() def write(lock, res): lock.write_acquire() print(threading.current_thread().ident, "Writing") res.value += 1 time.sleep(1) lock.write_release() def executeDemo(): lock = RWControll() res = SharedResource() writer1 = threading.Thread(target=write, args=(lock, res,)) writer2 = threading.Thread(target=write, args=(lock, res,)) writer3 = threading.Thread(target=write, args=(lock, res,)) reader1 = threading.Thread(target=read, args=(lock, res,)) reader2 = threading.Thread(target=read, args=(lock, res,)) reader3 = threading.Thread(target=read, args=(lock, res,)) reader4 = threading.Thread(target=read, args=(lock, res,)) writer1.start() reader1.start() writer2.start() writer3.start() reader2.start() reader3.start() reader4.start()

A classe SharedResource não interfere no controle dos processos de leitura e escrita. É, portanto, apenas uma classe auxiliar utilizada para representar o recurso que será compartilhado, podendo ser uma abstração de um banco de dados, um bloco de memória, um arquivo, entre outros. Nesse caso, apenas um atributo numérico value é definido.

A classe RWControll realiza o controle da concorrência entre processos leitores e escritores a partir de três atributos necessários. O primeiro, readers, é um numérico que indica a quantidade de processos leitores em execução. Mutex e lock são semáforos criados a partir do módulo nativo threading da linguagem Python, usados para controle e sincronização do uso compartilhado do recurso.

Em Python, um lock pode estar em algum dos dois estados possíveis, “bloqueado” ou “desbloqueado”, sendo criado no segundo deles. Existem dois métodos básicos para manipulação: acquire e release. Quando o estado está desbloqueado, acquire altera o estado para bloqueado e retorna imediatamente. Quando o estado está bloqueado, release bloqueia até que uma chamada para liberar em outro thread o altere para desbloqueado, então a chamada acquire o redefine para bloqueado e retorna. O método release só deve ser chamado no estado bloqueado. Se for feita uma tentativa de liberar um lock desbloqueado, um RuntimeError será gerado.

Um semáforo gerencia um contador interno que é decrementado por cada chamada de acquire e incrementado por cada chamada de release. O contador nunca pode ficar abaixo de zero; quando acquire descobre que é zero, ele bloqueia, esperando até que alguma outra thread chame release.

O semáforo é implementado de tal forma que gerencia um contador atômico, representando a diferença entre a quantidade de chamadas do método release e as chamadas do método acquire, com um valor adicional se assim desejado (primeiro e único parâmetro que pode ser passado para criar um semáforo).

O método acquire realiza o bloqueio na thread atual, decrementando o contador atômico do semáforo, caso este seja maior que zero. Caso contrário, deve ficar em estado de bloqueio até que ocorra alguma chamada do método release. Release, por sua vez, desbloqueia o semáforo, além de incrementar o contador atômico.

Para o controle do problema de leitor e escritor, propriamente dito, são implementados quatro métodos para bloqueio e liberação das duas entidades. Read_acquire, por exemplo, realiza o bloqueio do recurso compartilhado para processos de leitura, através do semáforo lock, exatamente quando o primeiro processo de leitura é colocado para execução, ou seja, quando a quantidade de leitores é igual a 1. Dessa forma, o primeiro leitor bloqueia o recurso para modo leitura e, a partir deste, todos os processos leitores poderão ser executados.

Em caso de término da execução de todos os leitores, ou seja, quando a quantidade de leitores é zero, o controle pode liberar o semáforo de recurso compartilhado.

Para os processos de escrita, o controle sempre irá executar o bloqueio ou a liberação do semáforo do recurso compartilhado. Para esse caso, ocorre a situação de exclusão mútua, ou seja, uma thread de escrita deve ter acesso exclusivo à base de dados.

Por fim, read e write implementam os métodos que cada processo, leitor e escritor, respectivamente, irá executar. Ou seja, cada thread leitora irá executar este método, que apenas informa no console o valor do recurso compartilhado e a identificação da thread em execução. A chamada do sleep é usada apenas para questões de demonstração. Os processos de escrita, por sua vez, realizam uma alteração no valor do recurso compartilhado, incrementado-o em uma unidade.