Problématique
Lorsque deux tâches (processus ou threads) accèdent à une même zone mémoire, elles peuvent interagir de manière indésirable,
- même si chaque tâche, prise indiduellement, se comporte correctement.
Concurrence sans problème
Tache1 :
compte+=1000 ;
Tache2 : Compte -=500 ;
//valeur initiale de Compte=2000
Charger(r1,Compte)
Charger(r2,1000)
Ajouter(r1,r2) //r1 :=r1+r2
Ecrire(r1 ,Compte) / /Compte=3000
Tache 2 :
Charger(r1,Compte)
Charger(r2,500)
Soustraire(r1,r2) //r1 :=r1- r2
Ecrire(r1 ,Compte) //Compte =2500
Concurrence problématique
Charger(r1,Compte)
Charger(r2,1000)
Ajouter(r1,r2) //r1 :=r1+r2
Ecrire(r1 ,Compte) //Compte=3000
Définitions
- Une ressource est dite ressource critique lorsque des accès concurrents à cette ressource peuvent résulter dans un état incohérent.
- On parle aussi de situation de compétition (race condition) pour décrire une situation dont l’issue dépend de l’ordre dans lequel les opérations sont effectuées.
- Une section critique est une section de programme manipulant une ressource critique.
Exclusion mutuelle
-Une section de programme est dite atomique lorsqu’elle ne peut pas être interrompue par un autre processus manipulant les mêmes ressources critiques.
- Un mécanisme d”exclusion mutuelle sert à assurer l’atomicité des sections critiques relatives à une ressource critique. en anglais : mutual exclusion, ou mutex
- Exclusion : deux tâches ne doivent pas se trouver en même temps en SC
- Progression : une tâche doit pouvoir entrer en SC si aucune autre ne s’y trouve
- Équité : une tâche ne devrait pas attendre indéfiniment pour entrer SC
- L’exclusion mutuelle doit fonctionner dans un contexte multi-coeurs
Les sémaphores
Introduit par Dijkstra en 1965 pour résoudre le problème d’exclusion mutuelle. Permettent l’utilisation de m ressources identiques (exemple imprimantes) par n processus.
Un sémaphore est une structure contenant deux champs :
– Struct {n : entier ;
en_attente : file de processus
}
Un sémaphore est une variable globale protégée, c’est à dire on peut y accéder qu’au moyen des trois procédures :
– I(S, x) : initialiser le sémaphore S à une certaine valeur x;
– P(S) : Peut-on passer ?
– V(S) : libérer?
Les moniteurs
–Proposée, par Hoare en 1974, dans le langage Portal. Les moniteurs sont un moyen aussi puissant mais
–beaucoup plus sûr de réaliser l'exclusion mutuelle et la synchronisation.
–C’est une structure de données composées d’attributs et de méthodes qui partagent en exclusion mutuelle ces attributs.
–Si un processus P1 est actif dans le moniteur (c-a-d en exécution d’une méthode du moniteur) sur un
–objet et qu’un autre processus P2 demande l’accès au moniteur (c-a-d invoque une méthode du
–moniteur) sur ce même objet alors P2 est mis en attente du moniteur jusqu'à ce que P1 libère l’accés.
–Chaque moniteur a une file d’attente gérée FIFO.
–Pour assurer l’exclusion mutuelle, il suffit de regrouper toutes les sections critiques et toutes les variables partagées d’un problème dans un même moniteur.
