Chapitre 1

NOTION DE PARALLELISME, DE COOPERATION ET DE COMPETITION

1. Introduction aux S.E

Un S.E est un ensemble de programmes qui coopèrent à la gestion des ressources de la
machine (ordinateur).
Les principaux objectifs d’un S.E sont :
 Gestionnaire de ressource : Le S.E permet l’ordonnancement et le contrôle de
l’allocation des processeurs, des mémoires et des périphériques d’E/S entre les
différents programmes qui y font appel.
 Présenter une machine virtuelle à l’utilisateur : Son rôle est de masquer des
éléments fastidieux liés aux matériel comme les interruptions, les horloges, la
gestion de la mémoire, la gestion de processus, …
2. Processus : La notion de processus constitue un modèle simple et efficace pour
représenter l‘exécution concurrente de tâches au sein d’un système d’exploitation
multitâches.
A. Définition : Un processus représente l’exécution d’un programme comportant des
instructions et des séquences. C’est une entité dynamique (active) créée à un instant
donné, qui disparaît en général au bout d’un temps fini.
NB : différence entre processus et programme : le programme est une description
statique ; le processus est une activité dynamique (il y a un début, un déroulement et
une fin, il a un état qui évolue au cours du temps).
 Exemple de processus :
- Copier un fichier sur disque
- Impression la fiche de paie
B. États d’un processus : Les processus passent par des états discrets différents. On dit
qu’un processus est :
- Élu (en Exécution) : si le processus est en cours d’exécution.
- Prêt : si le processus dispose de toutes les ressources nécessaires à son
exécution à l’exception du processeur.
- Bloqué : si le processus attend qu’un événement se produit pour progresser.
Les transitions entre ces trois états sont matérialisées par l’automate suivant :

Nouveau
Terminé
création
2 fin
Prêt Élu

1
4 3
Bloqué

États d’un processus

SYSTEME D’EXPLOITATION 2 DR. KHELDOUN

 La signification des quatre transitions est la suivante.
1. Le processus a épuisé le quantum de temps qui lui a été attribué.
L’ordonnanceur élit un autre processus parmi les processus prêts,
2. L’ordonnanceur élit ce processus parmi les processus prêts,
3. Blocage du processus élu dans l’attente d’un évènement (E/S ou autre)
4. Réveil du processus bloqué après disponibilité de l’événement bloquant
(Fin E/S, etc…)
NB : Sous UNIX, il y’a un autre état du processus appelé état « zombie ». En effet, un
processus zombie est un processus qui s’est terminé mais dont les ressources n’ont pas
encore été libérées. Il est de la responsabilité du processus père de libérer les ressources
ocupées par ses fils zombies mais il faut que le fils l’avertisse qu’il a terminé. Un
processus zombie est signalé par la mention <defunct>.

Père

Fils
Fork()

Exit(1)

État zombie
du fils

C. Processus dans Unix :

- Un processus est identifié par un numéro PID,
- La commande ps donne la liste des processus en cours d’exécution,
- La commande fork() crée un nouveau processus,
- getpid() : obtenir le numéro du processus courant.
- getuid() : obtenir le numéro d’usager auquel appartient le processus,
- kill(PID) : tuer un processus spécifié par PID.
- sleep(n) : se bloquer pendant n secondes.
- exit() : terminaison d’un processus.
- wait() : mise en sommeil sur la terminaison d’un fils.
NB : Lors du démarrage de système Unix, deux processus sont crées :
- Swapper(PID = 0) qui gère la mémoire,
- Init(PID = 1) qui crée tous les autres processus.

SYSTEME D’EXPLOITATION 2 DR. KHELDOUN

 D. Relation entre processus : Dans un système, plusieurs processus peuvent se dérouler
simultanément. Ces processus résultent de l’exécution de programmes. Durant leur
évolution, les processus d’un système interagissent les uns avec les autres. Selon que
les processus se connaissent mutuellement ou pas, ces interactions en deux types qui
sont : Coopération / Compétition.
1. Compétition : C’est la situation dans laquelle plusieurs processus doivent
utiliser simultanément une ressource à accès exclusif (ressource ne pouvant
être utilisée que par un seul processus à la fois (ressources critiques)).
Exemples :
- Processeur (cas du pseudo‐parallélisme)
- Imprimante
 Une solution possible (mais non la seule) : faire attendre les processus demandeurs
jusqu’à ce que l’occupant actuel ait fini (premier arriver, premier servi).
2. Coopération : C’est la situation dans laquelle plusieurs processus collaborent
à une tâche commune et doivent synchroniser pour réaliser cette tâche.
Un processus est dit coopératif s’il peut affecter les autres processus en cours
d’exécution dans le système ou être affecté par eux.
Exemples :
- P1 produit un fichier, p2 imprime le fichier,
- P1 met à jour un fichier, p2 consulte le fichier,
NB : La synchronisation se ramène au cas suivant : un processus doit attendre
qu’un autre processus ait franchi un certain point de son exécution.
Remarque : Notons que, pour les deux types de relations (compétition ou
coopération), on doit faire attendre un processus. Comment réaliser cette
attente ?
- Solution 1 : attente active
P1 P2
while (resource occupée) ressource occupée = true;
{} utiliser resource;
ressource occupée = true; ressource occupée = false ;

Inconvénient : l’attente active monopolise le processeur et donc dégrade la

performance globale de la machine.
- Solution 2 : blocage du processus
On définit un nouvel état pour les processus, l’état bloqué. L’exécution d’un
processus bloqué est arrêtée, jusqu’à son réveil explicite par un autre processus ou
par le système. blocage

actif bloqué
réveil
…
sleep(5);/* se bloquer pendant 5 secondes */
…

SYSTEME D’EXPLOITATION 2 DR. KHELDOUN

 3. Système de tâches et notion de parallélisme
A. Modèle de représentation de processus (décomposition en tâches) :
On appelle tâche une unité élémentaire de traitement ayant une cohérence logique.
Si l’exécution du processus P est constituée de l’exécution séquentielle des tâches
T1, T2, …, Tn, on écrit :
P = T1T2…Tn
A chaque tâche Ti est associé une date de début ou d’initialisation di et une date
de terminaison ou de fin fi.
Remarque1 : On parle alors de l’initialisation (lecture des paramètres d’entrée,
chargement d’information) et de la terminaison (écriture des résultats, libération des
ressources, sauvegarde d’information) d’une tâche.
Remarque2 : A toute suite de tâches T1T2…Tn élémentaires est associée une suite
d1f1d2f2…dnfn d’initialisations et de terminaisons de tâches. On appelle une telle
suite un mot de l’alphabet A = {d1, f1, d2, f2,… , dn, fn }.
Reamrque3 : L’ensemble de ces mots décrivent tous les comportements possibles du
système de tâches S, on l’appelle le langage L(S) de S.
Exemple :
Soit la tâche T correspondant à l’instruction N := N + 1 ;
En utilisant des instructions du langage machine opérant sur un registre R, il est
possible de décomposer la tâche T en trois tâches plus élémentaires :
P = T1T2T3 et A = d1f1d2f2d3f3 Où :
- T1 correspond à l’instruction LOAD R, N qui charge la valeur de N dans le
registre R.
- T2 correspond à l’instruction ADD R, 1 qui incrémente le registre R.
- T3 correspond à l’instruction STORE R, N qui transfert la valeur de R dans N.
B. Parallèlisation de tâches dans un système de tâches :
Pour augmenter le degré de multiprogrammation, donc le taux d’utilisation de l’UC,
on peut exécuter en parallèle certaines tâches d’un processus séquentiel. Pour cela,
on introduit la relation de précédence "<" sur un ensemble E de tâches élémentaires.
 Définition : Une relation de précédence sur un ensemble E est une relation vérifiant :
- ∀ T ∈ E, on n'a pas T < T
- ∀ T ∈ E et ∀ T' ∈ E, on n'a pas simultanément T < T' et T' < T
- la relation < est transitive, i.e. si T, T’ et T’’ ∈ E tels que T < T’ et T’ < T’’,
alors T < T’’.
Où Ti < Tj signifie que la terminaison de Ti doit nécessairement intervenir avant
l’initialisation de Tj (en terme de date : fi < dj ).
NB : Si on a ni Ti < Tj, ni Tj < Ti, alors on dit que Ti et Tj sont exécutable en parallèle.
 Définition : On appelle système de tâches S = (E, <), un couple constitué d’un
ensemble E de tâches et d’une relation de précédence "<" sur cet ensemble.

SYSTEME D’EXPLOITATION 2 DR. KHELDOUN

 Une relation de précédence peut être représentée par un graphe orienté. Par
exemple, le système de tâches S = ((T1, T2, T3), (Ti<Tj pour i
inférieur à j)) à pour graphe (graphe de précédence) :

T1 T2 T3

On pourra faire des opérations de produit et de composition parallèle (l’union) des

graphes G1 et G2 de systèmes de tâches.
 Définition : Le produit G1*G2 est le graphe de précédence obtenu à partir des
graphes G1 et G2, en ajoutant des arêtes joignant chaque sommet terminal de G1 à
chaque sommet initial de G2. En effet, cela signifie que G1*G2 reprend les
contraintes de G1 et de G2, avec en plus la contrainte qu’aucune tâche de G2 ne peut
être initialisée avant que toutes les tâches de G1 ne soient terminées.
Exemple :
Prenons les deux graphes de précédences suivants.

T1 T1

T2 T3 T6 T7 T2 T3
* =
T4 T5
T8
T4 T5

G1 G2 T6 T7

T8

G1*G2

Question : Définir l’opération de composition parallèle (Union) sur les graphes de

précédences (G1 // G2). Montrer la par un exemple.
 Spécification dans les langages évolués :
Certains langages permettent d’exprimer la mise en séquence et en parallèle de
système de tâches.
- La mise en séquence : P1 ; P2 ; pour des programmes associés à des systèmes de
tâches S1 et S2.
- La mise en parallèle : parbegin P1 ; P2 ; parend ;

SYSTEME D’EXPLOITATION 2 DR. KHELDOUN

 Exemple : soit le programme suivant :

debut
parbegin
lire a ; lire b ;
parend
parbegin
c  a * a ; d  b * b;
parend
ec+d;
fin

 Conditions de Bernstein :
Soit I une instruction d’un programme, on dénote par :
- R(I) : l’ensemble des variables de l’instruction I qui ne changent pas par
l’exécution de l’instruction I.
- W(I): l’ensemble des variables de l’instruction I qui sont mises à jour par
l’instruction I.
On dira que deux instructions I1 et I2 peuvent s’exécuter en parallèle si les
conditions suivantes sont satisfaites :
 R(I1)∩ W(I2) = Ø
 W(I1)∩ R(I2) = Ø
 W(I1)∩ W(I2) = Ø
Exemple : soit le programme suivant :
Début lire(a) ; lire(b) ; ca+b ; écrire(c) ; Fin.
L’instruction lire(b)ne peut s’exécuter en parallèle avec ca+b car :
W(lire(b))∩ R(ca+b) = {b}
C. Parallélisme maximal :
Définition 1: Soit S = (E, <) un système de tâches. T1 et T2 sont dites non
interférentes vis‐à‐vis de S si :
- Ou bien T1 est un prédécesseur ou successeur de T2,
- Ou bien R(T1)∩ W(T2)= W(T1)∩ R(T2)= W(T1)∩ W(T2)= Ø
(conditions de Bernstein)
Définition 2 : Soit S = (E, <) un système de tâches. Si les tâches sont 2 à 2 non
interférentes alors il est déterminé.
Définition 3 : Un système de tâches de parallélisme maximal est un système
déterminé dont le graphe de précédence vérifie la propriété : la suppression de
tout arc (T1,T2) du graphe G entraîne l’interférence des tâches T1 et T2.

SYSTEME D’EXPLOITATION 2 DR. KHELDOUN

 Théorème : Soit S = (E, <) un système déterminé. Il existe un unique système S’ de
parallélisme maximal équivalent à S. S’ = (E, <’) avec <’ fermeture transitive1 de la
relation : R = {(T1, T2)| T1< T2 et (R(T1)∩ W(T2)≠Ø ou W(T1)∩ R(T2)≠Ø
ou W(T1)∩ W(T2)≠Ø) et (W(T1)≠Ø et W(T2)≠Ø)}
En résumé, si on n’a pas les conditions de Bernstein satisfaites, on crée un arc
(relation R).
L’algorithme de construction de système S’ découle du théorème :
- Construire le graphe de R,
- Éliminer tous les arcs (T1, T2) redondants, i.e. tels qu’il existe un chemin de
T1 à T2 contenant plus d’un arc.
4. Appel fork et threads :
Il existe deux façons dans le système UNIX d’exprimer le parallélisme :
- Création de processus par l’appel "fork()",
- Utilisation des "Threads".
 Solution des processus : Regardons comment l’utilisation d’un appel à la fonction
"fork()" peut être exprimée sous la forme d’un graphe de tâches :

Père Fils

debut
T0
T1

debut

pid= fork(); pid= fork();

T2

fin

Cela s’écrit en pseudo‐code :

D’où le graphe de tâches correspondant :

début
T0 ;
T1 ;
parbegin T2 ; T2 parend ;
fin ;

1
Déf : La fermeture transitive d'un graphe G= (X, A) est la relation transitive contenant la relation (X, A).
Il s’agit d’un graphe G*= (X, *) tel que : (x,y)* ssi il existe un chemin f dans G d’origine x et
d’extrémité y.

SYSTEME D’EXPLOITATION 2 DR. KHELDOUN

 Exemple :

pid=fork(); code correspondant à

if (pid==0) l’exécution du processus fils
{
printf(“je suis le fils, mon PID =
%d”, getpid());
}
else code correspondant à
{ l’exécution du processus père
printf(“je suis le père, mon PID =
%d”, getpid());
}

 Solution des Threads :

Idée : Un processus est défini par les ressources qu’il utilise et par l’emplacement
mémoire sur lequel il s’exécute. Il serait intéressant que les ressources soient
partagées et que l’on puisse y accéder d’une manière concurrentielle.
Solution : Création de plusieurs threads à l’intérieur du même processus.
Définition : Un thread est un processus léger. En effet, le concept de thread a pour
objectif de permettre à plusieurs threads d’exécution de partager un jeu de
ressources pour travailler ensemble afin d’accomplir une tâche donnée.

Remarque :
 Le terme multithreading est employé pour décrire la situation dans laquelle
plusieurs threads sont présents dans le même processus.
 L’utilisation de fork génère la poursuite de l’exécution au même emplacement
avec un code de retour différent, tandis qu’un nouveau thread commence son
exécution avec la fonction passée en paramètre.

SYSTEME D’EXPLOITATION 2 DR. KHELDOUN

 a. Manipulation des threads (utilisation de la norme POSIX) :
- Création de threads
int pthread_create(
pthread_t *tid, // sert à récupérer le TID du thread créé
const pthread_attr_t *attr,
// sert à préciser les attributs du thread `(taille de la pile, priorité….)
//attr = NULL pour les attributs par défaut
void * (*func) (void*), // est la fonction à exécuter par le thread
void *arg); //le paramètre de la fonction.
Cette fonction permet de créer un nouveau thread, elle renvoie 0 s'elle réussit, sinon
elle renvoie une valeur non nulle identifiant l'erreur qui s'est produite.

-Attente la fin d’un thread

void pthread_join( pthread_t tid,
void *status);// sert à récupérer la valeur de retour et l’état de
terminaison.
Cette fonction faire un attente d’un thread. L’équivalent de waitpid des processus
sauf qu’on doit spécifier le tid du thread à attendre.

- Terminaison de thread
void pthread_exit( void * status);
Termine l’exécution d’un thread.

- void pthread_self(void); retourne l’identifiant du Thread.

Exemple : Ce programme crée un autre thread qui va montrer qu’il partage des
variables avec le thread original, et permettre au "petit nouveau" de renvoyer un
résultat à l’original.

Thread principal pthread_create un_thread

pthread_join pthread_exit

SYSTEME D’EXPLOITATION 2 DR. KHELDOUN

 thread.c
#include <stdio.h>
#include <pthread.h>
void *fonction_de_thread(void *arg);
int val = 0;
int main (void *arg)
{ fonction exécutée par le
pthread_t un_thread; adresse de l’identifiant
thread créé
void *resultat_de_thread; du thread créé
printf("Père %d: Début (val = %d)\n", pthread_self, val);
pthread_create(&un_thread, NULL, fonction_de_thread, (void*)val);
printf("Père %d: création du thread %d\n", pthread_self, un_thread);

pthread_join(un_thread, &resultat_de_thread);
paramètre passé
printf("Père %d: Début (val = %d)\n", pthread_self, val);
return 0; à la fonction
}//fin main
identifiant du thread
attendu
void *fonction_de_thread(void *arg)
{
sleep(1);
printf(Fils %d: Début \n", pthread_self());
sleep(3);
val = 10;
printf("Fils %d: Modification (val = %d)\n", pthread_self, val);
sleep(1);
printf(Fils %d: Fin \n", pthread_self());
pthread_exit(NULL);
adresse de l’objet renvoyé au
}
thread appelant (ici NULL)

NB : compilation : gcc −D_REENTRANT thread.c −o thread −lpthread

permet l’utilisation établir un lien avec la
de code réentrant bibliothèque de threads

Résultat
Père -1208662336 : Début (val = 0)
Père -1208662336 : création du thread -1208665200
Fils -1208665200 : Début
Fils -1208665200 : Modification (val = 10)
Fils -1208665200 : Fin
Père -1208662336 : Fin (val = 10)

Remarque: Une fonction est dite réentrante si elle peut être appelée « simultanément » par
plusieurs threads et renvoyer pour chacun le résultat identique à celui en contexte mono‐thread.
Exercice : donnez un exemple de fonction non réentrante. long random (void).

SYSTEME D’EXPLOITATION 2 DR. KHELDOUN