wiki:MultiCourseTP10

Cours "Architecture des Systèmes Multi-Processeurs"

TP10 : Partage du processeur / Commutation de tâches

(franck.wajsburt@…)

A. Objectifs

Ce TP porte sur les mécanismes permettant à un processeur de fonctionner en mode multi-tâches, c'est à dire d'exécuter plusieurs programmes utilisateurs simultanément. On utilise pour cela la technique de multiplexage temporel, où chaque processeur travaille successivement pour différents programmes durant des tranches de temps de longueur fixe. L'objectif du TP est d'identifier les problèmes liés à la création, à la sauvegarde, et à la restauration de tâches logicielles, et d'analyser en détail le mécanisme de commutation de tâches.

Comme on souhaite exécuter des programmes indépendants les unes des autres, le mécanisme permettant de remplacer une tâche par une autre sur un même processeur doit être un mécanisme pré-emptif, où la commutation de tâche est imposée par le système d'exploitation, qui réquisitionne le processeur, sans consulter le programme en cours d'exécution, et sans coopération de la part de celui-ci: Chaque programme se comporte donc comme si il avait le processeur pour lui tout seul et ignore qu'il ne dispose que d'une partie du temps CPU et qu'il partage la mémoire et les périphériques avec d'autres programmes.

Bien que cette technique de virtualisation du processeur, ait été initialement développée pour des ordinateurs mono-processeur, elle est également utile pour des architectures multi-processeurs. Elle permet en particulier d'exécuter des applications parallèles multi-tâches coopératives possédant un nombre de tâches plus grand que le nombre de processeurs de la machine.

B. Architecture matérielle

On utilise une plate-forme matérielle différente de la plate-forme générique utilisée dans les TPs précédents. Comme la précédente, cette architecture contient un nombre variable de processeurs MIPS32, ainsi que les périphériques que vous connaissez déjà, mais chaque processeur peut exécuter jusque 4 tâches en parallèle, ce qui complique la gestion des périphérques.

Dans les TPs précédents, on avait une seule tâche par processeur, et un terminal TTY était donc identifié par le numéro du processeur. Comme on souhaite que chaque tâche dispose de son propre terminal TTY, on a besoin au maximum de 16 terminaux TTY (4 taches * 4 processeurs), et le contrôleur TTY possède donc 16 canaux. Ceci nécessite 16 lignes d'interruption, pour une plate-forme comportant 4 processeurs.

Chaque tâche (et donc chaque terminal) est identifiée par un double index (p, k), où p est le numéro du processeur, et k est le numéro de la tâche sur le processeur. L'index global d'une tâche task_id, qui est aussi l'index de terminal est calculé de la façon suivante :

task_id = p * 4 + k 

Pour les autres périphériques, il existe un seul contrôleur de disque dans l'architecture, mais chaque processeur possède son propre TIMER et son propre canal DMA. Les composants TIMER et DMA possèdent donc chacun 4 canaux.

Les lignes d'interruption devront être cablées comme suit sur le contrôleur ICU :

  • 1 ligne d'interruption provenant du contrôleur IOC : irq_in[0]
  • 4 lignes d'interruption provenant du contrôleur DMA : irq_in[8] à irq_in[11]
  • 4 lignes d'interruption provenant du contrôleur TIMER : irq_in[12] à irq_in[15]
  • 16 lignes d'interruption provenant du contrôleur TTY : irq_in[16] à irq_in[31]

L'archive attachment:multi_tp10.tgz contient les fichiers dont vous aurez besoin. Créez un répertoire de travail tp10, et décompressez l'archive dans ce répertoire. Outre les fichiers tp10_top.cpp, et tp10.desc, vous trouverez comme d'habitude le logiciel embarqué dans le répertoire soft.

Question B1: Complétez le fichier tp10_top.cpp pour réaliser le cablage des interruptions sur le composant ICU comme décrit ci-dessus. Attention : les 32 ports p_irq_in[i] doivent être connectés, et les ports inutilisés doivent être connectés à un signal qui a toujours la valeur false .

C. Contexte d'exécution d'une tâche

Le contexte d'exécution complet d'une tâche est défini par les valeurs des registres internes du processeur, et les valeurs stockées dans sa pile d'exécution seg_stack, le code défini dans son segment seg_code, et les données globale stockées dans son segment seg_data.

Question C1: Rappelez le principe du pseudo-parallélisme par multiplexage temporel sur un seul processeur. Quel est l'événement qui provoque la commutation de tâches ? Utilisez le chronogramme ci-dessous pour expliquer les différentes étapes du mécanisme de commutation de tâches. Indication: Vous pouvez suivre les appels de fonctions à partir de l'exécution de l'ISR _isr_switch (dans le fichier giet_2011/sys/irq_handler.c).

La réponse aux trois questions suivantes est dans le fichier giet/sys/ctx_handler.c.

Question C2: Où est sauvegardé le contexte d'une tâche ? Pourquoi n'est-il pas nécessaire de sauvegarder les valeurs stockées dans la pile lorsqu'on effectue un changement de contexte ?

Question C3: Le GIET utilise une politique d'assignation statique des tâches aux processeurs. Cela signifie qu'il n'y a pas de migration des tâches, et qu'une tâche particulière sera toujours exécutée sur le même processeur. Comment le GIET mémorise-t-il le placement des tâches (identifiées par leur index global task_id) sur les processeurs ?

Question C4: Pour chaque processeur, c'est le système d'exploitation qui contrôle l'ordonnancement entre les tâches assignées à ce processeur. Comment Le GIET mémorise-t-il quelle tâche est en cours d'exécution sur chacun des processeurs à un instant donné ?

Question C5: Parmi les 32 registres généraux du processeur MIPS32, quels sont ceux qu'il n'est pas nécessaire de sauvegarder lors d'un changement de contexte? Parmi les registres système, justifiez pourquoi il est indispensable de sauvegarder SR, EPC, CR ?

Analysez le code de la fonction _task_switch que vous trouverez dans le fichier giet/sys/giet.s pour répondre aux questions suivantes.

Question C6: Quels sont les arguments de cette fonction ? Comment la fonction récupère-t-elle ses arguments ? Quelle est sa valeur de retour ?

Question C7: La fonction _task_switch est découpée en deux parties. Que cherche-t-on à faire dans chacune de ces 2 parties ? Quels registres cette fonction a-t-elle le droit de modifier dans la phase de sauvegarde du contexte de la tâche sortante ?

Question C8: Pourquoi la fonction _task_switch qui réalise la commutation de contexte (et qu'on trouve dans tous les systèmes d'exploitation multi-tâches) est elle toujours écrite en assembleur ?

Question C9: A quelle adresse se branche la fonction _task_switch quand elle retourne à la fonction appelante ? Pourquoi faut-il initialiser la case contenant le registre $31 du tableau de contexte d'une tâche (avant qu'elle commence son exécution) ? Quelle valeur doit contenir cette case 31 du tableau de contexte ?

Question C10: La fonction _task_switch est appelée par la fonction _ctx_switch. Cette fonction _ctx_switch est chargée de choisir la tâche entrante, ce qui suppose la définition d'une politique d'ordonnancement entre les tâches. Quel est la politique d'ordonnancement implémentée par la fonction _ctx_switch ?

D. Création et lancement des tâches

Le GIET n'est pas un vrai système d'exploitation. Il ne fournit pas un service de création dynamique des tâches (c'est à dire création d'un nouveau processus, alors que la machine est déjà en fonctionnement). Le GIET utilise un mécanisme de création statique où les tâches sont créées une fois pour toutes par le code de boot. Cette technique statique est souvent utilisée dans les applications embarquées où le nombre de tâches ne varie pas au cours du temps.

Comme dans les TPs précédents le code de boot peut accéder aux points d'entrée des tâches grâce à la table de sauts située au début du segment seg_data. Ces points d'entrée sont rangés dans cette table dans l'ordre où les fonctions possédant l'attribut ((constructor)) ont été compilées.

Les idées générales sont les suivantes :

  • Lors du démarrage, tous les processeurs exécutent le même code de boot, mais cette exécution dépend de la valeur du proc_id.
  • Par convention, la première tâche exécutée sur le processeur (p) est la tâche T(p, 0). Les autres tâches T(p, k), avec k non nul, seront lancées plus tard lors des changements de contexte déclenchés par le timer associé au processeur (p). Il faut donc traiter de façon différente la tâches T(p, 0) et les tâche T(p, k) lorsque k est non nul.

Pour assigner les tâches aux processeurs et lancer l'exécution, le code boot doit initialiser différents tableaux:

  • Le tableau _current_task_array[NB_PROCS] définissant l'index local de la tâche en cours d'exécution n'a pas besoin d'être initialisé, puisque la première tâche qui commence à s'exécuter sur le processeur (p) est la tâche T(p, 0).
  • Le tableau _task_number_array[NB_PROCS], qui contient le nombre de tâches assignées à chaque processeurs doit être initialisé. Ce nombre ne doit pas être plus grand que 4.
  • Le tableau _task_contexte_array[NB_PROCS*NB_MAXTASKS] doit être initialisé pour toutes les tâcheT(p, k), quand k est différent de 0, car il faut définir les valeurs initiales de certains registres pour les tâches qui ne démarrent pas immédiatement.

Pour cela le code de boot construit et utilise un tableau intermédiaire (non utilisé ensuite par le GIET) tasks_entry_point[NB_PROCS * 4], qui est indexé par le numéro global de la tâche task_id, et contient l'adresse du point d'entrée de la tache (en pratique, c'est une des adresses définies au début du segment seg_data. Ce tableau task_entry_point est différent de la table de sauts située au début du degment seg_data, car il est fréquent que plusieurs tâches exécutent le même code et se branchent donc à la même adresse.

Question D1 : Pour chaque processeur (p), quels sont les 3 registres qui doivent être initialisés avant de lancer l'exécution de la tâche T(p, 0) ? Quelles valeurs doivent-ils prendre ? Vérifier vos réponses en comparant avec ce qui est fait dans le fichier reset.s.

Question D2 : Pour chacune des tâches T(p, k), avec k non-nul, quelles sont les 4 cases du tableaux de contexte qui doivent obligatoirement être initialisés ? Quelles valeurs doivent-elles prendre ? Vérifier vos réponses en comparant avec ce qui est fait dans le fichier reset.s.

Pour ce qui concerne le routage des interruptions, on souhaite le comportement suivant: chaque processeur reçoit et traite au moins 5 interruptions : 1 interruption provenant du TIMER (pour déclencher les changements de contexte) et 4 interruptions provenant du contrôleur TTY (chaque tâche possède son propre terminal). Le processeur 0 reçoit en plus l'interruptions IOC et l'interruption correspondant au canal 0 du DMA (donc 7 interruptions au total).

Question D3: Compte-tenu du cablage des interruptions défini dans la section B, quelles valeurs faut-il écrire dans les registes MASK[0] à MASK[3] du composant ICU pour effectuer le routage défini ci-dessus ? complétez le fichier reset.s en conséquence (tableau icu_mask_array)

A chaque ligne d'interruption est associée une routine d'interruption ISR. Les 7 ISRs utilisées dans cette architecture sont les suivantes

  • _isr_dma : ISR exécutée lorsque l'interruption provient du contrôleur DMA
  • _isr_ioc : ISR exécutée lorsque l'interruption provient du contrôleur IOC
  • _isr_switch : ISR exécutée lorsque l'interruption provient du TIMER (changement de contexte)
  • _isr_tty_get_task0 : ISR exécutée lorsque l'interruption provient d'un TTY associé à une tâche d'index k = 0
  • _isr_tty_get_task1 : ISR exécutée lorsque l'interruption provient d'un TTY associé à une tâche d'index k = 1
  • _isr_tty_get_task2 : ISR exécutée lorsque l'interruption provient d'un TTY associé à une tâche d'index k = 2
  • _isr_tty_get_task3 : ISR exécutée lorsque l'interruption provient d'un TTY associé à une tâche d'index k = 3

Question D4: Expliquez pourquoi il est nécessaire de définir 4 ISR différentes pour le composant TTY lorsqu'on veut pouvoir exécuter 4 tâches par processeur ?

Question D5: Comment doit être initialisé le vecteur d'interruptions ? Complétez le fichier reset.s en conséquence.

On souhaite que chaque tâche T(n, k) dispose d'une pile d'exécution d'une capacité de 64 Koctets.

Question D6: Vérifiez que la longueur du segment seg_stack définie dans le fichier tp10_top.cpp peut supporter la situation où les 4 processeurs exécutent chacun 4 tâches en parallèle. A quelles valeurs faut-il initialiser le pointeur de pile de de chacune des tâches T(n, k) ? Comparez les valeurs que vous proposez à celles qui sont définies dans le fichier reset.s.

Question D7 : Pourquoi est-ce le système d'exploitation, et non les tâches elles-mêmes qui décident de la périodicité des changements de contexte (c'est à dire la valeur du TICK). Complétez le fichier reset.s, pour que la période soit égale à 10000 cycles, et pour activer le timer.

E. Fonctionnement multi-tâches sur mono-processeur

Le répertoire soft contient trois applications logicielles déjà utilisées dans les TP précédents.

  1. main_pgcd.c est le programme interactif de calcul du PGCD (TP6). Il comporte une seule tâche logicielle définie par la fonction pgcd().
  2. main_display.c est le programme d'affichage sur le terminal graphique FBF d'une séquence d'images lues sur le disque IOC (TP8). Il comporte une seule tâche logicielle définie par la fonction display().
  3. main_fifo.c est le programme de transfert de données entre tâches à travers un canal de communication FIFO (TP9). Ce programme comporte deux taches logicielles parallèles et coopératives, définies par les deux fonctions producer() et consumer().

On va commencer par exécuter ces quatre tâches en multiplexage temporel sur un architecture matérielle comportant un seul processeur.

Il faut que les adresses des quatre tâches pgcd, display, producer et consumer soient rangées dans cet ordre au début du segment seg_data.

Vérifiez dans le fichier Makefile qui vous est fourni que ces quatre fonctions seront bien compilées dans cet ordre.

Question E1 : Completez le fichier reset.s, pour placer les quatre tâches sur le processeur 0.

Lancez la compilation du logiciel embarqué en utilisant le Makefile qui vous est fourni, puis lancez l'exécution.

$ ./simul.x -NPROCS 1 -DISK images.raw -SNOOP 1

Question E2 : Comparez la durée d'exécution de l'application display (lorsqu'elle partage le processeur avec 3 autres tâches), avec la durée d'exécution que vous aviez obtenue dans le TP6 (lorsque elle était seule à utiliser le processeur). Pourquoi le rapport n'est-il pas exactement égal à 4 ?

Question E3 : Faites varier la valeur du TICK (période entre deux interruptions TIMER). Que se passe-t-il lorsque la période est très grande (1 million de cycles) ? Que se passe-t-ii lorsque la période est très petite (500 cycles) ? Comment expliquez-vous ces comportement ?

F. Fonctionnement multi-tâches sur multi-processeurs

On va maintenant utiliser la technique de multiplexage temporel sur chacun des 2 processeurs d'une architecture bi-processeurs.

Question F1: Modifiez le fichier reset.s pour placer les deux tâches pgcd et producer sur le processeur 0, et les deux tâches display et consumer sur le processeur 1.

Lancez la compilation du logiciel embarqué en utilisant le Makefile qui vous est fourni, puis lancez l'exécution.

$ ./simul.x -NPROCS 2 -DISK images.raw -SNOOP 1

Question F2: Quelle différence de comportement observez-vous entre le fonctionnement mono-processeur et le fonctionnement bi-processeur ?

L'ordonnancement des tâches (ou des processus) est une des principales fonctions d'un système d'exploitation (avec la protection de l'accès aux ressources partagées que sont les périphériques, et la gestion de la mémoire virtuelle). Le GIET n'étant pas un vrai système d'exploitation, l'ordonnancement réalisé par la fonction _ctx_switch est très simple: chacune des tâches allouées à un processeur s'exécute à tour de rôle pour une durée fixe.

Question F3: Quelles critiques peut-on faire concernant cette politique d'ordonnancement du GIET ?

Question F4: Utilisez les différentes applications logicielles des TPs 6 à 9 pour lancer 16 tâches (coopératives ou non) sur une architecture à 4 processeurs. Il faut modifier le fichier reset.s pour placer les 16 tâches sur les 4 processeurs. Compilez et exécutez...

G. Compte-Rendu

Les réponses aux questions ci-dessus doivent être rédigées sous éditeur de texte et ce compte-rendu doit être rendu au début de la séance de TP suivante. De même, le simulateur, fera l'objet d'un contrôle au début de la séance de TP de la semaine suivante.

Last modified 15 months ago Last modified on Jan 5, 2023, 5:43:39 PM

Attachments (3)

Download all attachments as: .zip