# Système d'Exploitation : Cours 4 : Synchronisation

- [Système d'Exploitation : Cours 4 : Synchronisation](#système-dexploitation--cours-4--synchronisation)
  - [Interactions entre les programmes](#interactions-entre-les-programmes)
  - [Synchronisation](#synchronisation)
  - [Communication](#communication)
  - [Section critique](#section-critique)
  - [Sériabilité et atomicité](#sériabilité-et-atomicité)
  - [Gérer les risques d'incohérence](#gérer-les-risques-dincohérence)
    - [Guérir](#guérir)
    - [Solution à l'exclusion mutuelle](#solution-à-lexclusion-mutuelle)
  - [Sémaphores](#sémaphores)
    - [Sémaphore d'exclusion mutuelle (MUTEX)](#sémaphore-dexclusion-mutuelle-mutex)
    - [Sémaphores privés](#sémaphores-privés)
    - [Interblocage](#interblocage)
    - [Ordonnancement des ressources](#ordonnancement-des-ressources)
    - [Sémaphores généraux](#sémaphores-généraux)
  - [Producteur/Consommateur](#producteurconsommateur)
  - [Les sémaphores en C](#les-sémaphores-en-c)
    - [Inclure l'entête `semaphore.h`](#inclure-lentête-semaphoreh)
    - [Déclarer un sémaphore :](#déclarer-un-sémaphore-)
    - [Initialiser un sémaphore :](#initialiser-un-sémaphore-)
    - [Opération P sur un sémaphore :](#opération-p-sur-un-sémaphore-)

## Interactions entre les programmes 

- Les problèmes dans les systèmes multi tâches sont dus aux interactions entre les tâches parallèles
- Partage de ressource → même résulat que si on est en séquentiel (pas d'incohérence due à la parallélisation)
- Communiquer, coopérer → définir un protocole pour communiquer entre programmes

## Synchronisation

- Résoudre les problèmes de cohérence sur la mémoire partagée
- Spécifier les dépendances entres les étapes de traitements (si une action doit être effectuée avant une autre)
- Régler les problèmes de concurrence sur l'accès à une ressource partagée (logicielle ou matérielle)

## Communication

- Mémoire partagée
- Tubes FIFO
- Boites au lettres asynchrones
- Buffers circulaires

> Une instruction C peut être assemblée en plusieurs instruction au niveau du code assembleur ! → Une instruction C n'est pas forcément atomique

## Section critique

Portion de code dans lequel une tâche utilise des ressources partagée mais qui ne pas être utilisées par celles-ci durant l'exécution de cette portion de code.

> Les sections critiques diminuent le taux de parallélisme, il faut les réduire au maximum afin de garantir la cohérence des données sans dégrader les performances gagnées grâce à la parallélisation.

## Sériabilité et atomicité

**Seriabilité :** exécution de deux taches peut se faire dans n'importe quel ordre sans incidence. Leur parallélisation est indépendante de l'ordonnancement.

**Atomicité :** deux tâches ne peuvent être mises en parallèle. On ne peut pas mettre en pause l'une pour démarrer l'autre. Chacune dur un temps nul pour l'autre. L'atomicité évite les interactions entre les tâches mais ne résout pas le problème d'interaction entre elles. 

> Les périodes d'atomicité diminuent le taux de parallélisme, il faut les réduire au maximum afin de garantir la cohérence des données sans dégrader les performances gagnées grâce à la parallélisation.

## Gérer les risques d'incohérence

Les tâches qui entrent en conflit sur des données (lecture / écriture concurrente) doivent être atomiques.
- Synchronisation pessimiste : prévention (section critique) → empêcher un soucis de survenir
- Synchronisation optimiste : guérison (estampilles) → détecter le problèmes et corriger les données pour garantir leur cohérence.

→ Dépend de la possibilité d'avoir les tâches actives ensemble.

### Guérir

- Copier la date (l'estampille)
- Copier les données
- Calculer les nouvelles valeurs
  *Début de l'atomicité*
- Copier la date actuelle (est ce que quelqu'un a changé l'estampille)
- Si elle est inchangée, modifier les donnée et augmenter la date
  *Fin de l'atomicité*
Sinon recommencer

### Solution à l'exclusion mutuelle

- Indépendant de la vitesse d'exécution des tâches
- Pas plus de deux processus *en même temps* dans une section critique
- Un tâches hors de sa section critique qui ne cherche pas à y rentrer ne doit pas empêchant une autre d'entrer en section critique
- Deux tâches ne doivent pas s'empêcher mutuellement et indéfiniment d'entrer en section critique → problème d'interblocage (deadlock)
- Un processus doit toujours entrer en section critique au bout d'un temps fini → problème de famine (livelock)

## Sémaphores

Un sémaphore est un objet sur lequel seulement deux opérations atomique sont possibles.

- P(sem) : décrémentation de la valeur du sémaphore. Appel bloquant si la valeur est inférieure à 0 (barrière)
- V(sem) : incrémentation de la valeur du sémaphore. Permet de débloquer une tâche bloquée par un appel à P

> Vient du hollandais Passeren (prendre), Vrygeven (libérer)

### Sémaphore d'exclusion mutuelle (MUTEX)

Sémaphore binaire initialisé à 1 qui sert à protéger une section critique. Cela permet d'assurer l'accès cohérent à un ensemble de variable auquel on fait correspondre une MUTEX.

### Sémaphores privés

A utiliser quand une tâche ne peut utiliser qu'une seule des primitives P ou V.
Le processus qui fait P attend un signal des tâches qui font V.
Si le processus est en avance il est bloqué, si le signal est émis en avance il est mémorisé.

### Interblocage

Il faut faire attention à l'interblocage de tâches.
Exemple avec deux tâches et deux sémaphores :
- A : P(S1)
- B : P(S2)
- A : P(S2) → appel à P bloquant
- B : P(S2) → appel à P bloquant

La situation est bloquée.

> On peut s'inter bloquer même avec un seul sémaphore

Remèdes : 
- Annuler un appel à P
- Remonter la tâches dans le code
- Pouvoir restaurer les données de la tâches
- Annuler toutes les opérations qu'elle a faite
- En pratique : détecter et détruire les tâches concernées...
- Même soucis qu'avec les estampilles...

Prévention :
- Problèmes compliqué mais dans des cas particuliers il y a des solutions simples
- Annonce des besoin : une tache demande une seule fois toutes ses ressources

### Ordonnancement des ressources

La tâche peut faire des demandes successives pourvu qu'elle porte sur des ressources comparables et qu'elles soient faites en suivant une *relation d'ordre*.

### Sémaphores généraux

- Utilisés comme compteur de ressources : pas limité à 0 ou 1 contrairement aux MUTEX
- Valeurs du sémaphore : valeure initiale correspond au nombre de ressource maximum, la valeur courante, le nombre de ressources disponibles.
- L'opération P permet d'acquérir une ressource, appel bloquant si aucune ressource n'est disponible
- L'opération V permet de libérer une ressource

## Producteur/Consommateur

Un système possède N emplacement pour stocker de l'info :
- Les tâches *productrices* produisent de l'information vers ces emplacements
- Les tâches *consommatrices* utilisent l'information et libèrent l'emplacement correspondant.

Un sémaphore est nécessaire pour synchroniser les deux types de processus : 
- Bloquer les producteurs s'il n'y a plus de places
- Bloquer un consommateur s'il n'y a plus d'information disponible.

## Les sémaphores en C

### Inclure l'entête `semaphore.h`

```c
#include <semaphore.h> 
```

### Déclarer un sémaphore :

```c
sem_t semaphore;
```

### Initialiser un sémaphore : 
```c
int sem_init(sem_t *semaphore, int pshared, unsigned int value)
```

- `semaphore` &rarr; adresse sur sémaphore à initialiser
- `pshared` &rarr; indique si le sémaphore est partagé entre des threads, si il est égale à 0 le sémaphore sera partagé et doit avoir une adresse visible de tous ces threads (globale ou varibale allouée dynamiquement)
- `value` &rarr; value à initialiser

### Opération P sur un sémaphore : 

```c
int sem_wait(sem_t * semaphore)
```


<br><br>
Opération V sur un sémaphore

```c
int sem_post(sem_t * semaphore);
```