Projet système PC : 2014 - CADIC Étienne, MARITAZ Jérémy, CRAIPEAU Alexis

De Ensiwiki
Aller à : navigation, rechercher
[[Fichier:]]
Titre du projet PotatOS
Cadre Projet Système d'Exploitation 2014
Page principale Projet_système

Équipe Étienne Cadic Jérémy Maritaz Alexis Craipeau
Encadrants Damien Dejean Gaëtan Morin Grégory Mounié,


Présentation générale

Bienvenue sur la page wiki de notre projet Système d'exploitation. Vous trouverez ici non seulement des informations sur les spécificités de notre système, mais aussi la manière dont le projet s'est déroulé, et quelques informations supplémentaires destinées à vous aider à passer le mode user, si vous en êtes actuellement à zoner sur la page wiki des anciens en quête d'une aide désespérée !

Objectifs

L'objectif de ce projet était d'écrire une ébauche de système d'exploitation respectant les normes de protection traditionnelles. On sous-entend par-là un système d'exploitation gérant le cycle de vie des processus, leur ordonnancement, et une manière d'offrir à l'utilisateur du système, la possibilité d'écrire des applications "inoffensives". Comme le système d'exploitation a accès à des zones critiques de la mémoire, il faut trouver une manière de "museler" les processus, en leur offrant un certain niveau de permission. Par convention, les systèmes d'exploitation disposent de 4 niveaux de protection appelés protection rings (kernel = 0, usermode = 3), chacun ayant des permissions de plus en plus étendues à mesure qu'on se rapproche du niveau 0.

Cahier des charges

Les spécifications précises du projet peuvent être consultées sur cette page : Projet système : spécification.

Conduite du projet

Dans cette partie nous détaillons les différentes étapes du déroulement du projet.

Git

Notre projet était développé avec le gestionnaire de versions GIT. Pour toute la première partie du projet nous avons avancé séparément sur trois branches différentes, pour nous familiariser avec l'environnement de travail et être sûrs d'avoir tous le même niveau de compréhension du projet. À partir de la séance 3, nous avons réuni le code des 3 branches en essayant de garder le meilleur code de chaque partie.

Diagramme prévisionnel

Voici les différentes étapes que nous avons planifié pour mener à bien le projet. On peut noter que les estimations sont sans prétentions, et destinées à terminer le projet dans les temps, sans extensions, car nous n'avions pas les ressources humaines pour envisager plus gros.

Planning prev systeme.png

Diagramme effectif

Voici le diagramme effectif.


Planning effectif.png

Réalisation

Processus

Pour représenter les différents états des processus, on a choisi d'utiliser un type ENUM qui nous permet d'avoir très rapidement l'information sur l'état dans lequel le processus se trouve. Pour implémenter ces différents états et le cycle de vie des processus, on a mis en place des files FIFO et avec priorité selon le contexte. Des primitives de création de files sont fournies avec le dépôt initial du projet, que nous avons largement re-utilisé.

La spécificité de ces primitives est qu'on doit rajouter un champs "link" à la structure Processus pour les lier entre eux. Cette particularité apporte un élément intéressant : utiliser un seul champ link pour toutes les files apporte une garantie que le processus ciblé est toujours dans un état cohérent, ce qui a rendu le débogage plus efficace.

En effet, les seuls états où un processus n'est pas dans une file sont : ACTIF et ZOMBIE.

Comme la table des processus est statique, (le nombre de processus max est fixé à la compilation du noyau), la seule chose que l'on réalise vraiment dans l'ordonnancement est de changer la manière dont les processus sont liés entre eux en les changeant de files.

Le schéma suivant illustre bien cet état statique de la table, et de la dynamique des files de processus en fonction de leur état.

Ordonnance - New Page.png

Ordonnanceur

Notre ordonnanceur fonctionne de manière un peu particulière. On a en effet deux manières de changer de contextes entre processus. Soit on est dans une situation où le processeur souhaite mettre en pause un processus dans le but d'en exécuter un suivant, soit on souhaite terminer un processus et laisser la main au processus suivant activable.

On a donc deux fonctions void ordonnance(void) et void laisser_main(void) appelant toutes les deux le contexte_switch. Ceci permet notamment de dissocier le réveil de processus d'une simple terminaison, et d'être sûr que le réveil n'apparaît que lors du quantum de temps suivant.

Filiation

La filiation de processus est réalisée en liant les processus fils entre eux par une liste doublement chaînée dont la tête est contenue dans la structure du processus père. Chaque processus connaît aussi son père. Pour finir, pour des problématiques de synchronisations entre père et fils, un champs pid_bloquant a été rajouté pour que le système d'exploitation puisse savoir sur quel fils le père s'est bloqué (si le fils n'avait pas encore fini son exécution). De ce fait, lorsqu'un processus se finit, il peut vérifier si son père était en train de l'attendre et le réveiller.

C'est toujours le père qui finit les processus fils, à part si celui-ci est tué avant.

Endormissement

Pour gérer l'endormissement de processus, une file de priorité de processus endormis a été ajoutée, leur priorité de réveil étant l'opposé de leur heure de réveil (un plus haut nombre pour la priorité est synonyme de processus plus prioritaire). De ce fait, les processus sont triés dans la file, le processus devant se réveiller le plus tôt sera donc au sommet de la file, ce qui permet un réveil peu coûteux en temps. La structure d'un processus contient donc un champs qui correspond à son heure de réveil, que l'on fixe au moment de l'endormissement.

Reveil - New Page.png

Terminaison

La terminaison des processus est réalisé par l'appel système exit lors du retour de la fonction principale exécutée par le processus. Pour le mode user, comme on ne peut pas initialiser une quelconque fonction de terminaison alors qu'on est en mode kernel, et que le code kernel et user sont séparés, il a fallu placer la fonction de terminaison dans le crt0 du mode user, et placer en dur cette adresse lors de l'initialisation de la pile user d'un processus. Cette fonction de terminaison réalise la même action que l'appel système de la fonction exit dans syscalls.S.

Libération de mémoire

Lorsqu'un processus se termine, il faut libérer la mémoire attribuée à ses piles user et kernel lors de sa création. Cependant, il est impossible de libérer la pile d'exécution d'un processus alors qu'il est encore ACTIF. Il fallait donc le faire plus tard, et trouver un moyen pour que le système puisse savoir qu'un processus est dans un état instable, à savoir qu'il a été détruit, mais que la mémoire attribuée à ses piles n'a pas encore été libéré.

Nous avons opté pour un champ supplémentaire "dirty" passé à 1 si le processus est dans cet état instable, et 0 sinon.

Lorsqu'on repasse à idle, comme on a rien de mieux à faire on parcourt la table des processus pour voir si certains ont été libérés, et lors d'un start, on vérifie que l'emplacement du processus ne contient pas une pile encore allouée (si tel est le cas, on libère d'abord les piles avant de l'allouer de nouveau).

Sémaphores

La structure d'un sémaphore est la suivante : < SID, compteur, (lien) en_attente, (lien) sem_link, (flag) deleted >.

Le lien "en_attente" permet de lier des processus à un sémaphore. Cela permet de connaître tous les processus qui sont bloqués par un sémaphore et de faire des actions d'ajout, de suppression et de parcours avec une bonne complexité. Le lien "sem_link" a été créé a posteriori pour améliorer la performance algorithmique de recherche d'un sémaphore libre. Tous les sémaphores, de la même façon que les processus, sont stockés statiquement dans une table de sémaphores. Voici les deux façons de gérer les sémaphores (création, suppression) :

     1  - Ancien algorithme : Initialement, tous les sémaphores ont un SID à -1. Pour chercher un sémaphore libre, on parcourt la table jusqu'à trouver 
la première case avec un sémaphore dont le SID vaut -1. On attribue ensuite la valeur de l'index de la table au SID et on initialise le compteur.
Pour la suppression, on libère les processus chaînés sur "en_attente" et on passe le SID à -1.
     2  - Algorithme performant : Les sémaphores sont placés dans la table avec des SID de la valeur des index. Tous les sémaphores ont le flag "deleted" 
à 1, ce qui signifie que le sémaphore n'est pas actif. De plus, tous les sémaphores sont chaînés sur "sem_link". Ainsi, si on désire créer un sémaphore,
on parcours la liste chaînée "sem_link" et non plus la table. On aura donc, dès le premier élément, un sémaphore libre. On lui attribut dont la valeur
voulue pour son compteur et son SID reste son index dans le tableau. On le retire ensuite de la liste "sem_link" et on passe le flag "deleted" à 0.
Dans cet algorithme, le flag "deleted" a pour intérêt de pouvoir tester ponctuellement si un sémaphore de SID = i existe ou pas (sans avoir à parcourir
toute la liste "sem_link" ou la table des sémaphores).

Pour comprendre le lien entre les processus et le sémaphore, cf ci-dessus le schéma des processus.

Mode User

Voici un schéma illustrant le traitant du mode user : Ordonnancement - New Page.png

Difficulté rencontrée

La plus grande difficulté de ce projet est de comprendre et implémenter le mode utilisateur. Il ne faut pas négliger l'importance de cette partie tout en gardant à l'esprit que toute la partie clavier et gestion de la console sont à intégrer ensuite dans ce nouveau mode.