wiki:AS6-TME-B5

Context Navigation

Version 77 (modified by franck, 8 months ago) (diff)
--

INDEX

A. Questions
B. Travaux pratiques

DOCS → [Config] [MIPS U] [MIPS K] [markdown] [CR.md]
COURS → [1 (+code) (+outils)] [2] [3] [4] [5] [6] [7] [8] [9]
TME → [1] [2] [3] [4] [5] [6] [7] [8] [9]
CODE → [gcc + soc] [1] [2] [3] [4] [5] [6] [7] [8] [9]

5 - Gestion des Threads

La majorité des réponses aux questions sont dans le cours, c'est voulu. Les questions suivent à peu près l'ordre du cours, elles sont simples, mais vous avez quand même besoin de comprendre le cours pour y répondre :-) Quand une question vous demande si quelque chose est vrai ou faux, ne répondez pas juste "oui" ou "non », mais justifiez vos réponses avec une petite phrase. Le but de ces questions est d'évaluer vos connaissances, donc plus vous êtes précis, mieux c'est. Vous avez un corrigé que vous devez consulter pour vous autocorriger, mais pour qu'il soit utile, lisez-le après avoir cherché vous-même les réponses. Dans certains cas, ce ne sera pas simple, mais tentez quand même une réponse, même si vous savez que c'est faux, car ce sera plus simple de comprendre la réponse.

A. Questions

A.1. Questions générales

Dites-en une phrase ce qu'est un processus informatique (selon Wikipédia)
Est-ce qu'un processus utilisateur s'exécute toujours dans le mode utilisateur du MIPS ?
Nous avons vu qu'un processus utilisateur peut faire des appels système, c'est-à-dire demander des services au noyau du système d'exploitation. Est-ce qu'un processus peut faire des interruptions et des exceptions ?
Un processus dispose d'un espace d'adressage pour s'exécuter, qu'y met-il ?
Dans un fichier exécutable, avant qu'il ne soit chargé en mémoire, on trouve le code du programme et les données globales. Est-ce qu'il y a aussi les piles d'exécution des threads ? Justifiez votre réponse.
Un thread de processus informatique représente un fil d'exécution de ce processus. Il est défini par une pile d'exécution pour ses fonctions, un état des registres du processeur et des propriétés comme un état d'exécution (RUNNING, READY, DEAD, et d'autres que nous verront plus tard). Combien de threads a-t-on par processus au minimum et au maximum ?
Tous les threads d'un processus se partagent le même espace d'adressage, et donc le même code, les mêmes variables globales, les mêmes variables dynamiques (nous les verrons dans un prochain cours). Est-ce qu'ils se partagent aussi les piles ?
Lorsque l'on crée un nouveau thread (un nouveau fil d'exécution du processus), il faut indiquer sa fonction principale, c'est-à-dire la fonction par laquelle qu'il doit exécuter. Est-ce que le nouveau thread pourra appeler d'autres fonctions ?
Est-ce qu'on peut créer deux threads avec la même fonction principale ?
Combien d'arguments la fonction principale d'un thread peut-elle prendre et de quel type ?
Que se passe-t-il lorsqu'on sort de la fonction principale d'un thread ?
L'exécution en temps partagé est un mécanisme permettant d'exécuter plusieurs threads à tour de rôle sur le même processeur. Comment s'appelle le service du noyau chargé du changement de thread ?
La phase de changement de thread a une certaine durée, c'est un temps perdu du point de vue de l'application. Comment nomme-t-on cette phase pour indiquer que c'est un temps perdu ?
Pour l'exécution en temps partagé, le noyau applique une politique, laquelle définit l'ordre d'exécution. Si les threads sont toujours prêts à être exécutés et que le noyau les exécute à tour de rôle de manière équitable, comment se nomme cette politique ?
Dans cette politique équitable, quelle est la fréquence type de changement de thread ? Donnez une justification.
Comment nomme-t-on la durée entre deux interruptions d'horloge ? Ici, c'est le temps d'une instance d'exécution d'un thread.
Le mécanisme de changement de thread (dont vous avez donné le nom précédemment) se déroule en 3 étapes, quelle que soit la politique suivie. Quelles sont ces étapes ?
Comment se nomme la fonction qui provoque la perte du processeur par le thread en cours au profit d'un nouveau thread ?
Qu'est-ce qui provoque un changement de thread sans que le thread n'en fasse lui-même la demande ?
Dans le mécanisme de changement de thread, l'une des étapes est la sauvegarde du contexte, est-ce la même chose qu'un contexte de fonction ? Dites de quoi il est composé.
Où est sauvé le contexte d'un thread ? Que pouvez-vous dire de la fonction de sauvegarde ? (langage, prototype, valeur de retour, etc.)
Chaque thread dispose de sa propre pile d'exécution, doit-on aussi sauver la pile lors des changements de thread ?
Après qu'un thread a été élu et que son contexte a été chargé dans le processeur, donnez le nom de la fonction responsable du chargement et dites où elle retourne ? Attention, il y a deux cas. Vous avez une partie de la réponse dans le cours à partir du slide 23, et vous avez des commentaires dans le code de kernel/kthread.c. L'idée n'est pas de répondre de manière précise, mais de comprendre pourquoi il y a deux cas.

A.2. Questions sur l'implémentation

Quelles sont les fonctions de l'API utilisateur des threads et les états de threads ? Indiquer les changements d'état provoqué par l'appel des fonctions de cette API. Regardez les transparents pour répondre.
La structure thread_s rassemble les propriétés du thread, sa pile et le tableau de sauvegarde de son contexte. Cette structure est, dans l'état actuel du code entièrement dans dans le segment des données globales de l'application. Pouvez-vous justifier cette situation et en discuter ?
Le tableau de sauvegarde du contexte d'un thread est initialisé avec des valeurs qui seront chargées dans les registres du processeur au premier chargement du thread. Tous les registres n'ont pas besoin d'être initialisés avec une valeur. Seuls les registres $c0_sr ($12 du coprocesseur système) , $sp ($29 des GPR) et $ra ($31 des GPR) ont besoin d'avoir une valeur choisie. Pourquoi ?
$c0_sr est initialisé avec 0x413, dite pourquoi.

L'ordonnanceur est codé dans la fonction sched_switch(). Il est appelé par thread_yield() et par thread_exit() (et par d'autres fonctions que nous verrons plus tard).
La fonction sched_switch() appelle d'abord l'électeur de thread qui choisit le thread entrant (qui gagne le processeur), puis sched_switch() sauve le contexte du thread sortant (qui perd le processeur) et charge le contexte du thread entrant, enfin sched_switch() change l'état du thread entrant à RUNNING.
Est-ce que sched_switch() sait pourquoi un thread demande à perdre le processeur ?

int thread_yield (void) {
  thread_tab[thread_current_idx]->state = TH_STATE_READY;  // état futur du thread sortant 
  sched_switch ();                                         // changement de threads (ou pas)
  return 0;
}
void sched_switch (void) { //
  int th_curr = thread_current_idx;                        // n° du thread courant dans thread_tab
  int th_next = sched_elect ();                            // demande le numéro du prochain thread
  if (th_next != th_curr) {                                // Si c'est le même thread, ne rien faire !
    if (thread_save (thread_tab[th_curr]->context)) {      // sauve le ctx du thread sortant et rend 1
      thread_current_idx = th_next;                        // mise à jour de thread_current_idx
      thread_load (thread_tab[th_next]->context);          // chargement de contexte & sortie par jr $31
    }                                                      // donc de thread_save(), mais qui rend 0
  }
  thread_tab[thread_current_idx]->state= TH_STATE_RUNNING; // the thread choisi est dans l'état
}

Quand un thread est élu pour la première fois, à la sortie de thread_load(), on appelle la fonction thread_bootstrap(). Retrouvez dans les transparents du cours les étapes qui vont mener à l'exécution de la fonction principale du thread élu, et expliquez-les.
Un thread peut perdre le processeur pour 3 raisons (dans la version actuelle du code), quelles sont ces raisons ?
Quand un thread TS perd le processeur pour une raison X à la date T, il entre dans le noyau par kentry, puis il y a une séquence d'appel de fonction jusqu'à la fonction thread_load() du thread entrant TE. Lorsqu'on sort de ce thread_load(), on est dans le nouveau thread TE. Plus tard, le thread TS sera élu à son tour et gagnera à nouveau le processeur en sortant lui aussi d'un thread_load(). En conséquence, on sortira de la séquence des appels qu'il y avait eu à la date T.
Expliquez, en vous appuyant sur la description du comportement précédent, pourquoi on ne sauve pas les registres temporaires dans le contexte des threads.

Dans le cours, nous suivons l'exécution du code au démarrage (vers le slide 37), nous pouvons voir que la fonction kinit() fait 3 choses importantes : (1) initialiser à 0 la section BSS (contenant les variables globales non explicitement initialisées dans le programme), (2) demander à l'architecture de s'initialiser et (3) lancer la première (et ici seule) application. Où sont définis les symboles __bss_origin, __bss_end, __main_thread, _start et quel est leur type ?

void kinit (void)
{
    kprintf (banner);
// 1 
    extern int __bss_origin, __bss_end;                 
    for (int *a = &__bss_origin; a != &__bss_end; *a++ = 0);

// 2 
    arch_init(20000);                                         // init architecture ; arg=tick

// 3
    extern thread_t _main_thread;                             // thread struct pour main()
    extern int _start;                                        // _start() point d'entrée app.
    thread_create_kernel (&_main_thread, 0, 0, (int)&_start);
    thread_load (_main_thread.context);
 
    kpanic();
}

Dites ce que sont les arguments 2 et 3 de thread_create_kernel() dans le code de kinit() et pourquoi, ici, on les met à 0 ?
Dans la fonction kinit(), que se passe-t-il quand on sort de thread_load()et pourquoi avoir mis l'appel à kpanic() ?
Dans quelle pile s'exécute la fonction kinit() ? Dans quelle section est-elle ? Pourquoi n'est-elle que temporaire ?
Pour le chargement de thread main() avec thread_load (_main_thread.context), on initialise les registres $16 à $23, $30, $c0_EPC, est-utile ? Si oui pourquoi ? Sinon, pourquoi faire ces initialisations ?
Dans le deuxième TME2, vous avez dû modifier le code syscall_handler (gestionnaire de syscalls) pour le rendre interruptible. En effet, lorsque l'application demande un service au noyau, mais que le noyau ne peut pas le rendre immédiatement (comme la lecture d'une touche du clavier), si vous restez bloqué dans l'appel système en attendant la donnée et que les interruptions sont masquées, alors le noyau ne peut pas gérer les IRQ (pour le TME 2, il ne pouvait pas gérer l'IRQ du timer pour gérer le dépassement du temps de jeu). Pour rendre l'appel système interruptible, vous aviez dû mettre 0x401 dans le registre c0_sr dans le gestionnaire de syscall, avant d'appeler la fonction de service. Nous allons changer cette politique et considérer que les appels système ne sont plus interruptibles.
Quelle(s) conséquence(s) voyez-vous pour les appels système ?
Que doit-faire le noyau si un thread A lui demande une ressource que le noyau n'a pas ?
Le thread A ne doit pas attendre activement la ressource par scrutation parce que c'est du gâchis de temps CPU, alors le noyau a deux possibilités, les voyez-vous ?
Mettez-vous à la place du noyau si vous devez gérer des ressources, par exemple des places dans un restaurant, que vous avez des clients qui se présentent et que toutes les places sont occupées. Que faites-vous ?

B. Travaux pratiques

Pour la suite de la séance, récupérez l'archive du tp5 et placez là à côté des tp1 et tp2. Le code est fonctionnel, vous pouvez le tester. Je ne vous fais pas modifier, ou pire écrire, la gestion des threads, mais je vous invite à lire le code, c'est très commenté. Les principaux fichiers modifiés sont kernel/hcpua.S pour les fonctions thread_load(), thread_save() et thread_launch() (app_launch() a disparu, elle n'est plus utile). Des fichiers sont nouveaux : kernel/kthread.h qui contient le code de thread_create_kernel(), thread_yield(), thread_exit(), sched_switch() et quelques autres. common/thread.h' qui contient les prototypes de fonctions communes au noyau et à l'utilisateur et 'ulib/thread.c' qui contient aussi les fonctions thread_create(), thread_yield(), thread_exit() mais avec des appels système. Je vous invite vraiment à lire le code, c'est un bon exercice de lire le code des autres, croyez-moi. Pour lire le code, vous devez suivre les appels lors de l'entrée dans l'application ou les interruptions d'horloge, ce n'est pas une lecture linéaire du fichier (même si ce n'est pas inutile pour voir une vue d'ensemble).

Vous pouvez voir la différence entre les fichiers du TME B2 et du TME B3

01_gameover/               01_threads
|-- common                 |-- common
|   `-- syscalls.h         |   |-- syscalls.h
|-- kernel                 |   `-- thread.h
|   |-- harch.c            |-- kernel
|   |-- harch.h            |   |-- harch.c
|   |-- hcpua.S            |   |-- harch.h
|   |-- hcpuc.c            |   |-- hcpua.S
|   |-- hcpu.h             |   |-- hcpuc.c
|   |-- kernel.ld          |   |-- hcpu.h
|   |-- kinit.c            |   |-- kernel.ld
|   |-- klibc.c            |   |-- kinit.c
|   |-- klibc.h            |   |-- klibc.c
|   |-- ksyscalls.c        |   |-- klibc.h
|   `-- Makefile           |   |-- ksyscalls.c
|-- Makefile               |   |-- kthread.c
|-- tags                   |   `-- Makefile
|-- uapp                   |-- Makefile
|   |-- main.c             |-- uapp
|   `-- Makefile           |   |-- main.c
`-- ulib                   |   `-- Makefile
    |-- crt0.c             `-- ulib
    |-- libc.c                 |-- crt0.c
    |-- libc.h                 |-- libc.c
    |-- Makefile               |-- libc.h
    `-- user.ld                |-- Makefile
                               |-- thread.c
                               `-- user.ld

Questions

En utilisant le mode debug et le fichier label0.s, donner une estimation de l'overhead de changement de thread

Etat du code par une lecture directe du registre READ du TTY par `tty_read()`

Pour la partie pratique, vous allez changer la manière de lire les caractères du TTY pour la rendre plus efficace. Tous les changements seront faits dans le fichier kernel/harch.c. Commençons par comprendre le code proposé qui est fonctionnel, mais qui a un problème que nous allons résoudre.

uapp/main.c

Le code ci-dessous contient l'application donnée pour ce TP. Nous avons 3 threads : main, TO et T1.
main et T1 se contente d'afficher des messages sur le TTY0 et d'attendre (l'attente active (DELAY) est là pour ralentir l'affichage des messages).
T0 lit le clavier de TTY1

/*--------------------------------------------------------------------------------*\
   _     ___    __
  | |__ /'v'\  / /      \date        2022-02-22
  | / /(     )/ _ \     \copyright   2021-2022 Sorbonne University
  |_\_\ x___x \___/                  https://opensource.org/licenses/MIT

\*--------------------------------------------------------------------------------*/

#include <libc.h>
#include <thread.h>

#define DELAY(n) for(int i=n;i--;) __asm__("nop");

thread_t t0, t1;

void * t0_fun (void * arg)
{
    char buf[64];
    for (int i = 0;; i++) {
        fprintf (1, "entrez un truc : ");
        fgets (buf, sizeof(buf), 1);
        fprintf (1, "%s\n", buf);
    }
    return NULL;
}

void * t1_fun (void * arg)
{
    for (int i = 0;; i++) {
        fprintf (0, "[%d] t1 is alive (%d) : %s\n", clock(), i, (char *)arg);
        DELAY(1000000);
    }
    return NULL;
}

int main (void)
{
    thread_create (&t1, t1_fun, "bonjour");
    thread_create (&t2, t2_fun, NULL);
    for (int i = 0;; i++) {
        fprintf (0, "[%d] app is alive (%d)\n", clock(), i);
        DELAY(1000000);
    }
    return 0;
}

ulib/libc.c

La fonction fgets() est dans la libc, c'est une fonction bloquante du point de vue de l'utilisateur. Il l'appelle pour lire count caractères sur le TTY n°tty et les enregistre dans buf.
fgets() demande 1 caractère à la fois et elle le revoit sur l'écran (c'est un loopback) pour que l'utilisateur sache que son caractère a été pris en compte.
Il y a quelques subtilités dues au fait que lorsque vous taper sur enter, le clavier envoie deux caractères '\r' (13 = carriage return) et '\n' (10 = line feed), on jette \r. En outre, on gère le back space et le delete (à qui on donne le même comportement pour simplifier). Je vous laisse essayer de comprendre pour le plaisir.
Quand fgets() appelle read(), cela fait l'appel système SYSCALL_READ.

int read(int fd, void *buf, int count)
{   
    return syscall_fct( fd, (int)buf, count, 0, SYSCALL_READ);
}   
    
int write(int fd, void *buf, int count)
{   
    return syscall_fct( fd, (int)buf, count, 0, SYSCALL_WRITE);
}

int fgets (char *buf, int count, int tty)
{
    // to make the backspace, we use ANSI codes : https://www.wikiwand.com/en/ANSI_escape_code
    char *DEL = "\033[D \033[D";                // move left, then write ' ' and move left
    int res = 0; 
    count--;                                    // we need to add a NUL (0) char at the end
    char c=0;
    
    while ((count != 0) && (c != '\n')) {       // as long as we can or need to get a char

        read (tty, &c, 1);                      // read only 1 char
        if (c == '\r')                          // if c is the carriage return (13)
            read (tty, &c, 1);                  // get the next that is line feed (10)
    
        if ((c == 8)||(c == 127)) {             // 8 = backspace, 127 = delete
            if (res) {                          // go back in the buffer if possible
                write (tty, DEL, 7);            // erase current char
                count++;                        // count is the remaining place
                buf--;                          // but is the next address in buffer
                res--;
            }
            continue;                           // ask for another key
        } else
            write (tty, &c, 1);                 // loop back to the tty

        *buf = c;                               // write the char into the buffer
        buf++;                                  // increments the writing pointer
        count--;                                // decrements the remaining space
        res++;                                  // increments the read char
    }
    *buf = 0;                                   // add a last 0 to end the string

    return res;                                 // returns the number of char read
}

kernel/ksyscall.c

Je ne met pas toutes les étapes de l'appel du gestionnaire de syscall, vous avez ici le vecteur de syscall qui montre bien que l'on appelle la fonction du noyau tty_read().

void *syscall_vector[] = {
    [0 ... SYSCALL_NR - 1 ] = unknown_syscall,   /* default function */
    [SYSCALL_EXIT         ] = exit,
    [SYSCALL_READ         ] = tty_read,
    [SYSCALL_WRITE        ] = tty_write,
    [SYSCALL_CLOCK        ] = clock,
    [SYSCALL_THREAD_CREATE] = thread_create_kernel,
    [SYSCALL_THREAD_YIELD ] = thread_yield,
    [SYSCALL_THREAD_EXIT  ] = thread_exit,
    [SYSCALL_SCHED_DUMP   ] = sched_dump,
};

kernel/harch.c

Le thread tente de lire le clavier en lisant status, en cas d'échec il cède le processeur avec thread_yield(), en sachant qu'on lui rendra plus tard.
En cas de succès, il enregistre le caractère lu dans le buffer et décrémente le nombre de caractères attendus, si c'est le dernier, il sort.
Notez qu'il n'y a pas de loopback (c'est-à-dire de renvoi du caractère vers l'écran. C'est une opération complexe, on ne peut pas tout renvoyer (par exemple les flèches), c'est à la fonction système de faire ce travail.

int tty_read (int tty, char *buf, unsigned count)
{
    int res = 0;                                        // nb of read char
    tty = tty % NTTYS;                                  // to be sure that tty is an existing tty
    int c;                                              // char read

    while (count--) {
        while (!__tty_regs_map[ tty ].status) {         // wait for a char from the keyboard
            thread_yield();                             // nothing then we yield the processor
        }
        c = __tty_regs_map[ tty ].read;                 // read the char
        *buf++ = c;
        res++;
    }
    return res;                                         // return the number of char read
}

Le problème et une solution possible

Le code proposé à un problème. Pour le comprendre, nous allons partir d'un exemple illustré par le schéma ci-dessous :

T0 appelle tty_read() qui cède le processeur à T1 en l'absence de frappes.
Le thread T0 demande des lectures à chaque fois qu'il a le processeur, T1 prend le temps qui lui est donné jusqu'à l'IRQ du TIMER.
Si l'utilisateur frappe beaucoup de touches pendant que T0 n'a pas le processeur. Les caractères lus doivent être stockés quelque part dans le contrôleur de TTY pour ne pas les perdre. Mais si cette mémoire est trop petite, on risque de perdre des caractères.

L'idée va être d'utiliser l'IRQ du TTY pour réagir à chaque frappe du clavier pendant l'exécution de T1 pour lire le clavier et stocker les caractères dans une file d'attente. Sur le schéma ci-dessous est représentée l'exécution de l'isr du TTY qui vole des cycles à T1 pour lire le caractère reçu par le contrôleur de TTY.

Mise en place d'une FIFO entre l'isr du TTY et la fonction `tty_read()`

Le caractère lu est mis dans une structure FIFO (First In First Out). Le schéma ci-dessous illustre le fonctionnement de la FIFO. Une fifo simple a un écrivain et un lecteur. L'écrivain écrit des données avec une commande push() tant que la FIFO n'est pas pleine. Si, il y a deux comportements possibles : l'écrivain attend de la place ou alors l'écrivain jette la donnée, ça dépend de ce qu'on veut. Ici, on jettera, parce qu'on n'a pas le moyen de ralentir le flux de données (les frappes du clavier). Le lecteur lit les données avec pull() tant que la FIFO n'est pas vide.

Pour implémenter la FIFO, nous allons utiliser un tableau circulaire et des pointeurs. Il y a une structure et 2 fonctions d'accès.

/**
 * Simple fifo (1 writer - 1 reader)
 *   - data      buffer of data
 *   - pt_write  write pointer for L fifos (0 at the beginning)
 *   - pt_read   read pointer for L fifos (0 at the beginning)
 *
 * data[] is used as a circular array. At the beginning (pt_read == pt_write) means an empty fifo
 * then when we push a data, we write it at pt_write, the we increment pt_write % fifo_size.
 * The fifo is full when it remains only one free cell, then when (pt_write + 1)%size == pt_read
 */
struct tty_fifo_s {
        char data [20];
        int  pt_read;        // points to the cell to read   
        int  pt_write;       // points to the cell to write
};
/**
 * \brief   read from the FIFO
 * \param   fifo    structure of fifo to store data
 * \param   c       pointer on char to put the read char 
 * \return  1 on success, 0 on failure
 */
static int tty_fifo_pull (struct tty_fifo_s *fifo, int *c)
{
    if (fifo->pt_read != fifo->pt_write) {
        *c = fifo->data [fifo->pt_read];
        fifo->pt_read = (fifo->pt_read + 1)% sizeof(fifo->data);
        return 1;
    }
    return 0;
}
/**
 * \brief   write to the FIFO
 * \param   fifo    structure of fifo to store data
 * \param   c       char to write
 * \return  1 on success, 0 on failure
 */
static int tty_fifo_push (struct tty_fifo_s *fifo, int c)
{
  // écrire le code de push en vous inspirant de pull
}

Les schémas ci-dessous le comportement de la FIFO.

A l'initialisation comme la structure est dans les variables globales, les pointeurs pt_read et pt_write sont à 0.
La fifo est vide puisque pt_read == pt_write.
On écrit A et on incrémente pt_write, pt_read ne bouge pas puisque l'on ne lit pas.
On écrit B et C.
On lit A et on incrémente pt_read, on peut lire parce que pt_read != pt_write et donc la FIFO n'est pas vide
On écrit D et E. Lors de l'incrément de pt_write on revient à 0 à cause du modulo size
On écrit F et ce sera fini parce que la fifo est pleine (pt_write + 1)%size == pt_read, si on veut écrire à nouveau, il faut lire.

Utilisation de la FIFO

Pour utiliser la FIFO, vous allez de devoir :

créer une fifo par TTY, donc un tableau de struct tty_fifo_s de taille NTTYS.
Vous allez devoir changer le code de tty_read() qui doit désormais lire la fifo.
Créer une fonction tty_isr(int tty) qui lit le registre READ du tty en argument et écrit le caractère lu dans la FIFO du tty
Faire le binding des lignes d'interruption des TTY. C'est-à-dire modifier arch_init() pour
- démasquer les lignes IRQ 10, 11, 12 et 13 dans le masque de l'ICU, ce sont les entrées de l'ICU utilisées par les TTY0 à TTY3.
- initialiser les cases 10, 11, 12 et 13 des deux tableaux du vecteur d'interruption : irq_vector_isr[] et irq_vector_dev[]

Download in other formats:

Plain Text