Exclusão múltipla

Pesquisa sobre exclusão mútua

Introdução

Nesta pesquisa, relacionamos uma série de tópicos que tratam das soluções possíveis para a exclusão mútua, que é originada a partir de um problema chamado “condição de disputa”, existente em sistemas multiprogramados modernos, que executam vários processos paralelamente, e estes concorrem sempre pelo uso da CPU.

Vamos entender o que é uma condição de disputa, e quando ocorre.

Quando 2 processos, que executam paralelamente, necessitam acessar um mesmo recurso do sistema operacional ao mesmo tempo, é necessário que se faça um gerenciamento para que esses 2 processos não entrem em conflito na tentativa de utilização do recurso, causando a condição de disputa, podendo resultar em uma falha de sistema e mal funcionamento no software do qual o processo faz parte.

Visando a solução deste problema, foi criado um procedimento que tem por objetivo identificar a seção crítica de um processo, que é parte do programa que acessa os recursos compartilhados do sistema operacional. Através deste procedimento, é implementada a regra de que dois ou mais processos nunca podem entrar em sua zona crítica ao mesmo tempo, evitando assim, que acessem ao mesmo tempo recursos compartilhados do SO. A partir desta necessidade, é criado o conceito de exclusão mútua.

Examinaremos várias propostas para obter exclusão mútua, de modo que enquanto um processo esta ocupado executando em sua região critica nenhum outro processo entrara em sua região critica e assim, evitando problemas.

Desabilitando Interrupções

A solução mais simples e fazer cada processo desativar todas as interrupções imediatamente depois de ele entrar em sua região crítica e reativá-las imediatamente depois de ele sair dela. Com as interrupções desabilitadas, não pode ocorrer qualquer interrupção de relógio. A CPU só alterna de um processo para outro como resultado de interrupções de relógio ou de outras interrupções, no final das contas, com as interrupções desligadas a CPU não alternara de um processo para outro. Assim, uma vez que tenha desabilitado as interrupções, um processo pode verificar e atualizar a memória compartilhada sem temer a intervenção de um outro processo.

Essa abordagem é geralmente pouco atraente porque não é aconselhável dar o poder de desativar interrupções a processo de usuário. Suponha que um deles tenha feito isso e nunca mais as tenha ligado. Isso poderia ser o fim do sistema. Além disso, se o sistema e multiprocessador (com duas ou mais CPUs), desabilitar as interrupções afetara somente a CPU que executou a instrução desabilitar. As outras continuarão executando e podem acessar a memória compartilhada. Por outro lado, frequentemente e conveniente para o próprio kernel desativar interrupções pelo tempo de algumas instruções enquanto ele está atualizando variáveis ou listas. Se uma interrupção ocorreu enquanto a lista de processos prontos, por exemplo, estava em um estado inconsistente, poderiam ocorrer condições de corrida.

A conclusão é: desativar interrupções é frequentemente uma técnica útil dentro do sistema operacional em si, mas não e apropriada como um mecanismo geral de exclusão mutua para processos de usuário.

A possibilidade de realizar exclusão mutua desabilitando interrupções, mesmo dentro do núcleo, está se tornando menor a cada dia em virtude do número crescente de chips multinúcleo até em PCs populares. Dois núcleos já são comuns, quatro estão presentes em maquinas sofisticadas e 8 ou 16 virão em breve. Em um sistema multicore (multiprocessador), desabilitar as interrupções de uma CPU não impede que outras CPUs interfiram nas operações que a primeira CPU está executando. Consequentemente, esquemas mais sofisticados são necessários.

Variáveis de impedimento

Como uma segunda tentativa, busquemos uma solução de software. Considere que haja uma única variável compartilhada (trava), inicialmente contendo o valor 0. Para entrar em sua região crítica, um processo testa antes se há trava. Se a trava for 0, o processo altera essa variável para 1 e então na região critica. Se a trava já estiver com o valor 1, o processo simplesmente aguardara até que ela se torne 0. Assim, um 0 significa que nenhum processo está em sua região crítica e um 1 indica que algum processo está em sua região crítica.

Infelizmente, essa ideia apresenta exatamente a mesma falha que vimos no diretório de spool. Suponha que um processo leia a variável trava e veja que ela e 0. Antes que possa alterar a variável trava para 1, outro processo e escalonado, executa e altera a variável trava para 1. Ao executar novamente, o primeiro processo também colocara 1 na variável trava e, assim, os dois processos estarão em regiões críticas ao mesmo tempo.

Alternância obrigatória

A solução de alternância obrigatória, tem como objetivo resolver o problema de condições de disputa que o conceito de seção crítica não consegue, por si só, resolver e aplicar de forma mais eficiente a exclusão múltipla.

O funcionamento desta solução é relativamente simples. Uma varável de controle turn é usada como indicador para instruir se o processo (1) pode ou não entrar em sua zona crítica. Caso o valor desta variável seja 0, o processo 1 é liberado para entrar em sua zona crítica, a partir deste momento, um segundo processo (2) verificar também o valor da variável, que contínua como 0, até que o processo 1 saia de sua zona crítica, alterando o valor desta variável para 1, e a partir deste momento o processo 2 pode entrar em sua zona crítica.

Uma grande desvantagem desta solução pode ser encontrada no exemplo dado acima. Enquanto o segundo processo aguarda para poder entrar na zona crítica, ele fica em uma espera ociosa, que não é aceitável se o tempo o tempo de espera não for breve, o que, se confirmado, causa uma indesejável perda de tempo da CPU.

Outra desvantagem desta solução, é que ela não garante que não haverá uma parada de sistema, causada por erro de alternância, assim não cumprindo um dos papéis fundamentais que a solução deve cumprir, que é garantir que nenhum processo em execução fora da sua seção crítica bloqueie outros processos.

Solução de Peterson

Outra solução possível para o a exclusão mútua, é a solução de Peterson.

Esta solução foi desenvolvida pelo matemático G.L. Peterson no ano