Office

On cherche a faire un simulateur de gestion de guichet, légèrement tiré par les cheveux afin de coller aux éléments déjà fait durant les TP précédents et de ne pas compliquer les choses inutilement.

Description du système

Nous cherchons a faire communiquer des systèmes distant: Un système d’acquisition de tâches (ici, les buzzer), et un système de traitement de tâches (le traitant). Pour bien constater que ce sont deux systèmes distinct, ils seront matérialisé par un processus (programme) différents (input, processor). Ces deux systèmes communiquerons via un fichier (ici, un tube (pipe)) : ./input | ./processor. Afin que notre système soit non trivial, le traitant devra traiter certaines tâches plus prioritairement que d’autres, i.e., certaines tâches devront être traitées avant d’autres, si c’est possible. Pour ce faire, le traitant devra accumuler dans une file de priorité des tâches avant de les traiter. Malheureusement ceci nous imposera d’utiliser des lectures non bloquantes (voir section lectures de fichiers non bloquantes).

digraph {
  rankdir="LR";
  I [shape=record, label="input | {Lire etat buzzer\nConstruire une (ou plusieurs) tâche(s)\nL(es)'écrire(s) sur stdout}"];
  P [shape=record, label="processor | {Tant qu'il y'a des taches à lire\n les mettres dans une file \n Tant qu'il y'a des tâches a traiter,\nles traiter\nS'il n'y en avait aucune faire une pause (1s)}"];
  I -> P [label="task {id, start, payload, ...} "];
}

Le diagramme idéal serait un diagramme de séquence. Cependant si nous vous le fournissons, la quasi totalité du code serait donnée. Désolé.

Sources

Exceptionnellement pour l’année scolaire 24/25, téléchargez le patch suivant puis appliquez le à votre dépôt.

git apply 0001-Adds-Office.patch

Tâches

Une tâche définit l’une unité de traitement de notre système artificiel, elles sont définies dans le fichier task.h.

Elles sont composé de :

  • ID: un numéro unique qui sert à identifier la tâche.
  • payload: la valeur utilise du message (ici, nombre de seconde à attendre, mais on pourrait imaginer un protocole plus intéressant).
  • start: heure avant laquelle la tâche ne peut pas être traitée.

task.h étant inclus à l’identique dans nos deux systèmes, nous les écrirons et lirons directement dans notre code, i.e, sans transformation.

Lectures de fichier non bloquantes

Les lectures sur les fichiers sont, par défauts, bloquantes, i.e., les fonctions de lectures attendent que les données soient disponibles avant de les retourner (ou de retourner une erreur). Cela condamnerait notre traitant (processor) à bloquer sur la lecture d’un message avant de bloquer sur son traitement. En toute généralités, il existe plusieurs solutions à notre problème (multiplexage d’IO avec timeout select, alarmes et gestion de signaux (MI206), threads [attention à la synchronisation], …), nous avons choisi celle qui nous paraissait la plus simple utiliser avec les connaissance actuelle : rendre le flot de lecture non bloquant. Nous vous fournissons pour cela une fonction int set_non_blocking(FILE *strean) qui rend le flot stream non bloquant. Une fois un flot débloqué1, les lectures pourront renvoyer une erreur si aucune donnée n’est disponibles pour l’instant. La macro FAGAIN() permet de distinguer cette erreur, non fatale et temporaire, d’une erreur classique. Attention tout de même au fait qu’aucune donnée n’a été lue2.

Dates et heures

La gestion des dates, en toute généralité, est un sujet très complexe. Ceci n’étant pas l’objet de ce TP, nous utiliserons les fonctions les plus simple possibles. L’appel time(NULL); retourne le nombre de secondes écoules depuis le jeudi 01/01/1970 (UTC). Deux remarques :

  • L’heure retournée dépend de l’horloge “locale” (i.e, de la machine), elle n’est donc pas synchronisé entre plusieurs machines’.
  • Sur ma machine le type time_t est en fait un long long (64 bits), le nombre maximum de seconde qu’on peut représenter est donc \(2^{64}\) secondes, soit \(\sim 584302086301\) années. Ce nombre devrait être suffisant pour notre TP. Avec 32 bits ce ne serait que \(\sim 136\) ans … donc ce compteur déborderait en 2106 … ce qui est tout de même assez pour notre TP (et normalement jusqu’à ma retraite).

Pour plus d’information sur cette fonction : man 3 time

File de priorité

Notre traitant accumulera les tâches à traiter dans une file de priorité (implémenté par un tas). La priorité d’une tâche (i.e., l’ordre de tri ce tas) est donnée par l’antériorité du champ start d’une tâche (i.e., les plus vieilles sont les plus prioritaires).

La construction d’un tas nécessite deux paramètres : un comparateur (la fonction décrite avant), et une taille. Je vous propose de la fixer arbitrairement à 1024.

Les données mises dans ce tas devront avoir un bloc mémoire associé, il faudra allouer un bloc pour chaque tâche, par exemple avec un struct task *t = malloc(struct task). Une fois les tâches traitées, il faut restituer ce bloc avec un appel a free(t).

Travail demandé

Réaliser le programme input.c, qui générera des tâches en fonctions des boutons appuyés les buzzers, puis l’écrira sur la sortie standard. Pensez à désactiver le buffering sur la sortie standard (ou utiliser fflush(stdout)).

  • L’ID est un nombre unique strictement monotone (+ 1 semble largement suffisant)
  • La durée de la tâche (champ payload) est un nombre aléatoire sur 10s (rand()%10 + 1).
  • Le départ de la tâche est heure actuelle + wait_time[numéro du joueur] + wait_time[numéro du bouton]. (Si vous voulez déplacer un bout de la formule dans le charge payload, ne vous gênez pas)

Réaliser le programme processor.c qui consommera les tâches soumisses (ce programme est un peu plus complexe à mettre en œuvre).

  • Faire une fonction de comparaison3 entre deux tâches. Une tache est avant un autre si le champ start d’une tâche est antérieur a celui de l’autre tâche. En cas d’égalité, on comparera la payload puis enfin l’ID.

  • Une première boucle qui lit la totalité des messages (task) reçus sur l’entrée standard (donc jusqu’à une erreur de lecture) et les insère dans une file de priorité. Si l’appel de FAGAIN est vrai, cette erreur ne sera pas une vrai erreur (donc on ne quitte pas).

  • Une seconde boucle jouera toutes les tâches de la file de priorité dont l’heure est expirée. Pour simplifier, jouer une tâche consistera à faire une pause de payload secondes (sleep). remarque: si aucune tâche n’est expirée, nous attendrons tout de même une seconde.

Temps d’attente

Pour simplifier le calcul du temps d’attente vous pouvez utiliser un tableau du genre :

int wait_time[] = {1, 2, 4, 8, 16};

Bien entendu, rien ne vous empêche de faire deux tableaux … ou d’améliorer la formule pour la rendre plus crédible.

Compiler les bibliothèques

Depuis le répertoire office :

make -C ../buzzer libbuzzer.a make -C ../heap heap.a

Tester

Penser a tester vos composant indépendamment :

./input | tee replay.bin | hexdump ## Affiche la sortie de input en hexadécimal ## Le tee sert a "sauvegarder" ces trames cat replay.bin | ./processor ## Rejoue les trames sauvegardées

Pour utiliser les fake buzzer, il vous faudra d’abord créer un tube nommé : mkfifo XXXXX (remplacer XXXXX par un nom au choix), puis partager votre terminal en deux (ou ouvrir deux terminaux côte a côte4).

``` ## Dans le premier terminal: ./input XXXXX | ./processor

Dans l’autre terminal :

../buzzer/fake –delay 2 XXXXX ```

Les faux buzzers n’envoient pas beaucoup de donnée, n’hésitez pas a le modifier pour augmenter le nombre de trames et leur diversité.


  1. Ce terme n’est pas courant dans la littérature mais me parait compréhensible, le flot est non bloquant. 

  2. Vous pourrez utiliser le mot-clef break ou continue pour quitter ou aller à l’itération suivante de la boucle en cours — même si en général c’est une mauvaise idée, ici ça vous sera bien pratique. 

  3. Rappel: en math une comparaison est une différence, dont le signe nous renseigne sur l’ordre (négatif avant, positif après, nul identique). 

  4. En vrai il n’est pas nécessaire qu’ils soient côte à côte mais ça me parait pertinent pour mieux voir ce qui ce passe.