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.