Chapitre suivantIndex des CoursChapitre précedentChapitre 4

Principes de la gestion de l'information

 

IV-1.1. Objets et liaisons

Tout processus, en particulier ceux qui constituent le système d'exploitation, décrivent un ensemble d'objets et leurs relations ainsi que les opérations qui y sont associées. Chaque objet est défini par une représentation concrète qui est constituée d'un ensemble d'informations située dans la mémoire de l'ordinateur et sur les périphériques (disques, bandes magnétiques...). Le processeur accède aux objets, c'est à dire à leur représentation, par leur localisation en mémoire centrale ou périphérique grâce à leur adresse de rangement. On peut aussi dire qu'un processus manipule des entités structurées (variables, tableaux en mémoire, fichiers, autres processus...). Il connaît leurs adresses et sait comment ils sont structurés en mémoire ou sur un disque.

Pour pouvoir manipuler ces objets il faut imaginer des mécanismes auxquels les processus manipulateurs ont accès pour établir une correspondance entre les identificateurs des objets (leur nom) et l'adresse en mémoire de leur représentation. Cette correspondance est désignée sous le terme général de liaison. Le procédé qui met en relation l'objet et sa représentation s'appelle la chaîne d'accès.

Nous nous intéresserons dans ce chapitre à des objets extérieurs aux processus qui se déroulent. Ces objets sont créés, modifiés et conservés indépendamment d'eux, même si ce sont des processus particuliers qui les génèrent et les détruisent. Ils peuvent être créés et détruits dynamiquement mais leur durée de vie peut être indépendante de celle des processus qui les mettent en œuvre. Les fichiers sont un exemple de ce type d'objets mais les notions que nous allons expliquer sont bien plus générales. L'étude des fichiers et de leur manipulation n'est donc qu'une illustration d'une notion beaucoup plus large.

On peut résumer les différents modèles de chaînes d'accès entre un objet et sa représentation aux deux schémas suivants.

Soit X l'identificateur de l'objet, R sa représentation et a son adresse. En absence de liaison il n'y a aucune relation entre l'objet R et son identificateur X (fig. 4.1).

figure 4.1 : Objet non existant

En pratique l'objet n'existe pas puisqu'il n'y a aucun moyen d'accéder à sa représentation à partir de son identificateur. Pour faire disparaître un fichier il suffit donc de détruire la liaison entre son identificateur (son nom) et sa représentation (les informations qu'il contient). C'est ainsi qu'on procède, dans tous les systèmes d'exploitation : on se limite à couper le lien et l'objet, non accessible, devient inexistant. Les utilitaires de récupération de fichiers ne font que tenter de rétablir, avec plus ou moins de succès, ces liaisons car l'information continue à exister sur le disque, tant que l'espace correspondant n'est pas réutilisé. Ces utilitaires ne peuvent pas être efficaces avec des systèmes multiutilisateurs comme Unix : les nombreux processus qui coexistent dans la mémoire récupèrent rapidement une partie de l'espace rendu disponible donc effacent définitivement une part de l'information. Supprimer un lien pour supprimer un fichier est une méthode rapide mais ne permet pas d'assurer une très grande confidentialité.  Ceci explique comment on peut souvent, sinon retrouver une information sur un disque, du moins en trouver des traces. L'utilisateur moyen croit assurer la confidentialité de certaines informations en les effaçant mais ceci n'est pas suffisant vis-à-vis d'un spécialiste. Nombreux sont les dépositaires d'informations illégales qui ont la mauvaise surprise de se voir confondus. Ceci est arrivé à plus d'un utilisateur de copie pirate de logiciel qui a cru se prémunir contre une enquête en effaçant le logiciel douteux!

Dans les systèmes sécurisés on efface un fichier en réinitialisant l'espace qu'il occupait. Cette méthode est efficace mais beaucoup plus lente et est donc réservée à des situations particulières.

Imaginons une table (fig. 4.2) qui contienne la liste de tous les identificateurs des objets. Un même objet peut apparaître, avec différents identificateurs, plusieurs fois dans la table: dans les systèmes Unix un fichier peut exister dans différents répertoires mais sa représentation (les données) est unique.

figure 4.2 : Liaison par substitution

Comment établir la liaison indispensable à l'existence d'un objet?

On peut la réaliser par substitution. On remplace, avant d'exécuter la procédure qui manipule l'objet, tous les identificateurs {a} de l'objet X par son adresse a (fig. 4.2). Cette méthode est efficace car l'objet R est accédé rapidement mais elle a le défaut de ne pas être modifiable sans recommencer le processus de substitution. Lorsqu'on déplace l'objet R toute la table doit être mise à jour. La liaison ne peut pas être modifiée dynamiquement puisque le processus de substitution se déroule avant usage de l'objet.

L'autre méthode est de procéder par chaînage. Toutes les occurrences de l'identificateur X de l'objet pointent sur un objet intermédiaire r dans lequel on inscrit l'adresse a de sa représentation R (fig. 4.3). Lorsqu'on déplace l'objet seul a doit être mis à jour. Cette façon de faire est donc beaucoup plus souple mais elle nécessite deux lectures au lieu d'une pour établir le lien.

figure 4.3 : Liaison par chaînage

On peut même imaginer un chaînage avec plusieurs objets relais r en cascade. Ce chemin d'accès est aisément modifiable car il suffit de changer l'adresse a dans l'objet r pour établir une liaison avec un nouvel objet R': R' est alors accédé, de l'extérieur, avec l'identificateur X. Le processus qui manipule les représentations R et R' peut gérer dynamiquement la liaison au cours de son activité puisqu'il suffit de modifier r sans toucher à la table des identificateurs X. Par contre cette méthode de liaison est beaucoup moins rapide que la précédente car il faut parcourir toute la chaîne d'accès: la table des identificateurs ne mène à la représentation qu'au terme de plusieurs indirections. C'est ainsi que procède Unix comme nous le verrons au paragraphe 6.

IV-1.2. Protections

Lorsqu'un système d'exploitation permet à plusieurs processus de se dérouler simultanément, il est indispensable de savoir protéger les objets : tous les processus n'ont pas le droit d'accéder aux mêmes objets. La notion de protection englobe l'ensemble des méthodes qui définissent les règles d'utilisation de ces objets et qui garantissent qu'elles sont respectées. Cette notion est quasiment absente des systèmes pour ordinateur personnel comme Windows et MacOs.

On peut interdire à un processus tout accès à un objet, en supprimant, uniquement pour lui, toute possibilité de liaison. L'objet devient donc inexistant et invisible pour ce processus. On peut imaginer des procédures d'accès qui vérifient, avant l'exécution du processus, l'usage que l'on va faire de l'objet. On peut donc contrôler si ces règles sont en accord avec les opérations permises. L'utilisation d'une procédure d'accès simplifie la mise en œuvre des contrôles puisqu'ils sont tous fait avant lancement du processus. Malheureusement cela n'est pas toujours possible car cette méthode interdit tout changement des chemins d'accès au cours de la vie du processus : concrètement cela signifie qu'il devient impossible d'ouvrir un fichier dynamiquement à l'intérieur d'un programme. Les instructions correspondantes sont remplacées par des ordres extérieurs à celui-ci qui doivent être exécutés avant démarrage du processus. Il devient impossible de demander à l'utilisateur de préciser le nom des fichiers qu'il veut manipuler au cours de l'exécution du processus puisque les assignations des liaisons ont dues être établies préalablement. C'est pourquoi le contrôle par procédure d'accès est utilisé de façon limitée dans les logiciels modernes.

Les contrôles doivent permettre de refuser à un processus utilisateur, sans privilège particulier, d'effectuer certaines opérations : par exemple un processus pourra consulter le contenu d'un fichier sans jamais pouvoir le modifier. Dans le cas le plus extrême il n'aura aucun indice lui permettant de soupçonner son existence et pour ce processus le fichier n'existe pas. Les contrôles sont complexes et il est difficile de vérifier leur qualité. L'un des grands jeux des pirates informatiques est de trouver les faiblesses des protections installées sur les gros systèmes et de passer au travers. Ceci est une activité sévèrement punie par la loi.

Un système d'exploitation met en relation des processus et des objets. Les liaisons et les protections évoluent de façon dynamique. Ces possibilités d'évolution identifient des droits. Plusieurs processus peuvent posséder des droits identiques sur une sélection d'objets, ce qui permet de définir des classes de droit ou domaines Di. On peut dessiner des matrices de droits d'accès (fig. 4.4) où l'on représente suivant une ligne les droits des processus appartenant à un même domaine, chaque colonne correspondant à un objet. Comme les domaines sont eux-mêmes des objets ils apparaissent dans les lignes et dans les colonnes. La liste des droits possibles dépend de la nature de l'objet. Par exemple on peut définir pour différents types d'objets:

q  objet fichier: lire, écrire, exécuter. Ce dernier droit s'applique à un programme ou à un script (un script est un fichier de commandes en Unix, appelé aussi fichier batch en DOS).

q  objet périphérique: demander, réquisitionner, allouer, libérer un contrôleur de disque par exemple.

q  objet domaine: changer de domaine, c'est à dire acquérir les droits d'un autre domaine, ou modifier les droits à l'intérieur d'un domaine...

La figure 4.4 en présente un exemple.

 

fichier 1

fichier 2

disque

D1

D2

D3

D1

<r,w,x>

<r,w>

<alloc,droits>

<> 

<chgt requis>

<appel>

D2

<r>

<r,x>

<demande,libère>

<appel>

<> 

<> 

D3

<> 

<> 

<> 

<> 

<> 

<> 

figure 4.4 - Exemple de matrice de droits d'accès

<> Signifie que l'objet considéré ne figure pas dans le contexte du domaine considéré : fichier 1 est ainsi invisible dans le contexte de D3.

Par définition un domaine ne peut se modifier lui-même : D1 peut appeler D3, c'est à dire se placer dans le contexte de D3 (appel), D1 peut changer les droits de D2 (changement requis) mais pas les siens propres. Cette action n'est pas réciproque : D1 peut se placer dans le contexte de D3 mais ne pourra alors plus revenir dans son contexte initial. <r> signifie droit de lecture, <w> d'écriture, <x> d'exécuter suivant la terminologie Unix. Une colonne représente une liste d'accès sur un objet, une ligne une liste de capacité.

Une grosse difficulté, lorsqu'on veut sécuriser un système d'exploitation, est de s'assurer qu'un processus ne puisse acquérir des droits indus. Ainsi un processus P appartenant à D2 peut se placer dans le contexte D1. Il peut alors modifier fichier 1, ce qui lui était interdit auparavant. On peut imaginer des cas où, à partir d'un premier domaine de droits, en passant successivement par différents domaines Dj, on peut se retrouver dans la situation où le processus P acquerrait des privilèges indus. Il est très difficile de vérifier tous les moyens qu'un processus possède pour accéder aux droits d'un domaine.

Les listes de droits possibles ne sont pas les mêmes suivant les systèmes d'exploitation. Unix distingue fondamentalement trois possibilités en ce qui concerne les fichiers :

  • r ou droit de lecture
  • w ou droit d'écriture, de modifier et même d'effacer complètement le fichier
  • x ou droit d'exécution. Ce droit ne prend de sens que pour un programme exécutable ou un script. D'autres systèmes ne différentient pas x et w.

Ces droits peuvent être attribués séparément au propriétaire du fichier (ou de l'objet), à un groupe particulier d'utilisateurs ou à toute personne. Ils sont inscrits dans des listes de contrôle d'accès ou ACL (Access Control List). Les systèmes Unix ne distinguent que le propriétaire, le groupe de l’utilisateur et les autres personnes. D'autres systèmes permettent une discrimination plus fine en enregistrant des noms de personnes et de groupes suivis des droits particuliers sur chaque objet.

La notion de droit et le groupe auquel il appartient, sont identifiés. Elle nécessite donc l'existence d'une procédure d'identification qui permette de s'assurer sérieusement de l'identité de la personne utilisatrice des objets. En début de session il faut fournir un identifiant puis un mot de passe, jamais affiché sur l'écran, personnel et confidentiel. Dans les systèmes les plus stricts il est obligatoire de le changer régulièrement. Parfois un second mot de passe est indispensable pour accéder à certaines fonctionnalités. Enfin toute demande de connexion est enregistrée et les responsables de l'exploitation font un audit régulier de ce fichier afin de détecter tout usage inhabituel. Les objets indispensables au bon fonctionnement du système d'exploitation sont particulièrement protégés et sont souvent totalement invisibles pour les utilisateurs ordinaires. Ces mécanismes manquent dans DOS et MacOs, sont facilement contournables sous Windows 9x puisque les fichiers ne sont pas protégés et expliquent pourquoi ces systèmes ne peuvent être considérés comme sûrs, même après ajout de certains utilitaires qui tentent de pallier à cette faiblesse. Cette déficience devient dangereuse lorsqu'on veut partager des informations à travers un réseau. Le minimum de sécurité apporté par la nécessité de pouvoir accéder au micro-ordinateur qui possède l'information disparaît. C'est pourquoi Novell et d'autres fournisseurs ont ajouté des mécanismes d'identification à leurs logiciels de réseaux. Windows NT, Unix sont sécurisés.

Une protection totale est difficile à assurer. On peut oublier de protéger correctement certains objets ou même être obligé de les laisser partiellement visibles. Par exemple, dans Unix, le fichier des mots de passe, /etc/passwd, peut être lu par n'importe qui, du moins dans les systèmes conventionnels. Ils sont encryptés mais l'algorithme de cryptage est dans le domaine public. Il n'est pas réversible mais, muni d'un dictionnaire, on peut tenter de retrouver la chaîne de caractères encryptée qui apparaît dans le fichier passwd. Si on code son prénom en guise de mot de passe il ne faudra pas plus de quelques minutes à un pirate disposant des outils nécessaires pour le retrouver! Il ne faut pas néanmoins exagérer: une protection efficace est possible et il ne faut imaginer que les films de fiction deviennent aussi simplement réalité.

Il existe des situations moins évidentes: il peut arriver que l'on désire protéger un domaine D3 contre un domaine D1 mais, si D1 a des droits sur D2 et D2 sur D3 on ne peut pas se prémunir aisément contre des transitions interdites. On résout cette difficulté par des méthodes hiérarchiques: D1 a des droits sur D2 mais D1 est protégé contre D2. Ceci rend malheureusement difficile la coopération entre deux domaines distincts. On peut également imaginer des systèmes méfiants qui spécifient clairement les droits des autres domaines sur toute partie de leur information. Cependant lorsque la gestion des droits est dynamique des autorisations indues peuvent se propager.

IV-2. Désignation des fichiers

IV-2.1. Organisation d'un système de fichiers

Le fichier est l'unité de conservation de l'information. C'est un objet complexe qui n'est pas constitué uniquement des informations visibles par l'utilisateur.  Son descripteur contient les informations nécessaires à sa localisation physique sur le disque et à son usage. Le nom de ce descripteur est interne, c'est à dire que l'utilisateur ne le connaît pas. Il n'accède au fichier que par son nom externe. La liaison entre ces deux noms est établie au moyen du catalogue.

Un fichier peut éventuellement être défini par un nom local à la procédure en cours d'utilisation. C'est ce qui est fait lors de l'appel à la primitive d'ouverture dans un langage de programmation. Cette méthode est plus efficace que l'usage du nom externe car son interprétation est plus rapide et peut apporter une plus grande souplesse dans la gestion du fichier.

Ces différentes possibilités sont résumées dans la figure 4.5.

Figure 4.5 - Les différents noms d'un fichier

On rencontre le plus souvent trois modèles de catalogue:

  • organisation en un seul niveau (fig. 4.6)
  • On associe directement le descripteur aux noms externes. Il n'y a aucun classement possible aussi ce système n'existe pratiquement plus.

  • organisation à deux niveaux (fig. 4.7)
  • Il existe des catalogues secondaires par utilisateur. Certains systèmes comme ceux propres à IBM emploient des structures à un niveau qui ressemblent aux structures à deux niveaux. Les règles d'écriture dans le catalogue imposent un nom à plusieurs champs séparés par des points, le premier étant l'identificatif de l'utilisateur. Les mécanismes de sécurité interdisent à une personne de retrouver les éléments du catalogue qui ne correspondent pas à ses propres fichiers, sauf autorisation explicite.
  • organisation arborescente (fig. 4.8) :

figure 4.8 : catalogue arborescent

C'est la plus connue de nos jours puisqu'elle est utilisée par Unix et les systèmes qui s'en sont inspirés (DOS, OS/2...).

On peut créer un système à autant de niveaux de répertoires que désiré (il existe cependant des limitations pratiques suivant les systèmes). Un répertoire ou directory possède un père : il s'agit du répertoire de niveau plus élevé dans la hiérarchie et un ou plusieurs fils, fichiers ou répertoires plus bas dans l'arborescence. Le répertoire de niveau le plus élevé est appelé racine. Il ne possède pas de père. Nous utiliserons ici Unix comme exemple car on y trouve un sur-ensemble des possibilités de Windows et de MacOs.

/ désigne le répertoire racine. Le nom d'un répertoire est construit en donnant sa filiation : /users/yves/appli1 par exemple (fig. 4.8). Par convention, désigne le répertoire courant, appli1 dans cet exemple. Le répertoire père, Yves dans ce même exemple.

Unix possède une possibilité intéressante de désignation d'un objet à partir d'un autre objet. On peut, par exemple, établir un lien symbolique entre les fichiers appli et toto. appli n'est pas un véritable objet mais un simple pointeur dans le répertoire Marianne qui désigne l'objet toto qui se trouve sous prog. Le système établit un lien qui permet un accès facile, à partir des deux répertoires, du même objet.

On peut construire des liens entre fichiers comme entre répertoires.

Dans la plupart des systèmes d'exploitation on peut introduire un suffixe séparé par un point, dans les noms de fichiers. Leur signification varie avec le système: .com ou .exe désigne un module exécutable pour DOS et Windows, .f pour une source fortran, .c pour une source en langage C, .o est un module compilé pour Unix. Le choix des suffixes est le plus souvent dépendant de l'application ou du compilateur qui utilise le fichier.

Le nombre de caractères que l'on peut utiliser pour désigner un objet dépend du système d'exploitation. Windows est un exemple hybride curieux : DOS limite les noms à huit caractères + une extension de trois lettres. Comme Windows s'appuie sur DOS les noms plus longs sont rangés et désignés au moyen de fichiers annexes qui contiennent les caractères supplémentaires.

IV-2.2. Liaisons et entrées-sorties

Lorsqu'on écrit un programme il est intéressant de séparer la notion d'entrées-sorties de celle de fichier. Cela permet de modifier dynamiquement le mode de communication que l'on veut utiliser. Ainsi il devient possible de lire les données dans un fichier ou de les frapper directement au clavier, selon son choix, sans avoir à modifier le programme ni devoir le compiler à nouveau. Les systèmes d'exploitation, qui le permettent, possèdent une structure de communication plus générale appelée flot d'entrées-sorties. Lorsque le processus est exécutée, on construit d'abord cette structure puis on l'affecte à un fichier ou un périphérique dynamiquement au moment voulu. La figure 4.9 résume les trois états possibles de cette structure.

figure 4.9 - Les différents états d'un flot d'entrées-sorties

Avant association (fig. 4.9a) la structure est définie mais aucun lien n'existe. Les communications sont impossibles car aucun chemin d'accès n'est établi entre cette structure et un objet. Par la suite, elle va servir à définir des pointeurs qui associent le flot d'entrées-sorties à un fichier (fig. 4.9b) ou directement à un périphérique (fig. 4.9b) (écran, clavier...) ainsi que les procédures nécessaires à leur réalisation. Les schémas b et c se ressemblent. Ils différent par la valeur des pointeurs qui désignent des primitives et des tampons différents. Le fait que ces éléments ne soient pas directement contenus dans le programme facilite la gestion dynamique des communications. Le flot possède toutes les caractéristiques d'un organe d'entrées-sorties mais celles-ci ne sont que partiellement déterminées avant affectation. Pour Unix les noms de flot sont des entiers. 0 désigne le flot d'entrée, 1 le flot de sortie des résultats, 2 le flot de sortie des messages d'erreurs. On les connaît aussi sous les noms standard in ou stdin, standard out ou stdout et standard err ou stderr. On peut associer le flot de sortie d'une première procédure avec le flot d'entrée d'une deuxième au moyen d'un pipe. La liaison utilise un buffer interne. On retrouve ce procédé, en plus rudimentaire sous DOS. Par exemple pour lire à l'entrée le défilement à chaque fin de page on pourra utiliser sous Unix: ls | more, sous DOS dir | more. Le symbole "|" indique le routage à travers le pipe.

situter les flots d'entrée et de sortie, qui sont normalement envoyés du clavier et vers l'écran, au moment où le programme est chargé en mémoire pour être exécuté. Appelons le mon_prog. La syntaxe sera:

mon_prog < fic1 > fic2

Le programme lira ses données dans le fichier fic1, écrira les résultats dans le fichier fic2 au lieu d'utiliser le clavier et l'écran. Seules les erreurs éventuelles continueront à être affichées à l'écran car le flot correspondant à stdout n'est pas dérouté.

IV-3. Organisation physique des fichiers

IV-3.1. Organisations physique et logique

L'organisation physique des fichiers décrit la façon dont les octets sont rangés sur le support magnétique. Ceci dépend du système d'exploitation et explique pourquoi une disquette créée sous DOS n'est pas lisible sous MacOs : l'organisation des fichiers est différente et, en dehors de leur contenu, les octets n'ont pas la même signification. De même un système de fichiers Unix BSD est illisible sous Unix System V. Mieux encore il arrive qu'un changement de version du système d'exploitation nécessite une modification de l'organisation physique et qu'un disque devienne illisible lorsqu'on le connecte à une machine qui utilise une version plus ancienne!

Il faut distinguer l'organisation physique et l'organisation logique : le processus utilisateur du fichier le voit comme un flot d'octets rangés à des adresses successives à partir du premier. Dans la réalité ces informations sont le plus souvent dispersées sur la surface du support et c'est le système qui établit la relation entre ces deux organisations. Un fichier est donc un ensemble d'informations dont la structure interne n'est pas directement visible. Ce point sera évoqué au chapitre VI lorsque nous présenterons les principaux modèles de structuration de l'information contenue dans ce flot.

Nous nous intéresserons dans ce chapitre à la structure physique de l'information. Cela signifie que nous nous préoccuperons de la façon dont un système d'exploitation organise l'information sur le support magnétique.

IV-3.2. Organisation physique sur un support magnétique

Le quantum lu ou écrit n'est pas l'octet mais le secteur. DOS utilise des secteurs de 256 octets, Unix de 512 à 4096 octets suivant les systèmes. La raison en est que la préparation d'un transfert, entre disque et mémoire, est onéreuse et demande plusieurs cycles de temps du processeur. Le choix de la taille du secteur résulte d'un compromis entre temps de transfert et de préparation. Plus le canal de transfert est efficace, plus grand est le secteur: ainsi sur Cray il est de 4096 octets car les dispositifs d'entrées-sorties sont très rapides.

Les disques modernes comportent au minimum deux faces. Ils peuvent être constitués de plusieurs plateaux tournant sur le même axe (fig. 4.10). Sur une face d'un plateau on peut accéder à toute l'information rangée sur une circonférence sans devoir déplacer la tête de lecture. Ce groupe s'appelle une piste. Elle est accédée plus rapidement que des secteurs dispersés au hasard puisqu'il suffit d'attendre une rotation (la vitesse est de l'ordre de plusieurs milliers de tours par minute) pour lire ou écrire son contenu. Les disquettes DOS de diamètre 3 1/2", formatées à 1,4 M octets comprennent ainsi 80 pistes par face, chacune contenant 18 secteurs. Il existe une tête de lecture par face. Ces têtes sont solidaires et toutes les pistes de même diamètre sont accessibles simultanément. C'est pourquoi il existe un troisième niveau d'organisation qui est le cylindre. Il est constitué de l'ensemble des pistes de même diamètre accessibles simultanément. Sur une disquette le cylindre est constitué de deux pistes. Dans les disques de très grande capacité une face sert souvent uniquement à l'asservissement du déplacement du bras qui porte les têtes.

figure 4.10 - Schéma d'un disque

Formater un disque revient à créer les secteurs sur le support magnétique vierge. On écrit puis on lit chaque secteur. S'il s'avère défectueux son adresse est inscrite dans un emplacement réservé. Si le nombre de secteurs défectueux dépasse la taille de cette table, le formatage échoue et le disque est déclaré inutilisable. Il ne reste plus qu'à le changer. Un disque neuf doit être livré avec une fiche indiquant la liste des zones qui ont été trouvées mauvaises à la vérification. Il est en effet impossible de garantir qu'il n'y a pas d'erreurs dans un support à très haute densité, aussi doit-on exiger ce contrôle du fabriquant. Lorsqu'on a besoin d'espace pour créer ou étendre un fichier, le système avant toute réservation, vérifie que les secteurs alloués ne sont pas inscrits dans la table. Si des messages d'erreur apparaissent lors d'opérations d'écriture certains systèmes sont capables d'ajouter immédiatement les adresses des secteurs erronés à la liste de ceux qui sont défectueux et réparent ainsi le disque. Des utilitaires de vérification peuvent également le faire mais l'information qui aurait été précédemment inscrite dans ces positions est perdue.

Notons que le formatage est la seule opération qui efface complètement le contenu d'un disque puisque, dans l'opération de vérification, chaque secteur est initialisé. Comme ceci est long, il faut compter plusieurs heures pour formater un disque de plusieurs G octets, certains utilitaires permettent un formatage rapide en supprimant l'opération d'écriture-lecture de vérification. Ceci est extrêmement dangereux car une information inscrite dans un secteur défectueux est illisible et peut conduire à la perte de l'ensemble du fichier.

Une bande magnétique, quelque soit son conditionnement, ne possède pas de structure. Les informations sont écrites par blocs. Leur longueur peut souvent être choisie afin d'obtenir le meilleur compromis entre les temps de préparation et de transfert de l'information. Les supports modernes ont des capacités qui dépassent plusieurs giga-octets mais le temps d'accès est très lent. Ceci fait que les bandes sont le plus souvent utilisées pour les sauvegardes et les archivages.

IV-3.3. Organisation séquentielle d'un support magnétique

C'est la seule organisation qui existe sur les bandes magnétiques (fig. 4.11). Les informations sont rangées les unes après les autres. La relation entre les adresses physique et logique est donc particulièrement simple. Un fichier est contenu dans des blocs contigus. En général on range au début, avant d'écrire le contenu, son nom, sa date de création et d'autres informations pertinentes. A la fin du dernier bloc une marque spéciale EOF (end of file) indique la fin du fichier. Plusieurs fichiers peuvent être rangés les uns derrière les autres.

Figure 4.11 - Organisation d'une bande magnétique

Cette implantation peut être reproduite sur un disque. Dans ce cas on utilise les secteurs d'une même piste, des pistes groupées sur un même cylindre et des cylindres contigus. Les adresses logiques du fichier correspondent aux adresses physiques dans l'ordre que nous venons de citer. Cette organisation est efficace car on minimise les déplacements des têtes de lecture mais il faut réserver tout l'espace nécessaire au fichier dés sa création. Rien ne pourrait garantir autrement que les blocs contigus ne soient pas utilisés pour un autre fichier. On l'utilise donc pour des fichiers essentiels du système d'exploitation dont la taille est fixe et qui doivent être accédés le plus efficacement possible. C'est la cas du système d'exploitation contenu dans le fichier command.com pour DOS.

Cette structure n'est pas naturelle pour un disque où n'importe quel secteur peut être atteint directement. Aussi n'est-t-elle, le plus souvent, que simulée. Les blocs qui constituent un fichier sont, le plus souvent dispersés, et le système de fichiers établit les liens nécessaires.

IV-3.4. Organisation aléatoire

On réserve le plus souvent l'espace nécessaire à un fichier au fur et à mesure des besoins. Dans ce cas on alloue les blocs sur la surface suivant un algorithme qui dépend du système d'exploitation. Nous évoquerons ce problème dans la section 2 du chapitre V. Les adresses physiques des informations appartenant à un même fichier sont donc dispersées aléatoirement sur la ou les surfaces. Il faut établir une correspondance entre ces adresses physiques et les adresses logiques contiguës, seules reconnues à l'intérieur du fichier. Les différents blocs constituent un ensemble qu'il faut chaîner pour pouvoir les parcourir successivement ou retrouver rapidement une adresse logique. Nous allons examiner deux méthodes de chaînage: par blocs chaînés ou au moyen de tables d'implantation.

IV-3.4.1. Blocs chaînés

Lors de sa création le système alloue un ou plusieurs blocs à un fichier. Leur nombre dépend du système d'exploitation. Chacun est constitué de plusieurs secteurs contigus. Dans chaque bloc un emplacement est réservé pour inscrire la valeur d'un pointeur sur le bloc suivant (fig. 4.12). Comme le dernier bloc n'est pas forcément complètement rempli, il faut prévoir également un emplacement pour indiquer le nombre d'octets réellement inscrits.

Le descripteur du fichier contient deux pointeurs sur le premier et le dernier bloc. Augmenter l'espace réservé au fichier revient à modifier la valeur du pointeur de fin de fichier dans le descripteur. Celui du bloc final doit être modifié pour pointer sur l'adresse d'un nouveau bloc. Ceci permet, à priori, d'ajouter un espace n'importe où dans le fichier: il suffit de changer le pointeur du bloc précédent et d'inscrire dans le nouveau bloc celui du bloc suivant. En pratique aucun système d'exploitation n'utilise cette possibilité car elle est difficile à exploiter . Les blocs sont ajoutés à la fin.

Figure 4.12 - Structure en blocs chaînés

Cette structure est simple mais peu efficace. Pour retrouver une information placée à une adresse logique précise il est nécessaire de parcourir successivement tous les blocs. Cette recherche, déjà lente par elle-même est encore ralentie par de nombreux déplacements des têtes de lecture puisque les blocs sont dispersés sur toute la surface. Imaginons par exemple le fichier contenant ce chapitre créé au moyen d'un traitement de texte. Lors de la première sauvegarde les premiers blocs ont été alloués le long d'un cylindre mais les suivants, au fur et à mesure du travail de rédaction, ont été placés là où un espace était disponible. Les différents fichiers créés par différents programmes se trouvent donc entrecroisés. Rapidement le disque se trouve morcelé et son accès s'en trouve ralenti. Il est alors conseillé de le compacter. Cette opération consiste à regrouper les différents blocs d'un même fichier à des adresses physiques contiguës le long de cylindres successifs. C'est ce que font les utilitaires de réorganisation de disque pour Windows et MacOs. Tous ceux qui les ont utilisés savent combien les performances du système d'exploitation s'en trouvent améliorées. Unix emploie une autre structure qui évite cette difficulté. Il n'est pas nécessaire de défragmenter le disque.

IV-3.4.2. Table d'implantation

Pour accéder aux blocs constitutifs d'un fichier, il existe une méthode plus efficace. On construit une table d'implantation contenant la liste des adresses de début des différents blocs (fig. 4.13).

Figure 4.13 - Principe d'un accès par table

Ajouter un bloc revient à modifier et à réorganiser la table. La correspondance entre adresses physiques et logiques est aisée. Soit S la taille d'un bloc et a l'adresse logique recherchée dans le fichier. Le rang r du bloc est obtenu en calculant la partie entière b de la division de a par S. Le reste de la division indique l'adresse dans le bloc. Il suffit donc de lire la valeur du pointeur contenu dans la ligne b de la table pour retrouver l'adresse de ce bloc. L'accès est donc plus rapide que par blocs chaînés. Regrouper les blocs constitutifs d'un fichier à des adresses contiguës peut optimiser les mouvements des têtes de lecture. Néanmoins cela est moins nécessaire que dans l'organisation précédente car on calcule directement les adresses. L'interface du disque peut alors réorganiser les requêtes pour minimiser les déplacements.

Figure 4.14 - Tables chaînées

Cette structure présente néanmoins une difficulté. Pour que le système d'accès soit efficace il est indispensable de ranger les tables à des adresses prédéterminées et donc de leur donner une taille fixe. Pour créer des fichiers contenant plus de blocs que le nombre maximum de lignes prévu dans une table on peut envisager deux mécanismes : allouer un espace supplémentaire c'est à dire chaîner des tables entre elles (fig. 4.14) ou établir plusieurs niveaux d'indirection (fig. 4.15).

Figure 4.15 - Table à deux niveaux d'indirection

Chaîner les tables (fig. 4.14) présente le même inconvénient que chaîner des blocs. Il faut les parcourir successivement pour accéder à un bloc de rang donné. C'est pourquoi on préfère le deuxième mécanisme (fig. 4.15) à condition de limiter le nombre d'indirections. Dans la pratique on ne dépasse pas deux niveaux. Ceci limite donc la longueur d'un fichier. Unix utilise des tables avec niveaux d'indirection et la longueur maximum d'un fichier dépend de l'implantation réalisée par le constructeur. C'est ainsi que certains ont du modifier récemment la structure de leur système de fichiers afin de réaliser des serveurs d'archivage capables de stocker des espaces dépassant le téraoctet. C'est une des principales raisons pour lesquelles toutes les nouvelles versions des systèmes d'exploitation utilisent des mots de quatre octets. On ne vise absolument pas à améliorer la précision des calculs en nombres flottants mais à représenter les entiers sur 64 bits. Ceci permet d'adresser des tailles de fichiers en rapport avec les capacités des supports qui atteignent maintenant plusieurs dizaines de G octets.

 IV-4. Système de fichiers sous Unix

IV-4.1. Eléments d'un système de fichiers

Unix possède de nombreuses variantes. La plupart des fournisseurs de systèmes se rattachent soit à Système V d'origine ATT soit à Berkeley (BSD). Les différences sont peu visibles pour les utilisateurs mais les systèmes de fichiers sont incompatibles. Une normalisation, elle-même incompatible avec les deux premiers systèmes, a été tentée sous l'égide de l'OSF (Open System Fundation). Dans ce qui suit nous résumerons brièvement BSD et System V.

L'espace disque est attribué par blocs de 512 à 4096 octets suivant les systèmes. La structure est composée de trois entités: le super bloc, le fichier des inodes et les fichiers de données : fichiers réguliers et répertoires.

Un système de fichiers est un disque virtuel créé par le responsable du système. Un disque peut être partitionné en plusieurs systèmes. Chez certains constructeurs un système de fichiers peut être réparti sur plusieurs disques. L'utilisateur ne voit que ces disques virtuels. Le super bloc contient des informations sur l'espace utilisé dans le disque virtuel, la liste des inodes des informations sur les fichiers réguliers. Le nom interne d'un fichier est un nombre entier appelé inode.

IV-4.2. Le super bloc

Le super bloc décrit l'état d'occupation des secteurs du disque virtuel, alloués au système de fichiers. Lorsqu'on cherche à écrire sur un disque, il est en effet indispensable de connaître la liste des emplacements libres et occupés. Il faut donc construire et tenir à jour une carte d'occupation des lieux. Les inodes sont les noms internes des fichiers reconnus sous la forme de nombres entiers. Le super bloc maintient également la liste des noms libres utilisables, indispensable à la création de nouveaux fichiers.

Parmi les informations les plus importantes que contient le super bloc, on retiendra

  • s_isize: la taille en blocs de la liste des inodes (i_list).
  • s_fsize: la taille en blocs du système de fichiers.
  • s_fname: le nom externe du système de fichiers.

Remarquons que ces informations déterminent le nombre maximum de fichiers que l'on peut créer et la taille du système de fichiers.

  • s_free: la liste des blocs libres.
  • s_inode: la liste des inodes libres
  • s_tfree: le nombre de blocs libres
  • s_tinode: le nombre d'inodes libres

Ces indications sont indispensables à l'allocation de l'espace et des fichiers. L'utilisateur peut la consulter au moyen de la commande df.

Le super bloc est chargé et verrouillé en mémoire au moment du démarrage ou lorsqu'un système de fichiers est monté (mount) et devient visible pour les utilisateurs. Il est constamment remis à jour et sauvegardé régulièrement sur disque ou volontairement par la commande sync.

IV-4.3. La liste des inodes

La liste des inodes ou i_list est l'élément fondamental du système de fichier. Tout dommage à cette structure détruit irrémédiablement les liens donc les fichiers qui deviennent difficilement récupérables. Pour s'en convaincre il suffit de savoir qu'elle contient les renseignements suivants pour chaque inode :

  • i_uid, le numéro de l'utilisateur qui est son nom interne dans le système.
  • i_mode, les droits d'accès sur le fichier.
  • i_size, sa taille en blocs.
  • toutes les informations sur sa date de création, de modification et de dernier accès.
  • un pointeur permettant, comme nous allons le voir, d'accéder à son contenu.

On y trouve également des informations indiquant s'il s'agit d'un fichier, d'un répertoire ou de tout autre fichier spécial. L'utilisateur consulte son contenu, pour la part qui lui est accessible, au travers des protections, au moyen de la commande ls qui liste les informations sur les fichiers contenus dans un répertoire.

On utilise un adressage direct pour accéder au fichier s'il est court , de l'ordre de dix blocs,  un adressage indirect pour les fichiers plus longs, comme schématisé dans la figure 4.16. La i_list comme le superbloc est chargée en mémoire et régulièrement remise à jour sur disque.

Figure 4.16 - Structure d'accès à un fichier

IV-4.4. Accès à un fichier

Imaginons qu'on recherche le fichier /usr/essai. Le processus pour y accéder est le suivant :

  1. Lecture de la i_list pour retrouver la référence du répertoire / (racine).
  2. Lecture de ce fichier répertoire. Les répertoires contiennent, entre autre, les noms interne et externe des fichiers et répertoires fils. usr est, par exemple, l'inode xxx
  3. Lecture de la i_list pour retrouver les références de l'inode xxx.
  4. Lecture des blocs correspondants à cet inode. On y trouve le nom interne yyy correspondant au nom externe essai.
  5. Lecture de la i_list pour retrouver les références de l'inode yyy.
  6. Accès au fichier yyy soit /usr/essai

Ce simple exemple montre la nécessité de préserver l'intégrité de la i_list. On notera également que l'accès serait extrêmement lent si celle-ci ainsi que le super bloc n'étaient pas chargés dans la mémoire de l'ordinateur. Ce n'était pas le cas des systèmes Multics connus par le passé et dont Unix est dérivé. Seul l'effondrement du prix des mémoires a permis à Unix de devenir un système efficace. Auparavant il souffrait des mêmes défauts que son prédécesseur et cette méthode d'accès était très lente.

IV-4.5. Fragilité des systèmes de fichiers

L'information écrite sur un disque évolue rapidement. A un instant donné il n'est pas garanti que la géographie physique du disque corresponde exactement à la copie du super bloc et de la i_list qui existent sur celui-ci puisque seules leurs images dans la mémoire sont modifiées instantanément. La mise à jour est effectuée régulièrement par leur recopie sur le disque mais si le système est arrêté inopinément alors qu'il était en pleine activité, il n'est pas certain que la cohérence du système de fichiers soit préservée. C'est pourquoi il ne faut jamais arrêter brusquement une machine Unix: il faut utiliser la procédure shutdown prévue à cet effet. Entre autre chose celle-ci recopie les informations de la mémoire sur les disques.

Au démarrage de tout système une procédure analyse le système de fichiers pour vérifier la cohérence des informations inscrites dans le super bloc et la i_list. Tout fichier ou morceau de fichier dont le chemin d'accès ne peut être retrouvé est placé dans un répertoire spécial appelé lost+found!

Cette vérification se déroule en cinq phases :

  1. phase I : vérification de la liste des inodes
  2. phase II : vérification des chemins d'accès
  3. phase III: vérification de la connectivité des répertoires
  4. phase IV : vérification des liens symboliques
  5. phase V : vérification du super bloc

Ceci peut prendre un certain temps si la capacité en disques est élevée. Les procédures de démarrage les plus évoluées sont capables de s'apercevoir si un système a été précédemment arrêté proprement. Elles évitent alors cette étape fastidieuse.

figure 4.17 : Réalisation moderne d'un système de fichiers Unix

Les constructeurs de systèmes informatiques sont conscients de la fragilité des systèmes de fichiers. Aussi ont-ils recherché, chacun à leur manière, une solution à ce problème inacceptable maintenant qu'Unix a quitté le domaine universitaire pour devenir un système utilisé dans les entreprises. Ils introduisent une couche logicielle entre la représentation Unix des fichiers et la structure physique sur le disque (fig. 4.17) qui réalise un certain nombre de fonctionnalités supplémentaires cachées. Par exemple la i_list comme le super bloc sont dupliqués un certain nombre de fois de façon à éviter leur perte. Il devient possible de reconstituer ces informations fondamentales à partir de leurs différentes images. Certains constructeurs ont même introduit des fonctions qui permettent de redimensionner dynamiquement les systèmes de fichiers sans arrêter le fonctionnement de l'ordinateur.

Tous ces éléments font que, bien que présentant une interface et des commandes d’utilisation commune, les systèmes de fichiers Unix sont parfaitement incompatibles entre constructeurs différents et même, cela s'est déjà vu, d'une version à la suivante d'un système d'exploitation. On ne peut pas débrancher un disque d'une machine Unix pour l'installer sur une machine en provenance d'un fournisseur différent et espérer pouvoir relire l'information qu'il contient. Windows ne présentent pas cette difficulté au même degré car, quelque soit l'origine de la machine, le système d'exploitation est toujours le même.

Cependant attention aux versions car les tables de références peuvent être écrites sur 16 ou 32 bits, ce qui les rend parfaitement incompatibles.

IV-5. Fonctions d'accès élémentaires

Un processus qui doit échanger des informations avec un fichier doit mettre en oeuvre un ensemble de fonctions qui réalisent les différentes opérations que nous avons évoqué tout au cours de ce chapitre, à savoir:

  • construction du flot d'entrées-sorties et liaison avec le système de fichiers. Cette opération est faite lors de l'ouverture du fichier. Après usage la liaison est rompue par la fermeture. Les paramètres gérables par le programmeur dépendent du système d'exploitation et des informations qui existent dans les descripteurs.
  • usage du fichier en utilisant une méthode adaptée. Nous les avons évoquées dans la section 2.

L'écriture des opérations qui réalisent les entrées-sorties dépend du langage de programmation. Néanmoins on retrouve un certain nombre de principes communs qui seront évoqués ici. Le problème le plus délicat est celui des options qui dépendent, comme nous venons de l'évoquer, du système d'exploitation mais aussi du langage, voire du compilateur. Lorsqu'on envisage de porter un programme sur différentes plates-formes il est donc sage de bien structurer l'application afin de regrouper ces parties du code pour pouvoir les modifier facilement. Il faut également éviter, dans la mesure du possible, les fonctions trop particulières qui pourraient ne pas exister ailleurs ni employer des techniques qui n'utilisent pas les appels normaux au système d'exploitation. Le non respect de ces quelques règles peut conduire à des programmes non portables ou même, dans le cas le pire, à des applicatifs qui ne fonctionnent plus lors d'un simple changement de version du système d'exploitation. La rapidité des processeurs modernes ne justifie plus les "bidouillages" souvent employés par le passé.

IV-5.1. Organisation du descripteur

Le descripteur d'un fichier contient des informations:

  • sur la localisation physique du fichier (voir les figures 4.12 à 4.14)
  • relatives à son utilisation
  • sur les droits d'accès

Parmi les informations relatives à l'utilisation on retiendra l'existence d'indications sur :

  • l'usage courant du fichier: disponibilité ou réservation par un ou plusieurs processus. On dit alors que le fichier est bloqué.
  • la nature du fichier. MacOs est capable de reconnaître l'application qui a créé le fichier car cette information est inscrite dans le fichier. Windows le fait par identification de l'extension du nom de fichier. Dans le cas d'Unix, cela n'est pas prévu.
  • la taille du bloc physique de transfert. Elle n'est pas toujours mentionnée. Les anciens systèmes IBM, comme VM par exemple, demandent cette information.
  • les dates de création, de dernière modification, de lecture, le nombre d'accès...
  • la nécessité de sauvegardes. Un drapeau spécial peut être exploité par une procédure spéciale. Ce drapeau est levé chaque fois que le fichier est modifié.
  • les droits d'accès pour les systèmes qui les gèrent.

Cette liste n'est pas limitative. Elle dépend du système d'exploitation. Ainsi la notion de droits d'accès est inexistante sur les micro-ordinateurs DOS ou MacOs. Unix ignore toute notion de bloc physique de transfert.

IV-5.2. Accès à un fichier

L'accès à un fichier comprend obligatoirement trois étapes. L'ouverture pour en permettre l'usage, les opérations de lecture et d'écriture puis la fermeture qui déclenchera le vidage des tampons sur disque. Ces différentes opérations nécessitent la connaissance d'un certain nombre de paramètres indispensables à la communication. Leur nombre, leur nature est très dépendante du système d'exploitation et de sa réalisation. 

IV-5.2.1. Ouverture et fermeture

L'ouverture d'un fichier est préalable à tout usage de celui-ci. La forme de la demande dépend à la fois du système d'exploitation et du langage utilisé. Parmi les nombreux paramètres possibles on retiendra:

  • le nom externe du fichier et éventuellement le nom interne.
  • son état: existant, nouveau à créer...
  • les conditions d'utilisation: en lecture, en écriture, les deux à la fois...
  • l'état du fichier: nouveau, déjà existant, temporaire pour la durée d'utilisation...
  • une longueur de bloc de transfert éventuellement.

La primitive d'ouverture crée la structure d'utilisation du flot (fig. 4.9) et marque, dans l'interface du flot, les conditions d'usage. On peut éventuellement préciser les conditions de partage entre plusieurs processus. Une lecture simultanée ne pose pas de problème lorsque l'information ne change pas mais devient délicate si elle est modifiée. Nous l'évoquerons au paragraphe suivant. Lors de l'ouverture on alloue les tampons nécessaires au transfert - on peut parfois indiquer leur taille et leur nombre- et on crée éventuellement le fichier ainsi que son descripteur s'il n'existe pas encore. La primitive retourne un code d'erreur qu'il convient de tester avant de commencer la moindre opération sur le fichier.

A la fermeture il suffit, dans la majorité des cas, de donner la référence du flot de communication. Le descripteur en mémoire est supprimé, celui sur le disque est mis à jour et les tampons sont vidés. Il faut insister sur l'importance de cette dernière opération. En général lorsqu'un processus se termine normalement les fichiers encore ouverts sont automatiquement fermés. Mais si le processus s'arrête de façon anormale, en cas d'erreur ou de panne, l'information contenue dans les tampons est perdue. Ce risque est facilement évitable en évitant de maintenir ouvert un fichier plus longtemps que son usage ne le nécessite.

IV-5.2.2. Accès à l'information

L'ensemble des primitives de lecture et d'écriture doit gérer non seulement les informations à lire ou à écrire mais aussi un ensemble de paramètres qui dépendent de la méthode d'accès. On utilisera des primitives différentes pour les accès synchrones et asynchrones.

Accéder à l'information nécessite trois opérations :

  • la détermination des adresses physiques de transfert en mémoire et sur disque
  • la préparation du transfert
  • le transfert proprement dit.

Il faut savoir que les deux premières étapes sont sensiblement de même durée que la quantité d'information à transférer soit petite ou grande, d'où la nécessité absolue de gérer correctement les tailles de blocs physiques échangés afin de minimiser le nombre d'interruptions du processeur.

Dans le cas de fichiers partagés, c'est également au cours de la préparation du transfert que doivent être réglés les conflits d'accès éventuels, notamment en écriture. Sans précaution particulière on risquerait de voir deux processus différents modifier presque simultanément un même enregistrement; l'information écrite sur le disque pourrait donc être fausse. Pour répondre à cette difficulté il existe deux techniques.

Dans la première on réserve le fichier à l'usage exclusif d'une seule application. Les autres processus sont mis en attente mais des délais maximum doivent être précisés si on veut éviter des verrous mortels. Cette technique est trop frustre si un fichier doit être partagé entre un grand nombre d'applications: on imagine mal les différents terminaux d'un système de réservation se mettant en attente les uns sur les autres jusqu'à la fin des transactions précédentes! Les systèmes transactionnels, les bases de données utilisent une approche plus fine en bloquant uniquement l'accès à un enregistrement donné. Si une application lit un article avec l'intention de le modifier, par exemple pour une réservation de siège dans un train, elle le marque et le rend indisponible pour tout autre. Le schéma temporel est le suivant :

Requête 1

Requête 2

......
boucle sur les enregistrements
lire le fichier;
.....
choix de l'enregistrement n à modifier;
bloquer (n);
fin boucle
.....
modifier (n);
libérer (n);

......
boucle sur les enregistrements
lire le fichier;
.....
ignore n si bloqué
fin de boucle
......

L'article n reste invisible ou non modifiable pour la deuxième reqête tant que la première n'a pas terminé son opération.

Une erreur classique est de ne pas vérifier, avant modification, si un article qui a été préalablement lu sans blocage, n'a pas été modifié depuis. Ceci explique les gags comme les doubles réservations. Il faut aussi faire très attention à bien gérer la libération des articles: si une application vient à disparaître prématurément il n'est pas simple de gérer la libération des enregistrements qui n'ont pas été débloqués.

Chapitre précedentIndex des CoursChapitre suivant

Révisé le :23-Sep-2007| ©2007 www.technologuepro.com