Skip to main content

Allocation

Le système d'exploitation, les processus systèmes et utilisateurs se trouvent dans la mémoire, il faut donc un mécanisme de protection pour isoler les processus. Ce mécanisme c'est le MMU vu plus tôt.

Mono-programmation

Lorsqu'un seul processus s'exécute à la fois en même temps que le système d'exploitation. C'est le cas sur les systèmes très rudimentaires comme MS-DOS.

Etant donné qu'il n'y a qu'un seul processus à la fois, le système d'exploitation n'a pas beaucoup à faire car il n'y a pas besoin d'isoler la mémoire (sauf pour la petite partie réservée au système d'exploitation).

Le BIOS rélise une gestion des périphériques.

Multi-programmation

Partitions fixes

On peut pré-découper la mémoire en morceaux de taille variable (les partitions). On va donc tenter de placer chaque processus dans la plus petite partition qui peut la contenir.

L'un des problème de ce système est qu'il va y avoir beaucoup de restes (fragmentation interne) car si un a besoin de 4 unité mais que la seul partition que l'on peut prendre en contient 8, on a 4 unités non-utilisées.

Partitions variables

On alloue l'espace selon les besoins des processus, on va créer des partitions en fonction des demandes faites par les processus.

Table de bits

La table de bits correspond à une cartographie de la mémoire découpe en blocs d'allocations de taille fixe. Pour chaque bloc on va noter un 1 si c'est occupé, ou un 0 si le bloc est libre dans la table de bits.

Ainsi il suffit de seulement stoquer 1 bit par unité d'allocation. Cependant le problème est que si les unités d'allocations sont petits, alors il la table sera grande mais ce sera plus précis.

A l'inverse si les unités d'allocations sont grande, la table sera plus petite mais sera moins précise (ce qui implique donc un plus grand gaspillage de mémoire).

Un autre problème est que plus la taille est grande, moins l'allocation sera rapide car il faudra parcourir toute la table jusqu'a trouver le segment d'unités libre recherché.

Liste chainée

Une autre méthode correspond à conserver une liste chainée des partitions mémoire. Cette liste est généralement triée suivant les addresses des partitions libres, ainsi les partitions qui se suivent dans la mémoire se suivron dans la liste.

Chaque élément de la liste chainée n'a alors qu'a stoqué 4 informations : si le bloc est libre ou pas, la position du début de la partition, la longueur de la partition et le lien avec la partition suivante. Par exemple P86 signifie qu'il y a un processus sur la partition en position 8 d'une longueur de 6 unités.

Ce qui implique également de facilité la fusion de blocs libre, si un proramme libère une partition, cette partition pourra être facilement fusionnée avec les éventuelles partitoins libres adjacentes pour former une partition plus grande.

L'avantage est de rendre l'allocation beaucoup plus rapide, le désavantage est que cela crée de la fragmentation.

Pour en savoir plus, vous pouvez regarder sur ce site.

Choix de la partition

Lorsque l'on recherche la partition de mémoire qui pourra accueillir un programme, il y plusieurs algorithmes possibles.

  • L'algorithme first-fit qui correspond à prendre la première partition libre trouvée étant suffisament grande pour contenir le programme. C'est souvent cette algorithme qui est utilisé car il est très rapide.
  • L'algorithme best-fit qui correspond à parcourir toute la mémoire à la recherche de la meilleure partition. Cependant cette méthode est assez peu efficace et crée beaucoup de fragmentation externe en créant des bouts de partitions trop petites pour être utilisées
  • L'algorithme worst-fit qui correspond à de nouveau parcourir toute la mémoire mais cette fois-ci à la recherche de la plus grande zone disponible afin d'éviter de créer trop de fragmentation externe comme le best-fit. Cet algorithme est particulièrement rapide pour les listes triées par taille.

Fragmentations

  • La fragmentation interne survient lorsque la mémoire est divisée en unité d'allocation de taille fixe.
  • La fragmentation externe survient suite aux allocations et libérations successives, la mémoire ressemble donc à un gruyère.

Solutions à la fragmentation

Le compactage qui consiste à rassembler les zones mémoires occupées ensemble et les zones libre ensemble. Cependant cela est couteux en ressource.

La pagination permet d'avoir un espace addressage en mémoire physique non contigu. Elle va avoir une "table des pages" pour savoir où sont les morceaux. Cette méthode est utilisée par tous les sytèmes d'exploitations actuels.

Fonctionnement

On va donc diviser la mémoire logique en blocs de taille fixe (les pages), on va faire de même avec la mémoire physique (que l'on va appeller les frames)

L'espace de stockage pour le swapping est également découpé en blocs de même taille que les frames.

Ainsi une page correspond à une frame. Ainsi la table des pages va lier chaque page à une frame. La fragmentation externe avec la pagination n'existe donc plus. La fragmentation interne est limitée à 1/2 page par processus en moyenne. La taille en nombre de page est examinée, si il y a suffisament de frames disponibles, le processus démarre. Sinon le processus ne peut pas démarrer car il n'y a pas assez d'espace disponible. La mémoire est donc vue par le programme comme étant contigue.

Les frames

Les frames sont gérées par le système d'exploitation. Le SE va garder la liste des frames libres et occupées et le nombre de frames disponibles.

Le SE doit mettre en place une protection pour empécher un processus de dépasser son espace d'adressage (isolation de la mémoire des processus).