PR : Contrôles des connaissances
3. Majuscules, Shadoks et franges
examen de rattrapage 12/06/2017

Vous créerez dans votre répertoire personnel, s'il n'est pas déjà là, le sous-répertoire "public_html" dans lequel vous placerez toutes vos réponses, qui y seront automatiquement ramassées. Seuls les fichiers demandés le seront, aussi il est impératif de bien contrôler leur création: nom exact (sans confondre minuscules et majuscules, tiret et souligné etc, ni placer des espaces autour du nom) et droit d'accès 640 pour un fichier non exécutable et droit d'accès 750 pour ses répertoires parents ou un fichier exécutable. Dans le cas où une réponse nécessite les fonctions écrites dans une réponse précédente, celles-ci ne doivent pas être recopiées, le recours au mécanisme d'inclusion des langages de programmation étant plus fiable et plus lisible.

Notes sur 20.

1. File de message POSIX


Warning: fsockopen(): unable to connect to ssl://www-master.ufr-info-p6.jussieu.fr:8083 (Connection refused) in /dsk/www-master/html/2016/ecrire/inc/distant.php on line 699

Warning: fsockopen(): unable to connect to ssl://www-master.ufr-info-p6.jussieu.fr:8083 (Connection refused) in /dsk/www-master/html/2016/ecrire/inc/distant.php on line 699

1.1 Serveur (2  point(s))

Ecrivez un premier programme (appelé serveur dans la suite) qui crée une file de messages POSIX de nom "/file_exam" et qui traite NB_REQUETE (déclarée comme constante) requêtes sur cette file. Le traitement d’une requête consiste à récupérer une chaîne de caractère (d’au plus 256 caractères) envoyée via la file de messages par un client (écrit à la question 2), à passer cette chaîne de caractères en majuscule (pensez à la fonction toupper qui renvoit le caractère majuscule correspondant au caractère passé en paramètre) puis à afficher le pid du client ainsi que la chaîne de caractères en majuscule.

Exemple d'appel :
$PWD/bin/serveur_file
Barème

- 
- 


1.2 Client (2  point(s))

Ecrivez un second programme qui correspond au client du serveur écrit à la question 1. Ce client prendra la chaîne de caractères à envoyer au serveur en paramètre sur sa ligne de commande et n’attendra aucune réponse du serveur avant de se terminer.

Exemple d'appel :
$PWD/bin/client_file aenvoyer
Barème

- 
- 

2. Shadokeries

Le but de cet exercice est d’écrire un programme créant quatre threads (en plus du thread initial). Chacun effectuera une attente de durée aléatoire puis écrira une des lettres de l’alphabet Shadok (GA, BU, ZO et MEU) en fonction de son rang de création. Les threads devront se synchroniser de façon à afficher systématiquement l’alphabet dans l’ordre indépendamment des tirages aléatoires effectués.

Voici le squelette du code C que vous allez compléter dans les questions suivantes :

#define _XOPEN_SOURCE 700

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <ctype.h>
#include <errno.h>

#define NB_SHADOK 4

char *lettre[4]={"GA","BU","ZO","MEU"};

        /* Déclaration des variables globales si nécessaire */

void *thread_shadok(void *arg){

                /* Code à écrire en question 2 */

}

int main(){
        int i;
        int *p;
        pthread_t tid[4];

        srand(time(NULL));

        printf("Les shadoks vont commencer\n");

                /* Code à écrire en question 1 */

        printf("Les shadoks ont fini\n");
        return EXIT_SUCCESS;
}

Warning: fsockopen(): unable to connect to ssl://www-master.ufr-info-p6.jussieu.fr:8083 (Connection refused) in /dsk/www-master/html/2016/ecrire/inc/distant.php on line 699

Warning: fsockopen(): unable to connect to ssl://www-master.ufr-info-p6.jussieu.fr:8083 (Connection refused) in /dsk/www-master/html/2016/ecrire/inc/distant.php on line 699

2.1 Main (2  point(s))

Complétez le code de la fonction main de façon à assurer la création des quatre threads exécutant la fonction thread_shadok. Vous prendrez garde à passer en paramètre à chaque thread son rang de création et de stocker son tid dans le tableau tid. Votre code doit de plus assurer que l’affichage final "Les shadoks ont fini" ne soit réalisé qu’une fois les quatre threads effectivement terminés.

Exemple d'appel :
$PWD/bin/shadok
Barème

- 
- 


2.2 Threads (4  point(s))

Donnez le code de la fonction thread_shadok réalisant le traitement décrit ci-dessus. La synchronisation entre les threads sera exclusivement réalisée à l’aide de variables conditions. Vous préciserez clairement les déclarations des variables globales le cas échéant.

Barème

- 
- 
- 
- 

3. Parcours d’arbre, fork et signaux.

On s’intéresse au problème suivant : déterminer si deux arbres binaires ayant pour feuilles un caractère de l’alphabet ASCII ont la même suite de feuilles lorsqu’on les parcourt, indépendamment de leurs nœuds. Par exemple les deux arbres binaires :

|----|---- c
|    |
a    b

et

|---------- c
|  
|----  b
|
a

ont même suite de feuilles bien qu’ils soient balancés différemment (le premier a une feuille comme fils gauche, alors que le deuxième a un sous-arbre).

Si deux arbres n’ont pas le même nombre de feuilles, ils n’ont évidemment pas la même suite de feuilles, même si la suite du plus petit est égale au début de même longueur de la suite du plus grand. On considère aussi que l’ordre des feuilles doit être respecté, l’arbre ci-dessous n’ayant pas même suite que les deux ci-dessus :

|---------- b
|  
|---- c
|
a

Pour fixer l’implémentation, vous sont fournies une structure C arbrebin implémentant un arbre binaire en C, et deux fonctions ab1 et ab2 construisant les deux arbres binaires ci-dessus.


Warning: fsockopen(): unable to connect to ssl://www-master.ufr-info-p6.jussieu.fr:8083 (Connection refused) in /dsk/www-master/html/2016/ecrire/inc/distant.php on line 699

Warning: fsockopen(): unable to connect to ssl://www-master.ufr-info-p6.jussieu.fr:8083 (Connection refused) in /dsk/www-master/html/2016/ecrire/inc/distant.php on line 699

Warning: fsockopen(): unable to connect to ssl://www-master.ufr-info-p6.jussieu.fr:8083 (Connection refused) in /dsk/www-master/html/2016/ecrire/inc/distant.php on line 699

Warning: fsockopen(): unable to connect to ssl://www-master.ufr-info-p6.jussieu.fr:8083 (Connection refused) in /dsk/www-master/html/2016/ecrire/inc/distant.php on line 699

3.1 Fonction Fringe (1  point(s))

Ecrire la fonction C

void fringe (struct arbrebin *a, int fildes)

qui parcourt récursivement l’arbre donné en premier argument, et qui, à chaque rencontre d’une feuille, l’écrit sur le flux donné en deuxième argument.

Barème

- 


3.2 Comparer (3  point(s))

Ecrire un programme C construisant 2 arbres binaires, créant 2 processus fils et allouant 2 tubes. Chaque processus fils parcourt un des arbres et écrit sur un des tubes. Comment rédiger ce programme pour que le processus principal lise les deux tubes, caractère par caractère, affiche leur comparaison et s’arrête dès qu’ils se révèlent différents si c’est le cas ? On évitera de laisser orphelins les processus fils.

Exemple d'appel :
$PWD/bin/samefringe_full
Barème

- 
- 
- 


3.3 Suspendre (3  point(s))

La solution précédente a le défaut de toujours parcourir l’intégralité des deux arbres, ce qui n’est pas acceptable par exemple en cas d’arbre volumineux différant dès leur première feuille. Donner une nouvelle version de la fonction fringe suspendant le processus à chaque feuille rencontrée, et indiquer comment modifier le programme principal pour qu’il relance ou supprime les processus selon que les deux feuilles sont égales ou non.

Exemple d'appel :
$PWD/bin/samefringe_opt
Barème

- 
- 
- 


3.4 Interrompre (3  point(s))

On souhaite enfin modifier cette dernière version pour que la frappe de ^C au clavier permette d’interrompre par le signal SIGINT le processus principal, sans que ce signal interrompre l’un et/ou l’autre de ses processus fils. Le processus principal doit alors forcer ses processus fils à se terminer, et éviter qu’ils ne deviennent orphelins avant de se terminer lui-même.

Exemple d'appel :
$PWD/bin/samefringe_sigint
Barème

- 
- 
-