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.
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é.
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
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.
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.
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 :
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
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)
.
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)
).
+ 1
semble largement suffisant)payload
) est un nombre aléatoire sur 10s (rand()%10 + 1
).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.
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.
Depuis le répertoire office :
make -C ../buzzer libbuzzer.a
make -C ../heap heap.a
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
../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é.
Ce terme n’est pas courant dans la littérature mais me parait compréhensible, le flot est non bloquant. ↩
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. ↩
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). ↩
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. ↩