Programação Concorrente

1. Uma breve introdução aos processos

2. Mecanismos de exclusão mútua

3. Mecanismos de sincronismo

4. Tratamento de deadlocks

Os tópicos a serem examinados podem ser encontrados nos seguintes capítulos de livros:

1. Modern Operating Systems, Tanenbaum, cap. 2 e 6

2. Operating Systems Concepts, Peterson/Silberschatz, cap. 5 e 6

3. Outros bons livros de sistemas operacionais, nos capítulos sobre processos ou concorrência

0. Preâmbulo

A compreensão correta do que são processos, do que eles representam e como são tratados por um sistema computacional pode ser melhor entendida a partir da compreensão da evolução de sistemas operacionais. Esse tópico será muito rapidamente visto em sala de aula, desde as máquinas que não tinham SO até os vários modelos de SO existentes atualmente, mas aconselha-se que esse tema seja melhor visto em algum dos livros apontados como referência.

1. Processos

Existe uma grande discussão quanto a definição exata de processos. A definição que adotaremos aqui é a de que processos nada mais são do que programas em execução, isto é, um programa passa a ser denominado processo quando é carregado para execução. Neste momento diversos eventos ocorrem, dentre os quais o principal é definir a identificação desse processo durante a sua execução.

A execução coletiva de processos pode ser classificada como sequencial, quando a execução de cada processo for estritamente sequencial, ou concorrente, quando a execução de dois ou mais processos puder ser feita de modo simultâneo, compartilhando ou não recursos do sistema.

As interações entre execuções de diversos processos podem ser representadas por grafos de processos (que identificam quais processos ativam outros processos) e por grafos de precedência (que identificam quais processos devem ser concluídos antes do início de um dado processo). O entendimento correto de como tais grafos determinam os processos é de grande importância para a compreensão do processo de concorrência.

2. Exclusão mútua

A execução de dois ou mais processos concorrentes pode ser feita com ou sem interação entre eles. Quando não existe interação o tratamento dos mesmos é bastante simples. Já quando existe interação entre os processos é preciso tomar cuidado com vários detalhes. Um deles é a obtenção de exclusão mútua, que é necessária quando dois ou mais processos têm que acessar um dado recurso que não pode ser compartilhado. Essa situação pode levar a erros de execução, que podem ser evitados através de mecanismos como desabilitação de interrupções, soluções de software com espera ocupada (Dekker, Peterson, etc.) ou ainda por primitivas sem espera ocupada (semáforos, block e wake-up, monitores, troca de mensagens, etc.).

3. Sincronismo

Um segundo problema no tratamento da interação entre processos é a necessidade de sincronismo entre eles, em determinadas situações. Esse problema é tipico em situações em que um processo produz informação a ser consumida por outro processo. Nesse caso o primeiro não pode produzir uma informação nova antes que a anterior seja consumida e o segundo processo não pode consumir nada que ainda não tenha sido produzido. Soluções para este problema podem ser obtidas com o uso das mesmas primitivas sem espera ocupada listadas acima.

4. Deadlocks

Um último, e bastante grave, problema no tratamento de processos concorrentes é a obtenção de processos livres de deadlock. Deadlocks ocorrem quando dois processos se travam na disputa por dois recursos, de tal forma que um dos processos possui o recurso A e espera pelo recurso B, enquanto o outro possui o recurso B e espera pelo A. Nessa situação se torna impossível que um deles (P1 por exemplo) avance, uma vez que para isso é preciso que o outro (P2) libere o recurso que possui, o que apenas é feito se ele (P2) obtiver o outro recurso (de posse de P1) para avançar. Isso caracteriza o que chamamos de espera circular e pode ser tratada evitando que pelo menos uma das condições necessárias para deadlock ocorra. O tratamento de deadlocks é realizado através de métodos como do avestruz, time-stamp, banqueiro ou da padaria.

Problemas semelhantes são o de starvation, quando um processo espera indefinidamente por algum recurso, e o de livelock, que é parecido com deadlock porém sem o bloqueio definitivo dos processos. O problema de starvation, em particular, é de grande interesse na análise de eficiência dos vários mecanismos de gerenciamento do SO, quando se procura identificar a possibilidade ou não de sua ocorrência.