Programmation des Systèmes
Synchronisation de processus (suite)
Travaux Dirigés assurés par Philippe Décogné
11/01/2003
Soit un système composé de deux processus cycliques Exécution et Impression, et d'un tampon AVIS de n cases. Le tampon AVIS est géré de façon circulaire.
Le processus Exécution exécute une requête de travail et transmet ensuite au processus Impression un ordre d'impression de résultats déposé dans le tampon AVIS. La case de dépôt est repérée par un index i de dépôt, initialisé à 1. Les dépôts s'effectuent depuis la case 1 jusqu'à la case N, puis retour à la case 1 (gestion circulaire).
Le processus Impression prélève les ordres d'impression déposés dans le tampon AVIS et exécute ceux-ci. La case de retrait est repérée par un index j de retrait, initialisé à 1. Les retraits s'effectuent depuis la case 1 jusqu'à la case N, puis retour à la case 1 (gestion circulaire).
Programmez la synchronisation des deux processus à l'aide des sémaphores et des variables nécessaires à la gestion des tampons.
On étend le système à trois processus Exécution et trois processus Impression. Complétez la synchronisation précédente pour que celle-ci demeure correcte.
Schéma de fonctionnement d'un sémaphore
K définit le nombre d'accès simultanés au sémaphore, autrement dit le nombre de processus autorisés à accéder au sémaphore en même temps.
La liste d'attente des sémaphores est, en général, gérée de façon FIFO.
Les opérations sur sémaphore sont les suivantes :
Initialisation
init(val,sem)
début
K = val;
L = Ø
fin
Blocage du processus sur le sémaphore
p(sem)
début
k = k -1;
si k < 0 alors
mettre le processus appelant dans la liste L;
endormir le processus appelant;
finsi
fin
Déblocage du processus
v(sem)
début
k = k + 1;
si k <= 0 alors
sortir un processus de la liste d'attente
réveiller le processus
fin si
fin
Analyse du problème
Les processus communiquent par le tampon AVIS. Donc, la synchronisation doit porter sur lui.
Exécution
Le processus Exécution peut écrire dans le tampon à condition qu'il reste au moins une case vide.
D'autre part, le tampon comporte N cases. On aura donc pour le processus Exécution un sémaphore NVIDE initialisé à N.
À l'intérieur de la section critique, Déposer ordre, chaque fois que le processus écrira dans le tampon, il faudra qu'il incrémente l'index i de dépôt modulo N, pour tenir compte du fait que le tampon est circulaire.
Impression
Le processus Impression peut lire dans le tampon à condition qu'il y ait au moins une case pleine.
On utilisera donc pour ce processus un sémaphore initialisé à 0.
A l'intérieur de la section critique, Acquérir ordre, chaque fois qu'il lira dans le tampon le processus Impression incrémentera l'index j de retrait modulo N, pour tenir compte du fait que le tampon est circulaire. On appliquera ainsi une politique FIFO : premier écrit, premier lu.
Intercommunication
Dans la section critique, le processus Exécution doit :
- avant toute écriture, vérifier qu'il peut écrire en bloquant le sémaphore NVIDE, ce qui a pour effet de décrémenter NVIDE
- après toute écriture, avertir le processus impression qu'il peut lire en débloquant le sémaphore NPLEIN, ce qui a pour effet d'incrémenter NPLEIN.
On a donc, à la sortie de la section critique du processus Exécution
- NVIDE décrémenté de une unité, ce qui correspond à une case en plus utilisée pour l'écriture, donc une case en moins disponible pour les écritures suivantes
- NPLEIN incrémenté de une unité, ce qui correspond à une case en plus à disposition pour la lecture suivante.
De même, dans la section critique, le processus Impression doit :
- avant toute lecture, vérifier qu'il peut lire en bloquant le sémaphore NPLEIN
- après toute lecture, avertir le processus Exécution qu'il peut écrire en débloquant le sémaphore NVIDE.
Ainsi, à la sortie de la section critique du processus Impression, on obtient :
- NPLEIN décrémenté de une unité, ce qui correspond à une case utilisée pour la lecture, donc une case en moins pour les lectures suivantes
- NVIDE incrémenté de une unité, ce qui correspond à une case en plus à disposition pour les écritures suivantes.
Pseudo-code
/* Processus principal /*
/* Normalement il faudrait utiliser des threads avec variables
globales et pipe ou travailler en mémoire partagée */
/* Déclarations globales */
/* Nombre de cases dans le tampon AVIS
On pourrait l'utiliser en argument au programme, ce qui
permettrait de le faire varier en fonction des besoins */
N entier;
avis = tampon(0,1, ...,N-1) de messages;
NVIDE, NPLEIN: sémaphores;
/* Initialisation */
INIT(NVIDE, N);
INIT(NPLEIN, 0);
/* Création et lancement des threads secondaires */
lancer thread_execution;
lancer thread_impression;
fin
/* Thread Exécution */
/* Déclarations locales */
i = index de dépôt des messages dans le tampon AVIS
res = résultat de message
/* Initialisation */
i = 0;
/* Boucle */
Début_boucle
Exécuter_travail(requête, res);
/* Section critique */
P(NVIDE);
avis(i) = res;
i = i + 1 mod N;
V(NPLEIN);
Fin_boucle
Fin thread
/* Thread Impression */
/* Déclarations locales */
j = index de retrait des messages dans le tampon AVIS
mes = message
/* Initialisation */
j = 0;
/* Boucle */
Début_boucle
/* Section critique */
P(NPLEIN);
mes = avis(j);
j = j + 1 mod N;
V(NVIDE);
imprimer_resultat(mes);
Fin_boucle
Fin thread
Extension à plusieurs processus Exécution et Impression
Il faut, ici, éviter que plusieurs processus Exécution (resp. Impression) lisent (resp. écrivent) en même temps (dans) la même case.
On se trouve ici dans un schéma d'exclusion mutuelle sur les index de dépôts et de retraits. On utilisera donc deux sémaphores binaires MUTI et MUTJ initialisés tous les deux à 1 (un seul processus peut accéder à un moment donné à l'index).
Les variables i et j deviennent donc globales et sont initialisées dans le thread principal ainsi que les MUTEX.
On bloquera (resp. débloquera) les MUTEX en début (resp. en fin) de chaque section critique correspondante.
Pseudo-code étendu
/* Processus principal /*
/* Normalement il faudrait utiliser des threads avec variables
globales et pipe ou travailler en mémoire partagée */
/* Déclarations globales */
/* Nombre de cases dans le tampon AVIS
On pourrait l'utiliser en argument au programme, ce qui
permettrait de le faire varier en fonction des besoins */
N entier;
i,j entiers; /* index de dépôt et retrait */
avis = tampon(0,1, ...,N-1) de messages;
NVIDE, NPLEIN: sémaphores;
MUTI, MUTJ: sémaphores binaires
/* Initialisation */
i = 0;
j = 0;
INIT(NVIDE, N);
INIT(NPLEIN, 0);
INIT(MUTI,1);
INIT(MUTJ, 1);
/* Création et lancement des threads secondaires */
lancer thread_execution;
lancer thread_impression;
fin
/* Thread Exécution */
/* Déclarations locales */
res = résultat de message
/* Boucle */
Début_boucle
Exécuter_travail(requête, res);
/* Section critique */
P(MUTI);
P(NVIDE);
avis(i) = res;
i = i + 1 mod N;
V(NPLEIN);
V(MUTI);
Fin_boucle
Fin thread
/* Thread Impression */
/* Déclarations locales */
mes = message
/* Boucle */
Début_boucle
/* Section critique */
P(MUTJ);
P(NPLEIN);
mes = avis(j);
j = j + 1 mod N;
V(NVIDE);
V(MUTJ);
imprimer_resultat(mes);
Fin_boucle
Fin thread
Dans le service de gestion d'un magasin, un employé est chargé d'enregistrer les commandes des clients dans un fichier COM, et d'éditer les bons de commandes correspondants sur une imprimante IMP.
D'autre part, un processus facturation, lancé périodiquement, lit les commandes à facturer dans COM et édite les factures correspondantes sur l'imprimante IMP.
On propose la solution suivante :
processus employé début tant qu'il y a des commandes à enregistrer réserver(Com); enregistrer une commande dans Com; réserver(Imp); éditer un bon de commande sur Imp; libérer(Com); libérer(Imp); fin tant que fin processus facturation début répéter indéfiniment réserver(IMP); réserver(COM); tant qu'il y a des commandes à facturer dans COM lire la prochaine commande dans COM; éditer la facture correspondante sur IMP; fin tant que libérer(IMP); libérer(COM); attendre la prochaine période de facturation; fin répéter fin
Donnez une définition de l'interblocage.
Montrez que la programmation risque de conduire à un interblocage.
Modifiez le processus de facturation pour supprimer le risque d'interblocage.
Interblocage
L'interblocage est une situation dans laquelle p processus Pi sont en attente de r ressources elles-mêmes allouées à q processus Qi en attente de s ressources allouées aux processus Pi.
Dans ces conditions, les processus Pi et Qi sont bloqués indéfiniment en attente des ressources qui les intéressent.
Analyse du pseudo-code
Supposons qu'à un moment donné, le processus exécution détienne la ressource COM et le processus impression la ressource IMP.
Alors, on est dans le processus Exécution forcément avant la ligne éditer, sinon on aurait acquis la ressource IMP, ce qui n'est pas possible puisque le processus Impression la détient. On est donc ou on va être en attente de la ressource IMP.
De même, on est forcément dans le processus Impression en attente de la ressource COM, sinon on l'aurait acquis, ce qui n'est pas possible puisque le processus Exécution la détient.
À ce moment, on est en situation d'interblocage.
Résolution du problème
Pour éviter l'interblocage, il suffit de réserver la ressource COM au début du processus Impression.
En effet, si le processus Exécution détient déjà la ressource COM, le processus Impression devra attendre la libération de la ressource COM pour réserver ensuite la ressource IMP et commencer le traitement.
Pendant ce temps, le processus Exécution libérera la ressource IMP avant de réserver de nouveau la ressource COM.
On n'aura donc pas d'interblocage.
Pseudo-code
processus facturation début répéter indéfiniment réserver(COM); réserver(IMP); tant qu'il y a des commandes à facturer dans COM lire la prochaine commande dans COM; éditer la facture correspondante sur IMP; fin tant que libérer(IMP); libérer(COM); attendre la prochaine période de facturation; fin répéter fin
