brouillon - Ensiwiki - Ensimag
19 mai 2010 ... en utilisant les mêmes conventions qu'en cours et TD ; il est indispensable de ...
On définira le plus petit nombre possible de sémaphores, et on ...
part of the document
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 : lorsquil est demandé des programmes, ceux-ci sont généralement suffisants, et déventuelles explications complémentaires devront être très concises ; et lorsquil 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 lordre
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 lordre
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 lanalogie suivante : 3 processus fumeurs et un processus fournisseur sont réunis autour dune 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, dun de ces ingrédients : lun 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. Lorsquun 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, dabord 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 dinterblocage ? Expliquer pourquoi.
Question 2 : peut-on éviter ce risque en modifiant lordre 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 sexécuter en même temps ; par contre, une écriture ne peut avoir lieu que seule, cest-à-dire en labsence 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, cest-à-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 denvoyer un message à un autre processus par lappel de la procédure envoyer(processus,message) et de recevoir un message et de le ranger dans une variable m par lappel de recevoir(var m) ; recevoir met en attente le processus qui lexécute jusquà réception dun message. La désignation de chaque processus inclut le numéro de la machine sur laquelle il se trouve, et lon naura 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 dexclusion quaux 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 lune des machines un processus ServeurMutex analogue à celui de la question 1, et connu de tous les processus qui ont besoin de rentrer en exclusion mutuelle (et d'en sortir).
Comment faut-il modifier les solutions de cette question 1 pour les transposer dans ce nouvel environnement ?
On sinterdit souvent ce type de solution ; expliquer brièvement pourquoi (4 lignes maximum)
Question 4 :
Une façon distribuée de gérer ces synchronisations consiste à utiliser la technique du jeton circulant sur un anneau virtuel. On suppose installé sur chaque machine un processus ServeurLocal, qui reçoit un message du serveur local installé sur la machine située en amont, et le renvoie, une fois le traitement effectué, au serveur local de la machine située en aval (quil connaît sous la désignation de suivant ; cette variable est positionnée lors de linitialisation de lanneau virtuel, et on naura pas à sen préoccuper ). Ce message qui circule de machine en machine est appelé le jeton.
(On a vu en cours une solution basée sur lutilisation dun moniteur mutex_r, et dun processus station ; il est demandé ici de remplacer ceci par lutilisation dun processus serveur.)
Pour demander l'exclusion mutuelle, les processus doivent envoyer un message de demande au processus ServeurLocal installé sur leur machine et attendre son accord ; quand ils ont terminé, ils doivent lui envoyer un message pour le lui signaler.
Le principe consiste, pour chaque serveur local, à attendre le jeton pour attribuer la section critique à un des processus qui l'a demandée, puis à renvoyer le jeton sur lanneau virtuel quand la section critique est terminée. Contrairement à la solution vue en cours (qui utilisait un moniteur défini pour cela), le processus qui veut entrer en section critique doit envoyer un message au serveur local, et attendre sa réponse ; cest le serveur local qui doit gérer les attentes si plusieurs processus locaux veulent utiliser la section critique en même temps.
4.1 : Comment faut-il modifier la structure message, et les séquences dinstructions exécutées par les processus pour entrer en section critique et en sortir ?
4.2 : Quand une section critique est terminée, vaut-il mieux servir d'abord d'éventuelles autres demandes locales, ou renvoyer tout de suite le jeton sur l'anneau virtuel, et pourquoi ? (4 lignes maximum)
4.3 : Donner le programme du processus ServeurLocal.
Question 5 :
Réaliser une exclusion entre lecteurs et rédacteurs distribués sur un ensemble de sites présente un grand intérêt, parce que cela permet de dupliquer les données en installant des copies sur tous les sites où elles sont utilisées, et de laisser les lectures se faire directement et simultanément, sauf lorsqu'une écriture se produit auquel cas plus aucune lecture ne doit avoir lieu jusqu'à ce que l'écriture ait été répercutée sur toutes les copies.
Pour cela, la solution la plus simple consiste (comme pour l'exclusion mutuelle à la question 3) à installer sur lune des machines un processus ServeurLectRedac analogue à celui de la question 2, et connu de tous les processus qui ont besoin de lire et d'écrire.
Ce serveur doit toutefois différer de celui de la question 2 parce que, lors d'une fin d'écriture, le rédacteur doit lui passer la nouvelle valeur des données, qui doit être répercutée sur toutes les copies avant que l'on ne puisse considérer l'écriture comme terminée.
Modifier les solutions de la question 2 pour les transposer dans ce nouvel environnement.
On supposera que le serveur connaît, sur chacun des N sites sur lesquels une copie a été installée, un serveur de mise à jour ServeurMaj dont l'adresse est rangée dans une liste ListeServeurMaj, et on supposera disposer d'une procédure Diffuser(ListeProcessus, message) qui envoie message à tous les processus de ListeProcessus. On précisera aussi le programme des processus ServeurMaj.
Question 6 :
On peut aussi utiliser la technique du jeton circulant, comme à la question 4 : sur chaque site existe un serveur-jeton local ServeurLocal qui va assurer aussi les fonctions d'exclusion lecteurs/rédacteurs qu'assurait ServeurLectRedac.
En labsence de demande décriture, ce serveur-jeton local autorise les demandes de lectures (sans même attendre que le jeton soit là), et fait suivre sur lanneau virtuel le jeton dès quil arrive. Toute écriture, qui doit être réalisée seule, va nécessiter le jeton et le conserver jusquà ce quelle soit terminée localement ; mais il faut encore répercuter la nouvelle valeur sur toutes les copies, ce qui va être fait en l'insérant dans le jeton auquel on fait faire un tour complet, chaque serveur local répercutant la mise à jour sur la copie locale.
Pour tolérer le maximum d'accès simultanés aux données, on choisira, lors de la mise à jour d'une copie, de faire suivre tout de suite le jeton, et de procéder ensuite à la mise à jour dès que les lectures locales seront terminées (pour cela on utilisera sur chaque site traversé un ServeurMaj). On choisira aussi, lors de la fin dune écriture, de relancer immédiatement les lecteurs et de remettre le jeton en circulation, même si d'autres demandes décriture attendent. Ces choix seront discutés à la question suivante.
6.1 : Préciser les modifications à apporter aux champs de la structure message et aux séquences dinstructions exécutées par les processus pour début_lire, fin_lire, début_écrire, fin_écrire.
6.2 : Donner les programmes des processus ServeurLocal et ServeurMaj (nota : sur chaque site on connaît N , le nombre de sites de l'anneau virtuel, sur lesquels une copie a été installée).
Question 7 :
La synchronisation implémentée à la question précédente tolère un maximum de parallélisme, mais le comportement de l'ensemble des lecteurs et rédacteurs n'est pas strictement identique à ce qu'il serait si tous ces processus disposaient d'une copie unique située dans une mémoire commune. Par exemple, un processus peut, après avoir réalisé une écriture, envoyer un message à un autre processus, qui, s'il lit alors la donnée, ne doit pas la trouver dans l'état d'avant la mise à jour !
Si l'on veut offrir au programmeur cette assurance que tout se passe comme s'il disposait de données partagées situées dans une mémoire commune :
7.1 : sur le site qui termine une écriture, peut-on considérer localement l'écriture comme terminée (et permettre aux lecteurs locaux de passer et au rédacteur de continuer) dès que le jeton portant la mise à jour est parti, ou doit-on attendre d'être certain qu'elle ait bien été répercutée sur toutes les copies ? Qu'est-ce que cela nécessite ? (répondre en 6 lignes maximum)
7.2 : peut-on tolérer que des lectures aient encore lieu alors que les données ont déjà été modifiées sur certains sites, ou faut-il interdire toute lecture partout avant d'autoriser un début d'écriture ? (répondre en 6 lignes maximum)
7.3 : lorsqu'une mise à jour apportée par le jeton a été répercutée sur la copie locale, peut-on laisser les demandes de lectures locales s'exécuter ? ou faut-il ne les autoriser qu'une fois que toutes les copies ont été mises à jour ? Comment réaliser ceci à l'aide du jeton ? (répondre en 8 lignes maximum).
7.4 : donner la structure des messages et le programme des processus ServeurLocal et ServeurMaj qui assurent la même cohérence que le partage des données en mémoire commune.
PAGE
PAGE 2
