Correction de l'examen de systèmes opératoires
2ième Année Informatique et Mathématiques Appliquées
15 Novembre 2000
1 Exclusion mutuelle
On considère le problème de l'exclusion mutuelle dans le contexte
d'une architecture multiprocesseur. Seules les opérations de lecture et
les opérations d'écriture d'un mot mémoire sont considérées comme
atomiques.
On suppose qu'il existe N processus
numérotés de 0 à N-1 qui
peuvent classiquement demander l'accès en exclusion mutuelle à une
ressource commune. Pour résoudre ce problème, on se propose d'utiliser la notion
de privilège. Le privilège donne le droit d'entrer en exclusion mutuelle au processus qui l'obtient.
Si un seul processus à la fois peut obtenir ce privilège,
alors la propriété d'exclusion mutuelle est garantie. Pour faire circuler
le privilège entre les processus, on place les processus sur un anneau
logique. Chaque processus aura ainsi un successeur (et un prédécesseur).
Pour matérialiser la possession du privilège par un processus on utilise
un booléen. Le tableau EstPriv(N) indique pour chaque élément
EstPriv[i], si le processus i correspondant possède ou non
le privilège. Initialement, on suppose que les valeurs des éléments du tableau sont :
EstPriv[0] /\ (pour tout i : 0 < i < N :: ¬ EstPriv[i])
Pour l'algorithme des opérations Entrer et
Sortir, on propose donc les solutions suivantes où suc(x)
désigne l'indice du successeur du processus x sur l'anneau logique :
Entrer(int i) { Sortir( int i) {
while ( ! EstPriv[i] ) do { } ; EstPriv[suc(i)] = true ;
} EstPriv[i] = false ;
}
Questions - Réponses
-
Montrer sur un exemple, que l'invariant suivant :
invariant pour tout k : (EstPriv[k] => (pour tout i != k : ¬ EstPriv[i]))
n'est pas garanti par cette solution. Montrer que le privilège peut être perdu,
c'est-à-dire que l'état où tous les éléments du tableau EstPriv sont faux
est accessible et stable.
Réponse
Dans l'état initial, l'invariant est vérifié. Si le processus P0 exécute Entrer(0),
il réussit. Lorsqu'il sort d'exclusion mutuelle, l'exécution de la première affectation
EstPriv[suc(i)] = true rend l'invariant faux puisque l'état courant vérifie
alors EstPriv[0] /\ EstPriv[1]. Si l'on suppose que le processus P0 est alors
interrompu avant qu'il n'exécute la deuxième affectation EstPriv[0] = false,
le processus P1 peut entrer en exclusion (identique à exécuter l'opération Entrer(1))
puis commencer l'exécution de Sortir(1) jusqu'à la première affectation. Ce schéma
peut se reproduire de proche en proche, jusqu'à un état où tous les processus
les uns après les autres, sont entrés en exclusion mutuelle, ont exécuté leur
section cirtique puis ont débuté l'opération Sortir en exécutant la première
affectation.
Cependant, aucun ne l'a terminée en exécutant la deuxième affectation. L'état courant vérifie
alors pour tout i : EstPriv[i]. L'exécution de la deuxième affectation de chaque opération
Sortir en cours par chacun des processus, conduira alors à l'état pour tout i : ¬ EstPriv[i].
Le privilège est alors définitivement perdu, cet état étant stable.
- Modifier la solution proposée pour qu'elle garantisse l'invariant précédent
et évite la perte définitive du privilège.
Réponse
La modification consiste à inverser l'ordre des deux affectations dans l'opération
Sortir. L'invariant est alors bien garanti et bien que l'état pour lequel
tous les éléments du tableau EstPriv sont faux puisse exister momentanément,
celui-ci n'est jamais stable.
- Quelle propriété, généralement souhaitable lorsqu'on propose
une solution au problème de l'exclusion mutuelle, n'est pas garantie
par cette solution ?
Réponse
La propriété qui n'est pas vérifiée est la propriété d'indépendance. En effet, tout
processus i peut entrer en exclusion mutuelle seulement si le privilège
est propagé jusqu'à lui. Autrement dit, après être sorti d'exclusion mutuelle,
un processus i ne retrouvera le privilège et ainsi le droit d'entrer en exclusion
que lorsque chacun des autres processus aura lui-même obtenu et rendu le privilège.
On constate donc qu'un processus ne réussira pas forcément à entrer en exclusion
même si tous les autres processus sont hors exclusion.
- On aurait pu obtenir une solution similaire en utilisant simplement
une seule variable entière globale pour « implanter » la circulation du privilège.
Donner les algorithmes des primitives Entrer et Sortir dans ce cas.
Réponse
On introduit une variable entière Tour qui prend ses valeurs sur l'intervalle
[0..N-1]. Initialement, on peut supposer que Tour égale 0.
Entrer(int i) { Sortir( int i) {
while ( i != Tour ) do { } ; if (i != Tour) abort() ;
} Tour = suc(i) ;
}
2 Mécanisme de sémaphore
On propose la classe Sémaphore suivante pour décrire le
mécanisme de sémaphore. On suppose que ces primitives sont exécutées
de façon atomique. La classe Queue
implante une file d'attente FIFO d'objets et
la référence Actif désigne le processus appelant la primitive :
class Sémaphore {
int cpt = 0 ;
Queue fifo = new Queue ;
P() {
if ( cpt == 0 ) { fifo.insérer(Actif) ; Actif.Suspendre(); }
cpt-- ;
}
V() {
Processus unPr ;
if ( ! fifo.vide ) {unPr = fifo.extraire() ; unPr.Continuer() ;}
else { cpt++ ; }
}
Sémaphore( int v0 ) { cpt = v0 ; }
}
Questions - Réponses
-
Dans un contexte monoprocesseur proposer une solution pour
obtenir la propriété d'atomicité des primitives.
Réponse
Dans un contexte monoprocesseur, l'atomicité d'une primitive peut être obtenue
en garantissant que le processeur ne sera pas préempté avant la fin de la primitive.
Pour cela, il suffit d'exécuter la primitive en mode ininterruptible.
- Montrer que les algorithmes proposés pour les primitives
ne garantissent pas le mécanisme de sémaphore et proposer la correction
adéquate en justifiant vos modifications.
Réponse
L'algorithme de l'opération V n'est pas correct car il ne comptabilise pas
toujours le « jeton » normalement produit par cette opération. À titre d'exemple,
si le sémaphore a initialement un compteur nul, un premier appel à P
sera bloquant et le processus appelant sera inséré dans la file du sémaphore.
Si une opération V est alors exécutée, le processus dans la file sera débloqué
mais le compteur ne sera pas incrémenté. Par suite, l'opération P
se terminera en décrémentant par contre le compteur. Celui-ci deviendra alors négatif
alors que l'exécution d'un couple de primitives V,P aurait dû conduire
à un compteur nul.
Une solution correcte peut être obtenue en incrémentant systématiquement le compteur
dans la primitive V :
V() {
Processus unPr ;
cpt++ ;
if ( ! fifo.vide ) {unPr = fifo.extraire() ; unPr.Continuer() ;}
}
3 Moniteurs de Hoare : un canal diffusant
On considère la modélisation et l'implantation sous la forme d'un moniteur
de Hoare d'un canal unidirectionnel de communication permettant de diffuser un message
à plusieurs récepteurs. Tout message émis par un processus diffuseur
sur le canal devra être reçu par des processus lecteurs sur un nombre
fixé de sorties numérotées. L'interface de ce moniteur est la suivante :
moniteur Canal {
/* dépôt d'un message sur l'entrée du canal */
Diffuser ( Message m ) ;
/* lecture du message courant sur la sortie s donnée par l'appelant */
Message Lire ( int s ) ;
/* constructeur permettant d'engendrer un objet canal avec p sorties */
Canal ( int p ) ;
}
Synchronisation entre processus diffuseur(s) et lecteurs
La diffusion d'un message est de type synchrone : l'opération de diffusion ne se
termine que lorsque le message produit a été effectivement lu (consommé)
sur les p sorties. Les diffusions sur un canal donné sont traitées séquentiellement et
le canal ne comporte donc qu'une seule « case ».
3.1 Première étape
Dans un premier temps, et pour simplifier la recherche d'une solution, on impose
simplement que le message courant soit lu p fois sans tenir compte du paramètre
« numéro de sortie » dans l'opération Lire. On suppose de plus qu'il
n'existe qu'un seul processus diffuseur.
On introduit deux variables d'états : d'une part degré qui mémorise le degré de la
diffusion (le nombre de sorties) et d'autre part nbL qui mémorise le nombre de
lectures du message courant à faire.
On utilise deux variables conditions : DernierLect permet de synchroniser
la terminaison de l'opération de diffusion avec les lectures et MesALire
permet de synchoniser les lectures du message courant ;
Les opérations Diffuser et Lire doivent respecter les pré et post-conditions
suivantes :
-
{ nbL == 0 } Diffuser( Message m ) { nbL' == 0 }
- { nbL > 0 } Lire( int s ) { nbL' == nbL - 1 }
On propose la solution incomplète suivante pour la classe moniteur Canal
moniteur Canal {
int degré = 0 ; int nbL = 0 ; Message case ;
condition DernierLect = new condition ;
condition MesALire = new condition ;
/* dépot d'un message sur l'entrée du canal */
Diffuser ( Message m ) {
case = m.clone() ;
nbL = degré ;
/* nbL > 0 */
MesALire.signal() ;
if (nbL > 0) DernierLect.wait() ;
/* nbL == 0 */
}
/* lecture du message courant sur la sortie s donnée par l'appelant */
Message Lire ( int s ) { ... }
/* constructeur permettant d'engendrer un objet canal avec p sorties */
Canal ( int p ) { degré = p ; }
}
Questions
-
Programmer l'opération Lire en précisant les pré et post-conditions
habituelles associées aux opérations signal et wait ;
Réponse
/* lecture du message courant sur la sortie s */
Message Lire ( int s ) {
if (nbL == 0) MesALire.wait() ;
/* nbL > 0 */
nbL-- ;
Message Rep = case ;
if (nbL > 0) MesALire.signal() ; /* réveil en chaîne */
else /* nbL == 0 */ DernierLect.signal() ;
return Rep ;
}
- On suppose maintenant qu'il existe plusieurs processus diffuseurs.
Modifier l'opération Diffuser pour obtenir une solution correcte.
Réponse
L'opération Diffuser devient une opération qui doit être exécutée de
façon atomique. Une deuxième opération ne peut déposer un message avant que le
message précédent déposé ait été lu « degré » fois. L'opération Diffuser
devient une section critique. Il suffit donc d'une variable booléenne et d'une variable
condition associée pour contrôler l'utilisation de cette section critique.
moniteur Canal {
...
bool Libre = true ;
condition AccèsLibre = new condition ;
/* dépot d'un message sur l'entrée du canal */
Diffuser ( Message m ) {
if (!Libre) AccèsLibre.wait() ;
libre = false ;
case = m.clone() ;
nbL = degré ;
/* nbL > 0 */
MesALire.signal() ;
if (nbL > 0) DernierLect.wait() ;
/* nbL == 0 */
libre = true ;AccèsLibre.signal() ;
}
...
}
3.2 Deuxième étape
On tient compte maintenant des numéros de sorties et l'on veut assurer la lecture du message
courant une seule fois sur chaque sortie.
Questions
-
Récrire les pré et post-conditions des opérations Diffuser
et Lire en précisant les variables d'états et les variables conditions introduites ;
Réponse
Il faut enregistrer chaque événement de lecture du message diffusé sur chaque sortie.
Pour cela, on introduit une variable d'état de type tableau de booléen bool Lu[0..degré-1].
Le nombre d'éléments de ce tableau à vrai sera toujours égal à la valeur de la variable nbL.
Autrement dit, le moniteur maintiendra l'invariant :
|
invariant |
nbL = |
|
(Lu[i] ? 0 : 1)
|
Les opérations Diffuser et Lire doivent maintenant respecter les pré et post-conditions
suivantes :
-
{ nbL == 0 /\ pour tout s : Lu[s] } Diffuser( Message m ) { nbL' == 0 /\ pour tout s : Lu'[s] }
- { nbL > 0 /\ il existe s0 : ¬ Lu[s0] } Lire( int s ) { nbL' == nbL - 1 /\ Lu'[s0] }
- Modifier les opérations Diffuser et Lire en conséquence pour
obtenir la solution recherchée.
Réponse
moniteur Canal {
int degré = 0 ; Message case ;
int nbL = 0 ; /* Contrôle de la terminaison de Diffuser */
condition DernierLect = new condition ;
bool Libre = true ; /* Protection de l'opération Diffuser */
condition AccèsLibre = new condition ;
bool[] Lu ; /* Contrôle des lectures sur chaque sortie */
condition[] MesALire ;
/* dépot d'un message sur l'entrée du canal */
Diffuser ( Message m ) {
if (!Libre) AccèsLibre.wait() ;
/* Libre */
libre = false ;
case = m.clone() ;
nbL = degré ;
for ( int k = 0 ; k < degré ; k++ ) {
Lu[k] = false ; MesALire[k].signal()
};
if (nbL > 0) DernierLect.wait() ;
/* nbL == 0 */
libre = true ; AccèsLibre.signal() ;
}
/* lecture du message courant sur la sortie s */
Message Lire ( int s ) {
if (Lu[s]) MesALire[s].wait() ;
/* nbL > 0 /\ ¬ Lu[s] */
nbL-- ; Lu[s] = true ;
Message Rep = case ;
if (nbL == 0) DernierLect.signal() ;
return Rep ;
}
/* constructeur permettant d'engendrer un objet canal avec p sorties */
Canal ( int p ) {
degré = p ;
Lu = new bool[degré] ; MesALire = new condition[degré] ;
for ( int k = 0 ; k < degré ; k++ ) Lu[k] =true ;
}
}
Ce document a été traduit de LATEX par
HEVEA.