Ce cours s'intéresse aux différentes méthodes permettant l'allocation de l'espace mémoire aux programmes à exécuter. Il aborde les différentes méthodes d'allocation et notamment les mécanismes de pagination et de segmentation

Nous commençons par un bref rappel du concept de mémoire au niveau matériel. La mémoire physique est constituée d'un ensemble de mots mémoire contigus désignés chacun par une adresse physique. Le processeur accède aux mots de la mémoire centrale par le biais de deux registres, le registre Adresse RAD et le registre donnée RDO. Le registre RAD contient l'adresse du mot à lire ou l'adresse du mot où écrire tandis que le registre RDO contient soit la donnée à écrire, soit la donnée lue. Les lignes d'adresses, de données et de commandes du bus font la liaison entre les registres processeur et la mémoire. Dans un système en monoprogrammation, la mémoire centrale est occupée d'une part par les procédures du système d'exploitation , d'autre part par un seul programme utilisateur . Comme nous l'avons vu plusieurs fois déjà, l'occurrence d'opérations d'entrées/sorties demandées par le processus peut entrainer une inactivité du processeur si celles-ci sont gérées par DMA. Par exemple, avec un processus effectuant 50 % de calcul et 50 % d'entrées/sorties, le processeur est inactif durant 50% du temps. Une telle inactivité du processeur n'est pas souhaitable : on place donc un second programme en mémoire centrale de même profil. Le processeur est maintenant occupé à 100 % (cas idéal et non réel) car il exécute le second processus durant l'entrée/sortie du premier processus . Le système est maintenant multiprogrammé.

Le schéma ci-dessous représente le taux d'activité du processeur en fonction du nombre de processus présents en mémoire centrale et en fonction du temps d'entrée-sortie de ces processus. 

Fig 1 : Degré de multiprogrammation

Dans un système multiprogrammé, trois problèmes sont à résoudre vis-à-vis de la mémoire centrale : 

Les méthodes d'allocation mémoire peuvent être divisées en deux grandes familles :

Dans cette méthode d'allocation, le programme est considéré comme un espace d'adressage insécable. La mémoire physique est découpée en zones disjointes de taille variable, adaptables à la taille des programmes : ces zones sont appelés des partitions . Initialement, la mémoire centrale est uniquement occupée par les procédures du système d'exploitation. La zone réservée aux programmes utilisateurs est vide et constitue une unique zone libre. Au fur et à mesure des chargements de programmes, la zone libre va se réduire et à l'instant t, elle n'occupe plus qu'une fraction de la mémoire centrale (mémoire basse). Lorsque l'exécution des programmes se termine (ici P2 et P4), la mémoire est libérée : il se crée alors pour chaque zone libérée, une nouvelle zone libre. Finalement, la mémoire centrale se retrouve constituée d'une ensemble de zones allouées et de zones libres réparties dans toute la mémoire. Les zones libres sont organisées en une liste chaînée de zones libres repérée par une tête de liste.

Fig 2 : Allocation en partitions variables

Dans ce contexte, charger un nouveau programme consiste à trouver une zone libre suffisamment grande pour pouvoir y placer le programme. Une première stratégie pour trouver et choisir cette zone libre est de prendre la première zone libre suffisamment grande trouvée au cours du parcours de la mémoire (parcours de la liste chaînée) : c'est la stratégie First Fit. Ici, donc, le programme 7 est placée dans la zone libre de 120K ce qui crée une nouvelle zone libre résiduelle de 40K.

Fig 3 : Stratégie First Fit

Une seconde stratégie pour trouver et choisir cette zone libre est de prendre la zone libre dont la taille est la plus proche de celle du programme à allouer, donc celle engendrant le plus petit trou résiduel : c'est la stratégie Best Fit. Ici, donc, le programme 7 est placée dans la zone libre de 100K ce qui crée une nouvelle zone libre résiduelle de 20K.

Fig 4 : Stratégie Best Fit

Au fur et à mesure des opérations d'allocations et de désallocations, la mémoire centrale devient composée d'un ensemble de zones occupées et de zones libres éparpillées dans toute l'étendue de la mémoire centrale. Ces zones libres peuvent devenir trop petites pour permettre l'allocation de nouveaux programmes (problème de fragmentation de la mémoire). Par exemple, sur la figure 5, la mémoire centrale com port e 3 zones libres mais aucune d'elles n'est assez grande pour contenir un programme 8 de 180K. Pourtant l'ensemble des 3 zones libres forme un espace de 120 + 20 + 150 = 350K suffisant pour le programme 8. Pour permettre l'allocation du programme 8, il faut donc réunir l'ensemble des zones libres pour ne former plus qu'une zone libre suffisante : c'est l'opération de compactage de la mémoire centrale .

Fig 5 : Fragmentation et compactage de la mémoire centrale

Le compactage de la mémoire centrale est une opération coûteuse. Il n'existe pas d'algorithme simple permettant d'optimiser le nombre d'octets déplacés lors d'une telle opération. Par ailleurs elle suppose une translation des adresses dynamiques. Dans le mécanisme de chargement dynamique, les adresses du programme chargé en mémoire centrale ne sont pas translatées de la valeur de l'adresse d'implantation au moment du chargement, mais seulement au moment de l'exécution. L'adresse d'implantation du programme est conservée dans un registre processeur - le registre de translation - .Ainsi lors de l'opération de compactage, déplacer un programme consiste seulement à changer la valeur d'adresse d'implantation à charger dans le registre de translation. L'allocation en mémoire centrale d'un seul tenant souffre donc de deux défauts principaux : 

Une solution est de diviser le programme en portions de taille fixe et égales à l'unité d'allocation de la mémoire centrale. On dit alors que le programme est découpé en pages. Le mécanisme d'allocation associé s'appelle la pagination.

Dans le mécanisme de pagination, l'espace d'adressage du programme est découpé en morceaux linéaires de même de taille : la page. 

L'espace de la mémoire physique est lui-même découpé en morceaux linéaires de même taille : la case.

La taille d'une case est égale à la taille d'une page. Dans ce contexte, charger un programme en mémoire centrale consiste à placer les pages dans n'importe quelle case disponible.

Fig 6 : Principe de la pagination

L'espace d'adressage du processus étant découpé en pages, les adresses générées dans cet espace d'adressage sont des adresses paginées, c'est-à-dire qu'un octet est repéré par son emplacement relativement au début de la page à laquelle il appartient. L'adresse d'un octet est donc formé par le couple <n°de page à laquelle appartient l'octet, déplacement relativement au début de cette page >. 

Les octets dans la mémoire physique eux ne peuvent être adressés au niveau matériel que par leur adresse physique. Pour toute opération concernant la mémoire, il faut donc convertir l'adresse paginée générée au niveau du processeur en une adresse physique équivalente. L'adresse physique d'un octet s'obtient à partir de son adresse virtuelle en remplaçant le numéro de page de l'adresse virtuelle par l'adresse physique d'implantation de la case contenant la page et en ajoutant à cette adresse physique d'implantation le déplacement de l'octet dans la page. C'est la MMU (Memory Management Unit) qui est chargée de faire cette conversion. Il faut donc savoir pour toute page, dans quelle case de la mémoire centrale celle-ci a été placée : cette correspondance s'effectue grâce à une structure particulière appelée la table de pages. Dans une première approche, la table des pages est une table contenant autant d'entrées que de pages dans l'espace d'adressage d'un processus. Chaque processus a sa propre table des pages. Chaque entrée de la table est un couple < n°de page, n°de case physique dans laquelle la page est chargée >. Dans l'exemple de la figure ci-dessous, le processus a 4 pages dans son espace d'adressage, donc la table des pages a 4 entrées. Chaque entrée établit l'équivalence n°de page, n°de case relativement au schéma de la mémoire centrale.

Fig 7 : Table des pages

Puisque chaque processus dispose de sa propre table des pages, chaque opération de commutation de contexte se traduit également par un changement de table des pages, de manière à ce que la "table active" corresponde à celle du processus élu. Deux approches existent pour la réalisation de la table des pages :

Dans la première approche accéder à un emplacement mémoire nécessite seulement un accès à la mémoire : celui nécessaire à la lecture ou l'écriture de l'octet recherché puisque la table des pages est stockée dans des registres du processeur. Dans la deuxième approche accéder à un emplacement mémoire à partir d'une adresse paginée <p,d> nécessite au contraire deux accès à la mémoire : 

Fig 8 : Traduction d'une adresse paginée en adresse physique

Pour accélérer les accès à la mémoire centrale et compenser le coût lié à la pagination, un cache associatif est placé en amont de la mémoire centrale. Ce cache associatif contient les couples <n°de page, adresse d'implantation de la case> les plus récemment accédés. Lorsque la MMU doit effectuer une conversion d'adresse paginée, elle cherche tout d'abord dans le cache si la correspondance n°de page, adresse d'implantation de la case recherchée n'est pas dans le cache. Si non, elle accède à la table des pages en mémoire centrale et place le nouveau couple référencé dans le cache. Si oui, elle effectue directement la conversion : un seul accès mémoire est alors nécessaire pour accéder à l'octet recherché.

Fig 9 : Traduction d'une adresse paginée en adresse physique avec ajout d'un cache associatif

La pagination constitue un découpage de l'espace d'adressage du processus qui ne correspond pas à l'image que le programmeur a de son programme. Pour le programmeur, un programme est généralement constitué des données manipulées par ce programme, d'un programme principal, de procédures séparées et d'une pile d'exécution. La segmentation est un découpage de l'espace d'adressage qui cherche à conserver cette vue du programmeur. Ainsi, lors de la compilation, le compilateur associe un segment à chaque morceau du programme compilé. Un segment est un ensemble d'emplacements mémoire consécutifs non sécable. A la différence des pages, les segments d'un même espace d'adressage peuvent être de taille différente. D''une manière générale, on trouvera un segment de code, un segment de données et un segment de pile.

D'une manière similaire à ce qui se passe avec la pagination, la segmentation de l'espace d'adressage d'un processus génère des adresses segmentées, c'est-à-dire qu'un octet est repéré par son emplacement relativement au début du segment auquel il appartient. L'adresse d'un octet est donc formé par le couple <n°de segment à laquelle appartient l'octet, déplacement relativement au début du segment >.  Pour toute opération concernant la mémoire, il faut ici encore convertir l'adresse segmentée générée au niveau du processeur en une adresse physique équivalente. L'adresse physique d'un octet s'obtient à partir de son adresse segmentée en remplaçant le numéro de segment de l'adresse segmentée par l'adresse physique d'implantation du segment en mémoire centrale et en ajoutant à cette adresse physique d'implantation, le déplacement de l'octet dans le segment. C'est la MMU (Memory Management Unit) qui est chargée de faire cette conversion. Il faut donc connaitre pour tout segment, l'adresse d'implantation dans la mémoire centrale du segment : cette correspondance s'effectue grâce à une structure particulière appelée la table des segments .

Fig 10 : Table des segments

Dans une première approche, la table des segments est une table contenant autant d'entrées que de segments dans l'espace d'adressage d'un processus. Chaque entrée de la table est un couple < n°de segment, adresse d'implantation du segment >. Ici le processus a 4 segments dans son espace d'adressage, donc la table des segments a 4 entrées. Chaque entrée établit l'équivalence n°de segment, adresse d'implantation du segment relativement au schéma de la mémoire centrale.

Plus précisément la conversion d'une adresse segmentée <s,d> avec s, numéro de segment et d déplacement dans le segment suit les étapes suivantes, en mettant en jeu un registre processeur qui contient en partie haute, le nombre maximal de segments de l'espace d'adressage couramment actif (LT) et en partie basse l'adresse de la table des segments de l'espace d'adressage couramment actif.

Fig 11 : Traduction d'une adresse segmentée en adresse physique

L'allocation des segments en mémoire centrale s'effectue selon le même principe que pour l'allocation de partitions variables. Pour allouer un segment de taille S, il faut trouver une zone libre dont la taille soit au moins égale à la taille du segment S. Elle engendre les mêmes problèmes de fragmentation . Une solution, très largement répandue, est de combiner pagination et segmentation, c'est-à-dire de paginer les segments.

Dans la cas où pagination et segmentation sont simultanément employées, une table des segments est définie pour chaque segment de l'espace d'adressage du processus. Chaque segment est à son tour paginé, il existe donc une table des pages pour chaque segment. Ainsi une entrée de la table des segment ne contient plus l'adresse du segment correspondant en mémoire physique mais contient l'adresse de la table des pages en mémoire physique pour ce segment. L'adresse d'un octet dans l'espace d'adressage du processus est un couple <s,d>, le déplacement d étant à son tour interprété comme un couple numéro de page p, déplacement d' dans cette page. Les mécanismes de traduction d'adresses vus dans les paragraphes précédents se superposent l'un à l'autre. 

Fig 12 : Traduction d'une adresse segmentée et paginée en adresse physique