CSC 4103 – Programmation système

Contrôle Final 2 – Année 2019/2020

Le barème est donné à titre indicatif

Durée du contrôle : 2h
Tous les documents sont autorisés
Dans vos programmes, on ne vous demande pas de gérer les cas d'erreur

Le but de cet exercice est de créer un petit répartiteur de charge. Notre système est composé d'un processus maître et de processus esclaves. Le maître, lorsqu'il reçoit un travail à faire, choisit un esclave et délègue l'exécution de ce travail à l'esclave choisi.

En détail, lorsqu'un utilisateur soumet un travail, il indique le temps que va durer ce travail en secondes. Le maître choisit alors un esclave oisif, note l'instant où cet esclave aura terminé son travail (en additionnant la durée du travail à l'heure courante), puis lui délègue le travail.

Création des esclaves (7 points)

Le nombre d'esclaves (1,5 point)

Notre programme prend en argument le nombre N d'esclaves à créer. Pour commencer, écrivez une méthode main qui affiche un message d'erreur avant de quitter si le processus ne reçoit pas en argument le nombre d'esclaves. Votre programme doit ensuite stocker ce nombre dans une variable globale n de type entier. On vous rappelle que la fonction int atoi(const char* str) permet de convertir une chaîne de caractères en entier.

int n;

int main(int argc, char** argv) {
  if(argc < 2) {
    fprintf(stderr, "Usage: %s N\n", argv[0]);
    exit(1);
  }
  n = atoi(argv[1]);
}

État des esclaves (1 points)

Pour représenter l'état d'un esclave, on a besoin d'une structure de données contenant :

le PID de l'esclave,
une variable nommée end de type time_t et représentant l'heure à laquelle le dernier travail donné à l'esclave sera terminé (time_t est simplement un alias pour le type entier unsigned long long).

Après avoir donné la définition de cette structure que nous nommerons slave_state, donnez le code permettant de définir une variable globale nommée slaves stockant un pointeur vers un tableau de slave_state.

struct slave_state {
  pid_t pid;
  time_t end;
}

struct slave_state* slaves;

Allocation de l'état (1 point)

Donnez le code à ajouter au main pour stocker dans la variables slaves un pointeur vers un tableau de n structures slave_state alloué dynamiquement à l'aide de malloc.

slaves = malloc(n * sizeof(*slaves));
for(int i=0; i<n; i++)
  slaves->end = 0;

Démarrage des esclaves (2 points)

Complétez votre fonction main de façon à créer n processus fils. Chaque processus fils doit être numéroté de 0 à n-1 et il doit appeler la fonction void wait_job(int i) où i est ce numéro. Le maître, de son côté, doit enregistrer le PID de l'esclave dans le tableau slaves à l'indice i. À cette question, on considère que la fonction wait_job vous est fournie. À terme, cette fonction contiendra contiendra le code exécuté par les fils.

for(int i=0; i<n; i++) {
  int pid = fork();

  if(pid == 0) {
    /* fils */
    wait_job(i);
    exit(0); 
  } else {
    /* père */
    slaves[i].pid = pid;
  }
}

Attente de la terminaison des esclaves (1,5 points)

Complétez votre fonction main de façon à ce que le maître appelle une fonction void master() qu'on suppose aussi fournie. Cette fonction contiendra à terme le code exécuté par le maître. Enfin, après avoir appelé la fonction master(), le maître doit attendre la terminaison des processus enfants avant de quitter.

On vous rappelle que la fonction pid_t wait(int* wstatus) permet d'attendre la terminaison d'un fils et de stocker son code de retour dans wstatus.

master();
for(int i=0; i<n; i++) {
  int wstatus;
  wait(&wstatus);
}

Saisie des commandes (4,5 points)

Interaction avec l'utilisateur (2,5 points)

La fonction master doit exécuter une boucle infinie. À chaque itération de la boucle, la fonction master doit commencer par lire une ligne saisie par l'utilisateur que vous stockerez dans une variable locale cmd. Si cette ligne est exactement égale à exit, la fonction master doit appeler la fonction quit() avant de retourner dans le main. Si la ligne saisie n'est pas égale à exit, la fonction doit alors lire une seconde ligne, la convertir en entier et stocker ce nombre dans une variable locale nommée duration. Cette variable duration donne le temps, en secondes, que va mettre la commande cmd à s'exécuter. Enfin, la fonction master doit appeler la fonction void dispatch(char* cmd, int duration). On suppose aussi cette fonction est fournie. À terme, cette fonction va s'occuper de sélectionner un esclave et de transmettre la commande à exécuter à cet esclave.

On vous rappelle que :

La fonction char* fgets(char* s, int size, FILE* stream); permet de lire une ligne à partir du flux stream (stdin dans notre cas). La fonction stocke le résultat dans le tableau de caractères s et s'assure que, au plus, seuls les size premiers caractères de la ligne seront stockés dans s.
La fonction int strcmp(const char* s1, const char* s2) renvoie 0 si les chaînes pointées par s1 et s2 sont égales.

void master() {
  while(1) {
    char cmd[256];
    fgets(cmd, 256, stdin);
    if(strcmp(cmd, "exit") == 0) {
      quit();
      return;
    }

    char buf[256];
    fgets(buf, 256, stdin);
    int duration = atoi(buf);

    dispatch(cmd, duration);
  }
}

Terminaison des esclaves (2 points)

La fonction quit doit s'occuper de terminer les esclaves. Pour cela, elle doit envoyer un signal SIGTERM à chacun des esclaves. On vous rappelle que la fonction void kill(pid_t pid, int sig) permet d'envoyer le signal sig au processus pid.

void quit() {
  for(int i=0; i
      

Délégation du travail à un esclave (5 points)

De façon à déléguer le travail à un esclave, nous procédons en trois étapes :

la fonction int earliest() va trouver l'indice de l'esclave qui terminera son travail le plus tôt,
la fonction int select(int duration) va sélectionner un esclave oisif pour exécuter une commande durant duration secondes et mettre à jour sa variable end de façon appropriée,
la fonction void dispatch(const char* cmd, int duration) utilise select pour sélectionner un esclave puis s'occupe de déléguer le travail à l'esclave sélectionné.

Premier esclave prêt (1 points)

Écrivez la fonction int earliest() renvoyant l'indice de l'esclave qui terminera son travail le plus tôt (champ end de la structure slave_state).

int earliest() {
  int res = 0;
  for(int i=1; i<n; i++)
    if(slaves[i].end 
      

Sélection d'un esclave (2 point)

Écrivez la fonction int select(int duration) renvoyant l'indice d'un esclave oisif. Pour cela, votre fonction doit boucler tant qu'il n'existe pas d'esclave oisif, c'est-à-dire tant que le champ end de l'esclave renvoyé par earliest est plus petit que l'heure courante renvoyée par la fonction time. Une fois l'esclave identifié, votre fonction doit mettre à jour le champ end de l'esclave sélectionné de façon appropriée en considérant que duration est le temps en secondes que mettra une commande à s'exécuter.

int select(int duration) {
  int res;
  time_t now;

  do {
    now = time(NULL);
    res = earliest();
  } while(now 
      

Délégation à l'esclave (2 points)

Écrivez la fonction void dispatch(const char* cmd, int duration). Cette fonction doit utiliser select pour sélectionner un esclave puis écrire dans un fichier nommé slave-N la commande cmd, où N est l'indice de l'esclave.

Pour construire la chaînes de caractères "slave-N", vous pouvez utiliser la fonction sprintf(const char* buf, const char* fmt, ...). Cette fonction se comporte comme printf, mais, au lieu d'écrire sur la sortie standard, elle écrit directement dans le tampon buf en mémoire.

void dispatch(const char* cmd, int duration) {
  int i = select(duration);
  char buf[256];
  snprintf(buf, 256, "slave-%d", i);
  FILE* f = fopen(buf, "w");
  fprintf(f, "%s", cmd);
  fclose(f);
}

Traitement chez l'esclave (3,5 points)

Traitement chez l'esclave (2,5 points)

Un esclave (fonction wait_job(int i)) doit exécuter une boucle infinie. À chaque tour de boucle, l'esclave doit lire le contenu de slave-i où i est le paramètre de wait_job. Après avoir lu le contenu du fichier, l'esclave doit supprimer le fichier à l'aide de la fonction unlink(char* file_name). Enfin, l'esclave doit exécuter la commande lue dans un processus fils.

Plutôt que de recopier le code permettant de construire la chaîne de caractères slave-i de votre question précédente, vous pouvez supposer que vous diposez d'une fonction char* make_slave_name(int i) renvoyant la chaîne de caractère "slave-i" à partir de l'indice i.

void wait_job(int i) {
  char buf[256];
  snprintf(buf, 256, "slave-%d", i);
  while(1) {
    FILE* f = fopen(buf, "r");
    char cmd[256];
    fgets(cmd, 256, f);
    system(cmd);
    fclose(f);
    unlink(buf);
  }
}

Problème de synchronisation (1 points)

Comme le maître ne se synchronise pas avec les esclaves, on peut imaginer un scénario dans lequel des écritures dans slave-i seraient perdues. Donnez, de façon textuelle, un ordonnancement aboutissant à ce scénario. Répondre à cette question ne doit pas nécessiter plus de 5 ou 6 lignes de texte.

Avec le scénario suivant, la commande cmd2 est perdue :

Maître ouvre, écrit cmd1, ferme
Esclave ouvre, lit cmd1, ferme
Maître ouvre, écrit cmd2, ferme
Esclave supprime le fichier