Aula 26/03

Atômicidade - Programação com variaveis compartilhadas

aula baseada no capitulo 2 do livro de Ben-Ari e Andrews

Definição: Um programa concorrente consiste em um numero finito de processos. Cada processo é escrito usando um conjunto finito de instruções atômicas.

Definição: O estado de um programa é o conteúdo de suas variaveis em um dado momento.

Varivel explicitas: Variaveis declaradas no programa, faceis de serem vistas.

Variaveis implicitas: Registradores e pontos de controle (PC, IC).

Um processo executa um sequencia de instruções. Ou seja, processo é algo sequencial. Alem disso, um processo possui uma parte da memoria.Uma instrução é uma sequencia de uma ou mais instruções atomicas.Instrução atomica é uma ação indivisivel que examinam ou alteram o estado do programa.

A execução de um programa concorrente consiste de sequencias de instruções atomicas intercaladas. Ou seja, quando aplicações são executadas de forma paralelas eu posso definir/enxergar uma sequencia na qual as intruções atomicas foram executadas.

História é uma sequencia de execução das ações atomicas.

Papel da sincronização => restringir o conjunto das historias possiveis a um conjunto desejavel. Ou seja, cada processo roda de forma independete, para que eu não tenha historias desejadas eu preciso de algum mecanismo para sincronizar as execuções.

Exclusão mutua => Criar sessões que parecem atomicas.

Condição de sincronização => atrasar uma ação ate que seja valida uma condição.

Definição: O estado de um algoritmo concorrente corrresponde aos estados das variveis e os respectivos ponteiros de controle dos processos.

Definição: Dados dois estados s1 e s2, existe uma transição entre s1 e s2 se alguma das intruções apontadas pelos ponteiros de controle muda de s1 para s2.

Um diagrama de estados é uma representação de todos os possiveis estados da aplicação, a cada passo.

Mini-EP

Encontre o máximo de um vetor com inteiros positivos. Tranforme o codigo sequencial para um paralelo.

int m = 0
for [i = 0 to n-1]
    if (a[i] > m)
        m = a[i]
  1. Transformar para um for atomico, que faz tudo de uma vez
  2. Transformar o if e a atribuição em uma estrutura atomica (sessao critica <>), porem isso faz com que todo mundo entra na sessão critica
  3. Criar um novo if para reverificar, almentando a eficação da sessão critica.
int m = 0
forall [i = 0 to n-1]   
    if (a[i] > m)
        <if (a[i] > m)
            m = a[i]>

A tarefa do mini-ep é descobrir qual a quantidade ótima de if”s a serem colocados. Sendo que o ultimo if é atomico (esta na sessão critica). A ideia é minimizar o numero de acessos a sessão critica.