Correction série N° 1

Ce document présente une correction d’une série d’exercices portant sur la gestion des ressources partagées en informatique, notamment l’utilisation des sémaphores pour la synchronisation des processus. Il évalue la compréhension des concepts de ressources critiques, d’exclusion mutuelle, et de gestion concurrente dans un contexte d’impression et d’accès à un fichier partagé.

Exercice I

Il s'agit d'analyser les problèmes liés à l'utilisation concurrente d'une imprimante par plusieurs processus et de proposer une solution de synchronisation.

a- Problème d'utilisation simultanée de l'imprimante

Le problème est que l’imprimante ne peut pas être utilisée par deux processus (Px) en même temps. Si deux processus impriment simultanément, cela entraînera un entrelacement des lignes provenant de différentes sources sur le papier, rendant le document imprimé inexploitable.

Conclusion : L’imprimante est une ressource non partageable simultanément, ce qui nécessite une gestion d’accès exclusif.

b- Identification de la ressource critique

Le problème est causé par le partage du fichier, qui est une ressource partageable exclusivement. Cette ressource est donc un fichier accessible à un seul point d’accès à la fois.

Conclusion : La ressource critique est le fichier, qui doit être protégé pour éviter les accès concurrents.

c- Protection de la ressource par un sémaphore

La ressource sera protégée par un sémaphore défini comme (s, fs, 1), où fs indique que la ressource est un fichier et 1 signifie qu’il n’y a qu’un seul point d’accès possible simultanément.

Le processus TRT1 s’écrit ainsi :

TRT1 :
Produire des données
ALLOUER(s)
Imprimer les données
LIBERER(s)
Aller à TRT1

Le sémaphore garantit que l’impression est réalisée par un seul processus à la fois.

Réponse finale : Utilisation d’un sémaphore (s, fs, 1) pour protéger l’accès exclusif à l’imprimante.

Exercice II

Il s'agit de gérer l’accès concurrent à N imprimantes banalisées, c’est-à-dire identiques et interchangeables, par plusieurs processus.

a- Identification des ressources et sémaphores nécessaires

Les ressources sont les N imprimantes, considérées comme une seule ressource à N points d’accès car elles sont banalisées.

Le sémaphore de partage des imprimantes est (s, fs, N), qui permet de savoir s’il y a au moins une imprimante libre.

Pour déterminer laquelle des N imprimantes est libre, un tableau T[1..N] est utilisé, initialisé à 0 (libre) pour chaque imprimante.

Ce tableau est partagé entre tous les processus et constitue une ressource critique à un seul point d’accès. Il doit donc être protégé par un sémaphore (p, fp, 1).

b- Algorithme de gestion des imprimantes

Le processus TRT1 s’écrit :

TRT1 :
Produire des données
ALLOUER(s)         // Vérifie qu'une imprimante est disponible
ALLOUER(p)         // Protection du tableau T

For ip = 1 to N do
{
    If (T[ip] = 0) Then
    {
        T[ip] = 1    // Marque l'imprimante ip comme occupée
        break
    }
}

LIBERER(p)         // Libère la protection du tableau

Imprimer les données sur ip

ALLOUER(p)         // Protection du tableau pour libérer l'imprimante
T[ip] = 0          // Marque l'imprimante ip comme libre
LIBERER(p)

LIBERER(s)         // Libère le sémaphore d'imprimantes disponibles

Aller à TRT1

Ce mécanisme garantit que :

• Un processus ne peut accéder qu’à une imprimante libre.
• Le tableau d’état des imprimantes est protégé contre les accès concurrents.
• La ressource imprimante est correctement allouée et libérée.

Réponse finale : Utilisation d’un sémaphore (s, fs, N) pour la disponibilité et d’un sémaphore (p, fp, 1) pour protéger le tableau d’état des imprimantes.

Exercice III

Il s'agit de gérer l’accès concurrent à un fichier partagé F entre un processus R (écrivain) et plusieurs processus L (lecteurs), avec des règles d’exclusion et de priorité différentes.

a- Description du problème et ressources

La ressource partagée est le fichier F.

Le partage n’est pas statique :

• Le fichier est accessible de façon exclusive entre le processus R et les processus L.
• Les processus L peuvent accéder simultanément au fichier entre eux (accès multiple).

Un sémaphore (w, fw, 1) est nécessaire pour protéger F entre R et L.

Les processus L ne doivent pas se bloquer si R n’écrit pas. Le premier L qui entre doit tester si R écrit. S’il écrit, il doit attendre, sinon il bloque R et laisse passer les autres L.

Le dernier L qui sort libère le fichier pour R.

Un compteur NB_L compte le nombre de lecteurs en cours d’utilisation du fichier. Ce compteur est une ressource critique protégée par un sémaphore (p, fp, 1).

b- Cas 1 : Priorité aux lecteurs (Px L prioritaires)

Processus R :

TRT_R :
Produire des données
ALLOUER(s)
Ecrire dans le fichier F
LIBERER(s)
Aller à TRT_R

Processus L :

TRT_L :
ALLOUER(p)
NB_L++
If (NB_L = 1) then
{
    ALLOUER(s)
}
LIBERER(p)

Lire les données

ALLOUER(p)
NB_L--
If (NB_L = 0) then
{
    LIBERER(s)
}
LIBERER(p)

Traiter les données

Aller à TRT_L

Ce protocole garantit que :

• Le premier lecteur bloque l’écrivain en allouant s.
• Les lecteurs suivants peuvent lire simultanément.
• Le dernier lecteur libère la ressource pour l’écrivain.

Réponse finale : Mise en œuvre d’un compteur NB_L protégé par un sémaphore p et d’un sémaphore s pour l’exclusion mutuelle entre lecteurs et écrivain.

c- Cas 2 : Partage équitable entre lecteurs et écrivain

Pour un partage équitable, un sémaphore supplémentaire (w, fw, 1) est utilisé pour bloquer les lecteurs lorsque l’écrivain attend le fichier.

Processus R :

TRT_R :
Produire des données
ALLOUER(w)
ALLOUER(s)
Ecrire dans le fichier F
LIBERER(w)
LIBERER(s)
Aller à TRT_R

Processus L :

TRT_L :
ALLOUER(w)
ALLOUER(p)
NB_L++
If (NB_L = 1) then
{
    ALLOUER(s)
}
LIBERER(p)
LIBERER(w)

Lire les données

ALLOUER(p)
NB_L--
If (NB_L = 0) then
{
    LIBERER(s)
}
LIBERER(p)

Traiter les données

Aller à TRT_L

Ce protocole garantit :

• Que les lecteurs ne peuvent pas entrer si l’écrivain attend (grâce à w).
• Un accès équitable entre lecteurs et écrivain.
• Une protection correcte du compteur NB_L et de la ressource fichier.

Réponse finale : Ajout d’un sémaphore w pour assurer l’équité entre lecteurs et écrivain.

Méthode

Ce sujet récompense la maîtrise des concepts suivants :

• Identification claire des ressources critiques et des points d’accès.
• Utilisation correcte des sémaphores pour assurer l’exclusion mutuelle et la synchronisation.
• Gestion des compteurs partagés protégés par des sémaphores pour éviter les conditions de course.
• Capacité à adapter les protocoles selon les exigences de priorité ou d’équité.
• Respect des conventions données dans l’énoncé, notamment la notation des sémaphores et la structure des processus.

Les erreurs pénalisées sont :

• Oublier de protéger les variables partagées (comme le tableau des imprimantes ou le compteur NB_L).
• Confondre les sémaphores pour la ressource principale et ceux pour la protection des structures de données.
• Ne pas respecter l’ordre d’allocation et de libération des sémaphores, ce qui peut entraîner des interblocages.
• Ignorer les conditions d’entrée et de sortie des sections critiques.

En résumé, la rigueur dans la définition des ressources, la protection des accès et la gestion des sémaphores est essentielle pour réussir ce type d’exercice.