Projet système : spécification

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette page est maintenue par les enseignants et utilisée par les élèves de la matière concernée. Vos contributions sont les bienvenues, mais merci d'en discuter avant de faire des modifications non triviales de la page, pour être sûr de ne pas perturber le déroulement du cours.

Mycomputer.png  Deuxième Année  CDROM.png  Informatique 

Sommaire

Introduction

L'objectif du projet système est de réaliser un noyau de système d'exploitation sur l'architecture Intel IA32 permettant l'exécution de programmes applicatifs simples. Les applications sont écrites en termes de processus parallèles se partageant le temps d'exécution sur le processeur avec des priorités différentes. Le noyau est bien sûr très petit, mais cependant réaliste car il offre un ensemble de services permettant d'exécuter des programmes significatifs.

Ce document énonce les spécifications du noyau de système. Une grande partie est consacrée à la description des appels systèmes que le noyau fournit aux applications.

Présentation générale

Le noyau de système d'exploitation manipule les objets suivants :

Des processus 
Un processus est l'entité contrôlant et gérant l'exécution des programmes. Chaque processus est caractérisé par son contexte de fonctionnement, son flot d'exécution et son espace mémoire. Les processus ont chacun un espace mémoire et ne partagent ni code, ni données sauf sous requête explicite au noyau.
De la mémoire (optionnel pour les apprentis)
Le noyau dispose d'une plage de mémoire physique, qu'il n'occupe pas, dont il est libre d'utilisation. Cette mémoire sera utilisée pour allouer un espace à un processus de manière à loger son code et ses données. C'est au noyau d'assurer la gestion de l'espace mémoire d'un processus en utilisant cette mémoire physique et les mécanismes de mémoire virtuelle .
Des primitives de synchronisation 
elles bloquent les processus et permettent l'échange coordonné d'information.
    • Des files de messages (Projet de spécialité 2A et Apprentis 2A): Une file de de message est un objet permettant la synchronisation entre des processus. C'est une restriction à des messages de taille fixe du pipe d'Unix.
    • Des sémaphores (option): Un sémaphore est un objet permettant la synchronisation entre des processus.
Une horloge 
L'horloge permet au noyau de partager le temps d'utilisation du processeur entre des processus concurrents. Elle permet aussi à un processus de mesurer le temps écoulé pour un calcul ou d'attendre qu'un délai soit passé avant de reprendre son exécution.
Une console 
La console est un moyen d'interaction entre le système et l'utilisateur. Elle permet aux processus et au noyau d'afficher du texte et de recevoir ce que tape l'utilisateur au clavier.

Les processus

Le nombre total de processus pouvant coexister à un instant donné dans le noyau de système est borné par une constante fixée à la compilation du noyau. Cette constante est nommée NBPROC. Une valeur typique de 30 peut être utilisée pour les tests ; en fin de projet, il sera intéressant de modifier cette valeur pour la faire passer par exemple à 1000 et d'observer comment varient les performances.

Chaque processus est identifié par un nombre unique appelé pid qui ne change pas au cours de sa vie et dont la valeur est strictement positive. Il est possible d'identifier tous les processus par des valeurs qui vont de 1 à NBPROC.

États d'un processus

À tout moment de son cycle de vie, un processus est dans un état qui caractérise son fonctionnement. Un processus peut être dans les états suivants :

Actif 
Le processus est celui qui possède le processeur.
Activable 
Le processus n'attend que la possession du processeur pour s'exécuter.
Bloqué sur sémaphore 
Le processus a exécuté une opération sur un sémaphore qui demande d'attendre pour progresser (par exemple wait).
Bloqué sur entrée/sortie 
Le processus attend qu'une entrée/sortie soit réalisée.
Bloqué en attente d'un fils 
Le processus attend qu'un de ses processus fils soit terminé.
Endormi 
Le processus a appelé wait_clock, la primitive de mise en sommeil jusqu'à une heure donnée.
Zombie 
Le processus a terminé son exécution ou a été terminé par l'appel système kill et son père est toujours vivant et n'a pas encore fait de waitpid sur lui.

Ordonnancement - Scheduling

Les processus activables se partagent l'utilisation du processeur selon des règles précises : le temps partagé avec priorités. C'est une partie du noyau qu'on appelle l'ordonnanceur (le scheduler) qui assure ces règles. Ce sont en fait un ensemble minimal de procédures qui mettent en oeuvre ces règles et qui sont appelées à chaque fois qu'un processus change d'état.

Les processus ont une priorité qui est un entier dont les valeurs possibles vont de 1 à MAXPRIO. Une valeur typique pour MAXPRIO est 256. Comme NBPROC, cette valeur peut être modifiée à chaque compilation du noyau.

Plus la valeur de sa priorité est grande, plus un processus est prioritaire pour l'utilisation du processeur. Un processus ne s'exécute jamais tant qu'il reste un autre processus de priorité supérieure actif ou activable. Les priorités sont décidées à l'extérieur du noyau de système lors de la création des processus. Elles ne peuvent être modifiées que par la primitive chprio. Le noyau de système ne change jamais de lui-même une priorité.

Tous les processus qui ont la priorité la plus élevée de tous les processus activables se partagent le temps d'utilisation du processeur de manière équitable, en respectant un ordre FIFO. Quand un processus devient actif, il prend la main pour un temps limité. En supposant qu'il est toujours actif quand le temps qui lui est alloué se termine, s'il existe un autre processus de même priorité et activable, alors il passe activable et c'est le processus qui attendait en activable depuis le plus longtemps qui prend la main pour la période suivante. Sinon il reste actif pour une nouvelle période.

L'horloge système permet d'effectuer ce contrôle en interrompant régulièrement le processeur. La fréquence de préemption est une constante de génération du noyau SCHEDFREQ qui peut prendre des valeurs comme 50 Hz ou 1000 Hz. L'horloge devrait avoir une fréquence égale ou multiple de SCHEDFREQ pour assurer correctement la préemption des processus.

Dès qu'un événement quelconque (entrée/sortie, appel à chprio, ...) change l'état d'un processus, il faut changer de processus actif si celui qui était actif ne l'est plus ou si un nouveau processus devient activable avec une priorité supérieure afin de respecter la règle de priorité. Le processus nouvellement activé disposera d'une nouvelle période de préemption aussi longue que possible (maximum 1 / SCHEDFREQ s) en perdant simplement le temps entre son activation et la précédente interruption d'horloge.

L'ordonnancement FIFO avec priorité doit également être appliqué aux autres objets du système qui bloquent des processus comme les sémaphores ou la console. Par exemple, quand on doit débloquer un processus d'un sémaphore, on choisit le plus ancien des plus prioritaires. Par contre, il n'y a pas de notion de partage de temps sur ces objets.

Vie d'un processus

Un processus est créé à l'aide de la primitive start, dont les paramètres sont :

  • le nom du programme à lancer, il permet au noyau de trouver puis charger le code et les données de l'application à lancer. Cette chaine pourra servir pour afficher la liste des processus existants dans le noyau du système ;
  • la taille d'une pile allouée par le noyau dans l'espace utilisateur pour l'exécution du processus (sauf au début du projet, où tous les processus sont exécutés en mode superviseur) ;
  • la priorité du processus;
  • un paramètre à passer lors de son lancement (ce sera le paramètre passé à la fonction initiale).

Dans le cas du projet Apprenti, un cinquième paramètre existe :

  • Un nom qui pourra servir à identifier facilement un processus dans la liste des processus obtenue avec ps par exemple.

La primitive start permet donc la création d'un processus qui exécutera un programme présent en mémoire. Le processus est créé dans l'état activable sauf si sa priorité est supérieure à celle du processus créateur, auquel cas il sera immédiatement activé.

Le noyau doit permettre à plusieurs processus d'exécuter le même programme.

Un processus peut prendre fin de trois manières différentes :

  • en sortant de la fonction initiale du processus par un retour normal de fonction,
  • en faisant l'appel système exit avec une valeur de retour,
  • en étant terminé par l'appel système kill, éventuellement appelé par un autre processus.

Pour gérer correctement la terminaison des processus, il est nécessaire que chacun connaisse son père --- celui qui l'a créé --- et ses fils --- ceux qu'il a créés. De plus, on définit un état spécial zombie, où le processus est considéré comme inexistant pour tous les appels systèmes sauf pour waitpid qui permet au père de récupérer la valeur de retour du processus.

Quand un processus est terminé, quelle que soit la manière :

  • il passe dans l'état zombie si son père existe toujours sinon il est immédiatement détruit (le pid est libéré) ;
  • chaque fils du processus terminé est marqué comme n'ayant plus de père et les fils zombies sont détruits.

Tout processus détruit doit être enlevé de la liste des fils de son père, mais les zombies y restent.

Les primitives de gestion des processus sont :

  • start : crée un processus dans l'état activable.
  • exit : termine le processus actif (ie. soi-même).
  • kill : met fin à un processus.
  • waitpid : attend la terminaison d'un processus fils et récupère sa valeur de retour.
  • getprio : lit la priorité d'un processus.
  • chprio : modifie la priorité d'un processus.
  • getpid : récupére l'identifiant du processus actif.

La mémoire (optionnel pour les apprentis)

Le noyau est responsable de la gestion de la mémoire physique de la machine. Son rôle est double:

  1. Gérer la quantité de mémoire allouée à un utilisateur du système (un processus par exemple)
  2. Gérer les droits d'accés d'un processus aux différentes zones de mémoire (protection de l'espace mémoire kernel, etc).

Votre kernel (pour les étudiants concernés par la mémoire virtuelle) doit implémenter cette gestion. Ceci implique de répertorier, et gérer l'allocation de mémoire physique, puis d'utiliser l'unité de gestion mémoire du processeur (Memory Management Unit ou MMU) pour isoler chaque processus dans un espace virtuel et ainsi contrôler ses accès à la mémoire. Ainsi, chaque processus sera isolé de ses voisins: il sera impossible d'accéder à la mémoire d'un processus utilisateur depuis un autre, sans passer par le noyau.

Empreinte mémoire du noyau

Le squelette de noyau livré pour le projet est prévu pour gérer 256 Mo de mémoire physique. Le noyau est chargé au début de la mémoire physique (à partir de l'adresse 1Mo ou 0x100000, la mémoire précédent étant réservée), son code et ses données statiques occupent quelques méga-octets. Ensuite vient son tas, jusqu'à l'adresse 64M (0x4000000), sur lequel va travailler son allocateur. Enfin la zone 64M-256M (0x4000000-0x10000000) est de la mémoire physique libre, disponible pour votre implémentation. En clair:

   0  +-------------+
      |  Réservé    |  Contient l'IDT, la GDT, la TSS et le code pour passer en mode réel.
  1M  +-------------+
      | Kernel:     |  Le code, les données et le tas du noyau.
      | code / data |
 64M  +-------------+
      | Mémoire     |  Mémoire physique libre, utilisable librement par le noyau.
      | physique    |
      | libre       |
      |             |
256M  +-------------+

Espace mémoire d'un processus

Pour exécuter un processus, le noyau doit lui allouer de la mémoire, et la lui présenter conformément à ses attentes (respecter le contraintes d'espace et d'adressage). Dans le cadre du projet, vous devez fournir cet espace mémoire à chacun des processus que vous éxecutez.

Le mapping mémoire d'un processus, c'est à dire son placement en mémoire (adresses virtuelles), la position de sa pile, de son tas, etc résultent d'un choix d'implémentation. La personne qui conçoit le noyau choisi arbitrairement - ou presque - les adresses où loger ces différents élements. Ensuite, c'est à l'aide du mécanisme de mémoire virtuelle que la correspondance adressage virtuel -> mémoire physique que la traduction est réalisée.

Pour le projet, vous devez respecter le mapping mémoire que nous proposons.

  • Le noyau est mappé entre 0 et 1Go, l'accès à cet espace mémoire est strictement réservé au noyau (niveau de protection Ring 0 chez Intel). Il est conseillé de mapper la mémoire physique dans le même espace virtuel (ie: entre 0 et 256Mo, @virtuelle = @physique).
  • Un processus est mappé dans l'espace 1Go - 4Go. Cet espace est accesible depuis l'espace utilisateur et depuis le mode noyau (niveau de protection Ring 3). Son code est linké pour s'éxecuter à l'adresse 1Go. Vous pouvez situer sa pile et son tas (si nécessaire) n'importe où entre 1Go et 4Go à condition que ces espaces n'entrent pas en conflit avec le code du processus (situé entre 1Go et 1Go + x pour mémoire).
  • La première page de l'espace mémoire (adresses entre 0 et 4Ko) ne doit pas être mappée, cela permet de faire une faute sur les déréférencement de pointeurs NULLs.

Cycle de vie d'un processus et de son espace virtuel

A titre d'exemple, nous allons décrire les étapes de création de l'espace mémoire d'un processus lors de son démarrage.

  1. A l'aide du nom de programme, reçu par start, on localise le code du programme à charger.
  2. Allocation du la mémoire physique pour le code et la pile.
  3. Créer un page directory et une page table pour réaliser les mappings mémoire.
  4. Mapper le kernel
  5. Copier le code et le mapper à partir de l'adresse 1Go
  6. Mapper la pile à l'adresse 2Go (par exemple).
  7. Associer le page directory au processus et le démarrer.

A chaque changement de contexte, il faut également changer le page directory pour que le processus qui va s’exécuter retrouve son espace virtuel, à savoir son code, sa pile et ses données. Lorsque le processus se termine, son mapping est détruit, le page directory et le page table sont détruits, la mémoire physique est libérée. Le processus a libéré son espace.

Partage de mémoire

Le noyau isole les espaces mémoire des processus en utilisant la MMU. Néanmoins, ces processus peuvent avoir besoin de communiquer entre eux. Il existe deux solutions pour contourner le problème:

  • Utiliser des files de messages par exemple, cela requiert un grand nombre d'appels système (à chaque send ou receive)
  • Partager de la mémoire entre processus, cela requiert un simple appel au noyau.

L'implémentation de files de message fait partie du sujet, néanmoins cela restreint le partage d'information à de simple entiers, passés par copie. La solution proposée est donc d'implémenter une solution de partage de mémoire.

L'API proposée est la suivante:

  • shm_create : créé une page partagée identifiée par une chaine de caractère
  • shm_acquire : permet d'obtenir un pointeur sur une page déjà partagée
  • shm_release : indique que le processus relache la référence qu'il a sur la page partagée

Elle permet de partager entre deux (ou plus) processus une page de taille standard (4 Ko) en l'identifiant à l'aide d'une chaine de caractère. Pour cela le noyau doit réserver une page de mémoire physique, qu'il va mapper à une adresse définie dans l'espace mémoire du processus. Cette adresse virtuelle n'est pas forcement identique pour tous les processus qui partagent la page. C'est un choix d'implémentation.

Tous les processus souhaitant acquérir cette page partagée doivent appeler shm_acquire pour obtenir un pointeur dessus, puis relacher la référence à l'aide de shm_release. Lorsqu'un processus est quitté à l'aide de exit ou tué à l'aide de kill ses références sur la page doivent être libérées.

L'horloge

Le noyau doit être capable de déterminer l'écoulement du temps et d'effectuer des actions à intervalles réguliers dans le temps. Pour cela, on utilise un quartz dont les oscillations sont décomptées par un circuit séparé du processeur afin de générer périodiquement une interruption. La périodicité de l'interruption est programmable en précisant le nombre d'oscillations du quartz entre chaque interruption. Dans la configuration du noyau, on préfèrera exprimer la fréquence d'interruption sous la forme d'une constante CLOCKFREQ qui peut prendre des valeurs de l'ordre de 100 Hz à 1000 Hz. Des interruptions plus fréquentes chargeraient trop le système pour un avantage trop faible, alors que des interruptions plus espacées rendraient la mesure du temps peu précise. La fréquence réelle d'interruption sera en pratique la plus proche possible de CLOCKFREQ mais ne peut pas être strictement identique, car la fréquence d'oscillation du quartz n'est pas forcément multiple de CLOCKFREQ.

Pour mesurer l'écoulement du temps, le noyau compte les interruptions qu'il reçoit. Pour connaître le temps réellement écoulé entre deux événements, il suffit de compter le nombre d'interruptions qui les sépare et de connaître le nombre d'oscillations du quartz entre chaque interruption ainsi que la fréquence du quartz. Cette mesure est précise à la période d'interruption près. Pour simplifier la mesure du temps écoulé dans le noyau et dans les applications, CLOCKFREQ ne pourra pas (même en extension) changer de valeur dynamiquement.

L'interruption de l'horloge permet également d'effectuer des vérifications périodiques, comme vérifier s'il est temps de changer de processus actif (ce qui a été discuté dans la section sur l'ordonnancement), ou s'il est temps de réveiller des processus qui auraient décidé de se mettre en pause jusqu'à une heure donnée.

Les primitives de l'horloge sont :

  • clock_settings : renvoie la fréquence du quartz et le nombre d'oscillations entre chaque interruption.
  • current_clock : renvoie le nombre d'interruptions déjà passées depuis le démarrage du système.
  • wait_clock : endort le processus jusqu'à ce que l'interruption dont le numéro (depuis le démarrage du noyau) passé en paramètre soit arrivée.


Des primitives de synchronisation

Les files de messages

Une file de messages est une structure de données permettant à des processus de se communiquer des informations et de se synchroniser selon le modèle producteur consommateur. Nous nous restreignons à des files pouvant contenir des messages de type entier (int). Le nombre maximum de files est défini par une constante du système NBQUEUE.

Un processus peut déposer (psend) un message dans une file ; trois cas sont possibles :

  • si un processus au moins est bloqué en attente de message, le message est transmis immédiatement au processus en attente le plus ancien parmi les plus prioritaires ; ce processus passe dans l'état activable (ou actif si sa priorité est supérieure) ;
  • si la file n'est pas pleine, le message est stocké dans la file ;
  • si la file est pleine, le processus est bloqué et l'opération sera poursuivie à la suite d'un retrait de message.

Lorsqu'un processus retire (preceive) un message d'une file :

  • si un message au moins est disponible dans la file, le premier message est transmis au processus. Si la file était pleine, il faut alors immédiatement compléter la file avec le message du premier processus bloqué sur file pleine ; ce processus devient activable ou actif selon sa priorité ;
  • si aucun message n'est présent, le processus se bloque et sera relancé lors d'un dépôt ultérieur.

Une file est créée par l'opération pcreate et supprimée par pdelete. Elle peut être réinitialisée par preset et on peut obtenir des informations sur l'état d'une file par pcount (nombre de processus bloqués en réception ou somme du nombre de messages dans la file et du nombre de processus bloqués en émission).

  • Remarque 1: Une file de messages doit avoir une capacité d'au moins 1 message.
  • Remarque 2: L'utilisation conjointe d'un tampon de stockage de messages et d'une file de processus bloqués en émission permet de simuler un tampon de taille non bornée.

En résumé, les primitives de gestion de file sont :

  • pcreate : crée une file de messages
  • pdelete : détruit une file de messages
  • psend : dépose un message dans une file
  • preceive : retire un message d'une file
  • preset : réinitialise une file
  • pcount : renvoie l'état courant d'une file

Les sémaphores (en option)

Les sémaphores se conforment à la sémantique de Dijkstra. Ils permettent la réalisation de sections critiques d'exécution entre plusieurs processus.

Leur mise en oeuvre comporte une valeur, la valeur du sémaphore, qui est un entier short int. La création et l'initialisation sont réalisées par la primitive screate qui retourne un identifiant de sémaphore, sid, qui devra être utilisé par tout autre primitive de manipulation de ce sémaphore. On dispose ensuite de la primitive wait permettant de réaliser le P sur un sémaphore, et la primitive signal permettant de réaliser le V. Une variante de signal est signaln qui permet de réaliser de manière atomique un nombre variable d'opérations signal, sans qu'aucun autre processus ne puisse s'exécuter entre les appels à signal. Une variante de wait est try_wait qui réalise le P uniquement dans le cas où le processus ne doit pas être bloqué.

On peut libérer un sémaphore à l'aide de la primitive sdelete, qui de surcroît libère tous les processus qui pouvaient être bloqués sur ce sémaphore. Les deux dernières primitives de manipulations des sémaphores sont scount, qui permet d'obtenir la valeur courante d'un sémaphore, et sreset qui permet de forcer une valeur dans un sémaphore, tout en libérant les éventuels processus bloqués sur ce sémaphore.

En résumé, les primitives de manipulations sont :

  • screate : pour créer un sémaphore ;
  • sdelete : pour détruire un sémaphore ;
  • signal et signaln : pour l'opération V sur un sémaphore ;
  • wait pour l'opération P ;
  • try_wait : pour l'opération P sans blocage ;
  • scount : pour obtenir la valeur courante du sémaphore ;
  • sreset: pour réinitialiser un sémaphore.

Le pilote de console

Introduction : les terminaux

Une console fait partie de ce qu'on appelle sous Unix les terminaux. Ce sont des éléments de base des systèmes d'exploitation qui sont des moyens d'envoyer des entrées à un programme et d'en voir les sorties. Une console est un terminal physique constitué d'un clavier et d'un écran. Le programme xterm est un autre type de terminal, qui effectue ses entrées et sorties dans une fenêtre graphique X-Window. Les imprimantes et les lignes séries sont aussi des terminaux.

L'unité de base manipulée par un terminal est le caractère. Les fonctions offertes par un terminal permettent de recevoir des caractères à partir de ce terminal ou d'en afficher.

À chaque fois qu'un caractère est reçu sur un terminal, celui-ci doit être placé dans un tampon pour être consommé plus tard par un programme. Si le tampon est plein, alors le caractère doit être abandonné. Quand un programme demande l'affichage d'un caractère, deux cas sont envisageables :

  • le périphérique est disponible pour afficher, le caractère est envoyé immédiatement,
  • le périphérique n'est pas disponible, dans ce cas le caractère doit être mis en attente dans un tampon. Si le tampon est plein, le processus émetteur est mis en attente, le temps que le tampon se libère.

Généralement, les terminaux fournissent beaucoup d'autres services :

  • l'affichage en écho d'un caractère lors de sa réception est souvent le mode de fonctionnement par défaut des terminaux,
  • la possibilité d'éditer une ligne en supprimant les fautes de frappe et en validant par Enter avant de transmettre les caractères à l'application,
  • la possibilité d'envoyer des signaux de contrôle à une application par certaines combinaisons de touches particulières (sous Unix, par défaut, Ctrl+C envoie un signal SIGTERM à l'application ce qui la termine),
  • ...

La console PC

Le pilote à développer dans ce projet doit fournir une interface de terminal dont les entrées se font au clavier et les sorties par le mode texte standard de la carte vidéo. Bien que la console soit souvent vue comme un unique objet, nous en détaillons les deux parties séparément. D'ailleurs, dans le projet, il est conseillé de ne pas développer ces deux parties au même moment.

Les appels systèmes cons_read, cons_write et cons_echo permettent d'accéder à la console.

cons_write envoie tous les caractères demandés à l'affichage.

cons_read prélève une ligne contenue dans le tampon associé au clavier pour la transférer à l'appelant. Si aucune ligne n'est disponible, l'appelant est bloqué jusqu'à la frappe du prochain caractère de fin de ligne.

L'appel système cons_echo permet de supprimer ou de réactiver l'affichage en écho des caractères frappés.

Le clavier

Le clavier est piloté par interruptions. Chaque interruption signale l'arrivée d'un scan code, qui fait partie d'une séquence qui permet d'identifier une touche du clavier en précisant si elle a été enfoncée ou relâchée. Pour ce projet, un automate vous est fourni qui transforme les scan codes reçus en texte correspondant aux touches tapées ; ces caractères doivent être placés dans le tampon du terminal.

L'automate de conversion s'utilise en appelant la fonction :

void do_scancode(int scancode);

Il appelle les fonctions :

void keyboard_data(char *str);
void kbd_leds(unsigned char leds);

Vous devez implanter keyboard_data. Cette fonction reçoit une chaîne de caractères qui correspond au texte converti à partir des scan codes. kbd_leds est une fonction que vous pouvez implanter si vous voulez que l'affichage des LEDs du clavier soit cohérent avec l'état de l'automate de conversion.

Le caractère de code ASCII 13 correspond à la frappe de la touche Entrée et doit être considéré comme l'indicateur de fin de ligne.

Au cours de l'entrée, il est possible d'éditer le contenu du tampon associé au clavier : la frappe de la touche backspace, signalée par le caractère de code ASCII 127, provoque la suppression du tampon du dernier caractère entré sauf si la ligne courante est vide.

L'écran

L'écran que nous considérons est le mode texte de base des cartes vidéo des PC dans lequel le noyau démarre. L'affichage fait 80 colonnes sur 25 lignes. Contrairement au clavier, l'affichage sur l'écran texte n'est pas piloté par interruption. L'affichage s'effectue en écrivant directement dans la mémoire vidéo pour y placer les caractères et leur couleur. Certaines opérations simples d'entrées-sorties supplémentaires sont nécessaires pour déplacer le curseur clignotant qui indique la position actuelle d'affichage. Il est donc possible d'écrire directement à l'écran dès qu'un programme en fait la demande, sans utiliser de tampon d'attente pour l'émission.

Les caractères affichables

Les caractères de code ASCII 32 à 126 sont tous affichés en les plaçant à la position actuelle du curseur clignotant et en déplaçant ce curseur sur la position suivante : à droite, ou au début de la ligne suivante si le curseur était sur la dernière colonne.

Les caractères de contrôle

Les caractères 0 à 31, 127 et 155 sont des caractères de contrôle. Le tableau ci-dessous décrit ceux que vous devez gérer. Tous les autres caractères de contrôle doivent être ignorés.

Code de contrôle Mnémonique Effet
8 BS Recule le curseur d'une colonne s'il n'est pas sur la première colonne
9 HT Avance à la prochaine tabulation (colonnes 1, 9, 17, ..., 65, 73, 80)
10 LF Déplace le curseur sur la ligne suivante, colonne 1
13 CR Déplace le curseur sur la ligne actuelle, colonne 1
Les autres caractères

Les caractères de code 128 à 154 et 156 à 255 ont une signification variable selon le jeu de caractères utilisé, qui change d'un système à l'autre. Nous vous conseillons de ne pas les afficher.

L'écho

Par défaut, une console affiche les caractères que l'utilisateur tape au clavier. C'est ce qu'on appelle l'écho. Dans le pilote de clavier, à chaque fois qu'une touche est appuyée et qu'une séquence de caractères est entrée en tampon, elle doit être affichée en même temps à l'écran sauf si le mode d'écho a été désactivé avec cons_echo. L'affichage de l'écho obéit à des règles différentes de celles de l'affichage normal :

  • les caractères 9 et 32 à 126 sont affichés normalement,
  • le marqueur de fin de ligne, 13, est affiché comme le caractère 10 en affichage normal,
  • les autres caractères de code inférieur à 32 sont affichés par le caractère ^ suivi par le caractère 64 + code (par exemple, Ctrl+C qui donne le code 3, s'affiche ^C),
  • dans le cas où un caractère est supprimé du tampon suite à la frappe de la touche backspace, l'écho doit provoquer l'effacement du caractère sur l'écran, ce qui peut être fait en envoyant successivement les codes 8 (BS), 32 (espace) et 8. Une limitation de cette séquence est qu'elle ne s'applique qu'à la ligne actuelle. Arrivé en début de ligne, le curseur ne remontera pas plus loin. D'autre part, les tabulations et caractères de contrôles ne sont pas correctement effacés. Il n'existe pas de solution simple pour surmonter ces difficultés.
  • tout autre cas est ignoré.

L'interpréteur de commandes

On utilisera un processus particulier pour servir d'interpréteur de commandes. Un interpréteur de commandes ou shell est l'interface entre l'utilisateur et le système d'exploitation.

Les commandes devant être mises en oeuvre sont les suivantes :

  • ps : affiche les informations sur les processus existants: pid,

état, nom du programme initial lors du lancement du processus ;

  • sinfo : affiche des informations sur les sémaphores existants : leur numéro, les processus en attente et la valeur des compteurs;
  • exit : sortie du noyau ;
  • echo : fait passer l'affichage en mode echo on ou echo off ;
  • ... : toute autre commande sera bienvenue, notamment des commandes qui démontrent chaque primitive du système.

La spécification de l'interpréteur est incomplète car faisant partie des innovations que vous avez à apporter. Il sera ainsi possible de s'inspirer des commandes des shells Unix.

Les primitives système

Les primitives système sont implantées à deux niveaux :

  • dans le noyau, sous la forme de fonctions.
  • dans une bibliothèque en mode utilisateur. Elle peuvent être appelées par n'importe quel processus utilisateur (donc avec les interruptions démasquées). Elles appellent les fonctions équivalentes au niveau noyau en effectuant un appel système (int $49).

Leur description est donnée dans cette section. Vous devez respecter tous les prototypes donnés dans la suite tant pour leurs noms que pour leurs paramètres.

chprio - Changement de priorité d'un processus

int chprio(int pid, int newprio);

La primitive chprio donne la priorité newprio au processus identifié par la valeur de pid. Si la priorité du processus change et qu'il était en attente dans une file, il doit y être replacé selon sa nouvelle priorité.

Si la valeur de newprio ou de pid est invalide, la valeur de retour de chprio est strictement négative, sinon elle est égale à l'ancienne priorité du processus pid.

Voir aussi :

clock_settings - Fréquence des tops d'horloge

void clock_settings(unsigned long *quartz, unsigned long *ticks);

Retourne dans *quartz la fréquence du quartz du système et dans *ticks le nombre d'oscillations du quartz entre chaque interruption.

Voir aussi :

cons_echo - Configuration du terminal

void cons_echo(int on);

Si on est nul, désactive l'écho sur la console, sinon le réactive.

Voir aussi :

cons_read - Lecture sur le terminal

unsigned long cons_read(char *string, unsigned long length);

Si length est nul, cette fonction retourne 0. Sinon, elle attend que l'utilisateur ait tapé une ligne complète terminée par le caractère 13 puis transfère dans le tableau string soit la ligne entière (caractère 13 non compris), si sa longueur est strictement inférieure à length, soit les length premiers caractères de la ligne. Finalement, la fonction retourne à l'appelant le nombre de caractères effectivement transmis. Les caractères frappés et non prélevés restent dans le tampon associé au clavier et seront prélevés aux appels suivants. Le caractère de fin de ligne (13) n'est jamais transmis à l'appelant&nbsp.

Lorsque length est exactement égal au nombre de caractères frappés, fin de ligne non comprise, le marqueur de fin de ligne reste dans le tampon. Le prochain appel récupèrera une ligne vide.

Voir aussi :

cons_write - Affichage sur le terminal

int cons_write(const char *str, long size);

Envoie sur le terminal la suite de caractères de longueur size à l'adresse str.

Voir aussi :

current_clock - Heure actuelle

unsigned long current_clock();

Retourne le nombre d'interruptions d'horloge depuis le démarrage du noyau.

Voir aussi :

exit - Terminaison normale du processus appelant

void exit(int retval);

Le processus appelant est terminé normalement et la valeur retval est passée à son père quand il appelle waitpid. La fonction exit ne retourne jamais à l'appelant.

Voir aussi :

getpid - Identification du processus appelant

int getpid(void);

La valeur de retour de getpid est le pid du processus appelant cette primitive.

Voir aussi :

getprio - Obtention de la priorité d'un processus

int getprio(int pid);

Si la valeur de pid est invalide, la valeur de retour est strictement négative, sinon elle est égale à la priorité du processus identifié par la valeur pid.

Voir aussi :

kill - Terminaison forcée d'un processus

int kill(int pid);

La primitive kill termine le processus identifié par la valeur pid. Si ce processus était bloqué dans une file d'attente pour un quelconque élément système, alors il en est retiré.

Si la valeur de pid est invalide, la valeur de retour est strictement négative. En cas de succès, la valeur de retour est nulle.

Voir aussi :

pcount - Obtention d'information sur une file de messages

int pcount(int fid, int *count);

La primitive pcount lit la quantité de données et de processus en attente sur la file fid. Si count n'est pas nul, elle y place une valeur négative égale à l'opposé du nombre de processus bloqués sur file vide ou une valeur positive égale à la somme du nombre de messages dans la file et du nombre de processus bloqués sur file pleine.

Si la valeur de fid est invalide, pcount signale l'erreur en retournant un code de retour négatif, sinon 0.

Voir aussi :

pcreate - Création d'une file de messages

int pcreate(int count);

La primitive pcreate alloue une file de capacité égale à la valeur de count. S'il n'y a plus de file disponible ou si la valeur de count est négative ou nulle la valeur de retour de pcreate est strictement négative sinon elle identifie la file qui a été allouée.

Voir aussi :

pdelete - Destruction d'une file de messages

int pdelete(int fid);

pdelete détruit la file de messages identifiée par fid et fait passer dans l'état activable tous les processus, s'il en existe, qui se trouvaient bloqués sur la file. Les processus libérés auront une valeur strictement négative comme retour de psend ou preceive. Les messages se trouvant dans la file sont abandonnés.

Si la valeur de fid est invalide, la valeur de retour pdelete est strictement négative, sinon elle est nulle.

Voir aussi :

preceive - Réception d'un message sur une file

int preceive(int fid,int *message);

La primitive preceive lit et enlève le premier (plus ancien) message de la file fid. Le message lu est placé dans *message si message n'est pas nul, sinon il est oublié.

Lorsque la file était pleine, on la complète immédiatement avec le message du processus bloqué en émission le plus ancien parmi les plus prioritaires, s'il en existe un (processus bloqué). Ce processus devient alors activable ou actif selon sa priorité.

L'obtention du premier message de la file peut nécessiter le passage dans l'état bloqué sur file vide jusqu'à ce qu'un autre processus exécute une primitive psend.

Il est possible également, qu'après avoir été mis dans l'état bloqué sur file vide, le processus soit remis dans l'état activable par un autre processus ayant exécuté preset ou pdelete. Dans ce cas, la valeur de retour de preceive est strictement négative.

Si la valeur de fid est invalide, la valeur de retour de preceive est strictement négative, sinon elle est nulle.

Un processus bloqué sur file vide et dont la priorité est changée par chprio, est considéré comme le dernier processus (le plus jeune) de sa nouvelle priorité.

Voir aussi :

preset - Réinitialisation d'une file de messages

int preset(int fid);

La primitive preset vide la file identifiée par la valeur de fid et fait passer dans l'état activable ou actif (selon les priorités) tous les processus, s'il en existe, se trouvant dans l'état bloqué sur file pleine ou dans l'état bloqué sur file vide (ces processus auront une valeur strictement négative comme valeur de retour de psend ou preceive). Les messages se trouvant dans la file sont abandonnés.

Si la valeur de fid est invalide, la valeur de retour de preset est strictement négative sinon elle est nulle.

Voir aussi :

psend - Envoi d'un message dans une file

int psend(int fid, int message);

La primitive psend envoie le message dans la file identifiée par fid. On distingue trois cas :

  • Si la file est vide et que des processus sont bloqués en attente de message, alors le processus le plus ancien dans la file parmi les plus prioritaires est débloqué et reçoit ce message.
  • Si la file est pleine, le processus appelant passe dans l'état bloqué sur file pleine jusqu'à ce qu'une place soit disponible dans la file pour y mettre le message.
  • Sinon, la file n'est pas pleine et aucun processus n'est bloqué en attente de message. Le message est alors déposé directement dans la file.

Il est possible également, qu'après avoir été mis dans l'état bloqué sur file pleine, le processus soit remis dans l'état activable par un autre processus ayant exécuté preset ou pdelete. Dans ce cas, la valeur de retour de psend est strictement négative.

Si la valeur de fid est invalide, la valeur de retour est négative sinon elle est nulle.

Voir aussi :

start - Démarrage d'un nouveau processus

Pour les étudiants de PCSEA, dans un premier temps, tant que la gestion de la mémoire virtuelle et la distinction kernel/user n'est pas encore opérationnelle, vous pouvez utiliser le prototype sans mémoire virtuelle ci-dessous qui simplifie la vie.

Sans mémoire virtuelle (apprentis 2A) :

int start(int (*pt_func)(void*), unsigned long ssize, int prio, const char *name, void *arg);

La primitive start crée un nouveau processus dans l'état activable ou actif selon la priorité choisie.

  • pt_func est un pointeur sur l'adresse du programme (de la fonction) à lancer dans le processus.
  • La pile du processus est allouée par le noyau dans l'espace utilisateur. Elle doit fournir à la fonction appelée exactement ssize octets utilisables sans compter l'espace nécessaire au stockage de l'adresse de retour, du paramètre et d'autres éléments de votre implantation. Elle sera libérée par le noyau dès la terminaison du processus.
  • La priorité du processus est égale à prio.
  • Le programme associé au processus est désigné par name. Ce nom pourra servir à identifier facilement un processus dans la liste des processus obtenue avec ps par exemple.
  • arg est un argument passé à la fonction ptfunc.

Avec mémoire virtuelle (projet de spécialité 2A) :

int start(const char *name, unsigned long ssize, int prio, void *arg);

La primitive start crée un nouveau processus dans l'état activable ou actif selon la priorité choisie.

  • Le programme associé au processus est désigné par name. Ce nom représente l'application que l'on veut lancer (exactement comme ls représente le nom du programme /usr/bin/ls sur une machine Linux) et permet au noyau de chercher dans sa table d'application (son système de fichiers) le code et les données à charger en mémoire.
  • La pile du processus est allouée par le noyau dans l'espace utilisateur. Elle doit fournir à la fonction appelée exactement ssize octets utilisables sans compter l'espace nécessaire au stockage de l'adresse de retour, du paramètre et d'autres éléments de votre implantation. Elle sera libérée par le noyau dès la terminaison du processus.
  • La priorité du processus est égale à prio.
  • arg est un argument passé au programme. Attention, avec la mémoire virtuelle, il faut bien réfléchir à la signification d'un pointeur dans le contexte d'un processus.

Si les arguments sont incorrects ou s'il n'y a plus de place pour créer un nouveau processus, la valeur de retour est strictement négative sinon c'est l'identifiant du processus. Cet identifiant, Process Identifier (ou PID) est la désignation unique d'un processus. A tout moment il ne peut exister qu'un seul processus pour un PID donné.

Dans les deux cas, il faut passer un paramètre à la fonction qui est lancée comme processus. Pour cela il faut connaître la constitution attendue de la pile pour que lors du lancement du processus, ce dernier aille chercher le paramètre au bon endroit dans la pile. Une explication relativement claire (...) de la manière dont les paramètres sont passés est disponible à cette [url:https://en.wikipedia.org/wiki/X86_calling_conventions#cdecl]. En substance, la pile doit ressembler à ceci :

  |          |
  +----------+
  |   arg    |
  +----------+
  |   exit   |
  +----------+
  | pt_funct |
  +----------+
  |          |

Voir aussi :

wait_clock - Attente temporisée

void wait_clock(unsigned long clock);

Passe le processus dans l'état endormi jusqu'à ce que le nombre d'interruptions horloge passé en paramètre soit atteint ou dépassé.

Voir aussi :

waitpid - Attente et récupération de la valeur de retour d'un fils terminé

int waitpid(int pid, int *retvalp);

Si le paramètre pid est négatif, le processus appelant attend qu'un de ses fils, n'importe lequel, soit terminé et récupère (le cas échéant) sa valeur de retour dans *retvalp, à moins que retvalp soit nul. Cette fonction renvoie une valeur strictement négative si aucun fils n'existe ou sinon le pid de celui dont elle aura récupéré la valeur de retour.

Pour un fils qui a été terminé par kill, la valeur de retour (retvalp) est nulle.

Si le paramètre pid est positif, le processus appelant attend que son fils ayant ce pid soit terminé ou tué et récupère sa valeur de retour dans *retvalp, à moins que retvalp soit nul. Cette fonction échoue et renvoie une valeur strictement négative s'il n'existe pas de processus avec ce pid ou si ce n'est pas un fils du processus appelant. En cas de succès, elle retourne la valeur pid.

Le processus fils terminé n'est définitivement détruit, et enlevé de la liste des fils que lorsque sa valeur de retour a été récupérée, ou que son père est lui-même terminé et ne pourra pas donc jamais récupéré cette valeur.

Voir aussi :

API de partage de mémoire (optionnel pour les apprentis)

L'implémentation de cette API est inhérente au projet requérant la mémoire virtuelle. Elle permet de partager une page entre plusieurs processus qui ne partagent par le même espace mémoire. Il est conseillé d'adopter une approche par reference counting. Cette implémentation va nécessiter que vous fassiez des choix pour répondre aux questions suivantes:

  • À quelle adresse mapper les pages ?
  • Combien de pages peut-on partager par processus ?

shm_create - Création d'une page partagée

void *shm_create(const char *key);

Permet au processus appelant de demander la création d'une page partagée au noyau. La page doit faire 4Ko et est identifiée auprès du noyau à l'aide de la chaine key. Si la page est allouée et mappé, son adresse virtuelle est retournée. En cas d'erreur (key est nulle, la page existe déjà, plus de mémoire), NULL est retourné.

Voir aussi:

shm_acquire - Obtenir une référence page partagée

void *shm_acquire(const char *key);

Cette primitive permet à un processus d'obtenir une référence sur une page partagée connue du noyau sous le nom key. Si la page est disponible, elle est mappée pour ce processus et son adresse est retournée. Sinon, la fonction retourne NULL.

Voir aussi:

shm_release - Relacher une référence page partagée

void shm_release(const char *key);

Informe le noyau que le processus appelant veut relacher la référence sur la page nommée par key. Si un référence a été acquise (par appel à shm_acquire par exemple), la page est démappée et l'adresse virtuelle fournie précédement n'est plus valide, sinon l'appel est sans effet. Quand cet appel amène à relacher la dernière référence sur une page partagée, la page physique correspondante est effectivement libérée.

Voir aussi:

API des sémaphores (optionnel)

scount - valeur du compteur d'un sémaphore

int scount(sem);

La valeur de retour de scount est :

  • -1 si la valeur de sem est invalide,
  • sinon, les 16 bits de poids fort sont à 0, et les 16 bits de poids faible, interprétés comme un entier signé sur 16 bits, sont la valeur du sémaphore.

Voir aussi :

screate - Création et initialisation d'un sémaphore

int screate(short int count);

La primitive screate alloue un sémaphore libre et l'initialise à la valeur count.

S'il n'y a plus de sémaphore disponible, ou si count est négatif, l'appel échoue et la valeur de retour est -1, sinon elle est égale a l'identification du sémaphore qui a été alloué.

Voir aussi :

sdelete - libération d'un sémaphore

int sdelete(int sem);

La primitive sdelete fait passer tous les processus (s'il y en a) de l'état bloqué sur sémaphore identifié par sem, à l'état activable, et rend invalide comme identification de sémaphore la valeur sem.

Si la valeur de sem est invalide, la valeur de retour de sdelete est -1, sinon elle est nulle.

Voir aussi :

sreset - reset d'un sémaphore

int sreset(sem, count);

La primitive "sreset" fait passer, s’il en existe, tous les processus se trouvant dans l’état bloqué sur le sémaphore identifié par "sem" à l’état activable et associe la valeur de "count" à ce sémaphore.

Si la valeur de "sem" est invalide ou si la valeur de count est négative, la fonction échoue et la valeur de retour est -1, sinon elle est nulle.

Voir aussi :

signal/signaln - V et V multiples sur un sémaphore

int signal(int sem);
int signaln(int sem, short int count);

La primitive signal incrémente de 1 la valeur du sémaphore identifié par sem et si la valeur après incrémentation est négative ou nulle, le premier processus se trouvant dans l'état bloqué dans la file d'attente du sémaphore passe dans l'état activable ou actif.

La primitive signaln est équivalente à count primitives signal exécutées de manière atomique, i.e. sans qu'un autre processus puisse s'exécuter entre deux appel à signal.

Dans les deux cas, si l'opération doit provoquer un dépassement de capacité du compteur, alors elle n'est pas effectuée.

La valeur de retour de signal/signaln est -1 si la valeur de sem est invalide, -2 en cas de dépassement de capacité et nulle sinon.

Voir aussi :

try_wait - P non bloquant sur un sémaphore

int try wait(int sem);

La primitive try_wait teste la valeur du sémaphore. Si la valeur est supérieure strictement à 0, alors la primitive décrémente de 1 la valeur du sémaphore identifié par sem. Si la valeur avant décrémentation est négative ou nulle, une erreur est retournée pour indiquer que l'opération P ne peut être appelée sans bloquer le processus appelant. Enfin, si l'opération doit provoquer un dépassement de capacité du compteur, alors elle n'est pas effectuée.

La valeur de retour de try_wait est -1 si la valeur de sem est invalide, -3 si le compteur est négatif ou nul, -2 en cas de dépassement de capacité, et nulle sinon.

Voir aussi :

wait - P sur un sémaphore

int wait(int sem);

La primitive wait décrémente de 1 la valeur du sémaphore identifié par sem. Si l'opération doit provoquer un dépassement de capacité du compteur, alors elle n'est pas effectuée. Sinon, si la valeur après décrémentation est strictement négative, le processus passe de l'état actif à l'état bloqué sur le sémaphore identifié par la valeur sem. Ce processus pourra repasser dans l'état activable ou actif lorsqu'un autre processus exécutera une primitive signal/signaln qui le libèrera, ou les primitives sreset ou sdelete.

La valeur de retour de wait est -1 si la valeur de sem est invalide, -2 en cas de dépassement de capacité, -3 si le réveil est consécutif à sdelete, -4 s'il est consécutif à sreset, nulle sinon.

Pour aller plus loin

Les possibilités d'extension du système sont très nombreuses. Nous en citons ici quelques unes :

  • implémenter les sémaphores.
  • interfacer votre système avec le système de fichiers en mémoire qui vous est fourni ou en réimplanter un.
  • mettre au point un chargement dynamique de programmes depuis un système de fichiers. Il faudra alors définir des règles d'allocation d'espace dans la mémoire utilisateur pour les programmes.
  • implanter ou améliorer le mécanisme d'adressage virtuelle pour:
    • mettre en oeuvre des processus lourds (si la mémoire virtuelle n'est pas obligatoire dans le projet)
    • réaliser du lazy-loading: n'allouer la mémoire physique que quand le processus l'accède réellement par traitement des fautes de pages
    • implémenter des threads (ou processus légers)
  • contrôler par gestion de faute de page la validité des zones mémoires passées en paramètre aux appels système.
  • implanter un mécanisme de signaux asynchrones à la Unix.
  • mettre en oeuvre plusieurs consoles virtuelles sur le système. Des processus différents pourraient alors utiliser chacun leur console.