Aula 28/03

Ações atomicas e comando await

Duas formas de obtermos «ordem» corretas:

  • Blocos atomicos - exclusão mutua
  • Atraso de edxecução ate que algo seja valido - condição de sincronização

Referencia critica

Definição: Referencia para uma variavel modifica por outro processo concorrente.

Se estes dois processos concorrentes não há referencia criticas a execução parece atomica.

Propriedade “no maximo uma vez”

Uma atribuição x = e satisfaz a propriedade se uma das seguintes opções forem satisfeitas:

  1. e contem no maximo uma referencia critica, e x não é lido por outro processo;
  2. e não contem referencias criticas, e nesse caso x pode ser lido.

Motivação: ter execução que pareçam atomicas com apenas uma referencia não é possivel saber quando ocorre a atualização.

Primitiva de sincronização: <await(B) S>

  • Enquanto B não for verdade, a execução espera - condição de atraso;
  • Se B for verdadeiro, S é executado - sequencia de comandos.

Note que S vai ser uma expressão atomica

Exemplos

  1. < await (s > 0) s = s-1>
  2. < await (coount > 0)>

Importante: Se a condição B respeita a propriedade no maximo uma vez, <await(B) é equivalente á while not B.

Produtor / consumidor

Variaveis p e c que controlam os itens produzidos e consumos.

Sincronização -> c <= p <= c+1

int buff p = 0, c = 0;

process Producer {

    int a[n];

    while (p < n){

        < await (p == c) >
        buff = a[p];
        p++;
    }
}

process Consumer {

    int b[n];

    while (c < n) {

        < await (p > c) > // Isso pode ser trocado por um while
        b[c] = buff;
        c++;
    }    
}

// Neste caso, os valores do vetor a[] vão ser tranferidos para o vetor b[] atravez do buff.
// As clausulas de <await> garante que essa tranferencia vai ser feita de forma correta.

Propriedades de Safety / Liveness

  • Safety: não acontece nada de errado durante.
  • Liveness: terminaçao chega ao estado final.

Se eu tenho um programa sequencia, temos as seguintes definições:

  1. Safety == estado final correto do programa.
  2. Liveness == Programa chega ao estado final.

Se eu tenho um programa em paralelo, as definições são as seguintes:

  1. Safety == Exclusão mutua e ausencia de deadlocks.
  2. Liveness == Um processo entrara em algum momento na seção critica, alem de uma mensagem chegar ao seu destino em algum momento.

Justiça (Fairness)

Garantia de que todos os procesos podem prosseguir.

  • Justiça incondicional: toda ação atomica passiva de execução é executada em algum momento.
boolean continue = true, try = false;

// Uma thread
concorrente {
    while (continue){
        try = true;
        try = false;
    }
}

// Outra thread
< await (try) continue = false >
  • Justiça fraca: Cada ação condicionamal atomica é executada em algum momento se a condição fica e permanece verdadeira.
  • Justiça forte: É incondicional. Toda ação condicional atomica executavel é executada em algum momento, assumindo que a condição é frequentemente verdadeira. Porem, JUSTIÇA FORTE É IMPRATICAVEL.