KSInu

Projet Systèmes II (Licence 2001-2002)

L'auteur de cette page est : Jean-Baptiste Yunes

Introduction

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 POSIX décrites en cours/TD. Le travail devra être réalisé par groupe de cinq étudiants au plus. Un rapport devra être remis le jour de la soutenance (dont la date sera fixée ultérieurement).

Le langage KSInu

Vous est fourni un assembleur du langage d'assemblage KSInu en langage machine KSInu. Les instructions du langage sont les suivantes :

Instructions (langage KSI)

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 :

ref

dont la syntaxe est : le caractère optionel *, suivit d'un caractère P ou M, suivi d'un nombre en base 10. Le caractère P indique qu'il s'agit d'une adresse sur la pile (les adresses de pile sont à l'envers). Le caractère M indique qu'il s'agit d'une adresse de la zone de données. Le caractère * indique l'indirection : l'adresse en question contient une adresse en zone de données. Par exemple : M10 désigne le onzième mot mémoire en zone de données; P3 désigne le quatrième mot mémoire à partir du sommet de pile; *M23 désigne le mot mémoire dont l'adresse est contenue dans le vingt-quatrième mot mémoire; *P10 désigne le mot mémoire dont l'adresse est contenue dans le onzième élément à partir du sommet de pile. Attention : l'indirection ne désigne que des mots mémoire en zone de données.

cst

dont la syntaxe est #NOMBRE. Il s'agit alors d'une constante.

saut

dont la syntaxe en langage KSInu est une simple étiquette. Cela représente donc une adresse de code.

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 :

Trappes système

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..

La machine KSInu

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.

La mémoire

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é).

Le processeur

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 :

Codage des instructions

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) :

Octet de type paramètres

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 :

Code des instructions

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'une fichier exécutable.

L'espace d'adressage

Il est constitué de 3 régions : la région de code, la région de données, la pile.

la région de code

cette région ne peut être adressée autrement que par le processeur et par les instructions faisant intervenir un argument de type : saut. Sa taille est fixe et d'au plus 256 mots. De plus cette région est protégée contre l'écriture.

la région de données

la taille de cette région est fixée statiquement dans l'exécutable par la directive DONNEES. Sa taille est d'au plus 256 mots.

la pile

la taille de cette région est modifiée dynamiquement par les instructions EMPILE et DEPILE. Sa taille est variable et d'au plus 256 mots.

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.

Le cadencement des instructions

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).

Le système KSInu

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.

Les 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 :

Signaux KSInu

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'ordonnancement

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.

Les entrées/sorties

Il existe deux TRAPPEs permettant de réaliser des entrées/sorties. Elles sont très primitives :

l'écriture

les écritures sont immédiates. Le format de sortie n'est pas précisé.

la lecture

les lectures sont effectuées dans un tampon d'entrée qui pourra être modifiée par une procédure particulière (voir plus bas).

La simulation

La simulation du système KSInu doit être réalisée par l'intermédiaire de deux processus Unix coopératifs :

1.      un processus chargé de simuler le système

2.      un processus d'interface permettant de "piloter" le système.

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 :

schema

Le système effectue lui-même les lectures des fichiers exécutables KSInu et les écritures de fichiers images KSInu.

L'interface

Elle doit permettre (entre autres) :

La réalisation

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 /ens/yunes/public/KSInu. 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.


Valid XHTML 1.0!Valid CSS!W3C-Amaya