Il est demandé d'implanter un système de gestion de processus sur une machine virtuelle par simulation au-dessus d'un système Unix.
Ce projet devra être réalisé sur les machines d'enseignement, en langage C et en utilisant les fonctions décrites en cours/TD. Le travail devra être réalisé par groupe de 3 étudiants au plus. Un rapport devra être remis le jour de la soutenance (dont la date sera fixée ultérieurement).
Vous est fourni un assembleur du langage d'assemblage KSInu en langage machine KSInu. Les instructions du langage sont les suivantes :
Mnémonique | Paramètres | Sémantique |
---|---|---|
DONNEES | cst | taille zone de données |
AFFECTE | ref,ref_cst | ref = ref_cst; |
AFFECTE+ | ref,ref_cst | ref += ref_cst; |
AFFECTESP | ref,saut | ref = saut; |
TEST | ref_cst,ref_cst | ref_cst==ref_cst |
SI | saut | if (test) goto etiquette; |
SAUT | saut | goto etiquette; |
CPILE | cst | augmente la pile |
DPILE | cst | diminue la pile |
APPEL | saut | ref = etiquette(...); |
RETOUR | return; | |
TRAPPE | cst | ref = syscall(...); |
etiquette: | représente un saut possible |
L'écriture d'un programme en langage KSInu est assez délicate, mais l'assembleur fournit devrait vous aider. Les commentaires commençent par // et terminent à la fin de la ligne. La première instruction (DONNEES) n'est pas une instruction machine, mais une information qui sera utilisée par le système (voir plus bas). Apparaissent trois types de paramètres :
Le point d'entrée du programme est soit la première instruction suivant DONNEES, soit l'instruction qui suit l'étiquette debut. Un simple programme serait :
DONNEES #2 debut:
AFFECTE M0,#0 AFFECTE M1,#1 boucle: AFFECTE+ M0,M1 AFFECTE+ M1,#1 TEST M1,#10 SI fin SAUT boucle fin: RETOUR
Ce programme calcule simplement la somme (dans M0) des neuf premiers entiers.
L'instruction TEST permet de comparer deux valeurs, et en cas d'égalité de mettre à jour un drapeau de la machine.
L'instruction SI permet de réaliser un saut à l'adresse indiquée si le drapeau est positionné (saut conditionnel).
L'instruction SAUT est un simple saut non conditionnel à l'adresse indiquée.
L'instruction CPILE permet d'augmenter la taille de la pile du nombre de mot indiqué. Alors le sommet de pile est déplacé de la bonne quantité. Les adresses de pile valides sont P0 pour le somet de pile, P1 pour l'élément situé derrière le sommet de pile, etc.
L'instruction DPILE permet de diminuer la taille de la pile du nombre de mots indiqués.
Pour manipuler les éléments de la pile on utilisera les instructions AFFECTE et AFFECTE+ avec des références sur la pile.
L'instruction AFFECTESP permet simplement d'obtenir un "pointeur" de fonction.
L'instruction APPEL réalise un appel de sous-programme. Pour cela, la pile est automatiquement augmentée d'un mot contenant alors l'adresse de retour qui sera donc dépilée avec l'instruction RETOUR. Attention donc : dans un sous-programme, le premier élément de la pile est l'adresse de retour, pas le premier paramètre. Par convention on utilisera aussi le deuxième élément de la pile pour renvoyer une valeur lorsqu'il s'agit d'une fonction.
L'instruction TRAPPE réalise une trappe vers le système : appel d'une routine du noyau. Elle se comporte comme un appel de sous-programme (empilement d'une adresse de retour, etc.) mais effectue en réalité un appel système. Les trappes valides sont :
Trappe | Sémantique |
---|---|
CLONE | fork(); |
RECOUVRE | exec(ref_cst) |
ATTENDS | wait(ref); |
FIN | exit(ref); |
CAPTURE | sigaction(cst,ref_cst); |
EMETS | kill(ref_cst,ref); |
ID | getpid(); |
IDP | getppid(); |
LIT | read(0,ref,ref_cst); |
ECRIT | write(1,ref,ref_cst); |
La trappe RECOUVRE permet de recouvrir l'espace du processus en cours par celui nécessaire pour exécuter celui contenu dans le fichier Unix désigne par le caractère ASCII du paramètre. Ex : AFFECTE P0,#65 puis TRAPPE RECOUVRE recouvre le processus courant par le code contenu dans le fichier a.objet (ASCII 'a' == 65).
La trappe ATTENDS permet d'attendre la mort d'un fils s'il en existe au moins un. En retour celle-ci renvoie le numéro du processus mort en P0. Et la variable passée en paramètre contiendra en retour la cause de la mort : le bit de poids fort (31) vaut 0 si la mort est naturelle (appel à TRAPPE FIN) et 1 si la mort a été causée par un signal, les 31 bits restants contenant alors la valeur (tronquée à 31 bits) de l'appel à TRAPPE FIN ou la valeur du signal ayant causé la mort.
La trappe FIN permet de terminer normalement un processus en renvoyant un code de retour.
La trappe CAPTURE permet de positionner le comportement en reception d'un signal. Si le second paramètre vaut 0 alors le signal est ignoré, si le second paramètre vaut 1 il s'agit du comportement par défaut (la mort), les autres valeurs possibles sont définies plus loin.
La trappe EMETS permet d'envoyer un signal.
Pour le reste, cela devrait être suffisamment explicite.
Chaque appel système renvoie sa valeur de retour sur le deuxième élément de la pile, les appels TRAPPE sont des appels de fonction..
Cette machine est constituée d'une mémoire, d'un processeur, d'un gestionnaire de mémoire virtuelle et de deux ports d'entrées/sorties.
L'unité d'accès à cette mémoire est le mot de 32 bits. Elle est constituée
de NPP
(16) pages physiques contenant
chacune NMPPP (32) mots. Un mot peut contenir une
instruction ou une donnée (entier signé).
L'unité d'exécution est définie par l'ensemble des instructions pouvant être interprétées. Chaque instruction est codée dans un seul mot mémoire.
Les instructions sont toutes codées de la manière suivante :
Octet d'adresse i | Octet d'adresse i+1 | Octet d'adresse i+2 | Octet d'adresse i+3 |
---|---|---|---|
Instruction | type params | param 1 | param 2 |
Certaines n'utilisent pas de paramètres, certaines 1 et d'autres 2.
L'interprétation des paramètres (param 1 ou param 2) est effectuée en utilisant l'octet de type des paramètres, de la manière suivante (les adresses sont toujours non signées) :
bit 7 | bit 6 | bit 5 | bit 4 | bit 3 | bit 2 | bit 1 | bit 0 |
---|---|---|---|---|---|---|---|
futur | futur | C/R param1 | M/P param1 | D/I param1 | C/R param2 | M/P param2 | D/I param2 |
L'indicateur C/R permet d'indiquer si le paramètre numéro 1 est une constante ou une référence (0 : constante, 1 : référence).
L'indicateur M/P permet d'indiquer si la référence est en zone de données (M : 0) ou sur la pile(P : 1).
L'indicateur D/I indique si la référence est directe ou indirecte (0 : directe, 1 : indirecte)..
Par exemple, l'instruction AFFECTE M0,P2 vaut donc (en héxadécimal) : 0x01260002.
Les codes des instructions sont les suivants :
Instruction | Code |
---|---|
AFFECTE | 0x01 |
AFFECTE+ | 0x02 |
SI | 0x03 |
SAUT | 0x04 |
CPILE | 0x05 |
DPILE | 0x06 |
APPEL | 0x07 |
RETOUR | 0x08 |
TEST | 0x09 |
TRAPPE | 0x0A |
AFFECTESP | 0x0B |
DONNEES | 0xFF |
Attention : DONNEES n'est pas une véritable instruction! C'est une directive ne pouvant apparaître que dans le premier mot d'un fichier exécutable.
Il est constitué de 3 régions : la région de code, la région de données, la pile.
L'espace d'adressage est virtuel, il existe donc une fonction permettant de transformer toute adresse virtuelle en adresse physique (par utilisation d'une table des pages). La table des pages est elle-même en mémoire physique. Un registre du processeur est utilisé pour contenir le numéro de la page physique contenant la table des pages.
Le système utilisera donc un fichier Unix hôte comme mémoire secondaire pour les pages physiques évincées.
Les instructions sont exécutées normalement par le processeur à raison d'une instructions par seconde (vitesse de l'horloge : 1Hz). Mais cette valeur pourra être modifiée (voir plus bas).
Il doît fournir les services de gestion de processus nécessaires au bon fonctionnement des instructions décrites; et donc une notion de processus.
À part le premier processus, tous les autres sont obtenus par clonage. Une primitive de recouvrement permet à un processus d'exécuter un code différent (avec un espace d'adressage neuf).
Les processus peuvent communiquer par l'intermédiaire de signaux prédéfinis :
Signal | Sémantique | Comportement par défaut | Peut être capturé | Peut être ignoré | Création d'une image |
---|---|---|---|---|---|
2 | arme fatale | terminaison | non | non | non |
3 | violation mémoire | terminaison | oui | non | oui |
4 | suspension | suspension de l'exécution | non | oui | sans objet |
5 | reprise | reprise de l'éxécution | non | non | sans objet |
6 | non définie | terminaison | oui | oui | non |
7 | non définie | terminaison | oui | oui | oui |
8 | instruction illégale | terminaison | oui | non | oui |
On rapelle que les valeurs 0 et 1 permettent respectivement d'ignorer ou de repositionner le comportement par défaut.
Certains signaux provoquent la création d'un fichier image du processus : on y mettra l'ensemble des informations nécessaires permettant une analyse post-mortem du processus: espace d'adressage, état du processeur, état du processus et tout ce que l'on jugera nécessaire. Le fichier généré aura pour nom <numéro de processus>.image.
Les processus peuvent prendre au moins cinq états : éligible, suspendu, attente de lecture, attente fils, zombi.
L'ordonnanceur de processus est préemptif : les processus ne peuvent obtenir le processeur plus d'un QUANTUM à la fois. Cette valeur pourra être modifiée (voir plus bas).
Il n'y a pas de priorités définies. Les processus éligibles pour l'exécution sont en simple FIFO.
Il existe deux TRAPPEs permettant de réaliser des entrées/sorties. Elles sont très primitives :
La simulation du système KSInu doit être réalisée par l'intermédiaire de deux processus Unix coopératifs :
Les deux processus communiquent par signaux et tube. Lorsque l'interface désire communiquer une information au système, elle envoie un message dans le tube et envoie un signal d'interface au système afin que celui-ci prenne en compte la requête dès qu'il lui est possible de le faire. Les réponses du systèmes sont affichées directement par le système lui-même.
Le processus interface est aussi chargé de cadencer la machine KSInu en envoyant le signal d'horloge : soit à intervalles réguliers, soit au gré de l'utilisateur.
On a donc le schéma suivant :
Le système effectue lui-même les lectures des fichiers exécutables KSInu et les écritures de fichiers images KSInu.
Elle doit permettre (entre autres) :
Comme d'habitude il est recommandé de procéder avec précautions; et surtout de commencer par réfléchir. Les choix sont très nombreux.
Un assembleur de code source KSInu est fournit : on trouvera ses sources dans le répertoire ici. Sa compilation (en utilisant make) ne devrait pas poser de problèmes fondamentaux. Les outils utilisées sont bison et flex. Il n'est pas conseillé en cas de problèmes de tenter de les modifier, faites donc un rapport de bogue à l'auteur. L'utilisation de cet outil est très simple : assembleur_ksi < fichier.source > fichier.objet. Sur la sortie erreur apparaîtra les erreurs ainsi que le code généré (en utilisant les mnémoniques pour plus de lisibilité). Voici quelques exemples de code source que vous pouvez tenter de compiler et utiliser comme tests pour le projet :
Par convention, les fichiers code source utiliseront l'extension .source, les fichiers exécutables .objet et les fichiers images .image.
Jean-Baptiste Yunès