02/04

Locks e Barreiras (Cap 3)

Problema da seção critica: Nesse problema n processos executam repetidamente uma seção critica e, após, uma seção nao critica.

• Protocolo de entrada: faz o codigo entrar na seção critica
• Protocolo de saida: faz o codigo sair da seção critica

process CD [i = 1 to n]
    while (true)
        protocolo_de_entrada

        seção_critica()

        protocolo_de_saida

        seção_normal()

Suposição: um processo que entra em uma seção critica sai dela. Ou seja, o processo passa pelo protocolo de entrada, executa, sai pelo protocolo de saida e termina a execução.

Propriedades a serem respeitadas

• Safety:
  1. Exclusão mutua - Garante que so haja um processo em dado momento.
  2. Ausencia de deadlocks - Se dois processos tentam entrar, ao menos um vai conseguir.
  3. Ausencia de atraso desnecessario - Se um processo esta tentando entrar um uma sessao critica e os outros estao em uma sessão nao critica, ele não é impedido de entrar.
• Liveness
  1. Entrada garantida - Um processo que esta aguardando a entrada na SC, este irá entrar em algum momento.

Vamos começar com 2 processos de exemplo:

1ª:

int turn = 1

process CS1
    while (true)
        < await (turn == 1) >

        sessao_critica

        turn = 2

        Sessao_nao_critica()

process CS2
    while (true)
        < await (turn == 2) >

        sessao_critica

        turn = 1

        Sessao_nao_critica()

• [x] Exclusão mutua (Por causa do wait)
• [x] Ausencia de deadlock (Por causa do await)
• [ ] ATRASO - Problema causado por causa da sessão nao critica, pois esta pode demorar e fazer com que o outro processo tenha que esperar, sendo que ele poderia ser executado. Logo, esse codigo é perfeito para executar processos alternardos, cada um vai rodar uma vez, e depois o outro, e assim por diante, mas eles nao vao rodar em paralelo. Tal fato se deve á sessai Sessao_nao_critica, que pode ter a execução demorada e atrasar o reasign da variavel turn.

2º:

boolean in1 = in2 = false

process CS1
    while (true)
        < await (!in2) in1 = true>

        sessao_critica

        in1 = false

        Sessao_nao_critica()

process CS2
    while (true)
        < await (!in2) in2 = true>

        sessao_critica

        in2 = false

        Sessao_nao_critica()

• [x] Exclusão mutua - A função wait cuida disso, fazendo funcionar
• [x] Ausencia de DeadLocks - Manejado pela clausa de atribuição do await
• [x] Atraso - Agora o problema foi corrigido, pois logo apos um processo terminar a sessão critica ele possibilita que o outro seja iniciado, atravez do booleano
• [x] Entrada garantida - Sim, com justiça forte

Como fazer para não usar os awaits

1. Primitiva de hardware
2. Algoritmos + tops

Instruções do tipo test-and-set

boolean TS (boolean lock)
    < boolean inicial = lock
      lock = true
      return inicial >

Tal implementação é garantida de ser atomica em nivel de hardware.Podemos substituir o <await…> por while(TS(lock)) sleep. Porem, tal medida pode sobrecarregar o cache. A sução é fazer:

while (lock) sleep
while (TS(dlock))    
    while (lock)
        sleep

Como implementar o await

A ideia para um await < await(B) S> é:

CSenter # Protocoloto de entrada

    while (!B)
        CSexit # Deixar algum outro processo funcionar
        sleep # Esperar
        CSenter # Fazer a entrada novamente

    S # Cheguei na condição e quero executar a instrução

CSexit # Protocolo de saida