Projet système PC : 2016 - Jérôme BARBIER, Jérémy LASCAUX, Florent TONNEAU

De Ensiwiki
Aller à : navigation, rechercher
GOOSE (GOOSE is Only an Operating System for Ensimag)

Goose logo.png auteur de l'image

Développeurs BARBIER Jérôme
LASCAUX Jérémy
TONNEAU Florent

Présentation

Objectifs

L'objectif de ce projet est de réaliser un système d'exploitation basique permettant à un utilisateur d'interagir pour lancer des processus, taper du texte... En fournissant aux développeurs des primitives systèmes pour manipuler des files de messages, créer des processus, interagir avec l'écran/le clavier...

Le système doit être prévu pour fonctionner sur une architecture x86 en 32bits d'origine Intel (le processeur est un processeur mono-coeur de la famille Pentium).

Cahier des charges

Le cahier des charges du projet est disponible sur le wiki à cette adresse : Projet système : spécification. Il s'agit d'un cahier des charges destiné à nous aiguiller le plus efficacement possible. Pour cela, il découpe le projet en 7 phases permettant d'ajouter de façon incrémentale des fonctionnalités au système. Les premières phases sont très guidées et les suivantes laissent davantage de place à la prise d'initiative. Le wiki fournit également des ressources complémentaires utiles à la compréhension du fonctionnement d'un système d'exploitation.

Galerie

Quelques captures d'écran du système, avec dans l'ordre :

  • L'écran après avoir booté
  • L'écran quand on tappe la commande "help"
  • L'écran quand on tappe la commande "ps" (après avoir lancé des processus avec "queue_demo"
  • L'écran affiché par le jeu de morpion quand il démarre (commande "morpion")
  • L'interpréteur de uBasic

Projet systeme jeromeb jeremyl florentt screenshot1.jpg Projet systeme jeromeb jeremyl florentt screenshot2.jpg

Projet systeme jeromeb jeremyl florentt screenshot3.jpg Projet systeme jeromeb jeremyl florentt screenshot4.jpg

Projet systeme jeromeb jeremyl florentt screenshot5.jpg

Gestion de projet

Organisation

Le projet a été organisé via la mise en place d'un trello pour l'organisation du travail, et d'un dépôt GIT pour la coopération au niveau du développement.

Afin d'assurer la lisibilité du code, ce dernier a été soumis à GNU/indent, un logiciel permettant de définir des règles de mise en forme pour le langage C. Nous avons décidé d'adopter les règles de style de GNU.

La documentation étant essentielle à tout projet nous avons choisi de nous y consacrer dès le début de ce projet. Pour cela, l'outil Doxygen a été d'une aide précieuse.

Ainsi, pour chaque phase, nous avons commencé par rechercher un découpage en tâches les plus indépendantes possibles de ce qui nous était demandé, et chacun d'entre nous s'est ensuite lancé sur une tâche. A la fin de chaque tâche, nous nous sommes imposés l'écriture de tests et le lancement, à minima, de tous les tests précédemment écrits pour valider que les changements opérés dans le code par la réalisation de la tâche ne provoquaient pas de régression sur le reste du code. Une fois cette validation faite, le code pouvait être poussé sur le dépôt GIT, et on pouvait passer à la tâche suivante.

Le système de lancement des tests fonctionne comme suit

  • On compile le système en mode test, en lui spécifiant quel test doit être inclut : make clean && make test=<NOM_DU_TEST>
  • On lance Qemu et on regarde la sortie de l'écran

Les fichiers codant les tests se trouvent dans kernel/tests et dans user/tests.

Des phases 1 à 4, les tests ne sont plus exécutables car ils étaient prévus pour fonctionner sur une seule pile, sans changement de droit d'exécution. Les changements induits par la phase 5 ont été trop profonds pour garder la rétro-compatibilité de ces tests. Il est par conséquent uniquement possible de lancer les tests contenus dans le dossier user/tests.

Pour lancer les tests fournis avec les sources du projet (mis à jour avec le nouveau test 19), il faut compiler le test "profs" : make clean && make test=profs.

Note : faire make clean est important dans le sens où en mode de test, le code classique du kernel (coté user) qui lance notamment le shell est remplacé par le code de test. Cela garanti que les tests sont exécutés dans les conditions de fonctionnement normales du système, juste après le boot et les diverses initialisations qu'il réalise.

Planning prévisionnel

Aucun planning prévisionnel n'a été mis en place. Cependant, dans le but de quand même réussir à mener à bien le projet, il a été décidé qu'une phase ne devait pas durer plus de trois jours.

Si jamais ce cas de figure devait arriver, alors au moins un des membres du groupe devait commencer à préparer la phase suivante pendant que les deux autres continuaient sur la phase bloquante, dans le but de toujours progresser.

Planning réalisé

Voici un diagramme de Gantt montrant le déroulement de la réalisation des principales phases du projet :

Diagramme de Gantt du déroulement du projet

Quelques autres informations :

  • Les sémaphores ont été implémentés en même temps que la phase 6
  • L'interpréteur uBasic a été ajouté en même temps que la phase 7
  • Le jeu du morpion a été ajouté en même temps que la phase 7

Utilitaires projet

  • Git hébergé sur une instance Gitlab
  • Framateam pour communiquer sur le projet le week-end et le soir :)
  • Trello liste des tâches à faire
  • Google doc pour partager les documents importants
  • Microsoft Visio pour réaliser les diagrammes
  • GNU/Indent pour la mise en forme du code source C
  • GDB pour débogger le code
  • Doxygen pour réaliser la documentation
  • Geany, Gedit et GNU/Emacs pour coder

Conseils

Dans la suite de cette page, nous avons ajouté divers conseils qu'il nous semblaient intéressant de donner, sous la forme d'encarts.

Compiler sur son ordinateur personnel
Si vous utilisez votre ordinateur personnel pour le projet, il se peut que vous ayez une version de GCC qui soit plus récente que celle des machines de l'ENSIMAG. Par défaut, GCC ne compile plus pour être compatible avec les anciennes versions des Pentium d'Intel et il se peut que vous rencontriez l'erreur 6 lors de l'exécution de votre code. Il s'agit d'une exception lancée par le processeur pour vous avertir que vous avez essayé d'exécuter un opcode invalide et cela arrive parce que GCC n'a pas compilé votre code pour être compatible avec l'ancien Pentium émulé par Qemu.

Pour régler ce problème, il faut éditer les deux Makefile de sorte à demander à GCC de compiler pour le bon processeur :

  • Pour le Makefile kernel : Ajouter -march=pentium à la variable CFLAGS
  • Pour le Makefile user : Ajouter -march=pentium à la variable KFLAGS

Quelques sites qui vont pouvoir vous aider tout au long de votre projet :

  • OS Dev - Exceptions : Pour comprendre ce que veut dire le code-erreur que votre CPU vous indique quand une exception se produit
  • Manuel Intel pour les développeurs : Il est donné dans les documents utiles du projet et peut vous aider à comprendre les mécanismes de changement de piles (pour la phase 5)

Etat du projet

Phase 1 - Affichage à l'écran

100 %

Le but de cette phase est de réaliser l'affichage à l'écran de caractères, il s'agit en grande partie de repartir d'un cours que nous avons eu l'année dernière en guise d'introduction aux systèmes d'exploitation.

Cette phase n'a donc pas posé de difficulté particulière.

Phase 2 - Gestion des processus, changement de contexte

100 %

Cette phase consiste à appréhender le concept de processus. Il s'agit de créer les structures de données et les systèmes permettant d'exécuter des fonctions en partageant leur temps d'exécution. Il faut donc pour cela y ajouter un système de changement de contexte couplé à une stratégie de découpage du temps de calcul (qui arrivera en phase 3, mais il vaut pieux préparer un peu le terrain avant) : l'ordonnanceur.

La seule difficulté de cette phase est de faire en sorte que les interruptions générées par l'horloge matérielle soient bien réceptionnées et que le changement de contexte qu'elles provoquent se déroule bien.

Gérer les processus
Il y plusieurs stratégies pour démarrer un processus. Afin de rendre votre code le plus débuggable possible si vous ne maîtrisez pas le C à la perfection, nous vous recommandons de créer une table de processus allouée dans le tas (donc rien de dynamique, y compris la pile !). C'est en effet plus simple de débugger avec GDB une structure statique qu'une structure pointée.

Cela aura aussi par la suite, quand vous devrez gérer la terminaison, l'avantage de vous éviter de vous poser la question de la dés-allocation.

Phase 3 - Ordonnancement, cycle de vie d'un processus, filiation

100 %

Le but de cette phase est de réaliser le système gérant la stratégie de changement de contexte à chaque interruption de l'horloge : l'ordonnanceur. La stratégie à adopter est largement détaillée dans le wiki et la difficulté réside dans l'interfaçage entre l'ordonnanceur et le travail réalisé en Phase 2. Elle n'est cependant pas excessive et est largement parallélisable.

De plus, c'est à ce moment que des comportements cruciaux (et intéressants) des processus sont à mettre en place : la filiation pour pouvoir retracer la vie d'un processus (et fournir l'appel système waitpid par exemple), et surtout la terminaison (soit naturelle, soit via les appels systèmes exit et kill) qui a un impact significatif sur l’ordonnanceur (il serait bête que l'ordonnanceur par exemple repasse la main à un processus mort !).

Pour résumer le fonctionnement de notre système, voici en détail le cycle de vie d'un processus :

Cycle de vie d'un processus en fonctionnement "normal"

Pour les choix d'implémentation de ce cycle de vie, il a été tenu compte des pré-requis de l'ordonnancement (à savoir qu'un processus avec la plus haute priorité est systématiquement et dès que possible le processus actif (état ACTIVE)), des spécifications (qui précisent qu'un processus doit avoir pour états actif, activable, bloqué sur I/O, bloqué sur sémaphore, bloqué sur attente d'un fils, endormi et zombie) et des contraintes du système (on ne peut pas désallouer le processus courant, d'où l'ajout d'un état intermédiaire, DEAD).

Il est à noter que le présent schéma ne représente pas les cas particuliers (par exemple quand un processus en tue un autre; cet autre passe de ACTIVABLE ou ASLEEP vers ZOMBIE ou DEAD).

Le modèle présenté a selon nous plusieurs avantages :

  • Il n'y a que 5 états possibles, dont un intermédiaire (DEAD) et un dont on doit préciser la raison (ASLEEP), ce qui facilite la compréhension du fonctionnement
  • L'état intermédiaire permet une dés-allocation des processus morts sans utilisation d'un système de ramasse-miettes, ce qui a pour conséquence de ne pas gâcher une plage de temps de calcul juste pour faire une désallocation et d'ajouter un processus supplémentaire pour faire la-dite dés-allocation
  • L'ordonnanceur peut se permettre de ne considérer que les processus dans l'état ACTIVABLE pour faire son travail, ce qui limite les erreurs lors du développement et de la maintenance.
Terminer un processus
Terminer un processus n'est pas une tâche aussi évidente qu'il n'y parait. Il faut tout d'abord détecter que la fonction que l'on veut exécuter a fini son travail (la définition même de la fin d'une tâche). Il y a plusieurs stratégies pour ça et si vous êtes un peu en avance sur les appels systèmes, il y en a une qui peut vous faire gagner beaucoup de temps (elle utilise exit).

Une fois que c'est fait, si vous travaillez en allocation dynamique de pile et/ou de processus (ce qui n'est pas forcément le bon choix, sauf si vous savez vraiment ce que vous faîtes), se pose la question de la dés-allocation. Comment désallouer le processus dont la pile est la pile dans laquelle on est en train de s'exécuter ? La seule solution à cette question est de faire en sorte que ce soit un autre processus qui fasse la dés-allocation. Reste à savoir selon quelle stratégie (le moteur de recherche de l'Ensiwiki est pour cela votre ami).

Phase 4 - Files de message, endormissement

100 %

Le but de cette phase est de réaliser un système d'exclusion mutuelle, les files de messages fonctionnant un peu comme les channels du langage Go. Il faut également pour cela réaliser un système permettant de mettre en attente des processus, il s'agit de l'endormissement.

En fait, les files de messages sont un système de synchronisation résolvant par implémentation d'elle-même le problème classique du producteur-consommateur : Un processus producteur vient déposer un message dans une file et un autre, le consommateur le lire. On peut déposer un nombre fini de messages, par exemple n. Si un processus veut déposer un message et que le nombre de messages dans la file est de n, alors le processus doit attendre qu'un autre processus consommateur vienne en retirer un avant de pouvoir déposer le sien. L'inverse est également possible : un consommateur voulant prendre un message dans une file vide doit attendre qu'un producteur vienne en déposer un.

Dans le système, le mécanisme de dépose et de récupération de message est couplé à l'ordonnanceur.

Cette phase n'a pas posé de problème particulier. Cependant, nous nous sommes aperçus que l'implémentation que nous avions proposée ne correspondait pas à celle qui était attendue du fait que les spécifications données pour le projet pouvaient être interprétées de plusieurs façons, elles ont depuis été corrigées.

Phase 5 - Mode utilisateur

100 %

Cette phase est la phase critique du projet : Il s'agit de passer d'un mode de fonctionnement jusque là en ring0 à un mode de fonctionnement partagé entre ring0 et ring3. En termes moins techniques, jusque là nous avions un système fonctionnant avec le plus haut niveau de permissions possible. Cette phase consiste à isoler les applications du cœur du système et donc de les exécuter avec le moins de permissions possibles.

Il s'agit d'une phase très critique car elle implique diverses modifications : les processus fonctionnent maintenant avec deux piles au lieu d'une seule et il faut être capable de sauter d'une pile à l'autre quand c'est nécessaire (un appel système ou une interruption s'effectuent via la pile système, et le reste du temps, on utilise la pile utilisateur).

Cette phase nous a posé moins de problèmes que ce que nous appréhendions, notamment à cause d'une analyse préalable plutôt efficace. Les problèmes auxquels nous avons été confrontés ont davantage été d'ordre techniques (comment s'assurer qu'un saut a bien été fait, comment lancer le processus spécifique idle qui s'assure que le système ne s'arrête pas...).

A partir de cette phase, le système de test a dû être mis à jour puisque les processus s'exécutent maintenant coté utilisateur. Les tests associés aux phases 1, 2, 3 et 4 ne sont donc plus fonctionnels. Ce n'est par contre pas un défaut dans le sens où la plupart des appels systèmes réalisés jusque là n'évolueront plus (nous sommes donc assurés de rester sur des codes qui fonctionnent).

Mais que ce passe-t-il ici ?
La phase 5 n'est pas, en termes de quantité de code, la plus grosse à réaliser. Cependant, si l'on parle en termes de réflexion, elle surpasse d'assez loin toutes les autres phases. Du coup, avant de vous lancer dans le code, n'hésitez pas à prendre du temps à parcourir le Wiki (la documentation fournie par les professeurs ou les conseils dans les projets précédents) afin de bien cerner le problème.

Ce qu'il faut voir dans cette phase, c'est que jusque là, vous exécutiez votre code en ring0, c'est à dire en mode superviseur avec tous les droits possibles. Maintenant, il va falloir passer en ring3, le coté "utilisateur" pour exécuter de façon plus sécurisée du code (en fait cela empêche le processeur d'exécuter certaines instructions comme inb, hlt...).

Pour information, les ring1 et ring2 sont définis par Intel comme étant des niveaux de protection destinés aux pilotes ("drivers").

Le problème, c'est qu'il n'existe pas de façon de dire explicitement au processeur de passer en mode utilisateur. Du coup, il va falloir le tromper et lui faire croire qu'il l'a déjà été à un moment pour qu'il puisse y revenir (vous allez trouver dans la documentation qu'il faut utiliser l'instruction iret, c'est elle qui va permettre ce passage).

Le wiki OS Dev propose une page d'information sur pourquoi/comment changer de niveau utilisateur.

Pour vous aider à débugger cette étape, nous vous conseillons de regarder les valeurs des registres esp, eip et cs (soit avec GDB, soit avec un écran bleu) :

  • cs va vous indiquer si vous êtes bien passé en mode utilisateur
  • eip (le compteur ordinal) vous indique le n° de ligne de code que vous exécutez actuellement
  • esp vous indique le sommet de votre pile, s'il évolue, c'est que vous avez exécuté du code (il reste à voir si c'est le bon)

Phase 6 - Pilote de clavier

100 %

Cette phase de gestion du clavier n'a pas été particulièrement difficile à implémenter surtout pour avoir seulement une réception des caractères tapés au clavier. En effet, la gestion d'une interruption clavier n'est pas très différente des interruptions précédemment gérées.

On notera dans cette phase, qu'il faut bien avoir fini la phase 5 et donc avoir supprimé tous les sti()/cli() du code pour qu'il n'y ai pas de problème d'interférence entre les différents appels systèmes et que la phase 4 ai été bien déboguée auparavant pour ne pas avoir de problème de gestion des caractères/processus dans les files de messages.

Phase 7 - Shell

100 %

Le but de cette phase est d'intégrer un processus faisant office d'interpréteur de commande. Ce processus devant bien entendu être un processus utilisateur, faisant des appels systèmes (au moins des appels à start pour lancer de nouveau processus).

Toute la difficulté de cette phase a été de faire en sorte que la commande soit interprêtée pour lancer correctement le bon processus. La gestion des priorités entre shell et processus lancés a aussi été un sujet de discussion.

Voici la liste des commandes supportées par notre shell :

Commande Utilité
ps Permet de lister tous les processus en cours, leurs noms, leurs statuts...
getprio <PID> Retourne la priorité d'un processus
chprio <PID> <NOUVELLE PRIORITE> Change la priorité d'un processus
kill <PID> Tue un processus, peu importe son état
qinfo [<FID>] Affiche des informations sur les files de messages, si un identifiant de file est fourni, alors affiche des informations sur la file associée à l'identifiant uniquement
sinfo [<SID>] Affiche des informations sur les sémaphores, si un identifiant de sémaphore est fourni, alors affiche des informations sur le sémaphore associé à l'identifiant uniquement
echo <on,off> Ative ou désactive l'affichage en echo de ce qui est tappé au clavier
exit Quitte le noyau et redémarre le système
morpion Lance un jeu de morpion
ubasic Lance l'interpréteur de uBasic. Le code source de uBasic sous licence BSD est disponible sur Github, et son auteur est Adam Dunkels
queue_demo Lance une démontration de l'usage des files de messages avec deux processus qui discutent pendant quelques secondes
ubasic_demo Lance une démonstration de l'usage de l'interpréteur de uBasic intégré

Extensions

Horloge calendaire

100 %

La gestion de l'horloge calendaire fut la première extension que nous avons faite. Son implémentation est assez simple et permet à notre système d'afficher la date et l'heure courante. La documentation se trouve à cette page RTC.

Sémaphores

100 %

L'ajout du support des sémaphores (informations sur Wikipédia) est optionnel dans le projet, cependant, nous avons décidé de le faire dans le but de proposer une alternative aux files de messages, qui elles sont requises.

L'implémentation des sémaphores proposée dans notre système correspond aux pré-requis des spécifications. Un jeu de tests est fourni coté utilisateur pour vérifier leur bon fonctionnement (vous pouvez le compiler via la commande "make test=semaphore").

Les primitives suivantes sont supportées (le mot-clé sid désigne un identificateur de sémaphore) :

Appel système Utilité
screate(<taille>) Crée un sémaphore de taille <taille>, pouvant donc laisser passer <taille> processus avant de bloquer
sdelete(<sid>) Détruit le sémaphore n°<sid>
wait(<sid>) Laisse passer le processus faisant l'appel si le sémaphore dispose de place disponible, sinon le bloque jusqu'à ce qu'une place se libère
signal(<sid>) Libère une place dans le sémaphore
signaln(<sid>, <n>) Libère <n> places dans le sémaphore
sreset(<sid>, <n>) Réinitialise le sémaphore en forçant le nombre de places disponibles dedans à <n>
try_wait(<sid>) Teste si de l'appel à wait() va résulter un blockage et si c'est le cas, n'appelle pas wait(), sinon procède à l'appel
Economiser du temps sur la réalisation des Sémaphores
Le sémaphore est une version simplifiée de la file de message, du coup, si vous avez déjà réalisé la file de messages, vous pouvez baser vos sémaphores dessus.

Notez cependant que procéder de la sorte peut vous pousser à mettre en place un système assez lourd, à vous de voir donc si vous préférez économiser du temps ou faire quelque chose de léger !

Interpréteur uBasic

80 %

Dans le même esprit que Bash pour GNU/Linux, nous avons voulu intégrer à notre système un mini langage embarqué. Au départ, notre choix s'est tourné vers le langage GNU Guile. Mais voyant l'immense travail pour l'interfacer à notre système et le peu de temps restants nous avons revu nos choix. Finalement le langage choisi a été uBasic. Nous en avons trouvé une implémentation minimaliste écrite en C disponible ici. L'intégration s'est faite prestement (seule la fonction atoi manquait à l'appel). Afin que l'on puisse interagir avec ce langage nous avons écrit une interface en ligne de commande. Cela permet de taper du code qui va ensuite être interprété par l'interpréteur uBasic. Les instructions importantes disponibles sont les suivantes :

Instruction Utilité
let Pour l'affectation des variables
for, next, to Utile pour les boucles
if, then, else Les conditions
rem Utile pour commenter le code
goto Instruction indispensable en Basic
print Pour afficher un joli message, et débogger quand on ne sait pas se servir de GDB :)
end Pour terminer son super programme

Système de fichier

10 %

Un petit système de fichier en mémoire a commencé à être développé, mais par manque de temps, a été abandonné.

L'idée était de stocker en mémoire une arborescence composée de fichiers et de dossiers, sans ré-implémenter un système complexe comme FAT et ses autres versions, mais en permettant tout de même de coder des programmes en basic (pour les utiliser avec l'interpréteur) dans des fichiers.

Il s'agissait également d'implémenter les commandes ps, sinfo et qinfo de la façon dont GNU/Linux peut le faire : avec des fichiers virtuels générés à la volée, diminuant donc le temps de blocage dû aux appels systèmes puisque le temps de traitement, contrairement à ce qui est fait actuellement, aurait été assumé par la partie utilisateur du système.

Les prémisses de ce système de fichiers ne sont pas disponibles sur la branche principale du projet, mais sont néanmoins disponibles sur une branche séparée dans le dépôt GIT.

Conclusion

Apports du projet

Au cours de ce projet, nous avons pu découvrir la conception d'un système d'exploitation. Durant ces 3 semaines intensives, nous avons mobilisé toutes les notions vues en cours de système d'exploitation et en logiciel de base (en première année). Le projet système a été un projet très enrichissant dans le sens où il a permis de pousser les concepts vus en cours jusqu'à l'implémentation, permettant de bien comprendre comment les différents mécanismes entrant en jeu dans un système d'exploitation interagissent entre eux. La quantité de travail à réaliser fut bien dosée, et le fait d'être en trinôme s'y prêtait à merveille. Nous avons eu, certes, quelques difficultés mais rien d'insurmontable cependant. Nous avons eu le temps de réaliser quelques extensions, mais malheureusement nous n'avons pas pu tout terminer dans le temps imparti (notamment l'intégration d'un système de fichiers et d'un Readline maison pour la gestion de la ligne de commande). Cela fut très enrichissant tant sur plan technique qu'humain, nous en garderons de bons souvenirs !