Dans le cadre de la réalisation d'une tâche par plusieurs processus, il existe des relations qui fixent leur déroulement dans le temps. L'ensemble de ces relations est généralement désigné par le terme de synchronisation.
Le problème de la synchronisation consiste donc à définir un mécanisme permettant à un processus actif :
- d'en bloquer un autre ou de se bloquer lui-même en attendant un signal d'un autre processus,
- d'activer un autre processus en lui transmettant éventuellement de l'information.
Deux techniques sont envisageables pour résoudre ce problème de synchronisation :
- l'action directe qui consiste pour un processus à agir sur un autre processus en le désignant par son identité. On utilise généralement deux primitives ayant pour argument l'identité du processus à bloquer ou à activer.
La synchronisation par sémaphore privés est un mécanisme d'action indirecte. Un sémaphore s est un sémaphore privé d'un processus p, si seul ce processus peut exécuter l'opération P(s) ; les autres processus pouvant agir sur le sémaphore s uniquement par l'opération V(s).
La synchronisation par sémaphore privé pose alors comme principe qu'un signal d'activation sera envoyé par la primitive V, et attendu par la primitive P. Ainsi un processus, dont l'évolution dépend de l'émission d'un signal par un autre processus, se bloque, au moyen d'une primitive P, derrière son sémaphore privé initialisé à zéro. Le signal de réveil de ce processus bloqué est obtenu en faisant exécuter par un autre processus une opération V sur le même sémaphore.
Par exemple, soit p un processus dont l'évolution dépend de l'émission d'un signal envoyé par un processus q : en introduisant le sémaphore signal initialisé à zéro, la solution du problème se programme comme suit :
- le processus p est déjà bloqué sur la primitive P(signal) lorsque le processus q exécute la primitive V(signal), alors le réveil devient effectif ;
Si le test des variables d'état indique que le processus p peut continuer, alors en exécutant l'opération V(sempriv), il se donne un droit de passage, et à la sortie de la section critique il ne se bloquera pas sur l'opération P(sempriv). Dans le cas contraire, l'opération V(sempriv) est sautée, et le processus p se bloque à la sortie de sa section critique sur l'opération P(sempriv) puisque le sémaphore était initialisé à 0.
Etudions maintenant ces schémas au travers de l'exemple des Philosophes et des Spaghetti. Cinq philosophes se réunissent au cours d'un repas : au menu des spaghetti. Les philosophes étant des hommes aussi, ils ne peuvent penser et manger en même temps, et doivent donc alterner ces deux activités. Selon leur savoir-vivre les spaghetti se mangent avec deux fourchettes, et malheureusement le restaurateur n'a prévu qu'une fourchette par personne.
- afin de ne pas se pencher au dessus de la table, un philosophe pour manger
- même s'il adore les spaghetti, un philosophe doit manger raisonnablement, i.e. pendant un temps limité,
- même s'il a très faim, un philosophe ne doit pas s'emparer d'une fourchette si
- au début du repas, tous les philosophes penseront.
Pour un philosophe i, le passage de l'état REFLEXION à l'état RIPAILLE n'est possible, d'après l'hypothèse 2, que si les philosophes situés sur sa droite et sur sa gauche sont dans un état différent de RIPAILLE. Si cette condition n'est pas réalisée, le philosophe i passe dans l'état ATTENTE ; cette transition sera réalisée grâce à un sémaphore privé sempriv[i], initialisé à 0. La demande de fourchettes s'écrit donc :
Naturellement, le test et l'affectation des variables d'état constituent des sections critiques protégées par un sémaphore d'exclusion mutuelle, noté mutex.
Pour un philosophe i, le passage de l'état RIPAILLE à l'état REFLEXION entraîne le réveil des philosophes situés à sa droite et à sa gauche si les conditions suivantes sont remplies :
- d'autre part on est sûr qu'ils disposeront de deux fourchettes, c'est-à-dire que le philosophe situé à la droite (gauche) du philosophe de droite (gauche) est dans état autre que RIPAILLE.
- la zone système (u-area) contenant des informations sur le processus ; cette zone est uniquement manipulée par le système,
- la zone d'instructions ; le code du programme exécuté par le processus est stocké ici.
A chaque processus est associé un numéro d'identification, le pid. Ce numéro, attribué par le système, permet de garder une trace de tous les processus, et sert également à la synchronisation et la communication entre processus.
Enfin, chaque processus a un père dont le numéro d'identification est donné par le ppid. Cette notion de parenté entre processus apparaît dès lors qu'un processus A “lance” un processus B, le processus A étant le père du processus B, et le processus B étant bien évidemment le fils du processus A. Ainsi, sur l'exemple suivant obtenue par la commande ps :
il apparait que le processus essai (pid 967, ppid 966) est le fils du processus csh (pid 966).
Il existe deux fonctions C qui permettent à un processus de connaître son pid et celui de son père. Ces deux primitives sont :
int getpid(void) int getppid(void)
4.2 Création de processus
4.2.1 La fonction system
La fonction system est le premier des mécanismes permettant à un processus de créer un autre processus. Inclus dans le fichier entête stdlib.h, le prototype de cette fonction est le suivant :
void system(char *commande)
et sa réalisation a pour effet d'exécuter la commande donnée en argument, le processus appelant étant interrompu jusqu'à la fin de l'exécution de la commande.
Par exemple, après avoir compilé et exécuté en arrière plan le programme suivant :
#include <stdio.h> #include <stdlib.h> void main(void)
{
system("sleep 60");
return;
}
un appel à la commande ps nous permet de mieux comprendre les mécanismes mis en jeux :
| UID PID PPID CP PRI NI VSZ | RSS WCHAN S TTY TIME COMMA |
| 25 866 859 1 44 0 1.91M | 384K pause S ttyp2 0:00.45 csh |
| 25 867 866 0 44 0 1.22M | 88K wait I ttyp2 0:00.01 essai |
| 25 925 867 0 44 0 1.71M | 160K wait I ttyp2 0:00.01 sh –c |
| 25 966 925 0 44 0 1.22M | 96K - I ttyp2 0:00.01 sleep |
Au cours de son exécution le processus essai appelle le noyau (par la fonction system).
Cet appel entraine la création d'un processus fils de nom sh -c (pid 925). Ce processus est à son tour le père du processus sleep (pid 966) correspondant à notre commande sleep 60 (les processus essai et sh -c seront bloqués jusqu'à la fin du processus sleep).
4.2.2 Les primitives exec
UNIX propose d'autres primitives pour créer des processus. Les primitives exec… représentent une famille de primitives dont l'objectif est la création d'un nouveau processus se substituant au processus appelant. Par exemple, la primitive execl, dont le protoype est le suivant :
int execl(char *ref, char *arg0, …, char *argn)
Figure n° 1 : Illustration du mécanisme de la fonction execl
Il est important de comprendre que le processus créé remplace le processus appelant, ce qui signifie d'une part qu'il n'y a pas de retour de la primitive execl (le processus appelant est purement est simplement éliminé), et d'autre part que le processus demeurant après la réussite de cette fonction possède le même numéro d'exécution, le même père, les mêmes priorités, etc. que le processus appelant (figure n°1).
Une illustration de ce mécanisme est donnée par l'exécution du programme essai.c suivant
:
| #include <stdio.h> #include <stdlib.h> void main(void) { execl("/bin/ps","ps", "al", (char *)0); printf("et maintenant je m'arrete\n"); return; } |
Au lancement du programme, le processus essai est créé. Ce processus de pid 867 occupe une taille mémoire de 88Ko.
| UID PID PPID CP PRI NI VSZ RSS WCHAN S TTY TIME | COMMA |
| 25 866 859 1 44 0 1.91M 392K pause S ttyp2 0:00.45 | csh |
| 25 867 866 0 44 0 1.22M 88K - R ttyp2 0:00.01 | essai |
Après l'appel à la primitive système execl, on remarque que processus de pid 867 correspond maintenant à l'exécution de la commande ps al (taille mémoire 224Ko).
| UID PID PPID CP PRI NI VSZ RSS WCHAN S TTY TIME | COMMA |
| 25 866 859 0 44 0 1.91M 392K pause S ttyp2 0:01.45 | -csh |
| 25 867 866 0 44 0 1.45M 224K - R ttyp2 0:00.03 | ps al |
On notera également que le message “et maitenant je m'arrete” n'apparaîtra jamais à l'écran.
4.2.3 La primitive fork
Cette primitive effectue donc une duplication du processus appelant (copie des données, du code, des priorités, etc.), ce qui signifie que le nouveau processus (appelé le fils) exécute une copie du programme mise en oeuvre par le processus appelant (nommé le père). La seule manière de distinguer le père du fils est que la valeur de retour de la fonction fork. Dans le processus fils elle est nulle, tandis qu'elle est égale au numéro d'identification du fils dans le processus père (figure n° 2)
Figure n° 2 : Illustration du mécanisme de la fonction fork
Prenons comme exemple, l'exécution du programme suivant :
| #include <stdio.h> #include <stdlib.h> void main(void) { printf("Bonjour je vais me dupliquer\n"); fork(); printf("j'ai reussi\n"); return; } |
qui provoque à l'écran deux fois l'affichage du message “j'ai reussi”. Une analyse plus détaillée, nous montre qu'au lancement du programme, un processus essai a été créé.
| UID PID PPID CP PRI NI VSZ RSS WCHAN S TTY TIME | COMMA |
| 25 866 859 0 44 0 1.91M 400K pause S ttyp2 0:01.45 | csh |
| 25 867 866 0 44 0 1.22M 88K - R ttyp2 0:00.03 | essai |
Puis, au moment de l'appel à la primitive fork, un deuxième processus essai est créé. Ce processus est conforme en tous points au premier, à ceci près qu'il est son fils. Ces deux processus ayant le même code, il est donc normal que l'on voit s'afficher à l'écran deux fois le message.
| UID PID PPID CP PRI NI VSZ RSS WCHAN S TTY TIME | COMMA |
| 25 866 859 0 44 0 1.91M 400K pause S ttyp2 0:01.45 | csh |
| 25 867 866 0 44 0 1.22M 88K - S ttyp2 0:00.03 | essai | essai |
4.3 Synchronisation de processus
4.3.1 La primitive wait
La primitive wait permet de synchroniser de manière rudimentaire des processus en suspendant l'exécution du processus en cours tant que l'un de ces fils ne s'est pas terminé. Le prototype de cette fonction est :
Lorsqu'un processus fils meurt, la fonction wait renvoie son numéro d'identification et place dans code l'adresse du code de terminaison de celui-ci.
4.3.2 Synchronisation par signaux
La synchronisation de processus par signaux est un mécanisme assez subtil. Un signal est une interruption logicielle informant un processus qu'un événement extérieur particulier ou anormal s'est produit dans son environnement. Par exemple, lors d'une division par zéro le signal floating point exception est émis à l'adresse du processus ne sachant pas calculer, lorsque vous interrompez un processus en tapant au clavier Ctrl-C le signal SIGINT est envoyé à destination de celui-ci, lorsqu'un processus viole la mémoire le signal SIGSEGV lui est adressé, etc.
Il existe de nombreux signaux et tous sont identifiés par une constante symbolique. La liste de ces constantes ainsi que toutes les fonctions permettant de manipuler les signaux sont définies dans le fichier standard signal.h. A chaque signal est associé un événement extérieur, et un comportement prédéfini du processus recevant le signal. Toutefois, un signal peut être envoyé sans que l'événement correspondant ne se soit produit -la seule information véhiculée est alors le type du signal-, et de plus le comportement standard d'un processus face à un signal peut être modifié.
Le tableau suivant présente quelques signaux, leur type, le comportement associé et le caractère modifiable ou non de ce comportement :
| Nom du signal | Evénement associé | Comportement associé | Modifiable |
| SIGINT | frappe de CTRL-C | terminaison du processus | oui | erreur arithmétique | terminaison du processus | oui |
| SIGKILL | signal de terminaison | terminaison du processus | oui |
| SIGUSR1 | terminaison du processus | oui |
| SIGUSR2 | terminaison du processus | oui |
| SIGCHLD | terminaison d'un fils | signal ignoré | oui |
Envoi d'un signal
L'envoi d'un signal d'un processus à un autre se fait au travers de la fonction kill dont le prototype est le suivant :
int kill(int pid, int sig)
où pid représente le numéro du processus destinataire, et sig le signal émis ; cette fonction renvoie 0 si elle s'est correctement déroulée et -1 sinon. Le processus émetteur et le processus receveur doivent en principe appartenir au même utilisateur.
Réception d'un signal
La prise en compte d'un signal par un processus se traduit par un comportement par défaut désigné symboliquement par la constante SIG_DFL, et définissant l'action à réaliser lors de la réception du signal. Ainsi, un processus recevant un signal pourra :
- se terminer,
- se terminer et engendrer une image mémoire (fichier core) qui plus tard sera analysée,
- ignorer le signal,
- s'interrompre,
- reprendre son exécution.
void (*signal(int sig, void (*p_traitement)(int))) (int)
où p_traitement sera initialisé soit avec l'une des constantes symboliques SIG_DFL et SIG_IGN, soit avec l'adresse de la fonction associée au traitement du signal sig. Le prototype de cette fonction est le suivant :
Une fois le signal capté et traité, le traitement associé au signal reste toujours en place (sauf sur les versions ATT d'UNIX où le comportement par défaut est réactivé).
Attente d'un signal
Enfin, la suspension d'un processus dans l'attente d'un signal est réalisé par la fonction pause dont le prototype est le suivant :
A la délivrance du signal, le processus exécutera le traitement prévu.
Exemple
A titre d'exemple, voici le changement du comportement par defaut d'un processus lors de la réception d'un signal. Ici, notre processus, au lieu de s'arrêter immédiatement à la réception du signal SIGINT, s'arrêtera seulement après en avoir capté 5. Voici le code exécuté par notre processus :
| #include <signal.h> int c = 0; void capte(int sig) { printf("Aie !!!, on me reveille\n"); c++; if (c > 5) {printf("j'en ai marre, bye bye\n");exit(0);} return; } void main(void) { signal(SIGINT,capte); for(;;) { printf("je dors!!!\n"); sleep(5); } return; } |
La fonction capte incrémente la variable c, et lorsque sa valeur sera supérieure à 5, le programme s'arrêtera. Cette fonction est associée, grâce à la fonction signal, au traitement par défaut du signal SIGINT, ce qui implique que chaque fois que le processus recevra ce signal, un appel à la fonction capte sera immédiatement réalisé.
Chapitre 3 / Gestion des processus
Dans le chapitre précédent, nous avions traité les différents mécanismes à mettre en oeuvre, soit pour protéger des informations partagées entre plusieurs processus (exclusion mutuelle), soit pour permettre à plusieurs processus de coopérer à un même but (synchronisation). L'étude des processus étant fondamentale pour la compréhension d'un système d'exploitation, nous allons maintenant aborder les mécanismes mis en jeu pour assurer à plusieurs processus un déroulement "simultané".
1. Contexte d'un processus
De nombreuses définitions ont été données à la notion de processus. La plus courante est qu'un processus est une entité dynamique représentant l'exécution d'un programme. Il est important de bien comprendre qu'un processus étant capable de recevoir, de la part du système d'exploitation, le contrôle du processeur pour un certain temps, celui-ci n'est pas uniquement défini par le code de son programme, mais également par un ensemble d'informations nécessaires au système.
Cet ensemble d'informations est appelé généralement le contexte ou le vecteur d'état d'un processus. Il est formé de deux parties :
- les informations utilisées par le système,
- les informations utilisées par le processus lui-même.
Lorsque le système "passera la main" d'un processus à un autre, il le fera en réalisant une opération appelée le changement de contexte.
1.1 Informations utilisées par le processus
1.2 Informations utilisées par le système
Les informations utilisées par le système servent à gérer l'attribution des ressources pour un processus donné. Habituellement, ces informations sont :
- le contenu des registres généraux ; ces registres sont adressables et modifiables par le processus,
- le Mot d'Etat du Processeur (MEP ou en anglais PSW Program Status Word) ; le MEP contient une copie des registres spécialisés (compteur ordinal, registre d'instruction, etc. -ces registres sont en principe inaccessibles au processus-), l'état d'exécution du processeur, le pouvoir du processus (un processus s'exécute en mode maître ou en mode esclave ; le mode maître lui permet de réaliser les instructions d'entrées-sorties, celles touchant aux interruptions et celles concernant la sécurité et la protection-, la priorité du processus, et pour finir les masques d'interruptions,
- le contenu de la mémoire virtuelle.
Toutes ces informations sont situées dans le bloc de contrôle du processus (PCB Process Control Bloc), les blocs de contrôle de tous les processus étant regroupés dans la table des processus.
2. Le parallélisme
Lorsque plusieurs processus existent en même temps dans un système, on parle alors de parallélisme. Il existe deux sortes de parallélisme :
- le parallélisme vrai, où n processus s'exécutent sur m processeurs (architecture multiprocesseur),
- le parallélisme simulé, où n processus s'exécutent sur un processeur qui est successivement attribué, par tranche de temps, à chacun des processus.
Supposons que nous disposions de trois processus effectuant uniquement du calcul (figure n°1). On remarque que le parallélisme simulé n'est pas un meilleur mode d'exploitation du processeur que la monoprogrammation car, que les processus se déroulent les uns à la suite des autres ou alternativement, le temps total d'exécution est le même.
Figure n°1 : Comparaison du temps d'exécution de trois processus n'effectuant que du calcul
Cependant, rares sont les programmes qui ne font que du calcul, et l'avantage du parallélisme simulé sur la monoprogrammation devient alors évident dès qu'un processus est par exemple bloqué dans l'attente de l'achèvement d'une entrée-sortie (échange avec l'utilisateur, lecture sur le disque, etc.).
Ainsi, à condition de disposer d'un dispositif d'entrées-sorties autonome, dès qu'un processus attend l'achèvement d'une entrée-sortie, le processeur lui est retiré au profit d'un autre processus. Si tous les programmes font suffisamment d'entrées-sorties, on arrive alors à masquer l'exécution des calculs par les temps d'attente des entrées-sorties ; chaque utilisateur a l'impression d'un temps de réponse quasiment identique à celui obtenu s'il était le seul à travailler sur la machine (figure n° 2).
Figure n°2 : Comparaison du temps d'exécution de trois processus effectuant du calcul et des entrées-sorties
3. Allocation du processeur réel
Nous allons donc voir maintenant comment est simulé le parallélisme sur une machine monoprocesseur, et plus exactement comment est alloué le processeur dans un système multitâches.
3.1 Définition du problème
Le problème de l'allocation du processeur peut être schématisé comme suit : au cours du temps, suivant une certaine loi d'arrivée, des processus demandent à utiliser le processeur (figure n° 3):
Figure n°3 : Schéma d'allocation du processeur
- actif ; seul le processus utilisant le processeur est dans cet état,
- bloqué ; cet état est attribué aux processus attendant la fin d'une entrée-sortie, la libération d'une ressource, ou en communication/synchronisation avec d'autres processus,
- attente ; cet état est attribué aux processus qui ne sont plus bloqués, et à ceux qui ont consommé leur quantum de temps ; dans les deux cas, le processus pourrait reprendre son exécution mais le processeur n'est pas disponible.
Le problème de l'allocation du processeur revient donc à définir le rôle du composant système qui aura la charge de faire transiter les processus d'un état à l'autre.
3.2 Le distributeur
Le distributeur (scheduller en anglais) est la partie du système d'exploitation chargée de veiller à la bonne attribution du processeur au cours du temps. Son rôle consiste :
- d'une part à sélectionner, en fonction d'une certaine stratégie, le processus à qui il attribuera le processeur,
- d'autre part à retirer, après un certain temps d'utilisation ou en fonction d'événements spécifiques (E/S, demande d'une ressource, etc.), le processeur au processus.
L'acquittement de cette tâche devra se faire en respectant les contraintes suivantes :
- la garantie à chaque processus d'un temps donné d'allocation,
- le respect d'un ordre de priorité entre les processus demandeurs,
- l'exécution totale d'un processus,
- la mise à l'écart d'un processus utilisant le processeur pendant un temps supérieur au maximum fixé par le programmeur ou le système.
3.3 Changement de contexte entre deux processus
- le distributeur interrompt le processus A,
- il sauve le contexte du processus A dans la table des processus,
- il réactualise les registres de l'unité centrale à partir du contexte du processus B, - et enfin il réactive le processus B.
Si l'on étudie ce schéma de plus près, on peut se demander "comment le distributeur s'y prend-il pour sauver le contexte de A ?". En effet, si le distributeur sauvegarde le contexte du processus A, c'est donc le processus associé au distributeur est actif et donc occupe l'unité centrale avec son propre contexte. La solution à ce problème recourt au mécanisme d'interruption. En fait, le système d'exploitation peut programmer l'horloge pour que celle-ci génère une interruption matérielle associée à une routine de changement de contexte. Le schéma précèdent peut donc être affiné ainsi :
- l'horloge génère une interruption qui est détectée par le matériel,
- le fonctionnement normal du processeur est arrêté ; le matériel sauvegarde dans une pile le contexte du processus interrompu,
- le code correspondant à l'interruption est fourni aux circuits de traitement des interruptions qui calculent l'adresse de cette dernière ; l'adresse de l'interruption est recopiée dans le compteur ordinal, le registre d'état est modifié, l'ordinateur passe alors en mode système,
- l'exécution de la routine d'interruption système entraîne la sélection d'un processus et de son contexte,
- la fin de l'interruption provoque le chargement du nouveau contexte, et ainsi rend le processus sélectionner actif.
Il est important de se rappeler que la routine d'interruption de changement de contexte, même si elle est câblée, fait partie du système d'exploitation. Les instructions qui s'y trouvent s'exécutent en mode système, le programme interrompu travaillant normalement en mode utilisateur.
Les stratégies de choix d'un processus par le distributeur sont nombreuses et visent souvent à réduire le temps de réponse pour des processus nécessitant un temps d'exécution court. Toutefois, d'une manière générale, il est possible de classifier ces stratégies selon qu'elles mettent en oeuvre les deux notions suivantes :
- la préemption ou réquisition du processeur ; lorsqu'un processus important passe dans l'état "demandeur", l'algorithme doit décider ou non d'interrompre le processus en cours pour donner la main au processus important, et le cas échéant il doit déterminer dans quel délai on devra le faire,
- la nature des informations utilisées pour déclencher le changement de contexte ; à coté des stratégies entièrement fixées à priori, il en existent certaines utilisant les informations attachées au processus ou les informations recueillies au cours de l'activité du système.
3.4.1 Stratégie sans recyclage des travaux
Ces stratégies sont généralement utilisées dans le traitement par lots. Elles utilisent la valeur du temps d'exécution du processus, valeur qui en général est inconnue au moment de la demande du processus.
a) File d'attente simple (FIFO) : le premier arrivé est le premier servi ; on ne tient pas compte du temps d'exécution ; les travaux courts ont un temps de réponse élevé si ils passent après des travaux longs (figure n° 4).
Figure n° 4 : Allocation du processeur par file d'attente simple
b) File d'attente ordonnée de manière croissante suivant le temps estimé d'exécution (figure n° 5): quand un processus arrive il est inséré à l'endroit correspondant à son temps d'exécution ; les travaux courts sont avantagés et les longs toujours retardés .
Figure n° 5 : Allocation du processeur par file d'attente ordonnée
3.4.2 Stratégie avec recyclage des travaux
Les méthodes précédentes, en se basant sur une estimation du temps d'exécution (temps éventuellement faux ou falsifié) et en allouant le processeur à un processus durant tout ce temps, sont peu adaptées aux conditions des systèmes conversationnels où les demandes sont nombreuses et fréquentes. Les stratégies avec recyclage des travaux évitent ces inconvénients en interrompant au bout de quelques millisecondes le processus pour allouer le processeur à un autre processus ; les processus interrompus sont placés dans des files d'attentes.
a) Balayage cyclique ou tourniquet (figure n° 6): le processeur est alloué successivement au processus et ce pour un temps déterminé (quantum) ; si le processus ne s'est pas terminé au bout du temps imparti, il est interrompu et remis en queue de la file d'attente.
Figure n° 6 : Allocation du processeur par tourniquet
Facile à mettre en place, cette méthode garantie que tout processus est servi au bout d'un temps fini, et limite le délai de prise en compte d'un processus.
b) Recyclage à plusieurs files d'attentes (figure n° 7) : les processus demandeurs sont rangés dans n files Q1, Q2, … Qn ayant chacune un quantum qi.
Figure n° 7 : Allocation du processeur par recyclage sur plusieurs files d'attente
Un processus situé en tête d'une file d'attente Qi ne sera pris en compte que si toutes les files précédentes sont vides ; un processus appartenant à la file Qi et n'ayant pas terminé, sera placé en queue de la file Qi+1. Les processus sortant de Qn y retournent. Enfin, tout processus arrivant dans Q1 est pris en compte dès que le processeur est libre. Cette stratégie présente les mêmes avantages que la stratégie du tourniquet, avec en plus des ajustements plus souples
3.4.3 Stratégie fondée sur la notion de priorité
Chapitre 4 / Allocation de la mémoire
L'exécution d'un processus demandant que le code du programme et les données utilisées soient présents en mémoire, cette dernière est une ressource essentielle du système d'exploitation. Sa gestion en est confiée à un allocateur qui l'attribuera tout ou partie au(x) processus demandeur(s). L'objet de ce chapitre est donc l'étude de l'allocation de la ressource mémoire au sein d'un système d'exploitation.
1. Définitions
1.1 Espace mémoire réel / espace mémoire virtuel
Lorsqu'un processus s'exécute, il référence un ensemble de ressources situées dans un espace mémoire de travail, et ceci sans se préoccuper de savoir à quelle adresse physique de la mémoire principale se trouvent ces ressources. Cet espace mémoire de travail, par opposition à la l'espace mémoire réel, est appelé l'espace mémoire virtuel ; dans l'espace mémoire virtuel les adresses mémoires sont dites virtuelles.
1.2 Mémoire virtuelle
La mémoire virtuelle est l'ensemble des mécanismes qui permettent d'établir la correspondance entre l'espace mémoire virtuel et l'espace mémoire réel (figure n°1).
Figure n°1 : Principe de la mémoire virtuelle
La mémoire virtuelle assure comme fonctions :
- la mise en correspondance entre les adresses virtuelles et les adresses physiques,
- la gestion de l'espace mémoire réel (allocation des emplacements, transfert de l'information),
- le partage de l'information entre processus,
- la protection de l'information.
De nombreux mécanismes de mémoire virtuelle ont été élaborés, et on peut les séparer en trois grandes familles :
- ceux où la correspondance entre l'espace mémoire virtuel et l'espace mémoire réel est réalisée au moment du chargement du programme ; le résultat de la compilation ou de l'édition de liens est un module translatable dont les adresses seront définitivement fixées lors de son chargement en mémoire réelle. Le chargeur, par réimplantation statique, peut placer le programme n'importe où dans l'espace mémoire réel.
- ceux où la correspondance entre l'espace mémoire virtuel et l'espace mémoire réel est réalisée lors de l'exécution du programme : toute adresse virtuelle est transformée en une adresse réelle au moment où elle est utilisée. Cette traduction dynamique des adresses autorise une réimplantation dynamique d'un programme au cours de son exécution.
1.3 Mémoire uniforme / Mémoire hiérarchisée
Lorsque l'espace mémoire réel est le seul support de l'information adressable par le processeur, celui-ci est dit uniforme. Dans une telle situation, la taille de l'espace mémoire virtuel est inférieure ou égale à la taille de l'espace mémoire réel. En outre, la gestion de l'espace mémoire virtuel se ramène au choix d'un algorithme de placement dans l'espace mémoire réel : une fois placées dans l'espace mémoire réel, les informations y demeureront jusqu'au moment où elles cesseront d'être utilisées.
2. Un cas de gestion de mémoire uniforme : le PC
Dans le cas où un seul processus à la fois utilise les ressources du système, la plus simple des gestions de l'espace mémoire réel est celle pratiquée dans le monde de la microinformatique. L'espace mémoire réel est ainsi partagé entre le système d'exploitation et l'unique processus utilisateur. Quand un processus demande à s'exécuter, le système d'exploitation le charge dans l'espace mémoire réel, l'exécute et à sa terminaison reprend la main.
OxFFF…
|
| Programme utilisateur |
| Système d'exploitation |
O
Figure n° 2 : Organisation de la mémoire sur un PC
Une telle organisation peut conduire à de graves problèmes dès lors qu'un processus accède, intentionnellement (virus) ou non (utilisation de structures de données dynamiques, récursivité infinie), à l'espace mémoire réel réservé au système d'exploitation. Ce problème a conduit à développer des solutions logicielles (fonctions permettant de tester si une opération est possible) et matérielles (registres limites) assurant une plus ou moins grande protection.
3. Gestion de la mémoire hiérarchisée
Une mémoire uniforme n'est pas adaptée au multiplexage de l'unité centrale entre un nombre important de processus, et ce pour trois raisons :
- les processus inactifs occupent inutilement une partie de l'espace mémoire réel,
- un processus ne peut pas disposer d'un espace mémoire virtuel de taille supérieure à l'espace mémoire réel,
- plus les processus sont nombreux, moins ils disposent de place.
L'utilisation d'une mémoire hiérarchisée résout ces problèmes en multiplexant l'espace mémoire réel.
3.1 Le Va et Vient (Swapping)
Que cette technique soit utilisée dans le cadre d'un partitionnement fixe ou variable de l'espace mémoire réel, deux problèmes se posent :
- à moins de disposer d'un mécanisme de réimplantation dynamique, la réactivation d'un processus interrompu implique qu'on le replace au même endroit, ce qui peut entraîner le vidage de plusieurs autres processus,
- il est nécessaire de mémoriser en permanence l'occupation de l'espace mémoire réel.
3.1.1 Gestion de l'espace mémoire réel par table de bits
Une première solution pour la gestion de l'occupation de l'espace mémoire réel consiste à utiliser une table de bits (figure n° 3) :
Figure n° 3 : Mémorisation de l'état d'occupation de la mémoire par une table de bits
l'espace mémoire réel est divisé en unités d'allocation de taille fixe (quelques mots à plusieurs Koctets selon les systèmes), et à chaque unité correspond, dans une table de bits, un bit dont la valeur est 0 si l'unité est libre, et 1 sinon. D'une mise en place rapide, cette technique relativement peu gourmande en place, est lente à l'exécution. En effet, lors de l'introduction d'un processus dont la taille est k unités d'allocation, il est nécessaire de trouver dans la table k bits consécutifs à zéro, ce qui est très difficile.
3.1.2 Gestion de l'espace mémoire réel par liste chaînée
Une deuxième solution pour la gestion de l'occupation de l'espace mémoire réel consiste à utiliser une liste chaînée des zones libres et/ou occupées (figure n° 4). Les informations composant la liste peuvent être placées soit dans un espace mémoire réservé (chaque maillon contient par exemple un pointeur vers la zone libre, une indication de taille et le(s) lien(s) de chaînage), soit dans la zone libre elle-même (un en-tête placé au début de chaque espace libre établit le lien avec la zone libre suivante).
De l'organisation de cette liste dépend l'efficacité des algorithmes. Le chaînage peut être construit dans l'ordre chronologique des libérations, mais le plus souvent on utilise les classements suivants :
- classement par adresses croissantes ou décroissantes,
- classement par tailles croissantes ou décroissantes, le choix dépendant de l'algorithme utilisé pour satisfaire une demande.
Lorsqu'une demande est émise, plusieurs algorithmes de sélection d'une zone sont possibles :
- on prend la première zone possible (first fit) qui est découpée en deux parties, l'une attribuée au processus demandeur, l'autre (appelée résidu) inutilisée ; cet algorithme est rapide puisque pratiquement sans recherche,
- on prend la plus petite zone possible (best fit) et on évite ainsi de fractionner une grande zone dont on pourrait avoir besoin ultérieurement,
- on peut également prendre la plus grande zone possible (worst fit) et ainsi obtenir le plus grand résidu possible.
D'une manière générale, le premier algorithme est le plus rapide de tous. Toutefois, selon l'organisation de la liste, les performances de ces algorithmes peuvent varier : dans le cas de l'algorithme de la plus petite zone possible, le classement par tailles évite de parcourir toute la liste ; si le classement est fait par adresses ou s'il n'y a pas de classement, une fois la zone allouée, le résidu reste à sa place alors qu'avec un classement par tailles il doit être déplacé. Enfin, ces techniques entraînent un phénomène d'accumulation des résidus en tête de liste, ce qui ralentit les recherches. On utilise souvent une liste circulaire qui permet de commencer l'exploration à partir de n'importe quel point.
3.1.3 Gestion de l'espace mémoire réel par subdivision ("buddy system")
| 1024 Ko | |
| Introduction d'un procesus A de taille 80 Ko | |
| | 128 Ko | 256 Ko | 512 Ko |
| Introduction d'un procesus B de taille 40 Ko | |
| | | | 64 K | o 256 Ko | | 512 Ko |
| Introduction d'un procesus C de taille 95 Ko | |
| | | | 64 K | | | 128 Ko | | 512 Ko |
| | | | | | | | | |
Fragmentation Allouée Libre
Figure n° 5 : Gestion de la mémoire selon le principe de subdivision
Au départ, il n'existe qu'une seule liste contenant un bloc de la taille de l'espace mémoire réel. Le principe de la méthode est le suivant : si t est la taille de l'espace mémoire réel demandé par un processus, on recherche alors un bloc dont la taille est égale à la plus petite puissance de deux qui est supérieure à t ; si un tel bloc n'existe pas, alors on le crée par divisions successives de blocs de taille supérieure (la division en deux d'un bloc créé deux blocs appelés les compagnons ou "buddy").
Cette solution, bien que très intéressante lors de la libération d'une zone allouée, conduit à une sous-utilisation de la mémoire. En effet, les tailles des zones étant arrondies à une puissance de deux, il se produit un phénomène important de fragmentation interne.
3.1.4 Libération d'une zone
Lors de la libération d'une zone allouée, trois situations différentes peuvent apparaître selon que la zone libérée est entourée de deux zones libres, d'une zone allouée et d'une zone libre, ou de deux zones allouées (figure n° 6).
Figure n° 6 : Libération d'une zone mémoire
3.1.5 Fragmentation et compactage
Au bout d'un certain temps d'utilisation, dans des systèmes d'allocation du type demande de zone, une fragmentation de l'espace mémoire réel se produit. Cette situation empêchant l'allocateur de trouver une zone de taille suffisante pour satisfaire toute demande nouvelle, il est alors nécessaire de compacter la mémoire. Ce compactage se traduit par un déplacement de toutes les zones allouées vers une extrémité de la mémoire, ce qui fait apparaître une zone libre dont la taille est la somme des tailles des zones libres primitives (figure n°7).
| | inutilisé |
| inutilisé |
|
| inutilisé | |
|
| inutilisé | |
|
| |
| |
| Système d'exploitation | Système d'exploitation |
Figure n° 7 : Compactage de l'espace mémoire réel
Cette méthode très coûteuse en temps n'est pas toujours applicable, notamment lors de l'absence de mécanisme de réimplantation dynamique. Par ailleurs, des simulations ont montré que lorsque l'algorithme d'allocation ne peut satisfaire une demande, alors le taux de remplissage de l'espace mémoire réel est tel que, même après un compactage on retombera très vite dans la situation précédente ; le système passe alors son temps à compacter la mémoire.
3.2 La pagination
3.2.1 La pagination à un niveau
Dans le mécanisme de pagination à un niveau (figure n° 8), une adresse virtuelle est composée de deux parties : un numéro de page p et un déplacement d à l'intérieur de la page ; les P bits de gauche d'une adresse de N bits fournissent un numéro de page, et les N-P bits de droite le déplacement dans la page. La taille de la page est 2N-P. La traduction d'une adresse virtuelle en une adresse réelle est réalisée par la table des pages située dans l'espace mémoire réel, et dans laquelle les entrées successives correspondent aux pages virtuelles consécutives. La pième entrée de cette table contient le numéro r de la page où est implantée la page virtuelle p. L'adresse réelle (r,d) d'un mot d'adresse virtuelle (p,d) est donc obtenue en remplaçant le numéro de page p par le numéro de case r trouvée dans la table.
Figure n° 8 : Principe de la pagination à un niveau
Lorsque le mécanisme de traduction des adresses utilise des tables de pages situées dans l'espace mémoire réel, toute traduction ralentit considérablement le processeur. Pour éviter cela, il existe plusieurs mécanismes accélérateurs comme les mémoires caches, les mémoires associatives, etc. dans lesquels on mémorise généralement les numéros des pages les plus fréquemment utilisées. La traduction d'une adresse consiste alors à consulter d'abord ces mémoires, la consultation de la table n'ayant lieu que si le numéro de page virtuelle ne s'y trouve pas.
Les tailles des pages choisies par les constructeurs sont en général du même ordre de grandeur (de 512 à 4096 octets). Ce choix est motivé par les considérations suivantes :
- la taille de la table des pages est proportionnel au nombre de pages de l'espace mémoire virtuel. Il est donc préférable d'avoir des pages de grande taille pour réduire la taille de la table, ce qui permet de la placer dans des registres ou dans une mémoire cache, d'où un gain de temps.
- le temps de lecture d'une page sur la mémoire secondaire est pratiquement proportionnel temps de positionnement de la tête de lecture. Pour réduire ce temps, il est préférable de travailler avec des pages de grande taille.
Afin d'améliorer le rendement du mécanisme de pagination, il est souvent associé à chaque entrée de la table des pages les informations suivantes :
- un bit d'invalidité qui lorsqu'il est positionné à 1 indique que a page virtuelle n'est pas déjà présente dans l'espace réel,
- des bits d'utilisation qui permettent de connaître l'usage qui est fait de la page (lecture, écriture),
- des bits de protection qui indiquent si la page peut être lue, écrite, exécutée.
3.2.2 Le remplacement de pages
Lorsqu'un processus référence une page virtuelle absente de l'espace mémoire réel, on dit q'on a un défaut de page. Le traitement d'un défaut de page est réalisé par le système qui avant de charger la nouvelle page virtuelle, devra commencer par libérer de la place dans l'espace mémoire réel en renvoyant en mémoire secondaire une page réelle. L'algorithme qui consiste à choisir la page à renvoyer s'appelle l'algorithme de remplacement. De nombreuses études ont été réalisées, et elles se distinguent essentiellement par les informations prises en compte et relatives à l'utilisation passée des pages.
Voici les principaux algorithmes de remplacement de page :
- le tirage aléatoire RAND ; la page éjectée est choisie au hasard,
- ordre chronologique de chargement FIFO ; la page éjectée est la page la plus anciennement chargée,
- degré d'utilisation LFU (Least Frequently Used) ; la page éjectée est la page la moins fréquemment utilisée,
- l'algorithme optimal OPT ; s'il existe des pages qui ne seront plus référencées alors remplacer l'une de ces pages, sinon remplacer la page qui sera le plus tardivement référencée.
Le dernier algorithme est totalement irréalisable car il est impossible de connaître à l'avance le moment où les différents pages qui seront référencées. Cependant, cet algorithme sert de référence pour la comparaison des performances des autres algorithmes (figure n° 9). Toutefois, au delà de l'ordre des performances, il est important de noter que d'une part les performances des algorithmes sont toutes proches de celles de l'algorithme RAND, et d'autre part l'influence de la taille mémoire est très largement supérieure à celle de l'algorithme de remplacement.
Nombre de défaut de page
la mémoire
Figure n° 9 : Performances comparées des algorithmes de remplacement de page
3.3 La segmentation
La pagination présente un espace mémoire virtuel monodimensionnel puisque les adresses virtuelles sont continues entre les valeurs 0 et un nombre maximum. Dans beaucoup de cas, il est préférable de disposer de plusieurs espaces mémoires virtuels appelés des segments, qui seront logiquement associés à des entités d'un seul type (on parlera de segment des tables de symbole, de segments procédure, de segments des constantes, etc.) (figure n° 10).
Figure n° 10 : Principe de la segmentation
Contrairement à la pagination, la segmentation de l'espace mémoire réel est une technique qui doit être connue du programmeur et/ou du compilateur. De ce fait, la segmentation assure une grande protection de l'information, permet le partage de données et de procédures (réentrance), simplifie la manipulation des données dont la taille varie dynamiquement, élimine les problèmes d'éditions de liens et de compilation séparée.
Chapitre 5 / La mémoire secondaire
Dans un système d'exploitation à mémoire hiérarchisée, la mémoire secondaire est un organe de stockage de grande capacité et de faible coût, ceci relativement à la mémoire centrale appelée aussi mémoire primaire. Actuellement, la mémoire secondaire est constituée essentiellement de supports magnétiques tels que les disques, les tambours étant devenus obsolètes et les moyens futuristes (disques optiques, disques laser réinscriptibles, etc.) n'étant pas encore mûrs. L'exploitation de cette mémoire secondaire est une des fonctions essentielles d'un système d'exploitation. D'une part le système assure le contrôle du disque et fournit une interface simple à son utilisation, d'autre part il s'occupe de son organisation notamment pour la gestion des fichiers.
1. Etude du disque magnétique
1.1 Structure physique d'un disque
Un disque est composé de pistes concentriques, elles-mêmes divisées en secteurs (figure n° 1). Bien que les secteurs situés à la périphérie du disque soient plus grands que ceux situés au centre, le même nombre d'octets est utilisé pour le stockage de l'information sur tous les secteurs. Chaque secteur est repéré par des marques, le formatage d'un disque consistant à poser ces marques.
Figure n° 1 : Structure d'un disque
On introduit également les notions de bloc et de cylindre :
- un cylindre correspond au nombre de pistes accessibles simultanément lors d'un accès au disque ; un cylindre contient donc autant de pistes que de têtes de lecture/écriture.
Enfin, chaque disque possède un contrôleur de disque assurant le déplacement du bras, la rotation du disque et la commande des têtes, le regroupement des séries de bits lues, etc. Ce contrôleur est un véritable ordinateur avec sa mémoire et ces registres. En outre, de nombreux contrôleur permettent un accès direct à la mémoire, déchargeant ainsi l'unité centrale du transfert de l'information. Le lien entre l'utilisateur et le contrôleur est assuré par le système d'exploitation au moyen d'un logiciel appelé le pilote (driver). Celui-ci traduira les requêtes systèmes en un programme exécuté par le contrôleur.
1.2 Le pilote du disque
L'utilisation d'un disque se fait donc au travers d'un pilote de disque. Celui-ci doit d'une part optimiser les temps d'accès au disque en fonction des demandes, et d'autre part gérer les erreurs logiques ou physiques rencontrées.
1.2.1 Les algorithmes d'ordonnancement du bras
Les temps de lecture ou d'écriture d'un bloc dépendent essentiellement des trois facteurs suivants :
- le temps de recherche ; temps nécessaire pour positionner la tête de lecture sur le bon cylindre,
- le temps de rotation ; temps nécessaire pour positionner la tête de lecture sur le bon secteur,
- le temps de transfert ; temps nécessaire pour transférer le bloc du disque dans la mémoire du périphérique.
En fait, le temps de recherche étant le plus important, sa réduction entraînera une amélioration sensible des performances du système. Aussi, il existe plusieurs algorithmes d'ordonnancement du bras visant à réduire ce temps de recherche (figure n° 2). Les principaux sont :
- SATF (shortest acces time first) le déplacement le plus court ; le pilote satisfait les requêtes concernant le cylindre le plus près de la position actuelle du bras, puis se déplace, dans un sens ou dans l'autre, vers le cylindre le plus proche comportant des requêtes à satisfaire. Simple à mettre en oeuvre, cet algorithme est généralement deux fois plus performant que le précédent. Toutefois, comme une demande concernant un cylindre éloigné du cylindre courant peut être indéfiniment retardée, si des demandes concernant des cylindres proches arrivent avec une fréquence suffisamment grande, cette stratégie n'est guère utilisée dans la pratique. En effet, de part ce qui précède, on en déduit que le temps moyen d'exécution d'une demande est diminué, alors que le temps maximum est augmenté. Il n'y a pas équité entre tous les cylindres, ce qui peut aller à l'encontre de certaines règles de priorités établies entre plusieurs processus.
- stratégie de l'ascenseur ; dans cette méthode le bras du disque se déplace dans un sens donné, s'arrête au dessus de chaque cylindre pour lequel des demandes existent et les traite. Lorsque le dernier cylindre comportant une file non vide a été atteint et traité, on change le sens de déplacement et on recommence. Les performances de cet algorithme sont en général moins bonnes que celles de l'algorithme SATF, mais la contrainte d'équité entre les cylindres est maintenant respectée.
| 0 5 10 | | 15 20 25 30 | | 35 |
| X | | | | | | | | X | | X | X | | | | X | | | | | | | | | | | | | | | | | | X | | X |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
Algorithme SATF, Ordre des requêtes : 11 1 36 16 34 9 12
| 0 5 10 | | 15 20 25 30 | | 35 |
| X | | | | | | | | X | | X | X | | | | X | | X |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
Algorithme de l'ascenceur, Ordre des requêtes : 11 1 36 16 34 9 12
Figure n° 2 : Déplacement comparé du bras du disque pour différents algorithmes d'ordonnancement
Il est à noter que tous ces algorithmes supposent que le pilote accepte de nouvelles requêtes pendant le traitement d'une première requête. Ceci est rendu possible par l'utilisation d'une table indexée par les numéros de cylindres, où chaque entrée pointe sur le premier élément d'une liste chaînée des différentes requêtes concernant un cylindre. En outre, quelques contrôleurs permettent au pilote de connaître le numéro de secteur situé sous la tête, autorisant alors une autre optimisation : le pilote peut, pour deux requêtes concernant le même cylindre, commencer par celle dont le secteur passera en premier sous la tête.
1.2.2 Le traitement des erreurs
Lors de l'exploitation d'un disque, le pilote doit traiter des erreurs logiques ou physiques. Les plus courantes sont :
- les erreurs de programmation (par exemple la demande d'un bloc qui n'existe pas, le positionnement sur un secteur ou un cylindre inexistant, l'utilisation d'une tête inconnue, etc.) ; en règle générale, le contrôleur vérifie les paramètres fournis par le pilote et ne les accepte pas s'ils sont incorrects. En théorie inexistantes, ces erreurs lorsqu'elles se produisent sont traitées lors de la mise à jour du système.
- les erreurs de recherche (positionnement du bras sur le mauvais cylindre) dues aux problèmes mécaniques ; un décalage, entre la position de bras mémorisée par le contrôleur et sa position réelle, peut se produire. Certains contrôleurs traitent l'erreur, d'autres se contentent de la signaler, obligeant ainsi le pilote à effectuer une opération de recalibrage du disque (déplacement du bras à sa position extrême, puis remise à zéro de la position mémorisée du bras).
2. Le système de gestion des fichiers
Le système de fichiers est l'une des parties les plus importantes d'un système d'exploitation (sur un certain système… c'est même pratiquement la seule fonction). Un premier aspect du système de gestion des fichiers est basé sur la notion de fichier et les fonctions qui lui sont associées ; cet aspect est appelé "l'interface utilisateur". Le deuxième aspect du système de gestion des fichiers est l'ensemble des mécanismes qui permettent au système d'établir la correspondance entre ce que manipule l'utilisateur et ce qu'il y a réellement sur le support de mémoire externe ; cet aspect est appelé "l'interface système".
2.1 La notion de fichier
Un fichier est un ensemble de données que l'on stocke et auxquelles on accède de manières diverses au hasard des traitements. Les caractéristiques essentielles d'un fichier sont :
- le stockage d'un volume quelconque d'informations,
- la permanence des données dont la durée de vie n'est pas liée à celle d'un programme,
- l'ordre d'accès aux informations imposé par les nécessités du traitement.
Les opérations possibles sur un fichier sont de nature :
- globale lorsque le fichier est considéré comme un tout ; parmi les opérations les plus courantes sur un fichier on trouve sa création, sa destruction, sa copie, etc.,
2.1.1 La structure et les modes d'accès d'un fichier
Pour les couches basses du système de gestion des fichiers (celles qui traitent avec le matériel), la structure d'un fichier est un ensemble d'octets ; de par son niveau, cette structure est dite physique. Par opposition, une structure logique d'un fichier a été introduit pour préciser la notion de fichier, vue du coté de l'utilisateur et/ou les couches hautes du système de gestion de fichiers. La structure logique d'un fichier peut être :
- une suite d'octets,
- une suite d'enregistrements de taille fixe, chaque enregistrement étant constitué de champs de nature diverse ; on peut lire ou écrire n'importe quel enregistrement, mais on ne peut pas insérer ou détruire un enregistrement au milieu de la liste,
- une arborescence de blocs du disque, chaque bloc contenant n enregistrements indexés ; l'accès aux enregistrements se fait par une clé et on peut insérer un bloc à n'importe quel niveau de l'arbre.
Les modes d'accès à un fichier dépendent du type du fichier. Pour les fichiers ordinaires, il est possible de réaliser plusieurs types d'accès au fichier :
- l'accès séquentiel ; on accède à une composante à la suite de l'accès à la composante précédente,
- l'accès relatif ou directe ; on accède à une composante quelconque identifiée par son rang dans le fichier,
- l'accès indexé ; on accède à une composante quelconque par la valeur d'un de ces champs.
2.1.2 Les types de fichiers
La plupart des systèmes d'exploitations possède plusieurs types de fichiers. Les principaux types de fichiers sont :
- les fichiers ordinaires ; ils sont constitués par les données et les programmes des utilisateurs,
A noter qu'il existe également d'autres types de fichiers correspondant soit aux périphériques, soit à des moyens de communication entre processus.
2.2 L'organisation du disque et la sauvegarde des fichiers
Cet aspect de l'exploitation d'un disque concernent les couches basses du système de gestion des fichiers. En effet, ici on ne se préoccupe plus de savoir comment un fichier se nomme, mais bien plutôt comment on va organiser le disque et stocker les fichiers afin d'obtenir un fonctionnement fiable et efficace du système de gestion des fichiers.
2.2.1 L'organisation du disque
Il existe deux stratégies pour stocker un fichier de n octets :
- on alloue n octets consécutifs sur le disque ; le principal problème de cette méthode est dû aux augmentations de taille du fichier, ce qui oblige à déplacer souvent le fichier de place,
- on divise le fichier en plusieurs blocs pas nécessairement contigus. Le premier problème à se poser est celui du choix de la taille d'un bloc. Ce choix est issu d'un compromis entre la vitesse de transfert et le taux de remplissage souhaité pour le disque ; l'expérience tend à prendre 512 octets, 1K ou 2K comme taille d'un bloc. Le deuxième problème qui se pose est celui de la mémorisation des blocs libres. Généralement on utilise une liste chaînée des blocs libres, ou une table de bits (le ième bit de la table indiquant si le ième bloc du disque est libre ou non), le choix de l'une ou l'autre des techniques étant principalement lié à la place disponible en mémoire centrale.
2.2.2 Le stockage des fichiers
3. Le système de gestion de fichiers d'UNIX
La notion de fichier sous UNIX ne se limite pas à la notion usuelle du fichier disque. Un fichier est un objet typé sur lequel est défini un ensemble d'opérations. Ainsi, un fichier peut être une suite d'octets sur le disque ou une ressource (physique ou logique) du système comme par exemple un terminal, une imprimante, la mémoire, etc. D'un point de vue interne, à chaque fichier correspond une entrée dans une table contenant ces attributs (par exemple son type, ses propriétaires, ses droits d'accès, etc.). Une telle entrée est appelée un noeud d'information ou i-node.
3.1 La structure arborescente
Grâce à la notion de répertoire, le système de gestion des fichiers d'UNIX est organisé sous la forme d'une arborescence. Cette arborescence repose essentiellement sur l'association faite dans les répertoires entre les noms des fichiers et leur numéro d'index ; la désignation extérieure d'un fichier est réalisée en utilisant un lien associé à ce fichier dans un répertoire, ce répertoire étant lui-même désigné par le même mécanisme dans un autre répertoire. Pour être opérationnelle, cette organisation arborescente suppose une origine symbolique appelée la racine absolue, notée / et située à un adresse fixe du disque.
Cette structure arborescente a été normalisée sous UNIX (figure n° 3), et se décompose en l'ensemble des répertoires suivants :
- /bin contient la plupart des utilitaires UNIX,
- /dev contient les fichiers spéciaux,
- /etc contient les programmes et les tables d'administration du système,
- /lib contient les bibliothèques utilisées par des langages de programmation,
- /tmp est utilisé pour les fichiers temporaires,
- /usr contient des répertoires utilisés par le système, plus les répertoires des
utilisateurs,
- /usr/lib contient d'autres bibliothèques utilisées par des langages de programmation,
- /usr/include contient les fichiers d'en-tête des langages du système UNIX,
- /usr/spool contient les fichiers nécessaire à la gestion des imprimantes.
/
bin include lib spool
Figure n° 3 : Structure conventionnelle du système de gestion de fichiers d'UNIX
3.2 Les types de fichiers
L'une des caractéristiques du système de gestion de fichiers d'UNIX est la grande variété des types de fichiers. On y retrouve principalement :
- les fichiers ordinaires ; le contenu de ces fichiers est non structuré ce qui fait d'eux des suites d'octets caractérisés uniquement par leur longueur. Aucune interprétation (binaire ou texte) et aucune organisation (séquentielle, directe, indexée) ne sont associées à ces fichiers ; les applications sont donc libres de les traiter comme elles le souhaitent,
- les répertoires,
- les fichiers spéciaux ; ils sont associés à des dispositifs physiques comme les imprimantes, la mémoire, les disques, etc. Ces fichiers sont traités comme les fichiers ordinaires, mais les opérations de lecture ou d'écriture active des dispositifs physiques particuliers. A un niveau plus fin, on distingue les fichiers spéciaux en mode bloc (les entrées-sorties sont réalisées par blocs et transitent par des caches du système), et les fichiers spéciaux caractères (les entrées-sorties sont réalisées caractères par caractères et ne transitent pas par les caches du système).
A ces différents types de fichiers s'ajoutent également les tubes nommés, les sockets et les liens symboliques.
3.3 Organisation du disque
- les disques de swap ; ils servent à la sauvegarde des contextes de processus ou des pages sorties momentanément de la mémoire.
- les systèmes de gestion de fichiers ; caractérisés par leur type qui est soit System V, soit ffs/ufs (BSD). L'organisation System V est la suivante : un bloc de démarrage utilisé au chargement du système, le super bloc contenant des informations générales sur le système (nombre de noeuds alloués et libres, liste de blocs libres, etc.), la table desi-nodes, et le bloc des données qui est découpé en blocs logiques allouables de taille 512, 1024, 2048 ou 4096 octets (figure n° 4).
Figure n° 4 : Structure physique du disque sous UNIX système V
3.3.1 Structure d'un noeud d'information
Chaque i-node (figure n° 5) est un bloc de 64 octets contenant des informations comme le l'identité du propriétaire, le type et les droits d'accès au noeud pour les différents utilisateurs, le nombre de liens physiques, etc., plus 13 adresses de blocs logiques (10 adresses directes, 1 adresse indirecte simple, 1 adresse indirecte double et 1 adresse indirecte triple).
Figure n° 5 : Structure d'un i-node
Avec une telle structure, les adresses des fichiers d'au plus dix blocs sont toutes contenues dans le noeud d'information. Lorsque la taille d'un fichier dépasse les 10 blocs, il suffit d'attribuer un nouveau bloc du disque référencé par un pointeur à simple indirection ; pour des tailles de fichier importantes, on utilisera les pointeurs à double ou triple indirection. L'avantage d'un tel mécanisme est que quelque soit la taille du fichier, la taille de son inode est constante. En outre, il ne faut au plus que trois accès disques pour trouver l'adresse de n'importe quel octet d'un fichier.
3.3.2 Structure d'un répertoire
3.3.3 Structure du système de gestion de fichiers
La gestion des fichiers sous UNIX est principalement réalisée par l'intermédiaire de trois tables (figure n° 6) :
- les tables de descripteurs ; chaque processus en possède une table de descripteur, et la manipulation d'un fichier se fera par un indice (un descripteur) dans cette table. A un descripteur correspond dans la table les attributs dynamiques du fichier (fermeture en cas de recouvrement, etc.), plus un pointeur sur la table des fichiers ouverts. Il est important de se rappeler que les trois premiers indices de cette table sont réservés pour l'entrée standard, la sortie standard et la sortie d'erreur standard. Enfin, un processus acquiert un descripteur soit par héritage (une recopie de la table des descripteurs de son père est réalisée à sa naissance), soit par l'utilisation des primitives open, pipe et dup,
- la table des fichiers ouverts ; pour chaque fichier ouvert, on y trouve en autres choses le nombre de descripteurs associés, le mode d'ouverture, la position courante et un pointeur sur le i-node correspondant. Une entrée dans cette table est obtenue lors de l'utilisation des primitives open et pipe.
- la table des i-noeuds présents en mémoire. Pour chaque i-node chargé en mémoire, en plus des informations présentes sur le disque, on trouve également dans cette table des informations comme le nombre d'ouvertures sur le fichier, le disque logique auquel appartient le i-node, etc.
Figure n° 6 : Organisation du système de gestion de fichiers
Bibliographie
Bibliographie
1. Systèmes d'exploitation
- Andrew Tanenbaum
- Architecture des Systèmes d'Exploitations
Michael Griffiths, Michel Vayssade
Hermes, 1988
2. UNIX
- La programmation sous UNIX
Jean-Marie Rifflet Ediscience, 1993
- Programmer UNIX
Richard Stoeckel Armand Colin, 1992
- UNIX, Initiation et Utilisation
Jean-Paul Armspach, Pierre Colin InterEditions, 1994
- Le système UNIX
Steve Bourne
InterEditions, 1985
Nous travaillerons avec le C-Shell, dont le prompt est symbolisé par le caractère %
Bien que Window 95 change considérablement les choses.
