Sémaphore vs Mutex

Introduction

Un processus de système d’exploitation (OS) interagit avec d’autres processus s’exécutant dans le même système pour effectuer une tâche commune. Les processus qui interagissent avec d’autres processus sont appelés processus de coopération.

Sur la base des stratégies de communication Inter-processus (CIB) mises en œuvre par un processus, il peut soit partager son espace d’adressage avec d’autres processus, soit communiquer via un échange de messages. Dans la première technique, il est essentiel de contrôler la communication car les deux processus partagent un espace d’adressage commun.

Ce contrôle de la communication de processus est connu sous le nom de synchronisation. Sans synchronisation appropriée, les processus peuvent lire des données obsolètes ou écraser d’autres données de processus.

Le sémaphore et le mutex sont deux mécanismes par lesquels nous pouvons implémenter la synchronisation et gérer la coordination des processus. Dans cet article, nous examinerons ces deux utilitaires de synchronisation et comparerons diverses caractéristiques.

Comprendre la section critique

Avant de discuter du sémaphore et du mutex, comprenons le problème de la section critique.

Supposons que nous ayons un système qui contient n processus. Chacun de ces processus comporte un segment de code dans lequel le processus peut effectuer une mise à jour de variable commune, une mise à jour de table ou écrire dans un fichier. Ce segment de code est appelé la section critique d’un processus.

2.1. Caractéristiques d’un problème de section critique

La caractéristique essentielle de la section critique est qu’une fois qu’un processus commence à exécuter sa section critique, aucun autre processus n’est autorisé à exécuter sa section critique. Autrement dit, deux processus ne peuvent pas exécuter leur section critique simultanément. Ce problème de section critique consiste à concevoir un protocole afin que les processus puissent utiliser la coopération.

Chaque processus doit obtenir l’autorisation d’entrer dans sa section critique. Le morceau de code qui implémente l’autorisation est connu sous le nom de section d’entrée. De même, le morceau de code qui implémente la sortie de la section critique est connu sous le nom de section de sortie.

2.2. Critères d’un problème de section critique

La solution à un problème de section critique doit satisfaire aux critères suivants:

• Exclusion mutuelle : Si un processus exécute sa section critique, aucun autre processus ne peut exécuter sa section critique
• Progression : Si aucun processus n’exécute sa section critique, d’autres processus peuvent décider d’exécuter leur section critique. En fonction de la solution et de la mise en œuvre, un processus est sélectionné qui peut exécuter sa section critique. Les caractéristiques notables sont que les processus ont la capacité de passer à un processus de sélection pour exécuter sa section critique
• Attente bornée : Il devrait y avoir une attente bornée pour un processus lorsqu’il a demandé sa section d’entrée de section critique et le nombre de fois qu’un autre processus exécute sa section critique

Verrous Mutex

Il existe plusieurs utilitaires pour résoudre le problème de section critique dans un système d’exploitation. Les verrous d’exclusion mutuelle (mutex) ou mutex sont la solution la plus simple. Nous utilisons les verrous mutex pour protéger la section critique et empêcher les conditions de course. Un processus doit acquérir le verrou avant d’accéder à sa section critique, et il libère le verrou une fois qu’il a terminé l’exécution de la section critique.

3.1. Comment fonctionne un verrou Mutex ?

Ces deux fonctionnalités pour acquérir et libérer des verrous sont représentées par deux fonctions – acquire() et release(). La fonction d’acquisition acquiert le verrou et la libération libère le verrou. Un verrou mutex a une variable booléenne qui décide si le verrou est disponible ou non. Si le verrou est disponible, la méthode acquire() réussit et le verrou est considéré comme non disponible. Tout processus qui tente d’accéder à un verrou indisponible est bloqué jusqu’à ce que le verrou soit relâché.

Le pseudo-code suivant montre la méthode acquire():

Le pseudo-code suivant montre la méthode release():

3.2. Inconvénients des Mutex

L’inconvénient majeur d’un verrou mutex est qu’il laisse le thread tourner si le verrou n’est pas disponible.

Alors qu’un thread a acquis le verrou et se trouve dans sa section critique, tous les autres threads tentant d’acquérir le verrou sont dans une boucle où le thread vérifie périodiquement si le verrou est disponible. Ainsi, il tourne pour le verrou et gaspille des cycles CPU qui auraient pu être utilisés de manière productive par d’autres threads.

C’est un problème majeur dans une seule machine CPU. Spinlock est également connu sous le nom d’attente occupée car le fil est « occupé » en attente du verrou.

3.3. Avantages des Mutex

Bien que les verrous mutex souffrent du problème de spinlock, ils ont un avantage. Comme le processus se bloque dans le processeur, il élimine le besoin de changer de contexte de processus, ce qui aurait autrement été nécessaire.

Le changement de contexte d’un processus est une opération longue car il nécessite d’enregistrer les statistiques d’exécution du processus dans le Bloc de contrôle de processus (PCB) et de recharger un autre processus dans la CPU. Il existe des processeurs multi-processeurs où un processus peut tourner dans un cœur de processeur et un autre peut exécuter leur section critique. Ainsi, un spinlock de courte durée dans certains scénarios est plus utile qu’un commutateur de contexte de processus.

Sémaphore

Un sémaphore est un autre utilitaire qui fournit également des fonctionnalités de synchronisation similaires aux verrous mutex, mais qui est plus robuste et sophistiqué.

Un sémaphore est une variable entière qui, en dehors de l’initialisation, est accessible via deux opérations atomiques standard – wait() et signal(). L’opération wait() est appelée P et l’opération signal() est appelée V.

Jetons un coup d’œil à l’opération wait():

Enfin, regardons l’opération signal():

!

Toutes les opérations à la valeur entière du sémaphore dans wait() et signal() exécutées atomiquement. Autrement dit, une fois qu’un processus modifie la valeur du sémaphore, aucun autre processus ne peut modifier simultanément la même valeur du sémaphore.

Sur la base de la valeur du sémaphore S, il est classé en deux catégories: le sémaphore de comptage et le sémaphore binaire. La valeur d’un sémaphore de comptage peut aller de 0 à une valeur finie. Alors que la valeur d’un sémaphore binaire peut être comprise entre 0 et 1.

4.1. Les sémaphores de comptage

Les sémaphores de comptage peuvent contrôler le nombre N d’instances d’une ressource donnée. Expliquons le sémaphore de comptage par analogie.

Supposons qu’il existe une bibliothèque avec trois salles d’étude, et qu’il y a un bibliothécaire qui détient dix clés, chacune pour une pièce différente. Une fois qu’un lecteur a besoin d’accéder à une pièce, il doit obtenir une clé pour utiliser la pièce. Une fois qu’un lecteur a terminé son utilisation, il remet la clé de la pièce au bibliothécaire. Une fois que toutes les pièces sont utilisées, un nouveau lecteur doit attendre qu’une pièce soit libérée par un lecteur existant.

Dans l’exemple ci-dessus, la ressource est une pièce et il en existe dix instances. Ces instances sont gérées via un sémaphore de comptage qui est initialisé avec ten. Cette valeur du sémaphore est contrôlée par les méthodes wait() et signal() du sémaphore. Le diagramme suivant illustre cela:

4.2. Sémaphores binaires

Un sémaphore binaire a deux valeurs possibles, 0 et 1. Si la ressource gérée par le sémaphore est disponible, la valeur du sémaphore est 1. Sinon, il est défini sur 0, indiquant que la ressource n’est pas disponible.

Un sémaphore binaire a la même fonctionnalité qu’un verrou mutex. Les systèmes qui ne prennent pas en charge les verrous mutex peuvent tirer parti des sémaphores binaires pour obtenir les mêmes fonctionnalités.

Le diagramme suivant illustre le sémaphore binaire:

Sémaphore vs. Mutex

Le tableau suivant résume les caractéristiques importantes des verrous sémaphores et mutex:

Conclusion

Dans cet article, nous avons discuté de divers aspects des mutex et des sémaphores.

Tout d’abord, nous avons discuté de la section critique et de la nécessité d’un mutex ou d’un sémaphore pour contrôler l’exécution de la section critique. Nous avons ensuite parlé de mutex et de sémaphore.

Enfin, nous avons fourni une comparaison du sémaphore et du mutex.