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