Chapitre I : NOTION DE PARALLELISME/CONCURRENCE

L'exécution des tâches peut se faire selon trois modes fondamentaux : séquentiel, parallèle et
concurrent. Chacun de ces modes définit une manière spécifique d’organiser et d’exécuter les
instructions, influençant directement les performances et l’efficacité des systèmes informatiques.

1 Programmation Séquentielle :
La programmation séquentielle est un modèle d'exécution dans lequel les instructions d'un
programme sont exécutées une à une, dans un ordre strictement linéaire.

Autrement dit, une instruction ne commence que lorsque la précédente a été

complètement exécutée.
1.1 Caractéristiques:

 Exécution linéaire : Le programme suit un seul chemin d'exécution, et chaque instruction

est exécutée dans l'ordre où elle apparaît dans le code.
Limité aux processeurs mono-cœur : Sur un processeur à un seul cœur, la programmation
séquentielle est la seule option. Un cœur ne peut exécuter qu'une seule instruction à la fois.
 Simplicité : Le principal avantage de la programmation séquentielle est sa simplicité. Il n'y a
pas de soucis de synchronisation ou de gestion de plusieurs tâches en parallèle.

1.2 Exemple :
Un exemple classique de programmation séquentielle serait un programme qui effectue une série
de calculs ou lit des données d'un fichier, puis les traite dans un ordre bien défini.
Exemple simple
a=5
b = 10
result = a + b # Exécution séquentielle : cette instruction attend la précédente
print(result)

1.3 Limites :

 Sous-exploitation des ressources : Sur des systèmes modernes avec plusieurs cœurs, un
programme séquentiel ne tire pas parti du matériel disponible.
 Attente bloquante : Si le programme attend des ressources externes (comme l'entrée
utilisateur ou des données provenant d'un disque ou réseau), l'ordinateur peut rester inactif,
ce qui mène à une sous-exploitation du processeur.

2 Programmation Concurrente
La programmation concurrente permet à plusieurs tâches ou unités de travail (comme
les threads) de s'exécuter indépendamment, mais potentiellement en même temps, sur un seul
processeur ou plusieurs. L'idée n'est pas que les tâches s'exécutent nécessairement en parallèle,
mais qu'elles sont programmées de manière à maximiser l'utilisation du processeur pendant
qu'elles attendent des événements, ce qui permet de gérer plusieurs tâches en même temps.

2.1 Caractéristiques

 Multiples tâches en intercalé : Dans un programme concurrent, plusieurs tâches peuvent

commencer, s'exécuter et finir dans n'importe quel ordre. Elles sont gérées de façon
intercalée.
 Système mono-cœur ou multi-cœur : Sur un processeur mono-cœur, l'ordonnanceur du
système d'exploitation s'assure que les tâches s'exécutent de manière alternée. Sur un
système multi-cœur, plusieurs tâches peuvent vraiment s'exécuter en parallèle.
 Partage de ressources : Plusieurs tâches peuvent partager le même espace mémoire et les
mêmes ressources, ce qui nécessite de gérer soigneusement l'accès à ces ressources.

2.2 Exemple :
Un serveur Web qui reçoit des requêtes. Plutôt que de traiter chaque requête séquentiellement, il
peut en traiter plusieurs à la fois, même si elles sont exécutées de manière entrelacée.

2.3 Avantages et Inconvénients :

 Avantages :
o Meilleure gestion du temps d'attente : Par exemple, si un thread attend une réponse
du réseau, un autre thread peut continuer à exécuter.
o Amélioration de la réactivité des applications interactives.
 Inconvénients
o Problèmes de synchronisation : Si plusieurs threads accèdent simultanément aux
mêmes ressources, cela peut entraîner des conflits et des erreurs (corruption de
données).
o Complexité accrue : Le programmeur doit gérer la synchronisation entre les tâches, ce
qui peut rendre le code plus complexe et sujet aux erreurs.

3 Programmation Parallèle
La programmation parallèle va plus loin que la programmation concurrente. Elle concerne
spécifiquement l'exécution réellement simultanée de plusieurs tâches, ce qui nécessite un
matériel permettant l'exécution de plusieurs threads en même temps, généralement sur un
processeur multi-cœurs.

3.1 Caractéristiques

 Exécution simultanée : Contrairement à la concurrence, où les tâches sont entrelacées, la

programmation parallèle implique l'exécution simultanée de plusieurs tâches sur des
processeurs ou cœurs différents.
 Optimisation des ressources matérielles : Permet d'exploiter pleinement les architectures
multi-cœurs, en décomposant une tâche en plusieurs sous-tâches exécutées en parallèle.

3.2 Exemple :
Un programme qui calcule la somme de grandes matrices peut décomposer cette tâche en
plusieurs sous-tâches qui sont exécutées sur différents cœurs de processeur.

3.3 Avantages & Inconvénients

3.3.1 Avantages

 Performance accrue : En utilisant plusieurs cœurs, les programmes parallèles peuvent

effectuer des calculs bien plus rapidement, ce qui est particulièrement utile pour les calculs
scientifiques ou les applications de traitement de données volumineuses.
 Scalabilité : Peut facilement être adapté à un plus grand nombre de cœurs pour des gains
de performance supplémentaires.

3.3.2 Inconvénients

 Communication inter-thread : Les threads parallèles doivent souvent partager des

données. Cela nécessite des mécanismes de synchronisation, ce qui peut entraîner une
surcharge.
 Complexité : Décomposer un problème en tâches parallèles et gérer la communication entre
elles peut être complexe. De plus, tous les problèmes ne peuvent pas être parallélisés
efficacement.

4 Résumé des Différences entre Séquentielle, Concurrente et Parallèle

5 Processus

 Un processus est un programme en cours d'exécution.

 Un programme est une suite d'instructions ; c'est du texte, un code statique.
 Le processus est un concept dynamique, il représente le déroulement d'une tâche faisant
partie d'une application ou un programme quelconque.

5.1 Cycle de vie d’un processus

Lors de l’exécution d’un programme, un processus change régulièrement d’état. C’est
l’ordonnanceur qui est responsable de ces changements d’état.
 new : le processus vient d’être crée,
 ready : complètement copié en RAM, il attend que l’ordonnanceur lui donne la main sur le
processeur,
 running : le processus est en cours d’exécution sur le processeur,
 blocked : le processus est bloqué par la lecture d’une entrée (clavier, lecture fichier),
 terminated : le processus s’est terminé normalement ou le système l’a arrêté et ses
ressources ont été libérées.

6 Thread

 Un thread est un fil d’exécution de code, à l’intérieur d’un processus, et qui a la possibilité
d’être ordonnancé.
 Il s’agit d’une version allégée d’un processus.
 Processus et threads partagent certaines propriétés, mais ne peuvent en aucun cas être
inter-changés.
 Tout processus a un thread principal, depuis lequel d’autres threads peuvent être lancés.
 Les threads d’un même processus partagent le même espace d’adressage,
 Toutes les ressources du processus peuvent être accédées par tous les threads, ce qui n’est
pas le cas entre deux processus distincts.
 Chaque thread possède son propre compteur de programme (PC), un ensemble de registres,
un état, et une pile. Les piles sont placées dans l’espace
 Sur un processeur simple coeur, les threads doivent se partager le processeur.
 Nous pouvons observer qu’un seul thread est en exécution à un instant donné, et que le
passage d’un thread à un autre peut être influencé par une communication inter-thread (deux
derniers cas), ou simplement dicté par l’ordonnanceur.

6.1 Dangers liés à l’utilisation des threads

 Etant donné que les threads d’un même processus partagent le même espace d’adressage:
un thread peut facilement corrompre les données utilisées par un autre thread.
o Des outils de synchronisation permettent toutefois d’éliminer les risques de ces
corruptions.
 si un thread effectue un accès mémoire erroné fatal
o le processus entier risque de se terminer.
 Un thread est lié à un programme particulier, et ne peut donc pas être lancé par un autre
programme.
 Les processus peuvent en revanche être lancé par un autre processus, et donc être plus
aisément réutilisés.

7 Différents types d’applications concurrentes

7.1 Application multi-threaded :

 contient deux ou plusieurs threads,

 qui peuvent ou non s’exécuter en même temps,
 et qui sont utilisés pour mieux organiser et structurer l’application (meilleure modularité)
Exemples :

 Système d’exploitation multi-tâches,

 serveur Web

7.2 Application parallèle

 chaque thread s’exécute sur son propre processeur (ou coeur), dans le but de résoudre plus
rapidement un problème ou pour résoudre un problème plus gros

Exemples :

 Prévisions météorologiques,
 Simulations physiques,
 traitement graphique, etc.

7.3 Application distribuée :

 contient deux ou plusieurs processus,

 qui communiquent par l’intermédiaire d’un réseau
o délais plus longs,
 et ce pour répartir, géographiquement, des données et des traitements

Exemples :

 Serveurs de fichiers,
 accès à distance à des banques de données
Chapitre I : NOTION DE PARALLELISME/CONCURRENCE (partie 2)
3 Pourquoi paralléliser ?

 Economiser du temps : si un CPU peut exécuter les opérations arithmétiques du programme

en temps T, alors N CPU peuvent idéalement les exécuter en temps T/N.
 Les limites du séquentiel : Limites de la vitesse de transmission (transmission des données
entre les différents éléments du hardware) .
 Les limites économiques : plus cher d’augmenter la rapidité d’un processeur que de multiplier
les processeurs ou les corps.
 La parallélisation est essentielle pour le traitement de grandes quantités de données. Par
exemple, dans les systèmes de Big Data, des techniques comme le traitement en parallèle
permettent de diviser de grandes bases de données en morceaux plus petits qui peuvent être
traités simultanément sur plusieurs machines ou cœurs de processeur. (Analyse de données
massives , Simulation scientifique…)

4 L'existence de la propriété du parallélisme dans les applications

4.1 Parallélisme de données:
la même opération est réalisée par plusieurs processeurs sur des données différentes:
exemple : addition de deux matrices;

4.2 Parallélisme de contrôle:

des opérations différentes sont réalisées simultanément.
indépendance /dépendance du flot (architecture pipeline: dupliquer les unités de traitements).

5 Classification des machines parallèles

Pour caractériser les différentes architectures de machines, la classification la plus connue et la
plus employée est celle de Michael J Flynn.
Elle s'appuie sur la notion de flot, un ensemble ordonné d'éléments de même nature.
Les instructions d'un programme et les données à traiter sont contenues dans un ou plusieurs
flots.
L'existence d'un ou plusieurs flots de chaque type définit quatre catégories de machines.

 les machines SISD ( Single Instruction Stream, Single Data Stream) ;

 les machines SIMD ( –Single Instruction Stream, Multiple Data Stream) ;
 les machines MISD ( –Multiple Instructions Stream, Single Data Stream) ;
 les machines MIMD ( –Multiple Instructions Stream, Multiple Data Stream).
Exemples de processeurs utilisant l'architecture NUMA
Intel Xeon Scalable (Série Platinum, Gold, Silver) :
Utilisé dans les serveurs multiprocesseurs, chaque processeur dispose de sa propre mémoire
locale (RAM) et peut accéder à la mémoire des autres processeurs, mais avec une latence plus
élevée.
Exemple : Intel Xeon Platinum 8280 (28 cœurs, 56 threads).
AMD EPYC (Série 7002 et 7003) :
Destiné aux serveurs et stations de travail, les processeurs EPYC utilisent NUMA pour gérer
l'accès à la mémoire locale et distante entre plusieurs processeurs.
Exemple : AMD EPYC 7742 (64 cœurs, 128 threads).

Intel Core i9 (avec plusieurs sockets) :

Bien que principalement pour des ordinateurs de bureau, lorsque ces processeurs sont installés
dans des systèmes multiprocesseurs, NUMA optimise l'accès à la mémoire locale pour chaque
processeur.
Exemple : Intel Core i9-10980XE (18 cœurs, 36 threads).

Qualcomm Centriq 2400 (ARM) :

Utilisé dans des serveurs haute performance, l'architecture NUMA est utilisée pour optimiser les
performances dans des environnements de cloud computing.
Exemple : Qualcomm Centriq 2460 (48 cœurs).

Chapitre II : SYNCHRONISATION DES PROCESSUS (Partie 1)

Introduction
Dans un système d’exploitation récent, les processus s’exécutent en parallèle ou en pseudo-
parallèle. De plus, ils partagent des ressources (imprimante, processeur, etc.) et des données.
Afin de bien gérer la compétition et la coopération des processus, il est important de mettre en
place des mécanismes de synchronisation et de communication.

Synchronisation des processus

Afin de bien utiliser les ressources partagées (généralement rares), il est important de bien
contrôler l’accès à ces ressources. La synchronisation consiste à mettre des conditions d’arrêt
avant l’accès aux ressources critiques dans les programmes.
Problème de la synchronisation
Le partage de ressources sans précautions particulières peut conduire à des résultats
incohérents et indésirables, notamment dans le cas d’un accès concurrent à ces ressources.

Exemple
Considérons deux clients A et B d’une banque qui partagent un même compte. Le solde du
compte est 10000 DA. Supposons qu’en même temps, les deux clients lancent chacun une
opération. Le client A demande un retrait de 10000 DA alors que le client B veut faire un dépôt de
1000 DA.
Les deux processus exécutant les requêtes des clients partagent la variable solde.
Terminologies relatives à la synchronisation
La compréhension de la synchronisation nécessite de connaître quelques terminologies, à savoir:

 Ressource critique (RC): c’est une entité dont l’utilisation ne doit être faite que par un seul
processus à la fois.
 Section critique (SC): la section critique d’un programme donné, est une séquence
d’actions de ce programme dont l’exécution est gérée en exclusion mutuelle.
 Exclusion mutuelle (EM): il s’agit d’une condition de fonctionnement qui assure à un
processus l’usage exclusif d’une ressource critique.

Comment assurer l’exclusion mutuelle?

Hypothèses de base sur les processus

 H1: les vitesses des processus sont quelconques;

 H2: les priorités et les droits des processus sont quelconques;
 H3: Tout processus sort de la section critique au bout d’un temps fini (pas de panne, ni de
blocage en SC);

Critères nécessaires pour des solutions valides

 C1) Exclusion mutuelle: à un instant Ti un seul processus en SC pour utiliser une ressource
critique;
 C2) Progression (Pas d’nterblocage): un processus en dehors de sa SC ne doit pas
empêcher les autres processus d’accéder à leur SC;
 C3) Attente bornée (pas de famine): Tout processus doit accéder à sa section critique au
bout d’un temps borné.

Structure d’un programme avec une section critique

Approches de synchronisation
On trouve plusieurs approches de synchronisation des processus. Le schéma ci-dessous illustre
une classification de ces approches :

Solutions logicielles par attente active

Première tentative
Le principe de la solution présentée repose sur une variable booléenne appelée occupe qui
indique si l’une des tâches s’exécute en section critique. Initialement, occupe est positionné
à faux.

Malheureusement notre solution est incorrecte car on peut imaginer le scénario suivant.
Les deux tâches peuvent se retrouver simultanément en section critique. Il n’y a donc pas
d’exclusion mutuelle.

Deuxième tentative
La deuxième tentative, utilise une variable entière tour qui indique l’identité de la tâche qui a
l’autorisation d’accéder à la section critique. Ainsi Ti peut accéder à la section critique seulement
si tour est égale à i.

 Cette solution garantit qu’une seule tâche peut se trouver en section critique.
 Cependant elle ne satisfait pas la 2ème contrainte.
o Les tâches doivent exécuter leur section critique en alternance.
o Une tâche peut donc attendre pour pénétrer en section critique alors que celle auquel le
tour lui revient ne l’utilise pas et n’a peut-être plus l’intention de l’utiliser.
 De plus, si une des deux tâches disparaît, l’autre attendra indéfiniment.

Troisième tentative
Le problème avec la solution précédente est lié au fait qu’elle tient compte de l’identité de la
tâche qui peut accéder à la section critique sans considérer son état. Pour remédier au problème,
remplaçons la variable tour de la solution précédente par un vecteur de booléen etat initialisé à
faux. Ainsi etat[i] est vrai si Ti est en section critique.
Malheureusement la nouvelle solution, ne garantit plus l’exclusion mutuelle comme le montre la
séquence qui suit.
Chapitre II : SYNCHRONISATION DES PROCESSUS (Partie II)
Quatrième tentative
Le problème avec la troisième tentative provient du fait que l’une des tâches peut vérifier l’état de
l’autre avant que cette dernière ait l’opportunité de modifier son état. Corrigeons ce problème en
déplaçant l’énoncé d’affectation. Ainsi etat[i] est vrai si Ti désire accéder à la section critique.

L’exclusion mutuelle est à présent garantie mais un autre problème surgit.

 Si T0 met etat[0] à vrai et juste après T1 met etat[1] à vrai, alors T0 et T1 bouclent
indéfiniment.
 Si les deux tâches progressent simultanément dans leur prélude elles se bloquent
mutuellement.
 Chacune croit que l’autre est engagée dans sa section critique. Ceci provient du fait que Ti
indique son intention d’entrer en section critique sans connaître l’intention de l’autre.

Cinquième tentative
Modifions la précédente tentative de manière à obliger une tâche à renoncer temporairement à
son désir de pénétrer en section critique si l’autre tâche désire elle aussi y entrer.
Bien que l’exclusion mutuelle soit garantie, un interblocage est possible si les
deux tâches exécutent leur prélude en alternance.
Cette séquence d’instructions a très peu de chance de se produire en réalité.
Elle nécessite en effet, des conditions difficiles à réaliser.
Algorithme de Dekker
L’algorithme de Dekker est une solution qui combine nos deuxième et cinquième tentatives.
L’algorithme est basé sur la 5 ème tentative mais règle le problème d’interblocage en donnant
priorité à l’une des deux tâches. La variable tour de la deuxième tentative impose l’ordre dans
lequel les tâches accèdent à la section critique. En cas de conflit, l’une des tâches se résigne
temporairement pour donner l’accès à l’autre tâche.

Exercice

 montrer que l’exclusion mutuelle est préservée ?

 Montrer qu’il n’y pas une situation d’inter-blocage ?

Preuve de l’exclusion mutuelle

 Supposons que T0 et T1 sont en section critique en même temps.

o Cela impliquerait que etat[0]=vrai et etat[1]=vraie.
o Or, une tâche ne peut entrer en section critique que si l’autre n’est pas dans sa boucle
externe.
o Ainsi, l’une des tâches est entrée avant l’autre.
 Cas où T0 entre en premier :
o T0 a trouvé etat[1]=faux.
o Seule T1 peut modifier etat[1].
o T1 ne vérifie etat[0] que si etat[1] est à vrai.

 Dans sa boucle interne, où elle attend que 𝑇0 exécute son postlude pour sortir.
o Donc, T1 est soit :

bloquée dans son prélude tant que 𝑇0 n’a pas terminé.

 Dans sa section non-critique, et si elle veut entrer en section critique, elle sera

 Cas où T1 entre en premier :

Un raisonnement similaire s’applique.

Conclusion : L’exclusion mutuelle est garantie.

Preuve de l'absence d’interblocage

 Cas 1 : Une seule tâche veut entrer

o Elle accède directement à la section critique, indépendamment de la valeur de tour.
 Cas 2 : Les deux tâches veulent entrer et tour = 0

o 𝑇0 trouve 𝑒𝑡𝑎𝑡[1]=𝑓𝑎𝑢𝑥
o Deux possibilités :

 Le même raisonnement s’applique pour 𝑇1 si 𝑡𝑜𝑢𝑟=1

 T 0 entre immédiatement en section critique.

o 𝑇0 trouve 𝑒𝑡𝑎𝑡[1]=𝑣𝑟𝑎𝑖
 𝑇0 attend dans sa boucle externe jusqu'à ce que 𝑒𝑡𝑎𝑡[1] devienne faux.
 Pendant ce temps, 𝑇1 attend dans sa boucle interne que tour = 1.
 Avant cela, 𝑇1 met 𝑒𝑡𝑎𝑡[1]=𝑓𝑎𝑢𝑥, permettant à 𝑇0 d’entrer en section critique.

o Le raisonnement est symétrique : 𝑇1 entre avant 𝑇0 .

 Cas où tour = 1

Conclusion : Aucune situation où les deux tâches resteraient bloquées

indéfiniment. Pas d’interblocage.
Algorithme de Peterson
Preuve de l’exclusion mutuelle

 Lorsque la tâche Ti veut accéder à la section critique, elle positionne intention[i] à vrai. La
variable tour départage les deux tâches si celles-ci désirent accéder en même temps à la
section critique.
 Pour vérifier que l’exclusion mutuelle est conservée, supposons que T0 et T1 sont toutes les
deux dans leurs sections critiques. Dans ce cas, intention[i] = vrai pour i = 0 et 1. Mais ces
tâches n’ont pas pu sortir de leurs boucles en même temps car tour ne peut prendre
simultanément la valeur 0 et la valeur 1. L’une des tâches est donc entrée en section critique
avant l’autre.
 Supposons que c’est Ti. Ti a alors évalué la condition de sa boucle pendant que Tj exécutait
tour = i. Mais à ce moment, Tj trouve intention[i] à vrai et tour à i lorsqu’elle évalue la
condition de sa boucle. Cette condition sera évaluée à vrai car ces variables conservent leurs
valeurs tant que Ti se trouve en section critique, ce qui préserve l’exclusion mutuelle.

Preuve de l'absence d’interblocage

 Pour vérifier qu’il n’y a pas d’interblocage, remarquons qu’une tâche Ti ne peut être bloquée
dans son prélude que si elle trouve sans cesse intention[j] =vrai et tour = j.
 Si Tj ne désire pas accéder à la section critique, intention[j] est à faux et Ti ne peut pas être
bloquée. Par contre si intention[j] est à vrai, Tj doit aussi être dans sa boucle pour qu’il y
ait interblocage.
 Mais à ce moment, la variable tour, valant nécessairement 0 ou 1, favorisera l’une des deux
tâche. Il ne peut donc pas y avoir d’interblocage.

Propriété d'équité :
Pour montrer que le protocole est équitable, il suffit de montrer que si Ti est dans sa boucle
d’attente et que Tj est dans sa section critique, Ti pénétrera en section critique avant Tj si celle-ci
désire à nouveau entrer en section critique.
Lorsque Tj sort de son postlude, intention[j] est à faux et Ti peut accéder à son tour à la section
critique. Si Tj désire à nouveau entrer en section critique, elle repositionne intention[j] à vrai et
tour à i. Ainsi Tj est bloquée dans sa boucle d’attente tant que Ti n’accède pas à la section
critique.
Exercice
Soit l'algorithme suivant pour gérer l'exclusion mutuelle

 Est ce que l’exclusion mutuelle est préservée ?

 Est-ce qu’il n’y pas une situation d’inter-blocage ?

Solutions Matérielles pour l’Exclusion Mutuelle

Les solutions matérielles reposent sur des mécanismes intégrés au processeur pour garantir
l'exclusion mutuelle sans nécessiter de supervision logicielle complexe. Voici les principales
méthodes :

 Monoprocesseurs: masquage d ’interruptions;

 Multiprocesseurs: instruction indivisible, TAS

1. Masquage des interruptions

Le masquage des interruptions est une solution matérielle simple utilisée pour assurer
l’exclusion mutuelle dans les systèmes mono-processeurs. Cette technique repose sur la
capacité du processeur à désactiver temporairement les interruptions pour empêcher toute
autre tâche d’interférer avec l’exécution d’un processus en section critique.

1.1. Principe du Masquage des Interruptions

Lorsqu’un processus doit accéder à une ressource critique (une section de code qui ne doit être
exécutée que par un seul processus à la fois), il suit ces étapes :

1. Désactivation des interruptions : Avant d’entrer en section critique, le processus

désactive les interruptions système en utilisant une instruction machine spéciale
(comme CLI en assembleur x86).
2. Exécution de la section critique : Le processus effectue les opérations nécessaires sur
la ressource partagée sans risque d'interruption par un autre processus.
3. Réactivation des interruptions : Une fois la section critique terminée, le processus
réactive les interruptions ( STI en assembleur x86), permettant ainsi au système de gérer
à nouveau les interruptions normalement.
1.2 Avantages et Inconvénients
Avantages

 Simplicité : Implémentation directe, ne nécessite pas de structures de synchronisation

complexes.
 Efficacité en mono-processeur : Fonctionne bien dans un environnement à processeur
unique, car aucune autre tâche ne peut s'exécuter pendant la section critique.

Inconvénients

 Non adapté aux systèmes multiprocesseurs : Si un seul processeur masque les

interruptions, un autre processeur peut toujours accéder à la ressource partagée.
 Blocage du système : Si un processus oublie de réactiver les interruptions, le système peut
devenir inutilisable.
 Diminution de la réactivité : Les interruptions servent souvent à gérer des événements
critiques (comme le traitement des entrées/sorties), leur désactivation prolongée peut
entraîner des délais ou des pertes de données.

2. Test_and_Set(TAS)
Instruction indivisible: réalisée une seule fois par le matériel:
Test_and_Set(TAS) : instruction indivisible de consultation et de modification d’un mot mémoire.

2.1 Principe du Test-and-Set

L'instruction Test-and-Set fonctionne sur une variable binaire (souvent appelée lock). Elle vérifie
la valeur de cette variable et la met à 1 en une seule opération atomique. Cela garantit qu'aucun
autre processus ne peut modifier cette variable en même temps.
L’instruction Test and Set Lock « int TSL (int b) » exécute de manière indivisible les opérations
suivantes :

 récupère la valeur de b,
 affecte la valeur 1 à b et
 retourne l’ancienne valeur de b.
Sémantique: Si v est libre, test_and_set renvoie libre, le processus obtient le
verrou et on entre en SC avec v occupé. Si elle était déjà occupé, cela signifie
qu'un autre processus a déjà pris le verrou.
2.2 Explication :
1. Prise du verrou
o Le processus tente de prendre le verrou en appelant test_and_set(v) .
o Si v== libre , il devient occupé , et le processus entre en section critique.
o Si v== occupé , la boucle continue jusqu'à ce que le verrou soit disponible (attente
active).
2. Libération du verrou
o Une fois la section critique terminée, le processus remet v à libre , permettant à un
autre processus d'entrer.

2.3 Problèmes du Test-and-Set

Bien que cette approche soit simple et efficace, elle présente certains inconvénients :

 Attente active (busy waiting) :

Les processus en attente exécutent en boucle l'instruction test_and_set , consommant
inutilement du temps CPU.
 Risque d’inversion de priorité :
Un processus à faible priorité peut monopoliser le verrou, retardant l’exécution des processus
à plus haute priorité.
o Supposons que Deux processus H et B, tels que H est plus prioritaire que B, partagent
un objet.
o Les règles d’ordonnancement font que H est exécuté dès qu’il passe à l’état prêt.
o Pendant que H est en E/S, le processus B entre en section critique.
o Ensuite, le processus H devient prêt alors que B est toujours en section critique.
o Le processus B est alors suspendu au profit du processus H.
o H effectue une attente active et B ne peut plus être réélu (puisque H est plus prioritaire).
o B ne peut plus sortir de sa critique et H boucle indéfiniment.
Verrous et sémaphores
Les solutions au problème de l’exclusion mutuelle présentées jusqu’à présent sont basées sur
l’attente active : une tâche qui ne peut pas progresser dans sa partie prélude occupe inutilement
le processeur. Un processeur peut être utilisé d’une façon plus productive s’il n’attend pas
activement qu’une condition change d’état.

Verrou (mutex)
Un verrou (mutex) fonctionne avec un mécanisme de mise en sommeil :

 Si un processus tente d’acquérir un verrou occupé, il est mis en veille (sleep() ou état
"bloqué") par le système d’exploitation.
 Quand le verrou est libéré, le système réveille un des processus en attente.
 Les opérations d’acquisition et de libération du verrou sont atomique (indivisibles)

Aucune attente active → le processus ne gaspille pas de CPU.

Fonctionnement d’un verrou (mutex) :
Le verrou est une structure composée de deux champs:

Initialement le verrou est ouvert

Deux procédures sont définies sur les verrous

Principe d’utilisation d’un Mutex

un verrou permet de résoudre le problème de l’exclusion mutuelle à n tâches de manière simple.

 Il suffit de verrouiller un verrou v avant d’entrer en section, bloquant ainsi les autres tâches
qui accèdent à leur section critique protégée par le même verrou v.
 La sortie d’une section critique se fait en déverrouillant v, ce qui libère le verrou ou réveille
une tâche bloquée pour l’accès à sa section critique.

problèmes
Le deadlock est l'un des problèmes majeurs liés à l'utilisation de verrous.
Comment se produit le deadlock ?
Un deadlock se produit lorsque plusieurs processus ou threads attendent indéfiniment l’un l’autre
pour libérer un verrou.
Exemple classique de deadlock :

 Processus A verrouille Verrou1 et attend Verrou2.

 Processus B verrouille Verrou2 et attend Verrou1.

Résultat : Les deux processus attendent indéfiniment, ils sont bloqués (deadlock).
Solution pour éviter le deadlock :

 Ordre d'acquisition des verrous : Toujours verrouiller les verrous dans un ordre prédéfini pour
éviter les cycles d'attente.
 Timeout : Mettre un délai d'attente pour détecter un deadlock avant qu’il ne devienne
permanent.

2. Les sémaphores
Pour contrôler les accès à un objet partagé, E. W. Dijkstra (1965) suggéra l’emploi d’un nouveau
type de variables appelées sémaphores.

 Un sémaphore est un compteur entier qui désigne le nombre d’autorisations d’accès

disponibles.
 Chaque sémaphore a un nom et une valeur initiale.
 Les sémaphores sont manipulés au moyen des opérations :
o P (désigné aussi par down ou wait) et
o V (désigné aussi par up ou signal)

2.1. Opérations principales :

 L’opération P(S) décrémente la valeur du sémaphore S si cette dernière est supérieure à 0.

Sinon le processus appelant est mis en attente.
 L’opération V(S) incrémente la valeur du sémaphore S, si aucun processus n’est bloqué par
l’opération P(S). Sinon, l’un d’entre-eux sera choisi et redeviendra prêt.
 Chacune de ces deux opérations doit être implémentée comme une opération indivisible.

2.2. Types de Sémaphores :

 Un sémaphore binaire est un sémaphore dont la valeur peut prendre que deux valeurs
positives possibles : en générale 1 et 0. Fonctionne comme un mutex
 Un sémaphore de comptage : la valeur peut prendre plus de deux valeurs positives
possibles. Il est utile pour allouer une ressource parmi plusieurs exemplaires identiques : la
valeur est initialisée avec le nombre de ressources.

2.3. Réalisations logicielles :

2.4. Exclusion mutuelle au moyen de sémaphores
Pour utiliser un sémaphore comme un mutex, on suit ces étapes :

1. Initialiser le sémaphore à 1 ( mutex = 1 ) → Seul un processus peut entrer.

2. Un processus qui entre en section critique exécute P(mutex) → mutex devient 0 .
3. Les autres processus qui tentent d’entrer voient mutex == 0 et sont bloqués.
4. Quand le processus termine sa section critique, il
exécute V(mutex) → mutex repasse à 1 , permettant à un autre processus d’entrer.

Explication :

2.5. Coordination de tâches :

Les sémaphores permettent non seulement d'assurer l'exclusion mutuelle, mais aussi
de synchroniser et coordonner des tâches dans un environnement concurrent.
Ils garantissent qu'une tâche attend un certain événement avant d'exécuter son travail.
 Un processus doit attendre un autre pour continuer (ou commencer) son exécution.
o si deux tâches T 1 et T 2 exécutent respectivement les instructions travail1 et travail2, et
que travail1 doit précéder l’exécution de travail2.

Exercice :
Nous avons trois tâches et nous voulons nous assurer que Tâche 1 s’exécute avant Tâche 2, et
Tâche 2 avant Tâche 3.
écrire une solution à ce problème en utilisant les sémaphores.

2.6. Deadlock (interblocage)

Un deadlock (interblocage) se produit lorsque deux ou plusieurs processus se bloquent
mutuellement en attendant une ressource détenue par un autre, ce qui les empêche de
progresser.

Pourquoi ce code cause un Deadlock ?

1. Processus 1 prend semA et veut semB , mais semB est pris par Processus 2.
2. Processus 2 prend semB et veut semA , mais semA est pris par Processus 1.
3. Les deux Processus attendent l’un sur l’autre et restent bloqués indéfiniment.

Comment Éviter un Deadlock ?

 Toujours prendre les ressources dans le même ordre

o Si tous les processus prennent semA avant semB , aucun ne pourra bloquer l’autre.
 Utiliser un timeout sur P()
o Au lieu d’attendre indéfiniment, un processus peut abandonner après un certain temps.

Le problème des philosophes mangeurs

Description du problème
Cinq philosophes sont assis autour d’une table circulaire. Chacun alterne entre deux activités :
penser et manger. Pour manger, un philosophe a besoin de deux fourchettes, droite et gauche.
Or, il y a seulement cinq fourchettes, placées entre chaque philosophe.

Chaque philosophe suit cette routine :

 Penser (état initial)

 Prendre la fourchette à sa gauche (s’il est disponible)
 Prendre la fourchette à sa droite (s’il est disponible)
 Manger (pendant un certain temps)
 Reposer les fourchettes
 Recommencer

Solution 1

 Chaque fourchette est représentée par un sémaphore binaire (0 ou 1).

 Chaque philosophe doit acquérir deux fourchettes (les sémaphores adjacents) avant de
manger.
 Après avoir mangé, il libère ses fourchettes pour les autres.
Les problèmes possibles
Ce problème illustre plusieurs défis liés aux systèmes concurrents :

 Interblocage (deadlock)
o Si chaque philosophe prend en même temps la fourchette à sa gauche, aucun ne pourra
prendre celle de droite. Tous attendent indéfiniment.
 Famine
o Un philosophe peut ne jamais manger si les autres monopolisent les fourchettes.

Solution 2
Stratégie adoptée :

 Un philosophe ne peut manger que si ses deux voisins ne mangent pas.

 Un philosophe qui veut manger doit attendre si ses voisins mangent.
 Lorsqu’un philosophe termine de manger, il réveille ses voisins potentiellement bloqués.

variables utilisées :

 Un tableau d’états pour suivre l’état de chaque philosophe (pensant, affamé, mangeant).
 Un tableau de sémaphores pour chaque philosophe afin de contrôler individuellement leur
accès aux fourchettes.
 Un sémaphore mutex globale pour protéger l’accès aux variables partagées (états, etc.)
Conclusion
Le problème des philosophes est un exemple classique de synchronisation en programmation
concurrente, illustrant les difficultés liées à la gestion de ressources partagées de manière
équitable et sans conflit. Il met en évidence les risques d’interblocage (deadlock) et de famine .
Communication par partage de variables (I)
Introduction
L’échange d'information entre processus est appelé communication.
Cela est possible via le partage d'une variable (zone mémoire commune) accessible par les
processus désirant communiquer.
Deux schémas de communication seront présentés dans ce cours:

 le modèle Producteur/Consommateur
 le modèle Lecteur/Rédacteur.

Modèle du producteur/ consommateur

 Le problème producteur-consommateur (également connu sous le nom de problème de

tampon borné) est un exemple classique de communication inter processus.
 Deux processus cycliques, un producteur et un consommateur, qui partagent un tampon
commun de taille fixe.
 Le producteur génère successivement des données et les écrit dans le tampon.
 Le consommateur lit les données du tampon, les supprime au cours de la lecture et utilise
ces données.
 La solution du problème doit respecter la condition qu'aucune donnée ne soit perdue ou
dupliquée,
 Les données sont lues par le consommateur dans l'ordre dans lequel il est écrit par le
producteur.

Exemple:
Impression en réseau

 Contexte : Dans un bureau, plusieurs employés envoient des documents à une imprimante
en réseau.
 Problème :
o Producteur : les utilisateurs envoient des documents à imprimer.
o Consommateur : l'imprimante traite les documents un par un.
o L’imprimante ne peut pas gérer plusieurs documents en même temps.
 Solution :
o Une file d’attente (spooler d’impression) stocke les travaux d’impression.
o L’imprimante récupère les documents un par un selon leur priorité.

Réalisation du problème Producteur/consommateur par Sémaphores

 Nous supposons que la vitesses relatives des processus est quelconques, le tampon est de
taille fixe: N cases (une case = un message) et tampon vide initialement, tout message
déposé est lu une fois et une seule fois.
 Le producteur ne peut déposer un message dans le tampon s'il n'y a plus de place libre.
 Le consommateur ne peut retirer un message depuis le tampon s'il n'y en a pas.
 Le consommateur ne doit pas retirer un message que le producteur est en train de
déposer.
 Le tampon est géré comme une file circulaire ayant deux indexes: l'indexe ip pour la
production et l'indexe ic pour la consommation.

Structure de l'algorithme Producteur-Consommateur

Solution du problème Producteur/consommateur par Sémaphores

 La solution du problème au moyen des sémaphores nécessite deux sémaphores,
o un sémaphore Nvide, initialisé à N (nombre de cases vides, initialement =N),
o et un sémaphore Nplein initialisé à 0 (nombre de cases pleines, initialement = 0).
 Le schéma présente une symétrie. Le producteur génère des cases pleines pour le
consommateur. Le consommateur génère des cases vides pour le producteur.
 Le tampon est accessible en concurrence par un producteur et un consommateur simultanés.
 Nous utilisons deux index ip et ic, initialisées à 0. ip est géré entièrement et seulement par
le producteur, l'autre est géré entièrement et seulement par le consommateur.

La fonction Produire(x) est une fonction de création de messages, elle peut être une lecture de
données d'une base de donnée ou bien une fonction de lecture de valeurs physiques d'un
capteur et de les transformer en une donnée numérique par exemple ou bien tout autre fonction
de création de messages. La fonction Consommer(x) d'impression par exemple, de transfert, de
sauvegarde.

Conclusion
Le problème Producteur-Consommateur illustre un défi classique de synchronisation dans les
systèmes multitâches, où des processus concurrents partagent un tampon commun. L'utilisation
des sémaphores permet de résoudre ce problème efficacement en garantissant :

 L'exclusion mutuelle, grâce à un sémaphore mutex, pour éviter les accès concurrents au
buffer.
 La synchronisation, avec les sémaphores Nplein et Nvide, qui contrôlent respectivement la
disponibilité des éléments à consommer et des espaces libres pour produire.
Communication par partage de variables (II)
Introduction
Considérons une situation où nous avons un fichier (une base de données par exemple) partagé
entre plusieurs processus. Si un processus essaie de modifier la base, aucune autre ne doit lire
ou écrire en même temps, sinon les modifications ne lui seront pas visibles. Cependant, si un
processus lit la base, d'autres peuvent le lire en même temps. C'est précisément dans un SE que
nous appelons cette situation le problème des lecteurs-redacteurs.

Paramètres du problème:

 Un ensemble de données (fichier, base de donnée …) est partagé entre plusieurs processus.
 Une fois qu'un rédacteur est prêt, il exécute son écriture. Un seul rédacteur peut écrire à la
fois.
 Si un processus est en cours d'écriture, aucun autre processus ne peut le lire.
 Si au moins un lecteur lit, aucun autre processus ne peut écrire.
 Plusieurs processus peuvent lire ensembles.

Lecteurs/rédacteurs par sémaphores

 Les vitesses relatives des processus sont quelconques,

 les priorités ou les droits des processus sont quelconques,
 Tout processus termine son écriture et/ou sa lecture au bout d'un temps fini
 La solution doit permettre les lectures en parallèle et interdire la lecture et l’écriture en
parallèle et l’écritures en parallèle.
 Nous utilisons :
o Une variable entière NbLecteur qui est un compteur représentant le nombre de lecteurs
en cours.
o Un sémaphore d'exclusion mutuelle mutexR utilisé entre les accès de tout rédacteur et
d'un groupe de lecteur.
o Un sémaphore d'exclusion mutuelle mutexL utilisée entre les lecteur
Explication :

 Le premier lecteur bloque les rédacteurs.

 Plusieurs lecteurs peuvent lire simultanément.
 Le dernier lecteur libère l'accès aux rédacteurs.
 Un rédacteur bloque l'accès aux autres rédacteurs et lecteurs.
 Ce modèle favorise les lecteurs, car ils peuvent se succéder sans attendre trop longtemps.

Problème principal : famine des rédacteurs

 Un rédacteur peut rester bloqué indéfiniment si de nouveaux lecteurs continuent à arriver et à

s'exécuter avant lui.

Exercice :
Modifiez le code de manière à empêcher les lecteurs d’entrer dans la base si un au moins des
rédacteurs est en attente.

Solution :
Idée principale

 Un rédacteur qui veut écrire bloque immédiatement l'entrée des nouveaux lecteurs.
 Les lecteurs attendent si au moins un rédacteur attend ou écrit.
 On utilise les sémaphores suivants :
o mutexL : Protège la variable NbLecteur (compteur des lecteurs actifs).
o mutexR : Garantit l'exclusion mutuelle des rédacteurs.
o verrou : Bloque l'entrée des nouveaux lecteurs lorsqu’un rédacteur attend.
o NbLecteur : Nombre de lecteurs actifs.
Explication :

 Un rédacteur bloque immédiatement l'entrée des nouveaux lecteurs avec P(verrou).

 Les lecteurs déjà en train de lire terminent, mais aucun nouveau lecteur ne peut entrer tant
qu’un rédacteur attend.
 Le premier lecteur bloque l’écriture avec P(mutexR), et le dernier lecteur la libère avec
V(mutexR).
 Ce modèle garantit que les rédacteurs ne sont pas affamés, tout en assurant l'accès aux
lecteurs dès que possible.

Conclusion
Le problème lecteur-rédacteur illustre les enjeux de la communication par partage de variables
entre processus concurrents. Il vise à gérer l’accès à une ressource partagée entre plusieurs
lecteurs, pouvant lire simultanément, et des rédacteurs, nécessitant un accès exclusif.
L'utilisation de sémaphores permet d’assurer la synchronisation, en garantissant la cohérence
des données. Ce problème met en évidence l’importance de prévenir les conflits d’accès et les
situations de famine dans les systèmes multitâches.

Communication par échanges de messages

La communication entre processus (IPC - InterProcess Communication) permet à plusieurs
processus de s’échanger des informations. Cela est essentiel lorsque :
des processus doivent coopérer pour résoudre une tâche ;
un système distribué ou multitâche doit synchroniser ses composants.
Une boîte aux lettres est un mécanisme d’IPC qui permet à un processus d’envoyer un message
à un autre via une file d’attente intermédiaire.
Fonctionne comme une file FIFO (First In, First Out)

Fonctionnement

 Envoi de message
o Un processus utilise une primitive comme send(mailbox, message) pour envoyer un
message. Le message est mis dans la boîte aux lettres.
 Réception de message
 o Un autre processus utilise receive(mailbox, &message) pour lire un message depuis la
boîte.
 Comportements possibles :
o Blocant : le processus est mis en attente si la boîte est vide (en réception) ou pleine (en
envoi)
o Non blocant : la fonction retourne immédiatement si la boîte est pleine/vidée

Communication par échanges de messages directe (Modèle CSP)

CSP (Communicating Sequential Processes) est un modèle de programmation concurrente
proposé par Tony Hoare. Il permet de modéliser des systèmes où plusieurs processus
communiquent exclusivement par échanges de messages (et sans mémoire partagée).

Principe de la communication directe

Dans le modèle CSP, la communication se fait :

 de manière synchrone
 entre deux processus spécifiques
 par échange de message direct, via un canal identifié
 l’envoi et la réception sont bloquants :
o Le send() ne s'exécute que si un receive() est prêt à lire, et inversement.

Caractéristiques :

La communication synchrone directe signifie que :

 Le message n’est pas stocké dans un tampon

 L’échange de message agit comme un point de rendez-vous entre les deux processus
 Aucun processus ne continue tant que l’autre n’est pas prêt
 Cela permet de synchroniser naturellement les processus.

Exemple : Communication entre un client et un serveur

Deux processus :

 Client : envoie une requête (message)

 Serveur : reçoit le message, le traite, et renvoie une réponse

Caractéristiques de la communication par messages :
 Pas de mémoire partagée

 Messages échangés via une file de messages, socket, ou canal

 Synchronisation implicite : un processus attend que l’autre envoie/reçoive

Interblocage
introduction

 L’allocation d’une ressource à usage exclusif nécessite un verrouillage (lock en anglais).

 Dans certaines situations, réaliser l’opération de verrouillage peut engendrer un blocage
mortel du processus qui verrouille.
 Le verrou (lock) devient mortel (dead). D’où le mot deadlock en anglais qui est appelé
interblocage en français.
 Un processus a besoin d'un ensemble de ressources (mémoire, espace disque, fichier,
périphériques, ...) attribuées par le système d’exploitation.

Le problème d'interblocage peut survenir, si des processus détiennent des ressources et en

demandent d’autres qui ne sont pas libres.

Exemple

 Deux Processus P1 et P2 ont besoins de deux ressources critiques R1 et R2.

 Chaque processus a besoins des deux ressources en même temps.
 Le processus P1 demande R1 puis R2 et le processus P2 demande R2 puis R1.
 un processus P1 détient une ressource R1 et attend une autre ressource R2 qui est utilisée
par un autre processus P2 ;
 le processus P2 détient la ressource R2 et attend la ressource R1.
 On a une situation d’interblocage (P1 attend P2 et P2 attend P1). Les deux processus seront
bloqués indéfiniment.
Le graphe suivant, appelé graphe d’allocation des ressources, représente le scénario de L'
interblocage.

Au niveau de code exécuté par les processus, l'interblocage se produit comme suit :

 Après que le processus P1 exécute P(mutex1) , une interruption horloge se produit

provoquant la suspension de P1 et l'activation de P2.
P2 exécute P(mutex2) sans se bloqué puis se bloque au niveau de p(mutex1).
 Après activation de P1, il se bloque en exécutant P(mutex2). Donc P1 et P2 seront bloqués
infiniment.

Un ensemble de processus est en interblocage si chaque processus attend la

libération d’une ressource allouée à un autre appartenant à l’ensemble.
Comme tous les processus sont en attente, aucun ne pourra s’exécuter et
donc libérer les ressources demandées par les autres. Ils attendront tous
indéfiniment.
2. Conditions nécessaire de survenue d’un interblocage :
Les 4 conditions suivantes doivent être vérifiées en même temps.

1. Exclusion mutuelle : Chaque ressource est soit attribuée à un seul processus, soit
disponible Utilisation d’une ressource en exclusion mutuelle, donc dans une section de
code critique
2. Détention et attente : Les processus qui détiennent des ressources précédemment
obtenues peuvent en demander de nouvelles. Sections critiques imbriquées
3. Pas de réquisition : Les ressources obtenues par un processus ne peuvent lui être
retirées contre son gré. Leur libération doit être explicite. Libération exécutée dans le
protocole de sortie de SC
 4. Attente circulaire : Il y a un circuit d’au moins 2 processus, chacun attendant une
ressource détenue par un autre processus du cycle.

3. Traitement de l’inter-blocage
Différentes catégories de méthodes pour gérer les interblocages :

 S’assurer que le système n’entrera jamais en interblocage: prévenir ou éviter les

interblocages;
 Autoriser l’entrée en situation d’interblocage, les détecter et récupérer;
 Ignorer le problème et prétendre qu’il n’y a jamais d’interblocages; utilisé par la plupart des
OS, incluant UNIX et Windows!
 Souvent, on peut combiner les méthodes (pour différents problèmes d’allocation de
ressources du système).

3.1 Prévention de l’interblocage :

Cette technique consiste à éliminer la possibilité de survenue d’un interblocage en rendant
fausse au moins une des 4 conditions de sa survenue, c'est-à-dire nier une des 4 condition.
3.1.1 Nier l’exclusion mutuelle :
Pas toujours faisable car il peut être difficile qu’une ressource critique puisse devenir non
critique.

 Par exemple au lieu d’imprimer directement, ce qui pourrait bloquer le processus si la

ressource n’est pas libre, le système d’exploitation remplace l’imprimante par un fichier, ce
qui donne l’illusion que l’attribution de la ressource a été possible, alors que ce n’est pas
forcément le cas. Une fois l’impression est terminé, ce fichier est mis en file d’attente
d’impression.
 Un processus unique accède a l’imprimante réelle en prenant les fichiers a imprimer un par
un dans la file d’attente. Ainsi, l’imprimante n’est plus partagée par plusieurs processus. Ce
genre de système dit de spooling (de l’abréviation SPOOL : Simultaneous Peripheral
Operations OnLine).

3.1.2 Nier la détention et attente :

C.à.d. demander toutes les ressources à accès exclusif d’un coup, ce qui élimine l’imbrication
des sections critiques.
On aura une seule section utilisant toutes les ressources. le principe de mise en œuvre est de
rendre atomique ou indivisible, la succession d’acquisition des ressources, on les obtient toutes
ou aucune, la phase d’acquisition des ressources devenant elle-même une section de code
critique.
EXEMPLE :

Nous utilisons un sémaphore d’exclusion mutuelle comme suit :

3.1.3 Nier la réquisition :
Pas de préemption: garantir la préemption: si un processus tient des ressources et en demande
une autre qui n’est pas disponible, toutes les ressources qu’il tenait lui sont retirées, et ces
ressources sont rajoutées à la liste des ressources qu’il attend.
Processus redémarré lorsqu’il peut avoir toutes les ressources dont il a besoin. Il faut pouvoir
sauvegarder/restaurer facilement l’état d’une ressource.
3.1.4 Nier l’attente circulaire :
Pour cela, imposer un ordre dans l’acquisition des ressources, de telle sorte à ne pas avoir de
cycle. On suppose que les ressources sont ordonnées, par exemple, sont numérotées et acquérir
les ressources en respectant cet ordre, de manière croissante, ou décroissante.

3.2 Eviter les interblocages

laisser aux processus faire ce qu’ils veulent, sauf qu’un contrôle (coûteux) est exécuté avant
chaque attribution de ressource. Cette technique utilise l’algorithme du banquier proposé par
dijkstra en 1965. L’algorithme du banquier est théoriquement excellent mais pratiquement peu
utile puisque il suppose que le système connaît auparavant les besoins des processus en
ressources ce qui n'est pas possible dans la majorité des cas. Il y a peu de systèmes qui mettent
en œuvre cet algorithme.
3.2.1 Algorithme du Banquier de dijkstra
Soit 5 processus (A,B,C,D et E) et Soit 4 types de ressources (R1, R2, R3 et R4) :

 6 copies de R1 (5 sont déjà attribuées aux processus)

 3 copies de R2 ( 3 sont déjà attribuées)
 4 copies de R3 (2 sont déjà attribuées)
 2 copies de R4 (2 sont déjà attribuées )
Il reste disponible : 1 copie de R1, 0 copie de R2, 2 copies de R3 et 0 copies de R4
Nous aurons 3 vecteurs

 vecteur des ressources existantes : E= [6 3 4 2 ].

 vecteur des ressources détenues :P= [5 3 2 2].
 vecteur des ressources disponibles :Av= E – P = [1 0 2 0]

3.2.3 Algorithme :

1. Trouver une rangé, R, de la matrice des ressources demandées et non obtenues, tel que
tous les éléments du vecteur R sont inférieur ou égale à Av. Si aucune rangé ne vérifie ce
critère alors il y aura interblocage.
2. Supposer que le processus de la rangé choisie obtient toutes les ressources qu’il demande
et qu’il se termine. Indiqué que ce processus s’est achevé et ajouter ses ressources au
vecteur Av.
3. Répéter les étapes 1 et 2 jusqu’à ce que tous les processus soient marqués comme
terminés c.a.d. pas d’interblocage, ou jusqu’il y ait un interblocage.

Exercice :
Dérouler l'algorithme du banquier sur l'exemple précédant.
Solution
Après application de l’algorithme du banquier sur l’exemple donné : le processus D se terminer
puis les deux processus (A , E) puis les autres ( B , C). Donc, il n'y a pas d'interblocage.

Que fait cet algorithme? Il accorde les demandes aux processus qui pourront
se terminer, récupère leur ressources, et continue ainsi jusqu'à ce que tous les
processus soient traités, ou bien jusqu'à ce qu'il soit impossible de continuer
dans ce cas il y a interblocage.
3.3 Détection de l'interblocage
Le système d'exploitation peut détecter l'interblocage en calculant le graphe d'allocation de
ressources. Un graphe d'allocation de ressource est un graphe orienté contenant deux types de
nœuds : les processus qui sont représentés par des cercles et les ressources représentées par
des carrés. Si nous avons plusieurs copies d'une ressource R, le carré aura plusieurs points
l'intérieur selon le nombre de copies :
Il y aura un arcs allant du processus P vers la ressource R si P demande R. Un arcs allant de la
ressource vers le processus si la ressource est allouer au processus:

Exercice :
Examiner le graphe d'allocation de ressources pour les trois scénarios suivants et préciser s'il y a
une situation d'interblocage ou non dans chaque cas.

Solution
(a) sans interblocage; (b) avec interblocage: il y a un circuit; (c) avec un circuit mais sans
interblocage.

À l'aide des exemples précédents, on s'aperçoit que:

 lorsque le graphe a un circuit et que les ressources n'ont qu'un élément dans le circuit, il y a
interblocage. Donc pour détecter ce type de problème, il suffit de bâtir le graphe, et de
détecter les circuits.
 lorsque les ressources dans le circuit ont plus d'un élément, on peut utilisé l'algorithme
similaire à celui du banquier pour détecter l'interblocage.

Conclusion
L’interblocage (ou deadlock) est une situation critique où plusieurs processus restent indéfiniment
bloqués en attendant des ressources détenues mutuellement. Pour y faire face, plusieurs
approches existent : l’évitement (comme l’algorithme du banquier), la détection suivie d’un
traitement (par arrêt ou reprise de processus), et la prévention par des règles d’allocation
strictes. Le choix de la stratégie dépend des besoins du système en termes de performance,
sécurité et complexité de mise en œuvre.