# 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
```