< Gérer la mémoire - utiliser la pagination pour une tâche utilisateur | TutoOS | Un système multi-tâches : des appels systèmes préemptibles >
Un système multi-tâches simple
Sources
Le package contenant les sources est téléchargeable ici : kernel_MultiTask.tgz
Pour naviguer dans l'arborescence : MultiTask
Exécuter plusieurs tâches simultanément grâce à l'ordonnanceur
Nous avons détaillé dans une partie précédente comment le noyau charge et exécute une tâche utilisateur. Dans ce chapitre, nous allons voir comment implémenter un ordonnanceur (scheduler) simple qui permet au noyau d'exécuter plusieurs tâches en quasi simultanéité.
L'implémentation actuelle est très simple :
- le noyau charge plusieurs tâches
- les interruptions sont ensuite rétablies
- lors de chaque interruption d'horloge, le processeur appelle une fonction particulière dont le rôle est de partager le temps CPU entre les différentes tâches. Si une tâche est elligible, le noyau va :
- sauvegarder la tâche en cours
- choisir la nouvelle tâche
- effectuer la commutation
- la nouvelle tâche s'exécute jusqu'à la nouvelle interruption d'horloge (...)
Un ordonnanceur appelé à chaque interruption d'horloge
Lors de chaque interruption d'horloge, le processeur fait appel à la fonction schedule() :
void isr_clock_int(void)
{
static int tic = 0;
static int sec = 0;
tic++;
if (tic%100 == 0) {
sec++;
tic = 0;
}
schedule();
}
La fonction schedule() peut être confronté à différents cas :
- Si aucune tâche n'est prète, le scheduler ne fait rien.
- Si aucune tâche ne tourne mais qu'une tâche est prète, nous sommes dans une situation déjà vue précédemment ! Le noyau passe la main à la tâche utilisateur à la différence que celle-ci n'est pas chargée par le programme principal mais suite à une interruption d'horloge.
- Si une tâche tourne et qu'au moins une autre tâche est prète : le scheduler effectue un changement de tâche. Cette partie est la plus délicate et nous place dans le vif du sujet... Pour passer la main à une nouvelle tâche, le noyau doit :
- sauvegarder la tâche en cours
- charger la nouvelle tâche
- effectuer la commutation
Le code de l'ordonnanceur est présent dans le fichier
schedule.c
#include "types.h"
#include "gdt.h"
#include "process.h"
void schedule(void)
{
u32* stack_ptr;
u32 esp0, eflags;
u16 ss, cs;
/* Stocke dans stack_ptr le pointeur vers les registres sauvegardes */
asm("mov (%%ebp), %%eax; mov %%eax, %0" : "=m" (stack_ptr) : );
/* Si il n'y a pas de processus charge et qu'au moins un est pret, on le charge */
if (current == 0 && n_proc) {
current = &p_list[0];
}
/*
* Si il y a un seul processus (qu'on laisse tourner) ou aucun
* processus, on retourne directement.
*/
else if (n_proc <= 1) {
return;
}
/* Si il y a au moins deux processus, on commute vers le suivant */
else if (n_proc>1) {
/* Sauver les registres du processus courant */
current->regs.eflags = stack_ptr[16];
current->regs.cs = stack_ptr[15];
current->regs.eip = stack_ptr[14];
current->regs.eax = stack_ptr[13];
current->regs.ecx = stack_ptr[12];
current->regs.edx = stack_ptr[11];
current->regs.ebx = stack_ptr[10];
current->regs.ebp = stack_ptr[8];
current->regs.esi = stack_ptr[7];
current->regs.edi = stack_ptr[6];
current->regs.ds = stack_ptr[5];
current->regs.es = stack_ptr[4];
current->regs.fs = stack_ptr[3];
current->regs.gs = stack_ptr[2];
current->regs.esp = stack_ptr[17];
current->regs.ss = stack_ptr[18];
/*
* La fonction l'interruption et la fonction schedule()
* empilent un grand nombre de registres sur la pile.
* L'instruction ci-dessous permet de repartir sur une pile
* noyau propre une fois la commutation effectuee.
*/
default_tss.esp0 = (u32) (stack_ptr + 19);
/* Choix du nouveau processus (un simple roundrobin) */
if (n_proc > current->pid+1)
current = &p_list[current->pid+1];
else
current = &p_list[0];
}
/*
* Empile les registres ss, esp, eflags, cs et eip necessaires a la
* commutation. Ensuite, la fonction do_switch() restaure les
* registres, la table de page du nouveau processus courant et commute
* avec l'instruction iret.
*/
ss = current->regs.ss;
cs = current->regs.cs;
eflags = (current->regs.eflags | 0x200) & 0xFFFFBFFF;
esp0 = default_tss.esp0;
asm(" mov %0, %%esp; \
push %1; \
push %2; \
push %3; \
push %4; \
push %5; \
push %6; \
ljmp $0x08, $do_switch" \
:: \
"m" (esp0), \
"m" (ss), \
"m" (current->regs.esp), \
"m" (eflags), \
"m" (cs), \
"m" (current->regs.eip), \
"m" (current)
);
}
Sauvegarder la tâche en cours
Nous allons tout d'abord détailler comment la fonction schedule() sauvegarde les registres de la tâche en cours (celle qui a été interrompue) dans la structure qui lui est dédiée et pointée par current.
Les registres à sauvegarder ont déjà été empilés sur la pile noyau par l'interruption d'horloge (ss, esp, eflags, cs et eip) et par l'appel explicite aux instructions pushad et push :
pile
La sauvegarde des registre se fait dans la structure struct process associée à la tâche encore en court et pointée par current :
struct process {
unsigned int pid;
struct {
u32 eax, ecx, edx, ebx;
u32 esp, ebp, esi, edi;
u32 eip, eflags;
u32 cs:16, ss:16, ds:16, es:16, fs:16, gs:16;
u32 cr3;
} regs __attribute__ ((packed));
} __attribute__ ((packed));
Le procédé pour récupérer ces valeurs sur la pile repose sur l'utilisation du registre ebp (voir pour plus de détail la partie sur les Stack Frame).
La variable stack_ptr adresse la pile de façon à pouvoir ensuite récupérer facilement le contenu des registres sauvegardés lors de l'interruption :
/* stocke dans stack_ptr le pointeur vers les registres sauvegardes */
asm("mov (%%ebp), %%eax; mov %%eax, %0" : "=m" (stack_ptr) : );
/* sauve l'ensemble des registres */
current->regs.ss = stack_ptr[18];
current->regs.esp = stack_ptr[17];
current->regs.eflags = stack_ptr[16];
/* etc... */
Choisir la nouvelle tâche
L'ordonnanceur choisit une nouvelle tâche et fait pointer la variable current vers la structure de la nouvelle tâche à activer :
/* Choix du nouveau processus (un simple roundrobin) */
if (n_proc > current->pid+1)
current = &p_list[current->pid+1];
else
current = &p_list[0];
Commuter
Une fois que l'ancienne tâche est sauvegardée et que la nouvelle tâche est choisie, le scheduler doit charger les registres du processeur avec les valeurs sauvegardées précedemment avant de commuter.
En premier lieu, le pointeur de pile noyau du TSS est initialisé de façon à ce que :
- la pile noyau, sur laquelle des registres ont été sauvegardés, soit nettoyée une fois la commutation effectuée
- la pile noyau soit préparée pour la nouvelle tâche
default_tss.esp0 = (u32) (stack_ptr + 19);
L'utilisation d'une seule pile noyau pour l'ensemble des tâches a l'avantage de la simplicité mais a également un inconvénient important : il est impossible de préempter une tâche alors qu'elle effectue un appel système. La raison est exposée en détail au chapitre suivant qui traite de la réalisation d'un système multi-tâches avec des appels systèmes interruptibles.
Ensuite, les valeurs sauvegardées correspondant aux registres ss, esp, eflags, cs et eip sont empilées afin de préparer la commutation. La fonction do_switch() est appelée pour effectuer la commutation proprement dite :
asm(" mov %0, %%esp; \
push %1; \
push %2; \
push %3; \
push %4; \
push %5; \
push %6; \
ljmp $0x08, $do_switch" \
:: \
"m" (esp0), \
"m" (ss), \
"m" (current->regs.esp), \
"m" (eflags), \
"m" (cs), \
"m" (current->regs.eip), \
"m" (current)
);
La fonction do_switch()
La fonction do_switch(), implémentée dans le fichier sched.asm, n'est pas très compliquée :
global do_switch
do_switch:
; recuper l'adresse de *current
mov esi, [esp]
pop eax ; depile @current
; prepare les registres
push dword [esi+4] ; eax
push dword [esi+8] ; ecx
push dword [esi+12] ; edx
push dword [esi+16] ; ebx
push dword [esi+24] ; ebp
push dword [esi+28] ; esi
push dword [esi+32] ; edi
push dword [esi+48] ; ds
push dword [esi+50] ; es
push dword [esi+52] ; fs
push dword [esi+54] ; gs
; enleve le mask du PIC
mov al, 0x20
out 0x20, al
; charge table des pages
mov eax, [esi+56]
mov cr3, eax
; charge les registres
pop gs
pop fs
pop es
pop ds
pop edi
pop esi
pop ebp
pop ebx
pop edx
pop ecx
pop eax
; retourne
iret
- l'adresse de la structure de la nouvelle tâche est récupérée dans le registre
esi
- un signal est envoyé au PIC pour rétablir les interruptions hardware
- le répertoire de page de la nouvelle tâche est chargé (note : à ce point là, nous sommes toujours dans l'espace d'adressage du noyau, partagé par toutes les tâches)
- les registres sont directement chargés à partir de la structure de la nouvelle tâche
- l'instruction
iret retourne de l'interruption et charge les registres 'ss, esp, eflags, cs et eip''
A ce moment, la commutation est achevée et la nouvelle tâche utilisateur s'exécute !
Note concernant les appels système
Dans cette première implémentation, les tâches ne peuvent êtres préemptées alors qu'elles réalisent un appel système car le partage de la pile noyau conduirait à des incohérences. Il faut donc désactiver les interruptions lors des appels. Celà se fait par le choix d'un INTGATE à la place d'un TRAPGATE :
init_idt_desc(0x08, (u32) _asm_syscalls, INTGATE|0x6000, &kidt[48]); /* appels systeme - int 0x30 */
Charger une tâche en mémoire
Le chargement d'une tâche, un peu sur le même modèle que dans les chapitres précédent, se fait grâce à la fonction load_task(). Dans l'exemple ci-dessous, le noyau charge la tâche task1() à l'adresse physique 0x100000 :
load_task((u32*) 0x100000, (u32*) &task1, 0x2000);
La fonction load_task() est définie dans le fichier process.c
- Elle commence par copier la fonction à l'adresse physique voulue et met à jour le bitmap de pages
- Elle crée le répertoire et les tables de page avec la fonction
pd_create(). Les pages physiques occupées par le code de la tâche sont mappées sur les pages virtuelles en 0x40000000.
- La pile noyau est pour le moment sur la même page que celle contenant le code et le pointeur de pile est en
0x40000FF0.
- Elle demande une page pour la pile noyau. L'adresse linéaire de cette page correspond à son adresse physique (elle se situe dans l'espace d'adressage du noyau).
- Elle initialise la
struct process de cette tâche
#include "lib.h"
#include "mm.h"
#define __PLIST__
#include "process.h"
void load_task(u32 * code_phys_addr, u32 * fn, unsigned int code_size)
{
u32 page_base, pages;
u32 *pd;
int i;
/* Copie du code a l'adresse specifiee */
memcpy((char *) code_phys_addr, (char *) fn, code_size);
/* Mise a jour du bitmap */
page_base = (u32) PAGE(code_phys_addr);
if (code_size % PAGESIZE)
pages = code_size / PAGESIZE + 1;
else
pages = code_size / PAGESIZE;
for (i = 0; i < pages; i++)
set_page_frame_used(page_base + i);
/* Creation du repertoire et des tables de pages */
pd = pd_create(code_phys_addr, code_size);
/* Initialisation des registres */
p_list[n_proc].pid = n_proc;
p_list[n_proc].regs.ss = 0x33;
p_list[n_proc].regs.esp = 0x40001000;
p_list[n_proc].regs.cs = 0x23;
p_list[n_proc].regs.eip = 0x40000000;
p_list[n_proc].regs.ds = 0x2B;
p_list[n_proc].regs.cr3 = (u32) pd;
n_proc++;
}
Ce code n'est pas très compliqué car l'objet de ce chapitre est seulement de montrer comment implémenter de façon simple un système multi-tâches. J'ai donc délibérément supprimé tout ce qui peut "allourdir" le code. Il est cependant nécessaire d'en pointer deux importantes limitations:
- le choix de pages libres pour le chargement de la tâche n'est pas géré par l'allocateur
- les pages choisies sont successives (il n'y a donc pas de gestion de la fragmentation)
Le contexte d'une tâche
Lorsque une tâche est interrompue pour laisser la main à une autre, son contexte d'exécution doit être intégralement conservé afin qu'elle puisse plus tard reprendre là où elle avait été interrompue.
La structure struct process définit pour chaque tâche :
- un identifiant, le pid
- l'ensemble des registres du processeur susceptibles d'être utilisés par la tâche
Un tableau de struct process est défini pour conserver le contexte de toutes nos tâches. Le nombre maximum de tâche est pour le moment très restreint, juste 32 :
struct process p_list[32];
La variable *current pointe sur la tâche en cours d'exécution et n_proc nous renseigne sur le nombre total de tâches :
struct process *current = 0;
int n_proc = 0;
Exécuter plusieurs tâches
La fonction principale main() du noyau est très simple : elle initialise les structures habituelles puis elle charge les tâches utilisateur en mémoire et rétabli les interruptions. A chaque tic d'horloge, l'ordonnanceur est activé et donne la main à une nouvelle tâche.
#include "types.h"
#include "lib.h"
#include "gdt.h"
#include "screen.h"
#include "io.h"
#include "idt.h"
#include "mm.h"
#include "process.h"
void init_pic(void);
int main(void);
void _start(void)
{
kY = 16;
kattr = 0x0E;
/* Initialisation de la GDT et des segments */
init_gdt();
/* Initialisation du pointeur de pile %esp */
asm(" movw $0x18, %ax \n \
movw %ax, %ss \n \
movl $0x20000, %esp");
main();
}
void task1(void)
{
char *msg = (char *) 0x40001000;
int i;
msg[0] = 't';
msg[1] = 'a';
msg[2] = 's';
msg[3] = 'k';
msg[4] = '1';
msg[5] = '\n';
msg[6] = 0;
while (1) {
asm("mov %0, %%ebx; mov $0x01, %%eax; int $0x30":: "m"(msg));
for (i = 0; i < 1000000; i++);
}
return; /* never go there */
}
void task2(void)
{
char *msg = (char *) 0x40001000;
int i;
msg[0] = 't';
msg[1] = 'a';
msg[2] = 's';
msg[3] = 'k';
msg[4] = '2';
msg[5] = '\n';
msg[6] = 0;
while (1) {
asm("mov %0, %%ebx; mov $0x01, %%eax; int $0x30":: "m"(msg));
for (i = 0; i < 1000000; i++);
}
return; /* never go there */
}
int main(void)
{
printk("kernel : gdt loaded\n");
init_idt();
printk("kernel : idt loaded\n");
init_pic();
printk("kernel : pic configured\n");
/* Initialisation du TSS */
asm(" movw $0x38, %ax \n \
ltr %ax");
printk("kernel : tr loaded\n");
init_mm();
printk("kernel : paging enable\n");
hide_cursor();
load_task((u32 *) 0x100000, (u32 *) & task1, 0x2000);
load_task((u32 *) 0x200000, (u32 *) & task2, 0x2000);
kattr = 0x47;
printk("kernel : scheduler enable\n");
kattr = 0x07;
sti;
while (1);
}
< Gérer la mémoire - utiliser la pagination pour une tâche utilisateur | TutoOS | Un système multi-tâches : des appels systèmes préemptibles >
