Mercredi 28 Juillet 2010 - 13:21:29

Bonjour à tous!

Juste vous informé que je suis maintenant accessible à l'adresse ngoucheme de Overblog.

Mecri pour ce désagrément!

Cordialement

Mardi 9 Juin 2009 - 16:33:34

La pagination

Sur les premiers ordinateurs, la mémoire physique présente (de type RAM) avait une petite capacité car elle était chère. Les programmeurs devaient ainsi tenir compte de sa taille et les programmes devaient  être réécrits dès qu’ils étaient utilisés sur des machines disposant de moins de mémoire que prévu.

Depuis la fin des années 1950, des mécanismes de “mémoire virtuelle” ont été développés pour dépasser ces limitations. Aujourd’hui, les processeurs travaillent “sur du vent”, avec des données et des instructions qui sont situées dans un espace d’adresses purement “virtuelles”, totalement décorrélé de l’espace des adresses physiques. Ces données/instructions peuvent être en réalité stockées en RAM ou bien sur le disque dur (swap, fichiers exécutables ou bibliothèques de fonctions) ou sur d’autres machines du réseau local (NFS), etc.

Dans cet article,  nous allons nous concentrer sur une autre technique de mémoire virtuelle : la “pagination”.

Nous présenterons d’abord quelques généralités sur les principes de la mémoire virtuelle  en faisant abstraction de la technique choisie (segmentation ou pagination). Nous donnerons davantage de détails sur le cas particulier de la pagination.

L’objectif associé à la “mémoire virtuelle” est de pouvoir écrire des programmes en considérant que la mémoire disponible est “infinie” ou du moins indépendante de la RAM disponible.  A cette fin, les autres ressources disponibles (telles que le disque dur local ou celui d’une autre machine sur le réseau) peuvent être utilisées pour stocker les parties de cette mémoire virtuelle qui ne servent pas souvent. Ceci permet de libérer de la RAM[1] pour y stocker ce qui sert plus fréquemment. C’est le mécanisme de swap qu’on retrouve sur la plupart des OS génériques, tels que Linux.

Les mécanismes de mémoire virtuelle présentent beaucoup d’intérêt. Ils permettent de :

-           s’abstraire de la taille de la RAM disponible ;

-          utiliser des ressources de stockage autres que la RAM : disque dur et pourquoi pas, la RAM ou le disque dur d’une machine distante sur le réseau ;

-          signaler des erreurs de programmation grâce au contrôle de tous les accès aux adresses fictives par l’intermédiaire de la MMU[2].

La pagination est une technique basé sur une double indirection qui sert à étendre la mémoire virtuelle jusqu'à un maximum de 4Go quelque soit la RAM disponible, c'est donc un mécanisme extrêmement performant implanté directement dans la MMU ( Memory Management Unit ) qui est elle même généralement inclus dans les microprocesseurs récents, et c'est donc pour cela qu'elle est très largement utilisé dans tous les OS modernes. Elle permet aussi selon sa configuration de séparer différentes parties de la mémoire notamment la distinction des processus et pourra donc être utilisée pour détecter des tentatives de violation d'accès.

[3]Lorsque la mémoire physique devient pleine et qu'un thread a besoin d'accéder à des données non présentes dans la mémoire physique, le Gestionnaire de mémoire virtuelle (VMM) déplace quelques pages de la mémoire physique vers une zone de stockage de disque appelée fichier d'échange. Le VMM charge alors les données demandées par le thread dans la zone de mémoire physique libérée.

Figure 1: Pagination

L'espace d'adressage virtuel attribué à un processus est divisé en pages correctes et en pages incorrectes. Les pages correctes correspondent aux pages situées dans la mémoire physique, qui sont disponibles pour le processus. Les pages incorrectes sont celles qui n'existent pas dans la mémoire physique. Elles ne sont pas disponibles pour le processus ou ne sont pas stockées sur le disque. Lorsqu’un thread demande à accéder à une page incorrecte, le processeur émet un défaut de page. Le VMM intercepte le défaut de page et localise la page physique. Au contraire, pour libérer de la mémoire physique, le VMM sélectionne le contenu de certaines pages et le transfère sur disque.

Concrètement la pagination est implémentée sur le principe suivant :

-          La mémoire physique est partitionnée en petits morceaux de même taille : les cadres de pages (page frames) ou pages physiques

-          Chaque processus est aussi partitionné en petits morceaux de même taille appelés pages logiques)

-          Les pages d'un processus peuvent donc être assignées aux cadres disponibles n’importe où en mémoire principale

Par conséquent, un processus peut être éparpillé n'importe où dans la mémoire physique. De même la fragmentation externe est éliminée.

Initialement : deux processus P1 et P2 découpés respectivement en 3 pages (P11, P12, P13) et 4 pages (P21, P22, P23, P24). Par exemple, le processus P2 a deux pages (P21, P23) en mémoires et deux sur le disque (P22, P24).

Adresses virtuelles		Traduction d’adresse	Adresse physiques
1	P11		A	P12
2	P12		B	P13
3	P13		C	P21
4	P21		D	P23
5	P22
6	P23
7	P24

                                                                        

Instant d’après

Le processeur a besoin de la page P24, il se produit un défaut de page, et un algorithme[4] de remplacement de pages est appliqué. La page P13 est renvoyée sur le disque et la page P24 est transférée en mémoire principale.  C’est le swapping.

Adresses virtuelles		Traduction d’adresse	Adresse physiques
1	P11		A	P12
2	P12		B	P24
3	P13		C	P21
4	P21		D	P23
5	P22
6	P23
7	P24

                                                                                                                                     

Figure 2: Pagination

 

La table des pages

La MMU dispose d'une table des pages pour convertir les adresses virtuelles en adresses physiques. Les principales informations dans la table :

-           un bit (0/1) qui indique si la page est en mémoire principale ou non

-          Numéro du cadre (page physique)

-          Protection : bits de lecture, écriture, exécution

-          Modifié : 1 bit (M) qui indique si une page modifiée et par conséquent doit être écrite sur la mémoire secondaire (le disque)

-          Référencé (accédé) : 1 bit (R) qui est mis à 1 chaque fois que la page est lue ou écrite.

Conclusion

La pagination permet une meilleure utilisation de la mémoire en diminuant au maximum la fragmentation :  il n’y a aucune création de trous inutilisables entre les programmes. La pagination permet d’avoir un espace virtuel très grand quelque soit (ou presque) la quantité de mémoire physique disponible. La pagination permet donc, sur une machine donnée, d’exécuter des programmes plus grands que la mémoire physique.

Cependant, La taille des tables de pages peut devenir très importante si l’espace virtuel est très grand (chaque processus devant avoir sa propre table) : ceci peut obliger à ranger les tables de pages dans un espace virtuel, lui-même paginé. Il faut alors, pour éviter une traduction d’adresse trop longue que le système soit aidé par des dispositifs matériels. Un processus ne peut pas utiliser simultanément deux routines qui ont été construites à la même adresse dans l’espace virtuel.

 

Mardi 9 Juin 2009 - 13:43:21

Les disques durs, aussi petits soient-ils, contiennent des millions de bits, il faut donc organiser les données afin de pouvoir localiser les informations, c'est le but du système de fichiers. Le formatage logique d’un disque permet de créer un système de fichiers sur le disque, qui va permettre à un système d'exploitation (DOS, Windows 9x, UNIX, ...) d'utiliser l'espace disque pour stocker et utiliser des fichiers. Le système de fichiers est basé sur la gestion des clusters (en français « unité d’allocation »), c’est-à-dire la plus petite unité de disque que le système d’exploitation est capable de gérer.

Un cluster est constitué d’un ou plusieurs secteurs, ainsi plus la taille d’un cluster est importante, moins le système d’exploitation aura d’entités à gérer.

En contrepartie, étant donné qu’un système d’exploitation ne sait gérer que des unités d’allocation entière, c’est-à-dire qu’un fichier occupe un nombre entier de cluster, le gaspillage est d’autant plus grand qu’il y a de secteurs par cluster. On comprend alors toute l’importance du choix du système de fichiers.

En réalité le choix du système de fichiers se fait en premier lieu suivant le système d’exploitation que vous utilisez.

Au fil des années, de nombreux systèmes de fichiers ont vu le jour sur le marché suivant les différentes variétés des systèmes d’exploitation. On peut par exemple citer :

-       La  FAT16 ; la FAT32

-       NTFS ;

-       Ext2, Ext3, ReiserFS, Linux Swap ;

-       HFS (Hierachical File System), MFS (Macintosh File System)

-       UFS (Unix File System)

-       …

Dans cet article, il sera question pour nous de présenter les deux premiers système de fichiers la firme Microsoft : le système FAT16 et le système FAT32.

Le premier système (SF)  de fichier ayant été utilisé sur un système d’exploitation Microsoft est le système FAT (File Allocation Table). Ce SF un index qui liste le contenu du disque. C’est la table d’allocation de fichiers ou FAT (File Allocation Table).

La table d’allocation des fichiers permet de conserver la structure du fichier en créant des liens vers les blocs constitutifs d’un fichier, étant donné que les blocs qui constituent un fichier ne sont pas toujours stockés de manière contiguë sur le disque.

Le système FAT16 est un système 16 bits permettant de décrire un fichier par un nom d’une longueur de 8 caractères et une extension qui en comporte 3.

Pour améliorer ce point, la version originale de Windows 95 (employant le système FAT16) a été dotée d’une prise en charge améliorée de la FAT, il s’agit du système VFAT (Virtual FAT). La VFAT est un système 32 bits permettant d’enregistrer un fichier avec un nom de 255 caractères de long.

Le système de fichiers FAT est un système 16 bits, cela signifie qu’il ne peut pas adresser les clusters sur plus de 16 bits. Le nombre maximum de clusters repérables avec le système FAT est ainsi de 2¹⁶, soit 65536 clusters. Or, étant donné qu’un cluster est constitué d’un nombre fixé (4,8,16,32, ...) de secteurs de 512 octets contigüs, la taille maximale d’une partition FAT se trouve en multipliant le nombre de clusters par la taille d’un cluster. Avec des clusters d’une taille 32Ko, la taille maximale d’une partition FAT est donc de 2Go.

D’autre part, un fichier ne peut occuper qu’un nombre entier de clusters, c’est-à-dire que si un fichier occupe plusieurs clusters, le dernier sera occupé en partie, et la place inoccupée restante est autant de place perdue. Par conséquent plus la taille d’un cluster est réduite, moins il y a de gaspillage de place. On estime qu’un fichier gaspille en moyenne la moitié d’un cluster, cela signifie que sur une partition de 2Go 16Ko seront perdus par fichier…

Bien que la VFAT soit astucieuse, elle ne permet pas de remédier aux limitations de la FAT16. Ainsi, un nouveau système de fichiers (et non une meilleure prise en charge de la FAT telle que VFAT) est apparu avec Windows 95 OSR2. Ce système de fichiers, appelé FAT32 utilise des valeurs 32 bits pour les entrées de la FAT. En réalité seuls 28 bits sont utilisés car 4 bits sont réservés.

Avec l’apparition du système de fichiers FAT32, le nombre maximal de clusters par partition est passé de 65535 à 268 435 455 (2²⁸-1). La FAT32 autorise donc des partitions d’une taille beaucoup plus élevée (jusqu’à 8 téraoctets). En réalité la taille théorique maximum d'une partition FAT32 est de 8 To, toutefois Microsoft la limite volontairement à 32 Go sur les systèmes Windows 9x afin de favoriser NTFS. Puisqu’une partition FAT32 peut contenir beaucoup plus de clusters qu’une partition FAT16, il est possible de réduire de façon signifiante la taille des clusters et de limiter par la même occasion le gaspillage d’espace disque. A titre d’exemple, pour une partition de 2Go, il est possible d’utiliser des clusters de 4Ko avec le système FAT32 (au lieu de 32Ko en FAT16), ce qui diminue l’espace gaspillée par un facteur 8.

En contrepartie la FAT32 n’est pas compatible avec les versions de Windows antérieures à la version OEM Service Release 2. Un système démarrant avec une version précédente ne verra tout simplement pas ce type de partition.

Le nombre de clusters étant limité, la taille maximale d'une partition dépend de la taille de chaque cluster. Voyons voir la taille maximale d'une partition suivant la taille des clusters et du système de fichiers utilisé:

Taille d'un cluster	Système de fichier FAT16	Système de fichier FAT32 (théorique)
512 octets	32 Mo	64 Mo
1 Ko	64 Mo	128 Mo
2 Ko	128 Mo	256 Mo
4 Ko	256 Mo	8 Go (1 To)
8 Ko	512 Mo	16 Go (2 To)
16 Ko	1 Go	32 Go (4 To)
32 Ko	2 Go	2 To (8 To)

Lorsque vous formatez un disque dur, il faut donc déterminer avec précaution le type de système de fichiers à utiliser, en prenant celui permettant d'avoir un espace disponible le plus proche possible de la taille désirée!

Lorsque plusieurs systèmes d’exploitation cohabitent sur une même machine, le problème du choix du système de fichiers est à son paroxysme. En effet, le système de fichiers est étroitement lié au système d’exploitation, ainsi lorsqu’il y a plusieurs systèmes d’exploitations, il faut choisir pour chacun d’entre-eux le système d’exploitation en prenant en compte le fait qu’il est possible que l’on ait à accéder à des données de l’un à partir d’un autre. Une première solution consiste à utiliser des partitions FAT pour tous les systèmes, en faisant attention à n’utiliser que des partitions d’une taille inférieure à 2Go. La solution la plus adaptée est d’utiliser pour chacun des systèmes une partition dont le système de fichiers est le plus adapté, et de dédier une partition en FAT16 aux données vouées à être partagées par les différents systèmes d’exploitation. 

Bibliographie

 http://fr.wikipedia.org/wiki/FAT32

 http://fr.wikipedia.org/wiki/FAT16 : le système FAT16, consultée le 24 mai 2009 à 11h00

ghttp://fr.wikipedia.org/wiki/Syst%C3%A8me_de_fichiers: le système FAT16, consultée le 24 mai 2009 à 12h00

 : le système FAT32, consultée le 23 Mai 2009 à 15H00