# Cour 5 -- Théorie de la concurrence

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

[Somaire](IAsAMpizSpawifCj1gZ__g#)\
[precedent](/WyOYasmPQPKvNqlL6rrtHw)

> [time= 14 oct 2020]

[TOC]

## test and set
- **test-and-set** \
lit la valeur courante et
- **reset**\
remet a 0


- on a bien exclusion mutuelle
- on a pas interblocage
- mais on peut avoir **famine**

## sémaphore
Intoduit par Dijkstra en 1965.\
Objets de plus haut niveau pour modéliser des ressources.

Idée général:\
On dispose d’un certain nombre (connu) de ressources.\
Les processus qui en ont besoin, peuvent les demander.
Si il n’en reste plus de disponible, les processus sont mis en attente (de différentes manières)

On va distinger 3 type de sémaphore:
- **sémaphore faibles**\
les processus mis en attente sont bloqués,
lorsque la ressource est de nouveau disponible,
**un** processus en attente est réveillé.
- **sémaphore fort**\
les processus mis en attente sont bloqués
et mis dans une structure FIFO,
et lorsque la ressource est de nouveau disponible,
le processus en attente depuis le **plus longtemps** est réveillé.
- **sémaphore busy-wait**\
les processus restent actifs
et font des sortes de await pour tester si la ressource est de nouveau disponible.

Un sémaphore S se compose de 2 champs:
- **S.V**: un entier (ou booléen) représene la valeur de S
- **S.L**: une liste des processus en attente (endormis)
- semaphore fort: FIFO

Les opération de base(atomiques):
- Wait(S) (aussi appelé *down(S)* ou *P(S)*)
- Signal(S)

## sémaphore faible / fort

def Wait(S):
{
    if S.V > 0:
        S.V -= 1
    else:
        S.L = S.L.union({P})
        P.état = bloqué
}

def Signal(S):
{
    if S.L.empty():
        S.V += 1
    else:
        P = Extraire(L)
        P.état = prêt
}

### sémaphore busy-wait

def Wait(S):
{
    await(S.V > 0)
    S.V -= 1
}

def Signal(S):
{
    S.V += 1
}

Sémaphore busy-wait **binaire** S s'implémente facilement avec un test-and-set

def Wait(S):
{
    await(test_and_set(S) == 0)
}

def Signal(S):
{
    reset(S)
}

### Sémaphore
:::info
**Propriété:**
Soit k la valeur de S.V à l'initialisation. On a:
1. $S.V \geq 0$
2. $S.V = k + \#signal(S) - \#Wait(S)$
:::
- #signal(S) est le nombre d'opération signal
- #Wait(S) est le nombre d'opération wait

### Exclusion mutuelle

L'algo vérifie l'exclusion mutuelle
(sous hypothèse de terminaison de SC et d’équité entre processus).
$$
\begin{align}
&Nb_{SC} = \#Wait(S) - \#Signal(S)\\
&\text{On sais avec la propriété précédente:}\\
&S.V = 1 + \#signal(S) - \#Wait(S) \geq 0\\
&\#signal(S) - \#Wait(S) \leq 1\\
&Nb_{SC} \leq 1\
\end{align}
$$
### absence d'interblocage

$$
\begin{align}
&\text{Supposons P1 et P2 bloqué dans le Wait}\\
&\Rightarrow \#Wait(S) = \#Signal(S)\\
&\Rightarrow S.V = 1 (cf.porp)
\end{align}
$$

### absence de famine
- Oui pour 2 processus.
- Mais pour n processus on a famine pour:
- sémaphore faible (oui)
- sémaphore fort (non)

### Récapitulatif

| | sémaphore fort | sémaphore faible | busy-await |
|:---------------------- |:------------------:|:------------------:|:------------------:|
| absence d'interblocage | :white_check_mark: | :white_check_mark: | :white_check_mark: |
| absence de famine | :white_check_mark: | :x: | :x: |

## probleme de précédence
Une tâche T doit être réalisée avant T’

solution:

S = Semaphore_binaire(0)
# T se termine en faisant un signal:
signal(S)

# T' commence avec un wait
wait(S)

## producteur / consomateur
Communication asynchrone:
- Des ressources sont produites et stockées dans un buffer
- Elles sont consomées par d'autres processus (si disponibles!)



## Les philosophes

n philosophes pensent et mangent.\
Pour manger, un philosophe doit avoir sa baguette de gauche et sa baguette de droite.

Porpriéte:
1. on ne mange qu'avec les baguettes à proxi
2. Une baguete n'est tenue que par au plus un philosophe
3. absence de blocage
4. absence de famine
5. Efficace

### naive

### ticket

L'agorithme vérifié l'absence de famine sous hypothèse déquité entre philosophe et de terminasion des repas si:
- tikect est un sémaphore fort
- tikect est un sémaphore faible et M = n - 1

### asymétrique
Il suffit qu'un des philosophe commence par la baguette de droite



## algorithme de Freidberg - Peterson (1987)

pour l’exclusion mutuelle de n processus

### portier


### Algorithme


Propriété: si deux processus détiennent les deux sémaphores, alors ils n’ont pas franchi de la même manière le test (3).

Preuve: Supposons le contraire.
Un processus détient donc S0 et l’autre S1.
Leurs variables monnum a donc une valeur différente.
Si ils franchissent le test de la même manière (Vrai ou Faux), il faut donc que numero ait changé entre les deux tests.
Or cela suppose qu’un processus ait détenu les deux sémaphores (ligne 6) ! Impossible.

### exclusion mutuelle
Preuve: Supposons le contraire.
Si Pi et Pj sont en SC au même moment, ils détienne chacun un sémaphore. Aucun n’est donc « portier »... ils ont donc accédé à leur SC via le else ligne 13, et donc ils ont franchi de la même manière le test ligne 3.
Contradiction avec la propriété précédente.

Propriété: Si le portier attend le sémaphore Sk (lignes 5 ou 9), alors le nb de proc ayant monnum==k diminue.

Preuve:
Il y a au plus un portier (il faut passer le test l3 avec ⊤). Supposons que son monnum=0.
Le nombre de processus attendant S0 est fini. Et la valeur de numero ayant été changée par le portier, aucun nouveau processus n’attendra S0 (pour le moment).
Le portier va alors laisser réveiller et faire passer tous les processus en attente de S0 et leur nombre diminue donc!

### Absence de famine

Propriété: Le portier finit par accéder à sa SC (sous hypothèse...)
Preuve:
Lors que tous les processus attendant le sémaphore dont s’occupe le portier, seront passés, alors... le portier passera lui-même !
Bien sûr cela suppose équité entre processus et terminaison de la SC...

Propriété: L’algorithme assure l’absence de famine (sous hypothèses...)

Preuve:
Supposons que Pi soit en famine. Alors ce n’est pas un portier (cf la propriété précédente).
Pi n’a besoin que d’un seul sémaphore pour gagner sa SC (avec le else ligne 13). Disons S0.
Si un processus Pj a monnum=numero=0, alors il deviendra portier et fera passer Pi.
Sinon c’est que S0 est pris par le portier de S1. Dans ce cas numero vaut 0. Et quand le portier de S1 se passé en SC, ce sera au tour de S0: un portier finira par être choisi et Pi pourra aller en SC.