# Création d'un noyau

multitâche sur 68000

Par Supernova

Nous allons voir a travers cet article comment realiser un noyau multitache. Ce noyau sera applicable a toute machine a base de 68000 (comme l'Amiga, l'Apple..). Il pourra aussi etre embarque sur des microcontroleurs. Mais avant, rappelons quelques notions concernant les environnements multitaches.

LA THEORIE

  Les differents traitements

1. Traitement unique

   Chaque tache debute lorsque celle anterieure est terminee. C'est un systeme monotache/mono processeur. Le traitement est donc sequentiel.

     Avantage: simple a mettre en oeuvre
     Inconvenients: delais d'execution importants
     mauvaise utilisation des ressources

2. Traitement quasi parallele

   C'est un systeme multitache ou multithread mono processeur. Ainsi les taches ou threads sont executes alternativement. La simultaneite est donc virtuelle.

     Avantages:
       utilise les ressources au maximum
       ameliore les temps de reponse
     Inconvenients:
       plus complique a mettre en oeuvre
       necessite une analyse coherente

3. Traitement parallele

   C'est un systeme multitache ou multithread multi processeur. Il fonctionne en reelle simultaneite, c-a-d que les differentes taches s'executent en meme temps.

     Avantage: ameliore la production et les temps
     Inconvenient: cout et mise en oeuvre difficile

  Definitions

- Une tache est une entite composee d'une ou de plusieurs sequences d'instructions.
- Un thread est la plus petite entite d'execution d'un systeme multitache/multithread.
- Un processus peut etre compose de plusieurs taches et/ou plusieurs thread.
- Une tache peut etre composee de plusieurs thread, dans ce cas, les threads se partagent les segments de donnees, pile etc...

  Les taches

Dans un systeme multitache, la gestion dynamique des taches est fondamentale. Cet ordonnancement est bien souvent decoupe en deux parties:

- le scheduler (ordonnanceur)
- le dispatcheur (repartiteur)

Le premier a deux roles:

1. gerer la commutation d'etat entre les taches
2. choisir la tache a executer

Le second realise l'election de la tache et le changement de contexte associe.

  Descripteur de processus

(Voir figure 3 ci-dessus)

Toute les operations de l'ordonnanceur ne sont pas directement realisee sur le processus. En fait, il manipule une image de la tache: c'est son descripteur.

L'etat d'une tache determine si elle est prete, en cours d'execution, ou en attente de quelque chose comme la liberation d'une ressource commune (imprimante...)

La supervision indique son numero d'identification qui lui permet d'etre connue de l'executif et des autres processus, par exemple. Elle indique aussi sa priorite, comme le temps processeur qui lui est alloue ou sa position dans la file d'attente.

Le contexte est en general une serie de pointeur sur le code a executer, une zone de sauvegarde des registres lors de la commutation entre les taches...

Enfin, la derniere information est un pointeur sur le descripteur suivant.

  Ordonnancement des taches

L'ordonnancement est caracterise par:

- son efficacite
- son temps de reponse: le plus faible possible lors d'une reaction a un evenement externe
- son impartialite: le partage du processeur doit etre equitable sur les taches a priorite egale
- son debit: le plus de taches possibles dans un temps donne.

Les differentes methodes d'ordonnancement:

1. circulaire: on l'appelle aussi "round robin" ou "tourniquet".
   Chaque tache a la meme priorite. Les taches sont executees dans l'ordre ou elles apparaissent dans une file d'attente.
2. par priorite: chaque tache a un niveau de priorite different.
   La tache la plus prioritaire est lancee. Elle garde le processeur tant qu'elle n'est pas terminee ou bloquee (FIFO)
3. par priorite a fils multiple
   Les fils sont crees suivant la priorite des taches. Chaque fil est gere par l'algorithme du tourniquet.

   Il y a deux grandes familles de noyaux multitaches:

   - preemptif: (windows 95) une horloge genere une interruption a intervale regulier. Le sous programme d'interruption (ordonnanceur) explore la table des descripteurs et alloue suivant le cas le processeur. Dans ce cas, une tache peut prendre le processeur sans le savoir.
   - non preemptif: (windows 3.1, UNIX) la tache est executee jusqu'a ce qu'elle fasse appel a un service du noyau. A ce moment la, l'ordonnanceur compare les priorite en attente. Cette methode a l'avantage de permettre au programmleur de decider quand sa tache va rendre la main. Le risque majeur est bien sur de bloque tout le systeme si la tache se met en boucle infinie ou plante.

   La partie theorique est maintenant terminee. Nous n'allons pas aborder ici les notions de semaphores, synchronisation, etc, inherentes aux systemes multitaches car ils depasseraient le cadre de cet article. Ce sont neanmoins des points tres interessants que je vous invite a etudier si cet article vous laisse sur votre faim.

   LA PRATIQUE

     Cahier des charges

   Il est indispensable que les notions precedentes soient comprises. La connaissance de l'assembleur est aussi plus que souhaitable et particulierement le fonctionnement des piles LIFO, qui equipent le 68000.

   Nous allons a present definir le cahier des charges et essayer de nous y tenir. Nous pourrons eventuellement continuer cette serie d'articles si la demande s'en fait sentir.

   - Le langage retenu pour la creation de ce noyau est evidemment l'assembleur. L'assembleur utilise est Devpac 2.
   - Le noyau sera du type tourniquet preemptif avec un quantuum (base de temps de l'horloge) fixe a 20ms. Cette base de temps represente le temps minimal alloue a une tache lors de son traitement. Il faut qu'elle soit rapide, pour que l'utilisateur ne s'appercoive pas de la commutation, mais pas trop pour ne pas gaspiller le temps processeur a ne faire que de la commutation. Nous avons choisi 20ms car ce temps correspond a la duree d'un balayage video et nous pourrons donc a cet effet utiliser l'interruption qui lui est dediee...

   Descripteur de processus

   Penchons nous maintenant sur le descripteur de tache. Nous y trouvons presque tous les elements decrit dans la partie theorique, soit:

     CODE : pointeur sur le code de la tache
     PILE : pointeur sur la pile de la tache
     ETAT : 1 mot pour representer l'etat de la tache
     PRIO : 1 mot refletant la priorite de la tache
     Nous entendons ici par priorite la quantite de temps alloue a la tache lors de son traitement. Il s'agit du nombre de quantuum qui lui sont attribues. La tache aura donc une duree de 20*PRIO ms car nous avons fixe un quantuum de 20 ms
     NEXT : pointeur sur le descripteur suivant

   Voici la traduction en C de cette structure:

            struct tache{
                 int *CODE;
                 int *PILE;
                 short ETAT;
                 short PRIO;
                 tache *NEXT;
            }

   et celle en assembleur:

       CODE     equ     0
       PILE     equ     4
       ETAT     equ     PILE+4
       PRIO     equ     ETAT+2
       NEXT     equ     PRIO+2

       processus
            ds.l     1     ;pointeur sur le code
            ds.l     1     ;pointeur sur la pile
            ds.w     1     ;etat
            ds.w     1     ;priorite
            dc.l     1     ;pointeur sur le descripteur suivant

     Commutation de tache

   Nous devons maintenant nous interesser a la commutation de tache proprement dite. Que se passe t-il lors du passage d'une tache a une autre?

   1. sauvegarde de la position ou la derniere tache a ete interrompue. C'est exactement ce qui se passe lors de l'appel d'une sous-routine avec un BSR en assembleur ou un GOSUB en basic. Ainsi, lors de la reprise de cette tache, le micro processeur executera l'instruction qui suivra celle ou la tache a ete interrompue.
      Cette sauvegarde est realisée intrinsequement au 68000. En pratique, le 68000 va empiler le PC (Program Counter) qui indique l'instruction pointee. Le PC a la taille d'un mot long, le poids faible est d'abord empile, puis c'est le tour du poids fort.
   2. sauvegarde du status register qui represente l'etat du CPU et le CCR (Code Condition Register). Cette sauvegarde est indispensable car entre deux instructions, ce dernier peut etre modifie, et si la commutation a lieu a ce moment-la, lors de la reprise, le registre aura ete modifie... Cette sauvegarde est aussi realisee automatiquement apres celle du PC. Un nouveau mot est empile.
   3. sauvegarder tous le contenu des registres car nous ne pouvons pas prevoir a l'avance quels seront ceux utilise par la tache qui aura la main.
      Nous devons nous charger de cette sauvegarde. Celle-ci sera fait sur la pile de la tache courante, donc a la suite de PC et SR. Nous disposons a cet effet d'une instruction particuliere qui realise l'empilement (ou l'empilage?) de plusieurs regitres en un coup. Il s'agit de MOVEM.
   4. restituer le contexte de la nouvelle tache, c'est-a-dire restauration des registres sauvegardes
   5. branchement a l'instruction suivante de celle ayant ete interrompue precedemment.

   Que se passe t-il lors de la premiere commutation? En effet, aucune tache n'a son contexte defini. C'est pourquoi, a l'initialisation, on cree un contexte par defaut avec des registres vides, un PC pointant sur la premiere instruction des taches et un SR de $2300. Cela revient en fait a creer le contexte que les taches auraient au lors de lors interruption, le demarrage d'une tache agissant alors comme s'il s'agissait de la reprendre.

     Fonctionnement du noyau

   Le code du noyau n'est que l'application de ce qui a ete decrit precedemment, presque mot pour mot... Nous allons voir en detail ce qu'il se passe et comment le traduire. Chaque processus a sa propre pile. Lorsque le processus "A" tourne, l'etat des piles est celui represente fig. 5

   - Lorsque l'interruption survient, les registres PC et SR sont automatiquement empiles, comme le montre l'etape 1 de la figure 6.

   - Le 68000 se branche sur le noyau multitache. (routine d'interruption). Le quantuum de la tache est decremente puis compare a zero. Si ce n'est pas le cas, on ressort du noyau en depilant SR et PC grace a un RTE et la tache reprend son execution.

     sinon

   - les registres de la tache courante sont sauves par le MOVEM, comme le montre l'etape 2 de la figure 6.
   - l'ordonnanceur balaye les descripteur des taches et elit la premiere qui a l'etat EXEC.
   - L'adresse de pile de la tache courante est sauve dans son descripteur a l'offset PILE.
   - La pile de la nouvelle tache est restauree, ainsi que les registres grace au MOVEM (etape 3 fig 6). Enfin, celle-ci reprend son execution avec le RTE qui depile SR et PC en fin de routine d'interruption. (etape 4, fig 6.)

   CAS PRATIQUE

   Vous trouverez joint avec l'article les sources commentes du noyau que nous venons de decrire. Il s'agit de deux fichiers:

   - noyau.s : contient le code du noyau proprement dit
   - taches.s : contient le code des taches lancees par le noyau

   Nous pouvons ainsi garder toujours le noyau sous la main et ecrire les taches en annexes, comme des routines tout a fait independantes. Dans l'exemple donne, nous avons 5 taches:

   - la tache 0 s'occupe de scruter le clavier et en particulier l'appui sur la touche espace pour tout arreter.
   - les taches 1 a 4 changent la couleur 0

   A titre d'exercice, vous pouvez ameliorer la tache 0 afin d'en faire un pointeur capable d'arreter et redemarrer des taches, lors d'appui sur certaines touches. Il suffit pour cela de changer leur valeur contenue dans ETAT. Ces valeurs sont contenues dans des noms symboliques tels que EXEC, SUSP, DORM... Amusez vous aussi a changer les valeurs des quantuum pour voir l'effet que cela produit sur les taches et notamment a l'affichage. Pourquoi ne pas synchroniser certaines d'entres elles avec des valeurs "verrou" qu'elles testent? (il s'agit des semaphores).

   LITTERATURE

   Pour ceux qui voudraient approfondir les notions que nous avons appercues dans cet article, ou tout simplement pour les completer avec de nouvelles informations, je vous recommande la lecture de ces ouvrages:

   - Les bases de l'informatique industrielle (3 tomes)
   - La programmation sous UNIX (J.M Riflet, ediscience)
   - La communication sous UNIX (du même auteur)
   - STMAG n° 43
   - Dream n° 50 (avril 97) avec un dossier sur les systemes d'exploitation

   La plateforme ideale pour s'experimenter a la programmation multitache reste sans doute Linux. Pour les gens qui aiment "bidouiller" avec leur micro, savoir ce que leur OS a dans le ventre et disposer de centaines d'outils de developpements (compilateurs, shells, debuggers, profiler, ... ) courrez vous proccurer les guides d'introduction a Linux, tres repandus sur le Net. N'oubliez pas non plus que ce systeme est disponible sur nos machines, avec l'interface X Window! Si vous voulez vous essayer a ce systeme sur Falcon, la distribution la plus repandue est la WatchTower.

   Faites moi part de vos ameliorations, suggestions et questions sur:

   3615 RTEL1 bal SUPERNOVA
   ou
   supernova@rtel.fr

   Bon code!

   23/03/98, 22h37
   TOXIC MAG

   [NdTB : la prochaine fois, pense aux accents ! ;-)]

   [Retour au sommaire]