Examen mai 2010 - Ensiwiki - Ensimag

ENSIMAG 2ème Année
Mercredi 19 mai 2010 EXAMEN DE
SYSTEMES D'EXPLOITATION ET PROGRAMMATION CONCURRENTE Durée : 3 heures
Documents autorisés Il est demandé de rédiger les solutions dans un pseudo langage
(Pascal, Ada...) en utilisant les mêmes conventions qu'en cours
et TD ; il est indispensable de respecter les notations et les
indications de l'énoncé, faute de quoi la solution sera
considérée comme fausse.
La clarté et la concision des solutions seront des éléments
importants d'appréciation : lorsqu'il est demandé des programmes,
ceux-ci sont généralement suffisants, et d'éventuelles
explications complémentaires devront être très concises ; et
lorsqu'il est demandé une réponse textuelle, ne pas dépasser le
nombre de lignes maximum demandé : le correcteur ne lira plus ce
que vous écrirez au delà...
_____________________________________________________
I - Exercices de synchronisation Exercice 1 :
Soient 3 processus exécutant chacun le programme
suivant :
P1 : Tantque V faire ... ; A1 ; ... ;
refaire
P2 : Tantque V faire ... ; A2 ; ... ;
refaire
P3 : Tantque V faire ... ; A3 ; ... ;
refaire
Compléter ces programmes en utilisant des sémaphores,
pour réaliser les synchronisations demandées
ci-dessous. On définira le plus petit nombre possible de
sémaphores, et on précisera la valeur initiale de leur
compteur. On pourra, si nécessaire introduire un ou des
processus supplémentaires.
Question 1 : Les actions Ai ne sont jamais simultanées,
et se déroulent dans un ordre quelconque.
Question 2 : Les actions Ai ne sont jamais simultanées,
et se déroulent toujours en suivant l'ordre
A1 A2 A3 A1 A2 A3 A1 A2 A3 ...
Question 3 : Les actions Ai ne sont jamais simultanées,
et se déroulent toujours en suivant l'ordre
A1 (A2 OU A3) A1 (A2 OU A3) A1 ...
Question 4 : Les actions Ai peuvent être simultanées, et
se répètent toujours globalement - par exemple :
(A2 A1 A3 ) ( A1 A3 A2 ) ( A2 A3 A1 ) ...
Exercice 2 : le problème des trois fumeurs
Le fonctionnement de 4 processus est décrit par
l'analogie suivante : 3 processus fumeurs et un processus
fournisseur sont réunis autour d'une table. Pour fumer, 3
ingrédients sont nécessaires : du tabac, du papier, et une
allumette.
Chaque fumeur est un processus cyclique qui dispose, en
quantité illimitée, d'un de ces ingrédients : l'un du papier,
le second du tabac, et le troisième des allumettes ; il doit
donc attendre et prendre sur la table les deux ingrédients qui
lui manquent. Lorsqu'un fumeur a fini de fumer, il réveille le
processus fournisseur, qui dépose sur la table 2 des 3
ingrédients nécessaires, choisis au hasard, et se rendort.
Question 1 : on suppose que le premier fumeur, qui
dispose de tabac, demande, toujours dans le même ordre, d'abord
du papier, puis des allumettes ; le deuxième demande des
allumettes puis du tabac, le troisième du tabac puis du papier.
Donnez les algorithmes des 4 processus en utilisant des
sémaphores - dont un sémaphore associé à chaque ingrédient, et
une procédure alea(var i, var j) qui retourne i et j dans
[1..3] avec i != j.
Y a-t-il risque d'interblocage ? Expliquer pourquoi.
Question 2 : peut-on éviter ce risque en modifiant
l'ordre dans lequel un ou des processus demandent les
ingrédients dont ils ont besoin ?
Question 3 : une autre solution consiste à associer des
sémaphores non aux ingrédients que demandent les fumeurs, mais
à ceux dont ils disposent.
Donnez la nouvelle version des algorithmes.
II - Exclusion mutuelle et lecteurs/rédacteurs par
serveur
Dans de nombreux systèmes, les outils de programmation
des synchronisations qui sont offerts aux programmeurs ne sont
ni les moniteurs ni les sémaphores, mais la communication par
boite aux lettres (ou l'envoi de message).
Pour réaliser une synchronisation complexe entre des
processus, il faut alors créer un processus serveur qui la gère
: les processus qui doivent se synchroniser envoient une
demande à ce serveur, et attendent une réponse qui leur
permettra de continuer ; de la même façon, lorsqu'ils libèrent
quelque-chose qui peut permettre à un autre processus en
attente de continuer, ils envoient cette information au
serveur. Le serveur reçoit toutes ces informations, tient à
jour des variables représentant l'état de la synchronisation,
range les demandes en attente, ou en reprend certaines pour
relancer les processus qui les avaient émises en leur envoyant
la réponse qu'ils attendent.
On a vu en cours que, dans un système centralisé,
envoyer un message à un processus consiste à le déposer dans
une boite aux lettres où ce processus viendra la retirer. On
rappelle que les boites aux lettres sont des objets de type
tampon, qui sont des moniteurs munis des procédures deposer et
retirer ; un processus serveur est généralement muni d'une
boite que l'on appelle BalServeur, et chaque processus p
dispose d'une boite privée BalPriv[p] sur laquelle il peut
attendre de recevoir une réponse. On dispose d'une fonction
moimeme qui retourne le numéro du processus qui est en train de
s'exécuter.
On pourra aussi utiliser des objets de type file,
manipulables par les fonctions et procédures vues en cours et
en TD : entrer(element,file), sortir(varelement,file),
vide(file)return(bool), ....
Question 1 :
On peut utiliser un serveur de ce type pour réaliser des
synchronisations très simples, comme l'exclusion mutuelle (même
si cela peut paraître une façon un peu lourde de le faire) : le
processus qui veut entrer en section critique doit en faire la
demande au processus serveur ServeurMutex, et attendre sa
réponse ; et lorsqu'il quitte la section critique, il doit le
lui signaler. On appellera BalServeurMutex la boite au lettres
de ce serveur, et fatt la file dans laquelle il range les
processus en attente.
Préciser la structure des messages échangés, et donner
le programme de ce serveur, ainsi que les instructions
exécutées par les processus qui veulent entrer en section
critique et en sortir.
Question 2 :
On peut aussi réaliser les exclusions entre lecteurs et
rédacteurs de cette façon.
Rappelons que l'exclusion entre lecteurs et rédacteurs
consiste à contrôler les accès que plusieurs processus peuvent
essayer de faire simultanément à une même donnée, à un même
ensemble de données, ou à un fichier : toutes les lectures
doivent pouvoir s'exécuter en même temps ; par contre, une
écriture ne peut avoir lieu que seule, c'est-à-dire en
l'absence de toute autre écriture et de toute lecture.
Les processus qui veulent accéder en lecture aux données
(ou au fichier), dénommés « lecteurs », doivent être programmés
de la façon suivante :
début_lire ; /* obtenir l'autorisation de lire */

fin_lire ; /* signaler la fin de lecture */
et ceux qui veulent écrire, les « rédacteurs » :
début_écrire ; /* obtenir l'autorisation d'écrire */

fin_écrire ; /* signaler la fin de l'écriture */
On demande de préciser le contenu de début_lire,
fin_lire, début_écrire, fin_écrire, la structure des messages
échangés, et le programme d' un serveur ServeurLectRedac muni
d'une boite aux lettre BalServeurLR, et qui donne priorité aux
lecteurs sur les rédacteurs,
2.1 : en admettant qu'il y ait risque de privation
(indication : utiliser 2 files d'attente) ;
2.2 : donner les modifications à apporter pour éviter ce
risque. Réalisation des mêmes synchronisations dans un environnement
réparti
On se situe maintenant dans un environnement réparti, c'est-
à-dire composé de plusieurs ordinateurs interconnectés qui
communiquent par messages. Il existe, sur chaque machine, un
système de communication qui permet à chaque processus d'envoyer
un message à un autre processus par l'appel de la procédure
envoyer(processus,message) et de recevoir un message et de le
ranger dans une variable m par l'appel de recevoir(var m) ;
recevoir met en attente le processus qui l'exécute jusqu'à
réception d'un message. La désignation de chaque processus
inclut le numéro de la machine sur laquelle il se trouve, et
l'on n'aura donc pas à se préoccuper des adresses de machines.
On remarquera que, pour deux processus situés sur la même
machine, envoyer(processus,message) est tout à fait équivalent à
déposer le message dans une boite aux lettres associée au
processus destinataire (boite aux lettres du serveur pour un
processus serveur, boite aux lettres privée pour les autres), et
recevoir(var m) équivalent à retirer un message de la boite aux
lettres associée au processus en exécution.
On se pose le problème de réaliser dans cet environnement le
même type d'exclusion qu'aux questions 1 et 2 - en particulier
pour permettre aux processus d'accéder à des informations qui
peuvent être distribuées ou dupliquées sur plusieurs machines.
Question 3 :
Pour réaliser une exclusion mutuelle générale, la solution
la plus simple consiste à installer sur l'une des machines un
processus ServeurMutex analogue à celui de la question 1,