Liens utiles

Consignes

Ce TP donnera lieu à une évaluation. Vous pouvez travailler en binômes.

Estimation du temps

Envoyer votre TP

Votre TP devra être envoyé par email à votre enseignant (Pierre.Hyvernat@univ-savoie.fr, Florian.Hatat@univ-savoie.fr ou Thomas.Seiller@univ-savoie.fr). Le sujet de votre mail doit contenir la chaîne "info524".

Vous devez envoyer une unique archive tar contenant :

points importants :

  1. votre archive doit contenir un répertoire et pas seulement des fichiers en vrac. Mon répertoire de travail s'appelle "Pierre_Hyvernat-TP2" ; pour créer l'archive, la ligne de commande est :

    $ tar cvf Pierre_Hyvernat.tar Pierre_Hyvernat/
    
  2. tous vos fichiers doivent commencer par une entête contenant vos noms et prénoms, ainsi que votre filière.

Si ces consignes ne sont pas respectées, l'enseignant se réserve le droit de vous enlever 5 points (ou plus) sur la note finale.

Utiliser l'image fournie

L'archive fournie pour ce TP contient une image QEMU avec un MINIX déjà installé et configuré.

Pour l'utiliser, il suffit de télécharger l'image dans le répertoire /tmp et la décompresser :

$ cd /tmp/
$ mkdir TP2-OS
$ cd TP2-OS
$ wget http://lama.univ-savoie.fr/~hyvernat/Enseignement/1112/info524/minix.img.bz2
$ bunzip2 minix.img.bz2

Pour démarrer MINIX :

$ qemu -localtime -net user,hostfwd=tcp::2232-:22  -net nic,model=rtl8139 \
       -m 256 -drive if=ide,media=disk,cache=writeback,file=minix.img

Le mot de passe pour l'utilisateur root est root, et le mot de passe pour l'utilisateur etu est etu.

1. Appels systèmes sous MINIX 3

Comme MINIX est un micro-noyau, la plupart des appels systèmes sont gérés par un serveur (par exemple, "mfs" pour le système de fichiers de MINIX, ou "sched" pour l'ordonnanceur). Les sources de chaque serveurs sont dans le répertoire /usr/src/servers/.

1.1. Messages et appels systèmes

Sous MINIX, un appel système doit envoyer un message au serveur correspondant. Chaque message est une structure constituée de :

  1. un champ "m_source" contenant le numéro interne du processus qui doit recevoir le message,
  2. un champ "m_type" contenant le numéro de l'appel système que l'on effectue,
  3. des arguments pour l'appel système dans le dernier champ "m_u".

Les numéros d'appels système sont des constantes définies dans le fichier "/usr/include/minix/call.h".

Suivant les arguments de l'appel système, le champ "m_u" a un type différent. Par exemple, "m_u" peut être de type

Le type des messages ainsi que des synonymes pour accéder aux différents champs sont définis dans le fichier "/usr/include/minix/ipc.h".

Lorsque le message est prêt, on l'envoie avec la commande "send()" ou "sendrec()" (qui permet en plus de recevoir un message en réponse) de prototypes

int send (endpoint_t dest, message *m_ptr);
int sendrec (endpoint_t src_dest, message *m_ptr);

Ces fonctions sont définies en langage d'assemblage dans le fichier "/usr/src/lib/libc/arch/i386/rts/_ipc.S".

On peut également utiliser la commande "_syscall()" de prototype

int _syscall (endpoint_t _who, int _syscallnr, message *_msgptr);

définie dans le fichier "/usr/src/lib/libc/other/syscall.c". Modulo un traitement des erreurs, on a :

int _syscall(endpoint_t who, int syscallnr, message *msgptr)
{
  int status;
  msgptr->m_type = syscallnr;
  _sendrec(who, msgptr);
  return(msgptr->m_type);
}

1.2. Ajouter un appel système

Suivez les étapes ci-dessous pour ajouter l'appel système "changer_nom()" qui permettra à un processus de changer son nom tel qu'affiché par la commande "top".

Vérifiez que vous comprenez à quoi sert chacune des étapes car vous aurez besoin de refaire le même travail dans la suite du TP. N'hésitez pas à demander de l'aide à votre encadrant de TP.

ajouter un numéro d'appel système dans "/usr/include/minix/com.h" et "/usr/src/include/minix/com.h".
Le fichier "/usr/include/minix/com.h" contient les numéros des messages utilisé par MINIX et les serveurs. L'appel système que l'on va ajouter fait intervenir le serveur "pm" (Process Manager) et s'appelle PM_CHANGE_NAME.

Allez regarder comment le numéro est défini et affichez le (en décimal) grâce à un mini programme en C.

Ne modifiez pas le fichier "/usr/src/include/minix/com.h" car il vous faudrait alors recompiler tout le noyau, ce qui prend du temps...

ajouter la gestion du nouvel appel système dans le serveur correspondant
Le serveur qui va recevoir l'appel "changer_nom()" est le process manager dont les sources se trouvent dans "/usr/src/servers/pm/". Le message correspondant à cet appel système va contenir le nouveau nom du processus dans son champ "m3_ca1" (chaîne de caractères de taille inférieure à 16).

  1. Ajoutez une fonction "do_changename()" dans le fichier "/usr/src/servers/pm/misc.c". Cette fonction prend en argument un pointeur vers un message (qui contiendra le nouveau nom du processus) et un pointeur vers une structure "mproc" (définie dans "/usr/src/servers/pm/mproc.h") :

    /*===========================================================================*
     *              do_change_name                                               *
     *===========================================================================*/
    PUBLIC int do_changename(message *m_ptr, struct mproc *mp)
    {
          printf("Fonction \"do_changename\" pour le processus %d\n", mp->mp_pid);
          strncpy(mp->mp_name, m_ptr->m3_ca1, 16);
          /* Attention, dans "m3_ca1", le dernier caractère est le chiffre "un" comme
             dans "m3_ca2" ou "m3_ca3" */
          return OK;
    }
    

  1. Ajoutez le prototype de la fonction "do_changename()" dans le fichier "/usr/src/servers/pm/proto.h" :

    ...
    
    /* misc.c */
    ...
    _PROTOTYPE( int do_changename, (message *m_ptr, struct mproc *mp) );
    

  1. Modifier la fonction "main". Cette fonction contient une instruction "switch(call_nr)" qui permet de gérer les messages entrants. À l'intérieur de cette fonction, la variable "m_in" contient le message reçu et la variable "mp" est un pointeur vers le processus qui a envoyé le message.

    Ajoutez un cas pour gérer le message "PM_CHANGE_NAME" :

       ...
       switch(call_nr) {
           ...
           case PM_SETGROUPS_REPLY:
               ...
           break;
           case PM_CHANGE_NAME:
               printf("serveur PM : changement de nom...\n");
               result = do_changename(&m_in, mp);
               break;
           ...
    

  1. Recompilez le serveur process manager pour vérifier que vous n'avez pas fait d'erreur de C :

    # cd /usr/src/servers/pm/
    # make clean all install
    
    puis recompilez et installez le nouveau noyau :

    # cd /usr/src/tools
    # make install
    

  2. Si tout a fonctionné, vous pouvez maintenant rebooter et choisir le nouveau noyau (2)

    # halt
    ...
    c0d0p0s0> off
    
    puis relancer QEMU et tester le nouvel appel système avec le programme suivant :

    #include <lib.h>
    #include <string.h>
    
    int changer_nom(const char *s) {
      message m;
      int r;
      strncpy(m.m3_ca1, s, 16);
      r  =  _syscall(PM_PROC_NR,PM_CHANGE_NAME,&m);
      return(r);
    }
    
    
    int main (void) {
      changer_nom("Bob l'Eponge");
      while (1);
      return 0;
    }
    
    Si vous faites maintenant un "top" vous pourrez voir un processus avec le nom "Bob l'Eponge"...

  3. bien sûr, pour un "vrai" appel système, il faudrait également ajouter la définition de "changer_nom" dans les bibliothèques du système pour que l'utilisateur n'ait pas à utiliser la fonction bas-niveau "_syscall()"...

Le nom du processus affiché par la commande "ps" est l'ancien nom. Proposez une explication, si possible avec une justification.

Vous inclurez un fichier "reponses.txt" à votre archive qui contiendra :

  1. le numéro en décimal du message "PM_CHANGE_NAME",
  2. votre réponse à la remarque ci dessus.

2. Le serveur d'ordonnancement

Le but de ce TP est maintenant d'ajouter deux appels systèmes gérés par l'ordonnanceur :

  1. "superman()" qui permet à un processus de devenir prioritaire sur tous les autres,
  2. "kryptonite()" qui permet à un processus superman de redevenir normal.

Avant de commencer ceci, il faut d'abord comprendre quel type d'ordonnanceur MINIX utilise...

2.1. Ordonnancement sous MINIX

Les sources de l'ordonnanceur de MINIX se trouvent dans le répertoire "/usr/src/servers/sched/". L'ordonnanceur de MINIX est un simple tourniquet avec quantum de temps et priorités. Chaque file ("queue" en anglais) contient des processus de même priorité :

L'ordonnanceur choisit toujours le premier processus dans la file de priorité la plus forte (càd la file de numéro le plus petit possible).

La constante NR_SCHED_QUEUES ainsi que d'autres constantes similaires sont définies dans le fichier "/usr/include/minix/config.h".

  1. Cherchez la valeur de "NR_SCHED_QUEUES".
  2. Quelle est la priorité par défaut d'un processus noyau ("TASK_Q") ?
  3. Quelle est la priorité par défaut d'un processus utilisateur ("USER_Q") ?

Faites tourner (à la main) l'algorithme du tourniquet avec priorité et quantum de temps. Montrez, avec un exemple simple, qu'il est très facile de provoquer une famine.

Pour éviter les famines qui apparaissent avec l'algorithme naïf, chaque processus qui termine son quantum de temps (qui fait donc une utilisation intensive du processeur) va devenir un peu moins prioritaire (sa priorité va diminuer et son numéro de file augmenter de 1). C'est ce que fait la fonction "do_noquantum()" dans le fichier "/usr/src/servers/sched/schedule.c".

Par contre, lorsqu'un processus se retrouve bloqué (entrées / sorties) avant que son quantum de temps ne soit écoulé, sa priorité ne change pas : il est simplement remis en fin de file.

Pour éviter que tous les processus se retrouvent avec un priorité minimale (càd dans la file de numéro le plus grand) au bout d'un moment, les processus peuvent regagner un niveau de priorité de temps en temps, à condition que cela ne leur donne pas une priorité supérieure à leur priorité initiale. C'est la fonction "balance_queues()" du fichier "/usr/src/servers/sched/schedule.c".

Regarder ce qu'il se passe sur vos exemples de famine si vous utilisez cette amélioration.

Vérifiez dans les fonctions "do_noquantum()" et "balance_queues()" que c'est bien ce qu'il se passe.

2.2. Superman

Nous allons maintenant ajouter les appels systèmes "superman() et "kryptonite()" de prototypes :

int superman(void) ;
int kryptonite(void) ;

Ces appels systèmes auront l'effet suivant :

Pour accéder aux processus, le noyau n'utilise pas le PID (qui est défini par le process-manager), mais un numéro appelé endpoint qui permet d'obtenir plus facilement au processus dans la table des processus. Vos appels système du process-manager vers l'ordonnanceur devront donc utiliser ce endpoint plutôt que le PID du processus appelant.

Implémentez les deux appels systèmes "superman()" et "kryptonite()" en suivant les consignes ci-dessous.

Consignes

  1. Vous implémenterez deux messages pour l'ordonnanceur :
    • "SCHEDULING_SUPERMAN"
    • "SCHEDULING_KRYPTONITE"
    Comme pour "CHANGE_NAME", ces messages utiliseront un champ ("m1_i1" par exemple) pour stocker le numéro du processus appelant ; il passeront ce processus à l'état correspondant.

  2. Les fonctions "do_superman(message *m_ptr)" et "do_kryptonite(message *m_ptr)" correspondantes seront définies dans "/usr/src/servers/sched/schedule.c". Le message pointé par "m_ptr" contiendra le endpoint du processus que l'on veut modifier.

  3. Pour vous faciliter la vie, vous pouvez modifier la structure "schedproc" définie dans "/usr/src/servers/sched/schedproc.h".

  4. Vous pouvez vous inspirer de la commande "do_nice()" définie dans "/usr/src/servers/sched/schedule.c". En particulier :
    • pour obtenir un "struct schedproc *" à partir d'un "endpoint", on utilise :

        int proc_nb;
        struct schedproc *rmp;
        int endpoint = m_ptr->m1_i1;          /* on récupère le "endpoint" */
        sched_isokendpt(endpoint, &proc_nb);  /* on le convertit en indice dans la table des processus */
        rmp = &schedproc[proc_nb];            /* on récupère un pointeur vers le "schedproc" correspondant */
        ...
      
    • pour relancer l'ordonnanceur pour prendre en compte la nouvelle priorité de "rmp", on utilise :

        ...
        schedule_process(rmp);
        ...
      
    (La fonction "do_nice" fait tout cela, avec de la gestion d'erreurs en plus. Vos fonctions "do_superman" et "do_kryptonite" pourront être plus simple et ne pas gérer les cas problématiques...)

  5. Vous devrez également modifier la fonction "do_noquantum" pour qu'elle ne baisse pas la priorité des supermen.

  6. Un nouveau processus hérite de l'état de son père : si un superman fait un fork, son fils est également un superman. Ceci sera pris en compte par la fonction "do_start_scheduling()" du fichier "schedule.c".

Vous devrez probablement modifier les fichiers suivants :

Si vous voulez modifier un autre fichier, demandez confirmation auprès de votre encadrant de TP.

2.3. Passer par le process manager

On ne peut malheureusement pas envoyer de message directement à l'ordonnanceur : il faut passer par le process manager...

Ajouter un nouveau message "PM_SUPERMAN" au process manager, en suivant les consignes ci dessous.

Le message "PM_SUPERMAN" sera traité (comme "PM_CHANGENAME") par le process manager. Le message contiendra un unique champ "m1_i1" :

L'utilisateur pourra alors définir :

int kryptonite(void) {
        message m;
        int r;
        m.m1_i1 = -1;
        r  =  _syscall(PM_PROC_NR,PM_SUPERMAN,&m);
        return r;
}

int superman(void) {
        message m;
        int r;
        m.m1_i1 = 1;
        r  =  _syscall(PM_PROC_NR,PM_SUPERMAN,&m);
        return r;
}

et utiliser "superman()" pour pouvoir passer un programme C en mode superman.

Vous devrez probablement modifier les fichiers suivants :

Si vous voulez modifier un autre fichier, demandez confirmation auprès de votre encadrant de TP.

2.4. Tests

Écrivez des petits programmes de test pour regarder ce qu'il se passe dans les conditions suivantes :

  1. un unique superman qui fait des entrées / sorties en compétition avec des processus normaux,
  2. un unique superman sans entrées / sorties en compétition avec des processus normaux,
  3. plusieurs supermen faisant des entrées / sorties en compétition (entre eux et avec des processus normaux),
  4. plusieurs supermen sans entrées / sorties en compétition entre eux,
  5. ...

Commentez.