Examen de Systèmes - Master I - 2007-2008

Exercice

int i=-1,j=10;
printf("%d %d %p %p\n",i,j,&i,&j);
i=fork();
printf("%d %d %p %p\n",i,j,&i,&j);
if (i==0) j++;
printf("%d %d %p %p\n",i,j,&i,&j);

Indiquez quelles valeurs seront affichées (certaines suppositions pourront être faites) et expliquez pourquoi.

Exercice

On se propose de réaliser un tri par fusion distribuée utilisant des processus et divers moyens de communication associés. La fusion consiste à obtenir à partir de deux listes triées, une liste triée rassemblant les éléments des deux listes. Par exemple: fusion([1,3,7,8],[2,4,5,6])=[1,2,3,4,5,6,7,8]. L'idée générale est d'utiliser un arbre de processus communicants se répartissant le calcul.

Les feuilles de cet arbre sont des processus réalisant un calcul élémentaire consistant à lire deux valeurs sur leur entrée standard puis renvoyant sur leur sortie standard les deux entiers dans l'ordre naturel.

écrire le code feuille.c de l'exécutbale feuille correspondant à une feuille de l'arbre.

Les noeuds de l'arbre sont des processus réalisant les opérations suivantes :

création de deux fils et de tubes anonymes associés permettant d'obtenir une communication du père vers chacun des deux fils (tubes descendants) et de chaque fils vers le père (tubes montants), puis recouvrement des deux fils par un programme adéquat, le tout selon le schéma suivant :

$\includegraphics[width=7cm]{Image001.eps}$
distribution : réception sur l'entrée standard d'entiers distribués alternativement sur les tubes descendants, et ce jusqu'à épuisement de l'entrée standard,
fusion : réception sur les tubes montants des données triés par les fils et envoi sur la sortie standard du résultat de la fusion.

écrire le code de la fonction creefils (avec paramètres adéquats)
écrire le code de la fonction distribution (avec paramètres adéquats)
écrire le code de la fonction fusion (avec paramètres adéquats)
écrire le code noeud.c de l'exécutable noeud qui lorsqu'il est lancé avec un argument représentant un nombre entier positif crée un arbre de hauteur correspondant à cet entier. La hauteur 0 correspondant au cas particulier de l'exécution du programme feuille.

Problème

On se propose d'utiliser différents concepts systèmes pour réaliser la simulation d'un « self-service ». Chaque individu qui désire manger doit faire la queue pour passer devant chacun des 5 stands (entrées, plats, fromage, desserts et boissons). On notera qu'il ne peut y avoir plus d'une personne à la fois devant chaque stand. D'autre part, une personne peut ne rien prendre et ne faire que passer devant un stand donné, toutefois et quelle que soit sa décision, son passage prend toujours un certain temps (nombre de secondes tirées au hasard entre 1 et 60). De l'autre coté des stands, des employés sont présents pour réaliser le service demandé (aller chercher le plat correspondant et le donner au demandeur). On notera que toutes les denrées sont en nombre infini.

La simulation doit faire en sorte que chaque individu soit représenté par un processus et que le « service » soit un processus constitué de threads chacun représentant un employé (donc 5 au total). La présence d'un individu dans un stand donné est représentée par un sémaphore.

On demande donc:

quel mécanisme envisagez-vous de mettre en place pour qu'un client désireux de manger un plat puisse le faire savoir à l'employé concerné et que celui-ci puisse lui servir en retour ?
écrire le code du programme qui sera exécuté pour représenter un client.
écrire le code du programme qui sera exécuté pour représenter le « service ».
on voudrait faire en sorte que le nombre de chaque denrées servies puisse être consulté à tout instant, quels mécanismes sont à mettre en place ?
modifiez le code du « service » en conséquence.

Jean-Baptiste Yunès 2008-02-05