# Cour 1 -- Théorie de la concurrence

###### tags `cour` `M1 S1` `Concurrence`

[Somaire](IAsAMpizSpawifCj1gZ__g#)\
[~~precedent~~]()
> [time= 9 sept 2020]

[TOC]

## introduction

**Pourquoi utiliser des programmes concurrents?**\
Pour gagner en efficacité!
Distrivuer les données, partager les ressources, utiliser des réseaux...

#### Plan:
**Théorie**:
- Intro
- définition
- instruction atomique
- sémantique d'entrelacement
- Exclusion mutuelle
- algo de Dekker
- algo de Peterson
- algo de la boulangerie (ticket)
- monieur, sémaphores
- lecteurs / écrivains
- producteurs / consomateurs
- Extension
- Communication par envoie de message

**Pratique**
En JAVA (avec le module concurency)
- thread
- variables partagées
- synchronized
- wait
- signal
- ...

On va prouver les algorithme concurent.

On aurra besoin d'installer [SPIN](http://spinroot.com/spin/)

## définition
:::success
Un programme concurent est un ensemble de **programme séquentiels** executé en **"parallele\*"** avec de la **communication\*\*** entre eux.
:::
### Parallele
Ici on considère des exécutions sur des processus différents (sens habituel de "parrallèle") mais aussi des systèmes multi-taches ou le parallélisme n'est qu'apparent.

### communication
- communication de données.
- synchronisation: échange d'informations sur le *controle* (état) des processus.

### execution concurentes
:::success
**procesus**: programme en cous d'execution
:::

L'execution d'un programm concurrent:
- ensemble fini de processus séquentiels
- chaques processus est décrit par un ensemble fini d'**instruction atomique**
- chaque processus dispose d'un *pointeur d'instruction* (pointeur de controle, compteur de prog.) désignant la prochaine instruction devant etre executée.
- l'execution du programe concurent consiste en un **entrelacement arbitraire** des instruction des processus.
- lors d'une execution, la prochaine insctruction est donc choisis parmi celles pointées par les points d'instruction

Il y a donc **plusieur scénario possible**

## Communication par mémoire partager
Diférents processus peuvent partager de la mémoire(des variables).
On peux distinger 2 cas:
###### les variables simple
Les variables **simple** avec une lecture et une écriture **atomique**.
On en distingue 2 types:
- Les variables en lectures et en écriture pour plusieurs processus **"++Mutiple++ Reader/ ++Mutiple++ Writer"**
- les variables *propre* en lecture pour plusieur processus mais en écriture pour un seul **"++Mutiple++ Reader/ ++Single++ Writer"**

###### Construction élaborées:
- sémaphores
- test and set, swap ...
- moniteur


On a donc plusieur scénario, avec un ++programme non déterministe++.

### instruction atomiques
:::success
Une **instruction atomique** est exécutée complètement sans interruption.
:::

**Exemple:**
- :white_check_mark: x:=5
*est bien atomique*
- :x: x:=x + 1
*est pas atomique*

    tmp := x
    x := temp + 1

- :x: Si x:=2 alors x:=3
*non atomique (sauf si test-and-set)*


Les résultats peuvent etre très différent.

## Hypothèse d'atomicité
Attention au compilateur.

:::warning
**Eviter** les instruction manipulan **plusieur variables** ou occurences de variables pouvant etre modifiées et lues par plusieurs procesus.
:::

Plusieurs cas:
- **registre atomique**: opération de *lecture* et d'*écriture* atomiques
- **test-and-set**: on affecte une valeur à un registre et on renvoie la valuer
- **swapp** : on échange la valeur d'un registre *partagé* et d'un registre *local*

## Sémantique d'entrelacement
:::success
**L'++état++ d'un programme concurent P est un n-uplet** avec:
- un pointeur d'instructions par processus
- une valeur pour chaque variable (locale ou partagée)

++Exemple:++ *(n=1, end, x=1, b~2~, u=2)*
:::

:::success
Pour 2 etats s~1~ et s~2~, on écrit **s~1~ ->~p~ s2** lorsque l'on peut passer de s~1~ à s~2~ en utilisant une instruction pointé dans s~1~.

++Exemple:++ (n=1, end, x=1, b~2~, u=2)* ->~p~ (n=2, end, x=1, end, u=2)*
:::

:::success
Le **driagamme d'état** de P est le systeme de transitions (un graphe) **S~p~(S, A, s~0~)**
- S est l'ensemble des états possibles pour P
- A est la relation -> P
- s~0~ est l'état initial de P
:::
Un chemin dans S~p~ est un scénario possible pour P.

L'ensemble des chemin sont tout les état possible de mon programme.

On se limitera parfois au scénario "équitables" où chaque processus avance de temps en temps...

On prouvera la correction de nos algorithmes pour tout entrelacement (ou tout entrelacement équitable) -> notion Robuste.

### Discution de Sémantique

*Que l’on considère des systèmes multi-tâches sur 1 CPU, ou des systèmes multi-processeurs, ou encore des systèmes distribués (avec envoi de messages), le choix de la sémantique d’entrelacement est raisonnable...*

:::info
##### Système multi-tache:
Un CPU avec plusieurs processus (pas de « vrai » parallélisme). Il y a bien une succession d’instructions d’un processus, puis d’un autre, etc.

Sémantique OK !
:::

:::info
##### Systeme multi-processeur
Plusieurs CPU (avec mémoire locale) + mémoire globale.
Chaque processus est affecté à un CPU.
La sémantique d’entrelacement ne correspond pas exactement à la réalité, mais elle est correcte si il n’y a ++pas de conflit de ressources++ (*ie d’accès en lecture et en écriture à une même donnée*). D'ou l'importance du problème de ++l’exclusion mutuelle++.
:::

:::info
##### Système distribués:
Plusieurs machines, pas de ressources globales, des canaux de communication.
Très différent des deux autres cas... mais la sémantique d’entrelacement reste intéressante (on y intègre l’envoi et la réception de messages).
:::

### Ecriture d'un programme concurent
instruction spécial:
- **loop forever** boucle infinie.
- **await C**: attente active d'un condition booléenne C dépendant de la partagées.

**+** la syntaxe particulière des *sémaphores*, *test-and-set*, *moniteurs*...
**+** la syntaxe JAVA (pour les TP)

---

## exclusion mutuelle

### Probleme de section critique
:::info
**Le probleme:**
N (>2) processus exécutent continuellement 2 séquences d'instructions:
- une section non critique (**SNC**)
- une section critique (**SC**)

de telle manière que l'exécution mutuelle assurée en SC: ++au plus **un processus** en SC à tout instant++.
:::
Nous allons utiliser des variables partagées (*qui ne seront pas utilisées en SNC et SC!*) dans:
- **préprotocole** avant d'accéder en SC
- **postprotocole** apres avoir accéder à la SC

++Processus P:++

loop forever
p1: section NC (section non critique)
p2... pré-protocole
pi: section critique
pj...: post protocole

:::warning
hypothéses supplémentaires:
- SC critique termine toujours
- SNC peut ne pas terminer (boucle infinie)
- Les 2 processus restent toujours actifs
:::

:::success

#### propriété attendu
- **Execution mutuelle**:
Au plus un seul processus en SC à tout instant.
- **Absence de famine**:
Si un processus souhaite accéder à sa SC, il y parviendra un jour.
- **Absence d'inter-blocage**:
Si plusieurs processus essaient d’accéder au même moment à leur SC, ils ++ne doivent pas se bloquer dans le préprotocole++ et un processus doit réussir à y accéder.
- **Attente borné**:
Lorsque un processus attent pour accédé à sa SC, on peut borner le nombre de fois ou il sera "doubler" par d'autres processus.
- **Absence de privilèges**:
Chaque processus est traité à égalité.
:::

Absence de famine => Absence d'inter-blocage

###### Le problème

###### Diagramme d'état

Se programme donne P1 puis P2 etc...
Si P1 est dans sa section critique boucle a l'infini. Le programme n'arrete pas.

- :white_check_mark: Execution mutuelle
- :white_check_mark: Absence d'inter-blocage
- :x: Absence de famine
- (:white_check_mark:) Attente borné
- :x: Absence de privilèges

[suivant](/_24sdF4rT7uqUo-gfwI6QA)