Ce document, destiné aux étudiants en informatique de troisième année, présente le cinquième travail pratique (TP 5) du cours de Systèmes d'exploitation des ordinateurs. Il aborde le concept fondamental de l'exclusion mutuelle, spécifiquement implémentée via les sémaphores POSIX.
Les exercices proposés guident les étudiants à travers la parallélisation du produit de matrices, d'abord sans threads, puis en utilisant des processus légers (threads) et des sémaphores pour gérer l'accès concurrent. Une analyse comparative des performances est également requise, permettant de comprendre l'impact de la concurrence sur le temps d'exécution.
Exclusion Mutuelle par Sémaphore : Multiplication de Matrices en Parallèle
Ce guide explore le concept d'exclusion mutuelle à travers l'exemple de la multiplication de matrices en parallèle, en utilisant des sémaphores pour synchroniser les processus légers (threads). Il s'agit d'une approche courante en programmation concurrente pour optimiser les performances des calculs intensifs.
Exercice 1 : Produit de deux matrices
L'objectif est d'effectuer en parallèle le produit de deux matrices A et B d’ordre n (n*n). Pour ce faire, on crée m (m < n) processus légers (threads). Chaque processus léger est chargé de calculer quelques lignes de la matrice résultat R.
La formule de calcul pour chaque élément R[i, j] est la suivante :
Pour j = 0 à n-1, R[i, j] = ∑ k = 0, n-1 (A[i, k] * B[k, j]);
Défis de l'implémentation
Pour aborder ce problème, plusieurs étapes de programmation peuvent être envisagées :
-
Implémentation sans threads
Écrire le programme de la fonction
CalculeLigne, sans l'utilisation de threads, pour établir une base de référence séquentielle. -
Implémentation avec threads et sémaphores
Écrire le programme de la fonction
CalculeLigne, en utilisant des threads et des sémaphores, pour gérer la concurrence et l'accès aux ressources partagées. -
Analyse comparative des performances
Comparer les temps d'exécution des deux programmes (avec et sans threads/sémaphores) pour évaluer le gain de performance apporté par la parallélisation.
Des outils comme
#includepeuvent être utilisés pour mesurer précisément le temps d’exécution des différentes implémentations.; clock_t temps; temps = clock();
Rappels sur les fonctions de manipulation des sémaphores POSIX
Les sémaphores POSIX sont des outils essentiels pour la synchronisation entre processus ou threads. Voici un rappel des fonctions principales :
-
Inclusion :
#includeCette bibliothèque contient les services POSIX pour manipuler les sémaphores.
-
Type
sem_tCe type de données désigne un sémaphore.
-
Initialisation :
int sem_init(sem_t *sem, int pshared, unsigned int valeur)Cette fonction permet d'initialiser le sémaphore
sem.sem: est un pointeur sur le sémaphore à initialiser.pshared: indique si le sémaphore est local au processus (pshared = 0) ou partagé entre le père et le fils (pshared != 0).valeur: est la valeur initiale du sémaphore.
-
Attendre (P) :
int sem_wait(sem_t *sem)Cette fonction est équivalente à l'opération P (attendre) sur le sémaphore. Elle décrémente la valeur du sémaphore. Si la valeur devient négative, le thread appelant est bloqué jusqu'à ce que le sémaphore soit signalé. Elle retourne 0 en cas de succès.
-
Signaler (V) :
int sem_post(sem_t *sem)Cette fonction est équivalente à l'opération V (signaler) sur le sémaphore. Elle incrémente la valeur du sémaphore. Si des threads sont bloqués en attente, l'un d'eux est réveillé. Elle retourne 0 en cas de succès ou -1 en cas d'erreur.
-
Essai d'attente :
int sem_trywait(sem_t *sem)Cette fonction tente de décrémenter la valeur du sémaphore
sem. Si sa valeur est supérieure à 0, elle la décrémente et retourne 0. Sinon, elle retourne immédiatement une erreur sans bloquer le thread. C'est une opération atomique. -
Obtenir la valeur :
int sem_getvalue(sem_t *sem, int *sval)Cette fonction permet de récupérer la valeur courante d'un sémaphore et de la stocker dans
*sval. Elle retourne 0 en cas de succès. -
Détruire :
int sem_destroy(sem_t *sem)Cette fonction détruit un sémaphore. Il est crucial de s'assurer qu'aucun thread n'est bloqué sur ce sémaphore avant de le détruire. Elle retourne -1 si des threads sont encore bloqués en attente sur ce sémaphore.
Foire Aux Questions (FAQ)
-
Qu'est-ce que l'exclusion mutuelle ?
L'exclusion mutuelle est un mécanisme de synchronisation qui garantit que plusieurs threads ou processus n'accèdent pas simultanément à une ressource partagée critique. Cela prévient les conditions de course et assure l'intégrité des données.
-
Quel est le rôle d'un sémaphore dans la programmation concurrente ?
Un sémaphore est une variable spéciale (un entier non négatif) utilisée pour contrôler l'accès à une ressource commune par plusieurs processus. Il permet de signaler la disponibilité d'une ressource et de bloquer les processus si la ressource est indisponible, facilitant ainsi la synchronisation et l'exclusion mutuelle.
-
Pourquoi utiliser des threads pour la multiplication de matrices ?
La multiplication de matrices, surtout pour de grandes tailles, est une opération qui peut être décomposée en tâches indépendantes (calcul de lignes ou blocs). L'utilisation de threads permet d'exécuter ces tâches en parallèle sur des processeurs multi-cœurs, réduisant significativement le temps de calcul global et améliorant les performances de l'application.