INFO502 : Systèmes d'exploitation

Les processus

Introduction

Allez hop commençons par une petite définition du type wikipédia :

Un processus (en anglais, process), en informatique, est défini par :

• un ensemble d'instructions à exécuter (un programme) ;
• un espace mémoire pour les données de travail ;
• éventuellement, d'autres ressources, comme des descripteurs de fichiers, des ports réseau, etc.

Un ordinateur équipé d'un système d'exploitation à temps partagé est capable d'exécuter plusieurs processus de façon « quasi- simultanée ». Par analogie avec les télécommunications, on nomme multiplexage (A. Tanenbaum parle de multiprogrammation) ce procédé. S'il y a plusieurs processeurs, le système essaie de répartir les processus de manière équitable sur les processeurs disponibles.

Le processus doit être imaginé comme quelque chose qui prend du temps, donc qui a un début et (parfois) une fin. De nombreux processus ne se terminent normalement jamais : système d'exploitation, serveurs web, serveurs mail, ... D'autres processus plus légers qui ne se terminent pas sont les daemon (acronyme a posteriori de "disk and execution monitor") du monde Unix.

Certains processus sont démarrés très tôt lors de la séquence de boot. Le système d'exploitation est un tel processus. Sinon, les processus sont normalement démarrés grâce à un appel système à partir d'un autre processus. L'utilisateur peut par exemple demander explicitement un nouveau processus (sous POSIX, grâce à un fork puis exec) ; mais la plupart du temps, il le fera à travers une application, par exemple en double-cliquant sur l'icône d'un programme dans l'explorateur de fichiers.

Le système d'exploitation est chargé d'allouer les ressources (mémoires, temps processeur, entrées/sorties) nécessaires aux processus et d'assurer que le fonctionnement d'un processus n'interfère pas avec celui des autres (isolation).

Pas sûr d'avoir tout compris ? Ce n'est pas grave, essayons autrement.

Définition : un processus est un programme en train de s'exécuter.

Cette définition implique en particulier que un programme (navigateur Firefox par exemple) peut correspondre à

• zéro processus si on ne l'a pas lancé,
• un processus si on l'a lancé,
• plusieurs processus si on l'a lancé plusieurs fois.

(Remarque : pour un programme comme Firefox, il y a fort à parier que l'exécution d'une seule instance de Firefox génère de multiples sous-processus...)

Que se passe-t-il quand je démarre une application?

L'ordinateur à une nouvelle tâche à accomplir, les instructions correspondantes sont donc envoyées au processeur. Comme il a plusieurs choses à faire le choix des instructions à exécuter n'est pas forcement simple. Il faut faire en sorte de partager le processeur entre les différentes tâches de manière équitable : c'est la fameuse gestion des processus.

Ceci permet de réaliser plusieurs activités en ~même temps~. Grâce à la gestion des processus on peut regarder un film (obtenu par des moyens tout à fait légaux cela va de soit), tout en jouant à la dame de pique.

(et dire que certain(e)s affirment que l'homme est mono tâche)

Plusieurs processus indépendants peuvent être actifs en même temps, mais sauf si l'ordinateur possède suffisamment de processeurs, on ne peut pas les exécuter simultanément. L'impression que plusieurs programmes s'exécutent en même temps vient simplement du fait que le processeur alterne rapidement entre eux. Comme le temps d'exécution d'une instruction par le processeur est très court, de l'ordre de la nano-seconde, le processeur peut réaliser plusieurs centaines de millions d'instructions par seconde. Ainsi, une tranche de temps de quelques fractions de seconde, partagée entre plusieurs processus, donne à l'échelle macroscopique l'illusion de la simultanéité.

En résumé : un système d'exploitation doit la plupart du temps traiter plusieurs tâches en même temps, et comme il n'a, en général, qu'un seul processeur, il devra contourner ce problème grâce à un pseudo-parallélisme. Il traite une tâche à la fois, s'interrompt et passe à la suivante. La commutation de tâches étant très rapide, il donne l'illusion d'effectuer un traitement simultané.

La table des processus

L'information sur les processus est conservé par le système dans une structure de données appelée table des processus. Cette table contient toutes les informations nécessaires à la gestion des processus :

• état du processus
• PID
• droits
• répertoire de travail
• pointeur vers la pile
• priorités
• ...

Sous Linux, on peut accéder à ces informations à travers le système de fichiers virtuel "Procfs". Il suffit d'aller dans le répertoire /proc/.

Création d'un processus

Pour les système POSIX, la création d'un processus est très simple : on utilise la fonction fork(). En C, le prototype de la fonction se trouve dans le fichier d'entêtes unistd.h.

Cette fonction prend 0 argument et permet de faire la chose suivante : elle crée un nouveau processus qui est une copie conforme du processus appelant. La seule différence visible entre l'ancien et le nouveau processus est que les processus ont un numéro (PID) différent. Pour le processus appelant, il peut obtenir le PID du nouveau processus en regardant la valeur de retour de fork. Pour le nouveau processus, cette valeur vaudra 0, et il devra utiliser la fonction getpid() pour obtenir son numéro.

Le processus appelant est appelé le père alors que le nouveau processus est appelé le fils.

Notez que l'espace mémoire du processus est dupliqué plutôt que partagé. Ceci veut dire que les processus ne peuvent pas communiquer en utilisant leur variables... Par contre, les descripteurs de fichiers du fils sont hérités directement de ceux du père ; ils peuvent donc essayer de communiquer en passant par ces fichiers. (Mais cela pose de nombreux problèmes de synchronisation.)

-- ... code C supprimé ... --

La technique consistant à faire

pid = fork();
if (pid) { /* le père */
  ...
} else { /* le fils */
  ...
}

montre que malgré le fait que les processus soient identiques à l'origine, on peut faire beaucoup de chose.

Remarque : fork() n'est pas directement un appel système, mais une fonction qui utilise l'appel système clone(). Cet appel système ne fait pas partie de la norme POSIX...

La deuxième technique utilisée dans les systèmes POSIX consiste à utiliser fork() pour dupliquer le processus, puis à complètement remplacer le fils par un nouveau processus. La fonction correspondante est la fonction execv :

pid = fork();
if (pid) { /* le père */
  ...
} else { /* le fils */
  execv("/usr/bin/...", argv);
  ...
}

La fonction execv prend 2 arguments : une chaîne contenant le chemin d'accès à un programme, et un tableau d'arguments à donner au programme. (C'est un peu plus compliqué que ça : le premier élément du tableau est le nom du programme, et le tableau doit se terminer par un pointeur NULL.)

Une dernière fonction importante est la fonction wait(pid) qui permet à un processus d'attendre l'arrêt du processus pid.

-- ...

L'API WIN32 possède de nombreuses fonctions avec des fonctionnalités similaires. Par exemple, la fonction CreateProcess permet de créer un nouveau processus (comme un fork suivi d'un exec), mais elle nécessite ... 10 arguments !

---

Un autre moyen de créer des processus est d'utiliser des 'processus légers' appelés Thread. Ces processus légers partage seulement une partie de la mémoire, ce qui en pratique est plus rapide pour simuler un parallélisme. On passe alors par une autre fonction. Sous GNU/Linux, lors de l'écriture d'un programme écrit en C il faut utiliser la bibliothèque pthread.h et lors de la compilation, faire un lien vers celle ci, en utilisant le paramètre -lpthread.

Arborescence des processus dans les systèmes POSIX

Nous avons vu que la fonction fork() permet de créer un processus fils. Le père connaît le PID de son fils : il lui est donné par la fonction fork(). Comme le fils peut lui même créer des processus fils, on obtient rapidement une arborescence de processus.

Vous pouvez visualiser cette arborescence à partir d'un terminal avec la commande pstree (l'option -p permet de demander l'affichage des PID)

$ pstree -p
init(1)─┬─acpid(25425)
        ├─atd(14365)
        ├─console-kit-dae(3632)─┬─{console-kit-dae}(3633)
        │                       ├─{console-kit-dae}(3641)
        ├─kdm(15564)─┬─Xorg(15566)
        │            └─kdm(15573)───sh(15608)─┬─conky(15751)
        │                                     ├─fluxbox(15703)───firefox-bin(6063)─┬─{firefox-bin}(6064)
        │                                     │                                    ├─{firefox-bin}(6065)
...
        │                                     ├─ssh-agent(15698)
        │                                     ├─unclutter(15742)
        │                                     ├─wicd-client(15749)
        │                                     └─xscreensaver(15683)

Le processus init est l'ancêtre de tout les processus, il a toujours 1 comme PID.

Remarque : sous Windows, les processus ne sont pas organisé en arborescence...

Mort d'un processus dans un système POSIX

Un processus peut se terminer pour plusieurs raisons :

• volontairement, grâce à la fonction exit() (POSIX) ou ExitProcess() (Windows),
• à cause d'une erreur,
• en recevant un signal d'un autre processus, grâce à la fonction kill() (POSIX) ou TerminateProcess() (Windows).

Lorsqu'un processus se termine, plusieurs choix sont possibles :

• que fait-on de ses fils ?
• que fait-on de son père ?

Linux fait la chose suivante : quand un processus s'arrête,

• tous ces fils s'arrêtent,
• son père reçoit un signal le prévenant que son fils vient de mourir.

Pour que le père puisse recevoir le signal correspondant, il faut qu'il utilise la fonction wait() ou waitpid(). Tant que le parent existe et qu'il n'a pas reçu le signal disant qu'un de ces fils est mort, le processus fils n'est pas entièrement supprimé : il devient un zombie. (Il n'occupe plus vraiment de place en mémoire, mais le système garde juste suffisamment d'information pour pouvoir prévenir le père si celui ci demande l'état du fils.)

Remarque : les processus Windows ne sont pas organisés sous forme d'arborescence. Chaque processus peut surveiller l'état d'un autre processus, s'il connaît son PID. Il n'y a donc pas de notion de processus zombie sous Windows.

-- ... code C supprimé ... --

Si on tue le processus fils pendant que le père ne fait rien, le processus fils devient un zombie. Dès que le père fait le wait, il reçoit la valeur du signal qui a terminé le processus et le zombie disparaît.

Si on ne tue pas le processus fils, le père n'exécutera jamais le printf(" >> Mon fils est mort...);.

Remarque : dans un système POSIX, lorsqu'un processus meurt, ses fils deviennent orphelins. Il continuent leur exécution mais sont adopté par init (PID : 1). Dans certains cas lorsque le processus est arrêté, il envoie explicitement un signal SIGTERM pour tuer ses processus fils. C'est par exemple ce qui arrive lorsqu'on lance des application à partir d'un terminal et que l'on quitte le terminal en question...

États d'un processus

On peut imaginer un SE dans lequel les processus pourraient être dans trois états :

• en cours d'exécution,
• bloqué : il attend un événement extérieur pour pouvoir continuer (par exemple une ressource; lorsque la ressource est disponible, il passe à l'état "prêt")
• prêt : suspendu provisoirement pour permettre l'exécution d'un autre processus.

Dans un système avec un unique processeur, au plus un processus peut se trouver dans l'état en cours d'exécution. Par contre, il peut y avoir de nombreux processus dans l'état bloqué ou dans l'état prêt.

Un processus peut passer d'un état à l'autre :

1. de en exécution à bloqué lorsqu'une ressource n'est pas disponible (entrées / sortie par exemple),
2. de bloqué à prêt si la ressource ayant provoqué le blocage devient disponible,
3. de en exécution à prêt si le système décide de suspendre l'exécution du processus,
4. de prêt à en exécution si le système décide de lancer l'exécution du processus.

On peut résumer ceci par le graphe de transitions suivant :

Les transition manquantes ne sont pas possible directement mais doivent passer par des transition intermédiaires.

On peut ajouter 2 états :

• nouveau pour un processus qui vient d'être créé,
• terminé pour un processus qui vient de se terminé.

Dans les systèmes type ordinateur de bureau, le passage de nouveau à prêt est automatique mais dans des systèmes temps réel, un processus peut parfois attendre dans cet état.

L'état terminé est en général passager. Par exemple, lorsqu'un processus terminé est un zombie, le processus n'est conservé que dans la table des processus. La mémoire utilisé par le processus est libérée. La question de savoir si ceci est véritablement un état du processus est donc essentiellement une question de vocabulaire.

exercice : ajouter les états nouveau et terminé et les transitions correspondantes au graphe précédent. Identifiez des situations provoquant les transitions possibles entre états.

Ordonnancement des processus

Nous avons vu qu'il pouvait y avoir de nombreux processus dans la table de processus (environ 150 sur mon ordinateur en ce moment même). Parmi ces processus, un seul (sur une machine à un processeur) peut se trouver dans l'état en exécution. C'est au système d'exploitation de décider qui, à un moment donnée, doit se trouver dans cet état. La partie du système faisant ceci s'appelle ordonnanceur (ou scheduler en anglais). En utilisant le contenu de la table des processus et éventuellement d'autres informations, ordonnanceur doit donc gérer les transitions entre états de tous les processus, et envoyer l'information nécessaire aux composants adéquat du noyau.

Comme d'habitude, l'ordonnanceur doit faire des compromis entre :

• la vitesse,
• l'utilisation de la mémoire,
• l'optimalité de la solution proposée.

Remarque : l'ordonnanceur est lui même un processus (ou un morceau de processus dans le cas des noyaux monolithiques).

Ordonnancement non préemptif

FIFO. L'algorithme d'ordonnancement le plus facile est probablement celui de type FIFO : premier arrivé, premier servi. Autrement dit, on préempte premier processus arrivé, et on l'exécute jusqu'à la fin. La seul structure de donnée est donc simplement une file.

Plus court temps d'exécution. Dans certain cas, on peut prévoir a l'avance le temps processeur dont aura besoin un processus pour s'exécuter. On peut alors choisir le processus le plus court et l'exécuter en premier. Ceci a en général tendance à diminuer le temps d'attente moyen d'un processus ; mais si des processus courts sont crées régulièrement, on peut assister à une famine : un processus peut ne jamais s'exécuter.

exercice : trouver une suite de processus qui provoque une famine.

Ces deux exemples sont acceptables pour un traitement par lots (batch) par exemple pour des calculs numériques. Ils ne sont par contre pas du tout adaptés pour un ordinateur personnel ou un système temps réels. (Pas de multiprogrammation.)

Ordonnancement préemptif

Pour pouvoir donner l'illusion de simultanéité, les processus sont en général exécutés par tranches de temps spécifiées à l'avance (time slice en anglais). Au bout de ce temps, le noyau reçoit une interruption et examine les processus. Il peut décider de continuer le processus courant, ou bien le remplacer par un autre processus. on parle de préemption.

Windows 3.1 ou MacOS 9 étaient des systèmes collaboratifs car les processus devaient explicitement laisser la main aux autres processus. Tous les systèmes d'exploitation modernes sont maintenant préemptifs. On parle maintenant de système préemptif lorsque la préemption peut s'effectuer même sur des processus en mode noyau. On parle parfois de noyau préemptible lorsque que les opérations en mode noyau sont elle même préemptibles.

Tourniquet. L'algorithme le plus simple est probablement celui du tourniquet (round Robin en anglais). C'est une variante de l'algorithme FIFO vu plus haut, mais qui préempte le processus courant au bout d'un moment. Si ce processus est encore en exécution, on le remet à la fin de la file des processus.

Le temps imparti à chaque processus ne doit pas être trop court (sinon, le changement de contexte prend trop de temps par rapport à l'exécution des processus) ni trop long (sinon, on perd l'illusion de parallélisme, et un processus bloqué risque d'occuper le processeur pendant trop longtemps).

Voici ce qu'on peut trouver dans le livre "Understanding the Linux kernel" :

The choice of quantum duration is always a compromise. The rule of thumb adopted by Linux is: choose a duration as long as possible, while keeping good system response time.

(extrait du chapitre "Process Scheduling").

Tourniquet avec priorité. Tous les processus ne naissent pas égaux : certains ont une importance plus élevée (les processus systèmes par exemple). Dans un cas comme le précédent, tous les processus ont le même statut... Pour corriger ce problème, on utilise parfois un algorithme similaire, mais on choisit le premier processus de priorité la plus élevé possible. Plutôt que de parcourir la file à sa rechercher, on utilise en fait plusieurs files : une pour chaque priorité.

Il faut faire attention car les processus de priorité basse risquent de ne jamais être exécutés (famine)... Par exemple, on peut diminuer petit à petit la priorité des processus qu'on exécute...

Une autre solution pour gérer les priorité en évitant certaines famines est d'exécuter toutes les files, mais pas en proportion égale. Par exemple, on choisit un processus dans les piles de priorité 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, ... De cette manière, les processus de la première file sont exécutés 2 fois plus de fois que ceux de la file 2, et 4 fois plus de fois que ceux de la file 3.

exercice : donnez un algorithme pour générer la suite précédente pour un nombre donné de files. Il faut que la file i soit utilisée 2 fois plus souvent que la pile i+1.

Répartition garantie. Chaque tache reçoit la même proportion du processeur, et chaque utilisateur reçoit la même proportion également.

tirage aléatoire. À chaque étape, on tire un "billet" au hasard, et le processus qui a le "billet gagnant" s'exécute.

Principe de priorité : Les processus qui ont été définit comme prioritaire on plus de "billet" à leur nom et ont donc plus de chance d'être tiré.

NB : POSIX définit une commande "nice" qui permet e donner à un processus un priorité plus faible (et par conséquent, nice -x augmente cette priorité). Il est évident que tout le monde ne doit pas pouvoir utiliser cette commande, il vaut mieux que l'administrateur se réserve ce droit

Ordonnancement équitable.

La mémoire

Introduction

RAM = Random Acces Memory. C'est ce que l'on appelle couramment la mémoire vive, elle peut être modifié à l'infini et sert à stocker temporairement les fichiers que l'ordinateur exécute.

ROM = Read Only Memory. On l'appelle aussi mémoire fixe ou mémoire morte, dès que l'on enregistre, le contenu d'une mémoire ROM ne peut pas être modifié (ex: un CD-ROM).

Gestion de la mémoire :

Lors du boot du PC, le système est chargé en mémoire. Tout processus créé est aussi chargé dans la mémoire.

Lorsque l'on créé uns seul processus, il est plus pratique de le charger en "bas" de la mémoire, à partir de la première case de l'espace mémoire. Puis les nouveaux processus peuvent être charger par dessus. Ainsi la machine comprend où commence l'espace mémoire.

Problèmes : 1 - l'espace d'adressage ne commence pas à 0; 2 - un processus peut demander dynamiquement de la mémoire; 3 - avec un accès direct, un processus peut faire "planter" un autre.

==> Il faut avoir une couche d'abstraction au-dessus de la mémoire physique.

Espaces d'adressage

Et si l'on créait des espaces d'adressage distincts pour chaque processus ? Par exemple : chaque processus utilise des adresse de 0 à n de la mémoire, on converti alors ces adresses en adresses physiques.

Certains des premiers processeurs avaient deux registres supérieurs :

- une Base => adresse physique du début de l'espace d'adressage

- une Limite => adresse physique de fin de l'espace d'adressage

Par exemple, lors de l'exécution d'un processus l'accès à une case "a" se transforme en l'accès à la Base+a et un test pour vérifier que : a+Base < Limite.

Malgré tout, ceci ne résout pas les problèmes liés au fait que des processus sont créés et disparaissent, réclament ou libèrent de la mémoire.

Va-et-vient (swapping)

Idée

Et si pour gérer tout cela on utilisait une mémoire auxiliaire (disque), pour stocker l'état de la mémoire de processus.

La mémoire vue par les processus ne correspond pas à la mémoire physique. À un instant donné, certains processus peuvent se retrouver sur le disque (dans le SWAP).

Quand un processus apparait, on lui cherche un morceau d'espace libre dans la mémoire.

gestion de la mémoire

• tableau de bits
• liste chaînée

Allocation

• first fit : utilise le premier bloc trouvé dans la mémoire dont la taille est égale ou supérieure au besoin.
• next fit : recherche un bloc disponible dont la taille convient exactement au besoin, et sinon utilise un bloc de taille supérieure.
• best fit : utilise le bloc le plus grand disponible.
• worst fit : first fit + recherche du bloc suivant à partir de la dernière case allouée.

Mémoire virtuelle

Idée

On ne garde pas tout le processus en mémoire physique.

Ceci permet d'offrir une mémoire virtuelle beaucoup plus grande que la mémoire réelle (physique).

L'espace d'adressage du processus est découpé en 'pages' de taille constante (sous GNU/Linux : 4Ko).

Il s'agit de mémoire virtuelle.

La mémoire virtuelle est découpée en 'cadres de page' de même taille que les pages. Idéalement, chaque page est dans un cadre. Les pages ne sont pas forcément dans des cadres consécutifs. Toutes les pages ne sont pas forcément dans des cadres : certaines peuvent être dans la swap.

Pagination

La traduction des adresses est plus complexe.

Si un processus fait référence à l'adresse 'a' :

1 - si une page est de taille "p" l'adresse "a" se trouve dans la page [a/p]

2 - l'adresse est à l'octet a%p dans cette page

3 - si la page [a/p] est dans le cadre n

L'adresse physique correspondant à "a" est (m*p)+(a%p).

Comme les adresse sont écrites en base 2 et que la taille d'une page est une puissance de 2, le quotient et le modulo s'obtiennent très facilement.

Si lors de l'étape 3, on réalise que la page n'est pas dans le cadre, on obtient un 'défaut de page'.

Dans ce cas, il faut trouver un cadre libre (ou en libérer un) et recopier la page en question à partir de la swap. Le processus est bloqué pendant ce temps.

Table des pages

Le système garde l'information sur les pages dans la table des pages, chaque entrée est de la forme :

Remarque :

Sous GNU/Linux, une page fait 4Ko soit environ $2^{12}$ octets.

Si on a un système d'exploitation sous 32 bits, la mémoire virtuelle contient $2^{32}$ octets, soit environ un million de pages.

Comme le nombre de pages est grand, chercher des informations prend du temps. Avec la mémoire virtuelle, chaque instruction est transformée en plusieurs instructions. Même si la table des pages est en mémoire, on y accède très souvent.

La plupart des processus accède tout le temps aux mêmes pages.

On rajoute un système pour accélérer l'accès à ces pages.

-> Le TLB :Translation Lookaside Buffer Partie matérielle du MMU (Memory Magement Unit).

Le TLB contient un petit nombre de la table des pages (moins de 64 pages) à accès ultra rapide -> ne contient que des pages en mémoire. Quand on fait référence à une adresse, on regarde en premier dans le TLB. Si une page n'est pas dans le TLB, on la cherche dans la table et on la met dans le TLB, pour les utilisations ultérieures (Remarque : il choisit une page à supprimer du TLB).

On parle du soft-miss quand une page est en mémoire mais n'est pas dans le TLB.

On parle de hard-miss dans la page n'est pas en mémoire (ou défaut de page).

Remplacement des pages

Algorithmes de remplacement de pages

Suite à une défaut de page , il faut recopier une page dans un cache, et il faut donc parfois supprimer une page de la mémoire.

-> Laquelle supprime-t'on ?

Algorithme optimal qui minimise le nombre de défaut de pages.

-> c'est compliqué et lent

-> on ne connait pas l'ordre des demandes de pages

Remplacement 'NRU' : Not recently Used

Idée

On remplace une page qui n'a pas été utilisée 'récemment'.

-> On utilise le bit de référencement ou d'accès en lecture

-> Régulièrement (interruptions horloge), on remet ce bit à 0

On choisit un cadre à supprimer par ordre de préférence :

- Bit référence 0 Bit écriture 0

- Bit référence 0 Bit écriture 1

- Bit référence 1 Bit écriture 0

- Bit référence 1 Bit écriture 1

FIFO

-> Pas bien

Algorithme de la seconde chance

Idée FIFO, mais on laisse une seconde chance aux pages références.

FIFO, si le dernier cadre a son bit de référence à 1, on remet le cadre en début de file avec son bit de référence à 0.

Tailles des pages

- Il faut choisir des pages pas trop grosses/petites pour éviter la fragmentation 'interne' (une page utilisée à moitié).

- Quand on accède à une page en swap on passe beaucoup de temps à chercher la page.

Les systèmes de fichiers

L'unité d'information crée par un processus est un fichier.

Comment ?

• Un support (disque, bande magnétique, etc..) peut être vue comme de la mémoire avec :

* une taille de bloc fixe

* une opération "read (a)" pour lire le bloc a

* une opération "write (a,b)" pour écrire b dans le bloc a

Une fichier n'est pas uniquement une suite d'octets. On veut organiser les fichiers de manière logique :

-> chaque fichier a (au moins) un nom

-> les fichiers ont organisés en arborescence dans des répertoires.

En général, le nom d'un fichier comporte une extension .ext (DOS 8.3) L'extension n'est qu'une partie du nom.

$file <nom_du_fichier>

Maintenant il y a une limite de taille du nom (255 caractères).

Comment stocker un fichier ?

- octets consécutifs sur le disque :

Avantage : rapide et simple, si on ne supprime pas

Inconvénient : si on supprime ou modifie -> c'est lent

-> Ce n'est pas utilisé pour les disques durs mais dans les CDs, DVDs, etc..

- suite de blocs -> (liste chainée) de blocs

Inconvénients :

- plus complexe d'accéder au milieu du fichier

- le pointeur prend quelques octets

Remarque : on a souvent besoin d'accéder à des plages de taille $2^{n}$

La taille d'un bloc de données (sans le pointeur) n'est pas une puissance de 2.

Pour corriger, on peut stocker les pointeurs dans un tableau à l'extérieur du fichier.

Cette taille doit être stocké en mémoire pour un accès rapide. Suivant la taille du bloc, on peut facilement atteindre une taille de 600mo pour un disque dur de 200Go.

-> Pas raisonnable

- Inode (index des nœuds)

On garde une taille des fichiers qui contient

- entête (information sur le fichier) sauf le nom

- adresse de blocs de données, un nombre fixe

- adresse d'un bloc qui contient des adresses de données

Le numéro d'une case (et donc d'un fichier) s'appelle un inode.

La table des inodes des fichiers ouverts est stockées en mémoire. Sa taille est proportionnelle au nombre de fichiers ouverts.

Remarque : la taille des blocs doit être

- ni trop petit (perte du temps pour la lecture sur le disque)

- ni trop gros (perte d'espace sur le dernier bloc)

Gestion des répertoires

- Un répertoire est donné par des informations (nom, date, etc...) et la liste de ces fichiers.

Attention : le nom des fichiers peut être long, on risque de perdre de la place.

Par exemple, on garde un tableau avec des numéros d'inode et un pointeur vers le nom de fichier.

Remarque : avec cette représentation, un fichier "physique" peut se trouver dans plusieurs répertoires.

On parle de lien physique entre les fichiers.

Sous Unix, la commande pour crée un lien physique est ln:

Attention : Il ne faut pas confondre un lien physique avec un lien symbolique.

Un lien symbolique est un nouveau fichier qui pointe sur un autre fichier (par son chemin d'accès).

- rajoute un inode

-> Il y a une direction.

Un lien physique ne peut exister que sur une unique partition.

Un lien symbolique peut pointeur n'importe où.

Remarque : une partition ressemble en général à :

Secteur de boot | Super bloc Information sur le FileSystem | Gestion espace libre |Taille inode | ....

Le système d'exploitation offre des fonctions "haut niveau" pour accéder aux fichiers.

Les fonctions principales sont : create(); delete(); open(); read(); write(); append();