Trabalho - Banco de Dados Orientado a Objetos

Nome: Adriany Alves Ribeiro             RGM: 147577-1

             Mariane Cardoso Cassola      RGM: 147540-1

Sandro Clayton

Tais Moreno              

Banco de dados orientado a objetos

São Paulo, 28 de Maio de 2015

Introdução:

Neste trabalho iremos apresentar algumas alternativas para realizar a exclusão mútua, que nada mais é do que um modo de fazer com que outros processos ou threads sejam impedidos de usar uma variável ou arquivo compartilhado que estiver sendo utilizado em outro processo e para isto o processo deve iniciar uma seção crítica. A seguir iremos ver alguns algoritmos que tem função de evitar que dois ou mais processos entrem nesta seção crítica, e realizar então esta técnica usada em programação concorrente.

Desabilitando Interrupções

Uma das formas de se obter exclusão mútua é desabilitando interrupções, mas essa meio acaba gerando limites ao software em uma seção crítica. No sistema uniprocessador, o mais simples a se fazer é desabilitar as interrupções assim que entrar na região crítica e habilitar antes de sair dela. O sistema não poderá mais utilizar temporizadores para obter controle do processador. No sistema multiprocessador se os threads não forem sincronizados, a desabilitação de interrupções não irá gerar a exclusão mútua, pois não irá evitar que eles executem simultaneamente. Sendo assim, apenas desabilitando interrupções não é a melhor forma de se obter exclusão mútua.

Variáveis de Impedimento

As variáveis de impedimento funcionam da seguinte forma: considere uma única variável compartilhada (lock), inicialmente no valor 0. Para poder entrar na sua região crítica, o processo antes deve testar se há variável de impedimento e verifica o valor da mesma. Caso o valor da variável seja 0, o processo entra na região crítica e altera o valor da variável para 1, mas se o valor for  1, o processo deverá esperar até que o valor passe a ser 0. Assim quando a variável for 0 significa que não existe nenhum processo na região crítica e se for 1 significa que ainda há algum processo em sua região crítica. Mas pode ocorrer uma falha, quando por exemplo um processo A verifica a variável lock e seu valor seja 0, e antes que este processo atualize o valor dela para 1, um processo B executa e atualiza o valor da variável lock para 1. Assim quando for executado novamente, o processo A também atualizará o valor da variável lock para 1, e então os dois estarão em suas regiões críticas ao mesmo tempo.

Alternância Obrigatória

Na alternância obrigatória nós trabalhamos com uma variável inicial para controlar a vez dos processos a entrarem na região crítica, é feito um algoritmo que determina que, por exemplo: o processo A só poderá acessar a região critica quando a variável estiver em 0, e o processo B só poderá quando a variável estiver em  1, está variável inicialmente é zero, então o processo que deseja entrar em região crítica verifica essa variável, no caso diremos que o processo A que verificou e então como a variável está em zero ele entra em estado critico, outro processo, no caso o B também necessita entrar, então ele verifica esta mesma variável e a encontra em zero, então ele entra em um loop testando continuamente está variável, assim que o processo que está em região crítica(processo A)  acabar, ele irá trocar esta variável para um, neste momento o processo B poderia entrar, mas neste momento vamos dizer que ele está na verdade ocupado  executando em sua região não-crítica, o único problema então passa a ser que, caso o processo A precise voltar a região crítica, ele precisará esperar até o processo B necessitar também, para que ele passe por ela e troque a variável para zero novamente, ou seja, o processo que necessita terá que esperar outros processos precisarem dar entrada, para depois trocarem a variável, e assim eles terem acesso. Isto nós faz refletir e ver que não é praticável caso lidemos com processos mais lentos do que o restante dos concorrentes.

Solução de Peterson

Consiste em que cada processo antes de entrar em sua região crítica deve realizar uma chamada enter_region com número próprio, 0 ou 1 como parâmetro (no caso de lidarmos com dois processos) . Está chamada fará com que  processo esperar até que ele possa entrar com segurança, depois que acabou, o processo chama leave_region para falar que terminou de usar e está deixando livre para o próximo.  Caso os 2 processos, fizerem a chamada enter_region quase simultaneamente. Os dois armazenaram seu número de processo em turn. O único armazenamento que contará vai ser o ultimo, o outro é perdido.

A instrução TSL

A instrução TSL (teste e atualize variável de trava), que funciona junto com a ajuda do hardware, lê o conteúdo na memória (variável lock) no registrador e armazena um valor diferente de zero nesta memória. Esses processos de leitura e armazenamento são indivisíveis, então a palavra na memória não pode ser acessada por nenhum outro processador sem a instrução TSL ter terminado, onde a CPU que está executando a instrução impede o acesso ao barramento de memória. Comparada com a alternativa de desabilitar interrupções, a instrução TSL é muito mais eficaz pois impedindo o barramento de memória, um processo dois não poderá acessar a palavra no processo de leitura e escrita do processo um, o que não acontece na desabilitação de interrupções. Ao entrar na região crítica, o processo verifica o conteúdo de lock retorna, e assim que termina de executar a região crítica, o processo volta a colocar o valor de lock em zero.

O problema produtor-consumidor

No problema produtor-consumidor dois processos compartilham de um mesmo buffer de tamanho fixo, onde o produtor coloca informação dentro do buffer e o consumidor a retira.O problema ocorre quando o produtor quer adicionar uma nova informação no buffer, mas este já está cheio. A solução é colocar o produtor para dormir e só despertá-lo depois de o consumidor ter retirado um ou mais informações do buffer. A mesma coisa para o consumidor que ao dormir só será despertado após conter alguma informação no buffer. Para ter controle sobre estes itens no buffer é usado a variável count. Se a capacidade do buffer for armazenar N informações, o código do produtor verifica se count é igual N. Caso for verdadeiro o produtor dormirá; do contrário, o produtor irá adicionar um item e irá incrementar a variável count. Isso se repete para o código consumidor, caso o valor de N for  0, ele remove um item e decresce a variável. Mas a condição de disputa ainda poderá ocorrer pelo fato de a variável count não ter acesso restrito, assim pode acontecer de o produtor e o consumidor dormirem para sempre. Uma solução para tal disputa seria adicionar um bit de espera pelo sinal de acordar, o qual é ligado quando um processo acordado recebe um sinal de acordar, e é desligado quando um processo tentar dormir e estiver com o bit ligado, mas o processo permanecerá acordado.