Exclusion Mutuelle et Progrès

Oui, cette solution respecte les trois règles de l'exclusion

mutuelle :
1. Exclusion Mutuelle : L'utilisation de sémaphores (mutex1
et mutex2) garantit qu'un seul thread peut entrer dans la
section critique (accéder aux files d'attente) à la fois,
assurant ainsi l'exclusion mutuelle.
2. Progrès : Le planificateur garantit que les processus sont
distribués entre les deux files d'attente, et le thread du
processeur consommera des processus des files non vides.
Cela garantit le progrès tant qu'il y a quelque chose à
exécuter.
3. Attente Bornée : L'utilisation de sémaphores garantit une
attente bornée. Lorsqu'un thread attend d'entrer dans la
section critique (par exemple, en attente sur mutex1 ou
mutex2), il aura finalement la chance d'entrer, empêchant
une attente indéfinie. expliquer

Explication des trois règles de l'exclusion mutuelle appliquées au

problème
1. Exclusion Mutuelle :
L’exclusion mutuelle est une propriété qui garantit qu’une seule entité (thread ou
processus) peut accéder à une section critique (une ressource partagée) à un moment
donné.
Dans cette solution :

Les sémaphores mutex1 et mutex2 jouent le rôle de verrous.

Lorsqu'un thread souhaite accéder à une file d'attente (ou une autre ressource
partagée), il doit attendre que le sémaphore correspondant soit disponible.

Cela signifie qu'aucun autre thread ne peut interférer ou modifier la ressource

pendant qu’un thread est dans la section critique. Une fois l'accès terminé, le
sémaphore est libéré, permettant à un autre thread d'entrer.

Exemple concret : Si deux threads tentent d'ajouter ou de retirer un élément d'une file
en même temps, seul un des threads obtiendra l'accès en premier grâce au sémaphore.

1/73
2. Progrès :
Le progrès garantit qu’aucun thread ou processus n’est bloqué de façon permanente si
des ressources sont disponibles.
Dans cette solution :

Le planificateur répartit les processus entre deux files d'attente.

Tant qu’il y a des processus à traiter dans l’une des files (non vides), le thread du
processeur (ou consommateur) continuera à retirer et exécuter ces processus.

Aucun thread n'est bloqué de manière indéfinie tant que des processus existent
dans les files.

Exemple concret : Si la file d’attente 1 devient vide, le thread du processeur peut passer
à la file 2, évitant ainsi un blocage. Cela permet d'assurer la continuité des opérations.

3. Attente Bornée :
Cette règle garantit qu’un thread en attente de ressources partagées finira par obtenir
l'accès dans un délai raisonnable.
Dans cette solution :

Les sémaphores garantissent un ordre équitable d'accès. Si un thread attend pour

accéder à une file (par exemple, bloque sur mutex1 ou mutex2), il sera
éventuellement débloqué lorsque l’autre thread libérera le sémaphore.

Aucun thread ne sera bloqué indéfiniment car les sémaphores assurent une file
d'attente ordonnée et équitable (en fonction du mécanisme FIFO intégré aux
sémaphores).

Exemple concret : Si plusieurs threads tentent d'accéder à la même file d'attente, le

système garantit que chaque thread attend son tour de manière équitable.

En résumé
Exclusion Mutuelle : Un seul thread accède à une section critique à la fois grâce aux
sémaphores.

2/73
 Progrès : Les threads continuent d'exécuter des processus tant qu’il y en a à traiter,
évitant ainsi les blocages.

Attente Bornée : Les threads en attente auront toujours la possibilité d’accéder aux
ressources sans rester bloqués indéfiniment.

donner les conecepte de base en systeme dexploitation

Les concepts de base en systèmes d'exploitation sont essentiels pour comprendre leur
fonctionnement. Voici les principaux concepts :

1. Système d'exploitation (OS) :

Le système d'exploitation est un logiciel intermédiaire entre le matériel de l'ordinateur et les
applications. Il gère les ressources matérielles et logicielles pour offrir une interface
utilisateur et exécuter des programmes.

2. Gestion des processus :

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

Création et terminaison : Les processus sont créés (par exemple, par un utilisateur ou
un programme) et peuvent se terminer volontairement ou par l'OS.

États du processus :

Nouveau (New) : En création.

Prêt (Ready) : En attente d'exécution.

En cours d'exécution (Running) : Actuellement en exécution.

Bloqué (Blocked) : En attente d'une ressource.

Terminé (Terminated) : Le processus a fini son exécution.

Planification des processus : L'OS détermine quel processus s'exécute à un moment

donné, en fonction d'algorithmes comme FIFO, Round-Robin, ou Priorité.

3/73
3. Gestion de la mémoire :
L'OS gère la mémoire pour allouer les ressources nécessaires aux processus en cours
d'exécution.

Mémoire principale (RAM) : Stocke temporairement les données et programmes actifs.

Mémoire virtuelle : Utilise le disque dur comme extension de la RAM pour exécuter des
processus lorsque la mémoire est insuffisante.

Techniques :

Pagination : Divise la mémoire en blocs de taille fixe (pages).

Segmentation : Divise la mémoire en segments de taille variable.

4. Gestion des fichiers :

Un fichier est une collection de données stockées sur un support (disque dur, SSD, etc.). L'OS
offre une structure hiérarchique (répertoires et sous-répertoires) pour organiser les fichiers.

Système de fichiers : Méthodes pour stocker et récupérer les données (par exemple,
FAT32, NTFS, EXT4).

Opérations de fichiers : Création, lecture, écriture, suppression, et renommage.

5. Gestion des E/S (Entrées/Sorties) :

L'OS gère les périphériques (clavier, souris, imprimante, etc.) pour permettre leur interaction
avec les applications.

Drivers : Logiciels spécifiques qui permettent à l'OS de communiquer avec les

périphériques matériels.

Buffering et Spooling : Techniques pour gérer les données en attente d'utilisation par
les périphériques.

4/73
6. Gestion des ressources :
L'OS gère les ressources partagées entre les processus.

Exclusion mutuelle : Garantir qu’une seule entité accède à une ressource partagée à un
moment donné.

Synchronisation : Coordination entre processus pour exécuter des actions dans un

ordre déterminé.

Deadlock (interblocage) : Situation où plusieurs processus sont bloqués en attente de

ressources.

7. Planification des tâches :

L'OS décide quel processus ou thread doit s'exécuter à un moment donné.

Planificateur à court terme : Sélectionne un processus prêt à exécuter immédiatement.

Planificateur à long terme : Contrôle le nombre de processus présents dans le système.

Algorithmes : Premier arrivé, premier servi (FIFO), Round-Robin, Priorité, etc.

8. Gestion de la sécurité et de la protection :

L'OS protège les données et ressources contre tout accès non autorisé.

Authentification : Vérifie l'identité des utilisateurs (mots de passe, biométrie).

Autorisations : Contrôle les actions des utilisateurs sur les fichiers et ressources.

Cryptographie : Chiffre les données pour empêcher l'accès non autorisé.

9. Systèmes multitâches :
Un système multitâche permet à plusieurs processus de s’exécuter simultanément en
partageant les ressources.

5/73
 Préemptif : L’OS peut interrompre un processus pour en exécuter un autre.

Coopératif : Les processus contrôlent eux-mêmes leur exécution.

10. Systèmes distribués :

Un système distribué est un ensemble de machines interconnectées travaillant ensemble
comme un seul système logique. Cela inclut :

Partage des ressources : Les systèmes partagent des fichiers, imprimantes, etc.

Transparence : L'utilisateur perçoit le système comme un tout cohérent.

11. Virtualisation :
La virtualisation permet d’exécuter plusieurs systèmes d'exploitation sur une seule machine
physique via des machines virtuelles. Les hyperviseurs, comme VMware ou VirtualBox,
gèrent cette virtualisation.

Ces concepts forment la base de tout système d'exploitation moderne et expliquent

comment il gère les ressources pour fournir des services aux utilisateurs et aux applications.

conecpte de base en synchronisation

La synchronisation est un concept clé en informatique, particulièrement dans les systèmes

d'exploitation et les systèmes parallèles. Elle permet de gérer la coordination entre plusieurs
processus ou threads qui accèdent à des ressources partagées. Voici les concepts de base en
synchronisation :

1. Problème de la synchronisation :

6/73
La synchronisation est nécessaire lorsque plusieurs processus ou threads :

Partagent des ressources (mémoire, fichiers, périphériques).

Doivent coordonner leurs actions pour éviter des erreurs comme des conditions de
course (race conditions), où l’ordre des exécutions impacte les résultats.

2. Section critique :
Une section critique est une partie d’un programme où des ressources partagées sont
accédées.

Problème : Si plusieurs processus accèdent simultanément à une section critique sans

coordination, cela peut entraîner des comportements imprévisibles.

Exemple : Deux threads modifiant la même variable globale sans verrou.

3. Règles de synchronisation (Critères de correction) :

Les mécanismes de synchronisation doivent respecter trois règles :

1. Exclusion mutuelle : Une seule entité (processus ou thread) doit accéder à la section
critique à la fois.

2. Progrès : Si plusieurs processus veulent accéder à une section critique et qu'elle est libre,
l’un d’eux doit pouvoir y entrer.

3. Attente bornée : Aucun processus ne doit attendre indéfiniment pour accéder à la

section critique.

4. Mécanismes de synchronisation :

a. Sémaphores :

Un sémaphore est une variable entière utilisée pour contrôler l'accès aux ressources
partagées.

7/73
 Types :

Sémaphore binaire : Fonctionne comme un verrou (valeurs 0 ou 1).

Sémaphore comptable : Peut avoir des valeurs supérieures à 1 (utile pour plusieurs
instances d’une ressource).

Opérations :

wait() : Diminue la valeur du sémaphore. Si le résultat est négatif, le processus est

bloqué.

signal() : Augmente la valeur du sémaphore et réveille un processus bloqué, s'il

existe.

b. Verrous (Locks) :

Permettent de bloquer une ressource jusqu'à ce qu'elle soit libérée par le processus ou
thread qui l’utilise.

Types :

Verrou simple.

Verrou à spin (spinlock) : Attend activement qu'un verrou soit libéré.

Verrous réentrants : Permettent à un même thread d'acquérir plusieurs fois le

verrou.

c. Moniteurs :

Une structure de données qui regroupe des variables partagées, leurs opérations, et un
mécanisme de synchronisation.

Les moniteurs permettent un accès sûr à une ressource grâce à des verrous implicites.

d. Variables conditionnelles :

Utilisées avec les moniteurs pour permettre à un processus d'attendre qu'une certaine
condition soit remplie.

Opérations :

wait() : Suspend l’exécution jusqu’à ce que la condition soit satisfaite.

signal() : Réveille un processus en attente.

e. Barrières :

8/73
 Un mécanisme de synchronisation utilisé pour bloquer un groupe de threads jusqu'à ce
qu'ils aient tous atteint un point commun d'exécution.

5. Problèmes classiques de synchronisation :

a. Le problème des lecteurs-écrivains :

Plusieurs processus (lecteurs) peuvent lire simultanément une ressource partagée, mais
un seul écrivain peut écrire à un moment donné.

Objectif : Assurer l’exclusion mutuelle pour les écrivains tout en permettant un accès
concurrentiel pour les lecteurs.

b. Le problème des philosophes mangeurs :

Plusieurs philosophes doivent alterner entre manger et réfléchir, en partageant des

fourchettes (ressources).

Objectif : Éviter les interblocages (deadlocks) et la famine (starvation).

c. Le problème des producteurs-consommateurs :

Les producteurs génèrent des données placées dans un tampon (buffer), et les
consommateurs retirent ces données pour traitement.

Objectif : Synchroniser les producteurs et consommateurs pour éviter un tampon vide

ou plein.

6. Synchronisation dans les systèmes distribués :

Horloges logiques : Assurent l’ordre des événements entre différents processus.

Algorithmes de consensus : Permettent aux processus d’un système distribué de se

mettre d’accord sur un état commun.

7. Défis en synchronisation :

9/73
 Deadlock (Interblocage) : Lorsque deux ou plusieurs processus attendent
mutuellement des ressources, provoquant un blocage permanent.

Starvation (Famine) : Lorsqu’un processus attend indéfiniment parce que d'autres ont
toujours la priorité.

Conditions de course : Lorsque plusieurs processus accèdent simultanément à des

données partagées sans coordination, entraînant des résultats imprévisibles.

8. Outils modernes pour la synchronisation :

Frameworks : Les bibliothèques comme [Link] (Java) et threading
(Python) offrent des primitives de synchronisation intégrées.

Langages : Certains langages modernes (comme Go avec les goroutines ou Rust)

intègrent des mécanismes natifs pour gérer la synchronisation efficacement.

En résumé :
La synchronisation est un mécanisme essentiel pour éviter les erreurs dans les systèmes
multi-thread ou multi-processus. Elle repose sur des outils comme les sémaphores, verrous,
et moniteurs pour coordonner l'accès aux ressources partagées tout en respectant les
critères d'exclusion mutuelle, de progrès et d'attente bornée.

resurce critique et section critique

Les notions de ressource critique et section critique sont fondamentales en

synchronisation. Bien qu'elles soient liées, elles désignent des concepts différents.

1. Ressource critique :
Une ressource critique est une ressource partagée entre plusieurs processus ou threads,
dont l'accès concurrent peut entraîner des problèmes si elle n'est pas correctement gérée.

10/73
Exemples de ressources critiques :

Une variable partagée (compteur global, tableau partagé).

Une base de données ou un fichier en écriture/lecture.

Une imprimante ou un autre périphérique.

Problèmes liés aux ressources critiques :

Condition de course (Race Condition) : Lorsque plusieurs processus accèdent à une

ressource critique en même temps, les résultats dépendent de l'ordre d'exécution.

Incohérence des données : Un accès concurrent peut corrompre les données ou

entraîner des résultats incorrects.

Objectif de synchronisation pour une ressource critique :

Assurer un accès contrôlé et ordonné à cette ressource pour éviter tout conflit.

2. Section critique :
Une section critique est une partie d’un programme qui accède à une ressource critique. Elle
représente le code où des conflits peuvent survenir si plusieurs processus ou threads
exécutent cette section en même temps.

Propriétés d'une section critique :

Sensibilité : Elle contient des instructions qui modifient ou utilisent une ressource
critique.

Exigence d'exclusion mutuelle : Un seul processus ou thread à la fois doit exécuter cette
section pour éviter des erreurs.

Exemple d'une section critique :

// Ressource critique : la variable partagée "compteur"

int compteur = 0;

// Section critique
void incrementer_compteur() {

11/73
 compteur = compteur + 1; // Accès concurrent peut causer des problèmes
}

Si deux threads exécutent cette fonction simultanément sans synchronisation, le résultat de

compteur peut être incorrect.

Différences clés entre ressource critique et section critique :

Aspect Ressource Critique Section Critique

Définition Ressource partagée sensible aux accès Partie du code accédant à une
concurrents. ressource critique.

Exemple Variable globale, fichier, périphérique. Instructions modifiant une variable

partagée.

Objectif Protéger la ressource contre les accès Restreindre l'accès concurrent à la

incorrects. ressource.

Exclusion Assurée en protégeant les sections Doit être respectée pour éviter des
Mutuelle critiques. conflits.

3. Gestion des sections critiques :

Pour gérer les sections critiques et protéger les ressources critiques, des mécanismes de
synchronisation sont utilisés :

Verrous (Locks) : Assurent qu’un seul thread peut entrer dans une section critique à la
fois.

Sémaphores : Contrôlent l’accès aux ressources critiques.

Moniteurs : Encapsulent les sections critiques et les mécanismes de verrouillage

associés.

Variables atomiques : Fournissent un accès sécurisé sans utiliser explicitement de

verrous.

12/73
Exemple illustratif :
Supposons une ressource critique : un fichier journal où plusieurs processus écrivent des
données.

1. La ressource critique est le fichier journal.

2. La section critique correspond au code d’écriture dans ce fichier :

python

# Section critique
with open("[Link]", "a") as fichier:
[Link]("Nouvelle entrée\n")

Pour éviter que plusieurs processus écrivent en même temps dans le fichier (ce qui pourrait
entraîner des incohérences), on utilise des mécanismes comme un verrou autour de cette
section critique.

En résumé :
Une ressource critique est une entité partagée sensible à l'accès concurrent.

Une section critique est le bloc de code qui accède ou modifie cette ressource.

La synchronisation vise à protéger les sections critiques pour assurer un accès sécurisé
aux ressources critiques.

donner les concpte de base et les type existe et soltion

sofware et hardware en et critere verfifer pour un solution
en csp

La problématique des sections critiques (Critical Section Problem, CSP) est un problème
fondamental en synchronisation, visant à garantir un accès sûr aux ressources partagées
dans les systèmes multitâches. Voici une vue d'ensemble des concepts de base, des types
existants, des solutions logicielles et matérielles, et des critères pour évaluer une solution.

13/73
1. Concepts de base
a. Section critique (Critical Section) :
Partie du programme où des ressources partagées sont accédées ou modifiées.

Le problème est de s'assurer qu'un seul processus ou thread exécute cette section à la
fois (exclusion mutuelle).

b. Problème des sections critiques (CSP) :

Plusieurs processus doivent accéder à des ressources partagées sans interférer les uns
avec les autres.

L'objectif est de synchroniser ces processus pour éviter des conditions de course (race
conditions) et des incohérences.

c. État d'un processus :

Un processus peut être dans l'un des états suivants :

1. Section critique : Accès exclusif à la ressource partagée.

2. Section d'entrée : Prépare l'entrée dans la section critique.

3. Section de sortie : Libère l'accès à la ressource.

4. Section restante : Parties du code qui n'accèdent pas aux ressources partagées.

2. Types de problèmes CSP

a. Problème à deux processus :
Deux processus doivent partager une ressource en respectant l'exclusion mutuelle.

b. Problème à n processus :
Généralisation pour n processus ou threads.

3. Solutions pour CSP

14/73
A. Solutions logicielles
1. Basées sur des drapeaux (Flags) :

Utilisation de variables pour indiquer si un processus est dans sa section critique.

Exemple : L'algorithme de Dekker ou de Peterson.

Fonctionnement :

Chaque processus signale son intention d'entrer dans la section critique.

L'autre processus décide en fonction des drapeaux.

2. Algorithmes de priorité :

Ajout d'une notion de priorité pour décider quel processus accède en premier à la
ressource.

Exemple : Algorithme de Bakery.

3. Moniteurs :

Structures de haut niveau encapsulant la ressource partagée avec des primitives

comme wait() et signal() .

4. Utilisation des sémaphores :

Un sémaphore est une variable utilisée pour contrôler l'accès à une ressource.

Deux opérations : wait() (P) et signal() (V).

B. Solutions matérielles
1. Instructions atomiques :

Les instructions comme Test-and-Set ou Compare-and-Swap permettent de tester

et de modifier une variable en une seule opération, sans interruption.

Fonctionnement :

Si la ressource est libre, le processus peut entrer dans sa section critique.

Sinon, il doit attendre.

2. Verrouillage matériel :

Les processeurs modernes intègrent des mécanismes de verrouillage matériel pour

garantir l’exclusion mutuelle.

15/73
4. Critères pour vérifier une solution
Une solution au problème des sections critiques doit respecter les trois critères suivants :

a. Exclusion mutuelle :
Un seul processus à la fois peut être dans sa section critique.

b. Progrès (Progress) :
Si plusieurs processus souhaitent entrer dans leur section critique, le choix de celui qui
entre doit être effectué dans un délai fini.

Les processus ne doivent pas être bloqués indéfiniment.

c. Attente bornée (Bounded Waiting) :

Un processus en attente d'accès à sa section critique doit y accéder dans un temps fini.

Empêche les problèmes de famine (starvation).

5. Comparaison des solutions logicielles et matérielles

Aspect Solutions logicielles Solutions matérielles

Complexité Plus complexes (algorithmes Plus simples à utiliser.

explicites).

Niveau Implémentées au niveau logiciel. Implémentées au niveau matériel

d'abstraction (processeur).

Efficacité Plus lentes (utilisation du CPU). Plus rapides (opérations atomiques).

Portabilité Compatibles avec tous les Dépend des architectures matérielles.

systèmes.

6. Exemple d'une solution logicielle : Algorithme de

Peterson
Principe :

16/73
 Fonctionne pour deux processus.

Utilise deux drapeaux (f lag[0], f lag[1]) et une variable partagée (turn).

Code :

bool flag[2] = {false, false};

int turn = 0;

// Processus i
flag[i] = true;
turn = 1 - i;
while (flag[1 - i] && turn == 1 - i) {
// Attendre
}
// Section critique
flag[i] = false;

7. Exemple d'une solution matérielle : Test-and-Set

Principe :
Utilise une instruction atomique test_and_set pour vérifier et modifier une variable.

Code :
c

bool lock = false;

bool test_and_set(bool *lock) {

bool old = *lock;
*lock = true;
return old;
}

// Section critique
while (test_and_set(&lock)) {

17/73
 // Attendre
}
// Section critique
lock = false;

En conclusion, la résolution du problème des sections critiques est essentielle pour garantir
la sécurité et la cohérence dans les systèmes multitâches. Les solutions, qu'elles soient
logicielles ou matérielles, doivent respecter les critères d'exclusion mutuelle, de progrès et
d'attente bornée.

❏ Calls to acquire() and release() must be atomic

Pour garantir que les appels à acquire() et release() soient atomiques, il est essentiel
qu'ils soient exécutés sans interruption, de sorte que l'exécution de ces fonctions ne puisse
être préemptée ou affectée par un autre processus ou thread. Voici quelques points à
considérer et des techniques pour y parvenir :

1. Pourquoi les appels acquire() et release() doivent

être atomiques ?
Problème : Si l'exécution de ces fonctions peut être interrompue, il pourrait y avoir des
conditions de course (race conditions) ou des incohérences dans l'état des sémaphores,
des verrous ou des autres mécanismes de synchronisation.

Exemple problématique :

Si deux threads appellent acquire() simultanément sur un verrou, et que les

instructions internes à acquire() ne sont pas atomiques, les deux threads
pourraient croire qu'ils ont obtenu le verrou, ce qui viole l'exclusion mutuelle.

18/73
2. Techniques pour rendre les appels acquire() et
release() atomiques

A. Solutions matérielles
1. Instructions atomiques :

Utilisation d'instructions matérielles comme :

Test-and-Set

Compare-and-Swap

Fetch-and-Increment

Ces instructions garantissent que la vérification et la modification d'une variable

partagée sont effectuées en une seule opération non interrompue.

Exemple (Test-and-Set) :

bool test_and_set(bool *lock) {

bool old = *lock;
*lock = true;
return old;
}

void acquire() {
while (test_and_set(&lock)) {
// Attendre
}
}

void release() {
lock = false;
}

2. Désactivation des interruptions :

Désactiver les interruptions pendant l'exécution de acquire() et release()

garantit qu'aucun autre processus ou thread ne peut intervenir.

Limitation :

Ne peut être utilisé qu'en mode noyau (kernel mode).

19/73
 Peut provoquer une latence si les interruptions restent désactivées trop
longtemps.

B. Solutions logicielles
1. Spinlocks (verrouillage actif) :

Une boucle d'attente active vérifie la disponibilité du verrou jusqu'à ce qu'il soit
libéré.

Exemple :

void acquire() {
while (__sync_lock_test_and_set(&lock, 1)) {
// Attendre
}
}

void release() {
__sync_lock_release(&lock);
}

Inconvénient : Peut entraîner une consommation excessive de CPU si le verrou

reste occupé.

2. Mutual Exclusion via drapeaux :

Utilisation d'algorithmes comme celui de Peterson ou des sémaphores pour

synchroniser l'accès.

Ces algorithmes fonctionnent uniquement dans un environnement multi-thread

limité.

3. Moniteurs ou Mutex :

Les appels acquire() et release() encapsulent un verrou natif qui garantit

l'exclusion mutuelle.

Exemple avec un mutex en Java :

java

20/73
 synchronized(lock) {
// Section critique
}

C. Implémentation hybride (matériel + logiciel)

1. Mécanismes modernes :

Les API modernes comme pthread ou std::mutex utilisent des solutions hybrides,
combinant des techniques matérielles (instructions atomiques) et logicielles (attente
passive ou active).

2. État non-bloquant :

Les bibliothèques modernes utilisent des structures non-bloquantes (lock-free) pour

réduire la latence.

3. Propriétés requises pour une solution correcte

Pour que les appels acquire() et release() soient corrects, ils doivent respecter ces
critères :

1. Atomicité :

Les deux fonctions doivent être exécutées sans interruption, garantissant qu'aucun
autre thread ne peut interférer avec leur exécution.

2. Exclusion mutuelle :

Une seule entité peut obtenir le verrou à la fois.

3. Attente bornée :

Les threads en attente d'un verrou doivent y accéder dans un délai fini.

4. Progrès :

Un thread ne peut pas être bloqué indéfiniment si aucune autre entité n'occupe le
verrou.

21/73
4. Exemple pratique (C avec pthread_mutex_t )
Code :
c

#include <pthread.h>

pthread_mutex_t lock;

void acquire() {
pthread_mutex_lock(&lock);
}

void release() {
pthread_mutex_unlock(&lock);
}

void* thread_function(void* arg) {

acquire();
// Section critique
release();
return NULL;
}

int main() {
pthread_mutex_init(&lock, NULL);

pthread_t t1, t2;

pthread_create(&t1, NULL, thread_function, NULL);
pthread_create(&t2, NULL, thread_function, NULL);

pthread_join(t1, NULL);
pthread_join(t2, NULL);

pthread_mutex_destroy(&lock);
return 0;
}

22/73
En conclusion, pour garantir que acquire() et release() soient atomiques, on peut
s'appuyer sur des instructions matérielles atomiques ou des primitives logicielles fiables
comme les mutex ou les sémaphores. Le choix dépend du niveau d'abstraction (logiciel ou
matériel) et des exigences de performance.

2/2

Compare-and-Swap

Compare-and-Swap (CAS) est une instruction atomique utilisée dans les systèmes
concurrents pour mettre à jour une valeur partagée de manière sûre sans utiliser de verrou
explicite. C'est un outil essentiel dans les implémentations de structures de données non
bloquantes (lock-free). Voici une explication détaillée de son fonctionnement, son
importance, ses avantages et ses inconvénients.

1. Fonctionnement de Compare-and-Swap
L'instruction CAS compare la valeur d'une variable mémoire à une valeur attendue. Si elles
sont égales, elle met à jour la variable avec une nouvelle valeur. Sinon, elle ne fait rien.

Pseudo-code de CAS :

bool CompareAndSwap(int* addr, int expected, int new_value) {

if (*addr == expected) {
*addr = new_value; // Mise à jour réussie
return true;
} else {
return false; // La mise à jour échoue
}
}

Paramètres :

addr : L'adresse de la variable partagée.

expected : La valeur que l'on attend que la variable ait.

23/73
 new_value : La valeur à laquelle on veut mettre à jour la variable.

Retour :

true si la mise à jour a réussi.

false si la valeur actuelle de la variable diffère de expected .

2. Exemple pratique

Problème :

Deux threads essaient d'incrémenter une variable partagée, sans verrou.

Code avec CAS :

#include <stdatomic.h>
#include <stdbool.h>

void increment(int* counter) {

int old_value;
do {
old_value = *counter; // Lire la valeur actuelle
} while (!atomic_compare_exchange_weak(counter, &old_value, old_value + 1));
// Réessayer jusqu'à ce que l'incrément soit appliqué avec succès
}

int main() {
int counter = 0;
increment(&counter); // Thread 1
increment(&counter); // Thread 2
printf("Counter: %d\n", counter); // Résultat : 2
return 0;
}

Explications :

Chaque thread lit la valeur actuelle de counter dans old_value .

24/73
 Si la valeur n'a pas changé pendant le calcul, CAS met à jour counter à old_value +
1.

Si la valeur a changé (condition concurrente), le thread réessaye avec la nouvelle

valeur.

3. Importance et applications
Structures de données lock-free :

CAS est couramment utilisé pour implémenter des piles, des files d'attente, des
listes chaînées, etc., sans utiliser de verrou.

Synchronisation fine :

Permet de gérer des ressources partagées sans bloquer des threads inutiles.

Optimisation des performances :

Réduit les surcoûts associés aux mécanismes de verrouillage traditionnels, comme

les mutex.

4. Propriétés de CAS
Propriété Description

Atomicité Garantit que la comparaison et la mise à jour sont effectuées en une seule opération
atomique.

Lock-free Ne nécessite pas de verrouillage global.

Non- Si la mise à jour échoue, le thread peut réessayer sans attendre.

bloquant

5. Avantages
1. Pas de blocage :

25/73
 CAS évite les problèmes de blocage (deadlock) qui peuvent survenir avec des
verrous traditionnels.

2. Performances élevées :

Réduction des context switches et des overheads liés à l'attente.

3. Équité :

Tous les threads peuvent tenter leur chance pour accéder à la ressource.

4. Simple à utiliser :

Bien adapté aux opérations élémentaires comme l'incrémentation atomique ou les

changements conditionnels.

6. Inconvénients
1. Boucles d’attente active (Spin) :

En cas de concurrence élevée, plusieurs threads peuvent constamment échouer et

réessayer, entraînant une utilisation excessive du processeur.

2. Pas adapté aux longues sections critiques :

CAS fonctionne mieux pour des opérations rapides. Pour des sections critiques
complexes, les verrous peuvent être plus adaptés.

3. Complexité dans les systèmes complexes :

L'implémentation de structures lock-free avec CAS peut devenir difficile et sujette à

des erreurs.

7. Support matériel
La plupart des processeurs modernes prennent en charge l'instruction CAS ou des
équivalents, souvent sous les noms suivants :

x86 : CMPXCHG

ARM : LDREX / STREX

26/73
 PowerPC : Compare-And-Swap

Ces instructions garantissent l'atomicité au niveau matériel, permettant une utilisation

efficace de CAS dans les environnements multithread.

8. Comparaison avec Test-and-Set

Aspect Compare-and-Swap Test-and-Set

Complexité Plus complexe (compare + mise à jour). Plus simple (modifie

uniquement).

Applications Structures non bloquantes, Accès basique à un verrou.

synchronisation fine.

Flexibilité Plus flexible pour les mises à jour Limité aux mécanismes de
conditionnelles. verrouillage.

Effet sur les Réduit les conflits inutiles. Peut entraîner plus de
performances contention.

9. Conclusion
Le Compare-and-Swap (CAS) est une instruction atomique puissante et flexible qui joue un
rôle clé dans la programmation concurrente moderne. Bien qu'elle présente des
inconvénients dans certains scénarios, elle est indispensable pour créer des structures de
données efficaces et non bloquantes. Le choix d'utiliser CAS ou une autre méthode dépend
du contexte, de la complexité de l'opération et des exigences de performance.

Critical Region

Critical Region (Région critique)

Une Critical Region ou région critique est un concept fondamental en programmation
concurrente. Elle désigne une partie d'un programme où une ressource partagée est
accédée ou modifiée. Pendant l'exécution dans cette région, il est crucial que l'accès soit
mutuellement exclusif pour éviter des problèmes comme des conditions de course ou des
incohérences de données.

27/73
1. Caractéristiques d'une région critique
1. Accès exclusif :

Une seule entité (processus ou thread) doit être autorisée à exécuter la région
critique à un moment donné.

2. Manipulation de ressources partagées :

Une région critique implique l'accès à des données ou ressources partagées, comme
des variables globales, des fichiers, ou des périphériques matériels.

3. Protection par synchronisation :

Des mécanismes comme des verrous (locks), des sémaphores ou des moniteurs
sont utilisés pour réguler l'accès à la région critique.

2. Problèmes liés à une région critique

1. Condition de course (Race Condition) :

Plusieurs threads accèdent simultanément à une ressource partagée, entraînant des

résultats indéterminés.

2. Deadlock (blocage) :

Deux ou plusieurs threads restent bloqués indéfiniment, chacun attendant une

ressource détenue par un autre.

3. Starvation (famine) :

Un thread n'obtient jamais l'accès à la région critique parce que d'autres threads
sont toujours prioritaires.

4. Incohérence des données :

Des données partagées peuvent être corrompues si plusieurs threads modifient

simultanément les mêmes valeurs.

28/73
3. Conditions pour gérer une région critique
Pour gérer correctement une région critique, une solution doit respecter les critères suivants
:

1. Exclusion mutuelle :

Un seul thread ou processus peut accéder à la région critique à un moment donné.

2. Progrès :

Si aucun thread n'est dans la région critique, un thread souhaitant y entrer doit
pouvoir le faire rapidement.

3. Attente bornée :

Un thread demandant l'accès à une région critique doit y accéder dans un délai fini.

4. Solutions pour gérer les régions critiques

A. Logiciels

1. Locks (verrous) :

Utilisation explicite de verrous pour s'assurer qu'un seul thread entre dans la région
critique.

Exemple en C :
c

pthread_mutex_t lock;

void critical_region() {
pthread_mutex_lock(&lock);
// Code de la région critique
pthread_mutex_unlock(&lock);
}

2. Sémaphores :

Un sémaphore peut être utilisé pour contrôler l'accès à la région critique via des
opérations P() et V() .

Exemple :

29/73
 c

sem_wait(&semaphore); // Entrer dans la région critique

// Code de la région critique
sem_post(&semaphore); // Quitter la région critique

3. Moniteurs :

Une structure haut niveau encapsule la région critique et contrôle l'accès via des
primitives comme wait() et signal() .

4. Algorithmes logiciels :

Algorithmes comme celui de Peterson ou de Dekker permettent de gérer une région

critique sans verrou matériel.

B. Matériels

1. Instructions atomiques :

Utilisation d'instructions comme Test-and-Set ou Compare-and-Swap .

Exemple avec Test-and-Set :

while (test_and_set(&lock)) {
// Attendre
}
// Code de la région critique
lock = false; // Libérer le verrou

2. Désactivation des interruptions :

Les interruptions peuvent être désactivées pour empêcher tout autre thread ou
processus de perturber la région critique.

Limité au mode noyau (kernel mode).

5. Exemple illustratif

Problème sans synchronisation :

30/73
Supposons deux threads qui incrémentent une variable globale.

int counter = 0;

void increment() {
counter++; // Non sécurisé
}

Si les deux threads exécutent counter++ simultanément, le résultat final peut être
incorrect à cause de l'incrémentation non atomique.

Solution avec mutex :

pthread_mutex_t lock;

void increment() {
pthread_mutex_lock(&lock);
counter++; // Sécurisé
pthread_mutex_unlock(&lock);
}

Le mutex garantit que chaque thread modifie counter sans interférence.

6. Comparaison des solutions

Méthode Avantages Inconvénients

Locks Simple à utiliser et implémenter. Peut entraîner des blocages.

Sémaphores Permet le contrôle sur plusieurs Complexe à gérer, risque de

threads. deadlock.

Moniteurs Abstraction élevée et sécurité Nécessite un support natif (Java,

intégrée. etc.).

Instructions atomiques Très rapides et efficaces. Limitées aux opérations

simples.

31/73
 Méthode Avantages Inconvénients

Désactivation des Efficace pour les sections courtes. Non applicable en mode
interruptions utilisateur.

7. Conclusion
Une Critical Region est une partie essentielle des systèmes multitâches et doit être protégée
pour éviter des conflits ou des incohérences. Le choix de la méthode de synchronisation
dépend du contexte, des ressources partagées, et des exigences en termes de performance
et de complexité.

Deadlock dans prblem de philosofe

Le problème des philosophes est un classique en programmation concurrente qui illustre

les défis de la synchronisation, notamment les deadlocks (blocages), les conditions de
famine, et les délais indéfinis.

1. Problème des philosophes

Description :
Cinq philosophes sont assis autour d'une table circulaire.

Chaque philosophe alterne entre deux activités :

Penser

Manger

Pour manger, un philosophe a besoin de deux fourchettes (une à gauche et une à

droite).

Représentation du problème :
Les philosophes représentent des processus.

Les fourchettes représentent des ressources partagées.

32/73
2. Deadlock dans ce problème
Comment un deadlock peut survenir ?
1. Chaque philosophe prend d'abord la fourchette à gauche de sa place.

2. Ensuite, ils tentent de prendre la fourchette à droite.

3. Si chaque philosophe réussit à prendre la fourchette à gauche mais attend indéfiniment

la fourchette à droite (qui est prise par un autre philosophe), aucun ne peut progresser.

Exemple de scénario :

Philosophe 1 prend la fourchette 1.

Philosophe 2 prend la fourchette 2.

Philosophe 3 prend la fourchette 3.

Philosophe 4 prend la fourchette 4.

Philosophe 5 prend la fourchette 5.

Chaque philosophe attend maintenant que son voisin libère une fourchette pour
pouvoir manger. Cela ne se produit jamais, donc un deadlock se produit.

3. Conditions nécessaires pour un deadlock

Les quatre conditions nécessaires pour qu’un deadlock survienne sont les suivantes :

1. Mutual Exclusion (Exclusion Mutuelle) :

Une fourchette ne peut être tenue que par un seul philosophe à la fois.

2. Hold and Wait (Détenir et Attendre) :

Un philosophe détient une fourchette et attend l’autre.

3. No Preemption (Non-préemption) :

Une fourchette ne peut pas être forcée de revenir à son état libre.

4. Circular Wait (Attente Circulaire) :

33/73
 Une chaîne circulaire de philosophes attend des ressources détenues par leurs
voisins.

4. Solutions pour éviter le deadlock

A. Approches logicielles simples
1. Imposer un ordre strict pour prendre les fourchettes :

Chaque philosophe prend toujours la fourchette avec le numéro le plus bas en

premier, puis celle avec le numéro le plus élevé.

Cela brise l’attente circulaire.

Exemple :

void philosopher(int id) {

int left = id;
int right = (id + 1) % 5;

if (id % 2 == 0) { // Pair : prendre gauche, puis droite

pthread_mutex_lock(&forks[left]);
pthread_mutex_lock(&forks[right]);
} else { // Impair : prendre droite, puis gauche
pthread_mutex_lock(&forks[right]);
pthread_mutex_lock(&forks[left]);
}

// Manger
pthread_mutex_unlock(&forks[left]);
pthread_mutex_unlock(&forks[right]);
}

2. Autoriser jusqu’à N - 1 philosophes à manger simultanément :

34/73
 Limiter le nombre de philosophes autorisés à prendre les fourchettes.

Utiliser un sémaphore global pour garantir qu’au moins une fourchette reste
disponible.

Exemple avec sémaphore :

sem_t max_diners;

void philosopher(int id) {

int left = id;
int right = (id + 1) % 5;

sem_wait(&max_diners); // Vérifier si manger est autorisé

pthread_mutex_lock(&forks[left]);
pthread_mutex_lock(&forks[right]);

// Manger
pthread_mutex_unlock(&forks[left]);
pthread_mutex_unlock(&forks[right]);
sem_post(&max_diners); // Libérer la permission de manger
}

B. Approches sophistiquées
1. Un philosophe peut prendre les deux fourchettes simultanément :

Utiliser une seule opération atomique pour "prendre deux fourchettes".

Cette méthode élimine complètement l’attente circulaire.

2. Utiliser un arbitre (solution centralisée) :

Introduire un processus ou un thread arbitre.

Les philosophes demandent les deux fourchettes à l’arbitre, qui gère l’accès.

Exemple :

35/73
 pthread_mutex_t arbiter;

void philosopher(int id) {

int left = id;
int right = (id + 1) % 5;

pthread_mutex_lock(&arbiter);
pthread_mutex_lock(&forks[left]);
pthread_mutex_lock(&forks[right]);
pthread_mutex_unlock(&arbiter);

// Manger
pthread_mutex_unlock(&forks[left]);
pthread_mutex_unlock(&forks[right]);
}

5. Comparaison des solutions

Méthode Avantages Inconvénients

Ordre strict Simple à implémenter, évite Moins flexible dans des

le deadlock. systèmes complexes.

Limiter à N - 1 philosophes Facile à comprendre et Utilisation sous-optimale des

efficace. ressources.

Philosophe prend deux Élimine totalement le risque Difficile à implémenter sans

fourchettes atomiquement de deadlock. support matériel.

Arbitre Contrôle centralisé, évite le Point de contention, moins

deadlock. performant.

6. Conclusion
Le problème des philosophes illustre les défis pratiques des deadlocks dans la gestion des
ressources partagées. Plusieurs solutions existent pour éviter ces blocages, mais le choix de
la méthode dépend des contraintes et des exigences du système (performance, simplicité,

36/73
etc.). Une compréhension claire des conditions de deadlock permet de concevoir des
systèmes robustes et fiables.

Critical Region for

Bounded-Buffer
Problem

Problème du tampon limité (Bounded-Buffer Problem)

Le problème du tampon limité est un autre problème classique en programmation
concurrente. Il s'agit de synchroniser l'accès à un tampon de taille limitée partagé entre
plusieurs producteurs et consommateurs. L'objectif est d'éviter des erreurs de
synchronisation telles que des dépassements de tampon ou l'accès simultané aux mêmes
données.

Description du problème
1. Tampon partagé : Il existe un tampon de taille finie (ou un buffer), où les producteurs
déposent des éléments et où les consommateurs les retirent.

2. Producteurs : Les producteurs ajoutent des éléments dans le tampon.

3. Consommateurs : Les consommateurs retirent des éléments du tampon.

4. Problèmes potentiels :

Sur-remplissage : Si un producteur tente d'ajouter un élément dans un tampon déjà

plein.

Sous-remplissage : Si un consommateur tente de retirer un élément d'un tampon

vide.

5. Objectif : Assurer une synchronisation correcte pour éviter les erreurs mentionnées ci-
dessus tout en permettant aux producteurs et consommateurs de fonctionner en
parallèle.

Modélisation de la solution avec une région critique

Le problème implique une région critique où les producteurs et les consommateurs
accèdent au tampon. Il est crucial de synchroniser l'accès au tampon pour garantir l'intégrité
des données et éviter les conditions de course.

37/73
1. Conditions de synchronisation pour une région critique
Pour résoudre ce problème, nous devons respecter trois conditions :

1. Exclusion mutuelle : Un seul thread (producteur ou consommateur) peut accéder au

tampon à la fois.

2. Progrès : Si un producteur ou un consommateur est bloqué, un autre thread doit être en

mesure de continuer son travail.

3. Attente bornée : Aucun thread ne doit attendre indéfiniment pour accéder au tampon.

2. Solution avec un tampon limité (buffer)

Variables nécessaires :

Tampon : Une structure de données pour stocker les éléments (par exemple, un tableau
circulaire).

Index : Variables pour suivre la première position libre (pour les producteurs) et la
première position occupée (pour les consommateurs).

Sémaphores :

Un sémaphore empty pour indiquer le nombre de places libres dans le tampon.

Un sémaphore full pour indiquer le nombre d'éléments disponibles dans le

tampon.

Un mutex mutex pour garantir une exclusion mutuelle lors de l'accès au tampon.

Initialisation :

Le sémaphore empty est initialisé à la taille du tampon (indiquant qu'il y a autant

d'emplacements vides).

Le sémaphore full est initialisé à 0 (aucun élément n'est présent au début).

Le mutex mutex est initialisé à 1 pour permettre un accès exclusif au tampon.

Code pour le producteur :

38/73
 // Producteur
void producer() {
while (true) {
// Générer un élément à ajouter au tampon
item new_item = produce_item();

// Attendre qu'il y ait de la place dans le tampon

sem_wait(&empty); // Attente sur le sémaphore empty

// Accéder de manière exclusive au tampon

pthread_mutex_lock(&mutex);

// Ajouter l'élément dans le tampon

buffer[in] = new_item; // `in` est l'index où ajouter un élément
in = (in + 1) % BUFFER_SIZE;

// Libérer l'accès au tampon

pthread_mutex_unlock(&mutex);

// Signaler qu'il y a un élément disponible pour la consommation

sem_post(&full); // Incrémenter le sémaphore full
}
}

Code pour le consommateur :

// Consommateur
void consumer() {
while (true) {
// Attendre qu'il y ait un élément à consommer
sem_wait(&full); // Attente sur le sémaphore full

// Accéder de manière exclusive au tampon

pthread_mutex_lock(&mutex);

// Retirer l'élément du tampon

item consumed_item = buffer[out]; // `out` est l'index de lecture
out = (out + 1) % BUFFER_SIZE;

// Libérer l'accès au tampon

39/73
 pthread_mutex_unlock(&mutex);

// Consommer l'élément
consume_item(consumed_item);

// Signaler qu'il y a de la place dans le tampon

sem_post(&empty); // Incrémenter le sémaphore empty
}
}

3. Explication du code
1. Exclusion mutuelle :

Le mutex mutex garantit que l'accès au tampon est exclusif, donc un seul thread
(producteur ou consommateur) peut modifier le tampon à la fois.

2. Sémaphores empty et full :

empty indique combien de places libres il y a dans le tampon. Un producteur

attendra sur ce sémaphore s'il n'y a pas de place dans le tampon.

full indique combien d'éléments sont actuellement dans le tampon. Un

consommateur attendra sur ce sémaphore s'il n'y a pas d'éléments à consommer.

3. Progrès :

Si un producteur ou un consommateur est bloqué, un autre thread pourra continuer

à s'exécuter tant qu'il y a de la place ou des éléments dans le tampon.

4. Attente bornée :

Les sémaphores garantissent que les threads ne sont jamais bloqués indéfiniment.
Chaque thread aura une chance de s'exécuter en fonction de la disponibilité des
ressources.

4. Analyse des critères de synchronisation

40/73
 Critère État avec la solution proposée

Exclusion Assurée par le mutex mutex autour de l'accès au tampon.

mutuelle

Progrès Les producteurs et les consommateurs peuvent continuer dès qu'il y a de la place
ou des éléments disponibles.

Attente bornée Le sémaphore empêche l'attente infinie ; chaque thread aura une chance
d'accéder à la ressource.

5. Améliorations et autres solutions

Approche sans sémaphores : Il est possible d'utiliser des techniques comme les
moniteurs ou des méthodes atomiques (par exemple, compare-and-swap ) pour
simplifier la solution et éviter l'utilisation de sémaphores explicites.

Solutions optimisées : Si le problème devient très complexe (avec un nombre élevé de

producteurs et consommateurs), des techniques avancées comme les algorithmes lock-
free ou wait-free peuvent être appliquées pour améliorer l'efficacité.

6. Conclusion
Le problème du tampon limité est une illustration classique des concepts de région
critique, synchronisation et mutuelle exclusion en programmation concurrente.
L'utilisation de sémaphores et de mutexes permet de gérer efficacement l'accès concurrent
à des ressources partagées, garantissant ainsi l'intégrité des données et le bon
fonctionnement du système.

Monitors

Monitors

Monitors

41/73
Un monitor (moniteur en français) est une abstraction de haut niveau utilisée pour la
synchronisation et la gestion de l'accès aux ressources partagées dans les systèmes
concurrentiels. Il est conçu pour simplifier la gestion des sections critiques en fournissant
une manière structurée de contrôler l'accès simultané à des ressources partagées tout en
garantissant la mutual exclusion (exclusion mutuelle) et la synchronisation.

Les moniteurs sont utilisés dans des langages de programmation comme Java ou Erlang, et
font partie d'une approche plus moderne de la synchronisation par rapport aux techniques
basées sur des verrous explicites, comme les mutexes et sémaphores.

1. Définition d’un Moniteur

Un monitor est une structure de données qui comprend :

Des variables partagées (ressources partagées, données à manipuler).

Des procédures ou méthodes qui permettent de manipuler ces données de manière

exclusive.

Des mécanismes de synchronisation, comme des conditions qui permettent de

bloquer et réveiller des threads en fonction des états des variables partagées.

Les moniteurs sont un moyen d’encapsuler la gestion des verrous et de la synchronisation

dans des structures haut-niveau qui simplifient la programmation concurrente.

2. Composants d’un Moniteur

Un moniteur se compose de trois éléments principaux :

1. Variables internes :

Les variables partagées qui sont protégées par le moniteur (par exemple, un
tampon partagé, une liste, etc.).

2. Procédures ou méthodes :

Les opérations que les threads peuvent appeler pour manipuler les variables
partagées. Ces méthodes sont l'unique moyen pour les threads d’interagir avec les

42/73
 ressources protégées.

3. Conditions :

Les conditions permettent à un thread de se suspendre en attendant un événement

spécifique (par exemple, un autre thread libère une ressource). Elles sont souvent
utilisées pour implémenter des mécanismes d'attente ou de notification
(signalement) dans les moniteurs.

Les deux principales opérations de condition sont :

wait() : Un thread appelle cette méthode pour suspendre son exécution, libérer le
verrou du moniteur et attendre qu'une condition spécifique soit remplie.

signal() ou notify() : Un thread appelle cette méthode pour réveiller un autre thread
en attente.

3. Propriétés d’un Moniteur

Exclusion mutuelle :

Un seul thread peut exécuter une procédure dans le moniteur à la fois, garantissant
ainsi que l'accès aux variables partagées est exclusif.

Synchronisation entre threads :

Grâce aux conditions (comme wait() et signal() ), les threads peuvent être
synchronisés de manière flexible, en fonction de l'état des variables partagées.

Sécurité :

L’utilisation de moniteurs aide à éviter les erreurs courantes dans les systèmes
concurrents, telles que les conditions de course, les deadlocks, et les starvations,
en gérant explicitement l'accès concurrent.

4. Exemple de Moniteur en Java

Java prend en charge les moniteurs via l'utilisation de synchronisation. En Java, chaque objet
dispose implicitement d’un moniteur associé, et la synchronisation des méthodes ou des

43/73
blocs de code est réalisée à l’aide du mot-clé synchronized .

Voici un exemple simple de moniteur en Java pour un compteur partagé :

java

class Counter {
private int count = 0;

// Méthode synchronisée pour garantir un accès exclusif

public synchronized void increment() {
count++;
}

public synchronized int getCount() {

return count;
}
}

Explication :

Le mot-clé synchronized sur les méthodes garantit que seul un thread peut exécuter
increment() ou getCount() à la fois, empêchant ainsi les conditions de course.

Si un thread appelle increment() , tout autre thread qui appelle l'une des méthodes
synchronisées doit attendre que le premier termine son exécution.

5. Moniteurs avec Conditions en Java

En Java, on peut également utiliser les méthodes wait() , notify() et notifyAll() pour
mettre en œuvre des conditions dans un moniteur.

Voici un exemple de moniteur de type producteur-consommateur avec conditions :

java

class BoundedBuffer {
private int[] buffer = new int[10];
private int count = 0;
private int in = 0;
private int out = 0;

44/73
 // Méthode pour ajouter un élément dans le tampon
public synchronized void produce(int item) throws InterruptedException {
while (count == [Link]) {
wait(); // Attendre si le tampon est plein
}
buffer[in] = item;
in = (in + 1) % [Link];
count++;
notifyAll(); // Réveiller les consommateurs
}

// Méthode pour retirer un élément du tampon

public synchronized int consume() throws InterruptedException {
while (count == 0) {
wait(); // Attendre si le tampon est vide
}
int item = buffer[out];
out = (out + 1) % [Link];
count--;
notifyAll(); // Réveiller les producteurs
return item;
}
}

Explication :

produce(int item) : Un producteur ajoute un élément dans le tampon. Si le tampon est

plein ( count == [Link] ), il appelle wait() pour se mettre en attente jusqu'à ce
qu'il y ait de la place.

consume() : Un consommateur retire un élément du tampon. Si le tampon est vide

( count == 0 ), il appelle wait() pour se mettre en attente jusqu'à ce qu'il y ait un
élément à consommer.

notifyAll() : Réveille tous les threads en attente (producteurs ou consommateurs), les

informant qu'ils peuvent continuer.

6. Avantages des Moniteurs

45/73
 Simplicité :

L'utilisation des moniteurs abstrait la complexité de la synchronisation des

ressources partagées. Les développeurs n'ont pas besoin de se soucier de
l'acquisition et de la libération manuelle des verrous comme avec les mutex.

Exclusion mutuelle et synchronisation :

Ils combinent l'exclusion mutuelle et la synchronisation entre threads dans un

mécanisme intégré et sûr.

Moins d'erreurs humaines :

Les moniteurs simplifient la gestion des conditions complexes (attente,

signalisation, etc.), réduisant ainsi les risques d'erreurs telles que les deadlocks ou
les conditions de course.

7. Inconvénients des Moniteurs

Performances :

Dans certains cas, l'utilisation des moniteurs peut entraîner une surcharge en raison
de la gestion des conditions et de l'accès exclusif.

Verrouillage global :

Le verrouillage d'un moniteur empêche plusieurs threads d'exécuter des méthodes

simultanément, ce qui peut nuire aux performances dans les systèmes fortement
concurrents.

Verrouillage fin :

Les moniteurs sont généralement utilisés pour des verrous de niveau global sur un
objet. Cela peut être trop restrictif pour certaines situations où un verrouillage plus
granulaire est nécessaire.

8. Conclusion
Les moniteurs sont une abstraction puissante pour gérer la synchronisation dans les
systèmes concurrents. En encapsulant les données partagées et en fournissant un

46/73
mécanisme intégré de gestion des verrous et des conditions, les moniteurs rendent la
programmation concurrente plus facile, plus sécurisée, et plus lisible. Toutefois, ils doivent
être utilisés judicieusement pour éviter des problèmes de performances dans des systèmes
très concurrentiels.

definition de thread

2/2

Définition de Thread
Un thread (ou fil d'exécution en français) est la plus petite unité d'exécution d'un
programme. Un thread permet à un programme de réaliser plusieurs tâches simultanément
en partageant les mêmes ressources du programme, comme la mémoire et les variables
globales, mais en exécutant des instructions indépendantes.

Un programme peut avoir un seul thread (c'est-à-dire être monothread), ou plusieurs

threads (multithread), ce qui permet d'effectuer plusieurs opérations en parallèle ou de
manière concurrente.

Caractéristiques d'un Thread

1. Exécution :

Un thread représente une séquence d'exécution dans un programme. Il contient son

propre compteur ordinal (qui garde une trace de l'endroit où l'exécution s'est
arrêtée), un ensemble de registres et un pointeur de pile.

2. Contexte d'exécution :

Chaque thread a son propre contexte d'exécution, mais il partage une grande
partie de l'état du programme principal (comme la mémoire du programme, les
fichiers ouverts, etc.).

3. Partage des ressources :

Les threads d'un même programme partagent la même mémoire et d'autres

ressources, ce qui facilite la communication entre eux. Cependant, cela peut
entraîner des problèmes de synchronisation s'ils accèdent simultanément aux
mêmes ressources partagées.

47/73
4. Indépendance :

Les threads d'un programme s'exécutent indépendamment les uns des autres.
Cependant, dans un programme multithreadé, plusieurs threads peuvent travailler
sur des tâches différentes simultanément, ce qui améliore la performance du
programme, notamment sur des systèmes multiprocesseurs.

Types de Threads
1. Threads Utilisateur (User Threads) :

Ce sont des threads gérés par une bibliothèque d'exécution au niveau du

programme. Le système d'exploitation ne les connaît pas directement, et c'est le
programme qui gère leur planification. Cependant, ces threads peuvent ne pas tirer
parti des systèmes multiprocesseurs si l'OS ne gère pas leur exécution de manière
optimisée.

2. Threads Noyau (Kernel Threads) :

Ce sont des threads gérés directement par le système d'exploitation. Chaque thread
utilisateur est mappé à un thread noyau, et c'est l'OS qui planifie leur exécution. Ces
threads peuvent être exécutés sur différents processeurs dans un système
multiprocesseur.

3. Threads Hybrides :

Ce modèle combine les threads utilisateur et noyau, où certains threads sont gérés
par la bibliothèque d'exécution, mais le système d'exploitation prend aussi en
charge certains aspects de leur gestion.

Avantages des Threads

1. Exécution concurrente :

Les threads permettent l'exécution simultanée de plusieurs parties d'un

programme, ce qui est particulièrement utile pour les applications nécessitant des
calculs parallèles ou pour répondre à des événements en temps réel.

48/73
 2. Partage des ressources :

Les threads d'un même programme peuvent partager les mêmes ressources
mémoire et variables globales, ce qui facilite la communication entre eux par
rapport aux processus indépendants.

3. Réactivité :

Dans les applications interactives (comme les interfaces utilisateur), l'utilisation de

threads permet de maintenir la réactivité de l'application tout en exécutant des
tâches en arrière-plan (comme le téléchargement de fichiers ou le traitement de
données).

Problèmes associés aux Threads

1. Conditions de course (Race Conditions) :

Lorsque plusieurs threads accèdent à des ressources partagées sans une gestion
correcte de la synchronisation, cela peut entraîner des résultats imprévisibles. Par
exemple, deux threads qui modifient une même variable en même temps peuvent
causer des incohérences dans les données.

2. Deadlock (Interblocage) :

Si deux ou plusieurs threads attendent indéfiniment que d'autres libèrent des

ressources nécessaires pour continuer leur exécution, cela peut provoquer un
deadlock.

3. Starvation (Étoile filante) :

Un ou plusieurs threads peuvent se voir refuser l'accès aux ressources par un autre
thread indéfiniment, ce qui peut entraîner leur "famine" (starvation).

Exemple de Thread en Java

En Java, un thread peut être créé de deux manières :

1. En étendant la classe Thread .

2. En implémentant l'interface Runnable .

49/73
Exemple avec Thread :

java

class MyThread extends Thread {

public void run() {
[Link]("Le thread est en exécution !");
}

public static void main(String[] args) {

MyThread t = new MyThread();
[Link](); // Démarre le thread
}
}

Exemple avec Runnable :

java

class MyRunnable implements Runnable {

public void run() {
[Link]("Le thread est en exécution !");
}

public static void main(String[] args) {

MyRunnable task = new MyRunnable();
Thread t = new Thread(task);
[Link](); // Démarre le thread
}
}

Conclusion
Un thread est une unité fondamentale d'exécution dans un programme. La gestion des
threads est essentielle pour créer des applications multithreadées performantes et
réactives. L'utilisation des threads permet de tirer parti des systèmes multiprocesseurs et
d'améliorer la réactivité des applications en permettant à plusieurs tâches de s'exécuter en

50/73
parallèle. Cependant, leur gestion doit être effectuée avec précaution pour éviter des
problèmes tels que les conditions de course, les deadlocks, et la starvation.

solution a temp active

2/2

Solution à Temporisation Active (Busy Waiting)

La temporisation active (ou busy waiting) est une technique utilisée pour synchroniser
l'exécution de plusieurs processus ou threads dans un système concurrent. Elle consiste à
faire attendre un processus ou un thread en effectuant un cycle d’exécution constant jusqu’à
ce qu’une condition soit remplie, plutôt que de se suspendre ou de relâcher le processeur.

Principe
Un thread ou un processus vérifie constamment une condition dans une boucle, en utilisant
des instructions répétées (comme while ) pour déterminer si la ressource ou l'état qu'il
attend devient disponible. Pendant cette vérification, le thread ne fait aucun travail utile, ce
qui peut entraîner une consommation inutile de ressources processeur.

Exemple
Un exemple classique de temporisation active est une boucle while qui vérifie si une
variable partagée est mise à jour :

while (flag == 0) {
// Boucle d'attente active
}

Dans cet exemple :

La boucle vérifie continuellement si flag est passé à 1.

Pendant ce temps, le thread ne fait rien d'autre qu'occuper le processeur.

51/73
Problèmes de la Temporisation Active
1. Utilisation inefficace du processeur :

Le thread en attente consomme du temps CPU sans accomplir de travail utile, ce qui
peut ralentir l'ensemble du système, surtout dans les environnements à ressources
limitées.

2. Scalabilité limitée :

Dans les systèmes multithread ou multiprocesseurs, la temporisation active peut

créer une surcharge importante si plusieurs threads utilisent cette méthode.

3. Augmentation de la consommation d'énergie :

En maintenant le processeur actif en permanence, la temporisation active augmente

la consommation d'énergie, ce qui est problématique dans les systèmes embarqués
ou les appareils fonctionnant sur batterie.

Situations où la Temporisation Active est Utilisée

Malgré ses inconvénients, la temporisation active peut être utile dans certaines situations
spécifiques :

1. Latence très faible :

Lorsque le coût de passer d’un état d’exécution à un état suspendu est plus élevé
que celui de rester actif (par exemple, dans les systèmes en temps réel ou avec des
délais très courts).

2. Systèmes matériels spécifiques :

Dans certains environnements matériels (comme les pilotes de périphériques), la

temporisation active peut être utilisée pour attendre des états précis.

3. Éviter des interblocages simples :

Dans certains cas, une attente active peut être utilisée pour éviter des conditions
complexes comme les interblocages.

52/73
Solutions Alternatives
Pour éviter les inconvénients de la temporisation active, plusieurs alternatives existent :

1. Sémaphores ou Mutex :

Ces mécanismes permettent à un thread de se suspendre jusqu'à ce qu'une

condition soit remplie, libérant ainsi le processeur pour d'autres tâches.

Exemple en pseudocode avec un sémaphore :

wait(semaphore); // Bloque le thread jusqu'à ce que le sémaphore soit

disponible

2. Signaux ou Interruptions :

Les threads ou processus peuvent être réveillés lorsqu'une condition est remplie via
un signal ou une interruption.

3. Attente passive avec Sleep :

Utiliser une méthode comme sleep() pour suspendre le thread pendant un

intervalle de temps donné.

Exemple :

while (flag == 0) {
sleep(1); // Pause de 1 seconde avant de vérifier à nouveau
}

4. Verrous avec Conditions :

Les threads peuvent attendre une condition spécifique avec des mécanismes
comme wait() et notify() dans les moniteurs.

Optimisation de la Temporisation Active

Si la temporisation active est absolument nécessaire, elle peut être optimisée pour réduire
son impact négatif :

53/73
 1. Utilisation de délais :

Introduire de petites pauses (par exemple, sleep() ou yield() ) dans la boucle

d'attente pour libérer le processeur périodiquement.

Exemple :

while (flag == 0) {
sched_yield(); // Cède le processeur à d'autres threads
}

2. Réduction de la priorité :

Exécuter le thread en attente active avec une priorité plus faible pour minimiser son
impact sur les autres tâches du système.

Conclusion
La temporisation active est une solution simple mais inefficace pour gérer la synchronisation
dans les systèmes concurrents. Elle est généralement remplacée par des solutions plus
avancées comme les sémaphores, les mutex, ou les interruptions pour améliorer l'efficacité
et la scalabilité. Toutefois, elle peut être utile dans des situations spécifiques où la latence et
la simplicité priment sur l'efficacité.

Solutions logicielles pour deux processus Solution 1 : Cette

solution consiste à laisser les deux processus partager une
variable entière
commune turn, initialisée à 0 (ou 1). Si la valeur de turn=i,
alors on permet au processus Pi d’exécuter
sa SC. Voici l’algorithme de cette solution : Le problème de
la solution 1 est qu’elle ne garde pas suffisamment
d’informations sur l’état de chaque
processus ; elle se rappelle seulement quel processus est
autorisé à entrer en SC. Pour remédier à ce
problème, nous pouvons remplacer la variable Turn par le
tableau suivant :

54/73
 Etat : Tableau[0..1] de Booléen.
Le tableau est initialisé à Faux. Si Etat[i] est Vrai, cette
valeur indique que le processus Pi est prêt pour
entrer en SC.
L’algorithme de la solution est : expliquer

Solutions logicielles pour deux processus

Dans les problèmes de synchronisation des processus, on cherche à garantir que deux
processus ne puissent pas entrer simultanément dans leur Section Critique (SC). Voici deux
solutions logicielles courantes pour gérer ce problème.

Solution 1 : Variable Commune turn

Principe

Une variable entière partagée turn est utilisée pour indiquer quel processus est
autorisé à entrer en SC.

La variable turn peut prendre deux valeurs :

turn = 0 : Le processus P0 est autorisé à entrer en SC.

​

turn = 1 : Le processus P1 est autorisé à entrer en SC.

​

Algorithme

1. Entrée en SC :

Chaque processus vérifie si la valeur de turn correspond à son identifiant.

Si ce n'est pas le cas, il attend (boucle d'attente active).

2. Sortie de SC :

Lorsqu'un processus quitte la SC, il attribue la valeur de turn à l'autre processus

pour lui permettre d'accéder à la SC.

Code Pseudocode

Pour le processus Pi : ​

55/73
 while (turn != i) {
// Attente active
}
// Section critique (SC)
// ...
turn = 1 - i; // Permet à l'autre processus d'entrer

Problèmes de la Solution 1

1. Faible état d'information :

La variable turn ne contient pas suffisamment d'informations sur l'état des

processus. Elle ne mémorise que le processus autorisé à entrer en SC, sans tenir
compte de l'intention ou de l'état des processus.

2. Équité limitée :

Cette solution impose une alternance stricte entre les processus. Si un processus n'a
pas besoin d'accéder à la SC, l'autre doit quand même attendre son tour, même si la
SC est libre.

3. Condition de Progrès non garantie :

Si un processus n'est pas actif, l'autre peut rester bloqué inutilement.

Solution 2 : Tableau d'États

Principe

On remplace la variable turn par un tableau Etat qui mémorise l'intention de chaque
processus d'entrer en SC.

Le tableau Etat[0..1] est initialisé à Faux .

Etat[i] = Vrai signifie que le processus Pi est prêt à entrer en SC.

​

Etat[i] = Faux signifie que le processus Pi n'est pas intéressé par la SC pour le
​

moment.

56/73
Algorithme

1. Entrée en SC :

Le processus Pi déclare son intention en mettant Etat[i] = Vrai .

​

Il vérifie ensuite si l'autre processus (P1−i ) n'est pas dans un état où il veut entrer en
​

SC.

2. Sortie de SC :

Le processus Pi réinitialise Etat[i] = Faux pour signaler qu'il quitte la SC.

​

Code Pseudocode

Pour le processus Pi : ​

Etat[i] = Vrai; // Déclare son intention d'entrer en SC

while (Etat[1 - i]) {
// Attente active : attend que l'autre processus ne veuille plus entrer
}
// Section critique (SC)
// ...
Etat[i] = Faux; // Quitte la SC

Comparaison des Deux Solutions

Critère Solution 1 (turn) Solution 2 (Etat)

Exclusion mutuelle Assurée Assurée

Progrès Non garanti si un processus est inactif Garanti

Attente bornée Non garanti (alternance stricte) Garanti

Complexité Simple Légèrement plus complexe

État des processus Ne tient pas compte des intentions Suit les intentions des processus

Conclusion

57/73
La Solution 2 (Etat) est une amélioration significative par rapport à la Solution 1 (turn), car
elle permet de mieux gérer l'état des processus et de garantir le progrès. Cependant, elle
repose toujours sur une forme de temporisation active, ce qui peut être inefficace. Des
solutions avancées, comme les sémaphores ou les moniteurs, permettent d'éliminer ce
problème.

Dans cette solution, le processus Pi fixe d’abord Etat[i] à

Vrai, signalant ainsi qu’il est prêt à entrer en
SC. Ensuite, Pi vérifie l’état du processus Pj en consultant la
valeur de Etat[j]. Le processus Pi attend
alors jusqu’à ce que le processus Pj lui indique qu’il n’a plus
besoin d’entrer dans sa SC (c’est à dire
jusqu’à ce que la valeur de Etat[j] devienne fausse). A ce
moment là , le processus Pi entre dans sa
SC. En sortant de sa SC, Pi remet son état à Faux,
permettant à l’autre processus d’entrer
éventuellement en SC.
Commentaire : Dans cette solution, le principe de
l’exclusion mutuelle est respecté . Toutefois, un
problème se pose si les deux processus mettent leur état à
Vrai, puis vont , chacun, itérer sur la
vérification de l’état de l’autre processus. On assiste ainsi à
une boucle sans fin pour les deux

Analyse de la Solution avec le Tableau d'États

Dans cette solution, chaque processus utilise un tableau partagé Etat[0..1] pour signaler
son intention d'entrer en Section Critique (SC). Bien que le principe de l'exclusion mutuelle
soit respecté, cette méthode présente un problème de blocage mutuel (deadlock potentiel),
comme décrit ci-dessous.

Étapes de Fonctionnement
1. Déclaration d'intention :

Le processus Pi met Etat[i] = Vrai , indiquant qu'il veut accéder à la SC.

​

2. Vérification de l'autre processus :

58/73
 Pi vérifie si l'autre processus (Pj ) est prêt à entrer dans sa SC en consultant
​ ​

Etat[j] .

Si Etat[j] est Faux, Pi entre dans la SC.

​

Sinon, Pi reste bloqué dans une boucle d'attente active jusqu'à ce que Etat[j]
​

devienne Faux.

3. Sortie de la SC :

Lorsqu'il termine sa SC, Pi remet Etat[i] = Faux , signalant qu'il ne souhaite plus
​

accéder à la SC, permettant ainsi à Pj d'entrer.

​

Problème : Boucle Sans Fin (Deadlock)

Scénario Problématique

1. Les deux processus P0 et P1 exécutent simultanément leurs instructions pour entrer en

​ ​

SC :

P0 fixe
​ Etat[0] = Vrai .

P1 fixe
​ Etat[1] = Vrai .

2. Les deux processus vérifient l'état de l'autre :

P0 voit que
​ Etat[1] = Vrai et entre dans une boucle d'attente.

P1 voit que
​ Etat[0] = Vrai et entre également dans une boucle d'attente.

3. Aucun des deux processus ne remet son état à Faux, car ils attendent indéfiniment que
l'autre processus le fasse.

Solution au Problème
Le problème se produit en raison d'un manque de coordination entre les deux processus
lorsque les deux déclarent simultanément vouloir entrer dans la SC. Une amélioration
courante consiste à introduire un mécanisme de priorité pour briser cette situation
d'interblocage.

Amélioration : Algorithme de Peterson

59/73
L'algorithme de Peterson ajoute une variable supplémentaire appelée turn pour gérer les
priorités entre les deux processus. Voici le principe :

1. Chaque processus continue d'utiliser le tableau Etat pour signaler son intention
d'entrer dans la SC.

2. Une variable turn indique quel processus doit avoir la priorité en cas de conflit.

Algorithme de Peterson

Pour le processus Pi : ​

Etat[i] = Vrai; // Déclare son intention d'entrer

turn = j; // Donne la priorité à l'autre processus
while (Etat[j] && turn == j) {
// Attente active
}
// Section critique (SC)
// ...
Etat[i] = Faux; // Quitte la SC

Comment cela résout le problème ?

1. Lorsque les deux processus déclarent simultanément vouloir entrer dans la SC ( Etat[0]
= Vrai et Etat[1] = Vrai ), la variable turn décide lequel des deux doit attendre.

2. Par exemple :

Si turn = 1, P0 attendra, et P1 pourra entrer dans la SC.

​ ​

Une fois que P1 termine sa SC, il remet Etat[1] = Faux , permettant ainsi à P0 ​

d'entrer.

3. Cela évite la situation de boucle infinie, car au moins un des processus pourra
progresser.

60/73
Conclusion
Dans la solution initiale, bien que l'exclusion mutuelle soit respectée, elle est vulnérable au
problème de blocage mutuel. En ajoutant une variable de priorité comme dans l'algorithme
de Peterson, on peut garantir :

Exclusion mutuelle : Un seul processus est dans la SC à un instant donné.

Progrès : Aucun processus n'attend indéfiniment si la SC est disponible.

Attente bornée : Chaque processus finit par accéder à la SC en temps raisonnable.

Critical Region

Critical Region (Région Critique)

Définition

Une région critique est une section du code dans un programme où plusieurs processus ou
threads accèdent simultanément à des ressources partagées, telles que des variables, des
fichiers ou des périphériques. L'objectif est de s'assurer que l'accès concurrent à ces
ressources est sûr et cohérent.

Dans une région critique, il est crucial d'éviter des situations telles que :

Conditions de concurrence : Lorsque plusieurs processus modifient une ressource

simultanément, cela peut entraîner des résultats imprévisibles.

Incohérence des données : Des modifications concurrentes peuvent corrompre l'état

des ressources partagées.

Caractéristiques d'une Région Critique

Pour qu'une région critique soit correctement gérée, les propriétés suivantes doivent être
garanties :

1. Exclusion Mutuelle :

Une seule entité (processus ou thread) peut accéder à la région critique à la fois.

2. Progrès :

Si plusieurs processus souhaitent entrer dans la région critique, l'un d'eux doit être
autorisé à entrer dans un délai raisonnable.

61/73
 3. Attente Bornée :

Aucun processus ne devrait attendre indéfiniment pour accéder à la région critique.

4. Indépendance de la vitesse :

Le comportement de la solution ne doit pas dépendre de la vitesse ou du nombre de

processeurs.

Problèmes Associés
1. Deadlock (Interblocage) :

Lorsque plusieurs processus attendent mutuellement l'accès à des ressources,

aucun ne progresse.

2. Starvation (Famine) :

Lorsqu'un processus est indéfiniment retardé dans l'attente de la région critique,

généralement à cause de l'attribution prioritaire à d'autres processus.

3. Conditions de concurrence :

Si deux ou plusieurs processus modifient simultanément une variable partagée sans

coordination, les résultats peuvent être imprévisibles.

Solutions pour Gérer les Régions Critiques

1. Solutions Logicielles

Utilisation d'algorithmes pour synchroniser les processus sans recours au matériel.

Exemples :

Algorithme de Peterson : Utilise une combinaison de drapeaux (flags) pour signaler

l'intention d'entrer dans la région critique et une variable turn pour gérer la priorité.

Algorithme de Dekker : Utilise des indicateurs pour assurer l'exclusion mutuelle dans un
environnement à deux processus.

62/73
2. Solutions Matérielles

Utilisation d'instructions matérielles pour gérer l'exclusion mutuelle.

Exemples :

Test-and-Set : Une instruction atomique qui vérifie et modifie une variable en une seule
opération.

Compare-and-Swap : Une autre instruction atomique utilisée pour gérer les ressources
critiques.

3. Mécanismes Système

Les systèmes d'exploitation fournissent des outils pour gérer les régions critiques,
souvent basés sur des primitives de synchronisation.

Exemples :

Mutex (Mutual Exclusion) : Verrous binaires qui permettent à un seul processus

d'accéder à la région critique.

Sémaphores : Objets de synchronisation qui permettent de gérer l'accès à des

ressources partagées avec plus de flexibilité (compteurs).

Moniteurs : Structures de données qui combinent données partagées et mécanismes de

verrouillage pour garantir une synchronisation sécurisée.

Exemple
Supposons deux processus qui doivent accéder à une variable partagée :

Sans gestion de région critique (résultat imprévisible) :

int counter = 0;

void increment() {

63/73
 counter = counter + 1; // Problème si exécuté simultanément par deux processus
}

Avec Mutex (résultat sécurisé) :

int counter = 0;
pthread_mutex_t lock;

void increment() {
pthread_mutex_lock(&lock); // Verrouillage
counter = counter + 1; // Accès sécurisé
pthread_mutex_unlock(&lock); // Déverrouillage
}

Conclusion
Une région critique est essentielle pour assurer une coordination correcte entre les
processus ou threads qui accèdent à des ressources partagées. Grâce à des mécanismes
logiciels et matériels adaptés, les risques d'incohérence des données, d'interblocages ou de
famine peuvent être minimisés.

deffirence entre Critical Region et sectoin critique

La Critical Region (région critique) et la Section Critique (SC) sont deux concepts proches en
programmation concurrente, mais ils diffèrent par leur portée et leur formalisation. Voici
une comparaison claire entre les deux :

1. Définition
Termes Critical Region Section Critique

Définition C'est un concept plus général pour gérer Une partie spécifique d'un programme
l'accès concurrent aux ressources où une ressource partagée est modifiée

64/73
 Termes Critical Region Section Critique

partagées. ou utilisée.

Portée En général, il s'agit d'une méthode ou d'une Il s'agit d'une portion de code
structure intégrée pour protéger les spécifique qui doit être protégée contre
ressources partagées. l'accès concurrent.

2. Niveau d'Abstraction
Critical Region Section Critique

Fournit un cadre abstrait pour gérer la synchronisation, Désigne une zone de code concrète où
souvent via des mécanismes comme des moniteurs. une ressource partagée est manipulée.

3. Concept vs Implémentation
Critical Region Section Critique

Implémente le concept d'exclusion mutuelle Nécessite une gestion explicite par le programmeur,
avec des abstractions de haut niveau (ex. : souvent avec des primitives comme des mutex ou des
moniteurs). sémaphores.

4. Exemples

Critical Region

Décrit dans un cadre structuré ou via des mécanismes comme les moniteurs :

monitor ExampleMonitor {
void accessCriticalResource() {
// Gestion automatique de l'accès à la ressource partagée

65/73
 }
}

Section Critique

Partie précise de code manipulant une ressource partagée, protégée avec un mutex ou
un sémaphore :

pthread_mutex_lock(&mutex);
// Section Critique
sharedResource++;
pthread_mutex_unlock(&mutex);

5. Comparaison des Propriétés

Propriétés Critical Region Section Critique

Abstraction Approche de haut niveau pour gérer les Nécessite une gestion explicite par le
ressources. programmeur.

Sécurité Généralement gérée par le système (ex. : Dépend des primitives utilisées (mutex,
moniteurs). sémaphores).

Complexité Moins complexe pour le programmeur. Peut nécessiter une gestion manuelle
complexe.

Résumé
Point clé Critical Region Section Critique

Concept ou Concept abstrait Implémentation concrète

implémentation

Gestion de Automatique via des abstractions Explicite avec des primitives

synchronisation (moniteurs). (mutex, etc.).

66/73
 Point clé Critical Region Section Critique

Utilisation courante Gérée par le système d'exploitation ou Partie spécifique du code à

une bibliothèque. protéger.

En résumé, une Critical Region est un concept abstrait qui peut inclure des Sections
Critiques, mais elle les gère automatiquement à un niveau supérieur d'abstraction. Une
Section Critique, en revanche, est une zone concrète du programme qui nécessite une
gestion explicite pour éviter les conflits.

Synchronization
In Window
❏ Uses interrupt masks to protect access to global
resources on uniprocessor systems
❏ Uses spinlocks on multiprocessor systems
❏ Spinlocking-thread will never be preempted expilquer
en francis

❏ Also provides dispatcher objects user-land which may

act mutexes, semaphores, events, and timers
❏ Events
❏ An event acts much like a condition
variable
❏ Timers notify one or more thread when time
expired
❏ Dispatcher objects either signaled-state
(object available) or non-signaled state
(thread will block)

2/2

Synchronisation sous Windows

Le système d'exploitation Windows fournit divers mécanismes de synchronisation pour gérer
l'accès concurrent aux ressources partagées, en fonction de l'architecture et du scénario.
Voici une explication détaillée en français :

Synchronisation dans les systèmes Windows

1. Gestion des ressources globales sur des systèmes uniprocesseurs :

67/73
 Windows utilise des masques d'interruption pour protéger l'accès aux ressources
globales.

Comment ça fonctionne :

Les interruptions sont temporairement désactivées pour empêcher les contextes

d'interruption ou d'autres threads de perturber un thread qui accède à une
ressource partagée.

Cela garantit une exclusion mutuelle, mais est limité aux systèmes à processeur
unique.

2. Gestion des ressources globales sur des systèmes multiprocesseurs :

Windows utilise des spinlocks (verrous tournants).

Spinlocks :

Ce sont des mécanismes de synchronisation où un thread attend de manière active

(boucle d'attente) qu'un verrou devienne disponible.

Caractéristique importante : Un thread utilisant un spinlock ne sera jamais

préempté (interrompu et remplacé par un autre thread). Cela garantit qu'il peut
conserver le contrôle jusqu'à ce qu'il termine son travail critique.

3. Objets du répartiteur (Dispatcher Objects) dans l'espace utilisateur :

Windows offre des dispatcher objects dans l'espace utilisateur, qui fonctionnent comme
des mécanismes de synchronisation.
Ces objets incluent :

Mutex (Mutual Exclusion) : Garantit qu'un seul thread accède à une ressource
partagée.

Sémaphores : Permettent à plusieurs threads d'accéder à une ressource partagée

avec des limites.

Événements : Fonctionnent comme des variables de condition pour synchroniser les

threads.

68/73
 Minuteries (Timers) : Notifications aux threads après l'expiration d'un délai spécifié.

4. Événements (Events) :

Les événements dans Windows sont comparables aux variables de condition utilisées
en programmation concurrente.

Un événement peut être signalé ou non signalé :

Signalé (Signaled-State) : L'objet est disponible, permettant à un thread de

poursuivre son exécution.

Non signalé (Non-Signaled State) : L'objet n'est pas disponible, forçant un

thread à attendre.

Cela permet une coordination précise entre plusieurs threads.

5. Minuteries (Timers) :

Les minuteries servent à :

Notifier un ou plusieurs threads lorsque le délai spécifié est écoulé.

Elles sont utilisées pour planifier des tâches ou pour des mécanismes de
synchronisation basés sur le temps.

Résumé
Systèmes uniprocesseurs : Utilisation de masques d'interruption pour empêcher les
conflits lors de l'accès à des ressources partagées.

Systèmes multiprocesseurs : Utilisation de spinlocks pour gérer la synchronisation,

garantissant qu'un thread n'est pas préempté.

Dispatcher Objects : Fournissent des primitives de synchronisation (mutex,

sémaphores, événements, minuteries) dans l'espace utilisateur.

69/73
 Événements et minuteries : Facilitent la coordination et la synchronisation des threads
en fonction des états (signalé/non signalé) ou du temps.

Ces mécanismes permettent à Windows de gérer efficacement la concurrence dans des

environnements complexes.

Synchronization
In Linux
❏ Linux:
❏ Prior to kernel Version 2.6, disables interrupts
to implement short critical sections
❏ Version 2.6 and later, fully preemptive
❏ Linux provides:
❏ Semaphores
❏ atomic integers
❏ Spinlocks
❏ reader-writer versions of both
❏ Critical regions
❏ On single-cpu system, spinlocks replaced by expliquer
en francis

Synchronisation sous Linux

Linux fournit plusieurs mécanismes pour gérer la synchronisation entre les threads et les
processus, en s'adaptant à l'évolution des versions du noyau et des architectures matérielles.
Voici une explication détaillée :

1. Gestion de la synchronisation avant la version 2.6 du noyau

Avant la version 2.6 du noyau Linux, les interruptions étaient désactivées
temporairement pour protéger les sections critiques (parties du code accédant à des
ressources partagées).

Pourquoi ?

Cela garantissait qu'aucun autre processus ou interruption ne puisse perturber

l'accès à la ressource partagée pendant une section critique.

Cette méthode était efficace pour les systèmes uniprocesseurs, car il n'y avait qu'un
seul processeur à gérer.

70/73
2. Synchronisation dans les versions 2.6 et ultérieures
Depuis la version 2.6, Linux est devenu entièrement préemptif :

Cela signifie qu'un thread ou un processus peut être interrompu à presque tout
moment, même dans le noyau, sauf dans des cas particuliers comme les spinlocks.

Cette préemption a amélioré la réactivité du système, particulièrement pour les

systèmes multiprocesseurs (SMP).

3. Mécanismes de synchronisation fournis par Linux

a. Sémaphores

Les sémaphores sont utilisés pour contrôler l'accès à une ressource partagée par
plusieurs threads ou processus.

Principe : Un compteur limite le nombre de threads pouvant accéder

simultanément à une ressource.

Utile pour les scénarios où plusieurs threads doivent accéder à une ressource, mais
en nombre limité.

b. Entiers atomiques

Les entiers atomiques permettent des opérations mathématiques (comme

l'incrémentation ou la décrémentation) sur des variables partagées, sans risque
d'interférences.

Ces opérations sont atomiques : elles se déroulent entièrement ou pas du tout, sans
être interrompues.

c. Spinlocks (Verrous tournants)

Les spinlocks sont utilisés pour les systèmes multiprocesseurs (SMP).

Ils fonctionnent en faisant "tourner" un thread dans une boucle jusqu'à ce qu'il
obtienne le verrou.

71/73
 Approprié pour des sections critiques très courtes, car il empêche le thread d'être
interrompu.

d. Verrous lecteur-rédacteur (Reader-Writer Locks)

Ce sont des versions avancées des sémaphores ou spinlocks.

Permettent plusieurs threads lecteurs d'accéder simultanément à une ressource,

mais limitent l'accès à un seul thread rédacteur.

Utile lorsque les lectures sont fréquentes, mais les écritures rares.

e. Régions critiques

Une région critique est une zone de code où des ressources partagées sont modifiées.

Linux gère ces régions critiques via des mécanismes comme les spinlocks ou les
sémaphores.

4. Particularité sur les systèmes à processeur unique

Sur les systèmes à processeur unique :

Les spinlocks sont remplacés par des mécanismes plus simples, comme la
désactivation des interruptions.

Pourquoi ?

Dans un système uniprocesseur, il n'y a pas de concurrence entre les

processeurs, donc la boucle d'attente des spinlocks n'est pas nécessaire.

La désactivation des interruptions suffit à protéger les ressources partagées.

Résumé
Caractéristiques Avant Linux 2.6 Depuis Linux 2.6

Gestion des Désactivation temporaire des Système entièrement préemptif.

interruptions interruptions.

72/73
 Caractéristiques Avant Linux 2.6 Depuis Linux 2.6

Synchronisation Méthodes simples pour Support avancé pour systèmes

uniprocesseurs. multiprocesseurs.

Mécanismes fournis Limités. Sémaphores, entiers atomiques,

spinlocks, etc.

Spinlocks sur Non utilisés, interruptions Toujours remplacés par des

uniprocesseur désactivées. mécanismes simples.

Ces mécanismes permettent à Linux de gérer efficacement la concurrence dans des

environnements variés, qu'il s'agisse de systèmes uniprocesseurs ou multiprocesseurs.

73/73