Gilles Dequen

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
===== Crible d'Erathostène Multi-Processus =====

Ce TP a pour objet de pratiquer la programmation multi-processus et la redirection des flux d'entée/sortie. La finalité de ce travail est d'être en mesure de mettre en place un filtre multi-processus pour la génération de nombres premiers. Pour cela .

Pour mettre en oeuvre ce programme, vous allez devoir vous munir d'un éditeur et d'un compilateur ''C''. Vous devrez utiliser les primitives système du langage ''C'' : ''fork'', ''wait'' et ''signal'' pour la création et la terminaison d'un processus, ''pipe'', ''dup'', ''open'' et ''close'' pour la création et la la redirection de flots d'entrée/sortie dans les tubes.

==== Principe général de l'algorithme ====

L'algorithme proposé calcule tous les nombres premiers contenus dans l'intervalle des ''unsigned int'' définit par le langage ''C''. Le principe de base est le suivant. On souhaite construire une chaine de processus reliés par des tubes. Chaque processus lit sur son entrée standard un flux d'entiers. **La première valeur de ce flux d'entrée devra être mémorisée**. Le processus génère alors une sortie standard - éventuellement redirigée vers un tube - son flux d'entrée privé de tous les éléments divisibles par la valeur mémorisée.

==== Q.1 - Première boucle ====

Ecrivez un programme ''C'' qui initialise une variable entière à 2 et qui envoie sur sa sortie standard la liste de tous les entiers supérieurs à 2 et inférieurs ou égal à 10000.

==== Q.2 - Premier tube ====

Modifiez le programme précédent afin que notre premier processus **A** soit le père d'un processus << fils >> **B** et qu'ils soient tous deux reliés par un tube. Les tâches réalisées sont les suivantes :

  * **A** écrit dans le tube la liste de tous les entiers supérieurs ou égal à 2 et inférieurs ou égal à 10000. Cette écriture se fait dans l'ordre croissant à partir de 2.
  * **B** lit la première valeur ''x'' du tube et la mémorise. Il affiche sur sa sortie standard toutes les valeurs qui ne sont pas divisibles par ''x''.

==== Q.3 - Construction de d'une chaine de filtrage ====

Etendre le principe décrit à la question 2. Pour ce faire, on crée un processus qui va produire la liste de tous les entiers supérieurs ou égal à 2 et inférieurs ou égal à 10000. Ce premier processus (i.e. //processus père//) est relié par un tube à un //processus fils//. Ce processus fils, suivant le principe décrit ci-dessus, lit la valeur 2 et renvoie sur sa sortie standard l'ensemble des valeurs de son entrée standard non divisibles par 2 (i.e dans ce cas, les nombre impairs). Toutefois, lors de la lecture du premier nombre non-multiple de 2, il va lui-même créer son processus fils, en le reliant par un tube. Ce troisième processus va filtrer sur les multiples du nouveau nombre premier, en l'occurrence 3.

Ainsi de suite, on construit une suite de processus chaînés entre eux, qui filtrent chacun les multiples d'un nombre premier. Un nombre qui arrive au bout de la chaîne sans être filtré est alors premier. En conséquence, il provoque la création d'un processus supplémentaire.

==== Q.4 - Arrêt par signal ====

On modifie le code précédent afin que la suite de valeurs transmises par le premier processus ne se termine pas à 10000 mais soit potentiellement infinie. Pour interrompre le calcul, on enverra un signal (''CTRL-C'' par exemple) au processus père qui enverra alors une valeur particulière dans le tube (par exemple ''0''), ou transmettra un signal au premier fils. Les processus fils seront alors amenés à se terminer après avoir affiché leur nombre premier et transmis le zéro ou le signal.