Threads, Semáforos e Deadlocks – O Jantar dos Filósofos

Neste artigo o nosso assunto central será a programação concorrente. Este paradigma foca-se principalmente na interação e execução de multitarefas, assim sendo, uma das principais preocupações quando nos deparamos com um algoritmo deste género são os problemas que podem ocorrer na sincronização e na partilha de recursos.

As vantagens da programação concorrente são o aumento do desempenho do programa, devido ao aumento da quantidade de tarefas que podem ser executadas durante um determinado período de tempo.

Ao longo das próximas linhas vamos debruçarmo-nos sobre alguns factos deste género de programação.

Como referimos há pouco, um dos principais problemas a ter em conta é o problema da sincronização. E podemos considerar vários casos neste problema, quer seja com ler e/ou escrever um ficheiro, partilhar recursos ou ter o problema do produtor-consumidor com um entrepósito limitado.

Mas antes de avançarmos, vamos recuar ainda um pouco atrás de modo a que o leitor se recorde e/ou familiarize mais simplesmente com esta temática.

A programação concorrente é um paradigma de programação usado na construção de programas de computador que fazem uso da execução concorrente de várias tarefas computacionais que podem ser implementadas como programas separados ou como um conjunto de threads criadas por um único programa. Nesta altura faz sentido diferenciar o termo processo do termo thread, enquanto que para executar um processo precisamos de uma pilha e de valores de registo que nos dizem o estado desse processo, uma thread é uma linha ou contexto de execução, ou seja é uma forma de um processo se dividir a si mesmo em duas ou mais tarefas que podem ser executadas concorrentemente.

As threads podem compartilhar o mesmo espaço de memória assim como podem partilhar as mesmas variáveis, ao contrário dos processos que têm as suas próprias variáveis, pilha e alocação de memória.

Por este motivo caro leitor, é fácil admitirmos que criar e finalizar uma thread é mais rápido e mais simples do que fazer a mesma operação utilizando processos. A comunicação entre threads é também mais simples que a comunicação entre processos, uma vez que as variáveis usadas são comuns.

As threads podem ser implementadas pelo programador ou ser implementadas automaticamente pelo kernel. Por exemplo, normalmente o Windows não escalona processos mas sim threads

Algumas das operações mais usadas no âmbito das threads envolvem a criação de uma thread e a junção de threads (pthread_create e pthread_join). 

Voltando então a uma das perguntas principais: Porque sincronizar? 

Porque o acesso concorrente a dados e recursos partilhados pode criar uma situação de inconsistência desses mesmos recursos, isto porque as várias instâncias acedem e manipulam-nos de uma forma “simultânea”, dando azo a situações de inconsistência e de falha. Então para que uma rotina ou programa seja consistente são precisos mecanismos que assegurem a execução ordenada e correta dos processos cooperantes.

Um dos mecanismos computacionais que podemos usar para que não haja inconsistência de recursos são os semáforos. Um semáforo é uma variável, um mecanismo de sincronização sem espera ativa. Esta variável pode ser manipulada através de duas primitivas atómicas, isto é, que não podem ser interrompidas por processos.

A sua função é controlar o acesso a recursos partilhados num ambiente multitarefa. A invenção desse tipo de variável é atribuída a Edsger Dijkstra.

Quando declaramos um semáforo, o seu valor indica quantos processos (ou threads) podem ter acesso ao recurso partilhado. Assim, para partilhar um recurso o leitor deve verificar qual o valor do semáforo para saber qual a ação a executar.

Assim, e de forma a consolidar os conhecimentos, as principais operações sobre semáforos são:

Inicialização
Recebe como parâmetro um valor inteiro indicando a quantidade de processos que podem aceder a um determinado recurso.
Operação wait
Decrementa o valor do semáforo. Se o semáforo está com valor zero, o processo é posto em espera. Para receber um sinal, um processo executa o wait e bloqueia se o semáforo impedir a continuação da sua execução.
Operação signal
Se o semáforo estiver com o valor zero e existir algum processo em espera, um processo será acordado. Caso contrário, o valor do semáforo é incrementado. Para enviar um sinal, um processo executa um signal.

As operações de incrementar e decrementar devem ser operações atômicas, ou indivisíveis, isto é, a instrução deve ser executada na totalidade sem que haja interrupções. Enquanto um processo estiver a executar uma dessas duas operações, nenhum outro processo pode executar outra operação nesse mesmo semáforo, devendo esperar que o primeiro processo encerre a sua operação. Essa obrigação evita condições de disputa entre as várias threads.

Para evitar espera, o que desperdiça processamento da máquina, a operação wait utiliza uma estrutura de dados (geralmente uma FIFO). Quando um processo executa essa operação e o semáforo tem o seu valor a zero, este valor é posto na estrutura. Quando um outro processo executar a operação signal havendo processos nessa mesma estrutura, uma delas é retirada (no caso FIFO, é retirada a primeira que entrou).

Tendo em conta que há necessidade de garantir a consistência dos recursos, a utilização mais simples do semáforo é em situações na qual se utiliza o princípio da exclusão mútua, isto é, que só um processo é executado de cada vez. Para isso utiliza-se um semáforo binário, com inicialização em 1. Esse semáforo binário atua como um mutex.

O princípio da exclusão mútua ou mutex, é uma técnica usada em programação concorrente para evitar que dois processos ou threads tenham acesso simultaneamente a um recurso partilhado. Esta partilha dá origem à chamada secção crítica que pode ser protegida da seguinte forma: 

pthread_mutex_lock()
[secção critica]
pthread_mutex_unlock()

Então, um meio simples para exclusão mútua é a utilização do tal semáforo binário, isto é, que só pode assumir dois valores distintos, 0 e 1. O fecho do semáforo deve ser feito antes de utilizar o recurso e deve ser libertado só depois do uso o recurso. Tendo em conta que apenas um processo pode entrar de cada vez na secção crítica, então os outros processos devem esperar pela sua vez.

Contudo o uso do princípio da exclusão mútua, pode originar alguns problemas, como por exemplo deadlocks ou starvation (inanição).

Um deadlock, ou bloqueio, é referente a uma situação em que existe um impasse entre dois ou mais processos, isto é, no nosso contexto, quando dois ou mais processos tentam aceder ao mesmo recurso, bloqueiam-se mutuamente impedindo a boa continuação do algoritmo.

Ocorre quando várias threads do conjunto estão à espera da libertação de um recurso por uma outra thread que, por sua vez, aguarda a libertação de outro recurso alocado ou dependente da primeira thread.

A starvation por seu lado, ocorre quando uma thread nunca é executada por estar à espera de uma resposta que uma outra thread supostamente lhe dará, contudo esta última thread por algum motivo (a thread pode morrer ou ficar bloqueada) nunca lhe dá a resposta esperada. Diz-se que neste caso a thread se torna um zombie, esperando uma resposta que possivelmente nunca terá.

Quando o escalonamento não é feito adequadamente, pode haver inanição. Uma solução para esta situação é a existência de um tempo máximo de espera.

A ocorrência da inanição dá-se também quando os programas entram em ciclo infinito (razão pela qual também se dá o nome de preterição indefinida a esta situação) e não fazem nenhum progresso no processamento, ao contrário do deadlock, que ocorre quando os processos permanecem bloqueados, dependendo da liberação dos recursos por eles alocados.

Após esta pequena explicação teórica, vamos caro leitor voltar ao algoritmo escolhido para fonte central deste artigo, o jantar dos filósofos. Este é considerado um problema clássico de programação concorrente, criado em 1965 por Edsger Dijkstra e tem como objetivo principal demonstrar a alocação de recursos quando temos processos que concorrem pela alocação dos mesmos, ou seja, os recursos disponíveis são escassos. Neste problema há a necessidade de reservar recursos entre vários processos sem deadlock ou starvation.

Publicado na edição 39 (PDF) da Revista PROGRAMAR.