Examen de Systèmes II
Licence - Juin 2002

Exercice

On suppose qu'une machine est constituée de $n_f$ frames (pages physiques). Cette machine est utilisée pour exécuter un processus qui fait appel dans l'ordre aux pages virtuelles suivantes : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. On suppose aussi que l'algorithme de choix d'une page à remplacer (lorsqu'aucune frame n'est libre) est un simple FIFO : on remplace la plus ancienne page (sans tenir compte des accès à cette page, la date d'une frame est donc modifiée lorsque qu'une page est chargée). Si avant chaque exécution les frames sont toutes libres :
  1. calculez la séquence de remplacement lorsque $n_f=3$,
  2. calculez la séquence de remplacement lorsque $n_f=4$,
  3. sauriez-vous dire pourquoi cela constitue une anomalie (dite de Belady) ?

Exercice

  1. Écrire un programme, recevant en paramètre un argument représentant un entier $n$, et permettant de construire un ``anneau'' de processus communiquant par tubes, comme sur le schéma suivant ;
    \begin{center}\vbox{\input{anneau.eepic} }\end{center}
  2. Modifier le programme précédent de façon que chaque processus $p_i$ créé dans l'anneau, exécute le code contenu dans le fichier executable_$i$.

Exercice

  1. Écrire un programme permettant d'ajouter un entier (tiré au hasard) à la fin d'un tableau toutes les secondes,
  2. Ajouter une fonction, appelée à la reception du signal SIGUSR1, permettant de calculer puis d'afficher la somme des éléments du tableau,
  3. Ajouter une fonction, appelée à la reception du signal SIGUSR2, permettant de supprimer les éléments impairs du tableau.

Problème

On vous propose d'implanter le crible d'Ératosthène : méthode datant du 3esiècle avant J.C. et permettant de calculer la liste des nombres premiers.

Le crible fonctionne de la manière suivante : écrivez les entiers de 2 à $n$; En partant du début de la liste on recherche le premier nombre non coché et non entouré; Cela indique qu'il est premier alors on l'entoure; Ensuite on l'utilise pour cocher ses multiples (il suffit de sauter du bon nombre de cases); Puis on recommence, jusqu'à épuisement. Voici le crible sur les entiers de 2 à 10 :

\begin{center}\vbox{\input{crible.eepic} }\end{center}
Pour réaliser cela, on vous demande d'utiliser comme ``support'' du crible un segment de mémoire partagé. Le programme devra ``paralléliser'' les éliminations des multiples en utilisant des processus auxiliaires judicieusement lancés et synchronisés. Lorsque le crible sera fini, le programme ``principal'' devra afficher la liste des entiers compris entre $2$ et $n$.

Il est demandé d'écrire un programme principal (de nom crible), prenant en paramètre l'entier $n$. Ce programme sera chargé de créer le segment, l'initialiser, et de lancer le premier processus auxiliaire avec comme paramètre le premier nombre premier (soit 2). Lorsque le travail des processus auxiliaires seront terminés (il faudra détecter la terminaison) le programme principal affichera la liste des nombres premiers et terminera à son tour.

On devra écrire le programme auxiliaire (de nom effacemultiples), prenant en paramètre l'entier à ``entourer'', et dont il faut cocher les multiples. Attention ce processus sera chargé de lancer l'auxiliaire suivant (il lui faudra donc déterminer au passage le nombre premier suivant). Par exemple, effacemultiples 2 lancera effacemultiples 3 qui a son tour lancera effacemultiples 5 et ainsi de suite.

Jean-Baptiste Yunes 2002-09-09