Processos concorrentes

Em um sistema multiprogramado:
     - processos são concorrentes: vários processos são (virtualmente) executados ao mesmo tempo;
     - processos são assíncronos: executam independentemente;
     - processos compartilham recursos.

Especificação da concorrência em programas

Hierarquia de processos: um grafo de processo é uma árvore cujos nodos correspondem a um processo.
     - uma aresta de um nodo Pi para um nodo Pj significa que Pj foi criado por Pi (Pi é o pai de Pj e Pj é o filho de Pi);
     - cada processo possui um pai, exceto o inicial, cujo pai é ele mesmo;
     - cada processo pai pode ter vários filhos.

A especificação da concorrência em programas pode ser expressa em diversas notações. As mais utilizadas são os comandos FORK e JOIN, e os comandos PARBEGIN e PAREND.

FORK e JOIN

O processo pai executa concorrentemente com o processo filho.

O programa A começa a ser processado e, ao encontrar o comando FORK, cria outro processo (ou subprocesso, ou filho) para a execução do programa B. O comando JOIN determina o ponto onde A sincroniza com B, isto é, o programa A só prossegue, a partir do comando JOIN, quando B terminar.

PARBEGIN e PAREND

O processo pai espera que o processo filho termine.

Os subprocessos contidos após o comando PARBEGIN serão executados concorrentemente, numa ordem imprevisível. O ponto de sincronização é definido pelo comando PAREND, sendo que os comandos a partir dele somente serão executados quando todos os outros já tiverem terminado. Devido à sua facilidade de compreensão e simplicidade, podem ser facilmente adicionados em uma linguagem de alto nível.

Problemas de comunicação entre processos

Em um ambiente com processos concorrentes assíncronos que compartilham recursos, um processo pode afetar ou ser afetado por outro processo.

Exemplo: Spooler de impressão.

P2 afeta o acesso de P1 ao recurso compartilhado. Isto acontece devido ao assincronismo entre P1 e P2.

A necessidade de confiabilidade dos sistemas multiprogramáveis torna extremamente importante a existência de mecanismos que garantam a comunicação entre processos concorrentes e o acesso aos recursos compartilhados, os quais são denominados mecanismos de sincronização entre processos.

O problema do produtor-consumidor representa um tipo de interação comum entre processos concorrentes assíncronos.

Os programas exemplificados a seguir representam a concorrência entre um processo de gravação e um de leitura em um buffer.

A variável contador guarda o número de dados contidos no buffer, ao passo que a variável n determina a capacidade do buffer. A implementação é de uma fila (FIFO), onde novo aponta para o fim da fila e prox para o início. Ao serem compilados os comandos contador++ e contador-- geram as sequências de instruções:

O exemplo a seguir ilustra uma possível execução, cujo resultado não é o esperado. Partindo do princípio que contador = 5 (armazenado em #end), após a execução das duas instruções, o contador deveria permanecer com o valor 5.

Porém, ele indica 4, o que não corresponde a realidade.

Exclusão mútua e seções críticas

A solução para evitar estes problemas de comunicação consiste em impedir que dois ou mais processos tenham acesso a variáveis de memória ao mesmo tempo. Quando um processo estiver acessando uma variável compartilhada, todos os outros que necessitarem dessa mesma variável devem esperar que o primeiro termine o acesso. É este o conceito de exclusão mútua, ou acesso mutuamente exclusivo.

O trecho de programa onde são realizados acessos às variáveis de memória compartilhadas é denominado seção crítica (ou região crítica).

No problema produtor-consumidor:

Para assegurar a exclusão mútua, dois ou mais processos não podem executar simultaneamente seções críticas que acessem as mesmas variáveis compartilhadas.

Toda a vez que o processo for executar sua seção crítica, ele deve executar um protocolo de entrada na seção crítica. Do mesmo modo, ao sair, o processo deverá executar um protocolo de saída da seção crítica.

     BEGIN
          .
          Entra_Seção_Crítica();
          Seção_Crítica;
          Sai_Seção_Crítica();
          .
     END

Estes mecanismos que permitem execução mutuamente exclusiva, devem ser providos pelo Sistema Operacional.

Soluções de hardware para o problema da exclusão mútua

Desabilitação de interrupções

A inibição das interrupções na entrada da seção crítica e a sua ativação na saída da seção crítica é a solução mais simples para a exclusão mútua. Como a mudança de contexto só ocorre através de interrupções, o processo que as desabilitou terá acesso exclusivo garantido.

Cabe notar que funcionamento do sistema pode ser seriamente comprometido caso o processo que desabilitou as interrupções não torne a habilitá-las.

Porém, esta solução só é válida em sistemas monoprocessáveis. Em sistemas multiprocessáveis, dois ou mais processadores podem estar executando processos distintos que queiram executar a mesma seção crítica.

Espera ocupada (instrução Test-And-Set)

Para suportar exclusão mútua, algumas arquiteturas de processador fornecem a instrução TAS (Test And Set).

A instrução TAS:

     · lê uma trava de memória (lock) e atualiza o valor do registrador (R1);
     · escreve a trava de memória (lock) com o conteúdo de um registrador (R1);
     · a leitura e a escrita são realizadas atomicamente, em um único ciclo de barramento (ciclo read-modify-write), ou seja, as instruções executam sem interrupção (indivisíveis).

A implementação da exclusão mútua entre produtor e consumidor com a instrução TAS:

     - enter() testa a variável lock
          se lock = 1 a entrada na seção crítica é permitida
          se lock = 0, espera até que lock = 1

Esta solução é denominada espera ocupada (busy wait) porque realiza uma má utilização de tempo do processador, pois o processo em enter() o mantém desnecessariamente.

Soluções de software para o problema da exclusão mútua

A exclusão mútua soluciona os problemas de comunicação, porém os problemas de sincronização também devem ser atendidos, através dos seguintes fatores:

     - o número de processadores e o tempo de execução dos processos concorrentes devem ser irrelevantes;
     - um processo, fora de sua seção crítica não pode impedir que outros processos entrem em suas próprias seções críticas;
     - um processo não pode permanecer indefinidamente esperando para entrar em sua seção crítica (starvation).

Semáforos

São variáveis especiais usadas para assegurar exclusão mútua, as quais ficam associadas aos recursos compartilhados, indicando quando eles estão sendo acessados por um dos processos concorrentes.

Um semáforo S é uma variável inteira acessada apenas através de duas operações, P(S) (ou wait(S), ou UP(S)) e V(S) (ou signal(S) ou DOWN(S)), que permitem a entrada e saída da seção crítica respectivamente. Essas operações são atômicas em sua totalidade.

Usando semáforos no problema produtor-consumidor:

Inicialmente S = 1

Os semáforos podem ser de dois tipos:

     - semáforos binários: assumem apenas os valores 0 e 1, sendo usados apenas para assegurar exclusão mútua.
     - semáforos contadores: usados para controlar a alocação de recursos.

Os semáforos contadores podem ser utilizado para a implementação da sincronização condicional. Uma vez que, se existe um processo que deve ser notificado sobre a ocorrência de um evento e outro capaz de detectar essa ocorrência, podemos utilizar um semáforo associado ao evento esperado para sincronizar ambos os processos.

Semáforos contadores no problema produtor-consumidor:
     - S, disponíveis e ocupados são variáveis do tipo semáforo

Considerando n (tamanho do buffer) igual à 2, e que o Consumidor é o primeiro a ser executado, vejamos a simulação. Como o buffer está vazio (ocupados = 0), o processo consumidor fica bloqueado.

Após o processo Produtor armazenar o dado no buffer e executar o V(ocupados), o processo Consumidor é liberado pois está apto para ler o dado do buffer.

Inicialmente: S = 1, disponíveis = n, ocupados = 0

Implementação da comunicação entre processos com o uso da notação PARBEGIN/PAREND e da sincronização de processos com semáforos a partir de um grafo:

Monitores

A programação com semáforos é propensa a erros, pois deve ser mantida uma correspondência, na ordem correta, entre as operações P e V nos processos que compartilham um recurso.

Os monitores são oferecidos por certas linguagens de programação e permitem uma melhor estruturação das seções críticas de um programa, tornando mais fácil o desenvolvimento e a correção de programas concorrentes.

Um monitor consiste de um módulo contendo: rotinas, estruturas de dados e variáveis de condição. Sua estrutura típica é mostrada na figura a seguir.

A cada instante, apenas um processo pode estar executando uma rotina do monitor, implementando, automaticamente, a exclusão mútua entre seus procedimentos. Cabe notar que o monitor permite a execução de um procedimento seu, mesmo que um ou mais processos estejam no estado de espera.

     PROGRAM Exemplo;
          MONITOR Região_Crítica;
               VAR X : INTEGER;
               PROCEDURE Soma; BEGIN
                    X := X + 1;
               END;
               PROCEDURE Diminui; BEGIN
                    X := X - 1;
               END;
          BEGIN
               X := 0;
          END;
     BEGIN
          PARBEGIN
               Região_Crítica.Soma;
               Região_Crítica.Diminui;
          PAREND;
     END.

O monitor encapsula as seções críticas (em forma de procedimentos) do programa, portanto:

     - não é necessário controlar a exclusão mútua em cada ponto de acesso ao recurso compartilhado;
     - uso correto dos mecanismos de exclusão mútua (semáforos) a cargo do compilador.

As variáveis de condição são estruturas do tipo fila, onde os processos esperam por algum evento. Duas operações se realizam sobre as variáveis de condição:

     - wait(c): processo passa a esperar na fila da condição c, quando esta impede a continuação da execução;

     - signal(c): desperta o processo esperando na fila da condição c. A instrução signal deve ser a última do procedimento, de modo que o processo abandone imediatamente o procedimento.

O problema produtor-consumidor com monitores:

Problemas de sincronização entre processos

São problemas que surgem na implementação de soluções para os problemas de comunicação e devem ser resolvidos antes destes. Os mais comuns são:

     1. Velocidade de execução dos processos: surge quando o mecanismo de controle implementado desconsidera as instruções dos processos além da seção crítica. No exemplo abaixo, o processo B é bloqueado pelo processo A, mesmo este estando fora de sua seção crítica.

          PROGRAM Velocidades;
               VAR Vez : CHAR;
               PROCEDURE Processo_A; BEGIN
                    REPEAT
                         WHILE (Vez =´B´) DO

                              (* Não faz nada *);
                         Seção_Crítica_A;
                         Vez := ´B´;
                         Processamento_Longo;
                    UNTIL False;
               END;
               PROCEDURE Processo_B; BEGIN
                    REPEAT
                         WHILE (Vez =´A´) DO

                              (* Não faz nada *);
                         Seção_Crítica_B;
                         Vez := ´A´;
                    UNTIL False;
               END;
          BEGIN
               Vez := ´A´;
               PARBEGIN
                    Processo_A;
                    Processo_B;
               PAREND;
          END.

     2. Starvation ou indefinitely postponed (postergação indefinida): ocorre quando dois ou mais processos esperam por um recurso alocado. Na decisão de qual processo ganhará o acesso ao recurso compartilhado, se o Sistema Operacional o fizer de modo aleatório ou através de prioridades, pode ser que um processo nunca seja escolhido. Para resolver este problema utiliza-se um mecanismo de fila, onde o primeiro a chegar é o primeiro a ser atendido (FIFO). 

     3.Sincronização condicional: ocorre quando o recurso não se encontra pronto para ser utilizado, devendo o processo permanecer no estado de espera. Surge em operações onde existam processos gerando informações (produtores) utilizadas por outros processos (consumidores). Como no exemplo do buffer, os processos devem estar sincronizados de forma que um processo não tente gravar dados em um buffer cheio ou ler de um buffer vazio.