Chapitre 2 & 3

INTRODUCTION  Afin que système gère plusieurs programmes (processus), et les exécuter dans les meilleurs délais possibles en partageant le temps processeur.  Une meilleure gestion du PC est nécessaire.  Pour cela, un programme du SE s’occupe de gérer l’utilisation ou l’allocation du proc...

INTRODUCTION  Afin que système gère plusieurs programmes (processus), et les exécuter dans les meilleurs délais possibles en partageant le temps processeur.  Une meilleure gestion du PC est nécessaire.  Pour cela, un programme du SE s’occupe de gérer l’utilisation ou l’allocation du processeur aux différents programmes : c’est le Scheduler.  La gestion du processeur central se base principalement sur l’organisation ou stratégie qui permet l’allocation du processeur aux différents programmes qui existent dans la machine. BELUERCHE & ZEBBANE 1 FILES D’ATTENTE DE SCHEDULING  Tout processus passe, durant sa vie, par les files suivantes :  Initialement, tout processus est inséré dans une file d’attente de travaux (job queue) avant son chargement en MC.  Quand le processus devient résidant en MC et il est prêt à s’exécuter, il est inséré (son PCB)dans une liste appelée la file d’attente des processus prêts (Ready queue).  Le processus reste dans la file Prêt jusqu’à ce qu’il soit sélectionné pour son exécution par le Scheduler. Une fois que le PC lui est alloué, le processus devient Actif.  Etant actif, le processus pourrait émettre une demande d’E/S vers un périphérique particulier. Il est alors placé (son PCB) dans la file d’attente du périphérique (Device queues). Chaque périphérique possède sa propre file d’attente.  Enfin, le processus actif pourrait créer lui-même un nouveau sous-processus (appelé processus fils) et attendre sa fin. BELUERCHE & ZEBBANE 2 FILES D’ATTENTE DE SCHEDULING File d’attente UC de proc. prêts E/S File d’attente d’E/S Requête d’E/S Tranche de temps expirée Le fils Le fils Création d’un fils termine s’exécute L’interruption En attente d’une se produit interruption BELUERCHE & ZEBBANE 3 CONCEPT DE SCHEDULING Définition  On appelle « Scheduling » du processeur l’organisation ou la politique d’allocation du processeur central aux programmes.  On appelle «Scheduler » la partie du SE qui s’occupe de cette organisation et répartit le temps processeur entre ces programmes. BELUERCHE & ZEBBANE 4  CONCEPT DE SCHEDULING Critères de performance de scheduling  Utilisation de l’UC (CPU utilization) – utiliser la CPU le maximum possible.  Débit (Throughput) – nombre de processus qui terminent leur exécution par unité de temps.  Temps de rotation (Turnaround time) – le temps depuis le lancement du processus jusqu’à sa terminaison (les attentes incluses).  Temps de réponse (Response time) – le temps depuis le chargement du processus en Mc jusqu’à sa terminaison (les attentes incluses).  Temps d’attente (Waiting time) – temps d’un processus dans les files d’attente des processus prêts et bloqués.  Equité (Fairness) – le Scheduler doit servir les programmes de même priorité d’une manière juste et équitable. 5 BELUERCHE & ZEBBANE  CONCEPT DE SCHEDULING Scheduling avec ou sans préemption  Une politique de Scheduling est non préemptive Libération volontaire du PC  Une fois le PC est alloué à un programme, celui-ci le gardera jusqu’à la fin de son exécution, ou demande d’une autre ressource.  Exemple: Mode multiprogrammé  Une politique de Scheduling est préemptive Libération non volontaire du PC  Une fois le PC est alloué à un programme, le système pourra le restituer et l’allouer à un autre programme selon certaines conditions. 6  Exemple: Mode Temps partagé. BELUERCHE & ZEBBANE  CONCEPT DE SCHEDULING Priorité de scheduling  L’allocation du processeur central aux programmes peut se faire suivant certaines valeurs de priorité, qui son affectées aux programmes automatiquement par le système de Scheduling, ou bien de manière externe par les utilisateurs  Deux types de priorités :  Priorité statique : une fois qu’elle est attribuée à un programme, elle ne changera jamais.  Priorité dynamique : la priorité affectée à un programme change en fonction de l’environnement d’exécution du programme. 7 BELUERCHE & ZEBBANE POLITIQUES DE SCHEDULING Politiques de scheduling Préemptives Non Préemptives Sans Sans Avec Priorité Avec Priorité Priorité Priorité 8 BELUERCHE & ZEBBANE  POLITIQUES DE SCHEDULING Politique « Premier Arrivé Premier Servi » (FCFS, First Come First Served- FIFO)  Politique non préemptive  La file des processus prêts est triée selon l’ordre d’arrivée. 9 BELUERCHE & ZEBBANE  POLITIQUES DE SCHEDULING Politique du Premier Arrivé Premier Servi (FCFS ou FIFO)  Exemple Processus Durée Date Date début Date fin Temps de Temps d’exe d’arrivée d’exe d’exe réponse d’attente A 3 0 0 3 3 0 B 6 1 3 9 8 2 C 4 4 9 13 9 5 D 2 6 13 15 9 7 E 1 7 15 16 9 8 Temps de réponse moyen (3+8+9+9+9)/5 = 7.6 ut 10 BELUERCHE & Temps d’attente moyen (0+2+5+7+8)/5 = 4.6 ut ZEBBANE  POLITIQUES DE SCHEDULING Politique du Premier Arrivé Premier Servi (FCFS ou FIFO)  Diagramme d’exécution arrivée de A arrivée de B arrivée de C arrivée de D arrivée de E A A A B B B B B B C C C C D D E CPU 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 T(ut) FP A B C C C D D E 11 BELUERCHE & ZEBBANE  POLITIQUES DE SCHEDULING Politique du Job le Plus Court d’Abord (SJF, Shortest Job First)  Politique non préemptive  La file des processus prêts est triée dans l’ordre croissant selon la durée d’exécution. 12 BELUERCHE & ZEBBANE  POLITIQUES DE SCHEDULING Politique du Job le Plus Court d’Abord (SJF)  Exemple Processus Durée Date Date début Date fin Temps de Temps d’exe d’arrivée d’exe d’exe réponse d’attente A 3 0 0 3 3 0 B 6 1 3 9 8 2 C 4 4 12 16 12 8 D 2 6 10 12 6 4 E 1 7 9 10 3 2 Temps de réponse moyen (3+8+12+6+3)/5 = 6.4 ut 13 BELUERCHE & ZEBBANE Temps d’attente moyen (0+2+8+4+2)/5 = 3.2 ut  POLITIQUES DE SCHEDULING Politique du Job le Plus Court d’Abord (SJF)  Diagramme d’exécution arrivée de B arrivée de C arrivée de D arrivée de E arrivée de A A A A B B B B B B E D D C C C C CPU 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 T(ut) FP A B C D E C D C 14 BELUERCHE & ZEBBANE  POLITIQUES DE SCHEDULING Politique du Job ayant le Plus Court Temps Restant (SRTF, Shortest Remaining Time First)  Politique préemptive  Une variante du SJF  La file des processus prêts est triée dans l’ordre croissant selon la durée d’exécution. 15 BELUERCHE & ZEBBANE  POLITIQUES DE SCHEDULING Politique du Job ayant le Plus Court Temps Restant (SRTF)  Exemple Processus Durée Date Date Préempté Repris à Date fin Temps de Temps d’exe d’arrivée début à d’exe réponse d’attente d’exe A 3 0 0 - - 3 3 0 B 6 1 3 4 11 16 15 9 C 4 4 4 - - 8 4 0 D 2 6 9 - - 11 5 3 E 1 7 8 - - 9 2 1 Temps de réponse moyen (3+15+4+5+2)/5 = 5.8 ut Temps d’attente moyen (0+9+0+3+1)/5 = 2.6 ut 16 Nbre BELUERCHE & de changements de Ctxt 6 ZEBBANE  POLITIQUES DE SCHEDULING Politique du Job ayant le Plus Court Temps Restant (SRTF)  Diagramme d’exécution arrivée de B arrivée de C arrivée de D arrivée de E arrivée de A A A A B C C C C E D D B B B B B CPU 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 T(ut) FP A B B(5) D E B(5) D B(5) 17 BELUERCHE & ZEBBANE  POLITIQUES DE SCHEDULING Politique du Tourniquet (Round Robin, RR)  Politique préemptive  Consiste à allouer le processeur aux processus suivant une durée d’exécution limitée appelée « Quantum »  La file des processus prêts est triée selon l’ordre d’arrivée.  La gestion de la file Fp est circulaire. 18 BELUERCHE & ZEBBANE  POLITIQUES DE SCHEDULING Politique du Tourniquet (Round Robin, RR)  Exemple Q=2ut Processus Durée Date Date Préempté Repris à Date fin Temps de Temps d’exe d’arrivée début à d’exe réponse d’attente d’exe A 3 0 0 2 4 5 5 2 B 6 1 2 4 7 16 15 9 9 14 C 4 4 5 7 12 14 10 6 D 2 6 9 - - 11 5 3 E 1 7 11 - - 12 5 4 19 BELUERCHE & ZEBBANE  POLITIQUES DE SCHEDULING Politique du Tourniquet (Round Robin, RR)  Exemple (suite) Temps de réponse moyen (5+15+10+5+5)/5 = 8 ut Temps d’attente moyen (2+9+6+3+4)/5= 4.8ut Nbre de changements de Ctxt 9 20 BELUERCHE & ZEBBANE  POLITIQUES DE SCHEDULING Politique du Tourniquet (Round Robin, RR)  Diagramme d’exécution (Q=2ut) arrivée de B arrivée de C arrivée de D arrivée de E arrivée de A A A B B A C C B B D D E C C B B CPU 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 T(ut) FP A B C B D B D E C 21 BELUERCHE & ZEBBANE  POLITIQUE À PLUSIEURS NIVEAUX DE QUEUES (MULTI-LEVEL QUEUES)  La file des processus prêts est subdivisée en plusieurs files.  Chaque file est gérée par une politique de Scheduling propre à elle.  Deux types de Politiques multi_niveaux  Files multi_niveaux indépendantes  Files multi_niveaux dépendantes  Cette politique est définie par les paramètres suivants :  Nombre de files.  L’algorithme de Scheduling de chaque file.  Une méthode déterminant dans quelle file placer un nouveau processus. 22 BELUERCHE & ZEBBANE  Une méthode de transition d’un processus d’une file à une autre (pour les files dépendantes).  POLITIQUE À PLUSIEURS NIVEAUX DE QUEUES (MULTI-LEVEL QUEUES) Files multi_niveaux indépendantes  Les processus sont divisés en classes selon leurs types. Arrivée Niveau 1 Processus de la classe 1  Chaque file est associée à une classe de Niveau 2 processus. Arrivée Processus de la classe 2  Un processus ne peut jamais changer de file PC durant son exécution. Arrivée Niveau n Processus de la classe n  Chaque file est gérée par une politique de Scheduling qui s’adapte mieux à la classe des processus qu’elle contient.  Exemple:  Processus batch FCFS. 23 BELUERCHE &  Processus interactifs Round Robin. ZEBBANE  POLITIQUE À PLUSIEURS NIVEAUX DE QUEUES (MULTI-LEVEL QUEUES) Files multi_niveaux dépendantes  Tous les processus arrivent, initialement, dans la même file. Arrivée Niveau 1 Processus  Un processus peut changer de file durant son exécution. Niveau 2 Processus PC  C’est un moyen pour augmenter ou baisser la priorité d’un processus. Niveau n Processus  Chaque file est gérée par une politique de Scheduling. 24 BELUERCHE & ZEBBANE  POLITIQUE À PLUSIEURS NIVEAUX DE QUEUES (MULTI-LEVEL QUEUES) Files multi_niveaux dépendantes  Exemple:  Soient Trois files:  F0 – gérée par la politique RR avec un quantum de 8 ms. RR, Quantum = 8 ms  F1 – gérée par la politique RR avec un quantum de 16 ms.  F2 – gérée par la politique FCFS. RR, Quantum = 16 ms  La politique de scheduling appliquée est décrite comme suit :  Initialement, chaque nouveau processus est placé dans F0. FCFS  Tout processus qui ne termine pas son exécution après avoir consommé son quantum (8ms), il sera replacé dans F1.  Si un processus de la file F1 est servi (16 m) et ne se termine pas, il est replacé dans F2. 25 BELUERCHE & ZEBBANE  La file F0 est plus prioritaire que F1 et qui plus prioritaire que F2 CHAPITRE V : GESTION DE LA MC BELUERCHE & ZEBBANE 26 INTRODUCTION  La mémoire est une ressource importante de stockage de données et de programmes qui doit être gérée avec prudence.  La gestion de la mémoire est du ressort du gestionnaire de la mémoire.  Le rôle du gestionnaire de la mémoire est  de connaître les parties libres et occupées,  d'allouer de la mémoire aux processus qui en ont besoin,  de récupérer de la mémoire à la fin de l'exécution d'un processus  et de traiter le recouvrement (va-et-vient (Swapping)) entre le disque et la mémoire centrale, lorsqu'elle ne peut pas contenir tous les processus actifs. BELUERCHE & ZEBBANE 27 TYPES DE MÉMOIRE 1 ns  Mémoire Volatile Registres Cache Niveau 1 Mémoire  Registres Volatile 5 ns Cache Niveau 2  Mémoires caches Vitesse d’accès 50 ns Mémoire Centrale (RAM) Coût  Mémoire Centrale 5 ms Mémoires Secondaire (Disque Dur) Mémoire  Mémoire Permanentes Permanente Mémoire Tertiaire 5s Archivage (Bandes magnétiques)  Mémoire secondaire Capacité de stockage BELUERCHE & ZEBBANE 28 MÉMOIRE CENTRALE Définition  Le terme mémoire désigne un composant destiné à contenir une certaine quantité de données, et à en permettre la consultation.  La mémoire centrale, dite aussi la mémoire vive (Random Access Memory, RAM), est un ensemble de mots mémoires où chaque mot a sa propre adresse. L'octet représente la plus petite quantité de mémoire adressable.  Deux types d’opérations peuvent s’effectuer sur les mots mémoires :  Lecture (Read)  Ecriture (Write) BELUERCHE & ZEBBANE 29 MÉMOIRE CENTRALE Objectifs du gestionnaire de la MC  Le gestionnaire de la mémoire est un module du système d’exploitation dont le rôle est la gestion de la mémoire principale (RAM).  Le but d’une bonne gestion de la mémoire est d’augmenter le rendement global du système.  Le gestionnaire de la mémoire doit viser les objectifs suivants :  La réallocation ou la réorganisation des programmes en mémoires.  Le partage  La protection  Organisation logique BELUERCHE & ZEBBANE 30 MÉMOIRE CENTRALE Objectifs du gestionnaire de la MC  Exemple de Réallocation 0 0 0 P1 P1 P1 50 50 50 P2 P2 100 P2 150 150 Réallocation Chargement P4 De P2 De P4 200 300 300 300 P3 P3 P3 400 400 400 BELUERCHE & ZEBBANE 31 CARACTÉRISTIQUES LIÉES AU CHARGEMENT D’UN PROGRAMME N o y a u (S o u s- Espace d'adressage (utilisateur/noyau) S y stè m e s ) K e rn e l D onnées N oyau  L'espace d'adressage est divisé en deux (02) (P C B s , P a g e s lib r e s ,...e t c.) parties : P ile  L’espace utilisateur : Images des processus utilisateurs (codes et variables). Tas  L'espace noyau : toutes les structures de U ser BSS données gérées par le système (PCB, liste de D onnées pages libres,…), y compris le noyau lui-même. C ode BELUERCHE & ZEBBANE 32 CARACTÉRISTIQUES LIÉES AU CHARGEMENT D’UN PROGRAMME Représentation des adresses d’un objet  Il existe plusieurs types d’adressages :  Adresses symboliques qui représentent les noms des objets contenus dans le code source.  Par exemple, int n.  Adresses logiques qui correspondent à la traduction des adresses symboliques lors de la phase de compilation.  Par exemple, le 50ème mot depuis le début d'espace mémoire.  Adresses physiques qui représentent l’emplacement physique des adresses logiques d’un programme lors de son exécution.  La traduction des adresses logiques en adresses physiques est assurée par l’unité de traduction d’adresses (MMU, Memory Management Unit).  Par exemple, l'emplacement mémoire situé à l'adresse FFF7. BELUERCHE & ZEBBANE 33 CARACTÉRISTIQUES LIÉES AU CHARGEMENT D’UN PROGRAMME Espace d'adressage logique versus physique  L'unité centrale manipule des adresses logiques (emplacement relatif).  L'espace d'adressage logique (virtuel) est donc un ensemble d'adresses pouvant être générées par un programme.  L'unité mémoire manipule des adresses physiques (emplacement mémoire).  L'espace d'adressage physique est un ensemble d'adresses physiques correspondant à un espace d'adresses logiques.  La conversion, au moment de l’exécution, des adresses logiques à des adresses physiques est effectuée par l’unité de gestion mémoire (MMU) qui est un dispositif matériel. BELUERCHE & ZEBBANE 34 CARACTÉRISTIQUES LIÉES AU CHARGEMENT D’UN PROGRAMME Espace d'adressage logique versus physique  Dans le schéma MMU, la valeur du registre de translation est additionnée à chaque adresse générée par un processus utilisateur au moment où elle est envoyée à la mémoire. R egistre d e T ran slatio n 14000 A d resse A d re sse L o g iq u e P h y siq u e C PU + M é m o ire 346 143 46 MMU BELUERCHE & ZEBBANE 35 STRATÉGIES D’ALLOCATIONS Stratégies d’allocations Contiguës Mémoire Non Contiguës Virtuelle Mono Partitions Segmentation Bloc Multiples Pagination Segmentation paginée Partitions Partitions fixes BELUERCHE & ZEBBANE variables 36 STRATÉGIES D’ALLOCATIONS : ALLOCATION CONTIGUËS Mono Bloc 0K Adresses basses  La MC est subdivisée en deux partitions contiguës: Système d’Exploitation  Une pour le système d’exploitation 400K  L’autre pour le processus utilisateur.  Un seul processus est autorisé en mémoire à un instant donné. Espace Utilisateur  Avantage : la gestion de la mémoire est simple.  Inconvénient : 2300K  La sous utilisation de la mémoire  La possibilité de ne pouvoir exécuter des programmes de grande 25600K Adresses hautes taille. 37 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION CONTIGUËS Début Mono Bloc  L’algorithme d’allocation Taille Pgme > Oui Chargement Taille Zone Impossible User No n Charger Pgme Exécuter Pgme Libérer Espace Mémoire 38 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION CONTIGUËS Partitions Multiples  Cette stratégie constitue une technique simple pour la mise en œuvre de la multiprogrammation.  La mémoire principale est divisée en régions séparées ou partitions mémoires.  Chaque partition dispose de son espace d’adressage.  Chaque processus est chargé entièrement en mémoire dans une seule partition.  Le partitionnement de la mémoire peut être :  Statique (fixe).  Tailles égales  Tailles inégales.  Dynamique (variable). 39 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION CONTIGUËS 0M 0M 8M 8M 8M 8M Base de Taille de Statut de 2M 10M partition Partition Partition 8M 4M 14M Partitions Multiples : Partitions Fixes 16M 6M 0M 8M Allouée 8M 20M 8M 2M Libre  Cette solution consiste à diviser la mémoire en 24M 8M 10M 4M Allouée partitions fixes, de tailles pas nécessairement 8M 28M 14M 6M Allouée égales, à l’initialisation du système. 32M 8M 20M 8M Allouée 8M 36M 28M 8M Libre  Le système d’exploitation maintient une table de 40M 36M 12M Allouée 12M description des partitions (PDT, Partition 8M 48M 16M Libre Description Table) indiquant les parties de 48M 48M mémoire disponibles (hole) et celles qui sont 8M 56M 16M occupées. 8M 64M 64M Partitions de tailles Partitions de tailles égales inégales 40 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION CONTIGUËS Système d’Exploitation Partitions Multiples : Partitions Fixes de tailles inégales Partition1  Algorithme de placement Partition2  Utilisation de plusieurs files  Chaque nouveau processus est placé dans la file d’attente de la plus petite partition qui peut le contenir. Partition3  Avantage : Efficace seulement si les Files d’attente ont un nombre similaire de programmes.  Inconvénient: il peut y avoir des partitions inutilisées (leurs files Partition4 d'attente sont vides) 41 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION CONTIGUËS Partitions Multiples : Partitions Fixes de tailles inégales Système d’Exploitation  Algorithme de placement Partition1  Utilisation d’une seule file globale Partition2  Il existe différentes stratégies d’attribution d’une partition libre à un processus en attente :  A la libération d’une partition, chercher le premier processus de la file Partition3 qui peut être loger.  Inconvénient: perte d’espace mémoire si le processus est de petite taille. Partition4  A la libération d’une partition, chercher le plus grand processus de la file qui peut être loger.  Inconvénient: les processus de petite taille sont pénalisés. 42 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION CONTIGUËS Partitions Multiples : Partitions Fixes  Avantage  Possibilité de charger plusieurs programmes en MC.  Inconvénients  La possibilité de ne pouvoir exécuter des programmes de grande taille.  Fragmentation interne de la mémoire:  Espace mémoire interne à une partition mais n’est pas utilisé (espace perdu).  Arrive lorsque la mémoire allouée est plus grande que la mémoire requise. 43 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION CONTIGUËS Exemple Partitions Multiples : Partitions Variables Soit une mémoire de 256K dont 40K sont occupés par le système d’exploitation. Soit cinq programmes P1, P2, P3, P4 et  La mémoire est découpée dynamiquement, P5 dont la taille est 60K, 100K, 30K, 70K et 44K suivant la demande. respectivement.  A chaque programme est allouée une partition exactement égale à sa taille. 0K 0K 0K 0K 0K SE SE SE SE SE 40K 40K 40K 40K 40K  Quand un programme termine son exécution, sa P1 P1 P1 P5 84K partition est récupérée par le système pour être 100K 100K 100K 100K 100K allouée à un autre programme complètement ou P2 P4 P4 P4 partiellement selon la demande. 170K 170K 170K 200K 200K 200K 200K 200K 230K P3 230K P3 230K P3 230K P3 230K P3  Le système d’exploitation maintient une table 256K 256K 256K 256K 256K des espaces disponibles. Terminaison Allocation Terminaison Allocation 44 BELUERCHE & ZEBBANE de P2 de P4 de P1 de P5 STRATÉGIES D’ALLOCATIONS : ALLOCATION CONTIGUËS Partitions Multiples : Partitions Variables  Algorithmes de placement (Allocation d’espace pour un nouveau programme)  First-fit (le premier trouvé) : Chercher, à partir du début de la mémoire, le premier espace libre qui peut le contenir.  Next-fit (le prochain trouvé) : Cet algorithme est une variante du précédent où la recherche d’un espace libre commence à partir du dernier bloc alloué.  Best-fit (le meilleur choix) : Chercher le plus petit espace libre qui peut le contenir.  Worst-fit (le plus mauvais choix) : Chercher le plus grand espace libre qui peut le contenir. 45 BELUERCHE & ZEBBANE  STRATÉGIES D’ALLOCATIONS : ALLOCATION CONTIGUËS 8K 8K 12 K 12 K Partitions Multiples : Partitions Variables F irst-fit B lo c allo u é  Algorithmes de placement: 22 K 6K B lo c lib re  Exemple d’allocation d’un bloc de 16K en utilisant lesD e rn ie r B e st-fit 18 K différents algorithmes de placement. b lo c allo u é 2K 6K 6K 14 K 14 K N e xt-fit W o rst-fit 36 K 20 K 46 BELUERCHE & ZEBBANE A v an t A p rès STRATÉGIES D’ALLOCATIONS : ALLOCATION CONTIGUËS Partitions Multiples : Partitions Variables  Avantage  Possibilité de charger plusieurs programmes en MC.  Pas de fragmentation interne de la mémoire.  Inconvénients  La possibilité de ne pouvoir exécuter des programmes de grande taille.  Fragmentation externe de la mémoire:  Espace mémoire total suffisant pour faire loger un programme mais n’est pas contigu.  La mémoire est fragmentée en un grand nombre de petits trous ( blocs libres) où un programme ne peut être chargé dans aucun de ces trous. 47 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION CONTIGUËS Partitions Multiples : Partitions Variables  Solutions à la fragmentation externe de la mémoire 0K 0K SE SE  Solution 1 : Le compactage = La réallocation = 40K 40K P5 Compaction Défragmentation P5 84K 84K 100K  Permet de regrouper les espaces inutilisés (les blocs libres) en P4 P4 un seul espace mémoire(contigu). 154K 170K P3  Le compactage entraîne un déplacement des programmes ce 184K 200K qui nécessite un changement d'adresse pour les programmes 230K P3 déplacés. 256K 256K  Très coûteuse en temps CPU. 48 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION CONTIGUËS Partitions Multiples : Partitions Variables  Solutions à la fragmentation externe de la mémoire  Solution 2 : Avoir une stratégie qui permet d’exploiter les trous sans faire recours au compactage. Stratégies d’allocation non contigües 49 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATION Stratégies d’allocation Contiguës Mémoire Non Contiguës Virtuelle Mono Partitions Segmentation Bloc Multiples Pagination Segmentation paginée Partitions Partitions fixes variables 50 Fragmentation BELUERCHE & ZEBBANE Fragmentation interne externe STRATÉGIES D’ALLOCATIONS : ALLOCATION NON CONTIGUËS 0 Pagination : Principe 1 Page 0 0  L’espace d’adressage logique du programme est découpé en petits blocs Page 0 2 de même taille appelés pages. 1000 0 1 1 4  L’espace de la mémoire physique est découpé en blocs de taille fixe Page 1 2 3 3 Page 2 appelés cases ou cadres de page (Frame Page) 2000 3 7 Page 2 4 Page 1  La taille d’une case est égale à la taille d’une page. 3000 Table de pages Page 3 5  Les pages logiques d’un processus peuvent donc être assignées aux cadres disponibles n’importe où en mémoire principale. Mémoire 6 Logique  Utilisation d’une table de pages pour localiser les pages d’un processus en mémoire. Elle contient l’adresse de base de chaque page 7 Page 3 dans la mémoire physique. 51 BELUERCHE & ZEBBANE Mémoire Physique STRATÉGIES D’ALLOCATIONS : ALLOCATION NON CONTIGUËS Pagination : Schéma de translation d’adresses  On divise chaque adresse (logique) générée par l’UC en deux parties : Adresse Adresse  Un numéro de page (p, Page Number) qui est utilisé comme un Logique Physique index dans la table des pages afin de récupérer l’adresse de base en Mémoire UC p d f d mémoire physique. Physique  Un déplacement dans la page (d, Page Offset) qui est combiné à l’adresse de base de la page pour définir l’adresse mémoire physique qui p sera envoyée à l’unité mémoire. f  Si T est la taille d’une page et U une adresse logique, alors l’adresse paginée (p,d) est déduite à partir des formules suivantes :  p = U Div T (où, Div est la division entière) Table de pages  d = U Mod T (où, Mod est le reste de la division) 52 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION NON CONTIGUËS Pagination : Schéma de translation d’adresses  Exemple: N° page N° frame  Soit la table des pages suivante d’un processus. 0 4  Calculer les adresses physiques correspondant aux adresses logiques suivantes: 1 6 73, 246, 300, sachant que la taille d’une page est de 100 octets. 2 7  @physique = @base(Frame) + déplacement 3 11  73  (0, 73)  @physique = @base(4) + 73  246  (2, 46)  @physique = @base(7) + 46  300  (3, 0)  @physique = @base(11) + 0 53 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION NON CONTIGUËS Pagination : Discussion  Avantage  Possibilité de charger plusieurs programmes en MC dans un espace non contigu.  Inconvénients  La possibilité de ne pouvoir exécuter des programmes de grande taille (le nombre de pages dépasse le nombre de frames).  Fragmentation interne de la mémoire peut se produire si la dernière page de l’espace d’adressage logique n’est pas pleine. 54 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION NON CONTIGUËS Segmentation : Principe  La segmentation est une stratégie de gestion mémoire qui reproduit le découpage mémoire tel qu’il est décrit logiquement par l’usager. Pile Programme  Chaque unité logique d’un programme usager est stockée dans un bloc principal mémoire, appelé segment à l’intérieur duquel les adresses sont relatives au début du segment.  Un segment est un ensemble d'adresses logiques contiguës. Sous- programe Data  Les segments sont de tailles différentes. Un programme sera donc constitué d’un ensemble de segments de code et de données, pouvant être dispersés en MC.  Utilisation d’une table de segments pour localiser les segments d’un processus en mémoire. Elle contient l’adresse de base de chaque 55 BELUERCHE & ZEBBANE segment dans la mémoire physique.  STRATÉGIES D’ALLOCATIONS : ALLOCATION NON CONTIGUËS Segmentation : Schéma de translation d’adresses s  Chaque segment est repéré par son numéro S et sa longueur variable L. limite base  Une adresse logique est donnée par un couple (S, d), où S est le numéro du segment et d le déplacement dans le Table de segment. CPU s d Segments  Chaque entrée de la table de segments possède, pour chaque segment, les informations suivantes : < oui +  Base contient l’adresse physique de début où le segment réside en mémoire. non  Limite spécifie la longueur du segment.  Le déplacement d dans le segment doit être compris entre Déroutement; erreur d’adressage 56 Mémoire physique 0 et la limite du segment (d  [0, L [ ) BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION NON CONTIGUËS Segmentation : Schéma de translation d’adresses N° Base Limite  Exemple: segment 0 1100 500  Soit la table des segments suivante d’un processus. 1 2500 1000  Calculer les adresses physiques correspondant aux adresses logiques suivantes: , , , , 2 200 600  Si d [0, Limite[  @physique = Base+ déplacement 3 4000 1200 Adresse logique Adresse physique 300 < 500  @physique = 1100 + 300 = 1400 800 > 600  Erreur d’adressage 600 < 1000  @physique = 2500 + 600 = 3100 1100 < 1200  @physique = 4000 + 1100 = 5100 57 BELUERCHE & ZEBBANE 1111 > 1000  Erreur d’adressage STRATÉGIES D’ALLOCATIONS : ALLOCATION NON CONTIGUËS Segmentation : Discussion  Avantage  Possibilité de charger plusieurs programmes en MC dans un espace non contigu.  Inconvénients  La possibilité de ne pouvoir exécuter des programmes de grande taille.  Fragmentation externe de la mémoire peut se produire le fait que les segments non pas la taille. 58 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : ALLOCATION NON CONTIGUËS Segmentation Paginée : Principe  La segmentation paginée permet d’éliminer la fragmentation externe de la mémoire.  Les programmes sont divisés en segments et chaque segment est divisé en pages de tailles égales  A chaque processus, on associe une table de segments et des tables de pages.  Chaque adresse de base d’un segment est une adresse de base d’une table de pages.  Une adresse logique (S, D), avec S numéro de segment et D déplacement dans le segment, est transformée en (S, p, d), où p est un numéro de page et d un déplacement dans la page p.  Chaque adresse devient alors un triplet (S, p, d). 59 BELUERCHE & ZEBBANE  STRATÉGIES D’ALLOCATIONS : ALLOCATION NON CONTIGUËS Adresse logique oui CPU S D D p d non Longueur Base de la Segmentation Paginée : Schéma de + du segment table de pages translation d’adresses Déroutement STBR Table de Segments + f f d Adresse physique 60 BELUERCHE & ZEBBANE Mémoire physique Table de pages pour le segment S STRATÉGIES D’ALLOCATIONS : ALLOCATION NON CONTIGUËS Segmentation paginée : Discussion  Avantage  Possibilité de charger plusieurs programmes en MC dans un espace non contigu.  Inconvénients  La possibilité de ne pouvoir exécuter des programmes de grande taille.  Fragmentation interne de la mémoire peut se produire si la dernière page de chaque segment n’est pas pleine. 61 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATION Stratégies d’allocation Contiguës Mémoire Non Contiguës Virtuelle Mono Partitions Segmentation Bloc Multiples Pagination Segmentation paginée Fragmentation Fragmentation Fragmentation Partitions Partitions interne externe interne fixes variables 62 Fragmentation BELUERCHE & ZEBBANE Fragmentation interne externe STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE  La mémoire virtuelle (Virtual Memory) est une technique qui permet l’exécution des processus qui ne peuvent pas être dans leur totalité en MC.  La mémoire virtuelle permet l’exécution de processus dont la taille est beaucoup plus grande que la taille de la mémoire physique.  Un processus est donc constitué de morceaux (pages ou segments) ne nécessitant pas d’être tous en MC durant l’exécution.  Seulement les morceaux qui sont en exécution sont chargés en MC.  Les autres morceaux peuvent être sur mémoire secondaire, prêts à être amenés en MC sur demande.  La mémoire virtuelle est une extension à la mémoire centrale  MV = MC +espace sur disque appelé (swap). 63 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Page 0  La mémoire virtuelle se base sur la technique de pagination Page 1 Page 2 ou segmentation paginée et elle est implémentée avec la pagination à la demande  La capacité d’exécuter un processus se trouvant partiellement en mémoire présenterait plusieurs avantages :...  La taille d’un programme n’est plus limitée par la taille de la Mémoire de map mémoire physique.  Comme chaque programme utilisateur pourrait occuper Disque moins de mémoire physique, il serait possible d’exécuter plus Page n Mémoire physique de programmes en même temps. Mémoire virtuelle 64 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Pagination à la demande : Principe  La pagination à la demande est semblable à un système de 0 1 2 3 Swap out pagination avec va-et-vient (swapping). Programme A 4 5 6 7  Les pages des processus ne sont chargées en MC que lorsque le processeur demande à y accéder. 8 9 10 11 Programme 12 13 14 15 Swap in B 16 17 18 19 1) Comment le processeur puisse distinguer entre les pages Disque qui sont en mémoire, et celles qui sont sur disque? MC 2) Que se passe-t-il si le processeur essaye d’utiliser une page qui n’est pas chargée en mémoire ? 65 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE 0 1 Cadre de Bit de 2 1) Comment distinguer entre les pages qui sont en page validité 3 mémoire, et celles qui sont sur disque ? 0 A 0 4 v 4 A 1 B 5 1 i  Chaque entrée de la table des pages comporte un champ 2 C 2 6 v 6 C A B supplémentaire, le bit validation V : 3 D 3 i 7 4 E 4 i 8 C D E  Il est à Valide (càd; 1) si la page est effectivement présente en 5 F 5 9 v 9 F MC. 6 G 6 i 10 F G H 7 i  Il est à Invalide (càd; 0) si la page n’est pas encore chargée en 7 H Table de pages 11 Mémoire 12 MC. logique 13  Il est initialisé à Invalide pour toutes les entrées de la table. 14 Disque 15 Mémoire physique 66 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE 1. Déterminer si la référence mémoire est valide. si l’adresse ne se trouve pas dans l’espace d’adressage, il s’agit d’une erreur 2) Que se passe-t-il si le processeur essaye d’adressage. d’utiliser une page qui n’est pas chargée en 2. S’il s’agit d’une référence valide mais la page n’est pas encore mémoire ? chargée en mémoire, on doit la charger.  L’accès à une page marquée invalide provoque un 3. Trouver un frame libre pour charger la page manquante. déroutement ou un défaut de page. 4. Lancer une opération d’E/S pour lire la page manquante à partir de l’unité de swapping.  La procédure permettant de manipuler un défaut de page est la suivante : 5. Mise-à-jour de la table de pages. 6. Redémarrer l’instruction interrompue, le processus peut alors accéder à la page. 67 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Page dans l’unité 3 de swapping SE 2 Page Déroutement référencée 1 Les étapes de traitement d’un défaut de Charge M i page 6 Redémarre l’instruction Frame libre 5 4 Mise-à-jour de la table de pages Charge en mémoire la page absente Programme 68 BELUERCHE & ZEBBANE Mémoire Physique STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Cadre de Exemple: page Bit de validité 0 H 0 3 v 1 Charge M 0 SE 1 4 v 2 J 1 SE B 2 5 v 3 M 3 i 2 D Mémoire Table de pages 3 H logique P1 4 Charge M P1 5 J M 6 A 0 A 0 6 v 7 E 1 B 1 i Mémoire Disque 2 2 v physique 2 D 3 7 v 3 E Table de pages Mémoire P2 logique P2 69 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE 3) Que se passe-t-il si il n’existe pas de frame 1. Trouver l’emplacement de la page désirée sur le disque (unité de swapping). libre ? 2. Trouver un frame libre :  S'il n'y a pas de cadres libres en mémoire, une autre page doit être retirée de la mémoire et la A. S’il existe, l’utiliser. remplacer par celle demandée  B. Sinon, utiliser un algorithme de remplacement de remplacement de page pages pour sélectionner un page victime.  La page retirée de la mémoire est dite page 3. Recopier la page victime sur le disque et mettre à jour la victime. table de pages.  La procédure de traitement d’un défaut de page, 4. Charger la page désirée dans le frame récemment libéré et avec prise en compte de remplacement de page mettre à jour la table de pages. est le suivant : 5. Redémarrer le processus interrompu. 70 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Les étapes de traitement d’un défaut de page avec remplacement de pages 71 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages  Ils sont conçus dans l’objectif de minimiser le taux de défaut de pages à long terme.  L’évaluation de ces algorithmes s’effectue en comptant sur une même séquence de références mémoires, le nombre de défauts de pages provoqués.  Cette séquence est appelée chaîne de références et elle est définie par la séquence des numéros de pages référencées successivement au cours de l’exécution d’un processus.  Afin de déterminer le nombre de défauts de pages pour une chaîne de références et un algorithme de remplacement, on a besoin de connaître le nombre de frames disponibles.  Le nombre de défauts de pages dépend du nombre de frames disponibles et du critère utilisé par l’algorithme de remplacement de pages afin de choisir la page victime. 72 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages Exemple  Soit une mémoire paginée dont la taille d’une page est de 100 octets. L’exécution d’un processus fait référence aux adresses logiques suivantes : 100, 432, 101, 612, 102, 103, 101, 611, 102, 103, 104, 610, 102, 103, 104, 101, 609, 102, 105 (1,0), (4,32), (1,1), (6,12), (1,2), (1,3), (1,1), (6,11), (1,2), (1,3), (1,4), (6,10), (1,2), (1,3), (1,4), (1,1), (6,9), (1,2), (1,5)  La chaine de références est : 1, 4, 1, 6, 1, 1, 1, 6, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1  La chaîne de références réduite est : 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1 73 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages Exemple (suite)  Pour la chaine de références « 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1 », le nombre de défauts de pages est :  Avec 3 frames  3 défauts de pages CR 1 4 1 6 1 6 1 6 1 6 1 Frame1 1 1 1 1 1 1 1 1 1 1 1 Frame2 4 4 4 4 4 4 4 4 4 4 Frame3 6 6 6 6 6 6 6 6 Défaut D D D de pages 74 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages Exemple (suite)  Pour la chaine de références « 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1 », le nombre de défauts de pages est :  Avec 2 frames  4 défauts de pages ou CR 1 4 1 6 1 6 1 6 1 6 1 Frame1 1 1 1 6 6 6 6 6 6 6 6 Frame2 4 4 4 1 1 1 1 1 1 1 Défaut D D D D de pages 75 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages Exemple (suite)  Pour la chaine de références « 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1 », le nombre de défauts de pages est :  Avec 2 frames  3 défauts de pages ou CR 1 4 1 6 1 6 1 6 1 6 1 Frame1 1 1 1 1 1 1 1 1 1 1 1 Frame2 4 4 6 6 6 6 6 6 6 6 Défaut D D D de pages 76 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages Exemple (suite)  Pour la chaine de références « 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1 », le nombre de défauts de pages est :  Avec 2 frames  5 défauts de pages ou CR 1 4 1 6 1 6 1 6 1 6 1 Frame1 1 1 1 6 1 1 6 6 6 6 6 Frame2 4 4 4 4 6 1 1 1 1 1 Défaut D D D D D de pages 77 BELUERCHE & ZEBBANE  STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages 1) FIFO  Critère : Ancienneté de la page  Cet algorithme mémorise dans une file FIFO les pages présentes en mémoire  Exemple: CR 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 F1 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7 F2 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0 F3 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1 DP D D D D D D D D D D D D D D D Taux de défauts de pages = Nombre de DP / Taille (CR) = 15/20 * 100 = 75% 78 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages FIFO : Discussion  L’algorithme FIFO est simple à mettre en œuvre.  Il ne tient pas compte de l'utilisation de chaque page.  L'algorithme est rarement utilisé car il génère beaucoup de défauts de pages. Avoir plus de frames pour avoir moins de défauts de pages 79 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages FIFO : Anomalie de Belady (Belady’s Anomaly)  Belady a montré par un contre-exemple que l’algorithme FIFO donne plus de défauts de pages avec l’accroissement du nombre de frames.  Ceci est connu sous le nom de l’anomalie de Belady. 80 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages Anomalie de Belady (Belady’s Anomaly) : Exemple  Application de FIFO sur la chaine suivante : « 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 »  Cas 1 : 3 frames CR 1 2 3 4 1 2 5 1 2 3 4 5 Frame1 1 1 1 4 4 4 5 5 5 5 5 5 Frame2 2 2 2 1 1 1 1 1 3 3 3 Frame3 3 3 3 2 2 2 2 2 4 4 DP D D D D D D D D D Nombre de défauts de pages = 9 81 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages Anomalie de Belady (Belady’s Anomaly) : Exemple  Application de FIFO sur la chaine suivante : « 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 »  Cas 2 : 4 frames CR 1 2 3 4 1 2 5 1 2 3 4 5 Frame1 1 1 1 1 1 1 5 5 5 5 4 4 Frame2 2 2 2 2 2 2 1 1 1 1 5 Frame3 3 3 3 3 3 3 2 2 2 2 Frame4 4 4 4 4 4 4 3 3 3 DP D D D D D D D D D D Nombre de défauts de pages = 10 82 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages 2) Optimal  Critère : Référence de la page dans le future  Les pages chargées en mémoire sont triées selon leurs prochaines dates de références.  Il retire la page pour laquelle la prochaine référence est la plus éloignée dans le temps.  Exemple: CR 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 F1 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 F2 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 F3 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 DP D D D D D D D D D Taux de défauts de pages = 9/20 * 100 = 45% 83 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages Optimal : Discussion  L’algorithme Optimal donne le meilleur taux de défauts de pages.  Cette stratégie est impossible à mettre en œuvre car il est difficile de prévoir les références futures d'un programme. Le remplacement de page optimal a été utilisé comme base de référence pour les autres stratégies 84 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages 3) LRU (Least Recently Used)  Critère : Référence de la page dans passé = Ancienneté dans la référence  Les pages chargées en mémoire sont triées selon leurs dernières dates de références.  Il retire la page la moins récemment utilisée.  Exemple: CR 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 F1 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1 F2 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 F3 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7 DP D D D D D D D D D D D D Taux de défauts de pages = 12 / 20 *100 = 60% 85 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages LRU : Discussion  L’algorithme LRU diminue le taux de défauts de pages.  Problème : la difficulté d'implémentation, qui requiert un support matériel.  Il faut mémoriser le temps à chaque fois qu'une page est référencée  Opération très couteuse. 86 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages 4) Seconde chance = Algorithme de l’Horloge A  Critère : Ancienneté dans la référence + Ancienneté dans le L B R=0 …... chargement K C  Chaque page possède un bit de référence Bit_R.  Bit_R = 1  la page est récemment référencée par le PC.  Bit_R = 0  la page n’a pas été référencée depuis un certain temps. J D  La page plus ancienne (selon FIFO) est pointée par un indicateur P.  Les pages en mémoire sont mémorisées dans une liste circulaire en I E forme d'horloge. H F  La page victime est celle qui possède un Bit_R =0. G 87 BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages 4) Seconde chance : Fonctionnement  Lorsqu’un défaut de pages se produit et il n’existe pas de frame libre, l’algorithme de remplacement de pages, seconde chance, est lancé. A. La page pointée par l'indicateur est examinée: B. Si P.Bit_R = 0 Alors // page victime trouvée 1) Retirer la page victime de la MC 2) Charger la page demandée à sa place et faire avancer l’indicateur d’une position (càd. P:= P.Svt) 3) Mettre à jours la table des pages 4) Redémarrer le processus interrompu Sinon 1) P.Bit_R := 0 // Donner une seconde chance à cette page 2) P:= P.Svt 88 BELUERCHE & ZEBBANE 3) Goto B STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Liste circulaire Liste circulaire Liste circulaire de pages de pages de pages Algorithmes de remplacement de pages R R R 0 3 0 3 0 3 4) Seconde chance : Fonctionnement 0 8 0 8 0 8  Exemple Page la plus ancienne 1 2 0 2 0 2 Référence à la page 4 qui n’existe pas en MC 1 5 0 5 0 5 Page 0 9 victime 0 9 1 4 Page la plus 1 7 1 7 ancienne 1 7 1 6 1 6 1 6 Bits de Bits de Bits de référence référence référence 89 Etape de recherche Etape de remplacement BELUERCHE & ZEBBANE STRATÉGIES D’ALLOCATIONS : MÉMOIRE VIRTUELLE Algorithmes de remplacement de pages 4) Seconde chance : Application CR 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 F1 7 7 7 2 2 2 2 4 4 4 4 3 3 3 3 0 0 0 0 0 Bit_R 1 1 10 1 1 1 10 1 1 10 0 1 10 0 0 1 10 0 1 1 F2 0 0 0 0 0 0 0 2 2 2 2 2 1 1 1 1 7 7 7 1 10 0 10 0 10 0 1 10 0 0 10 1 1 1 10 1 1 1 Bit_R F3 1 1 1 3 3 3 3 3 0 0 0 0 2 2 2 2 2 1 10 0 0 1 10 0 0 10 1 1 10 0 1 1 10 0 0 1 Bit_R DP D D D D D D D D D D D D D D Taux de défauts de pages = 14 / 20 * 100 = 70% 90 BELUERCHE & ZEBBANE