Condição de Corrida

Os sistemas operacionais sempre estão processando, assim é compartilhado memória ou arquivos em que um ou mais processos podem ler ou escrever no mesmo.

Segundo Tanenbaun (2010, p. 82) define condição de corrida como:

“Situação em que dois ou mais processos lêem e escrevem dados compartilhados e o resultado final depende da ordem de quem precisamente executa, e quando.”

Com essa definição podemos imaginar um spool de impressão, quando um processo quer imprimir um arquivo, o mesmo coloca o arquivo no diretório de impressão, se existir um arquivo já alocado, é impresso e outro arquivo é colocado.

Mas para nós entender o que a condição de corrida tem a ver com o spool de impressão, imaginamos o spool como uma fila, como mostrado na figura abaixo:

Imagem 1: Spool de Impressão.

Dentro dessa fila de impressora temos duas variáveis o IN (Apontador do próximo local livre da fila) e OUT (Apontador para o próximo arquivo a ser impresso), assim o valor 4 como esta na imagem acima esta sendo nosso OUT que será arquivo impresso e o IN para 7 que o próximo local livre na fila.  Sendo assim possuímos dois processos A e B, o primeiro a ser processado é o A, o mesmo lê a variável IN, mas antes de colocar um arquivo dentro da variável, o processador recebe uma interrupção e para o processo A, e começa a processar o processo B, o mesmo faz a mesmo caminho do processo A, lê a variável IN e nesse momento coloca um arquivo na variável, mas seu tempo de processamento acaba, e o processo A começa a processar novamente onde parou sendo assim coloca outro valor no IN.

Sendo assim chegamos à conclusão o processo B nunca vai ter seu arquivo impresso, pois o processo A colocou um valor em cima do B, e o spool não vai perceber essa situação de modificação de valores e vai continuar fazendo sua execução e imprimindo.

Então a condição de corrida depende da ordem e precisando que cada processo é executado.

Seção Crítica

Seção critica se refere a uma segmentação de um código, em que variáveis são alteradas onde seus valores são atualizados em uma tabela, e também gravados em alguma parte do arquivo, a função essencial da seção critica é evitar as condições de corrida, que podem ser evitadas se for possível impedir que dois processos entrem eu suas seções criticas ao mesmo tempo. Uma parte essencial em um sistema consiste em que apenas um programa pode realizar uma seção critica por vez, nunca mais de um programa. Para a seção critica do processo ser iniciada é necessário que esse processo ganhe a permissão para isso, esse pedido é feito através da seção de entrada, que é uma implementação que realiza esse pedido. A seção critica será encerrada com uma seção de saída. Seguindo quatro passos essenciais o problema da seção critica pode ser resolvido, Esses passos são:

1 – Nenhum dos dois processos pode estar simultaneamente dentro de suas regiões criticas.

2 – Nenhuma suposição pode ser feita sobre as velocidades ou sobre o numero de CPU’s.

3 – Nenhum processo que executa fora de sua seção critica pode bloquear outro processo.

4 – Nenhum processo deve ter de esperar eternamente para entrar em sua região critica.

 Tanembaum. Livro de Sistemas Operacionais

Soluções Existentes

A exclusão mutua, a sua principal função é proibir que mais de um processo faça a leitura de algum dado ou informação ao mesmo tempo, através da exclusão mutua será garantindo que apenas o processo que esta fazendo a leitura de qualquer dado tenha a prioridade absoluta para fazer, sem que outro processo tente fazer o mesmo.

Desativando Interrupções

Uma das maneiras de realizar a exclusão mutua é desativando as interrupções nos processos. Sendo assim, cada processo desativara suas interrupções antes que entre na seção critica, e quando sair da sua seção critica ira ativar novamente as interrupções. Essa é uma alternativa para que o processo possa fazer todas as suas leituras de dados e informações, sem que algum outro processo interfira. Um problema nessa abordagem pode ocorrer caso o processo que desativou suas interrupções não as ative novamente, assim o sistema ficaria preso a esse processo.  
           

Variáveis de bloqueio

Outra forma de realizar a exclusão mutua é através de uma variável de bloqueio, para isso utilizando a variável que fara o bloqueio e uma variável para liberar o bloqueio, a variável for 0 esta livre para fazer o bloqueio, se for 1 o processo precisa aguardar para entrar na seção critica. Um problema que seria recorrente nesse método, seria o risco de dois processos diferentes entrarem um sua seção critica juntos, com ambos definindo a variável de bloqueio 1 ao mesmo tempo.

Alternância Estrita

O método da alternância estrita faz através de um programa utilizando uma variável inteira que realiza uma checagem para ver qual processo devera entrar eu sua seção critica, em um determinado espaço de tempo será feito uma consulta a essa variável inteira para descobrir se o outro processo que esta em sua seção critica já saiu. Esse teste realizado na variável será feito até que o processo saia da seção critica, o que é chamado de espera ativa. Um dos problemas nessa utilização se um dos processos for muito mais lento que o outro, porque quando esse processo mais rápido estiver em sua seção critica, ele ira sair mais rápido que o outro processo saiu e assim ambos os processos ficaram em na sua seção não critica. Isso causaria um problema em que um processo que esta fora de sua seção critica estaria bloqueando um processo que esta tentando entrar em sua seção critica.

A solução de Peterson

A solução de Peterson combinava o uso de algumas operações diferentes uma que será chamada antes do processo entrar em sua região critica, essa operação fara com que o processo aguarde ate que esteja apto para entrar em sua seção critica. Quando esse processo terminar de fazer a sua sessão critica ele chamara por outra operação que indicara que ele já terminou seu ciclo na seção critica e deseja sair, abrindo espaço para que outro processo possa entrar em sua seção critica. Se dois processos solicitarem quase ao mesmo tempo a operação de entrada para a seção critica, sempre o que chamou primeiro essa operação é que entrara na seção critica.

Instrução TSL

O método da instrução TSL que funciona com auxilio do hardware da maquina, sendo usado em maquinas com vários processadores, para utilizar esse método é necessário que seja criada uma variável de bloqueio, para que apenas um dos processadores tenha acesso a memoria bloqueando a entrada de outros processadores. Quando um processo for entrar em sua seção critica ele precisara configurar a variável de bloqueio como 1. Para evitar que mais de um processo entre simultaneamente em sua seção é criada uma instrução que armazena o valor antigo da variável de bloqueio, então quando um processo for tentar entrar em sua seção critica ele primeiro ira checar esse valor antigo, caso seja diferente de zero significa que algum outro processo já definiu um bloqueio, então ele ira consultar esse valor antigo depois de um tempo para ver se ele já se alterou para 0. Quando for 0, ele então ira alterar a variável de bloqueio, ira chamar a operação de entrada da seção critica e depois que terminar chamara a operação de saída da seção critica e em seguida mudara o valor do bloqueio possibilitando assim que outro processo possa entrar na seção critica.

Tanembaum. Livro de Sistemas Operacionais

Inanição

Sendo buscadas várias soluções para sincronização de processos, alguns desafios foram encontrados, como a inanição.

A Inanição é quando um processo nunca é executado, como por exemplo, no escalonamento por prioridade, os processos com prioridade maior vão sempre ser executados, e quando um processo acaba outro entra com maior prioridade, sendo assim os processos com menor prioridade não vão ter nenhum progresso na execução de sua tarefa.

Definição de Deadlock

Deadlock ocorre quando um conjunto de processos ou um único processo está aguardando um outro conjunto de processos ou um único processo desocupar os recursos dos quais o processo precisa, ou seja, um processo solicita recursos se os mesmos estiverem ocupados ele entra em espera, se ele não conseguir mudar de estado pois os recursos que ele solicitou estão ocupados então essa situação fica caracterizada como deadlock.

Todas informações sobre deadlock são do livro de Silberschatz, Abraham - Fundamentos de Sistemas Operacionais.

Características de Deadlock

Em deadlock os processos nunca terminam a sua execução e os recursos disponíveis ficam ocupados, impedindo assim que outros processos possam ser executados.

A seguir é abordado sobre as quatro condições necessárias que devem ocorrer simultaneamente para caracterizar uma situação de deadlock em um sistema, somente existirá um deadlock se as quatro condições forem estabelecidas, pois uma é dependente da outra:

1. Exclusão mútua. Ao menos um recurso do sistema não poderá ser compartilhado entre os processos, este recuso pode atender a somente um processo de cada vez. Se outro processo estiver precisando desse recurso o mesmo deve esperar até que o recurso seja liberado.
2. Posse e espera. Um processo deve estar ocupando pelo menos um recurso do sistema, e esperando para adquirir outros recursos de sua necessidade, e os recursos que esse processo está esperando para adquirir deve estar ocupado por outros processos.
3. Inexistência de preempção. Os recursos não podem ser interrompidos, um recurso so pode ser liberado após ter sido desocupado pelo processo que o ocupava, assim o processo que estava em espera pode assumir o recurso.
4. Espera circular. Deve existir um conjunto de processos de modo que os mesmos sigam uma ordem, ou seja, o processo de ordem 0 deve esperar o recurso que está sendo ocupado pelo processo de ordem 1, o processo de ordem 1 deve esperar o recurso que está sendo ocupado pelo processo de ordem 2 e assim sucessivamente em todo o conjunto.

Métodos para Manipulação de Deadlocks

Existem três maneiras das quais podemos lidar com o problema do deadlock:

• Pode ser usado um protocolo para prevenir as ocorrências de deadlock, garantindo que o sistema nunca se encontre em estado de deadlock.
• A ocorrência de deadlock pode ser permita através do sistema, mas assim que o mesmo detecta-la deve ser executada uma recuperação.
• Existe também a possibilidade de fingir que o sistema está livre de deadlocks e que nunca terá problemas com isso.

     A terceira solução é usada na maioria dos sistemas operacionais, em casos como esse é responsabilidade do desenvolvedor de aplicações escrever programas que manipulem deadlocks.

Para impedir a ocorrencia de deadlocks um sistema pode utilizar um esquema de prevenção, o mesmo fornece um conjunto de métodos para garantir que pelos menos uma das quatro condições necessárias para haver um deadlock não seja satisfeita. Esses métodos restringem as formas pelas quais a solicitação de recursos é feita.

   O impedimento de deadlocks requer que o sistema operacional receba informações antecipadamente, a que recursos um processo solicitará e usará durante seu tempo de vida. Através desse recurso adicional, o sistema operacional pode decidir se para determinada solicitação o processo deve esperar ou não. Para definir se uma solicitação de um recurso pode entrar em espera ou não o sistema deve analisar os recursos disponíveis no momento, os recursos ocupados, e as futuras solicitações e liberação de processos.

Se um algoritmo de prevenção de deadlock ou de impedimento não for adicionado ao sistema, uma situação de deadlock pode ocorrer.

Na ausência de algoritmos de detecção e recuperação de deadlocks, o sistema não será capaz de detectar o que ocorreu, em um caso como esse um deadlock não detectado resultará em diminuição do desempenho do sistema. Isso ocorre devido os recursos estarem sendo mantidos por processos que não podem ser executados, de modo que o sistema irá parar de funcionar até que seja reiniciado manualmente.

Mesmo que esse método não esteja associado a uma abordagem viável ao problema de deadlock, ele é usado na maioria dos sistemas operacionais. Esse método é mais barato do que os de prevenção, impedimento ou detecção e recuperação que devem ser usados constantemente. Como os deadlocks em um sistema não são frequentes, um sistema pode entrar em estado de paralisação sem que esteja em estado de deadlock.

Prevenção de Deadlock

Para que um deadlock ocorra é necessário que as quatro condições que caracterizam um deadlock sejam estabelecidas. Assegurando que pelo menos uma dessas condições não se estabeleça, podemos nos prevenir contra a ocorrência de deadlocks. A seguir vamos analisar as quatro condições detalhadamente.

1. Exclusão Mútua. Deve estar presente em recursos não compartilháveis, a exemplo disso uma impressora não pode ser compartilhada simultaneamente por vários processos. Mas os recursos compartilhados necessariamente não precisam ser acessados ao mesmo tempo para ser considerado um recurso compartilhado. Porém a prevenção contra deadlock não pode ser feita através da negação da exclusão mútua, pois alguns recursos não podem ser compartilhados.
2. Posse e espera. Para que essa condição não seja satisfeita, devemos garantir que sempre que um processo solicitar um recurso, ele não esteja em posse de nenhum outro recurso.Um protocolo que pode ser usado requer que os processos solicitem e recebam todos os seus recursos antes de começar a ser executado pelo sistema. Outro protocolo permite que um processo solicite recursos apenas quando ele não tem qualquer recurso. Um processo pode solicitar alguns recursos e usá-los. Nessa condição quando ele estiver em posse dos recursos é necessário que ele libere-os para solicitar os novos. Esses dois recursos apresentam duas grandes desvantagens, a utilização dos recursos pode ser baixa, já que podem ficar muito tempo sem serem utilizados e é possível que haja inanição, já que um processo pode solicitar um recurso que seja muito popular assim ele sempre estará alocado fazendo com que o processo que o solicitou fique esperando indefinidamente.
3. Inexistência de Preempção. Para garantir que essa condição não ocorra pode ser usado o protocolo que se um processo estiver em posse de alguns recursos e solicitar outros recursos que não possam ser alocados, então os recursos que o processo estiver ocupando devem ser liberados, ou seja o processo deve sofrer uma preempção. O processo será reiniciado quando os recursos que ele tinha estiverem liberados e os adicionais que ele havia solicitado também. Enquanto ele está esperando se algum outro processo solicitar os recursos que o mesmo está ocupando seus recursos podem ser interrompidos mas isso ocorre somente se outro processo solicitar os recursos. Esse protocolo pode ser aplicado facilmente quando os recursos cujo estado pode ser facilmente salvo e restaurado posteriormente como os registradores da CPU e espaço de memória.
4. Espera Circular. Uma maneira de garantir que essa condição nunca ocorra é impor uma ordenação absoluta a todos os tipos de recursos e requer que cada processo solicite recursos em uma ordem de enumeração crescente. E também se várias instancias do mesmo tipo de recurso forem necessárias, uma única solicitação deve ser emitida para todas elas.

Impedimento de Deadlocks

Os algoritmos de prevenção de deadlock previnem  a ocorrência de deadlocks restringindo como as solicitações são feitas. Essas restrições garantem que  pelos menos uma das condições necessárias para se estabelecer o deadlock não se cumpra. Os possíveis efeitos colaterais podem ser a baixa utilização de dispositivos e uma reduzida taxa de transferência no sistema.

Outro método para evitar deadlocks é demandar mais informações sobre os recursos que serão solicitados. Com esse conhecimento da sequência completa de solicitações pode se tomar a decisão se o processo deve ou não esperar. Para que o sistema faça isso ele precisa de um mapeamento completo para saber quais recursos estão sendo ocupados, se estiverem ocupados informar qual processo os ocupa e também quais recursos estão livres.

Existem vários algoritmos que tratam esse método, o modelo mais simples e útil requer que cada processo declare a quantidade máxima de recursos que ele pode ocupar de cada tipo. Com essa informação já é possível que através de um algoritmo possa se garantir que a condição de espera circular não se estabeleça impedindo assim que se estabeleça um deadlock. O estado da alocação de recursos é definido através da quantidade de recursos disponíveis e alocados pelas demandas máximas dos processos.

Estado de Segurança

Um estado é seguro quando o sistema pode alocar recursos, em alguma ordem e evitar deadlock. O sistema se encontra em segurança somente se existir uma sequência de segurança. Um estado inseguro é um estado de deadlock, mas nem todos os estados inseguros são deadlocks. Enquanto o estado for seguro o sistema pode evitar estados inseguros. Através do comportamento dos processos é controlado os estados inseguros. Um sistema pode passar de um estado seguro para um estado inseguro.

Através de algoritmos de impedimento de deadlocks é necessário garantir que o sistema sempre esteja em estado seguro. Sempre que um recurso for solicitado o sistema deve analisar e verificar se o processo deve esperar ou ocupar o recurso. A solicitação do processo só é atendida se a alocação deixa o sistema em estado seguro.Mas dessa forma a utilização de recursos pode ser baixa por causa das restrições, um processo pode ficar esperando muito tempo para receber um determinado recurso, isso não ocorreria em uma situação oposta.

Algoritmo do Grafo de Alocação de Recursos

O sistema deve ter alocação de recursos com apenas uma instância de cada tipo de recurso, através do mesmo todos os recursos devem ser solicitados a priori do sistema. Uma aresta de requisição indica que o processo Pi pode solicitar o recurso Rj em algum momento no futuro, quando o processo solicita o recurso essa aresta de requisição é convertida em uma aresta de solicitação. Antes de atender qualquer requisição verifica-se se ao inverter a aresta cria-se um ciclo, esse ciclo é considerado um estado inseguro assim o processo é interrompido temporariamente. Se não existir ciclo o estado é seguro então a solicitação pode ser atendida. 

Algoritmo do Banqueiro

Esse nome foi escolhido pois poderia ser usado em um sistema bancário para garantir que o banco nunca alocasse seu dinheiro disponível de tal modo que não pudesse mais satisfazer as necessidades de todos os seu clientes. 

Quando um novo processo entra no sistema ele deve declarar a quantidade máxima de instâncias de cada tipo de recurso de que ele pode precisar. Essa quantidade não pode exceder a capacidade máxima do sistema.   Quando um processo solicitar recursos o sistema fará a análise se ele estiver em estado seguro ele aloca os recursos para determinado processo caso contrário o processo deve esperar.

Várias estruturas de dados devem ser mantidas para implementar o algoritmo do banqueiro, um vetor de um determinado tamanho indica a quantidade de recursos disponíveis de cada tipo, uma matriz define a demanda máxima de cada processo, a alocação de cada tipo correntemente alocada a cada processo, e também a necessidade de recursos remanescentes a cada processo.

Detecção de Deadlocks

Se um sistema não empregar um algoritmo de prevenção ou de impedimento uma situação de deadlock pode ocorrer. Nesse ambiente o sistema pode fornecer: um algoritmo que examine o estado do sistema determinar se ocorreu deadlock, e um algoritmo de recuperação de deadlock.

Uma Única Instância de cada Tipo de Recurso

Se todos os recursos possuem apenas uma unica instância, podemos definir um algoritmo de detecção de deadlocks que usa uma variante do grafo de alocação de recursos, chamado grafo de espera. Para detectar deadlocks, o sistema precisa manter o grafo de espera e periodicidade, invocar um algoritmo que busque um ciclo no grafo, pois só existe deadlocks se o grafo de espera contiver um ciclo.

Várias Instâncias de um Tipo de Recurso

É semelhante ao algoritmo do banqueiro, ele investiga cada sequência de alocação possível para os processos que permanecem inconclusos.

Recuperação de Deadlocks

Quando um algoritmo de detecção de determina que ocorreu um deadlock, existem várias alternativas. Uma delas é informar ao operador que ocorreu um deadlock e deixá-lo lidar com o problema manualmente. Outra é permitir que o sistema se recupere do deadlock automaticamente . Exitem duas possibilidades para interrupção de um deadlock. Uma é simplesmente abortar um ou mais processos para romper a espera circular. Outra é provocar a preempção de alguns recursos de um ou mais processos envolvidos no deadlock.

Encerramento de Processos

Para eliminar deadlocks abortando um processo, podemos usar dois métodos.

1. Abortar todos os processos em deadlock. Ele romperá com o ciclo de deadlock, mas os processos em deadlock podem ter sido executados por muito tempo, e os resultados desses processamentos parciais devem ser descartados e  refeitos posteriormente.
2. Abortar um processo de cada vez até o ciclo de deadlock ser eliminado. Esse método pode causa uma sobrecarga já que após cada processo ser abortado, um algoritmo de detecção de deadlocks deve ser executado para determinar se algum processo ainda está em deadlock.

Abortar um processo não é tarefa fácil, já que se o processo estava no meio de uma atualização de um arquivo e for encerrado esse arquivo ficará em um estado incorreto.

Se o método de encerramento parcial for usado uma politica para o encerramento dos processos deve ser estabelecida

1. A prioridade do processo.
2. Por quanto tempo esse processo foi executado e quanto tempo falta para ele ser concluído.
3. Quantos recursos o processo usou e de que tipos o processo usou, leva-se em consideração se os recursos são facilmente interceptáveis. 
4. De quantos recursos o processo precisa para concluir sua tarefa.
5. Quantos processos terão de ser encerrados.
6. Se o processo é interativo ou batch

Preempção de Recursos

Para eliminar deadlock através da preempção de recursos, um preempção sucessiva de alguns recursos dos processos e dar esses recursos a outros processos até que o ciclo do deadlock seja rompido. Para isso três aspectos devem ser considerados.

1. Seleção de uma Vítima. Devemos levar em consideração o custo dessa preempção, que inclui a quantidade de recursos que um processo em deadlock está mantendo e quanto tempo o processo levou para ser executado até o momento.
2. Reversão. Ao abortar um processo através da preempção de algum recurso que ele estava utilizando a melhor maneira de executar esse processo é reiniciando-o, embora seja mais fácil continuar de onde o processo foi interrompido isso requer que o sistema mantenha mais informações sobre o estado de todos os processos em execução.
3. Inanição. Em um sistema de seleção de vitima baseado principalmente em fatores de custo, pode ocorrer que sempre o mesmo processo seja selecionado como vitima. Com isso o processo nunca concluirá sua tarefa. Desta forma o sistema deve garantir que um único processo seja selecionado apenas uma determinada quantidade de vezes como vitima, para não entrar em inanição. A solução mais eficaz é colocar o numero de reversões no fator de custo.

Descrição do Algoritmo

   Esse algoritmo usa o sistema do tipo 'pegue a ficha', como os utilizados nas padarias muito movimentadas por isso foi apelidado de Algoritmo da Padaria de Lamport. Esse algoritmo toma como modelo um cenário do mundo real, ou seja, esperar para ser atendido em uma padaria. Ele é modelado segundo um modelo de padaria no qual um funcionário atende aos pedidos no balcão, onde esse funcionário só pode atender um cliente por vez.

    Em uma sequência ascendente de fichas pegas pelos clientes na entrada da padaria o funcionário faz o atendimento pelo cliente que estiver com a ficha de menor 'valor', o cliente faz o seu pedido, o funcionário pega as mercadorias, o cliente paga pelo que comprou e sai da padaria. Mas diferente de um distribuidor de fichas do mundo real, o algoritmo  de Lamport permite que vários threads obtenham o mesmo número de ficha. O algoritmo de Lamport inclui um mecanismo de resolução de impasse que garante que somente um thread por vez possa executar em sua seção crítica, no caso da padaria é quando o cliente está na sua vez de ser atendido.  O código foi desenvolvido na linguagem C++ e pode ser baixado AQUI!