Chapitre 3 : Gestion du parallélisme, communication et synchronisation entre processus
Chapitre 3 : Gestion du parallélisme: communication et synchronisation entre processus
Le multitâche permet donc de répartir le temps processeur entre plusieurs processus. Mais ce
multitâche ne sert à rien si il n'est pas possible de faire communiquer ces différents processus entre eux.
En environnement multitâche, les processus coopèrent en vue de la réalisation d’une activité
commune. On distingue deux sortes de coopération, la coopération temporelle faisant intervenir les notions
de blocage et déblocage des processus, la coopération spatiale se rapportant à l’échange d’informations
entre processus. Ces deux types de coopération caractérisent respectivement la synchronisation et la
communication.
L’une des difficultés de la mise en œuvre du multitâche étant d’assurer le partage des ressources du
système.
Trois outils sont définis pour permettre aux processus de communiquer et se synchroniser : les boîtes
aux lettres nommées message queues, les sémaphores, et les tableaux noirs : ce sont les IPC (Interprocess
Communication) permettant à des processus de communiquer et se synchroniser par : les signaux temps réel,
les fichiers temps réel, l’ordonnancement, les horloges haute précision et la mémoire non virtuelle. Un IPC
pouvant être utilisé par plusieurs processus, il est créé par le système d’exploitation et caractérisé par un nom
sous forme de chaîne de caractères. Lorsqu’un processus demande à créer un IPC partagé, il lui donne un
nom : si le nom n’est pas déjà utilisé par un IPC du même type, le système d’exploitation crée alors l’objet,
et le processus récupère un identifiant d’IPC lui servant à utiliser cet objet. Si le nom correspond à un IPC du
même type (boîte aux lettres, tableau noir, sémaphore) déjà existant, alors le système lui renvoie l’identifiant
de l’IPC déjà existant.
1 Le partage des ressources:
Lorsque le nombre des processus est largement supérieur aux ressources disponibles (le processeur est
lui-même une ressource), le problème de partage des ressources entre processus est crucial. Ce problème se
ramène à celui de l’ordonnancement des processus : quand et à qui allouer une ressource particulière .
2 Synchronisation :
Synchronisation des processus : pourquoi ?
- Partage de ressources : garantir que l'exécution en parallèle de plusieurs processus fournit le même
résultat qu'une exécution strictement séquentielle (pas d'interférences).
- Communication, coopération : garantir que l'échange d'information entre tâches obéit à un protocole
défini.
La synchronisation des processus implique l’introduction d’une section critique.
Exemple: mise à jour de comptes bancaires
VARIABLE val : ENTIER
PROCESSUS crediteur(c : ENTIER)
DEBUT
(1) val val + c
FIN
PROCESSUS debiteur(d : ENTIER)
DEBUT
(2) SI val < d ALORS
(3) ECRIRE(\D_ecouvert...")
(4) val val - d
FIN
(chaque ligne est supposée indivisible)
Pb: si on exécute : { val = 10 } debiteur(9) //debiteur(9) avec la séquence : (2)1 (3)1 (2)2 (3)2 (4)1 (4)2
Aucun découvert ne sera signalé, mais à la fin { val = -8 }
Les 2 processus entrent en conflit d'accès à la variable partagée « val ».
3 Synchronisation par événement :
Son rôle est d’attendre un événement (matériel, (capteur) ou logiciel) avant d’exécuter un calcul. (Figure 3.1
et 3.2)
Chapitre 3 : Gestion du parallélisme, communication et synchronisation entre processus
Figure 3.1 – Diagramme de transition lors d’un appel par événement : T2 plus prioritaire que T1.
Figure 3.2 – Chronogramme d’exécution pour le cas précédent.
4 Synchronisation par drapeau événement :
Le drapeau événement (event flag) permet simplement de signaler aux tâches la présence d'un événement.
Par exemple, une ISR est activée lors d'une interruption en provenance d'un périphérique, et peut ainsi
informer une tâche en attente que le périphérique est prêt pour livrer des données. (Figure 3.3 et 3.4)
Tâche T1 Tâche T2
void taskT1(void *cookie) { void taskT2(void *cookie) {
int evtMask; int evtMask;
evtMask = 9; evtMask ¦= 8;
event_signal(events, evtMask); event_wait(events, evtMask);
... ...
} }
Figure 3.3 – Définition de deux tâche T1 et T2.
Figure 3.4 – Chronogramme d’exécution pour les deux tâches T1 et T2.
Chapitre 3 : Gestion du parallélisme, communication et synchronisation entre processus
5 Interblocage:
Le phénomène d’interblocage (étreinte fatale ou deadlock) peut intervenir lorsque deux processus P1 et P2
sont en attente de libération de deux ressources R1 et R2 occupées respectivement par P1 et P2 de la
manière suivante : (Figure 3.5)
Processus P1 :
- Prendre la ressource R2 et l’occuper
- Prendre la ressource R1 dès que P2 la libère.
Processus P2 :
- Prendre la ressource R1 et l’occuper
- Prendre la ressource R2 dès que P1 la libère.
Ni le processus P1, ni le processus P2 ne peuvent s’exécuter car chacun attend une ressource occupée par
l’autre.
Figure 3.5 – Situation d’interblocage durant l’exécution de deux tâches.
L’interblocage peut arriver dans le cas de trois tâches partageant trois ressources critiques. (Figure 3.6)
Situation d'interblocage entre deux tâches Situation d'interblocage entre trois tâches
Figure 3.6 – Situation d’interblocage entre les tâches.
La tâche T1 détient actuellement la ressource R1 (une imprimante) et T1 veut la ressource R2 (un scanner).
La tâche T2 détient la ressource R2 et demande la ressource R3 (un tampon de mémoire). De même, la tâche
T3 détient la ressource R3 et souhaite la ressource R1. (Figure 3.6)
6 L’exclusion Mutuelle:
Le problème de l’exclusion mutuelle peut être mis en évidence sur deux exemples simple :
- deux trains circulant sur un tronçon de voie unique sont en exclusion mutuelle sur cette voie,
- deux processus en phase d’impression sont en exclusion mutuelle vis-à-vis de l’imprimante.
L’exclusion mutuelle de deux processus vis-à-vis d’une ressource partageable non réentrante
suppose une phase (section critique ) pendant laquelle un seul des deux processus est en possession de la
ressource.
Une possibilité de garantir l’exclusion mutuelle est de masquer les interruptions (empêcher le
processeur de gérer les interruptions) : l’interruption horloge temps réel n’étant plus traitée, ce qui peut
Chapitre 3 : Gestion du parallélisme, communication et synchronisation entre processus
entraîner un réamorçage du système dans le cas de non terminaison d’un processus, (code erroné, calcul très
long sans aucune entrée/sortie).
Exemple:
Par exemple, si deux tâches peuvent accéder à une imprimante et qu'aucune précaution n'est prise, il y a
risque de collision. Supposons la tâche A qui imprime "BONJOUR CR LF", la tâche B qui imprime
"BONSOIR CR LF". Le scheduler fonctionne en temps partagé, ou basé sur la priorité, les deux tâches ayant
la même priorité. Le temps d'allocation est celui de la préparation d'envoi d'un caractère plus l'envoi d'un
caractère. Le résultat de l'impression sera :
BBOONNJSOOUIRR CR LF
(ligne blanche : action du deuxième CR LF)
(ligne disponible pour une nouvelle impression).
C'est à dire un listing incompréhensible résultat des deux impressions des deux tâches.
7 Section Critique :
Il est important par exemple qu’un processus puisse réserver l’imprimante, puis lui envoyer un texte, sans
qu’un autre processus interagisse en même temps avec l’imprimante.
Donc, avant l’impression, le processus effectue l’appel RéserverAccèsExclusif (lock) afin de réserver un
accès exclusif à l’imprimante. Après l’impression du texte, il effectuera l’appel LibérerAccèsExclusif
(unlock) pour libérer l’accès à l’imprimante.
De même, si deux processus se partagent la même fenêtre d’affichage, il faut éviter que leurs sorties écran
soient mêlées.
L’accès à des ressources qui ne peuvent être simultanément utilisées par plusieurs processus est protégé par
les appels lock (réservation) et unlock (libération). Ces appels sont également réalisés à l’aide d’un
sémaphore.
- initialiser le Sémaphore à 1 ;
lock : Si le Sémaphore > 0 Si le sémaphore ≤ 0, le processus se suspend. Le
alors décrémente(Sémaphore) ; processus continue lorsque le sémaphore est
sinon suspendreProcessus(Sémaphore) ; positif > 0. Dans ce cas, le sémaphore est
décrémenté. L’appel lock a un effet similaire à
l’appel Attente.
unlock : incrémente(Sémaphore) ; Le sémaphore est incrémenté. Un processus
processus := suspendu est éventuellement réactivé. L’appel
processusSuspendu(Sémaphore) ; unlock a un effet similaire à l’appel Signal.
Si processus <> NIL
alors réactiveProcessus(processus) ;
décrémente(Sémaphore) ;
8 Modèles d’exécution synchrone et asynchrone:
Il existe deux modèles d’exécution de ces systèmes de contrôle-commande : l’exécution dite
synchrone et l’exécution asynchrone.
Soit une application, constituée d’un ensemble de tâches pour gérer le procédé, intègre en particulier
les deux tâches suivantes :
– Tâche de lecture des données entrées par l’opérateur à l’aide d’un clavier, appelée «Lecture_consigne».
L’intervention humaine fait que cette tâche peut être longue.
– Tâche d’alarme qui se déclenche sur un événement d’alerte correspondant au dépassement d’un paramètre
critique, appelée «Alarme». Celle-ci doit s’exécuter au plus vite pour éviter l’endommagement du procédé.
Dans le modèle d’exécution synchrone , la perception de l’occurrence de tout événement par le
système est différée du temps d’exécution de la tâche en cours. La prise en compte d’un signal d’alerte n’est
effective que lors de la fin de la tâche «Lecture_consigne». (Figure 3.7)
L’occurrence des événements externes a donc été artificiellement synchronisée avec le système
informatique, d’où le nom d’exécution synchrone.
Chapitre 3 : Gestion du parallélisme, communication et synchronisation entre processus
Figure 3.7 – Modèle d’exécution synchrone d’une application de contrôle-commande.
Dans le modèle d’exécution asynchrone, l’occurrence de tout événement est immédiatement prise en
compte par le système pour tenir compte de l’urgence ou de l’importance. La prise en compte d’un signal
d’alerte est immédiate sans attendre la fin de la tâche «Lecture_consigne». (Figure 3.8)
L’occurrence des événements externes n’est pas synchronisée avec le système informatique, d’où le
nom d’exécution asynchrone.
Dans ce contexte, nous avons des tâches qui sont interruptibles ou préemptibles.
Figure 3.8 – Modèle d’exécution asynchrone d’une application de contrôle-commande.
9 Le Sémaphore : (on peut rencontrer (P pour Wait) (V pour Signal))
Un sémaphore est un objet, peut être vu comme un verrou, que les processus utilisent à l’aide de deux
opérations :
- opération P (PRENDRE) : c’est une demande de ticket, le processus demandeur est bloqué jusqu’à sa
disponibilité ;
- opération V (VENDRE) : signale la disponibilité d’un ticket ; ainsi un processus en attente est choisi et
réveillé.
Si le sémaphore est libre, il devient pris.
Par contre s’il est déjà pris, le processus voulant le prendre passe dans l’état bloqué jusqu’à ce qu’il
lui soit possible de prendre le sémaphore, donc placer le numéro du processus dans la file d’attente du
sémaphore.
Un sémaphore est constitué de l’association d’un compteur à valeurs entières (valeur du
sémaphore=nombre de copie de la clé) et d’une file d’attente. (Figure 3.9)
Chapitre 3 : Gestion du parallélisme, communication et synchronisation entre processus
Figure 3.9 – Caractérisation d’un sémaphore binaire.
10 Utilisation des sémaphores :
Les sémaphores sont utilisés pour la synchronisation ou pour l’accès d’une ressource partageable.
Exemple 1 : accès simultané à l’imprimante par 2 tâches.
Tâche 1 : veut imprimer le texte : ‘je suis la tâche #1’
Tâche 2 : veut imprimer le texte : ‘je suis la tâche #2’
Si les deux tâches envoient les caractères en même temps, on obtient un résultat incompréhensible :
‘jjee susuisis llaa tactachhee ##12’
Solution: utiliser un sémaphore binaire initialisé à 1, avec la règle d’utilisation suivante : pour accéder à
l’imprimante chaque tâche doit obtenir le sémaphore de la ressource. (Figure 3.10)
Figure 3.10 – Utilisation d’un sémaphore binaire par deux tâches.
Exemple 2 : une tâche peut accéder à une structure de données par l’opération prendre du sémaphore
associé, si une autre tâche libère accidentellement ce sémaphore ceci provoque la mise en état prêt de la
tâche en attente du sémaphore qui se trouve libre à accéder aux mêmes données, ceci provoque la destruction
des données.
Le noyau TR (ou exécutif) crée un sémaphore en lui associe un Block de Contrôle de Sémaphore (SBC),
un ID (nom), une valeur (binaire ou entière) et une file de tâches en attente de sémaphore . (Figure 3.11)
Chapitre 3 : Gestion du parallélisme, communication et synchronisation entre processus
Figure 3.11 – Implémentation logicielle d’un sémaphore.
Les tâches en attente peuvent être traitées par FIFO ou par priorité.
11 Sémaphore à compte :
Il utilise un compteur et peut être pris plusieurs fois en même temps. (Figure 3.12)
Figure 3.12 – Implémentation logicielle d’un sémaphore à compte.
Tant que la valeur du compteur n’est pas nulle, une tâche peut prendre ce sémaphore.
12 Sémaphore d’exclusion mutuelle (mutex) :
Il initialisé à 0 : ressource libre. (Figure 3.13)
Figure 3.13 – Implémentation logicielle d’un mutex.
Chapitre 3 : Gestion du parallélisme, communication et synchronisation entre processus
13 Opérations sur les sémaphore :
Les principales opérations effectuées sur un sémaphores sont :
créer et supprimer un sémaphore,
prendre et vendre (acquérir ou libérer) un sémaphore,
effacer la file d’attente du sémaphore,
donner les informations sur le sémaphore.
Table 6.1: Opérations de création et suppression d’un sémaphore.
Operation Description
Create Créer un sémaphore
Delete supprimer un sémaphore
Prendre prendre un sémaphore
Vendre Vendre (libérer) un sémaphore
On peut utiliser: take et give , sm_p et sm_v , pend et post , ou lock
et unlock (réservation/libération.
Sem binaire: spécifier l’état initial (and the task-waiting order).
Sem à compte: spécifier la valeur initiale du compteur (ansd the task-waiting order).
Remarque: le mutex n’est libéré (vendre) que par la tâche qui la pris précédemment,
14 Accès aux ressources partageables :
Un sémaphore peut être utilisé pour la gestion d’une ressource. (Figure 3.14)
Figure 3.14 – Sémaphore binaire utilisé pour ressource partageable.
Le sémaphore est initialisé à 1 (ressource libre). Pour accéder à cette ressource, la tâche doit utiliser Prendre.
Exemple : structure de données partageable sur mémoire,
tAccessTask ()
{
:
Acquire binary semaphore token
Read or write to shared resource
Release binary semaphore token
:
}
Pour éviter toute erreur de libération accidentelle du sémaphore, on utilise de préférence un mutex.
15 Sémaphore Binaire:
Il ne peut prendre que deux valeurs : 1 ou 0. (Figure 3.15)
Chapitre 3 : Gestion du parallélisme, communication et synchronisation entre processus
Figure 3.15 – Sémaphore binaire : état et appel.
Soit un sémaphore S qui consiste en un entier S.val, et une file d’attente d’identificateurs de
processus S.file.
Procédure Prendre(S: in out sémaphore) - in pour S.val et out pour S.file.
Début
Masquer les interruptions -- La procédure prendre ne doit pas être interrompue
Si S.val=0 alors
Ajouter le n° de processus à S.file
Démasquer les interruptions
Passer dans l’état bloqué et appeler le dispatcher
Sinon
S.val ←0
Démasquer les interruptions
FinSi
Fin
Procédure Vendre(S:in out sémaphore)
Début
Masquer les interruptions
Si il existe un processus dans S.file alors
Enlever un processus de la file
Mettre ce processus dans l’état prêt
Sinon
S.val←1
FinSi
Démasquer les interruptions
Appel au dispatcher
Fin
A l’intérieur des primitives Prendre et Vendre, les interruptions sont masquées afin de les rendre non
préemptives.
V:
Compteur = compteur + 1
Si compteur <= 0
sortir une tâche de la file d'attente (FIFO)
– Lorsqu'une tâche à effectuée le V, le choix parmi les tâches en attente peut s'effectuer avec
les mêmes critères que pour l'ordonnancement
– Mécanisme qui peut être étendu à plusieurs ressources:
● Seule la valeur d'initialisation du compteur change
P:
Compteur = compteur – 1
Si compteur < 0
Mettre la tâche en file d'attente (FIFO)
Sinon accorder la ressource
– Compteur est initialisé à 1
– Si plusieurs tâches requiers le P (déjà à 0) constitution
de la file d'attente
– Une tâche qui acquiers la ressource « passe le P »
16 Gestion de synchronisation par sémaphores:
Synchronisation par Wait et Signal : (attente/signale) : rôle : Pour attendre un événement avant d’exécuter un
calcul.
Chapitre 3 : Gestion du parallélisme, communication et synchronisation entre processus
Deux tâches peuvent utiliser un sem binaire pour synchroniser leurs exécutions. Dans ce cas le sémaphore est
initialisé par 0 (non disponible), la tâche plus prioritaire tWaitTask s’exécute en premier lieu, à un certain
moment elle exécute prendre, ce qui la bloque (valeur = 0), la tâche moins prioritaire tSignalTask aura une
chance d’être exécuté, à un certain moment cette dernière libère le sémaphore (valeur = 1) et tWaitTask se
trouve relancée pour continuer son exécution.
Le code de ce scénario est le suivant :
tWaitTask ( )
{
:
Prendre(Sem_Bin_Res)
:
}
tSignalTask ( )
{
:
Vendre(Sem_Bin_Res)
:
}
Puisque tWaitTask est plus prioritaire elle préempte la tâche tSignalTask dès que le sémaphore sera libéré.
La même procédure est valables pour plusieurs tâches. (Figure 3.16)
Figure 3.16 – Synchronisation par sémaphore binaire.
17 Consommateur/producteur :
Le sémaphore peut être utilisé pour le problème de la synchronisation de processus , comme celui du
producteur/consommateur : un processus produit des données et les stocke dans une zone tampon, de taille
bornée. Un second processus consomme ces données (Figure 3.17). Le problème est de faire en sorte que le
producteur se bloque tant que le tampon est plein, et que le consommateur se bloque lorsque le tampon est
vide.
Tâche qui Tampon de Tâche qui
produit des données consomme les
données (zone de données
stockage)
Figure 3.17 – Description schématique du problème producteur/consommateur.
Un exemple concret est celui où on utilise un buffer circulaire, muni de deux pointeurs :
- put_ptr : pointeur qui donne l’adresse du prochain caractère à écrire,
- get_ptr : pointeur qui donne l’adresse du prochain caractère à lire,
En plus, le compteur des cases libres et la taille du buffer sont donnés. (Figure 3.18)
Chapitre 3 : Gestion du parallélisme, communication et synchronisation entre processus
Tâche Tâche
"Ecriture" "Lectutre"
Producteur Consommateur
Figure 3.18 – Utilisation d’un tampon circulaire pour le problème producteur/consommateur.
18 Solution du problème C/P par sémaphores :
On crée trois sémaphores : sem_data_disp (Plein), sem_espace_libre (Libre) et sem_update .
dont la valeur sem_res.count est le nombre des cases libres du buffer. Il est initialisé alors par la taille du
buffer. (Figure 3.19)
Sémaphore : Sémaphore :
disponibilité disponibilité
de l’espace des données
(Libre)
initialisation
Figure 3.19 – Utilisation des sémaphores pour le problème du producteur/consommateur.
19 Gestion de l’exclusion mutuelle par sémaphore:
Souvent appelé mutex (mutual exclusion) lorsqu’il est utilisé pour assurer l’exclusion mutuelle,
Il suffit en effet d’initialiser le sémaphore à 1 et d’encadrer chaque région critique par les deux
opérations PRENDRE() et VENDRE(). Nous avons alors :
Prendre(SEM) - Vendre(SEM) = nbre de processus en section critique
La figure 3.20 présente l’exemple de partage en exclusion mutuelle par sémaphore d’une ressource
partageable non réentrante (critique) entre 3 processus.
Porecessus Porecessus Porecessus
P1 P2 P3
Ressource
actif actif actif Variable
libre
Sémaphore
P()
0
En attente P() -1
occupée
En attente P() par P1
-2
V()
-1
occupée
V() par P3
0
occupée
V() par P2
1
Figure 3.20 – Gestion de l’exclusion mutuelle par sémaphores.
Chapitre 3 : Gestion du parallélisme, communication et synchronisation entre processus
20 Capacité d’une ressource : nombre d’accès simultanés (n est la capacité de la ressource).
Un moniteur temps réel est constitué d’un ensemble de fonctions de gestions des différentes ressources du
système offrant des services sous la forme de primitives. Il doit répondre aux deux objectifs suivants :
- satisfaire les critères temps réel ;
- faciliter la tâche du programmeur.
Pour évaluer l’intérêt que peut apporter un moniteur temps réel, examinant l’exemple suivant : soit un
programme effectuant un traitement, à un point donné de son exécution, on suppose que la suite de ce
traitement est conditionnée par l’arrivée d’une interruption qui entraîne, après son réarmement, la fin du
programme.
L’exécution d’un nouveau programme ne peut s’effectuer qu’après la fin du premier. On constate que la
phase d’attente est inutile.
Programme
d’interruption
attente
Processus P1
Traitement 1 interruption Traitement 2
Processus P2
t2
t1
Figure 3.21 – Gestion de processus sur un système multitâche temps réel.
On constate que l’arrivée de l’interruption entraîne l’abandon provisoire du programme en cours, ce qui
caractérise un système temps réel. (Figure 3.21)
21 Les primitives temps réel:
Les primitives sont des séquences programmées grâce auxquelles l’utilisateur peut demander au
moniteur l’exécution de fonctions déterminées, comme la gestion des ressources et des entrées/sorties.
Le terme ‘primitive’ a été choisi pour qualifier les fonctions de base d’un moniteur temps réel.
On distingue trois types de primitives, celles de signalisation, d’exclusion mutuelle et de
synchronisation.
22 La technique du temps partagé (time sharing):
Pour permettre à l’utilisateur d’intervenir d’une manière asynchrone, il faut priver un processus long
du processeur et céder ce dernier toutes les x millisecondes à un autre processus plus court, ceci afin de
minimiser le temps de réponse pour l’utilisateur.
