CSC 4103 – Programmation système

Contrôle Final 1 – Année 2025/2026

Le barème est donné à titre indicatif

Durée du CF: 2h
Document autorisé: polycopié du cours CSC4103

Echauffement (2 points)

On dispose de l'arborescence suivante:

libtab/
  include/
     tab.h
  lib/
     libtab.so
main/
  foo.c
  foo.h
  foo.o
  main.c
  main.o
  Makefile
	

Le fichier d'entête tab.h est inclus dans le fichier foo.c.

Indiquez la ligne de commande à exécuter depuis le répertoire main pour de générer l'exécutable nommé main à partir des fichiers foo.o et main.o, en en utilisant la bibliothèque tab située dans l'arborescence.

Donnez le contenu du fichier main/Makefile. Ce fichier doit permettre de générer les fichiers objets foo.o et main.o, et l'exécutable main. Il doit également définir une règle clean permettant de supprimer les fichiers générés.

Implémentation d'une arbre binaire de recherche (5.5 points)

Le but de l'exercice est d'implémenter plusieurs fonctions permettant de manipuler un arbre binaire de recherche permettant de stocker des couples (clé, valeur). Pour cet exercice, les clés sont des entiers, et les valeurs des chaînes de caractères.

On souhaite ici pouvoir associer plusieurs valeurs à une clé. L'arbre contient donc une arborescence de struct node, où chaque struct node correspond à une clé key. Chaque struct node contient une liste chainée des valeurs struct value associées à la clé key.

Par ailleurs, l'arbre est trié en fonction des valeurs des clés: pour tout noeud n ayant pour clé k, toutes les clés ayant une valeur < k sont stockées dans le sous arbre gauche de n, et toutes les clés ayant une valeur > k sont stockées dans le sous arbre droit de n.

Les structures de données et fonctions à implémenter dans cet exercice sont définies ici:

struct value {
  char* value;
  struct value* next;
};

struct node {
  int key;
  struct value* values; // liste chaine des values associées à key
  struct node* left;    // sous arbre dont les clés sont inférieures à key
  struct node* right;   // sous arbre dont les clés sont supérieures à key
};

/* Alloue et initialise un struct value */
struct value* new_value(const char* value);

/* Alloue et initialise un struct node */
struct node* new_node(int key, const char* value);

/* Insert un struct node dans un arbre */
struct node* insert(struct node* tree, int key, const char* value);

/* Affiche le contenu d'un arbre */
void print_tree(struct node* tree);
	

Voici un exemple de programme utilisant cet interface:

int main(int argc, char**argv) {
  struct node* scores = NULL;
  for(int i=0; i<5; i++) {
    char name[128];
    printf("Nom du joueur ?\n");
    fgets(name, 128, stdin);
    name[strcspn(name, "\n")] = 0; // supprime le \n terminal de la chaine

    char score_str[128];
    printf("Score du joueur ?\n");
    fgets(score_str, 128, stdin);

    scores = insert(scores, atoi(score_str), name);
  }

  printf("Scores des joueurs:\n");
  print_tree(scores);
  return EXIT_SUCCESS;
}
	

Et voici un exemple d'affichage produit par le programme:

Scores des joueurs:
AlphaX
Frag666
TempeteSniper
FpsGuerrier, Epic666, ChaosMaster
AcierXxX
VipereTueur
FeuPwn
NoobKiller, NightSlayer
ProHunter
W1d0wMak3r
Neon888
	

new_value et new_node (1 point)

Implémentez les fonctions struct value* new_value(const char* value) et struct node* new_node(int key, const char* value).

Ces fonctions allouent et initialisent un nouveau struct value (ou struct node). La fonction new_node initialise le champ values en appelant new_value.

insert (2 point)

Implémentez la fonction struct node* insert(struct node* tree, int key, const char* value).

Cette fonction insère un nouveau struct node dans l'arbre tree et retourne la racine de l'arbre après l'insertion.

print_tree (2 point)

Implémentez la fonction void print_tree(struct node* tree).

Cette fonction affiche le contenu de l'arbre de manière triée: elle affiche la clé la plus petite et la/les valeurs associées, puis passe à la clé suivante.

Remote Procedure Call (5 points)

Le but de cet exercice est d'implémenter un système de Remote Procedure Call (RPC) utilisant des processus. Ce système doit permettre de créer n processus qui exécuteront chacun une fonction function définie par le programme appelant. Le système doit également récupérer la valeur renvoyée par la fonction.

On souhaite pouvoir utiliser ce système pour calculer la valeur de π par la méthode de Monte-Carlo. Pour cela, il est nécessaire de choisir au hasard un grand nombre de points de coordonnées (x,y), où 0 < x < 1 et 0 < y < 1. La valeur π/4 peut alors être approximée en calculant le nombre de points pour lesquels x*x + y*y ≤ 1.

Pour cet exercice, on souhaite donc appeler un grand nombre de fois la fonction pi_monte_carlo, et calculer la somme des valeurs renvoyées par la fonction:

int pi_monte_carlo() {
  double x = drand48();
  double y = drand48();
  double result = x*x + y*y;
  if(result <= 1) return 1;
  return 0;
}
	

4 points

Implémentez une fonction nommée rpc. Cette fonction doit prendre en paramètre l'adresse d'une fonction ayant la même signature que pi_monte_carlo (correspondant à la fonction à invoquer), et un entier n (correspondant au nombre d'invocations de la fonction). La fonction rpc retourne un entier correspondant à la somme des valeurs retournées par les fonctions invoquées.

La fonction rpc doit:

Créer n processus. Chaque processus enfant doit appeler la fonction à invoquer et stocker le résultat de cette fonction dans une variable locale nommée result. Chaque processus enfant doit ensuite se terminer avec le code de retour result.
Attendre la terminaison des n processus enfants et récupérer leur code de retour.
La fonction rpc retourne la somme des codes de retour des processus

1 point

Implémenter la fonction main. Elle doit appeler rpc pour invoquer 1000 fois la fonction pi_monte_carlo, puis afficher la valeur estimée de π sous la forme d'un flottant. Pour cela, il est nécessaire de diviser la valeur retournée par rpc par le nombre d'invocation (1000), puis multiplier par 4.

Parallélisation d'un calcul (10 points)

Le système de RPC implémenté dans l'exercice précédent n'est pas très performant, et on souhaite calculer l'approximation de π par Monte Carlo plus rapidement en utilisant des threads. L'objectif de cet exercice est de concevoir un programme qui:

Crée 4 threads de calcul. Chaque thread de calcul appelera la fonction pi_monte_carlo pour effectuer nb_batches x nb_sample_per_batch mesures. Ces mesures seront regroupées par lot (batch) de nb_sample_per_batch mesures. Lorsqu'un lot est terminé, le thread qui l'a produit remplit une structure contenant le nombre de mesures et la somme de ces mesures, et il ajoute cette structure à une liste chaîne contenant les lots de mesures.
Crée un thread chargé de récupérer les lots de mesures, calculer une estimation de la valeur de π et l'écrire dans un fichier nommé mesures.txt.

Le fichier mesures.txt permet donc de voir l'évolution de l'estimation de π en fonction du nombre de mesures. Voici un exemple de contenu attendu:

#nb_samples pi_estimate
2.640000
2.920000
2.880000
2.980000
3.008000
2.980000
3.017143
3.035000
3.048889
3.052000
3.087273
3.100000
3.098462
3.114286
3.109333
3.092500
3.115294
3.124444
3.132632
3.124000
	

La communication entre les threads de calcul et le thread chargé de récupérer les lots de mesures se fait via une liste chaînée définie comme suit:

struct produced_data {
  struct produced_data* next; // lot de mesures suivant dans la liste
  int nb_samples; // nombre de mesures
  int sum; // somme des mesures
};

struct produced_data * produced_data = NULL; // liste chaînée contenant les mesures
	

Dans cet exercice, des threads accèderont de manière concurrente à des structures de données. Vous veillerez à garantir la consistence des données, par exemple en utilisant des verrous lorsque c'est nécessaire. Si besoin, indiquez sur votre copie les nouvelles structures à définir (ou modifier) et les éventuelles variables globales à déclarer.

4 points

Implémentez une fonction nommée worker_thread qui sera invoquée lors de la création des threads de calcul. Cette fonction doit:

Récupérer via son paramètre un entier nb_batches correspondant au nombre de lots à générer, et un entier nb_samples_per_batch correspondant au nombre de mesure par lot.
Générer nb_batches lots en appelant la fonction int pi_monte_carlo(). Pour chaque lot, le thread ajoute un struct produced_data à la liste chaine produced_data

Donnez également le code à ajouter dans la fonction main pour créer ces 4 threads de calcul attendre leur terminaison.

4 points

Implémentez une fonction nommée writer_thread qui sera invoquée lors de la création du thread chargé de récupérer les lots de mesures. Cette fonction doit:

Ouvrir en écriture le fichier output.txt dans lequel seront stockées les mesures.
Dans une boucle infinie, récupérer et enlever un lot de mesures de la liste produced_data
Pour chaque lot de mesures, mettre à jour l'estimation de la valeur de π, puis écrire dans output.txt une ligne de caractères ASCII contenant le nombre total de mesures et la valeur estimée de π (par exemple 1900: 3.132632).

Pour cette question, on ne se soucie pas de la terminaison du thread. Ce problème sera abordé à la question suivante.

2 points

On souhaite maintenant faire en sorte que le thread writer_thread se termine après avoir traité toutes les mesures générées par les threads de calcul.

Indiquez les modifications à apporter aux fonctions main et writer_thread pour créer ce thread avant la création des threads de calcul, et pour le faire terminer après la fin des threads de calcul.