SUPPORT PROF MOANDA-KUTI
SUPPORT PROF MOANDA-KUTI
SUPPORT PROF MOANDA-KUTI
SYSTEMES D’EXPLOITATION
DES
ORDINATEURS
NOTES DE COURS
(Version 2018)
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 2
Objectif général du cours : Présenter les principaux concepts d’un système d’exploitation tant du
point de vue de l’utilisateur que celui du concepteur.
Objectif spécifique : décrire chacune des couches constituant un système d’exploitation suivant le
plan ci-après :
Chapitre 3 : Inter-blocages
Description des situations d’inter-blocages qui peuvent arriver lorsque deux ordinateurs se
disputent une ressource.
Les systèmes d’exploitation multimédia et les systèmes multiprocesseurs ainsi que la sécurité ne
font pas l’objet de ce cours.
Les études des cas se feront en travaux de groupes.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 3
CHAPITRE 1
D'une manière générale, un système d'exploitation est un programme qui gère les
ressources les matérielles et logicielles d'un ordinateur. Il fournit les bases nécessaires pour les
l'exécution des programmes des utilisateurs. Il sert d'intermédiaire entre l'utilisateur de
l'ordinateur et les ressources matérielles de l'ordinateur. Les systèmes d'exploitation sont variés et
peuvent également se différencier dans la manière avec laquelle ils réalisent leurs tâches. Les
systèmes d'exploitation pour les Mainframe sont conçus principalement pour optimiser
l'utilisation des ressources matérielles. Les systèmes d'exploitation pour ordinateurs personnels
supporte toutes sortes d'applications, allant des jeux vidéo complexes aux logiciels de traitement
de texte, de gestion, et autres 'applications généralistes ou spécialisées. Ils sont conçus de manière
à maximiser le travail de l'utilisateur, ici la performance est un critère de première importance.
Les systèmes d'exploitation pour les mobiles (smartphones et tablettes) sont conçus pour fournir
un environnement dans lequel un utilisateur peut facilement s'interfacer avec le dispositif mobile
pour exécuter les programmes. Par conséquent, certains systèmes d'exploitation sont conçus pour
être conviviaux, d'autres sont conçus pour être efficaces, et enfin, certains combinent les deux
aspects.
Les systèmes d'exploitation modernes sont des programmes informatiques très larges et et
d'une très grande complexité. A titre d'illustration, le noyau du système d'exploitation linux 4.16
avoisine 26 millions des lignes de code1.Il est clair qu'un tel programme est généralement conçu
pièce par pièce suivant une méthodologie très rigoureuse et efficiente. Chaque pièce doit être une
portion bien délimitée u système, avec des entrées sorties et des fonctions soigneusement bien
définies.
1
https://en.wikipedia.org/wiki/Linux_kernel
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 4
Les utilisateurs
La figure ci-dessus peut être explicitée à l'aide de la figure 1.2 qui illustre sous forme des
différentes couches l'organisation d'un système informatique
Le système informatique est souvent présenté sous forme d’un empilement de niveaux ou
couches (6 ou plus). Le plus bas niveau (ou la couche la plus basse) contient les périphériques, les
circuits intégrés, les câbles, les alimentations, les cathodiques, etc. Vient ensuite le niveau ou
couche microarchitecture. Ce niveau comprend des registres internes de la CPU (Central
Processing Unit ou unité centrale de traitement) et un chemin de donnée contenant une ALU
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 5
(Arithmetic and Logic Unit ou unité arithmétique et logique). Le rôle du chemin de données
(lignes physiques utilisées pour transmettre les données) est d’exécuter un ensemble
d’instructions. Ces instructions peuvent utiliser les registres ou d’autres ressources. Le matériel et
les instructions accessibles à un programmeur en assembleur constituent le niveau ISA
(Instruction Set Architecture, architecture du jeu d’instructions) ou niveau langage.
Le langage machine d’un ordinateur possède entre 50 et 300 instructions, la plupart
servant à déplacer des données, à réaliser des opérations arithmétiques et à comparer des valeurs.
A ce niveau, les périphériques d’entrée/sortie sont contrôlés en chargeant des valeurs dans
des registres spéciaux dits de périphériques.
La programmation des opérations de lecture ou d’écriture est trop complexe. Pour
masquer cette complexité, on a recours à un système d’exploitation ou OS (operating system). Il
consiste en une couche logicielle qui cache, partiellement, le matériel et fournit au développeur
un jeu d’instructions plus pratique pour son travail.
Au-dessus du système d’exploitation, on trouve l’interpréteur de commande (Shell), le
système de fenêtrage, les compilateurs, les éditeurs et d’autres programmes indépendants des
applications.
indiquer le statut, le pavé numérique pour introduire les données, des écrans, etc..). Les systèmes
d'exploitations pour ces systèmes sont conçus principalement pour fonctionner sans intervention
de l'utilisateur.
Un ordinateur généraliste moderne est constitué d'un ou de plusieurs CPUs et d'un certain
nombre des contrôleurs des périphériques connectés à travers un bus commun donnant à la
mémoire partagée comme le montre la figure ci-dessous:
Chaque contrôleur est responsable d'un périphérique spécifique (par exemple: disque dur, audio,
affichage, etc). Tous ces contrôleurs sont directement intégrés sur la carte mère. Le CPU et les
contrôleurs peuvent fonctionner en parallèle, dans ce cas ils sont en compétition pour des cycles
mémoires, dès lors pour assurer un accès ordonné à la mémoire partagée, un contrôleur de
mémoire est requis pour synchroniser les accès mémoires.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 7
Une fois que le noyau est chargé en mémoire et qu'il est en exécution, il peut alors fournir des
services au système et à ses utilisateurs. Certains services sont fournis en dehors du noyau par
d'autres programmes systèmes qui sont chargés en mémoire au moment du démarrage pour
devenir des processus systèmes, ou system daemons (démons systèmes), qui tournent tant que le
noyau est en exécution. Dans les systèmes UNIX, le premier processus système est "init", il est
responsable de démarrer plusieurs autres daemons.
Une fois que ce processus est finalisé, le système est alors pleinement démarré, et va donc
attendre que survienne un événement.
L'occurrence d'un événement est généralement signalé par une interruption provenant soit du
matériel ou du logiciel. Le matériel peut déclencher une interruption à tout moment en envoyant
un signal au CPU par le canal du bus système. Le software peut déclencher une interruption en
exécutant une opération spéciale appelée "Appel Système" ou "System Call".
Les interruptions constituent une partie très importante de l'architecture des processeurs ou des
ordinateurs. Chaque conception d'un processeur à son propre mécanisme d'interruptions,
cependant plusieurs fonctions sont communes. De façon générale, lorsqu'une interruption
survient, le transfert de contrôle vers la routine de service de l'interruption (ISR) est effectuée en
appelant une routine générique qui examine la source de la requête d'interruption (IRQ), cette
routine fait appel à son tour au gestionnaire spécifique de 'interruption. Puisque les interruptions
doivent être exécutées rapidement, et que seulement un nombre prédéfini des interruptions sont
possibles, une table des pointeurs vers les routines d'interruptions est alors généralement utilisée
pour fournir la vitesse d'exécution nécessaire. La routine d'interruption est alors appelée
indirectement à travers cette table. La table des pointeurs est généralement stockée dans la partie
basse de la mémoire (les premiers centaines d'emplacement). Ces emplacements stockent les
adresses des routines de service d'interruptions de divers périphériques. La table d'adresses, aussi
appelée vecteur d'interruption, est indexée par le un numéro unique du périphérique, fourni
ensemble avec la requête d'interruption, permettant ainsi d'obtenir l'adresse de la routine de
service de l'interruption associé à ce périphérique.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 8
Les mémoires secondaires, sont des mémoires non volatiles permettant de stocker aussi bien des
programmes (systèmes et applications) que des données de manière permanente. Elles ont une
grande capacité de stockage et sont en lecture écriture.
La figure ci-dessous donne un aperçu des différentes mémoires que l'on peut trouver dans un
système informatique. Les mémoires les plus proches du CPU sont les plus rapides et les plus
chères par bit.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 9
Les entrées sorties permettent de connecter les périphériques au système informatique. Les
périphériques sont accessibles à l'aide des contrôleurs. Chaque contrôleur est spécifique à un type
des périphériques, et permet de faire l'interface entre le système d'exploitation et le périphérique.
Le contrôleur est responsable du mouvement des données entre le périphérique qu'il contrôle et
ses propres buffers (mémoires tampons). Le système d'exploitation a donc un programme
spécifique appelé "pilote (driver)" pour chaque contrôleur des périphériques. Le pilote fournit une
interface uniforme du système d'exploitation au contrôleur. Pour démarrer une opération entrée-
sortie, le pilote écrit (load) les registres se trouvant dans le contrôleur, ce dernier examine le
contenu de ces registres pour déterminer l'action à prendre, par exemple "lire un caractère en
provenance du clavier", le contrôleur démarre le transfert des données du périphérique vers ses
buffers locaux. Une fois que ce transfert est effectué, le contrôleur du périphérique informe le
pilote via une interruption qu'il a fini sa transaction, le pilote retourne alors le contrôle au système
d'exploitation en renvoyant les données ou un pointeur vers les données s'il s'agit d'une opération
de lecture. Pour les autres opérations, le pilote retourne une information de statut.
Cette approche de pilotage des périphériques par des interruptions est intéressante lorsqu'il s'agit
des petites quantités des données à transférer, cependant lorsqu'il s'agit d'une grande quantité des
données, par exemple, pour des transactions sur disque, le surcout de communications occasionné
lors d'une telle transaction est généralement très élevé si on doit utiliser l'interruption. Pour
résoudre une telle situation, on recourt à l'accès direct en mémoire "DMA" 'Direct Memory
Access). L'opération DMA consiste à accéder directement en mémoire sans passer par le CPU.
En effet, le CPU est impliqué juste avant le démarrage de l'opération, sa participation se limite à
indiquer les buffers concernés, à initialiser les pointeurs et autres compteurs du périphérique, et il
donne la main au contrôleur pour transférer un bloc entier des données directement vers la
mémoire ou provenance de la mémoire vers ses buffers. Une seule interruption est générée par
bloc transféré, pour juste informer le pilote que le transfert est effectué. Pendant le transfert via le
DMA, le processeur est donc disponible pour accomplir d'autres tâches. La figure ci-dessous
illustre le principe du DMA.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 10
Dans certains systèmes informatiques, pour éviter des arbitrages complexes dans les
communications, on utilise carrément des commutateurs ou des routeurs de manière à permettre
des communications directes sans un surcoût d'arbitrage pour l'accès aux ressources partagées
telles que le bus système, la mémoire, etc..
On peut classer les systèmes informatiques en fonction du nombre des processeurs principaux
utilisés pour exécuter le système d'exploitation et les programmes utilisateurs. On distingue alors:
Des systèmes uni-processeur
Des systèmes multiprocesseurs ou multicoeurs ou parallèles
Des systèmes en cluster
Il s'agit des systèmes informatiques à un seul CPU principal. Il existe certainement dans des tels
systèmes d'autres processeurs, mais ceux ci sont inclus dans les contrôleurs des périphériques. Le
CPU principal est le seul responsable pour l'exécution des programmes systèmes et des
utilisateurs. Les systèmes uni-processeur sont de plus en plus rare et se retrouvent essentiellement
dans les systèmes embarqués dont les performances des applications ne nécessitent pas
l'utilisation de plus d'un processeur.
Les systèmes multiprocesseurs, aussi appelés, systèmes parallèles ou multicoeurs, ont supplanté
les systèmes uni-processeur. Ce sont des systèmes informatiques qui ont au moins deux
processeurs principaux pour l'exécution des programmes systèmes et des utilisateurs. Ces
processeurs coopèrent dans l'exécution la réalisation des tâches. Les avantages des systèmes
multiprocesseurs par rapport aux systèmes uni-processeur sont donnés ci-dessous:
Débit élevé ou puissance de calcul élevée: avec plusieurs processeurs impliqués dans
l'exécution d'une tâche, la vitesse d'exécution de la tâche augmente. Cette augmentation
n'est pas proportionnelle au nombre des processeurs impliqués, du fait du coût relatif aux
communications entre processeurs
Fiabilité accrue : La redondance des processeurs permet d'assurer la continuité du service
même si un des processeurs est en défaillance.
Economie d'échelle : Un seul système multiprocesseur à deux CPUs peut couter moins
que deux systèmes uni-processeur pour le même travail.
Les systèmes en cluster regroupent à travers un réseau des systèmes individuels ou nœuds pour
offrir une puissance de calcul élevée comparable à celle des super ordinateurs, tout en
garantissant une gestion globale et une disponibilité de service ininterrompu.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 12
Les systèmes d'exploitation modernes sont multitâches, c'est à dire qu'ils permettent d'exécuter
simultanément plusieurs programmes (processus ou threads) informatiques. En fait il s'agit d'une
exécution concurrente et non parallèle de ces différents programmes. Chaque programme dispose
d'un temps pendant lequel il occupe le CPU, alors que l'utilisateur a l'impression d'une exécution
simultanée. Dans une certaine mesure, notamment pour les systèmes d'exploitation des années
70, le fait de faire tourner plusieurs programmes simultanément, a été dénommée
"multiprogrammation". La différence entre multitâche et multiprogrammation est très subtile.
Dans un système multitâche aussi appelé "temps partagé", chaque processus dispose d'un
quantum de temps pendant lequel il utilise le CPU, la commutation entre les processus est
tellement fréquente qu'elle laisse le temps aux utilisateurs d'interagir avec les programmes. En
fait le temps partagé est une extension logique de la multiprogrammation tout en permettant une
interactivité.
Les systèmes d'exploitation modernes sont pilotés par interruption. Tant qu'il n y a rien à
exécuter, le système d'exploitation attend qu'un événement survienne. Or comme on l'a souligné
précédemment, les événements sont signalés à l'aide d'une interruption ou d'une exception. Une
exception est une interruption logicielle générée lorsqu'une erreur survienne (division par zéro)
ou accès à une zone mémoire invalide) ou par une requête d'un programme utilisateur que le
système d'exploitation doit exécuté (appel système). Puisque le système d'exploitation et les
utilisateurs partagent les ressources matérielles et logicielles du système d'exploitation, il est
évident d'être sûr qu'une erreur provenant d'un programme utilisateur n'affecte que le programme
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 13
d'utilisateur au lieu d'affecter le système d'exploitation. D'autre part, il faut également être en
mesure de distinguer l'exécution du code du système d'exploitation et celle du code des
utilisateurs. Pour ces raisons, la plupart des systèmes informatiques fournissent un support
matériel pour différentier différents modes d'exécution.
Un bit appelé "mode bit" est alors ajouté dans le matériel pour indiquer le mode actuel
d'exécution. La valeur 0 correspond au mode noyau et la valeur 1 correspond au mode utilisateur.
La figure ci dessous illustre les deux modes d'exécution.
Au démarrage, le système est en mode noyau, et quand le système d'exploitation est chargé, il
commence alors à exécuter les programmes utilisateurs en mode utilisateur.
Le fonctionnement en dual mode fournit donc les moyens de protéger le système d'exploitation
contre les erreurs provenant des programmes utilisateurs. La protection est réalisée en désignant
les instructions du jeu d'instructions qui peuvent provoquer des disfonctionnements comme
"instructions privilégiées". Le hardware permet aux instructions privilégiées d'être exécutées
seulement en mode noyau.
Le concept de mode d'exécution peut être étendu au delà de deux modes, notamment pour les
CPUs supportant la virtualisation. Ces CPUs disposent a mode séparé pour indiquer le "Virtuel
Machine Manager" (VMM). Ce mode a plus des privilèges que le mode utilisateur et moins que
le mode noyau.
Un autre mécanisme de protection est le timer, qui permet au système d'exploitation de maintenir
un contrôle sur le CPU. En effet, on ne peut pas se permettre de laisser un programme tourner
indéfiniment dans une boucle infinie ou attendre indéfiniment un service d'appel système sans
jamais retourner le contrôle au système d'exploitation. Dans une telle situation, un timer est
utilisé pour générer une interruption après une certainement période. Une variable timer est
implémentée en utilisant une horloge (clock) et un compter. Le système d'exploitation initialise le
compteur, à chaque coup d'horloge le compteur est décrémenté, quand il atteint zéro, une
interruption est générée. Ainsi avant de passer au mode utilisateur, le système d'exploitation
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 14
s'assure que le timer est configuré pour générer l'interruption. Quand le timer génère
l'interruption, le contrôle est transféré automatiquement au système d'exploitation, qui peut alors
décider de traiter l'interruption comme une erreur fatale ou bien donner encore plus de temps à un
programme.
Un système d'exploitation fournit l'environnement dans lequel les programmes sont exécutés. Il
fournit donc un certain nombre des services aux programmes et aux utilisateurs de ces
programmes. Les services spécifiques fournis dépendent d'un système d'exploitation à un autre,
mais peuvent globalement être regroupés ou identifiés en classes communes. La figure ci-dessous
donne un aperçu des différents services fournis par un système d'exploitation et leur interaction.
La plupart des systèmes d'exploitation offrent une interface utilisateur (User Interface : UI). Celle
ci peut prendre plusieurs formes:
Ligne de commande (Command-Line Interface : "CLI")
Interface Batch
Interface graphique Utilisateur (Gpahical User Interface : "GUI')
La ligne de commande, aussi appelée "terminal" ou shell, utilise les commandes texte saisies à
l'aide du clavier pour les introduire dans le système. Ces commandes introduites sont alors
interprétées ou exécutées par le système. Dans l'interface batch les commandes et les directives
de contrôle de ces commandes sont introduites dans des fichiers, qui sont alors exécutés.
Dans le cas d’UNIX, de nombreux shells sont disponibles (sh, csh, ksh, bash, etc.).Quand un
utilisateur se connecte, un Shell est lancé. Ce Shell a pour entrée standard le clavier de
l'ordinateur, et pour sortie standard son écran. Il commence par afficher un prompt (signe
d’invite), une chaîne de caractères (par exemple un symbole « $ ») qui indique à l’utilisateur que
le Shell est prêt à recevoir une commande. La commande peut être spécifiée comme suit :
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 15
>$ date
Le shell crée un processus enfant qui exécute alors le programme date. Pendant que le fils
exécute, le shell attend sa terminaison. On peut trouver plusieurs descriptions du shell dans les
ouvrages sur UNIX. La figure ci-dessous donne l'aperçu d'un shell ou terminal "Bourne shell ou
bash" sous solaris.
Plus souvent, c'est l'interface graphique qui est utilisée. Il s'agit d'un système des fenêtres avec
un périphérique de pointage pour piloter les entrés-sorties, choisir dans les menus, et faire des
sélections, et un clavier pour introduire du texte. Une interface graphique d'un Ipad est illustrée
sur la figure suivante.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 16
Dans de nombreux systèmes, toute l’information sur chaque processus, hormis le contenu de
l’espace d’adressage, est stockée dans une table nommée table des processus, une ligne pour
chaque processus en cours.
Les principaux appels systèmes (fonctions spéciales du noyau ou services du noyau) pour
la gestion des processus couvrent la création et la disparition des processus.
Une UID particulière, appelée super utilisateur (surtout sous UNIX), possède des
pouvoirs spéciaux et peut violer certaines règles de protection. Dans des grands environnements,
seul l'administrateur système connaît le mot de passe associé à cette UID.
Les interblocages
Les processus dans un système d’exploitation doivent partager les ressources communes
de l’ordinateur (unité centrale, mémoire, périphériques, fichiers, etc.) et attendre si les ressources
nécessaires à leur exécution ne sont pas disponibles. .
Imaginons par exemple que l'ordinateur soit équipé d'un graveur CD-ROM et d'un lecteur
de cartouches, et que deux processus distincts désirent graver un CD-ROM à partir d'une
cartouche. Le processus 1 peut demander l'accès au lecteur de cartouches, qui lui sera accordé.
Pendant ce temps, le processus 2 peut réquisitionner (avec succès) le graveur. Le premier
processus demande ensuite l'accès au graveur, qui lui sera refusé, pendant que le second demande
à accéder au lecteur de cartouches, ce qui provoque un refus. Les deux processus sont bloqués en
attente d'une ressource qu'ils n'obtiendront jamais, puisqu'elle ne sera jamais libérée. Une telle
situation est appelée inter blocage, ou étreinte fatale, ou encore deadlock.
Tout ordinateur possède une mémoire principale qui contient les programmes en cours
d'exécution. Dans les cas les plus simples, seul un programme à la fois peut se- trouver en
mémoire principale. Pour exécuter un second programme, on doit d'abord décharger le premier
puis charger le second. Les systèmes complexes autorisent plusieurs programmes à cohabiter en
même temps en mémoire. Un mécanisme de protection doit alors être mis en place pour les
empêcher d'interférer entre eux et avec le système d'exploitation. Bien que d'origine matérielle, ce
mécanisme est contrôlé par le système d'exploitation. .
Il y a également la gestion de l'espace d'adressage des processus qui est un problème
important résolu par le système d'exploitation. Normalement, chaque processus est autorisée à
utiliser une plage d'adresses, s'étendant en général de 0 à une borne donnée (zone mémoire). Dans
les cas les plus simples, cette plage est de taille inférieure à celle de la mémoire principale. Le
processus peut alors remplir son espace d'adressage, qui tient intégralement en mémoire
principale.
Cependant, sur de nombreux ordinateurs, les adresses sont sur 32 ou 64 bits, ce qui donne
un espace d'adressage de 232 ou 264 mots suivants les cas. Que se passe-t-il si un processus, qui
possède un espace d'adressage supérieur à celui de la mémoire principale décide d'utiliser la
totalité de cet espace? Avec les premiers ordinateurs, un tel processus ne pouvait qu'échouer. De
nos jours, une technique appelée mémoire virtuelle permet au système d'exploitation de garder
une partie sur le disque, et d'assurer les allers-retours nécessaires entre ces deux parties.
Tous les ordinateurs sont munis de périphériques pour l'acquisition de données en entrée
et la production de données en sortie. De nombreux types de périphériques existent (claviers,
écrans, imprimantes, etc.). La gestion de ces périphériques est de la responsabilité du système
d'exploitation. Ainsi, tout système d'exploitation possède un sous-système d'entrées/sorties
responsable des périphériques. Une partie du logiciel est indépendante du périphérique et
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 19
s'applique à plusieurs, voire à la totalité, des périphériques du système. Une autre partie (par
exemple les pilotes) est spécifique à des périphériques particuliers.
Un autre concept clé présent dans quasiment tous les systèmes d'exploitation est le
système de fichiers. L'une des fonctions principales du système d'exploitation est en effet de
masquer les particularités des disques et autres périphériques d'E/S et de présenter au
programmeur un modèle abstrait homogène de fichiers indépendants du périphérique. Il faut des
appels système pour la création et la destruction de fichiers, et les opérations de lecture et
d'écriture. Avant de pouvoir lire un fichier, on doit le trouver sur le disque et l'ouvrir; après l'avoir
lu, on doit le refermer. L'ouverture et la fermeture de fichiers sont aussi faite à l'aide d'appels
système.
La plupart des systèmes d'exploitation utilisent la notion de répertoire (directory) pour
structurer l'espace des fichiers. Il faut aussi disposer d'appel système pour la création et la
suppression de répertoires, l'ajout et la suppression de fichiers dans un répertoire. Les entrées de
répertoire pouvant être des fichiers mais aussi des répertoires. Voir figure Fig. 1.8
Figure 1.9. (a) Avant montage, les fichiers de la disquette sont inaccessibles. (b) après montage, ils sont inclus dans
l’arborescence générale
Dans la partie (a), avant le montage, les deux systèmes de fichiers sont séparés et sans
liens. Les fichiers de la disquette ne peuvent pas être accédés depuis le répertoire racine, car
UNIX ne permet pas d'allouer des lettres ou des chiffres à chaque périphérique d'E/S.
La partie (b) de la figure montre le résultat du montage du système de fichiers de la disquette sur
le répertoire b, permettant l'accès à /b/x et /b/y. Si b contenait des fichiers avant le montage, ceux-
ci deviennent inaccessibles tant que la disquette est montée sur ce répertoire. En général, les
.systèmes de fichiers sont montés sur des répertoires vides.
La notion de fichier spécial est également importante sous UNIX. Leur rôle est de faire
apparaître les périphériques d'E/S comme des fichiers. Ainsi, ils peuvent être lus et écrits à l'aide
des mêmes appels système que ceux utilisés pour les fichiers ordinaires. Il y a deux catégories de
fichiers spéciaux, ceux en mode bloc et ceux en mode caractères. Les fichiers spéciaux en mode
bloc représentent des périphériques consistant en une collection de blocs accessibles de manière
aléatoire, comme les disques. Les fichiers spéciaux en mode caractères servent à représenter les
imprimantes, les modems et autres périphériques traitant des flots de caractères. Par convention,
les fichiers spéciaux sont placés dans le répertoire /dev. Par exemple, /dev/ip représente
fréquemment l’imprimante
La dernière caractéristique à aborder est reliée à la fois aux fichiers : les tubes. Un tube
(pipe) est une sorte de pseudo- fichier que l’on utilise pour relier deux processus, comme le
montre la figure fig. 1.10.
Processus A Processus B
tube
Fig. 1.10. : Deux processus reliés par tube.
1.6.5. La sécurité
L’interface entre le système d’exploitation et les programmes utilisateur est définie par
l’ensemble des appels système fournis par ce dernier (le programme de l'utilisateur). Les appels
système sont des fonctions appelées depuis un programme de l’espace utilisateur dont l’exécution
(le traitement) est effectuée dans l’espace noyau, et dont le retour est effectué dans le programme
appelant dans l’espace utilisateur.
Pour comprendre vraiment ce que fait un système d’exploitation, il faut soigneusement
examiner cette interface. Nous allons faire référence, dans ce qui va être décrit, à POSIX (ISO
9945-1) et donc à UNIX, system V, BSD, Linux, Minix, etc.). Notons que la plupart des systèmes
d’exploitation modernes possèdent des appels système équivalents. L’appel est souvent écrit en
assembleur, une procédure de bibliothèque est fournie afin d’effectuer l’appel système depuis un
programme C.
Prenons l’exemple de l’appel système read() pour lire un fichier, avec trois paramètres :
un pour spécifier le fichier, un pour indiquer où doivent être placées les données lues et un pour
le nombre d’octets à lire. Comme tous les appels système, il est invoqué depuis un programme C
par une fonction de même nom :
paramètre sont appelés par valeur, mais le deuxième est passé par référence : l’adresse du tampon
(et non son contenu) est transmise. L’appel effectif à la fonction à lieu (étape 4). Cette fonction
de bibliothèque, le plus souvent écrite en assembleur, place le numéro de l’appel système à un
endroit convenu, par exemple un enregistre (étape 5). Elle exécute une instruction TRAP pour
basculer en mode noyau et démarrer l’exécution à une adresse fixée du noyau (étape 6). Le code
noyau examine le numéro d’appel système, puis donne la main à l’appel système concerné en
utilisant une table de pointeurs indicée sur les numéros d’appel système (étape 7). Le code de
l’appel s’exécute alors (étape 8). Une fois l’exécution terminée, le contrôle peut être rendu à la
fonction de la bibliothèque (dans l’espace utilisateur), à l’instruction qui suit le TRAP (étape 9).
Cette fonction rend alors le contrôle au programme utilisateur comme procédure ordinaire (étape
10). Ce dernier doit enfin terminer l’opération en nettoyant la pile, comme pour n’importe quelle
invocation de procédure (étape 11).
Fig. 1.11 : Les 11 étapes de réalisation de l’appel système read (df, tampon, nbOctets)
Dans l’étape 9, l’appel système peut bloquer l’appelant, l’empêchant de continuer. Par
exemple, si la lecture se fait depuis le clavier et que rien n’a encore été tapé par l’utilisateur,
l’appelant doit être bloqué. Le système va alors chercher si un autre processus peut s’exécuter.
Plus tard, quand les données d’entrée seront disponibles, ce processus redeviendra candidat et les
tapes 9 à 11 pourront se dérouler.
La figure 1.12 donne quelques principaux appels POSIX. POSIX possède environ 100
appels de procédures. Les services proposés par ces procédures recouvrent la plupart des activités
du système d’exploitation. Ces services recouvrent la gestion des processus, des fichiers et
répertoires, et des entrées/sorties.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 23
Autres
S=chdir(nomrep) Change le répertoire de travail
S=mod(nom, mode) Change le droits d’accès d’un fichier
S=kill(pid, signal) Envoie un signal à un processus
Sec=time(&sec) Renvoie le temps écoulé depuis le 1er janvier 1970)
Le code de retour (statut) s est -1 si une erreur est survenue. Pid est un numéro de processus ; df est un descripteur
de fichier ; n est un nombre d’octets ; pos est un offset dans le fichier ; sec est le temps exprimé en secondes.
Le standard POSIX spécifie un ensemble de procédures que tout système compatible doit
fournir, mais il ne dit pas si ces procédures doivent être des appels système, des fonctions
bibliothèque ou autre chose. Si une procédure peut être exécutée sans invoquer l’appel système
(c’est-à-dire sans basculer en mode noyau) elle sera en général exécutée en mode utilisateur, pour
des raisons de performance. Cela dit, la plupart des appels POSIX provoquent effectivement des
appels système, presque toujours avec un appel système par procédure.
Le premier groupe des appels de la figure 1.12 est relatif à la gestion des processus.
L'appel fork est le seul moyen de créer un processus sous UNIX. Il crée une copie conforme du
processus appelant, jusqu'aux registres et descripteurs de fichiers. Après l'appel, le processus
appelant et la copie (parent et fils) sont autonomes. Toutes les variables ont la même valeur
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 24
initiale dans le parent et le fils, mais un changement de l'une d'elles dans un processus ne se
reflète pas dans l'autre puisque ce sont des copies distinctes (le texte du programme étant
constant, il n'est pas dupliqué). L'appel fork retourne une valeur nulle dans le processus enfant
et égale au PID du fils dans le processus parent. C'est ce qui permet à chaque processus de savoir
qui est le parent et qui est le fils.
Après le fork le fils exécute un code différent du parent. Prenons le cas du shell
(interpréteur de commande). Il lit une commande depuis le clavier, crée un processus enfant,
attend que ce dernier ait fini d’exécuter la commande, puis attend la commande suivante. Pour
attendre la fin du fils, le parent exécute un appel waitpid (qui retourne dès qu’un des enfants se
termine s’il y en a plusieurs). Quand waitpid se termine, son second paramètre reçoit le statut
de sortie du fils terminé. Les options supplémentaires sont offertes par le troisième paramètre.
Comment fork est-elle utilisée par le shell ?
Quand une commande est tapée, l’appel crée un nouveau processus. Ce dernier doit exécuter la
commande utilisateur. Il le fait en invoquant l’appel execve, qui remplace entièrement son
image par celle du binaire dont le nom est en premier paramètre. En fait, l’appel système est
exec, mais il est invoqué par plusieurs fonctions de bibliothèque légèrement différentes les unes
des autres.
Execve a trois paramètres : le nom du binaire à exécuter, un pointeur sur le tableau des
paramètres de la nouvelle commande, et un pointeur sur l’environnement. Les différentes
versions de exec permettent de fournir ces informations de façon variable.
Voyons l’exemple d’un squelette de shell de la figure 1.14 ci-après :
#define TRUE
While(TRUE) { /* boucle sans fin*/
type_prompt() ; /* émission du prompt */
read_commande(cmd, params) /* lecture commande */
if (fork() !=0){ /*création second processus*/
/* proc. Parent. */
waitpid(-1,&statut,0) /* attente fin du fils */
}else{
/* proc. Enfant. */
Execve(cmd,params,0) /* exécution commande */
}
cp fich1 fich2
qui copie le fichier fich1 dans fich2. Après le fork, le processus enfant retourne et exécute le
fichier de cp en lui fournissant les noms des fichiers source et de destination.
Le programme principal de cp (et de la plupart des autres programmes C) contient la déclaration
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 25
main(argc,argv env)
où argc est le nombre de mots sur la ligne de commande (y compris le nom de la commande elle-
même).
Le deuxième paramètre est un tableau dont les éléments sont les mots de la ligne de
commande. Dans notre exemple, argv[0] pointerait sur « cp », argv[1] sur « fich1 » et argv[2]
sur « fich2 ».
Le troisième paramètre est un tableau de chaînes de caractères de la forme
« nom=valeur », utilisé pour transmettre au programme les variables d’environnement (répertoire
de départ, type de terminal, etc.). Si l’environnement n’est pas nécessaire, on passe un pointeur
nul.
Les processus UNIX ont un espace mémoire divisé en trois parties : le segment de texte (c’est-à-
dire le code du programme), le segment de données (les variables) et le segment de pile. Le
deuxième croit vers le haut et le troisième vers le bas de l’espace d’adressage, comme on peut le
voir sur la figure Fig. 1.15.
Adresse (hexa)
FFF
Pile
Trou
Données
Texte
000
Fig. 1.15 : Les processus ont trois segments, le texte, les données et la pile.
De nombreux appels système sont liés au système de fichiers. Pour lire ou écrire un
fichier, il faut d'abord l'avoir ouvert avec open. Cet appel spécifie le chemin (absolu ou relatif) du
fichier à ouvrir et un code (O_RDONL Y, O_WRONL Y, O_RDWR, O_CREAT) précisant la
nature de l'ouverture. Le descripteur de fichier envoyé peut alors être utilisé pour lire et/ou écrire
le fichier. Une fois le fichier refermé via close, le descripteur de fichier pourra être réutilisé par
appel futur à open.
Les appels les plus fréquemment employés sont read et write. Bien que la plupart des
programmes fassent des lectures et écritures sur un mode séquentiel, dans certains cas le
programme a besoin d'accéder aléatoirement à n'importe quelle partie du fichier. Un pointeur est
associé à tout fichier ouvert, indiquant la position courante du processus dans le fichier. En cas de
lecture (écriture) séquentielle, il pointe sur le prochain octet à lire (écrire). L'appel lseek permet
de déplacer ce pointeur de façon à ce que la lecture (écriture) suivante puisse se produire à tout
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 26
Les deux premiers appels, mkdir et rmdir, créent (suppriment) un répertoire vide. L'appel
suivant, link permet au même fichier d'apparaître sous plusieurs noms, souvent dans les
répertoires différents. Un exemple typique d'utilisation est de partager un même fichier dans une
équipe, chaque membre de l'équipe ayant l'impression que le fichier se trouve dans son répertoire.
Il s'agit d'un partage et non d'une duplication du fichier, tout changement par un des membres de
l'équipe étant instantanément visible des autres. Par exemple:
link (/home/jim/memo","/home/jules/note");
Ceci signifie que le fichier memo de jim devient visible dans le répertoire de jules sous le
nom note. Les deux noms référencent désormais le même fichier physique. L'appel mount permet
de fusionner deux systèmes de fichiers en un seul. La situation typique est celle d'un utilisateur
introduisant une disquette dans le lecteur de la machine. L'appel mount permet d'attacher le
système de fichiers de la disquette sur l'arborescence principale.
L'appel chdir permet de changer le répertoire de travail courant. L'appel kill permet aux
utilisateurs d'envoyer des signaux. Si un processus désire gérer la réception d'un signal
particulier, il peut désigner une fonction de gestion à déclencher lors de la réception de ce signal.
Sinon, la réception du signal entraîne la disparition du processus (d'où le nom de l'appel). POSIX
définit quelques procédures pour la gestion du temps. Ainsi time renvoie simplement l'heure
courante sous la forme du nombre de secondes écoulés depuis le 1er janvier 1970 à 0h.
Jusqu'à présent, nous nous sommes concentrés sur UNIX. Jetons maintenant un rapide
coup d'œil à Windows. Les deux systèmes diffèrent de façon profonde dans leur modèle de
programmation. Un programme UNIX comprend du code qui accomplit une tâche donnée et qui,
pour ce faire, a besoin d'effectuer des appels système pour bénéficier de certains services. A
l'inverse, un programme Windows est ordinairement piloté par les évènements. Le programme
principal attend l'occurrence d'un événement quelconque et appelle une procédure de gestion de
cet événement. Les évènements typiques peuvent être la frappe d'une touche de clavier, l'appui
sur un bouton de souris ou l'insertion d'une disquette dans le lecteur. La procédure de gestion
traite l'événement, met à jour l'écran et l'état interne du programme. Cette approche induit donc
un style de programmation assez éloigné de celui utilisé pour UNIX..
Windows possède également des appels système. Sous UNIX, il y a pratiquement un
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 27
mappage 1-1 entre les appels système et les procédures de bibliothèque qui les invoquent. Avec
Windows. la situation est radicalement différente. Les appels de bibliothèque et les appels
système (ils se chiffrent en milliers) sont beaucoup moins étroitement liés. Microsoft a défini un
ensemble de procédures, appelé API Win32 (Application Program Interface, interface de
programmes d'application) que le programmeur doit utiliser pour requérir les services du système
d'exploitation. Cette interface est (partiellement) supportée par toutes les versions de Windows
depuis Windows 95.
Un système aussi large que complexe comme les systèmes d'exploitation actuels doit être
conçu avec soin pour qu'il fonctionne correctement et être facilement modifiable. L'approche la
plus commune dans la conception de tels systèmes est de partitionner la tâche en petits
composants ou modules plutôt que d'avoir un système monolithique. Chacun de ses modules doit
être une portion bien défini du système, avec des entrées, sorties et fonctions soigneusement bien
définies. On va donc distinguer essentiellement deux approches : une approche avec une
structure simple et une approche avec une structure en couche.
Les systèmes d'exploitation de cette famille n'ont aucune structure bien définie, on peut citer le
cas de MS-DOS et des premières version des systèmes UNIX, etc. Dans le cas de MS-DOS, les
interfaces et les niveaux de fonctionnalité ne sont pas bien séparés. Par exemple, les programmes
applicatifs (applications) sont capables d'accéder aux routines d'entrées - sorties pour écrire
directement sur les disques ou sur l'écran. Une telle liberté laisse le système MS-DOS vulnérable
aux programmes malveillants, qui peut amener le crash du système lorsque le programme de
l'utilisateur échoue. Bien évidemment MS-DOS a été aussi limité par le Hardware de l'époque, en
fait le processeur d'Intel 8088 pour lequel il a été écrit ne fournissait pas le mode dual et la
protection matérielle. La figure ci-dessous donne un aperçu de la structure en couche du MS-
DOS.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 28
Pour le cas du système UNIX traditionnel, la structure en couche prévoyait déjà une certaine
extension, elle est séparée en deux parties: Le noyau et les programmes systèmes comme le
montre la figure ci-dessous.
Avec le support matériel adéquat, les systèmes d'exploitation peuvent être divisés en modules
beaucoup plus petits permettant d'avoir un contrôle sur le matériel et les applications tout en
permettant des modifications et des extensions facilement. Une des méthodes pour appliquer la
modularité est l'approche en couches, dans laquelle le système d'exploitation est scindé en
plusieurs couches ou niveaux. La couche basse (couche0) est le matériel, et la couche la plus
élevée (couche N) est la couche d'interface utilisateur. La figure ci-dessous en donne
l'illustration.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 29
Un système d'exploitation en couche est une implémentation d'un objet abstrait composé des
données et des opérations qui manipulent ces données. Une couche M du système d'exploitation
est constituée des structures des données et un ensemble des routines qui peuvent être invoquées
par les couches supérieures, alors que la couche M peut invoquer les opérations des couches
inférieures. Le principal avantage de l'approche en couche est la simplicité de construction et le
débogage. La difficulté majeure réside dans le coût des interactions entre les couches et la
définition de ces couches. Parmi les systèmes d'exploitation en couche, on peut citer le MINIX de
TannenBaum.
L'approche micronoyau consiste à réduire la taille du noyau en y enlevant les fonctionnalités non
essentielles et à les implémenter comme programmes systèmes placés dans l'espace utilisateur. Il
y a cependant un petit consensus concernant les services qui doivent rester dans l'espace noyau et
ceux qui devraient être implémentés dans l'espace utilisateur. Typiquement, les micronoyaux
devraient fournir au minimum l'ordonnancement du processeur (gestion des processus) et la
gestion de la mémoire, ainsi les facilités des communications. La figure suivante montre
l'architecture type d'un micronoyau.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 30
L'approche donnant les meilleures performances est celle qui préconise la conception des
systèmes d'exploitation en utilisant des modules chargeables dans le noyau. Dans cette approche,
le noyau a un ensemble des composants de base et joint d'autres services additionnels à travers
des modules soit au démarrage ou pendant le fonctionnement. Cette approche est adoptée dans la
plupart des systèmes d'exploitation modernes tels que Windows et les variantes du système
UNIX ( Solaris, Linux, Mac OS X).
L'idée dans cette approche est que le noyau fournisse les services de base alors que les autres
services sont implémentés dynamiquement pendant que le noyau s'exécute. Lier les services
dynamiquement est préférable à l'ajout des nouvelles caractéristiques directement au noyau, ce
qui pourrait nécessiter une recompilation du noyau chaque fois qu'un changement est effectué.
Par exemple, on pourrait compiler le noyau avec les algorithmes d'ordonnancement du CPU et de
gestion de la mémoire, et par la suite ajouter le support des différents systèmes de fichier par le
moyen des modules chargeables.
Le résultat global ressemble à un système en couche dans la mesure où chaque section du noyau a
des interfaces bien définies et protégées, mais plus flexible que le système en couche du fait que
chaque module peut appeler n'importe quel module. L'approche est aussi similaire à l'approche
micronoyau du fait que le module principal a seulement des fonctions de base et la connaissance
de la manière de charger et communiquer avec les autres modules; cependant il est plus efficace,
puisque les modules n'ont pas à invoquer le passage des messages pour communiquer. la figure
suivante montre la structure du système d'exploitation Solaris, organisé autour d'un nouyau de
base et 7 types des modules noyau chargeables.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 31
Le système d'exploitation Linux utilise aussi les modules chargeables, principalement pour
supporter les pilotes et les systèmes des fichiers.
En pratique, peu des systèmes d'exploitation adoptent une seule structure strictement définie. En
fait, ils combinent différentes structures, produisant des systèmes hybrides qui résolvent les
problèmes de performance, de sécurité et de facilité d'utilisation. Par exemple, Linux et Solaris
sont monolithiques, puisque avoir le système d'exploitation dans un seul espace d'adresses fournit
une performance efficace. Cependant, ils sont modulaires, de sorte que toute nouvelle
fonctionnalité peut être dynamiquement chargé dans le noyau. Le système d'exploitation
Windows est aussi largement monolithique pour des raisons de performance, mais il garde
certains comportements se rapportant au systèmes micronoyaux, comme par exemple le support
pour les sous systèmes séparés, connus sous le nom de "operating-system personalities", qui
tournent comme processus utilisateur. Windows supporte aussi les modules noyau chargeables.
Pour terminer cette section, nous donnons ci-dessous les structures des différents systèmes
d'exploitations. Le lecteur peut consulter des ouvrages spécialisés pour approfondir les structures
se rapportant à chaque système.
1.7.5.1 Windows 7
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 32
1.7.5.2 Linux
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 33
1.7.5.3 Mac OS X
1.7.5.4 iOS
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 34
1.7.5.5 Android
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 35
CHAPITRE 2
PROCESSUS ET THREADS
Le concept central de tout système d'exploitation est le processus. Un processus est une
abstraction d'un programme en cours d'exécution.
Une des caractéristiques principales des systèmes d'exploitation est l'existence d'activités
évolutives simultanées plus ou moins étroitement couplées. Tout en exécutant un programme
utilisateur, l'ordinateur peut effectuer des lectures sur disque dur, afficher du texte à l'écran ou en
envoyer vers l'imprimante. Dans un système multiprogrammé, le processeur bascule également
entre les programmes, pour les servir à raison de quelques dizaines ou centaines de millisecondes.
Soient deux programmes distincts Pet Q qui ont chacun en mémoire un segment
procédure et un segment de données. Appelons p et q les processus résultant de l'exécution
respective de ces deux programmes.
L'exécution de l'ensemble (p,q) peut se dérouler de diverses manières caractérisées par des
formes particulières de sa trace temporelle c’est-à-dire la succession des états de la machine
repérée dans le temps (ou histoire du processus). On peut avoir les schémas suivants:
p
(1) + + q
+ +
(2) p q p q p
p
(3) q
Les systèmes d'exploitation ont besoin de savoir que tous les processus nécessaires
existent bel et bien. Lors de l'amorçage du système d'exploitation, plusieurs processus sont créés.
Lors de sa création, un processus reçoit un numéro fixe qui sert à le désigner, et permet
d’accéder à son bloc de contexte. Celui comprend :
- une zone de sauvegarde du mot d’état du processeur ;
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 37
Certains processus sont des processus de premier plan, à savoir des processus qui
interagissent avec l'utilisateur et accomplissent des tâches pour lui. D'autres processus sont des
processus d'arrière-plan, non associés à une utilisation particulière de l'ordinateur. Ces processus
ont des fonctions particulières. Par exemple, un processus d'arrière-plan conçu pour accepter les
courriers entrants.
Les processus qui restent à l'arrière-plan pour gérer des activités qui concernent les
courriers électroniques, les pages Web, les news, les impressions, etc. s'appellent des démons
(daemons).
Sous Unix, le programme ps sert à afficher la liste des processus en cours d'exécution.
Plusieurs champs sont également affichés pour chacun des processus. Le champ UID indique le
nom du propriétaire du processus ; PID (process Id) indique le numéro du processus; PPID
(parent PID) indique le numéro du processus père (celui qui a créé le processus PID), STME
indique l'heure de lancement du processus; TTY indique le terminal ou la fenêtre du processus;
CMD indique la commande qui a permis de lancer le processus.
Sous la gamme Windows, le fait de taper Ctrl-Alt-Del (une seule fois) permet de voir le
gestionnaire des tâches.
Au-delà des processus créés lors de l'amorçage, de nouveaux processus peuvent être créés
après coup. Il arrive souvent qu’un processus en cours d’exécution émette des appels système
pour créer un ou plusieurs nouveaux processus qui l’aideront dans son activité.
Sur les systèmes interactifs, les utilisateurs peuvent démarrer un programme en saisissant
une commande ou en (double) cliquant sur une icône. L’une ou l’autre de ces actions lance un
nouveau processus qui exécute le programme concerné.
Techniquement, un nouveau processus est créé du fait qu’un processus existant exécute un
appel système de création de processus.
Sous UNIX, un seul appel système permettant de créer un nouveau processus est l’appel
fork, qui crée un clone du processus appelant. Après l’appel fork, les deux processus, parent et
enfant, ont la même image mémoire et les mêmes fichiers ouverts.
Sous Windows, un seul appel de fonction Win32, CreateProcess, prend en charge à la fois
la création du processus et le chargement du programme appropriée dans nouveau processus. Cet
appel prend dix paramètres, et notamment le programme à exécuter, les paramètres de la ligne de
commande destinés au programme, différents attributs de sécurité, des bits de contrôle permettant
de vérifier l’héritage des fichiers ouverts, des informations de priorité, la déclaration de la fenêtre
que le processus doit créer et un pointeur vers une structure contenant les informations relatives
au processus nouvellement créé à retourner l’appelant.
Tant sous UNIX que sous Windows, une fois qu’un processus a été créé, le parent et le
fils disposent désormais de leur propre espace d’adressage. S’il arrive que l’un des processus
modifie un mot dans son espace d’adressage, le changement n’est pas visible par l’autre
processus. Sous UNIX, l’espace d’adressage initial du fils est une copie de celui de parent, mais il
existe deux espaces d’adressage distincts, et il n’y a pas de mémoire partagée en écriture
(certaines implémentations d’UNIX partagent le texte du programme entre les deux processus
dans la mesure où il n’est pas modifiable). En revanche, il est possible qu’un processus
nouvellement créé partage certaines ressources avec son créateur, comme c’est le cas des fichiers
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 38
ouverts. Sous Windows, les espaces d’adressage du parent et du fils sont différents dès le début.
La notion de processus et les opérations associées ne font pas habituellement pas partie du
répertoire de base d’une machine. Elles doivent être mises en œuvre par un ensemble de
programmes et/ou microprogramme dont l’ensemble constitue le noyau de gestion des processus.
On peut dire que la notion du processus dissimule aux utilisateurs du noyau, le mécanisme
d’allocation des processus physiques.
Une fois qu’un processus a été créé, il commence à s’exécuter, quelle que soit sa tâche.
Mais tôt ou tard, le nouveau processus s’arrête pour divers raisons :
- arrêt normal (volontaire) ;
- arrêt par erreur (volontaire) ;
- arrêt pour erreur fatale (involontaire) ;
- le processus est arrêté par un autre processus (involontaire).
Sur certains systèmes, lorsqu’un processus crée un autre processus, les processus parent et
enfant continuent d’être associés d’une certaine manière. Le processus enfant peut lui-même
créer plusieurs processus, formant une hiérarchie de processus.
Sous Unix, un processus ainsi que l’ensemble de ses enfants et de ses descendants successifs
forment un groupe de processus.
Sous Unix, lors de son démarrage, un processus spécial, appelé init, est présent dans
l’image d’amorçage. Lorsqu’il s’exécute, il lit un fichier indiquant combien de terminaux sont
présents. Ensuite, il génère un nouveau processus terminal. Ces processus attendent une ouverture
de session (login). Si l’une d’elles réussit, le processus de login exécute un shell pour accepter
des commandes. Ces commandes peuvent lancer d’autres processus, et ainsi de suite. Ainsi, tous
les processus de l’ensemble du système appartiennent à une arborescence unique, dont init est la
racine.
A la différence d’UNIX, Windows n’intègre pas le concept de hiérarchie des processus.
Tous les processus sont égaux. Le seul moment où l’on trouve une certaine hiérarchie est celui de
la création du processus. A ce moment-là, le parent récupère un jeton spécial (handle) qu’il peut
utiliser pour contrôler le fils. Cependant, il peut passer ce handle (jeton) à un autre processus, ce
qui invalide la hiérarchie.
Bien que chaque processus constitue une entité indépendante, avec son propre compteur
ordinal et son état interne, certains processus ont besoin d'entrer en interaction avec d'autres.
Soit deux programmes distincts P et Q qui ont chacun en mémoire un segment procédure
et un segment de données. P est un programme d'écriture dans un segment mémoire a et Q est un
programme de lecture du segment mémoire a modifié par q. Appelons p et q les processus
résultant de l'exécution respective de ces deux programmes. Le processus p transmet de
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 39
l'information au processus q en écrivant dans le segment a consulté par q. Pour qu'il y ait
cohérence des données lues par le processus q, la lecture du segment par q ne peut avoir lieu
avant la fin de l'écriture par p du segment.
Si q tente de lire le segment a avant la fin de l’écriture, il peut arriver qu’il n’y ait aucune
donnée à lire. A ce moment, q doit être bloqué jusqu’à ce qu’une donnée soit disponible, c’est-à-
dire jusqu’à ce que p ait terminé à écrire sur le segment a
Le processus à ce moment se bloque parce que, logiquement, il ne peut poursuivre son
exécution. En général il attend une entrée non encore disponible. Il se peut qu’un processus
conceptuellement prêt à s’exécuter et en mesure de le faire soit interrompu parce que le système
d’exploitation a décidé d’allouer le processeur à un autre processus. Sur les systèmes
multiprocessus, qui sont des systèmes qui permettent aux utilisateurs de réaliser plusieurs tâches
à la fois, le CPU est partagé par plusieurs processus créés par les différents utilisateurs. Le
système intercale l’exécution des processus, laissant à chacun la possibilité d’utiliser
périodiquement le CPU. Il faut alors définir un ordre pour l’allocation du processus au
processeur. C’est l’ordonnancement qui détermine le processus auquel est accordé le contrôle du
CPU. A la figure 2.1, on peut voir un diagramme montrant les trois états que peut prendre un
processus :
(1) Elu ou en cours d’exécution (c’est-à-dire utilisant le processeur en cet instant).
(2) Prêt (exécution temporairement arrêté pour laisser s’exécuter un autre processus). Il lui
manque le processeur.
(3) Bloqué (ne pouvant pas s’exécuter tant qu’un évènement externe ne se produit : bloc disque,
frappe clavier, etc.).
Fig. 2.1 : Un processus peut être en cours d'exécution, bloqué ou prêt. Les transitions entre les états, apparaissent
dans cette figure.
Logiquement, les deux premiers états sont analogues. Dans les deux cas, le processus est
prêt à s'exécuter, mais dans le deuxième état, le processeur est provisoirement indisponible. Le
troisième état est différent des deux autres dans le sens que le processus ne peut pas s'exécuter,
même si le processeur n'a rien d'autre à faire.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 40
Comme le montre la figure 2.1 , quatre transitions sont possibles entre ces trois états. La
transition 1 se produit lorsqu'un processus s'aperçoit qu'il ne peut pas poursuivre son exécution.
Les transitions 2 et 3 sont des transitions technologiques liées à l'allocation des processeurs
physiques aux processus. Cette transition est provoquée par l’ordonnanceur de processus qui est
un programme qui détermine le processus auquel est accordé le contrôle du processeur. La
transition 2 se produit lorsque l'ordonnanceur juge que le processus en cours d'exécution a eu
suffisamment de temps pour s'exécuter, et qu'il est temps de laisser un autre processus bénéficier
du temps processeur; cette opération s'appelle réquisition (en anglais : preemption). La transition
3 a lieu lorsque tous les autres processus ont profité du temps processeur et qu'il est l'heure pour
le premier processus de pouvoir s'exécuter. L'ordonnancement consiste donc à choisir le
processus à exécuter et la durée de cette exécution.
La transition 4 (réveil) est provoquée lorsque l'événement externe attendu par le processus
se produit. Il peut s'agir de l'arrivée d'une donnée quelconque. Si aucun autre processus n'est en
cours d'exécution à cet instant, la transition 3 est déclenchée et le processus commence à
s'exécuter. Dans le cas contraire, le processus doit rester pendant un certain temps en état prêt,
jusqu'à ce que le processeur redevienne disponible et que son tour arrive d'être traité.
Grâce au modèle de processus, il devient plus facile de se représenter ce qui se passe à
l'intérieur du système. Certains processus exécutent des programmes qui comprennent des
commandes saisies par l'utilisateur. D'autres font partie du système et gèrent des tâches telles que
le transport de requêtes pour les services de fichiers ou la gestion des détails de l'exécution d'un
disque. Lorsqu'une interruption de disque se produit, le système prend la décision d'arrêter
l'exécution du processus en cours d'exécution et exécute le processus du disque (qui était bloqué
dans l'attente de cette interruption). Ainsi, au lieu de penser en termes d'interruptions, on peut
réfléchir en termes de processus utilisateur, de processus disque, de processus terminal, etc., qui
se bloquent lorsqu'ils attendent un événement.
La gestion des processus fait appel à des files d'attente. Elle peut être représentée par le
modèle de la figure 2.2.
Processus
0 1 2 …….. n-2 n-1
Ordonnanceur
Fig. 2.2: La couche inférieure d'un système d'exploitation structuré en processus gère des interruptions et prend en
charge l'ordonnancement. Viennent s'y superposer les processus séquentiels.
numéro de processus, l’allocation de mémoire, l’état des fichiers ouverts, ordonnancement, ainsi
que toute information relative aux processus devant être enregistrée lorsque le processus bascule
de l'état en cours d’exécution vers les états prêt ou bloqué. La figure 2.3 illustre les champs les
plus importants que l’on retrouve dans les systèmes classiques. Les champs de la première
colonne sont liés à la gestion du processus. Les deux autres concernent respectivement la gestion
de la mémoire et celle des fichiers.
Fig.2.5 : Résumé des tâches que le système d'exploitation accomplit à son niveau le plus bas lorsqu'une interruption
a lieu
Même dans le cas de machines monoprocesseurs les threads se révèlent utiles. Créer un
processus est très onéreux. Lorsqu'un serveur doit répondre à de nombreuses requêtes un temps
précieux est donc perdu à créer un processus pour répondre à chacune d'entre elles. Les threads
sont beaucoup plus économiques puisqu'ils partagent un environnement unique qui ne doit donc
pas être initialisé pour chacun d'entre eux. La figure 2.6 (a) montre trois processus traditionnels.
Chacun a son propre espace d'adressage et un thread de contrôle unique. La figure 2.6 (b)
représente un processus unique avec trois threads de contrôle.
Thread Threads
Noyau Noyau
(a) (b)
Ayant décrit les threads, nous pouvons maintenant expliquer pour quelles raisons on peut
avoir besoin des threads. Dans de nombreuses applications, des activités multiples ont lieu
simultanément. Certaines de ces activités peuvent se bloquer de temps en temps. En décomposant
une application en plusieurs threads séquentiels qui vont s'exécuter quasiment en parallèle, le
modèle de programmation devient plus simple. C'est celui qui explique l'existence même des
processus. Au lieu de penser interruptions, timers et commutateurs de contexte, nous pouvons
raisonner en termes de processus parallèles. Mais maintenant avec les threads on ajoute un
élément nouveau: la capacité pour les entités parallèles à partager un espace d'adressage et toutes
les données. Autre argument en faveur des threads : étant donné qu'aucune ressource ne leur est
associée, ils sont plus faciles à créer et à détruire que les processus. Sur de nombreux systèmes, la
création d’un thread est une opération plus rapide que celle d’un processus.
Voyons un exemple concret permettant de percevoir l’utilité des threads. Prenons
l’exemple suivant : un serveur de sites Web. Les requêtes de pages arrivent et les pages sollicitées
sont retournées au client. Sur la plupart des sites Web, certaines pages sont plus souvent visitées
que d'autres. Les serveurs Web peuvent améliorer leurs performances en maintenant une
collection de pages souvent demandées dans leur mémoire principale, ce qui élimine la nécessité
d'un accès au disque pour les consulter. Une telle collection s'appelle un cache.
Fig. 2. 7 (a) Un paquetage de threads au niveau utilisateur. (b) Un paquetage de threads pris en charge par le noyau
Lorsque les threads sont gérés dans l’espace utilisateur, chaque processus a besoin de sa
propre table de thread privée pour le suivi des threads du processus. Cette table est analogue à la
table des processus du noyau, mais elle ne concerne que les propriétés des threads, comme le
compteur ordinal, le pointeur de pile, les registres, l’état, etc. La table des threads est gérée par le
système d’exécution (run time system).
Supposons maintenant que le noyau ait connaissance des threads et en assure la gestion.
Il n’est pas nécessaire de disposer d’un système d’exécution pour chacun ; comme le montre la
figure 2.13(b). En outre, il n’y a pas de table des threads dans chaque processus. C’est le noyau
qui possède une table des threads chargée du suivi de tous les threads du système. Lorsqu’un
nouveau thread veut créer ou détruire un thread existant, il effectue un appel noyau qui prend
alors en charge la création ou la destruction en actualisant la table des threads du noyau.
Plusieurs processus peuvent travailler sur un même problème, et étant donnés que ces
processus s'exécutent en concurrence (sur des monoprocesseurs) ou parallèle (multiprocesseurs et
ordinateurs distants), il est donc nécessaire qu'ils s'échangent des informations. Il existe donc des
mécanismes permettant aux processus de communiquer et de s'échanger des informations. Parmi
ces mécanismes, on peut citer entre autres, les variables communes, les fichiers communs, les
signaux, les messages et les tubes (pipe) de communication.
Les variables et fichiers communs peuvent être accédés en lecture et écriture par tous les
processus concernés, ainsi des problèmes peuvent survenir lorsque plusieurs processus essaient
d'accéder en même temps à ces ressources communes, des précautions doivent donc être prises
pour éviter la corruption des données. Les mécanismes prévus pour ce faire seront abordés dans
la section traitant de la synchronisation des processus. La ressource commune ou l'objet commun
à plusieurs processus, est appelée "ressource critique", et la portion du code du processus qui
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 46
Les signaux sont des interruptions logicielles que le système d'exploitation utilise pour
communiquer l'occurrence d'un événement aux processus utilisateurs. Les processus utilisateurs
peuvent indiquer aux processus systèmes le comportement à adopter en cas lors d e l'occurrence
de l'événement. Dans une certaine mesure, les processus utilisateurs peuvent ignorer le signal, ou
laisser le système d'exploitation mettre en œuvre le comportement prévu par défaut, qui consiste
généralement à tuer le processus. Certains signaux ne peuvent être ni ignorés, ni capturés.
Comme les interruptions matérielles, les signaux ont également une routine de service, ou une
action par défaut. Dans Unix, les types de ces actions par défaut sont donnés ci-dessous:
A : terminaison du processus
B : ignorer le signal
C : créer un fichier core
D : stopper le processus
E : la procédure de service ne peut être modifiée
F : Le signal ne peut être ignoré
Chaque signal est identifié au moyen d'un numéro entier positif. Le tableau ci-dessous décrit
quelques signaux utilisés sous Linux.
Il existe deux types de tubes de communications : les tubes sans nom (unamed pipe) et les tubes
nommés (named pipe). Les tubes permettent d'établir des communications unidirectionnelles
entre deux processus s'exécutant sur une même machine. pour assurer des communications
bidirectionnelles, il faut alors utiliser deux pipes sans nom. Les pipes sans nom ont une capacité
approximativement égale à 4 Ko. Ils peuvent être créés par le shell ou par l'appel système pipe().
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 47
Les tubes nommés sont plus intéressants que les tubes sans nom, ils offrent une grande capacité,
autour de 40 Ko, ils ont chacun un nom qui existe dans le système des fichiers, ils sont
considérés comme des fichiers spéciaux. Ils existent jusqu'à ce qu'ils soient supprimés
explicitement. Ils fonctionnent aussi comme des fichiers de type FIFO.
Les sockets ou prises sont des mécanismes permettant d'établir des communications entre des
processus s'exécutant sur des machines différentes connectées par un réseau de communication.
Par exemple, on utilise les sockets pour imprimer un fichier se trouvant sur une autre machine et
pour transférer un fichier d'une machine à l'autre.
Voyons les deux exemples suivants qui vont nous aider à formuler les contraintes
logiques imposées par la coopération. .
Exemple 1: Le processus p transmet de l'information au processus q en écrivant dans un
segment a consulté par q. On doit avoir:
fin(écrire (a) < deb(lire(a))
Ceci signifie que la lecture de a par q ne peut commencer avant la fin de l'écriture par p.
<début_j>;
<rendez-vous>
<suite_j>
Ainsi donc les contraintes de synchronisation peuvent s'exprimer sous les deux formes
équivalentes suivantes :
- On impose un ordre de précédence, dans le temps logique, sur certains points de la trace
temporelle des processus,
- On impose à certains processus une condition pour autoriser le franchissement de certains
points de leur trace temporelle.
Ces points privilégiés sont appelés points de synchronisation. On voit que les contraintes
de synchronisation peuvent être satisfaites en imposant à un processus « d 'attendre », pour
exécuter une action, qu'une certaine condition soit satisfaite. Le processus est donc mis dans un
état d'attente. Il est en attente, ou bloqué [dans cet état le processus est en attente, soit d'une
ressource qui lui manque (imprimante, espace mémoire ...), soit qu'il attend une interruption].
Sinon le processus est en cours d'exécution [le processus contrôle le processeur]. Un processus
qui entre dans l'état d'attente, à partir d'un point d'observable t, arrête sa progression en ce point et
cesse d'exécuter les actions. Lorsque le processus revient dans l'état actif, il reprend son
exécution, et son contexte privé retrouve l'état qu'il avait au point t. La transition actif attente
s’appelle blocage et le réveil est la transition inverse.
Nous allons donc utiliser la notion d'attente pour spécifier la synchronisation entre
processus. Cette spécification se fait en deux étapes:
1. Définir, pour chaque processus, ses points de synchronisation;
2. Associer à chaque point de synchronisation une condition de franchissement, exprimée au
moyen de variables d'état du système. Illustrations: Reprenons nos deux exemples précédents.
Nous notons ps un point de synchronisation. aut(ps) la condition de franchissement associé. Si
cette condition est vraie, le processus concerné est donc autorisé à exécuter l'instruction étiquetée
par ps. .
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 49
aut(ps): f=vrai
si e=non_arrivé alors
état(p) := bloqué
fsi {p est mis en "attente"}
Lorsqu'un é.m. reçoit la valeur arrivé, tous les processus en attente de e, s'il en existe, passe à
l'état actif. Revoyons nos deux exemples.
Exemple 1:
var e:événement_mémorisé;
processus p processus q
<suite_p) lire(a)
La synchronisation est correctement assurée car les opérations sur les é.m. sont indivisibles.
Exemple 2:
var e:événement_ mémorisé;
n:entier init 0;
processus pi
<début_i);
(A) n:=n+1;
Spécification du problème
Compte tenu de ces spécifications, nous chercherons à construire une solution de la forme:
On dit qu'un processus est en attente active lorsque ce processus simule l'effet de
l'opération de blocage en effectuant un test répété sur la condition de franchissement, qui peut
être mise à jour par d'autres processus. Le processus est maintenu ainsi toujours en état actif. Il
est toujours en cours d'exécution.
La solution la plus simple pour réaliser l'attente active est que chaque processus désactive
toutes les interruptions juste après son entrée dans la section critique, et qu'il les réactive juste
après l'avoir quittée. Si les interruptions sont désactivées, l'horloge ne peut envoyer
d'interruptions. Le processeur ne peut basculer d'un processus à un autre que s'il reçoit des
interruptions d'horloges des autres. L'exclusion mutuelle est réalisée à travers la mise en œuvre de
primitives du système d'exploitation afin qu'elles désactivent et activent les interruptions. L'accès
à une section critique peut être contrôlé en appelant ces primitives.
Desableinterrupt()
// section critique
Enablelnterrupt ()
Si aucun appel système n'est émis dans la section et qu'aucun déroutement ne survient, le
processus qui entre dans la section critique conserve le contrôle du processeur alors qu'il se
trouve dans la section critique garantissant son accès exclusif mutuel. Ce mécanisme est très
facilement mis en œuvre dans le logiciel. Il présente cependant des inconvénients majeurs:
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 52
Mais cette approche de donner aux processus utilisateurs le pouvoir de désactiver les
interruptions n'est pas très judicieuse. Qu'adviendrait-il s'il ne les réactivait jamais? Cela
donnerait le glas pour tout système.
Pour traiter par attente active le cas où plusieurs processus doivent mettre à jour et
consulter des variables communes, certaines machines possèdent une instruction qui réalise de
manière indivisible la consultation et la mise à jour du contenu d'un emplacement de mémoire,
appelé verrou ou lock. Cette instruction, souvent appelée Test And Set Lock (TSL), tester et
définir le verrou, peut également être utilisée sur les multiprocesseurs.
C'est une solution logicielle. Elle fonctionne de la manière suivante: supposons une
variable unique, partagée (un verrou) dont la valeur initiale est 0. Lorsqu'un processus tente
d'entrer dans sa section critique, il commence par tester le verrou. Si celui-ci est à 0, le processus
le positionne à 1 et entre en section critique. Si le verrou est déjà à 1, le processus attend qu'il
passe à 0. Ainsi, 0 signifie qu'aucun processus ne se trouve dans la section critique, et un 1
implique la présence d'un processus dans la section critique.
Exemples de programmes.
Programme en pseudo-langage
On peut alors programmer l'exclusion mutuelle par attente active, au moyen des
séquences suivantes:
épilogue : stz m
Enter_region :
TSL REGISTER, LOCK [copie lock dans le registre et la définit à 1]
CMP REGISTER, # 0 [lock était-elle à 0 ?]
JNE enter_region [si elle n'était pas à 0, boucle]
RET [retourne à l'appelant; entre en section critique]
Leave_region
MOVE LOCK, #0 [stocke un 0 dans lock]
RET [retounre à l'appelant
Cette solution logicielle présente un inconvénient majeur. Supposons qu'un processus lise le
verrou et constate qu'il est 0. Avant qu'il n'ait pu la positionner à 1, un autre processus planifié
s'exécute et le fait à sa place. Lorsque le premier processus reprend son exécution, il positionne
également le verrou à 1, et les deux processus entrent dans leurs sections critiques simultanément.
Alternance stricte
T. Dekker fut le premier à mettre au point une solution logicielle à l'exclusion mutuelle,
ne faisant pas appel à l'alternance stricte. G.L. Peterson découvrit une méthode plus simple pour
obtenir le même résultat, rendant obsolète la solution de Dekker.
Il se compose en deux procédures développées en C ANSI, ce qui signifie que les
prototypes de fonctions doivent être fournis pour toutes les fonctions et utilisées. Cependant, pour
des raisons de place, nous ne reproduisons pas les prototypes dans cet exemple et les suivants.
#define FALSE 0
#define TRUE 1
#define N 2 /* nombre de processus */
int turn ; /* à qui le tour ? */
int interested(N) ; /* toutes valeurs initialement 0
0 (FALSE)
void enter_region(int process) ; /* le processus est 0 ou 1 */
{
int other ; /* nombre des autres processus */
other = 1 – process ; /* l’opposé du processus*/
interested[process]= TRUE /* montre que vous êtes intéressé */
while (turn==process&&interested[other]==TRUE
/* intruction NULL */
}
void leave_region(int process) /* processus : qui quitte */
{
Interested[process]= FALSE ; /* indique départ de la section
Critique */
}
Fig. 2.11 : Solution de Peterson pour l’exclusion mutuelle
Avant d’utiliser les variables partagée ( à savoir d’entrer en section critique), chaque
processus appelle enter_region avec son propre numéro de processus, 0 ou 1, en tant que
paramètre. Cet appel le met en attente, si nécessaire, jusqu’à ce qu’il puisse entrer. Une fois qu’il
en a terminé avec les variables partagées, le processus appelle leave_region pour autoriser
un autre processus à entrer.
Voyons comment fonctionne cette solution. Au départ, aucun des processus ne se trouve
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 55
dans sa section critique. C’st alors que le processus 0 appelle enter_region. Il montre son
intérêt en définissant son élément de tableau et en positionnant turn à 0. Etant donné que le
processus 1 n’est pas intéressé, enter_region retourne immédiatement. Si le processus 1
appelle enter_region, il attend jusqu’à ce que interested[0] passe à FALSE,
évènement qui ne peut se produire qu’une fois que le processus 0 aura appel leave_region
pour quitter la section critique.
Prenons maintenant le cas de figure où les deux processus appellent enter_region
simultanément. Tous deux vont stocker leur numéro de processus dans turn. C’est l’opération de
stockage la plus tardive qui est pris en compte ; la première est remplacée et perdue. Supposons
que le processus 1 soit stocké en dernier, ce qui fait que turn est à 1. Lorsque les deux
processus arrivent à l’instruction while, le processus 0 ne l’exécute pas et entre en section
critique. Le processus 1 boucle et n’entre pas en section critique tant que le processus 0 n’a pas
quitté la sienne.
Les solutions par attente active sont bonnes mais elles ont pour inconvénient de
consommer inutilement du temps processeur. En effet, voici ce qu'elles proposent: lorsqu'un
processus souhaite entrer dans sa section critique, il vérifie si la « porte» est ouverte. Si ce n'est
pas le cas, le processus s'installe dans une petite boucle en attendant l'ouverture.
Voici quelques effets indésirables de cette approche. Prenons un ordinateur avec deux
processus: H, de priorité supérieure, et, L, de priorité inférieure. Les règles d'ordonnancement
font que. H s'exécute chaque fois qu'il se trouve en état prêt. A un moment donné, alors que L est
dans sa section critique, H se trouve prêt à l'exécution (par exemple, il a terminé une opération
E/S. H entre en attente active. Mais, étant donné que L ne peut pas être ordonnancé tant que H
est en cours d'exécution, L n’ a jamais l'occasion de quitter sa section critique et H boucle sans
fin. C'est ce qu'on appelle parfois le problème de l'inversion des priorités.
Il existe cependant quelques primitives de communication interprocessus qui bloquent au
lieu de consommer du temps processeur lorsqu'elles n'obtiennent pas l'autorisation d'entrer dans
leur section critique. L'une des plus simples fonctionne avec la paire sleep et wakeup. sleep
est un appel système qui provoque le blocage de l'appelant. Celui-ci est suspendu jusqu'à ce qu'un
autre processus le réveille. L'appel wakeup prend un paramètre, désignant le processus à
réveiller. Il arrive également que sleep et wakeup prennent tous deux un paramètre qui est une
adresse mémoire employée pour relier les sleep et les wakeup entre eux.
Problème du producteur-consommateur
- une opération "impossible" (dépôt dans un tampon plein ou retrait depuis un tampon vide)
bloque le processus qui tente de l'exécuter.
Le sémaphore a été proposé par le Hollandais E.W. Dijkstra comme une variable
permettant de contrôler les accès à des ressources communes (partagées). Un sémaphore est une
variable entière, qui à part son initialisation, ne peut être accédée que par deux opérations
atomiques (indivisibles) nommées wait() et signal(). L’opération wait() correspond à la primitive
P et l’opération correspond à la primitive V, tels que les a définis E.W. Dijkstra. La variable
entière sémaphore est en fait un compteur qui représente le nombre d’autorisations d’accès à une
section critique.
Les sémaphores sont donc manipulés au moyen des primitives wait() et signal().
L’opération Wait(S) ou P(S) décrémente la valeur courante du sémaphore S si cette dernière est
supérieure à 0, sinon le processus appelant est mis en attente. Elle est définie comme ci-dessous :
En pratique, le sémaphore est implémenté comme une structure, dont les éléments sont une
valeur entière, et une structure qui est une file d’attente ou une liste des processus.
Partant de cette implémentation, les primitives wait() et signal() peuvent donc redéfinies pour
s’aligner à la définition ci-dessus du sémaphore. Un processus en attente d’un sémaphore est
ajoutée dans la liste des processus.
Suivant cette définition, la valeur du sémaphore peut être négative, alors que dans la définition
classique avec attente active, la valeur du sémaphore est strictement positive. Lorsque la valeur
du sémaphore est négative, sa valeur absolue représente le nombre des processus en attente.
Linux dispose de la bibliothèque <semaphore.h> qui permet de créer et d’utiliser les sémaphores.
Le type sémaphore est noté sem_t. Les fonctions ci-dessous sont pourvues :
int sem_init(sem_t *sem, int pshared,unsigned int valeur):
intialisation d’un semaphore, sem est un pointeur sur le sémaphore à initialiser; value est la
valeur initiale du sémaphore ; pshared indique si le sémaphore est local au processus
pshared=0 ou partagé entre le père et le fils pshared ≠ 0. Actuellement Linux ne supporte pas
les sémaphores partagés.
int sem_wait(sem_t *sem) :
est équivalente à l’opération wait() ou P: retourne toujours 0.
int sem_post(sem_t *sem) :
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 59
Les sémaphores Posix servent donc à synchroniser les communications entre threads. Les
sémaphores d’Unix System V sont un autre type de mécanisme qui permet la synchronisation
entre processus. Sa gestion étant un peu plus complexe.
La solution par sémaphore n'élimine pas tous les problèmes posés par l'exclusion mutuelle. Les
principales difficultés rencontrées dans la pratique sont:
Les sémaphores résolvent le problème des wakeup perdus, comme le montre la figure
2.12. Il est essentiel qu'ils soient implémentés de façon indivisible. La méthode habituelle
consiste à implémenter up (V) et down (P) en tant que appels système. Le système d'exploitation
désactive toutes les interruptions pendant un court laps de temps durant lequel il teste le
sémaphore, l'actualise et place si nécessaire le processus concerné en sommeil. L'ensemble de ces
actions ne prend que quelques instructions et aucun dommage ne découle de la désactivation des
interruptions. Si plusieurs processeurs sont utilisés, chaque sémaphore doit être protégé par une
variable verrou, avec l'instruction TSL, pour s'assurer qu’un seul processus à la fois sonde la
valeur du sémaphore.
#include <semaphore.h>
#include <unistd.h>
#include <pthread.h>
#include <stdio.h>
#define taille 3
sem_t plein, vide, mutex;
int tampon[taille] ;
pthread_t cons, prod;
void consommateur(void) ;
void producteur (void) ;
int main()
{
//initiliser les sésmaphores
sem_init(&plein, 0 , 0 ) ;
sem_init(&vide, 0 , taille ) ;
sem_init(&mutex, 0 , 1 ) ;
//créer les threads
pthread_create(&cons ,NULL, consommateur ,NULL) ;
pthread_create(&prod ,NULL, producer ,NULL) ;
// attendre la fin des threads
pthread_join(prod,NULL) ;
pthread_join(cons,NULL) ;
printf ( " fin des threads \n" ) ;
return 0 ;
}
void* consommateur(void *)
{
int ic = 0, nbcons = 0, objet;
do {
sem_wait(&pl e in ) ;
sem_wait(&mutex ) ;
// consommer
objet = tampon[ic] ;
sem_post(&mutex) ;
sem_post(&vide) ;
printf ( "ici cons. : tampon[%d]= %d\n", ic, objet);
ic =(ic +1)% taille;
nbcons++;
sleep (2) ;
} while(nbcons <=5);
return (NULL) ;
}
void* producteur(void *)
{
int ip=0, nbprod=0, objet=0;
do {
sem_wait(&vide);
sem_wait(&mutex);
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 61
// produire
tampon[ip]= objet;
sem_post(&mutex);
sem_post(&plein);
printf ( " ici prod. : tampon[%d]= %d\n", ip, objet);
objet++;
nbprod++;
ip =(ip+1)%taille;
} while (nbprod<=5);
return NULL;
}
a. Définition
Moniteur sample
{
// Déclaration des variables
int i;
condition c;
//l Déclaration des. fonctions
void CriticalSectionEntryPoint(1)
{.
// Code de fonction
}
void CriticalSectionEntryPoint(2)
{
// Code de fonction
}
sample
{
// Code de fonction
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 62
}
// Code d’initialisation
}
}
Les conditions de blocage et de réveil sont exprimées en fonction des variables d'état, et le
mécanisme d'exécution du moniteur garantit que ces variables sont manipulées en exclusion
mutuelle. Enfin, un moniteur contient un programme d'initialisation, exécutée une fois et une
seule lors de la création du moniteur.
Le blocage et le réveil des processus s'expriment, dans les procédures du moniteur, au
moyen de condition. Une condition est déclarée comme une variable, mais n'a pas de "valeur".
Deux opérations sont autorisées sur les variables condition c au moyen des primitives: c.attendre
(c.wait) et c.signaler (wsignal. La fonction à valeur booléenne c. vide n'est testée que pour savoir
si oui ou non un processus est en attente.
Un processus réveillé par c.signaler reprend son exécution à l'instruction qui suit
immédiatement le primitive c.attendre qui l'a bloqué. La nécessité d'assurer l'exclusion mutuelle
aux variables d'état impose une contrainte supplémentaire sur le mécanisme de réveil: lorsqu'un
processus p réveille un processus q par une opération signaler, p et q ne peuvent être maintenus
simultanément actifs.
b. Exemples d’utilisation
Exemple 1:
sync: moniteur;
var fait:booléen;
fini:condition;
procédure fin_écrire;
début
fait: = vrai
fini. signaler
fin
procédure début_lire; si l fait alors
fini.attendre
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 63
fsi
'.'
début {initialisation}
fait:= faux
fin
fin sync
Processus p Processus q
Exemple 2
rendez-vous: moniteur;
var n : entier;
tousJà:condition;
procédure arriver,
début
n:=n+1
si n<N alors
tous_là.attendre {pas tous arrivés}
fsi;
tous_là.signaler {le dernier est là}
fin;
début {initialisation}
n:=O
fin
fin rendez_vous
processus pi
<début i>
rendez. vous arriver;
<suite i>
Le processus qui arrive le dernier au rendez-vous exécute tous_là.signaler et réveille un
des processus qui attendent, et un seul. Ce dernier, à son tour, exécute tous_là. signaler, réveillant
le suivant, et ainsi de suite.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 64
moniteur exemple
integer i ;
condition c ;
procedure producteur 0 ;
end;
procedure consommateur 0 ;
end;
end moniteur;
Les procédures peuvent appeler les procédures d'un moniteur chaque fois qu'ils le
souhaitent, mais ils ne peuvent pas accéder directement aux structures de données internes du
moniteur à partir de procédures déclarées à l'extérieur du moniteur. Les moniteurs ont une
propriété importante qui les rend intéressants pour faire de l'exclusion mutuelle : à un instant
donné, un seul processus peut être actif dans le moniteur. Les moniteurs sont des constructions du
langage de programmation, ce qui fait que le compilateur sait qu'ils sont spécifiques : il gère les
appels aux procédures de moniteur différemment des autres appels. Généralement lorsqu'un
processus appelle une procédure du moniteur, les premières instructions déterminent si un autre
processus est actuellement actif au sein du moniteur. Si c'est le cas, le processus appelant est
suspendu jusqu'à ce que l'autre processus ait quitté le moniteur. Sinon, il peut y entrer.
C'est au compilateur qu'il revient d'implémenter l'exclusion mutuelle sur les entrés dans le
moniteur, mais il est courant d'employer un mu tex ou un sémaphore binaire.
Malgré tout l'intérêt quant à l'exclusion mutuelle, les moniteurs ne suffisent pas. Il nous
faut également faire en sorte que les processus se bloquent lorsqu'ils ne sont pas en mesure de
poursuivre. Dans le contexte du producteur-consommateur, il est relativement aisé de placer tous
les tests d'état du tampon (plein, vide, etc.) dans des procédures de moniteurs, mais comment
bloquer le producteur s'il trouve un tampon plein ?
La solution consiste à introduire des variables conditionnelles prenant en charge deux
opérations: wait et signa1. Lorsqu'une procédure de moniteur découvre qu'elle ne peut se
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 65
poursuivre (le producteur apprend que le tampon est plein), elle effectue un wait sur une
variable conditionnelle, que nous appellerons full. Cette action provoque le blocage du
processus appelant. Elle permet à un autre processus, qui s'était vu auparavant interdire l'entrée
dans le moniteur, d'y entrer maintenant. Cet autre processus, par exemple le consommateur, peut
réveiller son partenaire en sommeil en envoyant un signal sur la variable conditionnelle que son
partenaire attend et en prenant soin de quitter le moniteur pour éviter que deux processus ne
soient actifs dans le moniteur.
Les variables conditionnelles ne sont pas des compteurs. Elles n'accumulent pas les
signaux pour une utilisation ultérieure, à la manière des sémaphores. Ainsi, si une variable
conditionnelle est signalée alors que personne ne l'attend, le signal est perdu pour toujours. En
d'autres termes, wait doit intervenir avant signal. La figure 2.15 donne l'articulation du code
pour illustrer le problème du producteur-consommateur avec les moniteurs.
Fig.2.15 : Résoudre le problème du producteur-consommateur avec les moniteurs. Une seule procedure de moniteur
est active à un moment donné. Le tampon possède N emplacements.
Moniteur ProducleurConsommateur
condilion full, empty() ;
integer count; "
procedure insert (item: integer);
begin
if count = n then wait (full);
insert_item(item);
count := count + 1;
if count + 1 then signal(empty)
end;
procedure remove(item :integer)
begin
if count = 0 then wait (empty);
remove_item(item);
count := count - 1;
if count = N - 1 then signal (full)
end;
count := 0;
end moniteur;
procedure producteur
begin
while true do
begin
item = produce_item;
Producte urConsommat eur. insert (item)
end
end;
procedure consommateur
begin
while true do
begin
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 66
item = ProducteurConsommateur.remove;
consume_item(item)
end
end
En automatisant l'exclusion mutuelle des sections critiques, les moniteurs rendent la
programmation parallèle nettement moins sujette aux erreurs qu'avec les sémaphores. Mais ils
présentent tout de même quelques inconvénients. Les moniteurs sont un concept de langage. Le
compilateur doit les reconnaître et prendre en charge d'une manière ou d'une autre l'exclusion
mutuelle. Le C, le Pascal et la plupart des autres langages n'ont pas de moniteurs. Avec les
moniteurs, il faut un langage qui les prenne en charge.
Les moniteurs posent un autre problème, également valable en ce qui concerne les
sémaphores. Ces deux notions ont été développées pour résoudre le problème de l'exclusion
mutuelle sur un ou plusieurs processeurs ayant tous accès à une mémoire commune.
Lorsque l'on passe sur un système distribué composé de plusieurs processeurs, chacun
disposant de sa propre mémoire et connecté en réseau local, ces primitives deviennent
inapplicables. On peut en conclure que les sémaphores sont des outils de trop bas niveau et que
les moniteurs ne sont pas praticables, exceptés dans quelques langages. En outre, aucune des
primitives ne permet de faire de l'échange d'informations entre ordinateurs. Il nous faut autre
chose.
et:
Le premier appel envoie un message vers une destination donnée, et le second reçoit un message
d'une source donnée. En l'absence de message disponible, le récepteur peut se bloquer jusqu'à ce
que celui-ci arrive. Il peut également retourner immédiatement un code d'erreur.
Dans le système d'échange de messages, les messages peuvent être perdus par le réseau.
Pour se prémunir contre les pertes de messages, l'émetteur et le récepteur peuvent décider que,
dès qu'il a reçu un message, le récepteur envoie un accusé de réception (acknowledgement). Si
l'émetteur n'a pas reçu d'accusé de réception passé un certain délai, il retransmet le message.
Les systèmes fondés sur les messages doivent également gérer la manière dont sont
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 67
nommés les processus, de façon qu'un processus spécifié dans les appels send ou receive ne
génère pas d'ambiguïté. L'authentification est également un problème lié à l'échange de messages:
comment le client peut-il savoir à coup sûr qu'il communique avec le véritable serveur de
fichiers, et non avec un imposteur?
void producer(void)
{
int item; /* tampon de messages*/
message m ;
while (TRUE) {
item = produce_item() ; /* génère quelque chose à placer dans
le tampon*/
receive(consumer, &m) ; /*attend l'arrivée d'un message vide*/
build message(&m,item) ; /*constuit un message à envoyer*/
send(consumer,&m); /*envoie l'élément au consommateur*/
}
{
void consumer (void)
{
int item, i ;
message m ;
for (i =0 ; i<N ;i++) send(producer, &m) ; /*envoie N messages vides*/
while (TRUE) {
receive(producer, &m) ; /*récupère un message contenant un
élément,* /
item = extract item(&m) ; /* extrait l'élément du message*!
send(producer,&m) ; /*retourne une réponse vide*/
consume item(item) ; /* utilise l'élément*/
}
}
Nous supposons que les messages sont tous de la même taille et que les messages émis
mais non encore reçus sont automatiquement mis en mémoire tampon par le système
d'exploitation. Dans cette solution on a un total de N messages. Le consommateur commence par
émettre N messages vides en direction du producteur. Chaque fois que le producteur possède un
élément à remettre au consommateur, il prend un message vide et renvoie un message plein. De
cette manière, le nombre total de messages reste constant au sein du système, ce qui permet de les
stocker dans un volume de mémoire déterminé à l'avance. Si le producteur travaille plus
rapidement que le consommateur, tous les messages finissent par être pleins; le producteur est
bloqué, en attente d'un message vide de retour. Si le consommateur est plus rapide, la situation
inverse se produit: tous les messages sont vides; le consommateur est bloqué dans l'attente d'un
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 68
message plein.
Il existe de nombreuses variantes d'échange de messages. Pour commencer, voyons
comment sont adressés les messages. Une méthode consiste à assigner à chaque processus une
adresse unique et à faire en sorte que les messages soient adressés aux processus. Une autre
solution consiste à inventer une nouvelle structure de données que l'on appellera mailbox (boîte
aux lettres). Celle-ci permet de placer dans le tampon un certain nombre de messages,
généralement spécifié lors de la création de la mailbox. Lorsque l'on utilise les mailbox, les
paramètres d'adressage des appels send et receive déclarent des mailbox, et non des
processus. Quand un processus tente d'émettre en direction d'une mailbox pleine, il est suspendu
jusqu'à ce qu'un message disparaisse de la mailbox, laissant de la place pour un nouveau
message.
A l'autre extrême, on peut éliminer toute opération de mise en mémoire tampon. Avec
cette approche, si le send est effectué avant le receive, le processus émetteur est bloqué
jusqu'à ce que receive s'exécute, moment où le message pourra être copié directement depuis
l'émetteur vers le récepteur, sans tampon intermédiaire. De même, si le receive intervient
d'abord, le récepteur est bloqué jusqu'à l'exécution d'un send. C'est ce que l'on appelle souvent la
stratégie du rendez-vous. L'échange de messages est souvent exploité dans les systèmes de
programmation en parallèle. Le MPI (Message-Passing Interface) en est une réalisation bien
connue, largement employée en informatique scientifique.
Considérons maintenant un fichier manipulé par des processus de deux classes différents:
les lecteurs, qui consultent le fichier sans modifier son contenu, et les rédacteurs, qui peuvent
modifier ce contenu. Soit à tout instant nlect et nred le nombre respectif de lecteurs et de
rédacteurs utilisant une procédure d'accès au fichier. Le maintien de la cohérence du fichier nous
amène à imposer les contraintes suivantes:
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 69
Soit fich un moniteur chargé d'assurer le respect de ces contraintes. Nous imposons la forme
suivante aux accès au fichier.
Processus processus
lecteur rédacteur
fich.début_lire; fich.début écrire;
<accès en lecture> <accès en écriture>
fich.fin_écrire ; fich.fin_lire ;
Les procédures début_lire, ..., fin_écriture doivent assurer le respect des contraintes
exprimées ci-dessus. Nous allons d'abord traduire ces contraintes en autorisation de
franchissement; il faut pour cela préciser les règles de priorité entre lecteurs et rédacteurs.
A titre d'exemple, supposons que la priorité soit donnée aux lecteurs (une écriture n'est
pas autorisée si des lecteurs sont en attente). Nous définissons les variables d'état suivantes:
ecr = une écriture est en cours (booléen)
nl= nombre de lecteurs en attente ou en cours de lecture
flch : moniteur
var ecr : booléen;
nl : entier
c_ecr, c_lect:condition ;
procédure début_lire ;
début
nl := nl + 1 ;
si ecr alors
c_lect. attendre;
c_lect.signaler [réveil en chaîne des lecteurs]
fsi
fin
procédure fin_lire
debut
nl := nl- 1 ;,
si nl=0 alors [le dernier lecteur a fini]
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 70
c_ecr.signaler
fsi
fin
procédure fin_écrire ;
début
ecr: = faux;
si nl>O alors [priorité aux lecteurs en attente]
c_lect. signaler
sinon
c_ecr.signaler .
fsi
fin;
début [initialisation]
ecr : = faux;
nl := 0
fin fich
Sur les anciens systèmes de traitement par lots (utilisant les cartes perforées ou les bandes
magnétiques pour les entrées), l’algorithme d’ordonnancement était simple : on prenait le job
suivant sur la bande. Avec les systèmes en temps partagé, l’algorithme d’ordonnancement est
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 71
devenu complexe, car on trouve généralement plusieurs utilisateurs en attente de service. Certains
mainframes aujourd’hui combinent encore des services de traitement par lots et en temps partagé,
ce qui oblige l’Ordonnanceur à décider s’il va d’abord choisir job le traitement par lots ou un
utilisateur interactif sur un terminal.
Avec l’avènement des ordinateurs personnels, la situation a évolué de deux manières.
Premièrement, il n’y a le plus souvent qu’un seul processus actif. Un utilisateur saisissant un
document sur un traitement de texte ne va sans doute pas compiler un programme simultanément
à l’arrière-plan. Lorsque l’utilisateur adresse une commande au traitement de texte,
l’Ordonnanceur n’a pas grand-chose à faire pour déterminer le processus à exécuter : le
traitement de texte est le seul candidat.
Deuxièmement, les ordinateurs sont devenus si rapides avec les années que le processeur
n’est plus une ressource rare. La plupart des programmes développés pour les PC sont limités par
la vitesse à laquelle est capable de présenter des entrées (en tapant ou en cliquant), et non par
celle à laquelle le processeur peut les traiter.
Si nous nous tournons vers les stations de travail en réseau et les serveurs haut de gamme,
la situation change. Ici, plusieurs processus se disputent du temps processeur, ce qui donne tout
son intérêt à l’ordonnancement. Par exemple, lorsque le processeur doit choisir entre exécuter un
processus qui rafraîchit l’écran après que l’utilisateur a fermé une fenêtre et en exécuter un qui
envoie un courrier électronique dans une file d’attente, cela fait une grosse différence au niveau
du temps perçu : une fermeture de fenêtre de 2 secondes pendant l’envoie du courrier
électronique pourrait paraître trop long pour l’utilisateur.
Outre le fait de sélectionner le bon processus à exécuter, l’ordonnancement doit également
se soucier de faire un usage efficace du processeur, car les passages d’un processus à l’autre sont
couteux en termes de temps de traitement : temps pris pour le basculement du mode utilisateur en
mode noyau, temps pris pour la commutation de contexte, temps d’enregistrement du mappage
mémoire, etc.
Pratiquement tous les processus alternent les rafales de traitement et les requêtes d'E/S (disque),
comme le montre la figure 2. 17.
Fig. 2. 17: Rafales d'utilisation du processeur alternant avec des périodes d'attente d'E/S. a} un
processus de traitement, b) Un processus d'E/S.
appel système est effectué pour accéder à un fichier en lecture ou en écriture. Lorsque l'appel
système est achevé, le processeur recommence un traitement jusqu'à ce qu'il ait besoin de
données supplémentaires ou qu'il faille écrire des données, et ainsi de suite.
Comme l'indique la figure 2.17, certains processus (a) passent le plus clair de leur temps à
faire du traitement, tandis que d'autres, (b), sont le plus souvent en train d'attendre des E/S. Les
premiers sont appelés processus de traitement, les seconds sont les processus d'E/S.
Quand ordonnancer?
Premièrement, lorsqu'un nouveau processus est créé. Il faut décider s'il faut exécuter
d'abord le processus parent ou le processus enfant. Etant donné que les deux processus sont en
état prêt, il s'agit là d'une décision d'ordonnancement normale.
Deuxièmement, lorsqu'un processus se termine. Un autre processus doit être choisi dans le
jeu de processus prêts.
Troisièmement, lorsqu'un processus bloque sur des E/S, un sémaphore ou autre, un autre
processus doit être sélectionné pour être exécuté. Il peut arriver que la raison du blocage joue un
rôle dans ce choix.
Quatrièmement, lorsqu'une interruption d'E/S se produit. Si l'interruption provient d'un
périphérique d'E/S qui vient de terminer son travail, tout processus qui était bloqué en attente
d'E/S peut désormais être exécuté. C'est à l'Ordonnanceur de décider si le processus à l’état prêt
doit être exécuté ou s'il faut donner priorité à celui qui était en cours d'exécution au moment de
l'interruption.
Si l'horloge matérielle fournit des interruptions périodiques à une fréquence de 50 ou 60
Hz, par exemple, une décision d'ordonnancement peut être prise à chaque interruption d'horloge
ou à chaque k ième interruption.
On peut classer les algorithmes d'ordonnancement en deux catégories selon leur manière
de réagir aux interruptions d'horloges. Un algorithme d'ordonnancement non préemptif
sélectionne un processus, puis le laisse s'exécuter jusqu'à ce qu'il bloque (soit sur une E/S, soit en
attente d'un autre processus) ou qu'il libère volontairement le processeur. Cette approche
correspond aux besoins des travaux par lots.
Par opposition, un algorithme d'ordonnancement préemptif sélectionne un processus et le
laisse s'exécuter pendant un délai déterminé. Si le processus est toujours en cours à l'issue de ce
délai, il est suspendu, et l'ordonnancement sélectionne un autre processus à exécuter.
L'ordonnancement préemptif nécessite une interruption à la fin du délai afin de redonner le
contrôle du processeur à l'Ordonnanceur. En l'absence d'horloge, l'ordonnancement non préemptif
est la seule solution.
Dans les systèmes de traitement par lots, les algorithmes non préemptifs, ou les
algorithmes préemptifs réservant de longs délais aux processeurs sont suffisants pour réduire le
nombre de changements de processus et améliorer les performances.
Dans les environnements comptant des utilisateurs interactifs, la préemption est
essentielle pour empêcher un processus donné de s’emparer du processeur et d’en refuser l’accès
à d’autres.
Dans les systèmes devant intégrer des contraintes de temps réel, la préemption est parfois
inutile, car les processus savent qu’ils ne doivent pas s’exécuter pendant de longues périodes. Ils
font leurs travails et se bloquent rapidement.
Systèmes interactifs
Temps de réponse : répondre rapidement aux requêtes
Proportionnalité : répondre aux attentes des utilisateurs
Dans le cas d’un algorithme d’ordonnancement non préemptif, les politiques ci-dessous
sont généralement utilisées :
La politique «Premier arrivé, premier servi» (en anglais «First Come, First Served) », ou
FCFS) utilise une file unique, sans priorité ni réquisition. Le processus élu s'exécute jusqu'à son
terme, et le prochain élu est le processus en tête de file. Un nouvel arrivant entre en queue de file.
Dans la politique du « Plus court d'abord » (en anglais « Shortest Job First » ou « SJF »,
les processus sont ordonnés dans la file d'attente selon leur temps de service supposé connu à
l'avance, les processus les plus courts étant en tête.
Sur le plan pratique, la politique SJF présente deux inconvénients: elle présente un risque
de privation pour les processus longs si le taux d'arrivées des processus court est élevé et elle
nécessite une connaissance exacte à priori des temps de service.
Les stratégies FCFS et SJF sont bien adaptées pour les systèmes « Batch » ou « Lot des
processus », dans la mesure où le temps de traitement maximal des processus est fixé par les
utilisateurs. Le temps de séjour d'un processus (temps de rotation ou de virement) est l'intervalle
de temps entre la soumission du processus et son achèvement.
On peut évaluer les performances de ces stratégies à l’aide des métriques telles que le temps de
séjour de chaque processus, le temps moyen de séjour, le temps d’attente et le temps moyen
d’attente.
Pour illustration, considérons, un lot de 5 processus dont les données d’ordonnancement sont
reprises dans le tableau suivant :
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 75
Time 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Process A A A B B B B B B C C C C D D E
Le temps de séjour pour chaque processus est obtenu en faisant la soustraction entre le temps de
terminaison et le temps d’entrée du processus. On obtient donc :
3+8+9+9+9
Le temps moyen de séjour est donc = 7,6
5
Le temps d’attente est calculé en faisant la soustraction entre le temps de séjour et le temps
d’exécution.
0+2+5+7+8
Le temps moyen d’attente est donc = 4,4
5
16
Vu qu’il y a 16 unités de temps pour exécuter 5 processus, on a donc en moyenne = 3,2
5
unités de temps par processus.
Si on applique ces deux politiques pour un système multiutilisateurs à temps partagé, c'est-à-dire,
un système interactif. Chaque processus se comporte comme suit : il attend une commande,
l'exécute, attend la commande suivante, et ainsi de suite. Alors parmi les processus prêts, le
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 76
processus élu est celui dont la commande à exécuter est la plus courte en temps. Le temps
d'exécution de la prochaine commande de chaque processus est estimé en se basant sur le
comportement passé du processus : Si 𝑇0 est le temps d'exécution estimé pour la première
commande et 𝑇𝑖 le temps d'exécution mesuré pour la ieme commande, les estimations
successives sont :
Les algorithmes non préemptif ne sont donc pas indiqués pour les systèmes multiutilisateurs à
temps partagé car les temps de réponse ne sont toujours pas acceptables.
1) La politique du temps restant le plus court (ou Shortest Remaining Time, SRT)
Il s'agit d'une version préemptive de l'algorithme consistant à prélever le job dont le temps
d'exécution restant est le plus court parmi ceux qui restent à exécuter. Chaque fois qu'un nouveau
processus est introduit dans le pool de processus à ordonnancer, l'Ordonnanceur compare la
valeur de temps de traitement restant à celle du processus en cours d'ordonnancement. Si le temps
de traitement du nouveau processus est inférieur, le' processus en cours d'ordonnancement est
préempté. Tout comme l'algorithme SJF, l'algorithme SRT favorise les travaux courts; les travaux
longs en revanche peuvent être victimes de famine.
Un raffinement du modèle du tourniquet, qui vise à réduire encore le temps de service des
travaux courts, est le tourniquet multi niveaux ou algorithme à file multi niveaux à retour
(Multilevel feedback queues, MFQ). Ce modèle comporte n files d'attente Fo, ...,Fn-1. A chaque
file Fi est associé un quantum Qi, dont la valeur croit avec i. Un travail de Fi n'est servi que si les
files de numéro inférieur à i sont toutes vides. Lorsqu'un travail issu de Fi a épuisé son quantum
sans être terminé, il entre dans la file Fi+1; les travaux issus de Fn-1 retournent dans cette file. Les
nouveaux travaux entrent dans Fo qui est le niveau le plus élevé.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 78
Le processus sélectionné par l'algorithme MFQ est le prochain processus de la file la plus
élevée contenant des processus. Généralement, la sélection au sein d'une file suit
l'ordonnancement FCFS. Les travaux tributaires des E/S demeurent dans les files de hauts
niveaux, dans lesquelles elles reçoivent une priorité supérieure aux processus tributaires du
processeur des files des niveaux inférieur. .
CHAPITRE III
INTERBLOCAGE
Les ordinateurs ont de nombreuses ressources, mais elles peuvent servir qu'à un seul
processus à la fois. On peut citer par exemple les imprimantes, les dérouleurs de bandes et les
entrées dans les tables internes du système.
Pour de nombreuses applications, les processus n'ont pas besoin d'un accès à une seule
ressource; ils doivent pouvoir accéder à plusieurs ressources. Supposons, par exemple, que deux
processus souhaitent chacun enregistrer un document numérisé sur un CD. Le processus 𝑃1
demande une permission pour utiliser le scanner, laquelle lui est accordée. Le processus 𝑃2 est
programmé différemment et sollicite d'abord une permission du graveur de CD, laquelle lui est
également accordée. Maintenant, A sollicite le graveur de CD mais la requête est refusée jusqu'à
ce que 𝑃2 le libère. Malheureusement. au lieu de libérer le graveur, 𝑃2 sollicite le scanner. A ce
stade, les deux processus sont bloqués et le resteront indéfiniment. C'est ce que l'on appelle inter
blocage (deadlock).
Les inter blocages peuvent également se produire entre ordinateurs. Par exemple, dans un
réseau d'ordinateurs, les périphériques tels que les scanners, les graveurs de CD, les imprimantes
et les dérouleurs de bandes sont des ressources partagées du réseau, disponibles pour tous les
utilisateurs et tous les ordinateurs. L'inter blocage peut se produire lors de l'utilisation de ces
ressources.
Autre situation d'inter blocage possible. Dans un système de gestion de base de données,
par exemple, un programme peut avoir à verrouiller plusieurs enregistrements qu'il utilise pour
éviter qu'ils entrent en concurrence. Si le processus 𝑃1 verrouille l'enregistrement R1 et que le
processus 𝑃2 verrouille l'enregistrement R2, puis que chaque processus tente de verrouiller
l'enregistrement de l'autre processus, nous sommes également en présence d'un inter blocage.
Ainsi, les inter blocages peuvent se produire aussi bien sur des ressources matérielles que
logicielles.
3.1. Ressources
Les inter blocages peuvent se produire lorsque des processus se sont vus accorder un
accès exclusif à des périphériques, des fichiers, etc.
Nous désignerons par ressources les objets alloués. Il peut s'agir d'un périphérique
physique ou d'une information. Donc pour nous, une ressource représente tout ce qui peut être
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 80
II existe deux types de ressources: retirables et non retirables (on les appelle parfois
ressources préemptibles et non préemptible). Une ressource retirable peut être retirée sans
dommages du processus auquel elle appartient. La mémoire est un exemple de ressource
retirable.
A l’opposé, une ressource non retirable ne peut être enlevée au processus auquel elle
appartient sans que le traitement échoue. Si un processus a commencé à graver un CD-ROM, le
fait de lui retirer subitement le graveur pour l'attribuer à un autre processus ne peut donner de
bons résultats.
En règle générale, les inter blocages impliquent des ressources non retirables.
Voici, sous forme résumée, la séquence d'événements nécessaires pour utiliser une ressource:
1. Sollicitation de la ressource.
2. Utilisation de la ressource
3. Libération de la ressource.
Pour certains types de ressources tels que les enregistrements d’une base de données, il
incombe à l'utilisateur de gérer lui-même l'emploi des ressources. Pour ce faire, il est possible
d'associer un sémaphore à chaque ressource. Ces sémaphores sont tous initialisés à 1. Il est
également possible d'employer des méthodes de synchronisation de type mutex. Les trois étapes
répertoriées ci-dessus peuvent alors être implémentées en tant que down sur le sémaphore pour
acquérir la ressource et l'utiliser, et en tant que up sur la ressource pour la libérer. La figure 3.1
illustre ces étapes.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 81
Fig. 3.1. Utiliser un sémaphore pour protéger les ressources. (a) Une ressource. (b) deux ressources.
(a) (b)
Fig.3.2. : (a) Code exempt d'interblocage. (b) Code contenant un interblocage potentiel.
Dans la figure 3.2 (a), l'un des processus acquiert la première ressource avant l'autre. Il va
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 82
donc obtenir la seconde ressource et accomplir son travail. Si l'autre processus tente d'acquérir la
ressource 1 qu'avant qu'elle ne soit libérée, l'autre processus sera tout bonnement bloqué jusqu'à
ce que celle-ci soit disponible.
Dans (b), la situation est différente. Il peut arriver que l'un des processus acquière les deux
ressources et bloque effectivement l'autre processus jusqu'à ce qu'il ait terminé. Toutefois, il peut
également arriver que le processus A acquière la ressource 1 et que le processus B acquière la
ressource 2. Chacun va alors se bloquer en tentant d'acquérir la ressource de l'autre et aucun des
deux processus ne pourra plus s'exécuter. Cette situation est un interblocage.
Il a été démontré qu’un interblocage devait remplir les quatre conditions suivantes :
1. Condition d’exclusion mutuelle : chaque ressource est soit attribuée à un seul processus,
soit disponible.
2. Condition de détention et d’attente : les processus ayant déjà obtenu des ressources
peuvent en demander de nouvelles.
3. Pas de réquisition : les ressources déjà détenues ne peuvent être retirées de force à un
processus. Elles doivent être explicitement libérées par le processus qui les détient.
4. Condition d’attente circulaire: il doit y avoir un cycle d’au moins deux processus,
chacun attendant une ressource détenue par un autre processus.
Ces quatre conditions sont nécessaires pour produire un interblocage. S’il en manque une,
aucun inter blocage n’est possible.
En 1972, Holt a démontré de quelle façon il était possible de modéliser ces quatre
conditions au moyen de graphes orientés. Ces graphes possèdent deux types de nœuds : des
processus, illustrés par des cercles, et des ressources, représentées par des carrées. Un arc allant
d’une ressource (carré) à un processus signifie que cette ressource a déjà été demandée et
attribuée, et qu’elle est actuellement détenue par ce processus. Dans la figure 3.3 (a), la ressource
R est actuellement attribuée au processus A.
Fig. 3.3. : Graphes d’attribution des ressources. (a) détient une ressource. (b) demande
Un arc allant d’un processus à une ressource signifie que le processus est bloqué en
attendant cette ressource. Dans (b), le processus attend la ressource S. Dans (c), nous nous
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 83
trouvons en face d’un interblocage : le processus C attend la ressource T qui est actuellement
détenue par le processus D. Ce dernier ne va pas libérer la ressource U détenue par C. Les deux
processus attendront indéfiniment.
Voyons par exemple comment utiliser les graphes de ressources. Imaginons que nous
ayons 3 processus, A, B, et C, et 3 ressources R, S, et T.
La figure 3.4 (a) indique les demandes et les libérations de ces 3 processus. Le système
d'exploitation est libre d'exécuter à tout moment tout processus non bloqué. Il peut donc choisir
d'exécuter A jusqu'à ce que A ait accompli toutes ses tâches, puis d'exécuter B de même pour
enfin exécuter C. Cet ordonnancement n'aboutit à aucun interblocage (car les ressources ne sont
pas en concurrence) mais il ne présente aucun parallélisme.
.
Supposons à présent que les processus accomplissent à la fois des opérations d'E/S et des
calculs, de sorte que le tourniquet soit un algorithme d'ordonnancement raisonnable. Les
demandes se font dans l'ordre illustré par (d). Si ces 6 demandes sont réalisées dans cet ordre, on
obtient les six graphes de ressources de la figure 3.4 (e) – (j). Une fois que la demande 4 est
soumise, A se bloque .en attendant S, comme le montre (h). Au cours des deux étapes suivantes,
B et C sont également bloqués, menant au final à un cycle et à l'interblocage de la figure 3.4.(j).
Toutefois, le système d'exploitation n’est pas censé exécuter les processus dans un ordre
particulier. Plus précisément, si le fait d'accorder une requête spécifique conduit à un
interblocage, le système d'exploitation peut simplement suspendre le processus sans accorder la
demande (par exemple, en n'ordonnançant pas le processus) jusqu'à ce qu'elle soit sûre.
Après l'étape (q), S peut être attribuée au processus B car A a terminé et C possède tout ce
dont il a besoin. Même si B se bloquait en sollicitant T, cela ne conduirait pas à un interblocage :
B attendrait que C ait terminé.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 84
Les graphes de ressources représentent un outil qui permet de voir si une séquence de
demande/libération donnée conduit à un inter blocage. Nous effectuons les demandes et les
libérations étape par étape et, après chacune d'elles, nous regardons si le graphe présente des
cycles. Si tel est le cas, nous assistons à un inter blocage ; dans le cas contraire, aucun inter
blocage n'a lieu. Les graphes de ressources peuvent également être généralisés pour gérer
plusieurs ressources de même type. En règle générale, on peut procéder de quatre façons pour
gérer les inter blocages :
1. Ignorer les problèmes.. .
2. Les détecter et y remédier
3. Les éviter de manière dynamique en allouant les ressources avec précaution
4. Les prévenir en empêchant l'apparition d'une des quatre conditions de leur existence.
La première façon pour gérer les inter blocages c'est d'ignorer les problèmes en appliquant
la politique de l'Autriche : il s'agit de plonger la tête dans le sable en prétendant qu'il n'y a aucun
problème. En effet, tous les mécanismes dédiés au traitement des inter blocages ne sont pas des
moyen efficace de traiter les inter blocages. Pour la plupart des systèmes d'exploitation, Windows
et UNIX, l'apparition d'inter blocage est fort rare. Par conséquent, dans de nombreuses situations,
le problème des inter blocages est ignoré, à l'instar d'une autriche qui s'enfonce la tête dans le
sable en espérant que le problème disparaisse.
Une deuxième technique consiste à détecter et à reprendre les inter blocages. Lorsque ce
procédé est utilisé, le système ne cherche pas à empêcher les inter blocages. Il les laisse se
produire, puis tente de les détecter et d'y remédier a posteriori. .
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 85
La troisième façon c'est d'éviter les inter blocages grâce à une attribution réfléchie des
ressources. Les principaux algorithmes destinés à éviter les inter blocages reposent sur le concept
des états sûrs (safe states). (L’algorithme du banquier qui est un algorithme d'ordonnancement
qui permet d'éviter les inter blocages proposé par Dijkstra en 1965).
La quatrième façon c'est d'empêcher une des quatre conditions d'existence des inter blocages :
s'attaquer à la condition de l'exclusion mutuelle (éviter d'attribuer une ressource lorsque cela n'est
pas absolument nécessaire et s'assurer que le nombre de processus susceptibles de réclamer la
ressource est aussi faible que possible) ; s'attaquer à la condition de détention et d'attente (exiger
d'un processus qui demande une ressource qu'il commence par libérer provisoirement toutes les
ressources qu'il détient. Il peut tenter ensuite d'obtenir tout ce dont il a besoin en une seule fois) ;
s'attaquer à la condition de non-préemption (ceci est moins simple à réaliser) ; s'attaquer à la
condition de l'attente circulaire (on peut établir une règle qui stipule qu'un processus est à tout
moment attribué à une seule ressource. S'il a besoin d'une seconde ressource, il doit libérer la
première ou les processus peuvent demander des ressources dès qu'ils le souhaitent, mais toutes
les demandes doivent être effectuées selon un ordre numérique).
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 86
CHAPITRE IV
Les systèmes mémoire des ordinateurs actuels possèdent des hiérarchies de mémoire à
plusieurs niveaux. La figure 4.1 présente une hiérarchie mémoire à trois niveaux, composée d'un
cache, d'une mémoire principale et d'une mémoire virtuelle.
Processeur Processeur
(Registres)
Cache
Mémoire (SRAM)
Mémoire
principale
(DDR DRAM)
Mémoire
virtuelle
(Disques,
Bande
magnétique
La raison principale pour laquelle les systèmes mémoire sont construits de manière
hiérarchique tient à ce que le coût par bit d'une technologie mémoire est généralement
proportionnel à la vitesse de traitement du dispositif. Les mémoires rapides, comme les RAM
statiques (SRAM), possèdent généralement un coût élevé par bit. Les technologies plus lentes,
comme la RAM dynamique (DRAM) sont moins chères, ce qui permet plus facilement de
construire de grandes mémoires.
Dans une hiérarchie mémoire, les niveaux les plus proches du processeur, comme le cache
représenté sur la figure 4.1, contiennent une quantité relativement faible de mémoire qui peut être
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 87
implémentée à l'aide d'une technologie mémoire rapide afin de proposer des temps d'accès
réduits. En avançant dans la hiérarchie vers le bas, chaque niveau contient de plus en plus
d'espace mémoire et propose des temps d'accès plus longs que le niveau situé juste au-dessus.
Le but de la hiérarchisation de la mémoire est de conserver les données les plus
fréquemment référencées par un programme aux niveaux supérieurs de la hiérarchie, de manière
à ce que la plupart des requêtes mémoire puissent être gérées par ces niveaux aux temps d'accès
plus rapides. En général, il n'est pas possible de prédire quels emplacements mémoire seront
accédés le plus fréquemment. Aussi les ordinateurs utilisent-ils un système de pagination à la
demande pour déterminer quelles données doivent être conservées dans les niveaux supérieurs de
la hiérarchie. Lorsqu'une requête mémoire est transmise à la hiérarchie, le niveau supérieur est
vérifié pour voir s'il contient l'adresse. Si c'est le cas, la requête se termine. Si ce n'est pas le cas,
le niveau du dessous est vérifié, ce processus se répétant jusqu'à ce que les données soient
trouvées ou que le niveau le plus bas de la hiérarchie soit atteint, auquel cas on a la certitude que
les données s'y trouveront.
Si une requête mémoire ne peut être gérée par le niveau supérieur de la hiérarchie, un bloc
d’emplacements séquentiels contenant les adresses référencées est copié du premier niveau qui
contient l'adresse à chaque niveau en dessous. Ce procédé est utilisé pour deux raisons: tout
d'abord, de nombreuses technologies de stockage, comme les DRAM en mode page, mais
également les disques durs, permettent de lire ou écrire plusieurs mots séquentiels de données en
moins de temps qu'il n'en faut pour écrire un nombre égal de mots aléatoirement positionnés; ce
qui permet d'amener plus rapidement un bloc de données multi octets dans les niveaux supérieurs
de la hiérarchie qu'on ne parviendrait à extraire individuellement chaque octet du bloc à partir des
niveaux inférieurs. Ensuite, la plupart des programmes obéissent au principe de la localité de
référence : des références mémoire qui interviennent dans une fourchette de temps assez courte
ont tendance à posséder des adresses proches les unes des autres, ce qui augmente les chances
pour que les différentes adresses à l'intérieur d'un bloc soient référencées peu après la première
référence à une adresse du bloc.
Les niveaux de la hiérarchie mémoire posséderont souvent des blocs de tailles différentes,
selon les caractéristiques des niveaux sous-jacents de la hiérarchie.
Etant donné que les différents niveaux d'une hiérarchie mémoire sont généralement
implémentés de manières différentes, les architectes d'ordinateurs utilisent des termes distincts
pour les décrire. Le ou les niveaux supérieurs de la hiérarchie sont généralement désignés par le
terme de cache. Les caches sont le plus souvent implémentés en utilisant de la SRAM, et la
plupart des ordinateurs actuels possèdent au moins deux niveaux de mémoire cache dans leur
hiérarchie mémoire. Les caches utilisent un dispositif matériel pour mémoriser les adresses qu'ils
stockent. Ils sont généralement de 32 à 128 octets. La mémoire principale de l'ordinateur est
généralement construite en DRAM, elle s'appuie sur des outils logiciels pour mémoriser les
adresses qu'elle contient et possède des blocs de plus grande taille, souvent de plusieurs kilo-
octet. Enfin la mémoire virtuelle est généralement implémentée en utilisant des disques et
contient toutes les données dans le système mémoire.
- Terminologie
Une série de termes ont été définis pour décrire les hiérarchies mémoire. Lorsque l'adresse
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 88
qu'une opération référence est trouvée dans un niveau de la hiérarchie mémoire, on dit qu'un hit
est survenu à ce niveau. Dans le cas contraire on dit qu'un miss est survenu (on peut alors aussi
parler d'échec, de défaut ou de défaillance). Selon cette terminologie, on parle alors de taux de hit
d'un niveau pour désigner le pourcentage de références à un niveau qui produisent un hit, et de
taux de miss pour désigner le pourcentage de références à un niveau qui produisent un miss. Le
taux de hit et le taux de miss d'un niveau de la hiérarchie s'additionnent toujours afin de produire
une somme de 100%. Comme nous l'avons expliqué, lorsqu'un miss intervient dans un niveau de
la hiérarchie, un bloc de données contenant l'adresse du miss est amené à ce niveau. A mesure
qu'un programme tourne, le niveau se remplira de données et manquera bientôt d'espace libre
pour stocker des blocs. Lorsque cela arrive, un bloc doit être retiré du niveau pour faire de la
place à un nouveau bloc. On parle alors d'éviction ou de remplacement et la méthode à laquelle le
système fait appel pour sélectionner un bloc à retirer est appelée politique de remplacement. Pour
simplifier l'éviction des blocs de données d'un niveau, un grand nombre de système mémoire
établissent une propriété d'inclusion qui garantit qu'une adresse présente dans un niveau donné du
système le sera également dans tous les niveaux inférieurs de la hiérarchie.
Une autre série de termes est employée pour décrire la manière dont les hiérarchies
mémoire gèrent les écritures (stockages). Dans les systèmes write-back, les données écrites sont
placée uniquement au niveau supérieur de la hiérarchie. Lorsque le bloc contenant les données est
évincé de ce niveau, les données écrites sont copiées au niveau inférieur de la hiérarchie. Les
blocs contenant des données qui ont été modifiées par écriture sont dits sales (dirty) ou modifiés,
afin de les distinguer des blocs propres, dont le contenu n'a pas été modifié.
Les systèmes mémoire write-through copient les données écrites dans tous les niveaux de la
hiérarchie, à chaque fois qu'une écriture est effectuée.
Si nous connaissons le taux de hit et le temps d'accès (temps pour terminer une requête
qui aboutit à un hit) pour chaque niveau dans la hiérarchie de mémoire, nous pouvons calculer le
temps d'accès moyen de la hiérarchie complète. Pour chaque niveau dans la hiérarchie, le temps
d'accès moyen est (Thit x Phit) + (Tmiss x Pmiss), où Thi! désigne le temps pour accomplir une
requête qui aboutit à un hit au niveau, Phil le taux de hit du niveau (exprimé sous forme de
probabilité), Tmiss le temps d'accès moyen aux niveaux sous-jacents dans la hiérarchie et Pmiss
le taux de miss dans la hiérarchie.
Trois technologies différentes sont utilisées pour implémenter les systèmes mémoires sur
les ordinateurs modernes: la RAM statique (SRAM), la RAM dynamique (DRAM) et les disques
durs. Les disques durs sont de loin les plus lents et sont réservés au niveau le plus bas du système
mémoire, c'est-à-dire à la mémoire virtuelle. La SRAM et la DRAM sont jusqu'à un million de
fois plus rapide.
La mémoire est une ressource importante qui doit être gérée avec attention. Elle n'est pas
infiniment grande dans un ordinateur, ni infiniment rapide et en plus elle est volatile. La mémoire
de la plupart des ordinateurs ont une hiérarchisation de la mémoire: une petite quantité de
mémoire cache est volatile, rapide et chère, quelques dizaines de mégaoctets de mémoire ont une
vitesse et un prix moyen (c'est la mémoire principale, ou RAM), et des dizaines ou des centaines
de gigaoctets de mémoire plus lente et non volatile servent de mémoire de masse. .
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 89
4.1.3. Caches
Les caches sont des mémoires SRAM, de taille raisonnable, très rapides, placées entre le
processeur et la mémoire principale. Elles permettent donc de réduire latence des échanges entre
le processeur et la mémoire. Lorsque le processeur veut accéder à un mot, il commence par le
chercher dans la cache avant d’aller le chercher dans la mémoire principale. Si l’information est
trouvée dans la cache, on parle de Cache « hit », et il n y a donc pas besoin d’accéder la mémoire
principale. Si l’information n’est pas dans la cache, on parle de cache « miss », il faut donc aller
chercher l’information en mémoire et la stocker dans la mémoire cache. La fréquence de succès
« hit rate » dépend de la taille de la cache, et de l’algorithme exécuté par le contrôleur de la
cache.
Généralement, le cache d'instructions d'un système est sensiblement plus petit (deux à
quatre fois plus petit) que son cache de données. Ceci est dû au fait que les instructions d'un
programme prennent généralement moins de place en mémoire que ses données. En outre, la
plupart des programmes passent 1a majorité de leur temps à effectuer des boucles qui utilisent les
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 90
b) Politiques de remplacement
Lorsqu'une ligne doit être évincée d'un cache pour faire de la place à de nouvelles
données (soit parce que le cache est plein, soit en raison de conflits portant sur un ensemble), le
choix de la ligne à évincer dépend de la politique de remplacement. L'une des politiques de
remplacement les plus courantes est appelée Least recently used (LRU), que l'on traduirait
littéralement: la moins récemment utilisée. Dans le cas du remplacement LRU, le cache trie
chacune des lignes des ensembles afin de définir celles qui ont été accédées le plus récemment,
puis évince la ligne la moins récemment utilisées de l'ensemble. Une autre politique qui a été
proposée est celle du remplacement aléatoire, qui consiste à évincer une ligne aléatoirement
sélectionnée dans l'ensemble approprié.
Le système d'exploitation a pour rôle de coordonner la manière dont ces différentes
mémoires sont utilisées.
L'entité du système d'exploitation qui gère la hiérarchie de la mémoire est appelée le
gestionnaire de la mémoire. Son rôle est de conserver la trace de la partie de la mémoire qui est
en cours d'utilisation et de celle qui ne l'est pas, d'allouer cette mémoire aux processus qui en ont
besoin, de la libérer quand ils ont fait leur travail, et de gérer le va-et-vient (ou swapping) entre la
mémoire principale et le disque quand cette mémoire principale est trop petite pour contenir tous
les processus.
Le coût de la mémoire était une contrainte importante pour les anciens systèmes
informatiques. Avant le développement des DRAM à semi-conducteurs, la technologie mémoire
la plus répandue était la mémoire centrale, qui utilisait un tore de ferrite (un anneau de matériau
magnétique). Le coût de production de ces tores magnétiques et la complexité de leur assemblage
dans les composants mémoire limitaient sérieusement les capacités mémoire de nombreux
ordinateurs, souvent en deçà du seuil requis par les programmes.
Le concept de mémoire virtuelle fut développé pour résoudre ce problème. Il s’agit d’une
technique qui permet alors d’exécuter des programmes dont la taille excède la taille de la
mémoire principale. Dans le système de mémoire virtuelle, les disques durs et d'autres supports
magnétiques forment la couche inférieure de la hiérarchie mémoire, les DRAM ou la mémoire
centrale constituant le niveau de mémoire principale dans la hiérarchie.
Chaque processus possède son propre espace d'adressage, généré par les compilateurs et
les liens. Cet espace d’adressage constitue la mémoire virtuelle du processus, c'est-à-dire un
ensemble d'adresses qu'il peut utiliser pour les opérations de chargement et de stockage. L'espace
d'adressage physique est un ensemble d'adresses utilisé pour référencer des emplacements dans la
mémoire principale. Les termes adresse virtuelle et adresse physique sont alors utilisés pour
décrire les adresses des espaces virtuel et physique.
L'espace d'adressage virtuel est divisé en pages, qui sont des blocs contigus de données
stockés sur des supports tels que la mémoire centrale, les disques durs et magnétiques.
Dans les systèmes actuels, les pages ont généralement une taille fixe entre 2 et 8 Ko.
Lorsqu'une page de données est référencée, le système la copie dans des cadres de page (des
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 91
emplacements de la mémoire principale permettant de stocker une page) afin qu'elle puisse être
accédée. Les pages qui ont été chargées dans la mémoire principale à partir du disque sont dites
avoir été mappées dans la mémoire principale. La figure 4.4 illustre un certain nombre de
concepts clés de la mémoire virtuelle.
La mémoire virtuelle permet donc à l'ordinateur d'agir comme si sa mémoire principale
possédait une capacité bien plus grande que ce n'est véritablement le cas.
Espace
Espace Page sur
d’adressage
d’adressage disque
virtuel
physique
(référencé par
(données en
le
mémoire)
programme)
Page physique
Page sur
Page virtuelle disque
Page physique
Page virtuelle cadre
de page Page non mappée
.
(elle sera mappée dans la mémoire Page sur
Page virtuelle disque
au moment d’être utilisée)
La figure 4.4 montre une mémoire virtuelle avec 4 pages (A, B, C, D) dont trois sont mappés en
mémoire centrale (B,C,D) et une page est sur le disque (A). Les pages sont de taille 4 Ko.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 92
La mémoire est une ressource importante qui doit être gérée avec attention. Aujourd'hui
malgré que la quantité moyenne de mémoire d'un ordinateur personnel soit mille fois plus
importante que celle de l'IBM 7094, le plus grand ordinateur du monde au début des années 1960,
la taille des programmes s'accroît aussi vite que celle des mémoires.
Aujourd'hui, n'importe quel programmeur aimerait disposer d'une mémoire infiniment
grande, infiniment rapide et qui serait aussi non volatile, c'est-à-dire qui ne perdrait pas son
contenu quand l'électricité est coupée. On peut souhaiter qu'il soit aussi bon marché.
Malheureusement, la technologie ne fournit pas de telles mémoires. Par conséquent, la mémoire
de la plupart des ordinateurs ont une hiérarchisation de la mémoire : une petite quantité de
mémoire cache est volatile, rapide et chère, quelques dizaines de mégaoctets ont une vitesse et un
prix moyens (c'est la mémoire principale, ou RAM), et des dizaines ou des centaines de giga-
octets de mémoire plus lente et non volatile servent de mémoire de masse.
Le système d'exploitation a pour rôle de coordonner la manière dont ces différentes
mémoires sont utilisées. L'entité du système d'exploitation qui gère la hiérarchie de la mémoire
est appelée le gestionnaire de la mémoire. Son rôle est :
- de conserver la trace de la partie de la mémoire qui est en cours d'utilisation et de celle qui
ne l'est pas,
- d'allouer cette mémoire aux processus qui en ont besoin,
- de la libérer quand ils ont fait leur. travail,
- et de gérer le va-et-vient (ou swapping) entre la mémoire principale et le disque quand
cette mémoire principale est trop petite pour contenir tous les processus.
Les systèmes de gestion de la mémoire peuvent être divisés en deux classes: celle qui
permet l'échange des processus entre la mémoire principale et le disque pendant l'exécution (va-
et-vient et pagination), et celle qui ne le permet pas. .
Programme
utilisateur
Système Système
d’exploitation d’exploitation
en RAM
Programme en RAM
utilisateur
Le système d'exploitation peut se trouver en bas de la mémoire vive (RAM), (a), ou bien
être en mémoire morte (ROM) en haut de la mémoire (b) ; les gestionnaires de périphériques
peuvent aussi se trouver en haut de la mémoire en ROM tandis que le reste du système en RAM
se situe tout en bas de la mémoire (c). Autrefois utilisé dans les mainframes et les mini-
ordinateurs, le premier modèle est aujourd'hui rare. Le deuxième modèle équipe de nombreux
ordinateurs de poche ou de systèmes embarqués. Enfin, le troisième modèle était exploité sur les
premiers ordinateurs personnels (ceux qui faisaient fonctionner MS-D0S) dans lesquels la partie
du système d'exploitation en ROM s'appelait BIOS.
Quand le système est organisé de cette manière, un seul processus peut s'exécuter à la
fois. Dès que l'utilisateur tape une commande, le système d'exploitation copie le programme
demandé depuis le disque vers la mémoire et l'exécute. Lorsque le processus se termine, le
système d'exploitation affiche une suite de caractères particulières, appelé invite (prompt), et
attend une nouvelle commande. Quand il reçoit la commande, il charge un nouveau programme
en mémoire, en écrasant le précédent.
b) La multiprogrammation
Dans un système de traitement par lots, une organisation mémoire en partitions fixes est
simple et efficace. Chaque tâche est chargée dans une partition quand elle arrive en tête de la file
d'attente et elle reste en mémoire jusqu'à sa terminaison. Tant qu'un nombre suffisant de tâches
peuvent rester en mémoire pour que le processeur soit occupé en permanence, il n'y a aucune
raison de suivre un procédé plus complexe.
Avec des systèmes à temps partagé ou orientés ordinateurs personnels, la situation est
différente. Parfois, la mémoire principale est insuffisante pour maintenir tous les processus
courants actifs: il faut alors conserver les processus supplémentaires sur un disque et les charger
pour qu'ils s'exécutent dynamiquement.
Deux approches de gestion mémoire peuvent être utilisées, suivant (en partie) le matériel
disponible. La stratégie la plus simple, appelé va-et-vient (swapping), consiste à considérer
chaque processus dans son intégralité (exécution puis placement sur le disque). L'autre stratégie,
appelée mémoire virtuelle, permet aux programmes de s'exécuter même quand ils sont
partiellement en mémoire principale. Le fonctionnement d'un système de va - et-vient est illustré
à la figure 4.8.
Fig. 4.8. : L'allocation mémoire change au gré des processus qui viennent en mémoire et qui la quittent.
Quand la mémoire est allouée dynamiquement, c'est le système d'exploitation qui doit la gérer. Il
y a généralement deux façons de conserver une trace de l'utilisation de la mémoire: à l'aide des
tables et à l'aide des listes.
Avec une table de bits, la mémoire est répartie en unités d'allocation dont la taille peut
varier de quelques mots à plusieurs kilo-octets. Chaque unité d'allocation correspond à un bit du
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 95
tableau de bits, lequel est 0 si l'unité correspondante est vide et 1 si elle est occupée (ou vice-
versa). Nous présentons à la figure 4.9: une partie de mémoire et le tableau de bits qui lui est
associé.
Fig. 4.9 : (a) Une partie de mémoire avec 5 processus et 3 trous. Les petites marques verticales indiquent les unités
d’allocation mémoire. Les zones grisées (valeur 0 dans le tableau de bits sont des zones libres. (b) Le tableau de bits
correspondant. (c) Les mêmes informations sous forme d’une liste chaînée.
Une autre manière de garder une trace de la mémoire est de maintenir une liste chaînée
des segments de mémoire alloués et libres; dans cette liste, un segment est soit un processus, soit
un trou entre deux processus.
La mémoire de la figure 4.9 (a) est représentée à la figure 4.9 (c) comme une liste chaînée
de segments. Chaque entrée de cette liste indique un trou (T) ou un processus (P), l'adresse à
laquelle il débute et sa longueur, et elle spécifie un pointeur sur la prochaine entrée..
Dans cet exemple, la liste des segments est triée par adresse, ce qui est pratique puisque
lorsqu'un processus se termine ou est transféré sur disque, la mise à jour est directe.
Un processus qui se termine a normalement deux voisins (excepté s'il est placé tout en haut ou
tout en bas de la mémoire), qui peuvent être des processus ou des trous, ce qui conduit aux quatre
combinaisons de la figure 4.10.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 96
Quand les processus et les trous sont indiqués dans une liste triée par adresse, plusieurs
algorithmes peuvent servir à allouer de la mémoire à un processus nouvellement créé (ou un
processus existant chargé depuis le disque).
L'algorithme le plus simple est l'algorithme de la première zone libre (first fit) : le
gestionnaire recherche tous les trous jusqu'à en trouver un dont la taille est supérieure à celle du
processus. Le trou est ensuite divisé en deux parties, l'une destinée au processus et l'autre à la
mémoire non utilisée, sauf si le processus et le trou ont la même taille, ce qui est statistiquement
peu probable.
Une petite variante de la première zone libre est l'algorithme de la zone libre suivante
(next fit) : dans l'algorithme précédent, étant donné que toutes les recherches commencent au
début de la mémoire, les zones se trouvant au début de la mémoire sont plus fréquemment prises,
en compte que celles de la fin. L'algorithme de la zone libre suivante fonctionne comme le
précédent et mémorise en outre la position de l'espace libre trouvé. II débute la recherche dans la
liste à partir de l'endroit où il s'est arrêté la fois précédente, au lieu de recommencer au début de
la mémoire.
Un autre algorithme bien connu est l'algorithme du meilleur ajustement (best fit). Il fait
une recherche dans la liste des zones libres la plus petite dont la taille est supérieure ou égale à
celle du processus. Plutôt que de casser un gros trou qui peut être nécessaire ultérieurement,
l'algorithme du meilleur ajustement essaye de trouver un trou qui correspond à la taille
demandée. '
Pour régler le problème des cassures et faire concorder de manière quasiment exacte un
processus et un trou minuscule, on pourrait penser à l'algorithme du plus grand résidu (worst fit) ,
qui consisterait à prendre toujours le plus grand trou disponible: ainsi, le trou restant serait assez
grand pour être réutilisé.
La mémoire virtuelle repose sur le principe suivant: la taille de l'ensemble formé par le
programme, les données et la pile peut dépasser la capacité disponible de mémoire physique. Le
système d'exploitation conserve les parties de programme en cours d'utilisation dans la mémoire
principale, et le reste sur le disque.
Les adresses peuvent être générées notamment au moyen de l'indexation, des registres de base et
des registres de segments.
Les adresses générées par le programme sont appelées des adresses virtuelles et elles
forment l'espace d'adressage virtuel. L'espace d'adressage virtuel est donc divisé en pages.
Dans les ordinateurs sans mémoire virtuelle, l'adresse virtuelle est placée directement sur le bus
mémoire et provoque la lecture ou l'écriture du mot de même adresse physique. Dans les
ordinateurs avec mémoire virtuelle, elles ne vont pas directement sur le bus mémoire mais dans
une unité de gestion mémoire (MMU, Memory Management Unit) qui fait correspondre les
adresses virtuelles à des adresses physiques (voir sur la figure 4.14).Ce procédé est appelée
traduction d’adresse.
Les programmes tournant sur un système doté d'une mémoire virtuelle utilisent les
adresses virtuelles comme arguments pour les instructions de chargement et de stockage, mais la
mémoire principale utilise des adresses physiques pour tenir registre des emplacements auxquels
les données sont réellement stockées. Lorsqu'un programme opère une référence mémoire,
l'adresse virtuelle qu'il utilise doit être convertie en son adresse physique équivalente.
mémoire ne sait rien de la MMU : elle interprète seulement qu'il s'agit d'une requête de lecture ou
d'écriture à l'adresse 8192, et elle la réalise. Ainsi, la MMU a effectivement fait correspondre
toutes les adresses virtuelles comprises entre 0 et 4095 à des adresses physiques comprises entre
8192 et 12287.
Fig. 4.15 : La relation entre adresses virtuelles et les adresses de la mémoire physique est indiquée dans la table
des pages
De la même manière, l'instruction
>> MOV REG, 8192
est transformé en
>> MOV REG, 24576
parce que l'adresse virtuelle 8192 se trouve dans la page virtuelle 2 et que cette page correspond
au cadre de page 6 (adresses physiques de 24576 à 28671). Autre exemple: l'adresse virtuelle
20500 est située à 20 octets du début de la page virtuelle 5 (adresses virtuelles de 20480 à 24575)
et correspond à l'adresse physique 12288 + 20 = 12308.
Cependant, cette capacité de mettre en correspondance les 16 pages virtuelles sur les 8
cadres de pages en initialisant correctement la MMU ne résout pas le problème posé par un
espace d'adressage virtuel plus grand que la mémoire physique. Puisqu'il n'y a que 8 cadres de
pages physiques, seules 8 des pages virtuelles de la figure 4.15 sont mises en correspondance
avec de la mémoire physique. Les autres, illustrées par des croix dans la figure, ne sont pas mises
en correspondance. En termes de matériel, un bit de présence/absence conserve la trace des pages
qui se trouvent physiquement en mémoire.
Que se passe-t-il si le programme essaye par exemple de faire appel à une page non
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 99
Les pages physiques sont divisées de la même manière au moyen d'un numéro de page
physique (NPP. ou PPN, Physical page number) et d'un décalage entre le début de la page
physique et l'adresse physique
Les pages virtuelles et physiques d'un système sont généralement de même taille, aussi le
nombre de bits requis pour les champs de décalage des adresses virtuelles et physiques est-il le
même, bien que les NPV et les NPP puissent être de différentes longueurs.
Lorsqu'une adresse virtuelle est traduite, le système d'exploitation recherche l'entrée
correspondant au NPV dans la table de pages et retourne le NPP correspondant. Les bits de
décalage de l'adresse virtuelle sont alors concaténés avec le NPP afin de générer l'adresse
physique, comme le montre la figure 4.13.
Sur n'importe quel ordinateur, il existe un ensemble d'adresses mémoire que les
programmes peuvent générer. Quand un programme utilise une instruction comme
Cela copie le contenu de l'adresse mémoire 1000 dans le registre REG (ou vice-versa, suivant
l'ordinateur).
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 101
CPU
Mémoire Contrôleur
Unité de gestion mémoire de
principale
disque
(MMU)
Bus
La MMU envoie les adresses physiques
à la mémoire
Fig. 4.14 : Localisation et fonction d’une MMU. Ici, la MMU est montrée comme une partie intégrante du CPU parce
que cette configuration est usuelle de nos jours. Toutefois, elle pourrait logiquement se trouver dans un composant
séparé, comme c’était le cas il y a quelques années.
Voyons comment fonctionne une MMU. La figure 416. nous présente un exemple
d'adresse virtuelle, 8196 (0010 0000 0000 0100 en binaire), mise en correspondance via MMU de
la figure 4.16. L'adresse virtuelle de 16 bits qui arrive est divisée en deux parties: un numéro de
page sur 4 bits et un décalage sur 12 bits. Avec 4 bits pour le numéro de page, nous pouvons
avoir 16 pages, et avec 12 bits pour le décalage, nous pouvons adresser l'ensemble des 4096
octets d'une page.
Le numéro de page est utilisé comme index dans la table des pages: le numéro du cadre de
page correspond à la page virtuelle. Si le bit de présence/absence est à 0, un déroutement vers le
système d'exploitation est mis en place. Si le bit est à 1, le numéro du cadre de page trouvé dans
la table des pages est copié dans les 3 bits de poids le plus fort du registre de sortie auxquels sont
ajoutés les 12 bits de décalage. qui sont copiés à partir de l'adresse virtuelle entrante sans être
modifies. Ils 10rmem ensemble une adresse physique sur 15 bits. Le registre de sortie est ensuite
placé sur le bus mémoire en tant qu'adresse de mémoire physique. Chaque processus possède ses
propres tables de pages que le système d'exploitation stocke en mémoire.
Quand un défaut de pages se produit, le système d'exploitation doit choisir une page à
enlever de la mémoire afin de faire de la place pour la page qui doit être chargée. Si la page qui
doit être supprimée a été modifiée quand elle était en mémoire, elle doit être réécrite sur le disque
pour mettre à jour la copie disque. Toutefois, si la page n'a pas changé (parce qu'elle contient par
exemple le texte d'un programme), la copie disque est déjà à jour et ne nécessite pas de réécriture.
La page à lire écrasera simplement la devant être évincée.
Bien qu'il soit possible de choisir au hasard la page à supprimer à chaque défaut de page,
les performances du système seront meilleures-si c'est une page peu utilisée qui est choisie. Si
une page souvent employée est enlevée, il faudra probablement qu'elle soit recherchée
rapidement, ce qui entraînera un dépassement supplémentaire.
Les interruptions d'horloge n'effacent pas le bit M parce que cette information est
nécessaire pour savoir si la page a été réécrite sur le disque ou pas. Si le bit R est effacé mais pas
le bit M, cela aboutit à une page de classe 1.
L'algorithme de la page non récemment utilisée ou NRU (Not recently Used) enlève une
page au hasard dans la classe la plus basse non vide. Avec cet algorithme, il est implicite qu'il
vaut mieux enlever une page modifiée qui n'a pas été référencée au moins dans un top plutôt
qu'une page bonne qui est beaucoup utilisée.
Un autre algorithme de pagination est l'algorithme premier entré, premier sorti ou FIFO
(First ln, first Out, premier entré, premier sorti). Le système d'exploitation maintient une liste de
toutes les pages couramment en mémoire, la page la plus ancienne étant en tête de liste et la page
la plus récente en queue. Dans le cas d'un défaut de page, la page en tête de liste est effacée et la
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 104
nouvelle page ajoutée en queue de liste. Avec cet algorithme on peut supprimer une page à
laquelle on a couramment recours.
On peut apporter une modification simple à l'algorithme FIFO afin d'éviter la suppression
d'une page à laquelle on a couramment recours: il s'agit d'inspecter le bit R de la page la plus
ancienne. S'il est à 0, la page est à la fois ancienne et inutilisée, elle est donc remplacée
immédiatement. Si le bit R est à 1, le bit est effacé, la page est placée à la fin de la liste des pages,
et son temps de chargement est mis à jour comme si elle venait d'arriver en mémoire. La
recherche continue alors.
L'opération de cet algorithme, appelée seconde chance, est illustrée à la figure 4.17. A la
figure (a), nous voyons que les pages de A à H se trouvent dans une liste chaînée, triées par leur
temps d'arrivée en mémoire.
Supposons qui un défaut de page se produise à l'instant 20. La page la plus ancienne est
A, qui est arrivée à l'instant 0, quand le processus a démarré. Si le bit R de la page A est à 0, elle
est évincée de la mémoire: elle est soit écrite sur le disque (si elle est modifiée), soit simplement
abandonnée (si elle est bonne). D'un autre côté, si le bit R est à 1, A est placée à la fin de la liste
et son temps de chargement est mis à jour avec le temps courant (20). Le bit R est aussi mis à O.
La recherche d'une page convenable continue alors avec B.
Page chargée en premier
0 3 7 8 12 14 15 18 Page chargée le plus
récemment
A B C D E F G H
(a)
3 7 8 12 14 15 18 20 A est considérée
comme une page
B C D E F G H A
nouvellement chargée
(b)
Fig. 4.17 : Opération de la seconde chance. (a) Pages triées dans un ordre FIFO. (b) Liste de pages lorsqu’un défaut
de page se produit à l’instant 20 et que le bit R de A est à 1. Les nombres au-dessus des pages correspondent à
l’instant de leur chargement.
Le travail de l'algorithme de la seconde chance consiste à chercher une ancienne page qui n'a pas
été référencée dans le précédent intervalle d'horloge. Si toutes les pages ont été référencées,
l'algorithme de la seconde chance dégénère en pur algorithme FIFO.
J E
F
I
H G
Un pointeur se trouve sur la page la plus ancienne. Quand un défaut de page survient, la
page pointée est examinée. Si son bit R est à 0, la page est évincée, la nouvelle page est insérée
dans l'horloge à sa place, et le pointeur est avancé d'une position; si le bit est à 1, il est effacé et le
pointeur est avancé sur la prochaine page. Ce processus est répété jusqu'à ce qu'une page avec
R=O soit trouvée. Cet algorithme de l'horloge diffère de l'algorithme de la seconde chance
uniquement dans son implantation.
Le fonctionnement de cet algorithme est donné à la figure 4.19 pour quatre cadres de pages et
des références de pages dans l'ordre suivant:
>> 0 1 2 3 2 1 0 3 2 3
Fig. 4.19 L’algorithme LRU utilisant une matrice dont les pages sont référencées dans l’ordre 0, 1, 2, 3, 2, 1, 0, 3, 2, 3
Pour les machines ne possédant pas le type de matériel pouvant implanter la pagination
LRU, à la place une solution logicielle peut être implantée. C'est l'algorithme NFU (Not
frequently Used). Il nécessite un compteur logiciel. A chaque interruption d'horloge. Le système
d'exploitation examine toutes les pages en mémoire. Pour chaque page, le bit R, de valeur 0 ou 1,
est ajouté à son compteur. Les compteurs mémorisent donc les différents référencements des
pages. Quand un défaut de page se produit, c'est la page avec le plus petit compteur qui est
remplacée.
Dans un système pagine {, les processus sont lancés sans qu'aucune de leur page soit en mémoire.
Dès que le processeur essaie d'exécuter la première instruction, il se produit un défaut de page, ce
qui amène le système d'exploitation à charger la page contenant cette instruction. D'autres défauts
de pages vont apparaître rapidement pour des variables globales ou la pile. Au bout d'un certains
temps, le processus dispose de la plupart des pages dont il a besoin et son exécution ne générera
que peu de défauts de pages. Cette méthode est appelée pagination à la demande parce que les
pages sont chargées uniquement à la demande et non à l'avance.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 107
L'ensemble des pages exploités par le processus courant est son ensemble de travail
(working set). Si la totalité de son ensemble de travail est présente en mémoire, l'exécution de ce
processus se déroule sans défaut de page jusqu'à son passage dans un autre état. Si la mémoire
disponible est trop petite pour charger l'ensemble de travail dans son intégralité, le processus
génère de nombreux défauts de pages et s'exécute plus lentement. Un programme qui génère de
nombreux défauts de pages provoque un écroulement du système. De nombreux systèmes
d'exploitation mémorisent l'ensemble de travail de chaque processus et le charge en mémoire
avant d'exécuter les processus. Cette approche est appelée modèle de l'ensemble de travail
(working set model). Elle a été conçue pour réduire le nombre de défauts de pages. Le
chargement des pages avant l'exécution est appelé préchargement (prépaging).
Notons que l'ensemble de travail est une fonction w(k,t) monotone. A chaque instant t, il existe
un ensemble de travail constitué de toutes les pages utilisées par les k références mémoire les plus
récentes.
L’algorithme de base de l’ensemble de travail est lourd puisque toute la table des pages
doit être examinée à chaque défaut de page jusqu’à ce qu’une page adéquate soit localisée. Il
existe un meilleur algorithme, appelé WSClock, qui utilise l’algorithme de l’horloge et les
informations de l’ensemble de travail. Grâce à sa simplicité d’implantation et à ses bonnes
performances, il est très employé dans la pratique.
La structure de données nécessaire est une liste circulaire des cadres de pages, comme
dans l’algorithme de l’horloge, et tel que décrit à la figure 4.20 (a).
1620 1
1620 1
1620 1 1620 1
1620 1 1620 1
1620 1
1620 1 1620 1
1620 1
1620 1
1620 1
1620 1 1620 1
1620 1 1620 1
Fig. 4.20 : Opération de l’algorithme WSClock. (a) et (b) donnent un exemple de ce qu’il se passe lorsque R=1.
Initialement, cette liste est vide. Lorsque la première page est chargée, elle est ajoutée à la
liste. Au fur et à mesure que des pages sont ajoutées, elles entrent dans la liste et forment un
anneau. Chaque entrée contient le champ Temps de la dernière utilisation de
l’algorithme de base de l’ensemble de travail, en plus du bit R (montré) et du bit M (non montré).
Comme pour l’algorithme, à chaque défaut de page, la page pointée est examinée en
premier. Si le bit R est mis à 1, cela signifie que la page a été utilisée pendant le top courant ; il ne
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 108
convient donc de l’effacer. Le bit R est mis à 0, le pointeur est avancé sur la page suivante et
l’algorithme se répète sur cette page. L’état qui intervient après cette séquence d’événements est
illustré à la figure 4.20 (b).
En principe, toutes les pages doivent être ordonnancées pour les E/S en un cycle d’horloge
environ. Pour réduire le trafic disque, il faut fixer une limite pour permettre à un maximum de n
pages d’être écrites en tâches de fond. Une fois cette limite atteinte, aucune nouvelle écriture
n’est ordonnancée.
Que se passe-t-il si le pointeur revient à son point de départ ? il existe deux cas à
distinguer :
1. Au moins une écriture a été ordonnancée.
2. Aucune écriture n’a été ordonnancée.
Sur la figure 4.21, nous donnons un résumé de la liste des algorithmes de remplacements de page
que nous avons examiné.
Algorithme Commentaire
Optimal Non implantable, mais utilisé comme référence
NRU Très grossier
FIFO Peut écarter des pages importantes
Deuxième chance Grande amélioration de FIFO
Horloge Réaliste
LRU Excellent, mais difficile à implanter
NFU Approximation passablement grossière de LRU
Ensemble de travail Quelque peu couteux à implanter
WSClock Algorithme de bonne efficacité
L’algorithme optimal remplace la page référencée en dernier parmi les pages courantes.
Malheureusement, il n’y a aucun moyen de déterminer quelle page sera la dernière. En pratique,
on ne peut avoir recours à cet algorithme. Il est néanmoins utile comme référence vis-à-vis
d’autres algorithmes qui peuvent être mesurés.
L’algorithme NRU divise les pages en quatre catégories suivant l’état des bits R et M. une
page est choisie aléatoirement parmi la catégorie la moins nombreuse. Cet algorithme est facile à
implanter, mais il est très grossier. Il en existe de meilleurs.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 109
L’algorithme FIFO mémorise l’ordre des pages chargées en mémoire en les conservant
dans une liste chaînée. L’effacement de la page la plus ancienne est très simple mais il se peut
que cette page serve encore. L’algorithme FIFO est donc un mauvais choix.
L’algorithme de la deuxième chance est une version modifiée de l’algorithme FIFO qui
vérifie si une page est utilisée avant de l’effacer. Si c’est le cas, cette page est conservée. Cette
modification augmente considérablement les performances. Quant à l’algorithme de l’horloge, il
s’agit simplement d’une implantation différente de l’algorithme de la deuxième chance. Il a les
mêmes performances que ce dernier mais s’exécute un peu plus rapidement.
L’algorithme LRU est un excellent algorithme, mais on ne peut l’implanter sans un
matériel spécialisé. Si ce matériel n’est pas disponible, on ne peu se servir de l’algorithme.
Les deux derniers algorithmes fonctionnent avec l’ensemble de travail. Les performances
de l’algorithme de l’ensemble de travail sont satisfaisantes, mais il est quelque peu couteux à
implanter. Enfin, l’algorithme WSClock est une variante dont les performances sont similaires et
qui en outre est facile à implanter.
Au fil des ans, de nombreux travaux ont été réalisés pour modéliser les algorithmes de
remplacements de pages du point de vue théorique. Nous présentons un seul modèle : l’anomalie
de Belady.
L’anomalie de Belady
Intuitivement, nous pouvons imaginer que plus il existe de cadres, moins il y a défauts de pages.
En réalité, ce n’est pas toujours le cas. Belady et al. ont proposé un contre-exemple dans lequel
un algorithme FIFO engendrait plus de défauts de pages avec 4 cadres qu’avec 3. Cette situation
étonnante est connue sous le nom d’anomalie de Belady. Elle est illustrée à la figure 4.22 pour
un programme qui possède 5 pages virtuelles, numérotées de 0 à 4. Les pages sont référencées
dans l’ordre suivant :
>> 0 1 2 3 0 1 4 1 2 3 4
A la figure 4.22 (a), nous voyons 9 défauts de pages sont générés avec 3 cadres. A la figure 4.22
(b), ce sont 10 défauts de pages qui sont générés avec 4 cadres.
Tous les cadres sont initialement vides
0 1 2 3 0 1 4 1 2 3 4
Page la + récente
0 1 2 3 0 1 4 4 2 3 3
2 0 1 2 3 0 1 1 4 2 2
2 4
0 1 2 3 0 0 1 4
Page la + ancienne
2
P P P P P P P P P 9 défauts de pages
(a)
Page la + récente
0 2 3 3 3 3 4 0 1 2 3 4
2 0 1 2 2 2 3 4 0 1 2 3
2
0 1 1 1 2 3 4 0 1 2
2
0 0 0 1 2 3 4 0 1
2
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 110
Page la + ancienne
P P P P P P P P P P 10 défauts de pages
(b)
Fig. 4.22 : L’anomalie de Belady. (a) L’algorithme FIFO avec 3 cases. (b) L’algorithme FIFO avec 5 cases. La lettre P
indique quelles sont les références de pages qui provoquent des défauts de pages.
4.5. La segmentation
La mémoire virtuelle paginée est à une dimension, les adresses virtuelles étant comprises
entre 0 et une adresse maximale. Comme la pagination, la segmentation divise un programme en
un certain nombre de blocs plus petits appelés segments, chacun étant alloué indépendamment à
la mémoire. Chaque segment est une suite d'adresses continues de 0 à une adresse maximale. La
longueur de chaque segment peut être comprise entre 0 et la longueur maximale autorisée par le
matériel. Les segments ont en général des longueurs différentes. De plus, leur longueur peut
varier en cours d'exécution.
Pour spécifier une adresse dans cet espace à deux dimensions, le programme doit fournir
une adresse en deux parties, constituées par un numéro de segment et une adresse (offset) à
l'intérieur de celui-ci. La figure 4.23 montre une mémoire segmentée.
Notons qu’un segment est une entité logique que le programmeur doit manipuler. Un
segment peut contenir une procédure, un tableau, une pile ou une succession de variables, mais
en général il ne contient pas d'objets de natures différentes. .
La segmentation simplifie également le partage des procédures et des données entre
plusieurs processus.
Fig. 4.24. : (a) Traduction d’adresse pour la segmentation. (b) descripteur de segment. S est l’adresse du segment.
Si les segments sont grands, il peut être difficile, voire impossible de les conserver tous en
mémoire principale. D'où l'idée de les paginer, afin de ne garder que les pages réellement
utilisées en mémoire.
Dans la pagination d'une mémoire segmentée, l'espace adressable est segmentée, alors que
la mémoire physique est paginée. Une adresse logique est composée d'un numéro de segment et
d'un déplacement à l'intérieur de ce segment. Chaque segment est divisé en pages et chaque
segment possède sa propre table des pages. La table des segments permet d'associer à chaque
numéro de segment l'adresse de la table des pages du segment.
Le déplacement à l'intérieur du segment de l'adresse logique est interprété comme étant
composé de deux champs: un numéro de page virtuelle appartenant au segment et un
déplacement à l'intérieur de cette page (figure 4.25). Le numéro de page virtuelle permet
d'extraire de la table des pages du segment le numéro de page physique. L’adresse physique est
alors la concaténation du numéro de page physique et du déplacement à l'intérieur de la page. Le
Pentium d'Intel utilise une mémoire virtuelle utilisant de la segmentation et de la pagination.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 113
Adresse logique
Numéro de page
Numéro de virtuelle dans le déplacement dans
segment segment la page
CHAPITRE V
ENTREES/SORTIES
5.1. Introduction
L'une des principales fonctions d'un système d'exploitation consiste à contrôler tous les
périphériques d'entrée/sortie (E/S) de l'ordinateur. Il doit émettre des commandes vers les
périphériques, intercepter les interruptions et gérer les erreurs. Il fournit également une interface
simple entre les périphériques et le reste du système. Dans la mesure du possible, l'interface doit
être la même pour tous les périphériques (indépendance des périphériques). Le code d’E/S, qui
représente une part significative du système d’exploitation fait l’objet de ce chapitre.
Nous présentons au départ, les principes des E/S du point de vue matériel, puis nous
examinerons les logiciels d’E/S en général, qui peuvent être structurés en couches, chacune
ayant une tâche définie à effectuer. Nous verrons à quoi servent ces couches et comment elles
s’adaptent les unes aux autres.
Chacun perçoit les aspects matériels des E/S de manière différente. Les ingénieurs y
pensent en termes de puces, câbles, alimentations électriques, moteurs et autres composants
physiques qui les constituent. Les programmeurs, quant à eux, s'intéressent davantage à
l'interface présentée au logiciel: les commandes acceptées par l'équipement, les fonctions qu'il
assume et les erreurs qu'il peut rapporter. La programmation de plusieurs périphériques d'E/S est
souvent intimement liée à leur fonctionnement interne. C'est pourquoi nous nous intéressons à la
programmation des périphériques et non à leur conception, leur construction ou leur entretien.
Les périphériques d'E/S peuvent être divisés en deux catégories du point de vue des
informations manipulées: les périphériques par blocs et les périphériques par caractères ou
alphanumériques. Un périphérique par blocs stocke des informations dans des blocs de taille fixe,
chacun possédant sa propre adresse. La taille classique des blocs s'étend de 512 à 32768 octets.
La propriété essentielle d'un périphérique par blocs est qu'il permet d'écrire et de lire chaque bloc
indépendamment des autres. Les disques représentent les périphériques par blocs les plus
courants.
Les périphériques alphanumériques représentent l'autre type de périphériques d'E/S. Le
périphérique alphanumérique accepte ou fournit un flot de caractères, sans aucune structure de
blots. Il n'est pas adressable et ne possède aucune fonction de recherche. Les imprimantes, les
interfaces réseaux, les souris et la plupart des autres périphériques que l'on ne peut apparenter à
des disques peuvent être considérés comme des périphériques alphanumériques. Toutefois cette
classification n'est pas parfaite: certains périphériques ne correspondent pas à chacun de ce
schéma. Les horloges, par exemple, ne sont pas adressables par blocs, pas plus qu'elles ne
génèrent ou n'acceptent des flots de caractères. Elles servent simplement à provoquer des
interruptions à des intervalles réguliers définis. Les écrans avec mappage mémoire ne
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 115
Les unités d'E/S sont généralement constituées d'un composant mécanique et d'un
composant électronique. Il est souvent possible de séparer les deux parties pour bénéficier d’une
conception modulaire. Le composant électronique s'appelle un contrôleur de périphérique ou
adaptateur. Sur les ordinateurs personnels, il prend souvent la forme d'une carte avec circuit
imprimé que l'on doit insérer dans un connecteur d'extension. Le composant mécanique est le
périphérique lui-même.
La carte du contrôleur est généralement équipée d'un connecteur sur lequel est branché un
câble que l'on connecte au périphérique. De nombreux contrôleurs sont en mesure de gérer 2,4,
voire 8 périphériques identiques.
L'interface entre le contrôleur et le périphérique est souvent de très bas niveau. Un disque,
par exemple, peut être formaté avec 256 secteurs de 512 octets par piste. Le lecteur produit en
réalité un flot binaire série, qui commence par un synchroniseur initial ou préambule, suivi des
4096 bits d'un secteur, et se termine par un total de contrôle, appelé souvent ECC (Error-
Correcting Code, code de correction d'erreurs). Le préambule est écrit au moment du formatage
du disque. Il contient le numéro du cylindre et du secteur, la taille du secteur et d'autres données
similaires, ainsi que les informations de synchronisation
Le travail du contrôleur consiste à convertir le flot binaire série en un bloc d'octets et à
apporter toute correction qui s'impose en cas d'erreur. Le bloc d'octets assemblé, bit par bit, dans
un tampon qui se trouve au sein du contrôleur. Une fois que le total de contrôle a été vérifié et
que le bloc a été déclaré sans erreur, il peut être copié dans la mémoire principale.
le processeur lit dans PORT du registre de contrôle et stocke le résultat dans le REG du registre
du processeur. De même, avec
le processeur écrit le contenu de REG dans un registre du contrôleur. La majorité des ordinateurs
récents, comme presque tous les mainframes, tels IBM 360 et ses successeurs, fonctionne ainsi.
Dans cette configuration, les espaces d'adressage de la mémoire et des E/S sont distincts, comme
l'illustre la figure 5.2. (a) Ainsi, les instructions .
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 117
>> R0, 4
et
>> MOV R0,4.
sont complètement différentes dans cette conception. La première instruction lit le contenu du
port d'E/S 4 et le place en R0 alors que la seconde lit le contenu du mot 4 de la mémoire et le
place dans R0. Les valeurs 4 de ces exemples se réfèrent à des espaces d'adressages différents et
sans aucun rapport entre eux.
0xFFF… Mémoire
Ports d’E/S
sont nécessaires pour lire et écrire dans les registres de contrôle du périphérique, leur accès
demande l’usage de code assembleur puisqu’il n’existe aucun moyen d’exécuter une instruction
IN ou OUT en C ou C++. L’appel d’une telle procédure surcharge le contrôle des E/S. Par contre,
avec les E/S mappées en mémoire, les registres de contrôle sont de simples variables en mémoire
et peuvent être adressés en C, à l’instar de toute autre variable. Ainsi, avec les E/S mappées en
mémoire, un pilote de périphérique d’E/S peut être entièrement écrit en C. Sans E/S mappées en
mémoire, il faut du code assembleur.
De plus, avec les E/S mappées en mémoire, aucun mécanisme de protection spécial n’est
nécessaire pour empêcher les processus utilisateur d’effectuer des E/S. Il suffit que le système
d’exploitation s’abstienne de placer dans l’espace d’adressage virtuel d’un utilisateur la portion
de l’espace d’adressage contenant les registres de contrôle. En outre, si les registres de contrôle
de chaque périphérique sont placés dans une page différente de l’espace d’adressage, le système
d’exploitation peut donner à un utilisateur le contrôle de certains périphériques et pas à d’autres,
en incluant simplement les pages nécessaires dans son tableau de pages. Une telle configuration
permet de placer différents pilotes de périphériques dans des espaces d’adressage différentes, ce
qui réduit la taille du noyau et évite les interfaces entre les différents pilotes.
Enfin, avec les E/S mappées en mémoire, chaque instruction qui peut référencer de la
mémoire est également en mesure de référencer les registres de contrôle. S’il n’y a pas d’E/S
mappées en mémoire, le registre de contrôle doit d’abord être lu dans le processeur, puis testé, ce
qui nécessite deux instructions au lieu d’une.
Les E/S mappées en mémoire possèdent par ailleurs des inconvénients. D’abord, la
plupart des ordinateurs actuels disposent d’une forme de mise en cache de mots mémoire. Il serait
désastreux de placer dans le cache le registre de contrôle d’un périphérique. La variable peut être
écrasée par une instruction précédente et lors de la demande du périphérique, le logiciel risque de
ne plus retrouver la variable.
Ensuite, s’il n’ y a qu’un espace d’adressage, tous les modules mémoire et tous les périphériques
d’E/S doivent examiner toutes les références mémoire pour savoir à qui ils doivent répondre.
La figure ci-dessous illustre les adresses des périphériques dans un ordinateur. La taille de ces
adresses sont fonctions des différents registres disponibles dans les périphériques.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 119
Que le processeur possède ou non des E/S mappées en mémoire, il doit adresser les
contrôleurs de périphérique pour échanger des données avec eux. Le processeur peut demander
les données au contrôleur d'E/S octet par octet, mais il gaspille ainsi le temps du processeur. On
fait souvent donc appel à une configuration différente et plus performante, appelée DMA (Direct
Memory Acces, accès direct à la mémoire). Le système d'exploitation peut exploiter le DMA
uniquement si le matériel est équipé d'un contrôleur DMA. Le contrôleur DMA a accès au bus
système sans être tributaire du processeur, comme l'illustre la figure 5.3. Il contient plusieurs
registres dans lesquels le processeur peut lire et écrire, dont un registre d'adressage mémoire, un
registre de décompactage d'octets et un ou plusieurs registres de contrôle. Ces derniers spécifient
le port d'ES à employer, la direction du transfert (lecture du périphérique d'E/S ou écriture dans le
périphérique d'E/S), l'unité de transfert (un octet ou un mot à la fois) et le nombre d'octets à
transférer par rafale.
contrôleur de disque (étape 2). Lorsque le contrôleur récupérée le mot suivant dans son tampon, il
sait où l'écrire. Une fois que chaque mot a été transféré (étape 2 à 4), le contrôleur DMA décide
du périphérique à servir ensuite. .
On peut connecter un périphérique rapide, comme par exemple une unité de disques, au
bus système. De nombreux bus peuvent fonctionner selon deux modes: mode avec un mot à la
fois ou mode bloc. Certains contrôleurs DMA peuvent également employer l'un ou l'autre mode.
Dans le premier mode, la progression est semblable à celle décrite précédemment: le contrôleur
DMA demande le transfert d'un mot et l'obtient. Si le processeur réclame aussi le bus, il doit
attendre que le transfert soit effectué. Ce procédé est appelé vol de cycle (cycle stoling). En mode
bloc, le contrôleur DMA demande au périphérique d'acquérir le bus, il émet une série de
transferts puis libère le bus. Il s'agit d'un fonctionnement en mode rafale (burst mode)
La plupart des contrôleurs DMA font appel à des adresses mémoire physiques pour les
transferts. Pour se servir des adresses physiques, le système d’exploitation doit convertir en
adresse physique l’adresse virtuelle du tampon mémoire prévu, puis écrire cette adresse physique
dans le registre d’adressage du contrôleur DMA. Au lieu de cela, certains contrôleurs DMA
procèdent selon un autre schéma, qui consiste à écrire les adresses virtuelles dans le contrôleur
DMA. Ce dernier doit alors utiliser la MMU (Memory Management Unit, unit de gestion
mémoire) pour réaliser la conversion virtuelle/physique.
Les ordinateurs n’exploitent pas tous le DMA (très lent). Le processeur qui est plus
rapide, peut effectuer toute l’opération d’E/S s’il n’a pas d’autre tâche à accomplir.
Dans un ordinateur personnel classique, la structure des interruptions est analogue à celle
de la figure 5.4. Au niveau matériel, les interruptions fonctionnement de la manière suivante:
lorsqu'un périphérique d'E/S a terminé la tâche qui lui était révolue, il déclenche une interruption.
Pour ce faire, il émet un signal sur la ligne du bus auquel il a été assigné. Le signal est détecté par
la puce du contrôleur d'interruption sur la carte mère, qui décide de la suite à donner.
Fig. 5.4. Comment se produit une interruption ? Les connexions entre les périphériques et le contrôleur
d’interruptions passent par les lignes d’interruption du bus et non par des câbles dédiés.
demande simultanée sur une ligne de bus d'une priorité supérieure, le périphérique est ignoré
pour l'instant. Dans ce cas, il continue d'émettre un signal d'interruption sur le bus jusqu'à ce qu'il
soit servi par le processeur. Pour gérer l'interruption, le contrôleur place un numéro sur les lignes
d'adressage afin de désigner le périphérique qui réclame de l'attention et émet un signal qui
interrompt le processeur.
A la réception du signal d'interruption, le processeur arrête la tâche en cours et commence
une autre tâche. Le numéro qui se trouve sur les lignes d'adressages est utilisé comme index dans
une table appelée vecteur d'interruption, pour charger le compteur ordinal avec une nouvelle
valeur, qui correspond au point de départ de la procédure de service de l'interruption
correspondante.
Le matériel confirme toujours certaines informations avant de commencer la procédure de
service. Les informations enregistrées et l'emplacement où elles le sont varient considérablement
d'un processeur à l'autre. Il faut au minimum enregistrer le compteur ordinal pour que le
processus interrompu puisse redémarrer, mais tous les registres visibles et un grand nombre de
registres internes peuvent également être enregistrés.
L'un des problèmes qui se posent est de savoir où enregistrer ces informations. L'une des
options consiste à les placer dans des registres internes que le système d'exploitation peut lire en
cas de besoins. Mais la plupart des processeurs enregistrent les informations sur la pile. Mais
quelle pile employer ? Si on se sert de la pile en cours, il peut fort bien s'agir de la pile d'un
processus utilisateur. Il est également possible que le pointeur de la pile ne soit pas autorisé, ce
qui provoque une erreur fatale lorsque le matériel essaie d'y écrire des mots. Si on utilise la pile
du noyau, il y a plus de chances que le pointeur soit autorisé et qu'il pointe vers une page fixe.
Toutefois, le basculement en mode noyau peut nécessiter le changement des contextes
MMU, ce qui invaliderait probablement une grande partie du cache et du tampon TLB. On
gaspille du temps processeur.
Un autre problème est dû au fait que les processeurs modernes sont fortement à base de
pipeline et sont souvent à base d'architectures super scalaires (parallèles). Sur les systèmes plus
anciens, après la fin de l'exécution de chaque instruction, le microgramme ou le matériel
vérifiaient s'il y avait une interruption en attente. Si tel était le cas, le compteur ordinal et le PSW
(Program Status Word, mot d'état du programme) étaient placés sur la pile et la séquence
d'interruption commençait. Après exécution du gestionnaire d'interruption, le processus inverse
avait lieu: l'ancien PSW et le compteur ordinal étaient retirés de la pile et le processus précédent
continuait. Dans le cas des processeurs à base de pipeline cette procédure n'est plus de mise.
L'interruption pour être prise en compte doit laisser l'ordinateur dans un état bien défini. Une telle
interruption s'appelle une interruption précise-et possède quatre propriétés:
le compteur ordinal (PC) est enregistré dans un emplacement précis ;
toutes les instructions qui précèdent celle pointée par le PC ont été entièrement
exécutées;
aucune instruction au-delà de celle pointée par le PC n'a été exécutée;
l'état d'exécution de l'instruction pointée par le PC est connu.
Une interruption qui ne répond pas à ces exigences est appelée une interruption imprécise et
complique la vie du développeur du système d'exploitation, qui doit comprendre ce qui se passe
et ce qui doit encore se produire.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 122
L'un des concepts clés des logiciels d'E/S est celui de l'indépendance par rapport .au
matériel. Cela signifie qu'il doit être possible d'écrire des programmes qui accèdent à n'importe
quel périphérique d'E/S sans qu'il soit nécessaire de préciser le matériel à l'avance. Par exemple,
un programme qui lit un fichier en entrée doit être capable de lire un fichier qui se trouve sur une
disquette, un disque dur ou un CD-ROM, sans qu'il faille modifier le programme en fonction du
périphérique. En outre, on doit pouvoir taper une commande comme
et la voir fonctionner, que l'entrée provienne d'une disquette, d'un disque IDE, d'un disque SCSI
ou du clavier, et que la sortie aille sur disque ou sur écran. C'est au système d'exploitation de
régler les problèmes dus aux différences entre les périphériques.
Le principe de désignation universelle est étroitement lié à l'indépendance par rapport au
matériel. Le nom d'un fichier ou d'un périphérique doit être une chaîne simple ou un entier simple
et ne doit dépendre en aucune manière du périphérique.
Sous UNIX, tous les disques peuvent être intégrés dans la hiérarchie du système de
fichiers de manière arbitraire. Ainsi, l'utilisateur n'a pas besoin de connaître le nom qui
correspond à un périphérique donné.
La gestion des erreurs est un autre point clé lié aux logiciels d'E/S. En général, les erreurs
sont gérées aussi près du matériel que possible. Si le contrôleur découvre une erreur de lecture, il
essaie de la corriger. S'il ne le peut pas, c'est le pilote de périphérique qui gère, en essayant par
exemple de relire le bloc.
Les transferts synchrones (bloquants) et les transferts asynchrones (pilotés par les
interruptions) sont également importants. La plupart des E/S physiques sont asynchrones: le
processeur commence le transfert et passe à autre chose en attendant l'interruption. Mais les
programmes utilisateurs sont bien plus simples à écrire si les opérations d'E/S sont bloquantes:
après un appel read du système, le programme est automatiquement suspendu jusqu'à ce que les
données soient disponibles dans le tampon.
La mise en mémoire tampon est un autre principe des logiciels d'E/S. Il arrive souvent que
les données qui proviennent d'un périphérique ne puissent pas être stockées directement dans leur
emplacement final. Par exemple, lorsqu'un paquet se présente en provenance d'un réseau, le
système d'exploitation ne sait pas où le placer avant de l'avoir stocké et examiné. En outre,
certains périphériques (comme les périphériques de son numérique) sont soumis à des contraintes
de temps réel importantes. Par conséquent, les données doivent être placées préalablement dans
un tampon de sortie afin d'établir une séparation entre le débit auquel le tampon est rempli et le
débit auquel il est vidé, et d'éviter les baisses de régimes du tampon.
Le dernier concept concerne les périphériques partageables et ceux qui ne le sont pas.
Certains périphériques d'E/S, tels les disques, peuvent être exploités simultanément par plusieurs
utilisateurs. En revanche, des périphériques, comme les lecteurs de bandes doivent être dédiés
(non partagé) à un seul utilisateur jusqu'à la fin de l'opération.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 123
Il existe trois manières fondamentalement différentes de construire des E/S : les E/S
programmées; les E/S pilotées par les interruptions et les E/S utilisant le DMA. La façon la plus
simple de gérer les E/S consiste à laisser le processeur s'occuper de toute l'opération. Cette
méthode est celle des E/S programmées.
Prenons l'exemple d'un processus utilisateur qui veut imprimer une chaîne de huit
caractères, « ABCDEFGH » sur l'imprimante. Il commence par assembler la chaîne dans un
tampon de l'espace utilisateur, comme l'illustre la figure 5.5(a).
Fig. 5.6. Ecriture d'une chaîne sur l'imprimante via une E/S programmée
Prenons à présent l'exemple d'une impression sur une imprimante qui ne place pas les
caractères en mémoire tampon mais imprime chaque caractère dès qu'il se présente. Par exemple,
si l'imprimante est en mesure d'imprimer 100 caractères/s, il faut 10 ms pour imprimer chaque
caractère. Cela signifie qu'après que chaque caractère est écrit dans le registre des données de
l'imprimante, le processeur se trouve dans une boucle inactive pendant 10 ms en attendant de
pouvoir sortir le prochain caractère. Cela est plus que suffisant pour procéder à un changement de
contexte et exécuter un autre processus durant ces 10 ms, qui sans cela auraient été perdues.
Pour permettre au processeur de réaliser d'autres opérations pendant qu'il attend que
l'imprimante soit à nouveau libre, on fait appel aux interruptions. Lorsque l'appel système pour
imprimer la chaîne est émis, le tampon est copié dans l'espace du noyau, et le premier caractère
est copié dans l'imprimante dès qu'elle peut accepter un caractère. Le processeur appelle alors
l'Ordonnanceur et un autre processus est exécuté. Le processus qui a demandé l'impression de la
chaîne est bloqué jusqu'à ce que toute la chaîne soit imprimée. La figure 5.7 indique la procédure
suivie lors d'un appel système.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 125
Fig.5.7. Ecriture d'une chaîne sur l'imprimante via une E/S pilotée par les interruptions. (a) code exécuté lorsque
l'appel système d'impression est émis. (b) procédure du service d'interruption.
Lorsque le caractère a été imprimé et que l'imprimante est prête à accepter le suivant, elle
génère une interruption. Celle-ci arrête le processus en cours et enregistre son état. Ensuite, on
exécute la procédure du service d'interruption de l'imprimante. La figure 5.7 (b) montre une
version brute de ce code. S'il n’y a pas de caractère à imprimer, le gestionnaire d'interruptions fait
en sorte de débloquer l'utilisateur. Sinon, il émet le caractère suivant, confirme l'interruption et
retourne au processus qui était en cours d'exécution avant l'interruption, et qui reprend alors où il
était resté.
L'inconvénient évident des E/S pilotées par les interruptions est qu'une interruption se
produit à chaque caractère. Comme les interruptions prennent du temps, cette méthode
consomme une certaine quantité de temps processeur. Une solution consiste à faire appel au
DMA. Dans ce cas, l'idée est de laisser le contrôleur DMA fournir les caractères un à un à
l'imprimante, sans déranger le processeur. Pour l'essentiel, le DMA fonctionne comme une E/S
programmée, à la différence que le contrôleur DMA fait le travail à la place du processeur
principal. Le code associé à l'E/S avec DMA est illustré à la figure 5.8.
(a) (b)
Fig. 5.8. Ecriture d'une chaîne sur l'imprimante via une E/S pilotée par les interruptions. (a) code exécuté lorsque
l'appel système d'impression est émis. (b) procédure du service d'interruption.
Le grand avantage de l'E/S par DMA est de réduire le nombre d'interruptions. On passe
ainsi de une par caractère à une par tampon imprimé. Si les caractères sont nombreux et les
interruptions lentes, l'amélioration peut être considérable. En revanche, le contrôleur DMA est
généralement beaucoup plus lent que le processeur principal. Si le contrôleur DMA n'est capable
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 126
de piloter le périphérique à pleine vitesse les E/S pilotées par les interruptions ou les E/S
programmées peuvent être plus appropriées.
Les logiciels d'E/S s'organisent typiquement en quatre couches, comme l'illustre la figure
5.9. Chaque couche réalise une fonction précise et présente une interface spécifique aux couches
adjacentes.
Si les E/S programmés sont parfois intéressantes, pour la plupart des E/S, il en est tout
autrement des interruptions qui sont une réalité déplaisante qui ne peut être évitée. Il faut les
enfouir dans les entrailles du système d'exploitation, de manière que la partie du système
d'exploitation qui en connaît l'existence soit aussi réduite que possible. Le meilleur moyen de les
dissimuler est de faire en sorte qu'un pilote de périphérique commence une opération d'E/S, se
bloque jusqu'à ce qu'elle soit terminée et que l'interruption se produise. Le pilote peut en effet se
bloquer lui-même en effectuant certaines commandes, par exemple, un down sur un sémaphore,
un wait sur une variable conditionnelle et un receive sur un message.
Pilotes de périphériques
Gestionnaires d’interruptions
Matériel
Donc, le traitement des interruptions est loin d'être insignifiant. Il demande également un
nombre considérable d'instructions processeur, en particulier sur les ordinateurs dans lesquels il
existe une mémoire virtuelle, et pour lesquels il faut configurer des tables des pages ou stocker la
MMU (par exemple, les bits R et M). Sur certains ordinateurs, le cache du TLB et du processeur
doivent être gérés lorsque l'on bascule entre les modes utilisateur et noyau, ce qui augmente le
nombre de cycles de l'ordinateur.
Fig. 5.10. Positionnement logique des pilotes de périphériques. En réalité, toute la communication entre les pilotes et
les contrôleurs de périphériques passe par le bus.
Les systèmes d'exploitation classent généralement les pilotes par catégories. Les
catégories les plus courantes sont les périphériques par blocs (comme les disques qui contiennent
plusieurs blocs de données que l'on peut adresser indépendamment) et les périphériques
alphanumériques (comme les claviers et les imprimantes, qui génèrent ou acceptent des flots de
caractères).
La plupart des systèmes d'exploitation définissent une interface standard, que tous les
pilotes par blocs doivent prendre en charge, et une seconde interface standard qui doit être
supportés par tous les pilotes alphanumériques. Ces interfaces se composent d'un certain nombre
de procédures que le reste du système d'exploitation peut appeler pour pouvoir exploiter le pilote
approprié. Parmi les procédures classiques, on trouve celles qui lisent un bloc (périphériques par
blocs) et celles qui écrivent une chaîne de caractères (périphériques alphanumériques).
Un pilote de périphérique possède plusieurs fonctions. La plus évidente consiste à
accepter les requêtes abstraites de lecture et d'écriture émises par le logiciel qui se trouve au-
dessus de lui et à vérifier qu'elles sont exécutées. Mais il doit prendre en charges d'autres tâches,
comme initialiser le périphérique si nécessaire, ou gérer les exigences en matière d'alimentation
électrique et d’enregistrement des événements.
Un pilote classique commence par vérifier que les paramètres d'entrée sont valides. Si ce
n'est pas le cas, il retourne une erreur. S'ils sont valides, il peut être nécessaire de convertir les
termes abstraits en termes concrets. Pour un pilote de disque, cela implique la conversion d'un
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 129
numéro de bloc linéaire en numéro de tête, piste, secteurs et cylindre selon la géométrie du
disque.
Le pilote vérifie ensuite si le périphérique est utilisé. Le cas échéant, la requête est placée
en file d'attente pour un traitement ultérieur. Si le périphérique est inoccupé, son registre d'état est
examiné pour vérifier que la requête peut être gérée. Il peut être nécessaire d'allumer le
périphérique ou de démarrer un moteur avant de commencer les transferts. Une fois le
périphérique allumé et prêt, le contrôle réel débute.
Le contrôle du périphérique consiste en l'émission d'une séquence de commandes. C'est
dans le pilote qu'est déterminée la séquence de commandes, selon les actions à entreprendre. Une
fois que le pilote connaît les commandes qu'il doit émettre, il les écrit dans les registres de
périphériques du contrôleur. Après que chaque commande est écrite dans le contrôleur, il peut
être nécessaire de vérifier qu'il l’a acceptée et qu’il est prêt à accepter la suivante. Cette séquence
se poursuit jusqu'à ce que toutes les commandes aient été émises. Certains contrôleurs reçoivent
une liste liée de commandes (en mémoire) qu'ils doivent lire et traiter seuls, sans l'aide du
système d'exploitation.
Une fois les commandes mises, deux situations peuvent se présenter. Dans la majorité des
cas, le pilote de périphérique attend que le contrôleur termine sa tâche et se bloque lui-même
jusqu’à ce que l’interruption vienne le débloquer. Dans d’autres cas, l’opération se termine sans
attente, auquel cas le pilote n’a pas besoin de se bloquer : à titre d’exemple, pour faire défiler un
écran en mode caractères, il est seulement nécessaire d’écrire quelques octets dans les registres
du contrôleur.
Bien que certains logiciels d'E/S soient spécifiques au périphérique, ce n'est pas le cas de
tous. La frontière qui sépare les pilotes des logiciels indépendants du périphérique est floue et
dépend du système (et du périphérique). En effet, certaines fonctions qui pourraient être réalisées
indépendamment du périphérique sont en réalité effectuées par les pilotes, entre autres pour des
raisons d'efficacité. Les fonctions de la figure 5.11 sont généralement prises en charge par les
logiciels indépendants du périphérique.
L'un des principaux problèmes d'un système d'exploitation est de faire en sorte que tous les
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 130
périphériques et pilotes d'E/S aient l'air plus ou moins analogues. Si les disques, imprimantes,
claviers, etc., sont tous interfacés de manières différentes, chaque fois qu'un nouveau
périphérique se présente, le système d'exploitation doit être modifié en conséquence. Or, il est
préférable d'éviter de s'attaquer au système d'exploitation à chaque nouvelle installation de
périphérique. La figure 5.12 (a) illustre une situation dans laquelle chaque pilote de périphérique
présente une interface différente au système d'exploitation. Cela signifie que les fonctions mises à
disposition par le pilote pour les appels système, ainsi que les fonctions du noyau dont le pilote a
besoin, diffèrent d'un pilote à l'autre..
Fig. 5.12. : (a) absence d’interface de pilote standard. (b) présence d’interface de pilote standard
En revanche, la figure 5.12 (b) illustre une conception différente dans laquelle tous les
pilotes présentent la même interface. Il devient alors beaucoup plus simple d'insérer un nouveau
périphérique, à condition qu'il se conforme à l'interface du pilote. Dans la pratique, les
périphériques ne sont toujours pas identiques, mais il n’existe qu’un petit nombre de types de
périphériques différents qui présentent dans chaque type de nombreuses similitudes. Ainsi, même
les périphériques par blocs et les périphériques alphanumériques ont des fonctions communes.
Un autre aspect de l’interface uniforme concerne les noms des périphériques d’E/S. Les
logiciels non tributaires du périphérique veillent à mapper les noms de périphériques symboliques
avec les pilotes idoines. Par exemple, sous UNIX, un nom de périphérique comme /dev/disque0
indique uniquement l’i-node d’un fichier spécifique ; ce i-node contient également le numéro de
périphérique majeur, qui sert à localiser le pilote approprié, ainsi le numéro de périphérique
mineur, passé comme paramètre au pilote pour indiquer l’unité à lire ou dans laquelle écrire.
Tous les périphériques possèdent des numéros majeurs et mineurs et on accède à tous les pilotes
par le numéro de périphérique majeur pour sélectionner le pilote.
La mise en mémoire tampon (buffering) est un autre aspect important, tant pour les
périphériques par blocs que pour les périphériques alphanumériques. Elle permet, dans le cas de
transfert caractère par caractère, d'éviter la procédure d'interruption après que chaque caractère
est transféré. Le processus utilisateur peut fournir un tampon de n caractères dans l'espace
utilisateur et la procédure de service de l'interruption place les caractères entrants dans le tampon
jusqu'à ce qu'il soit plein. Le tampon peut être placé dans le noyau. La mise en mémoire tampon
est une technique largement répandue, mais elle possède aussi un inconvénient. Si les données
sont trop souvent placées en mémoire tampon, les performances en souffrent.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 131
- Rapport d'erreurs
Les erreurs sont bien plus courantes dans le contexte des E/S que dans d'autres contextes.
Lorsqu'elles se produisent, le système d'exploitation doit pouvoir les gérer. De nombreuses
erreurs sont spécifiques au périphérique et doivent être gérées par le pilote approprié, mais la
structure de la gestion des erreurs n'est pas tributaire du périphérique. Les erreurs de
programmation, par exemple, un type d’erreurs d’E/S. Elles se produisent quand un processus
demande une opération impossible, comme écrire dans un périphérique d’entrée (clavier, souris,
scanner, ..) ou lire à partir d’un périphérique de sortie (imprimante, table traçante, etc.).
Les erreurs d’E/S sont un autre type d’erreur. Elles se produisent par exemple si on essaie
d’écrire dans un bloc de disque endommagé ou que l’on tente de lire des données provenant d’un
Camescope éteint. Dans de tels cas, c’est au pilote de déterminer ce qu’il convient de faire. S’il
ne le sait pas, il retourne le problème au logiciel non tributaire du périphérique.
Les tailles de secteurs varient d'un disque à l'autre, C'est au logiciel non tributaire du
périphérique de masquer cela et de fournir une taille de bloc uniforme aux couches supérieures.
Pour ce faire, il peut par exemple traiter plusieurs secteurs comme un bloc logique unique, Ainsi,
les couches supérieures ne communiquent qu'avec des périphériques abstraits qui exploitent tous
la même taille de bloc logique, indépendante de la taille des secteurs physiques.
Bien que la grande majorité des logiciels d'E/S résident dans le système d'exploitation,
une petite partie est composée de bibliothèques reliées entre elles par le biais de programmes
utilisateur, voire de programmes s'exécutant en dehors du noyau. Les appels système, y compris
les appels système d'E/S, sont normalement émis par des procédures de bibliothèques. Quand un
programme C contient l’appel
Dans les ordinateurs, on trouve principalement deux types d’horloges. Les horloges les
plus simples sont reliées à une alimentation de 220 volts et déclenchent une interruption à chaque
cycle du signal électrique sinusoïdal à 50 hertz (Europe) et 60 hertz (USA).
Le second type d’horloge est constitué de trois composants : un oscillateur à quartz, un
compteur et un registre de maintien, comme le montre la figure 5.31
Oscillateur à quartz
cristal choisi. A l’aide des quelques composants électroniques, ce signal peut être multiplié pour
obtenir des fréquences allant jusqu’à 1000 Mhz, voire davantage. L’horloge fournit aux divers
circuits d’un ordinateur, un signal de synchronisation qui alimente le compteur jusqu’à 0.
Lorsque le compteur arrive à 0, il génère une interruption, appelée top d’horloge.
La plupart des ordinateurs disposent d’une seconde horloge programmable que l’on
appelle couramment timer et que l’on peut configurer de manière que le compteur s’interrompe
selon l’exigence du programme. Ce timer vient en complément du timer du système principal
dont les fonctions ont été décrites précédemment. Tant que la fréquence d’interruption est faible,
utiliser un second timer spécifiquement pour les applications ne pose aucun problème. Les
problèmes surgissent quand la fréquence du timer dédié aux applications est très élevée.
En règle générale, on rencontre deux manière de gérer les E/S : par les interruptions et par
les interrogations. Les interruptions ont un temps d’attente faible, c’est-à-dire qu’elles se
produisent immédiatement après un événement, avec peu ou pas de délai. En revanche, avec les
processeurs modernes, les interruptions occasionnent une surcharge considérable en raison de la
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 134
CHAPITRE 6
SYSTEME DE FICHIERS
Toutes les applications ont besoin d'enregistrer des informations et de les retrouver. Le
premier problème posé est celui de la capacité de stockage des informations. En effet, lorsqu’ un
processus est en cours d'exécution, il ne peut enregistrer qu’une quantité limitée d'informations
dans son propre espace d'adressage. La capacité de stockage est restreinte à la taille de l'espace
d'adressage virtuelle.
Un deuxième problème qui se pose concerne le stockage des informations dans l'espace
d'adresse d'un processus : ces informations sont perdues quand un programme se termine. Pour
un grand nombre d'applications (par exemple les bases de données), les informations doivent être
conservées pendant des semaines, des mois, voir beaucoup plus. Il n'est donc pas acceptable de
les perdre lorsqu'un processus se termine.
Un troisième problème est que plusieurs processus ont fréquemment besoin d'accéder à
une partie de ces informations simultanément.
Ainsi, nous avons trois conditions essentielles pour un stockage à long terme de
l'information:
1. Il faut pouvoir enregistrer une très grande quantité d'informations.
2. Les informations doivent être conservées après la fin d'un processus qui les utilise.
3. Plusieurs processus doivent pouvoir accéder simultanément à une information.
La solution couramment employée pour traiter tous ces problèmes consiste à stocker
l'information sur des disques ou d'autres supports externes dans des unités appelés fichiers. Les
processus peuvent ainsi les lire, les écrire ou en créer si nécessaire. L'information enregistrée
dans des fichiers doit être persistante, c'est-à-dire qu'elle ne doit pas être affectée par la création
ou la fin d'un processus. Un fichier doit seulement disparaître quand son propriétaire le demande
expressément.
Les fichiers sont gérés par le système d'exploitation. Leurs structures, nommage, accès,
utilisation, protection et implantation sont des éléments majeurs de la conception d'un système
d'exploitation. Généralement la partie du système d'exploitation qui gère les fichiers est connue
sous le nom de système de fichier. Ce terme désigne donc à la fois, le principe d’organisation
des fichiers, les éléments de logiciel qui implémentent (réalisent) ce principe, et un ensemble de
fichiers organisés selon ce principe. Plusieurs systèmes de fichiers peuvent résider sur un disque.
6.1. Fichiers
Les fichiers sont un mécanisme d'abstraction. Ils permettent d'écrire des informations sur
un disque et de les lire plus tard. Mais l'utilisateur ne doit pas voir en détail comment et où est
stockée l'information, ni comment les disques fonctionnent.
Quand un processus crée un fichier, il lui donne un nom. Quand le processus se termine,
le fichier continue d'exister et d'autres processus peuvent y accéder via son nom.
Les règles exactes à appliquer pour nommer un fichier varient quelque peu d'un système à
l’autre. Les systèmes usuels autorisent des chaînes composées de 1 à 8 caractères pour former les
noms des fichiers. Certains systèmes de fichiers distinguent les majuscules des minuscules (ils
sont sensibles à la casse, comme UNIX) d'autres non, comme le MS-DOS et WINDOWS. De
nombreux systèmes de fichiers supportent des noms d’une longueur de 255 caractères.
De nombreux systèmes d'exploitation gèrent des noms de fichiers en deux parties séparées
l'une de l'autre par un point, comme dans progr.c. La partie qui suit le point, appelé l'extension
du fichier, indique normalement le type de fichier. Dans MS-DOS, par exemple, les noms de
fichiers ont 1 à 8 caractères plus une extension facultative de 1 à 3 caractères. Dans UNIX, la
taille de l’extension, si elle existe, dépend de l’utilisateur. En outre, un fichier peut avoir deux
extensions ou plus, comme prog.c.Z, où Z est communément employé pour indiquer que le
fichier (prog.c) a été compressé à l’aide de l’algorithme de compression normal. Quelques-
unes des extensions les plus courantes et leurs significations sont données à la figure 6.1.
Extension Signification
fichier.bak Fichier de sauvegarde
fichier.c Fichier source d’un programme C
fichier.gif Fichier image de format GIF(Graphical Interchange
Format)
fichier.hlp Fichier d’aide
fichier.html Fichier document en langage HTML (Hyper Text Markup
Language)
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 137
Dans certains systèmes (comme UNIX), les extensions de fichiers sont simplement des
conventions et ne sont pas imposées par le système d'exploitation. D'un autre côté, un
compilateur C insistera pour que les fichiers à compiler possèdent une extension en .c, et il
refusera de faire la compilation dans le cas contraire.
En revanche, Windows reconnaît les extensions et leur attribue une action. Les utilisateurs
(ou les processus) peuvent enregistrer des extensions avec le système d'exploitation et spécifier
pour chacune d'entre elles le programme qui lui est associé.
Les fichiers peuvent être structurés de différentes manières. La figure 6.2 illustre trois
structures possibles. Le fichier (a), est une séquence d'octets non structurée. Ici le système
d'exploitation ne s'occupe pas du contenu de ce fichier, il ne voit que des octets. Toute
signification doit être apportée par les programmes des utilisateurs. UNIX et Windows suivent
tous deux cette approche. Les programmes des utilisateurs peuvent mettre ce qu'ils veulent dans
les fichiers et les nommer à leur gré.
Le premier niveau de structure est montré à la figure (b). Dans ce modèle, un fichier est
une séquence d'enregistrements de longueur fixe, qui ont chacun une structure interne. Pour les
fichiers organisés de cette manière, le concept principal est qu'une opération de lecture renvoie un
enregistrement et qu'une opération d'écriture réécrit ou ajoute un enregistrement.
Le troisième type de structure de fichiers est présenté à la figure (c ). Dans cette organisation, un
fichier est un arbre d'enregistrements qui ne sont pas nécessairement tous de même longueur, et
dont chacun contient une clé dont la position est fixe dans l'enregistrement. Ici, l'opération
fondamentale ne consiste pas à obtenir le prochain enregistrement, bien que ce soit possible, mais
à obtenir un enregistrement avec une clé donnée.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 138
1 enregistrement
1 octet (byte) (record)
Ane Pan Chèvre
(a) (b) (c )
Fig.6.2. Trois sortes de fichiers. (a) Séquence d’octets. (b) Séquence d’enregistrement. (c ) Arbre
Les premiers systèmes d'exploitation proposaient un seul type d'accès aux fichiers : l'accès
séquentiels. Dans ces systèmes, un processus pouvait lire tous les octets ou tous les
enregistrements d'un fichier dans l'ordre, en commençant au début, mais il n pouvait pas les lire
dans le désordre. Les fichiers séquentiels étaient pratiques quand le support de stockage était une
bande magnétique plutôt qu' un disque.
Quand les disques ont servi à l'enregistrement des fichiers, il est devenu possible de lire
des octets ou des enregistrements d'un fichier dans n'importe quel ordre, ou d'accéder aux
enregistrements avec des clés plutôt qu'à partir de leur position. Les fichiers dont les octets ou les
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 139
enregistrements peuvent être lus dans n'importe quel ordre sont appelés fichiers à accès aléatoires
(random acces files), qui sont nécessaires à de nombreuses applications. Ces fichiers sont par
exemple indispensables aux bases de données.
Chaque fichier possède un nom et des données. De plus, tous les systèmes d'exploitation
associent des informations complémentaires à chaque fichier, comme l'heure et la date de
création du fichier, et sa taille.
. Nous appellerons ces informations les attributs du fichier. Un attribut est défini par un nom et un
domaine de valeurs. Le nom sert à désigner l'attribut; deux attributs distincts ont des noms différents. Le
domaine de valeurs spécifie les valeurs possibles que peut prendre l'attribut.
La liste des attributs varie considérablement d'un système à l'autre. La figure 6.4 en présente
quelques-uns, mais il en existe d'autres. Aucun système ne les gère tous, mais chacun est présent
dans un système ou dans un autre.
Attributs Signification
Protection Qui peut accéder au fichier et de quelle manière
Mot de passe Mot de passe nécessaire pour accéder au fichier
Créateur Créateur du fichier
Propriétaire Propriétaire actuel du fichier
Indicateur lecture seule 0 pour lecture/écriture, 1 pour lecture seule
Indicateur fichier caché 0 pour un fichier normal, 1 pour un fichier caché
Indicateur fichier système 0 pour un fichier normal, 1 pour un fichier système
Indicateur d’archivage 0 si le fichier a été archivé, 1 s’il doit être archivé
Indicateur fichier ASCII/binaire 0 pour un fichier ASCII, 1 pour un fichier binaire
Indicateur fichier accès aléatoire 0 pour un accès séquentiel, 1 pour un accès aléatoire
Indicateur fichier temporaire 0 pour un fichier normal, 1 pour supprimer le fichier lorsque le processus se
termine
Indicateur de verrouillage 0 pour un fichier non verrouillé, 1 pour un fichier verrouillé
Longueur d’enregistrement Nombre d’octets dans l’enregistrement
Position de la clé Position de la clé dans chaque enregistrement
Longueur de la clé Nombre d’octets du champ clé
Date de création Date et heure de création du fichier
Date du dernier accès Date et heure du dernier accès au fichier
Date de modification Date et heure de la dernière modification
Taille courante Nombre d’octets du fichier
Taille maximale Taille maximale autorisée pour le fichier
Les quatre premiers attributs sont liés à la protection du fichier et précisent qui peut accéder au
fichier. Les indicateurs sont des bits ou de petits champs qui contrôlent certaines propriétés
spécifiques. Les champs longueurs d’enregistrement, position de clé et longueur de clé se
trouvent uniquement dans les fichiers dont les enregistrements peuvent être recherchés avec une
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 140
clé. Les différentes dates mémorisent les dates et heures de création, de dernier accès et de
dernière modification. La taille courante indique la taille actuelle du fichier.
Les fichiers servent à stocker des informations et à les retrouver plus tard. Des systèmes
différents permettent des opérations différentes pour réaliser le stockage et la recherche. Ci-après
les principaux appels système relatifs aux fichiers :
1. Create : Le fichier est créé sans données. Le but de cet appel est d’indiquer la création
du fichier et de fixer un certain nombre de paramètres.
2. Delete : Quand un fichier n’est plus utilisé, il doit être supprimé pour libérer de
l’espace disque.
3. Open : Avant de servir d’un fichier, un processus doit l’ouvrir. Le but de cet appel est
de permettre au système de charger les attributs et la liste des adresses du fichier sur le
disque afin d’accélérer les accès ultérieurs.
4. Close : Quand tous les accès au fichier sont terminés, les attributs et les adresses du
fichiers ne sont plus nécessaires, par conséquent le fichier peut être fermé pour libérer de
l’espace dans les tables internes.
5. Read : Les données sont lues à partir du fichier
6. Write : Les données sont écrites dans un fichier, généralement à partir de la position
courante. Si la position courante est la fin du fichier, la taille du fichier augmente. Si la
position courante est le milieu du fichier, les données existantes sont remplacées et
définitivement perdues.
7. Append : Cet appel correspond à l’appel d’un write restreint. On en peut ajouter des
données qu’à la fin du fichier.
8. Seek : Pour les fichiers à accès aléatoire, il est nécessaire de préciser la position des
donnés à lire et à écrire. Une façon usuelle de le faire est un appel système seek qui
repositionne le pointeur à un endroit précis dans le fichier. Après exécution de l’appel,
les données sont lues ou écrites de cette position.
9. Get attributes : Les processus doivent souvent lire les attributs des fichiers pour
effectuer certaines opérations.
10. Set attributes : Certains attributs peuvent être déterminés par l’utilisateur et
modifiés après la création du fichier. Cet appel système sert à cela ;
11. Rename : Il arrive fréquemment qu’un utilisateur ait besoin de changer le nom d’un
fichier existant, ce qui est possible grâce à l’appel système rename. Cet appel n’est pas
strictement indispensable puisqu’un fichier peut généralement être copié dans un fichier
sous un nom différent, avant d’être effacé.
Pour conserver une trace des fichiers, les systèmes de fichiers possèdent généralement des
répertoires (catalogues) ou des dossiers, qui sont eux-mêmes des fichiers dans nombre de
systèmes (Unix).
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 141
Le répertoire (directory) le plus basique est un répertoire qui contient tous les fichiers. On
l’appelle quelquefois répertoire racine (root). Sur les premiers ordinateurs personnels, ce
systèmes était pratique, notamment parce qu’il y avait un seul utilisateur.
Un exemple de système avec un répertoire unique est donné à la figure 6.5. Ici le
répertoire possède quatre fichiers. Sur la figure nous indiquons les propriétaires des fichiers mais
pas les noms des fichiers.
Répertoire racine
A A B C
Fig. 6.5. : Système de répertoire à un seul niveau contenant quatre fichiers possédés par trois propriétaires différents
A, B et C.
Pour éviter les conflits qui surgissent lorsque différents utilisateurs choisissent un nom
identique pour leurs fichiers, il faut donc donner à chaque utilisateur un répertoire privé. De cette
façon, les noms choisi par un utilisateur ne vont pas interférer avec ceux d’un autre utilisateur et
il n’existe plus de problèmes dus au fait que des noms identiques se retrouvent dans plusieurs
répertoires. Cette conception est illustrée à la figure 6.6. Un tel système peut être exploité, par
exemple, dans un ordinateur multiutilisateur ou dans un simple réseau d’ordinateurs personnels
qui partagent un serveur de fichiers sur un réseau local.
Répertoire racine
Répertoire utilisateur
A B C
A A B B C C
Dans cette conception, il est implicite que lorsqu’un utilisateur essaie d’ouvrir un fichier,
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 142
le système sait à quel utilisateur il a affaire afin de savoir dans quel répertoire chercher.
Quand ce système est implanté dans sa forme la plus simple, les utilisateurs peuvent
uniquement accéder aux fichiers de leurs propres répertoires. On peut toutefois permettre aux
utilisateurs d’accéder aux fichiers d’autres utilisateurs en précisant certaines indications sur le
fichier à ouvrir.
La structure à deux niveaux élimine les conflits de noms entre les utilisateurs mais n’est
pas satisfaisante pour les utilisateurs qui ont un grand nombre de fichiers. Même sur un
ordinateur personnel avec un seul utilisateur, elle présente des inconvénients. Les utilisateurs
souhaitent souvent regrouper leurs fichiers de manière logique. Dans ce cas, une hiérarchie
générale, c’est-à-dire un arbre à répertoires, est nécessaire. Elle permet à chaque utilisateur
d’avoir autant de répertoires qu’il le souhaite afin de regrouper ses fichiers de manière logique.
Cette approche est présentée à la figure 6.7. Ici les répertoires A, B et C situés à la racine
appartiennent à des utilisateurs différents, deux d’entre eux ayant créé des sous-répertoires pour
des projets sur lesquels ils travaillent. Les systèmes modernes sont organisés suivant le modèle de
la figure 6.7.
Répertoire racine
répertoire utilisateur
A B C
A B B C C
B C C
C C C C
Quand le système de fichiers est organisé comme un arbre de répertoires, il faut trouver
un moyen de spécifier les noms de fichiers. On emploie couramment deux méthodes. En suivant
la première méthode, on donne à chaque fichier un chemin d’accès absolu qui reprend le chemin
de la racine jusqu’au fichier. Par exemple, le chemin /usr/jlb/courrier indique le
répertoire racine contient le sous-répertoire usr, qui comprend le sous-répertoire jlb, lequel
possède à son tour le fichier courrier. Les chemins d’accès absolu commencent toujours par
la racine et sont uniques. Dans UNIX, les parties du chemin d’accès sont séparées par le symbole
/ (slash), et par \ (backslash) dans Windows.
Il existe aussi des chemins d’accès relatifs, qui fonctionne conjointement avec le concept
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 143
La plupart des systèmes qui possèdent une structure hiérarchique de répertoires ont deux
entrées particulières dans chaque répertoire : « . », et « .. ». Dot fait référence au répertoire
courant, et dotdot au répertoire parent.
Les appels système autorisés pour la gestion des répertoires varient davantage d’un
système à l’autre que les appels système pour la gestion des fichiers. Nous présentons ci-après un
échantillonnage de ces appels.
1. Create : Un répertoire est créé. Il est vide mais comprend . et .. qui sont placés
automatiquement par le système.
2. Delete : Un répertoire est supprimé. Seuls les répertoires vides peuvent être supprimés.
3. Opendir : Les répertoires peuvent être lus. Par exemple, pour lister tous les fichiers dans
un répertoire, un programme de listing ouvre le répertoire afin d’extraire les noms de tous
les fichiers qu’il contient. Avant qu’un répertoire ne puisse être lu, il doit être ouvert, dela
même manière qu’un fichier.
4. Closedir : Quand un répertoire a été lu, il doit être fermé pour libérer de l’espace dans
les tables internes.
5. Readdir : Cet renvoie la prochaine entrée d’un répertoire ouvert.
6. Rename : Les répertoires comme les fichiers peuvent être renommés.
7. Link : Le lien permet à un fichier d’apparaître dans plus d’un répertoire. Cet appel
système désigne un fichier existant et un chemin d’accès, et il crée un lien depuis le
fichier existant vers le fichier indiqué par le chemin d’accès. De cette façon, le même
fichier peut apparaître dans plusieurs répertoires.
8. Unlink : Une entrée de répertoire est supprimée. Si le fichier qui est dédié est uniquement
présent dans un répertoire (le cas normal), il est effacé du système de fichier.
A présent, il est temps de passer du point de vue de l’utilisateur à celui du concepteur. Les
utilisateurs se préoccupent de la manière dont les fichiers sont nommés, des opérations qui sont
autorisées, de l’arborescence des fichiers, etc. Les concepteurs, eux, sont plutôt intéressés par
l’organisation de l’espace du disque et par la manière de rendre le système de fichiers efficace et
fiable, aspects que nous allons étudier dans les sections qui suivent.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 144
Les systèmes de fichiers sont enregistrés sur les disques. La plupart des disques peuvent
être divisés en une ou plusieurs partitions, avec des systèmes de fichiers indépendants sur chaque
partition. Le secteur 0 du disque, appelé MBR (Master Boot Record), sert à « booter » (démarrer)
la machine. La fin du MBR comprend la table des partitions, laquelle indique l’adresse de début
et de fin de chaque partition. Une de ces partitions est marquée comme étant la partition active.
Quand l’ordinateur a booté, le BIOS lit et exécute le MBR. En premier lieu, le programme MBR
localise la partition active, y lit le premier bloc, appelé bloc de boot, et l’exécute. Le programme
dans le bloc de boot charge le système d’exploitation contenu dans cette partition.
Mis à part le démarrage avec un bloc de boot, l’organisation d’une partition de disque
varie fortement d’un système de fichiers à l’autre. Le système de fichiers comprendra souvent
quelques-uns des items présentés à la figure 6.8. Le premier d’entre eux est le superbloc, réservé
au système. Il contient tous les paramètres clés concernant le système de fichiers, et est mis en
mémoire quand l’ordinateur démarre ou quand le système de fichier est modifié. Les
informations caractéristiques du super bloc incluent un nombre magique qui identifie le type du
système de fichiers, le nombre de blocs du système de fichiers et d’autres informations
importantes relatives à l’administration.
Viennent ensuite des informations sur les blocs libres du système de fichiers, par exemple sous
forme de tables de bits ou de listes chaînées. Elles sont suivies des i-nodes (un tableau contenant
toutes les caractéristiques d’un fichier), une i-node par fichier. Enfin, on trouve le répertoire
racine, qui contient le haut de l’arborescence du système de fichiers et, pour terminer, le reste du
disque qui renferme tous les répertoires et les fichiers.
MBR
L’aspect important dans le stockage des fichiers est probablement la mémorisation des adresses
de tous les blocs assignés à chaque fichier. Différentes méthodes sont employées.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 145
Allocation contigüe
La méthode d’allocation la plus simple consiste à stocker chaque fichier dans une suite de blocs
consécutifs. Ainsi, dans un disque avec des blocs de 1 Ko, un fichier de 50 Ko se verra allouer 50
blocs consécutifs. Nous donnons un exemple d’allocation contigüe à la figure 6.9. Les 40
premiers blocs du disque y sont indiqués, démarrant avec le bloc 0 sur la gauche. Initialement, le
disque est vide. Ensuite, un fichier A, d’une longueur de 4 blocs, est écrit sur le disque à partir du
début (bloc 0). Puis c’est un fichier d’une longueur de 6 blocs, B, qui est écrit juste après la fin du
fichier A. Chaque fichier commence au début d’un nouveau bloc, de sorte que si le fichier A avait
en fait une longueur de 3,5 blocs, on perdrait un peu d’espace à la fin du dernier bloc.
L’allocation contigüe de l’espace disque présente deux avantages importants.
Premièrement, elle est simple à mettre en place puisque garder une trace de l’emplacement des
blocs d’un fichier se résume à mémoriser deux nombres : l’adresse disque du premier bloc et le
nombre de blocs du fichier. Deuxièmement, les performances de lecture sont excellentes parce
que le fichier peut être lu dans sa totalité en une seule opération.
Malheureusement, l’allocation contigüe a aussi deux inconvénients majeures : avec le
temps le disque, le disque se fragmente. La figure 6.9 (b) donne l’état du disque lorsque les deux
fichiers D et F ont été effacés. En effet, quand un fichier est effacé, ses blocs sont libérés, laissant
une série de blocs libres sur le disque. Le disque consiste en une succession de fichiers et de
trous. Si le disque est plein, il devient nécessaire soit de le compacter- ce qui est cher parfois - ou
de réutiliser l’espace libre des trous. Et avant de créer un fichier, dans ce cas, on doit connaître sa
taille afin de pouvoir choisir le trou de bonne taille, à la bonne place.
La seconde méthode de stockage des fichiers consiste à conserver chacun d’eux comme
une liste chaînée de blocs de disque, comme illustré à la figure 6.10. Le premier mot de chaque
bloc sert de pointeur sur le bloc suivant. Le reste du bloc contient les données.
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 146
Contrairement à l’allocation contigüe, chaque bloc du disque peut être utilisé dans cette
méthode. Aucun espace n’est perdu dans une fragmentation du disque (excepté pour la
fragmentation interne dans le dernier bloc). De plus, pour l’entrée du répertoire, il suffit de
conserver l’adresse disque du premier bloc. Le reste peut être trouvé à partir de là. Avec la liste
chaînée, la lecture d’un fichier séquentielle est simple, mais l’accès aléatoire est extrêmement
lent. La quantité de données stockées dans un bloc n’est pas une puissance de deux, parce que le
pointeur prend quelques octets. Or de nombreux programmes lisent et écrivent dans des blocs
dont la taille est en puissance de deux. Lorsque les premiers octets de chaque bloc sont occupés
par le pointeur sur le prochain bloc, la lecture d’un bloc complet nécessite l’acquisition et la
concaténation de deux blocs du disque, d’où un temps supplémentaire pour la copie.
Fig. 6.10. Stockage d’un fichier à l’aide d’une liste chaînée de blocs de disque
Les deux inconvénients d’une liste d’allocation chaînée peuvent être éliminés en
optimisant l’accès des blocs suivants en gardant leurs pointeurs (références) dans une Table
d’allocation des Fichiers (FAT). Ce système a été proposé par MS-DOS. Chaque disque
dispose d'une table FAT et cette dernière possède autant d'entrées qu'il y a de blocs sur le disque.
Chaque entrée de la FAT contient le numéro du bloc suivant. Par exemple, dans la table suivante
commençant par le bloc 5, sera constitué des blocs : 5, 9, 12. Le numéro du bloc départ de
chaque fichier est gardé dans le répertoire, de cette façon, il sera toujours possible de localiser
tous les blocs d’un fichier, quelle que soit sa taille.
La i-node (index-node)
Chaque fichier est décrit par un i-nœud laquelle inclut les attributs et les adresses sur le
disque des blocs du fichier. Un simple exemple est montré à la figure 6.12. En fonction de l’i-
node, il est possible de retrouver tous les blocs du fichier. Le grand avantage de cette conception
par rapport aux fichiers chaînés utilisant une table en mémoire est que l’i-node a uniquement
besoin d’être en mémoire quand le fichier correspondant est ouvert.
Attributs du fichier
Adresse disque du bloc 0
Adresse disque du bloc 1
Adresse disque du bloc 2
Adresse disque du bloc 3
Adresse disque du bloc 4
Adresse disque du bloc 5
Adresse disque du bloc 6
Adresse disque du bloc 7 Adresse d’un bloc de
Adresse d’un bloc de
pointeurs pointeurs
Pour lire un fichier, il faut qu’il soit ouvert. Quand un fichier est ouvert, le système
d’exploitation se sert du chemin d’accès précisé par l’utilisateur afin de localiser l’entrée du
répertoire. L’entrée du répertoire fournit les informations nécessaires pour trouver les blocs du
disque. Suivant les systèmes, ces informations peuvent être l’adresse disque du fichier entier
(allocation contigüe), le numéro du premier bloc (cas de la liste chaînée) ou le numéro de l’i-
node. Dans tous les cas, la fonction principale du répertoire est de faire correspondre le nom
ASCII du fichier à une information nécessaire pour localiser les données.
Lorsque plusieurs utilisateurs travaillent ensemble sur un même projet, ils ont
fréquemment besoin de partager des fichiers. Ainsi, il est souvent souhaitable qu’un fichier
partagé apparaisse simultanément dans différents répertoires qui appartiennent à différents
utilisateurs. La figure 6.13 reprend le système de fichiers de la figure 6.9, mais cette fois, un des
fichiers de l’utilisateur C est présent dans un des répertoires de l’utilisateur B. La connexion entre
le répertoire de B et le fichier partagé est appelé lien Le système de fichiers est maintenant
l’équivalent d’un graphe orient acyclique ou DAG (Directed Acyclic Graph), plutôt qu’un arbre.
Répertoire racine
A B C
A B B C C
B C C
? C C C
Comme les fichiers sont généralement stockés sur disque, la gestion de l’espace disque est
primordiale pour les concepteurs de systèmes d’exploitation. Deux stratégies principales sont
envisageables pour stocker un fichier de n octets : l’allocation de n octets consécutifs ou la
division en un certain nombre de blocs qui peuvent être contigus ou pas.
Une fois que l’on a décidé de stocker les fichiers avec des blocs de taille fixe, la question
de la taille des blocs se pose. Suivant l’organisation du disque, on peut se servir du secteur, de la
piste ou du cylindre comme unité d’allocation.
Quand on dispose d’une unité d’allocation de grande taille, comme le cylindre, chaque
fichier, même de 1 octet, occupe un cylindre entier. Des études ont montré que la taille moyenne
des fichiers UNIX est de 1 Ko. En allouant un cylindre de 32 Ko à un fichier de 1 Ko, on gaspille
31 Ko sur 32, soit 97% de l’espace disque.
D’un autre côté, avec une unité d’allocation de petite taille, chaque fichier est constitué de
nombreux blocs. Pour lire chaque bloc, il faut donc un déplacement et un délai de rotation. De ce
fait, la lecture d’un fichier composé de nombreux blocs sera lente.
Sur certains systèmes d’exploitation, la taille a été définie il y a longtemps, quand les
paramètres des disques et les tailles de fichiers étaient différents. Pour UNIX, une taille de 1 Ko
est usuelle. Pour MS-DOS, la taille d’un bloc peut être toute valeur multiple de puissance de 2
comprise entre 512 octets et 32 Ko, mais elle est déterminée par la taille du disque.
Une fois que la taille de bloc est choisie, l’étape suivante consiste à mémoriser l’espace
libre. Les deux méthodes les plus employées sont illustrées à la figure 6.14. La première utilise
une liste chaînée de blocs contenant chacun des numéros de blocs libres. Avec des blocs de 1 Ko
et des numéros de blocs de 32 bits, chaque bloc de la liste inclut les numéros de 255 blocs libres
(un emplacement sur les 256 est nécessaire pour le pointeur sur le prochain bloc).
L’autre technique de gestion de l’espace libre fait appel à la table de bits. Un disque de n
blocs a besoin d’une table de n bits. Les blocs libres sont représentés par des 1 dans la table et les
blocs alloués par des 0 (ou vice- versa).
Blocs libres : 16, 17 et 18
42 230 86 1001101101101100
136 162 234 0110110110110010
210 612 897 1010110110110110
262 342 422 1000111011011001
310 180 142 0111011101110111
516 482 141 1101111111101110
Pour éviter que les utilisateurs n’occupent trop d’espace disque, les systèmes
d’exploitation multiutilisateurs fournissent souvent un moyen qui permet d’attribuer des quotas
d’espace disque. L’idée est que l’administrateur système attribue à chaque utilisateur une capacité
maximale de fichiers et de blocs, et le système d’exploitation vérifie que les utilisateurs ne
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 150
La destruction d’un système de fichiers est souvent plus grave que celle d’un ordinateur.
Si un système de fichiers est irrévocablement perdu, à cause d’une panne matérielle, d’une erreur
logicielle ou de rayures sur des disquettes, la restauration de toutes les informations sera difficile.
Si un système de fichiers ne peut offrir toutes les protections contre une défaillance matérielle de
l’ordinateur ou d’un support, il peut en tout cas aider à protéger les informations. Il existe
plusieurs solutions pour la sauvegarde du système de fichiers. On doit procéder régulièrement à
des sauvegardes, par exemple, sur des bandes.
Les sauvegardes sur bande servent généralement à régler l’un des deux problèmes potentiels
suivants :
1. Réparer un désastre : après, par exemple, une panne de disque ou un autre dommage
survenu à l’ordinateur (incendie, inondation, etc.).
2. Réparer une erreur : fichiers effacés accidentellement. On peut alors restaurer les fichiers
effacés.
Une sauvegarde sur bande prend un certain temps et occupe beaucoup d'espace. Deux
aspects sont à prendre en considération dans ce type de sauvegarde.
Premièrement, on peut se poser la question suivante : un système de fichiers doit-il être
sauvegardé dans son intégralité ou en partie? Dans de nombreuses installations, les programmes
exécutables (binaires) sont conservés dans une petites partie de l'arborescence du système de
fichiers. Il n'est pas donc nécessaire de sauvegarder ces fichiers s'ils peuvent être réinstallés à
partir des CD-ROM originaux. Comme la plupart des systèmes ont aussi un répertoire pour les
fichiers temporaires, il n'y a pas non plus de raison de les sauvegarder. Il est donc plus approprié
de sauvegarder seulement des répertoires particuliers et tout ce qu'ils contiennent, plutôt que le
système de fichiers dans son ensemble.
Deuxièmement, il est inutile de sauvegarder des fichiers qui n'ont pas changé depuis la
dernière sauvegarde, d'où l'idée de réaliser des copies incrémentales. Cela consiste à faire une
copie complète périodiquement, hebdomadairement ou mensuelle, et de faire une copie
journalière des fichiers qui ont été modifiés depuis la dernière sauvegarde totale.
Troisièmement, comme on copie généralement de grandes quantités de données, il est
souhaitable de compresser les données avant de les écrire sur une bande.
Quatrièmement, il est difficile de faire une sauvegarde d'un système de fichiers en
activité. Cependant, il existe des algorithmes pour faire des copies instantanés du système de
fichiers.
Cinquièmement, les bandes de sauvegardes doivent être conservées hors du site.
Pour dupliquer un disque sur une bande, on peut employer deux méthodes: la méthode de
la copie physique du fichier et la méthode de copie logique.
Une copie physique démarre au bloc 0 du disque, écrit dans l'ordre tous les blocs du
disque sur la bande, et s'arrête lorsque le dernier bloc a été copié.
Les principaux avantages de la copie physique sont sa simplicité et sa rapidité (elle peut
s'exécuter à la vitesse du disque).
Une copie logique débute par un ou plusieurs répertoires spécifiés et copie récursivement
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 151
tous les fichiers et répertoires trouvés et qui ont été modifiés depuis une certaine date. Dans une
copie logique, la bande de copie possède une série de répertoires et de fichiers soigneusement
identifiés, ce qui fait qu'il est facile de restaurer à la demande un fichier ou un répertoire
spécifique. La copie logique est la méthode la plus suivie.
Une autre partie où la fiabilité est un problème est la cohérence du système de fichiers. De
nombreux systèmes de fichiers lisent des blocs, les modifient et les réécrivent ensuite. Si le
système tombe en panne avant la réécriture des blocs, le système de fichiers peut se retrouver
dans un état incohérent.
La plupart des ordinateurs ont un programme utilitaire qui vérifie la cohérence des
système de fichiers. Par exemple, UNIX utilise fsck et Windows scandisk. Cet utilitaire peut
être exécuté à chaque fois que le système démarre, et spécialement après une panne.
Les accès disque sont beaucoup plus lents que les accès mémoire. Ainsi, la lecture d'un
mot mémoire nécessite au plus une dizaine de nanosecondes, alors que la lecture sur un disque
peut fonctionner à 10 Mo par seconde, ce qui est quarante fois plus lent pour un mot de 32 bits;
en outre, il faut ajouter entre 5 et 10 ms pour la recherche de la piste et le positionnement du bon
secteur sous la tête de lecture. Si un seul mot est nécessaire, l'accès mémoire est environ un
million de fois plus rapide que l'accès disque. En raison de cette différence de temps d'accès, de
nombreux systèmes de fichiers ont été conçus pour augmenter les performances des accès disque
à l'aide de différentes optimisations. Nous en verrons trois d'entre elles dans cette section.
Mémoire cache
La technique la plus répandue pour réduire les accès disque consiste à utiliser une
mémoire cache (block cache ou buffer cache). Il s'agit d'une succession de blocs qui
appartiennent logiquement au disque mais sont conservés en mémoire pour améliorer les
performances.
De nombreux algorithmes peuvent servir à gérer une mémoire cache, mais le plus courant
est de vérifier, à chaque accès, si le bloc demandé est présent dans cette mémoire cache. Le cas
échéant, la demande est satisfaite sans faire d'accès disque. Dans le cas contraire, le bloc est
d'abord chargé dans la mémoire cache puis copié où cela est nécessaire.
Pour augmenter les performances d'un système de fichier, une autre technique est
d'essayer de disposer de blocs de mémoire cache avant d'en avoir besoin. En particulier, de
nombreux fichiers sont lus de manière séquentielle. Quand le système de fichiers reçoit une
requête qui lui demande de produire le bloc k dans un fichier, il le fait ; mais quand il a terminé,
il effectue une discrète recherche dans la mémoire cache pour voir si le bloc k+1 est déjà présent.
Si ce n'est pas le cas, il fait une lecture de ce bloc, en espérant qu'il se trouvera déjà dans la
mémoire cache lorsqu'on en aura besoin.
Naturellement, cette stratégie de lecture anticipée fonctionne seulement pour des fichiers
Moanda Ndeko - Kuti Lusala : Systèmes d’Exploitation des Ordinateurs : Notes de cours 152
La mémoire cache et la lecture anticipée de blocs ne constituent pas les seuls moyens
d'améliorer les performances du système de fichiers. Une autre technique consiste à réduire le
déplacement du bras en rapprochant les blocs susceptibles d'être adressés en séquence et en les
plaçant de préférence sur le même cylindre. Quand on écrit un fichier, le système de fichiers doit
allouer les blocs un par un au moment où on en a besoin. Si les blocs libres sont mémorisés dans
une table de bits, et que cette table se trouve entièrement en mémoire principale, il est facile de
choisir un bloc libre aussi proche que possible du bloc précédent. Avec une liste de blocs libres
partiellement sur le disque, il est plus difficile d'allouer des blocs qui soient proches les uns des
autres.
Cependant, même avec une liste de blocs libres, il est possible de faire des groupes de
blocs consécutifs. L'astuce consiste à mémoriser l'espace disque occupé en groupes de blocs
consécutifs plutôt qu'en blocs. Si un secteur est constitué de 512 octets, le système pourra
recourir à des blocs de 1 Ko (2 secteurs) mais allouera des unités de stockage de 2 blocs (soit 4
secteurs). Ce n'est pas la même chose que d'avoir des blocs de disque de 2 Ko, puisque la
mémoire cache utilisera encore des blocs de 1 Ko et que les transferts disque seront également de
1 Ko. Par contre, la lecture séquentielle d'un fichier sur un système qui n'a pas de tâche en cours
réduit le nombre de recherches d'un facteur deux, ce qui améliore considérablement les
performances.
6.3.9. Les systèmes des fichiers LFS (Log-structured File System, système de fichiers structuré
en lot d'enregistrements)
a) Introduction au multimédia
Sur un ordinateur, le multimédia consiste souvent à lire un film préenregistré sur un DVD.
Il s’agit de la gestion, au moyen de l’informatique, sur un même support des textes, des sons, des
images fixes et animés et des graphiques.
Le multimédia sert également à télécharger des clips vidéo sur l'internet. Les pages Web
contiennent des éléments sur lesquels, on peut cliquer pour télécharger de petits films.
Même la création de vidéos suppose une prise en charge du multimédia. Le multimédia prend
également de l'importance dans le domaine des jeux informatiques.
La multimédia présente les deux caractéristiques importantes suivantes :
- Le multimédia utilise des débits de données très élevées et requiert des capacités de
stockage importante ;
- Le multimédia doit être lu en temps réel.
L'œil et l'oreille sont capables de traiter de formidables quantités d'information à la seconde.
Dans la plupart des systèmes, un fichier texte ordinaire est composé d'une séquence
linéaire d'octets exempte de toute structure connue ou recherchée par le système d'exploitation.
Avec le multimédia, la situation est encore plus compliquée. Pour commencer, la vidéo et le son
sont deux éléments totalement différents. Ils sont capturés par des périphériques différents, leur
structure interne est différente (la vidéo possède 25-30 trames/s contre 44 1000 échantillons/s
pour le son) et ils sont lus par des périphériques différents (un écran et des haut-parleurs).
De plus, de nombreux films proposent des sous-titres. Par conséquent, un film numérique
contient en réalité plusieurs fichiers : un fichier vidéo, plusieurs fichiers son et plusieurs fichiers
texte avec des sous-titre en plusieurs langues.
Ainsi, le système de fichiers doit, pour chaque fichier, conserver la trace de nombreux
"sous-fichiers". Un schéma possible consiste à gérer chaque sous-fichier comme un fichier
traditionnel (en utilisant par exemple un i-node pour conserver une trace de ses blocs) et à avoir
une nouvelle structure de données qui répertorie tous les sous-fichiers par fichier multimédia. Au
moment de regarder le film, cette organisation doit permettre à chaque téléspectateur de choisir
dynamiquement les pistes son et les sous-titres. Il est aussi indispensable et nécessaire de
synchroniser les sous-fichiers pour que, à la lecture de la piste son sélectionnée, ils soient
synchrones avec la vidéo.
La compression vidéo
Comme le multimédia prend trop de place, on peut pas le manipuler sans le compresser.
Tous les systèmes de compression nécessitent deux algorithmes : un pour compresser les données
à la source et un autre pour le décompresser à l'arrivée. Dans ce contexte, on fait référence
respectivement aux algorithmes d'encodage et de décodage.
Le processus d'encodage/décodage n'est pas nécessairement réversible. Lors du décodage,
on accepte quelques pertes de données, c'est-à-dire, le fichier décodée ne correspond pas
exactement au fichier d'entrée d'origine.
A titre d'exemple, nous allons présenter les systèmes de fichiers des CD-ROM. Ces
systèmes sont simples et sont conçus pour des supports en écriture seule.
Le plus répandu des systèmes de fichiers sur CD-ROM a été adopté comme standard
international en 1988, sous le nom de ISO 9660. Tous les CD-ROM actuellement sur le marché
sont théoriquement compatibles avec ce standard. Un des objectifs de ce standard était de faire en
sorte que chaque CD-ROM soit lisible sur chaque ordinateur, indépendamment de l'ordre des
octets et du système d'exploitation.
Les CD-ROM n'ont pas de cylindres concentriques tels qu'on les trouve sur les disques
magnétiques. Il dispose d'une simple spirale continue contenant les octets rangés dans une
séquence linéaire. Les octets placés le long de la spirale sont divisés en blocs logiques (secteurs)
de 2 352 octets. Certains d'entre eux sont destinés aux préambules, aux corrections d'erreurs et
autres tâches de gestion. La partie utile de chaque bloc logique est de 2 048 octets.
1 1 8 8 7 1 2 4 1 4-15
Localisation Taille du Date et Numéro L Nom du
du fichier fichier heure du CD fichier