description du processus de pagination sur la memoire

Publié le par stephane-alexi

 

DESCRIPTION DU PROCESSUS DE PAGINATION SUR LA MÉMOIRE

 

 

 


pour utiliser un ordinateur en programmation multiple, les système d'exploitation charge plusieurs processus en mémoire centrale . Pour bien gérer cet ensembles de processus il serait préférable d'affecter à chaque processus une adresse. Lorsque le nombre de tâches devient élevé pour satisfaire l'équitabilité et minimiser le temps de réponse de chaque processus , il faut pouvoir simuler la présence simultanée en mémoire centrale de tous les processus . D'où la technique de « »va et vient » ou recouvrement (swapping) qui consiste à stocker sur disque de façon temporaire l'image d'un processus , enfin de libérer la place de la mémoire pour d'autres processus . D'autre part la taille d'un processus doit pouvoir dépasser la taille de la mémoire disponible . L'utilisation de pagination et des segments permetent au système de conserver en mémoire centrale les parties utilisées des processus et de stocker sur disque le reste des parties. Ainsi le gestionnaire de la mémoire doit reconnaître les parties occupées et les parties libres , d'allouer de la mémoire les processus qui ont besoin de récupérer de la mémoire à la fin de l'exécution d'un processus et de traiter le recouvrement entre le disque et la mémoire centrale lorsqu'elle ne peut pas contenir tous les processus actifs


 

I- GESTION SANS RÉCOUVREMENT NI PAGINATION


 

A- La mono programmation


Ici en mémoire centrale il y a un processus utilisateur. Cette technique n'autorise qu'un seul processus actif en mémoire en un instant donné


 

B- La multiprogrammation


Elle permet de diviser un programme en plusieurs processus et à plusieurs utilisateurs, de travailler en temps partagé avec la même machine . Ainsi on a intérêt d'augmenter la taille de la mémoire centrale . A cet effet on peut diviser la mémoire centrale en n parties fixes detaillées , pas nécessairement égale

On a deux méthodes de gestion:

 

  • on crée une file d'attente par partition . Chaque nouveau processus est placé sur une file d'attente de la plus petite partition pouvant le contenir

Mais ici on perd en général de la place au sein de chaque partition et il peut y avoir des partitions inutilisées et leur file d'attente est vide

 

  • on crée une seule file d'attente globale et pour cela on a deux stratégies :
    dès qu'une partition se libère on lui affecte la première tâche de la file qui peut y tenir

    Ici on peut y affecter une partition de grande taille à une petite tâche , on perd beaucoup de places
    Dès qu'une partition se libère on lui affecte la plus grande tâche de la file qui peut y tenir

Ici on pénalise les processus de petites taille

 

II- GESTION AVEC RECOUVREMENT SANS PAGINATION


  Dès que le nombre de processus devient supérieur au nombre de partitions il faut pouvoir simuler la présence en mémoire centrale de tous les processus pour pouvoir satisfaire au principe d'équité et minimiser le temps de réponse des processus . La technique du recouvrement ou swapping permet de stocker temporairement sur disque les images des processus enfin de libérer de la mémoire pour d'autres processus .On utilise les partitions de taille variable car le nombre la taille et la position des processus peuvent varier dynamiquement au cour du temps


 

A- opérations sur la mémoire


le compactage de la mémoire permet de regrouper les espaces inutilisés . S'il y a une requête d'allocation dynamique de la mémoire pour un processus on lui alloue de la place dans le tas si le système d'exploitation le permet . Quand il n' y a plus de place , on déplace un ou plusieurs processus : soit pour récupérer par ce moyen des espaces inutilisés, soit en allant jusqu'au recouvrement

Il y a trois manières de mémoriser l'occupation de la mémoire : les tables des bits , les listes chaînées et les subdivisions


 

A- 1- la gestion de la mémoire par table des bits


   On divise la mémoire centrale en unités d'allocations de chaque octet à quelques Ko . A chaque unité , correspond un bit de la table de bit : valeur 0 si l'unité est libre , 1 sinon . Cette table est stockée en mémoire centrale . Plus la table moyenne des unités est faible , plus la table occupe la place

 

  •  

  • A-2 -Gestion de la mémoire par liste chaînée


  • On utilise une liste chaînée des zones libres en MC. On applique :

  • - soit le first fit , soit le best fit ou meilleur ajustement , soit le worst fit ou le plus grand residu

  • - soit un algorithme de placement rapide (quick fit ) : on crée des listes séparées pour chacune des tailles les plus courantes, et la recherche est considérablement accélérée. A l'achèvement d'un processus ou à son transfert sur disque, il faut du temps (mise à jour des liste chaînées) pour examiner si un regroupement avec ses voisins est possible pour éviter une fragmentation excessive de la mémoire.

  • En résumé, les listes chaînées sont une solution plus rapide que la précédente pour l'allocation, mais plus lente pour la libération.


  •  

  • A-3-Gestion de la mémoire par subdivision


  •  

  • On utilise l'existence d'adresses binaires pour accélérer la fusion des zones libres adjacentes lors de la libération d'unités. Le gestionnaire mémorise une liste de blocs libres dont la taille est une puissance de 2 ( 1, 2, 4, 8 octets, ...., jusqu'à la taille maximale de la mémoire). L'allocation et la libération des blocs sont très simples. Mais un processus de taille 2n + 1 octets utilisera un bloc de 2n+1 octets ! Il y a beaucoup de perte de place en mémoire.

  •  

  • Dans certains systèmes, on n'alloue pas une place fixe sur disque aux processus qui sont en mémoire.On les loge dans un espace de va et vient (swap area ) du disque. Les algorithmes précédents sont utilisés pour l'affectation


  •  

  • III- GESTION AVEC RECOUVREMENT AVEC PAGINATION OU SEGMENTATION

 La taille d'un processus doit pouvoir dépasser la taille de la mémoire physique disponible, même si l'on enlève tous les autres processus. Ainsi le principe de la mémoire virtuelle est utilisé par le système d'exploitation pour palier à certains problèmes posés par la gestion avec récouvrement ,avec pagination . Il conserve en mémoire centrale les parties utilisées des processus et stocke, si nécessaire, le reste sur disque. Mémoire virtuelle et multiprogrammation se complètent bien : un processus en attente d'une ressource n'est plus conservé en MC, si cela s'avère nécessaire. La mémoire virtuelle fait appel à deux mécanismes : segmentation ou pagination. La mémoire est divisée en segments ou pages. Sans recours à la mémoire virtuelle, un processus est entièrement chargé à des adresses contiguës ; avec le recours à la mémoire virtuelle, un processus peut être chargé dans des pages ou des segments non contigus.
  •  

  •  

  •  

  • A - La pagination


  • L'espace d'adressage d'un processus est divisé en petites unités de taille fixe appelées pages. La MC est elle aussi découpée en unités physiques de même taille appelées cadres. Les échanges entre MC et disques ne portent que sur des pages entières. De ce fait, l'espace d'adressage d'un processus est potentiellement illimité (limité à l'espace mémoire total de la machine). On parle alors d'adressage virtuel . Pour un processus, le système ne chargera que les pages utilisées. Mais la demande de pages à charger peut être plus élevée que le nombre de cadres disponibles. Une gestion de l'allocation des cadres libres est nécessaire. Dans un SE sans mémoire virtuelle, la machine calcule les adresses physiques en ajoutant le contenu d'un registre de base aux adresses relatives contenues dans les instructions du processus. Dans un SE à pagination, un sous-ensemble inséré entre l'UC et la MC, la MMU (Memory Management Unit ou unité de gestion de la mémoire) traduit les adresses virtuelles en adresses physiques. La MMU mémorise :

  • - les cadres physiques alloués à des processus (sous forme d'une table de bits de présence)

  • - les cadres mémoire alloués à chaque page d'un processus (sous forme d'une table des pages )

  • On dira qu'une page est mappée ou chargée si elle est physiquement présente en mémoire.

 

 

  • B - La segmentation


  • Dans cette solution, l'espace d'adressage d'un processus est divisé en segments, générés à la compilation. Chaque segment est repéré par son numéro S et sa longueur variable L. Un segment est un ensemble d'adresses virtuelles contiguës. Contrairement à la pagination, la segmentation est "connue" du processus : une adresse n'est plus donnée de façon absolue par rapport au début de l'adressage virtuel; une adresse est donnée par un couple (S , d), où S est le n° du segment et d le déplacement dans le segment, d ∈ [0 , L [ . Pour calculer l'adresse physique, on utilise une table des segments :

  •  

  • B – 1- La pagination segmentée


  • Lorsque le système possède beaucoup de pages, la consultation de la table des pages peut être lente et inefficace s'il y a beaucoup de pages non chargées. On la segmente alors par processus. Chaque processus possède une table des segments de la table des pages qui le concernent. Une adresse (P , r) , avec P n° logique de page et r déplacement dans la page, est transformée à la compilation en adresse (S , P' , r), avec S n° d'un segment et P' .

  •  

  • B-2- La segmentation paginée


  • La taille d'un segment peut être importante, d'où un temps de chargement long qui peut en résulter. La pagination des segments peut être une solution. Une adresse virtuelle (S , d), avec S n° de segment et d déplacement dans le segment, est transformée en (S , P , d' ), où P est un n° de page et d' un déplacement dans la page P.


  •  

  • IV- ALGORITHMES DE REMPLACEMENT DE PAGES


  • Les méthodes reposent sur 3 stratégies :

  • - une stratégie de chargement qui choisit les pages à charger et l'instant de chargement

  • - une stratégie de placement qui choisit un cadre libre pour chaque page à charger

  • - une stratégie de remplacement destinée à libérer certains cadres. La recherche se fait soit sur l'ensemble des pages (recherche globale), soit sur les pages "appartenant" au processus (recherche locale). Les stratégies de placement sont dépendantes des stratégies de remplacement : on charge nécessairement une page dans le cadre qui vient d'être libéré. On peut distinguer deux catégories de méthodes :

  • - pagination anticipée : on charge les pages à l'avance

  • - pagination à la demande : le chargement n'a lieu qu'en cas de défaut de page et on ne charge que la page manquante.


  •  

  • A - Remplacement de page optimal


  • Le SE indexe chaque page par le nombre d'instructions qui seront exécutées avant qu'elle ne soit référencée. En cas de nécessité, le SE retire la page d'indice le plus élevé, c'est à dire la page qui sera référencée dans le futur le plus lointain . Ceci est pratiquement impossible à appliquer . Toutefois, avec un simulateur, on peut évaluer les performances de cet algorithme et s'en servir comme référence pour les suivants.

  •  

  • B - not recently used


  • Le SE référence chaque page par deux bits R (le plus à gauche) et M initialisés à 0. A chaque accès en lecture à une page, R est mis à 1. A chaque accès en écriture, M est mis à 1. A chaque interruption d'horloge, le SE remet R à 0. Les bits R-M forment le code d'un index de valeur 0 à 3 en base 10. En cas de défaut de page, on retire une page au hasard dans la catégorie non vide de plus petit index. On retire donc préférentiellement une page modifiée non référencée (index 1) qu'une page très utilisée en consultation (index 2).

  •  

  • C - FIFO ( first in, first out)


  • Le SE indexe chaque page par sa date de chargement et constitue une liste chaînée, la première page de la liste étant la plus anciennement chargée et la dernière la plus récemment chargée. Le SE replacera en cas de nécessité la page en tête de la liste et chargera la nouvelle page en fin de liste. Deux critiques s'imposent

  • - ce n'est pas parce qu'une page est la plus ancienne en mémoire qu'elle est celle dont on se sert le moins

  • Ici le processus n'est pas stable : quand le nombre de cadres augmente, le nombre de défauts de pages ne diminue pas nécessairement . Ainsi le SE examine les bits R et M de la page la plus ancienne en MC (en tête de la liste). Si cette page est de catégorie 0, il l'ôte. Sinon, il teste la page un peu moins ancienne, etc... S'il n'y a aucune page de catégorie 0, il recommence avec la catégorie 1, puis éventuellement avec les catégories 2 et 3.

  •  

  • Pour le second procédé le SE examine le bit R de la page la plus ancienne (tête de la liste). Si R = 0, la page est remplacée, sinon R est mis à 0, la page est placée en fin de liste et on recommence avec la nouvelle page en tête. Si toutes les pages ont été référencées depuis la dernière fois on revient à FIFO,


  •  

  • D - LRU (least recently used)


  • En cas de nécessité, le SE retire la page la moins récemment référencée. Pour cela, il indexe chaque page par le temps écoulé depuis sa dernière référence et il constitue une liste chaînée des pages par ordre décroissant de temps depuis la dernière référence.


  •  

  •  

  •  

  • E- Améliorations


  • Dès qu'un seuil minimal de cadres libres est atteint, le SE réveille un dérobeur de pages . Celui-ci supprime les pages les moins récemment utilisées, par le procédé et les range dans la liste des cadres libres, ceci jusqu'à un seuil donné. Le SE vérifie qu'une page référencée sur défaut de page n'est pas dans la liste. Lorsque plusieurs processus exécutent le même ensemble de code, on a intérêt à utiliser des pages de code partagées, plutôt que des pages dupliquées. Mais on aura à prévoir une gestion spécifique des pages partagées pour éviter des défauts de pages artificiels.

  •  

  • F- Taille optimale des pages


  • Soit t la taille moyenne des processus et p (en octets) la taille d'une page. Soit e (en octets) la taille de l'entrée de chaque page dans la table des processus. Le nombre moyen de pages par processus est t/p.


  •  

  • G - Le modèle du Working Set


  • Le modèle working-set de comportement d'un programme est un procédé proposé par des informaticiens pour comprendre les performances d'un système paginé en  multi-programmation. . Dans le cas d'un système mono-processeur, le nombre de processus présents en mémoire augmente, l'utilisation du processeur augmente . Toutefois, si le degré de multi-programmation franchit un certain seuil, il en résulte une forte croissance du trafic de pagination entre disques et mémoire centrale, accompagnée d'une diminution brusque de l'utilisation du processeur. Le haut degré de multi-programmation empêche chaque processus de garder suffisamment de pages en mémoire pour éviter un grand nombre de défauts de pages. Le canal de liaison avec le disque arrive à saturation et beaucoup de processus sont bloqués par attente de transfert de pages. On parle de thrashing (déconfiture) du processeur. En d'autres termes, chaque processus exige un nombre minimal de pages présentes en mémoire centrale (appelé son working-set) pour pouvoir réellement utiliser le processeur. Le degré de multi-programmation doit être tel que le working-set de tous les processus présents en mémoire doit être respecté .

  •  

  • V- PARTAGE DE CODE ET DONNEES EN MEMOIRE CENTRALE


  •  

  • Des procédures peuvent être partagées entre plusieurs processus. On a intérêt à ce qu'il n'y ait qu'une copie du code qui sera exécutée par chaque processus avec ses propres données. Par exemple deux processus P1 et P2 sont susceptibles d'utiliser une procédure R. On ne peut pas prévoir l'ordre dans lequel ils vont entrer dans R ou sortir de R. Si l'un des deux processus est désalloué pendant qu'il exécute R et qu'il voit ses variables locales modifiées par l'exécution de R par l'autre processus, alors on dit que R n'est pas ré-entrante.

  •  

  • A - Cas de la pagination


  • Le partage du code et des données se fait par un double référencement aux pages contenant les informations communes.

  •  

  • A-1 Partage du code


  • Chaque fois qu'un processus fait référence à son propre code, il utilise un numéro de page fixe qui le fait accéder toujours à la même page virtuelle. Donc, si un processus partage son code, il va toujours référencer la même page virtuelle, quelle que soit la table des pages utilisée. Chaque tâche doit donc mettre le code exécutable de ce processus à la même adresse virtuelle.


  • A-2 Partage de données


  • Pour partager des données, la zone commune peut être à des endroits différents dans la table des pages de chacune des tâches. Soit une page commune P contenant un pointeur q :

  • - si D pointe sur une adresse dans P, le numéro de cette page doit être le même dans tous les processus

  • - si l'objet pointé n'est pas dans P, alors il doit avoir la même adresse virtuelle dans tous les processus

  •  

  • B- Cas de la segmentation


  • Pour que deux processus référencent une partie commune, il suffit que cette partie se trouve dans un segment qui possède le même descripteur dans la table des segments de chacun des processus.

 

 

 

sources d'inspiration document de YVES PAGNOTTE Systeme d'exploitation et programmation systeme

 


 

I

Commenter cet article