Home

Isabelle Puaut Septembre 2011

1. p P Disque V prot pr ex cutable pr prot V 1 rx L rxil V prot pr P L a gt u g A rx r prot V 1 irx 1irx rx 1 1 rw rw l Table des pages text Table des pages text V prot pr _ T H pr prot V Table des livres Tir F irw Table des livres TE 83W M moire physique Table des pages data Table des pages data Tables de traduction processus P Tables de traduction processus fork Un peu mieux partage du code Filesystem Swap V prot pr ex cutable pF 1 rx T irx a V prot DA H pr prot V 1 rx 1 lrxll TX 1 rw Tw Table des pages text V prot pr TU H pr prot V Table des livres Ha F Hi Table des livres 2 m Fi M moire physique Table des pages data Table des pages data Tables de traduction processus P Tables de traduction processus fork Beaucoup mieux copy on write Partage des pages tant que non modifi es Protection contre l criture bits de protection Marquage des pages comme tant copy on write Duplication paresseuse la premi re criture Juste apr s le fork 62 Filesystem Swap p P Disque V prot pr rx V prot pr Pi Vx pr prot V
2. Fichier C 10 m 3 m 13 12 D 0 1 OA Hi RS D FREE EOF EOF FREE BAD N FREE bloc libre EOF dernier bloc d un fichier BAD bloc d fectueux Autre bloc suivant dans le fichier ound UW r fami un 72 1 2 Mise en uvre des acc s Structuration logique des informations suite de caract res de structures etc en g n ral non structur Fonctions d acc s logiques acc s direct acc s s quentiel acc s index Entr es sorties physiques par blocs de taille fixe Un des r les du SGF mettre en uvre les E S logiques en utilisant les E S physiques Mise en uvre des acc s Structures de donn es Table d implantation du fichier informations de mise en uvre du fichier taille organisation logique Informations permanentes Charg es en m moire l ouverture pour acc l rer l acc s au fichier Exemple inode Unix FAT MS DOS Bloc de contr le d entr e sortie descripteur file handle informations li es par les acc s en cours prochain article lire pour les fichiers acc s s quentiel tampons d entr e sortie Dur e de vie dur e d ouverture d un fichier En g n ral une copie par processus ayant ouvert le fichier Mise en uvre des acc s Cache disque Unit de transfert bloc G r enti rement par logiciel Int r t Tout acc
3. gt pr v pr sente cache de table des ME PV traduction TLB gt pages a d faut de page pv non pv non pr sente E trouv e Unit de gestion m moire MMU Exemple 18 Soit un syst me avec un temps d acc s la m moire hors pagination de 100 ns un temps d acc s au TLB de 5 ns un descripteur de page virtuelle lu en un cycle m moire un taux de succ s du TLB de 90 Le temps d acc s m moire moyen est de 5 0 1 100 100 115ns contre 200ns sans TLB Caches de traduction et changements de contexte En g n ral les processus poss dent un espace d adressage virtuel priv gt deux processus diff rents peuvent utiliser la m me adresse virtuelle avec un contenu diff rent gt mise jour de la table de traduction courante lors d un changement de contexte gt contenu du TLB incorrect apr s un changement de contexte Solutions Vidage du TLB lors des changements de contexte Ajout d un champ ASID Address Space Identifier dans le TLB pour viter le vidage 31 Architectures avec TLB uniquement Le mat riel de pagination offre uniquement un cache de traduction les structures de donn es pour la fonction de pagination tant alors enti rement g r es par logiciel pv trouv e gt Pr cache de Pv T traduction TLB pv non trouv e Unit de gestion m moire Architectures avec TLB uniquement MIPS
4. Serveur Localisation possible des caches 87 Disque Disque M moire principale O M moire A A Machine Machine cliente serveur R seau Granularit du cache Bloc Plusieurs blocs Fichier complet Taille plus importante taux de pr sence dans le cache lev temps de chargement important probl me de coh rence de cache Politique de recopie Ecriture imm diate Co teux latence bande passante r seau S mantique claire en pr sence de d faillance Ecriture retard e Bonnes performances Quand les fichiers sont d truits rapidement le serveur n en a pas connaissance N autorise qu une coh rence faible S mantique peu d finie en pr sence de d faillance Ecriture la fermeture mise jour du serveur uniquement la fermeture du fichier Bonnes performances Permet de mettre en uvre la coh rence de session Optimisations possibles pour les fichiers de faible dur e de vie Compromis recopies p riodiques Coh rence des caches Coh rence faible Aucun protocole n cessaire Recopie r guli re du cache client peut assurer que les valeurs lues ne seront pas trop anciennes Coh rence de session Aucun protocole n cessaire Seul probl me avoir assez de cache client pour conserver les modifications sur le site client gt cache client sur disque est
5. 5 Limitation de la consommation m moire 5 1 Influence de la taille des pages 5 2 Fonctions de pagination adapt es 6 Gestion m moire et gestion du processeur 7 R implantation 7 1 Adressage par registre de base o oo a a 7 2 Adressage segment 7 3 Segmentation et pagination 16 17 17 18 20 22 22 24 31 31 32 33 36 36 37 42 III Allocation de la m moire par zone 1 Probl mes r soudre 2 Algorithmes d allocation dynamique 2 1 Classes d algorithmes d allocation dynamique 2 27 CBILIMAP res 2 MU DR BA E ME ele D Gr ner A dan that DE e 2 9 Sequential ts i Le is i Aier Les e le racheter N Ra armee Ar soie CR 4 24 Indexed AtS Tatra us arnaud A D Be NE ARTS 2 57 Buddy systems r r d as d N 4 06 ban 46 9 mL en MR RUE dus DVE tn Ba A ied e 48 28 va 3 Ramasse miettes IV Liaison et partage des objets dans un programme 1 Partage d objets 11 D finitions et motivations 1 2 Propri t s attendues d un m canisme de partage 1 3 Partage dans un espace pagin 1 4 Etude de cas partage et fork Unix 2 Edition de liens dynamique un survol 2 1 Edition de liens statique vs dynamique 2 2 Edition de liens d
6. Entr e dans la table de niveau 1 donne acc s une page virtuelle Entr e dans la table de niveau 2 donne acc s un ensemble de pages virtuelles contigu s hyperpage ou livre Revient consid rer que la m moire virtuelle est d coup e en hyperpages elles m mes d coup es en pages Une adresse virtuelle peut tre interpr t e comme un triplet n hyperpage n page d placement Adresses 0 0 0 virtuelles Page 0 de lhyperpage 0 0 1 0 Page 1 de 0 2 10 1 0 l hyperpage 0 hyperpage 0 1 0 0 Page 0 de 1 2 10 1 0 l hyperpage 1 yi hyperpage 1 38 Tables des pages plusieurs niveaux Contenu table des hyperpages table de niveau 2 Chaque entr e hp contient pr sent V bit indiquant si la table des pages de l hyperpage hp est pr sente en m moire physique adphys l adresse physique de d but de cette table des pages si elle est pr sente Remarque 24 Cette table des hyperpages joue le m me r le vis a vis de la table de pages que la table de pages vis a vis de la m moire Tables des pages plusieurs niveaux Interpr tation d une adresse virtuelle Registre de base Adresse virtuelle table des hyperpages hp pv d gt gt Let J m d 1 Table des hyperpages Table des pages Page p de de l hyperpage hp l hyperpage hp Tables des pages
7. acc l ration des acc s m moire etc 3 Autres m canismes permettant la r implantation dynamique 2 1 Adresse virtuelle et adresse physique Adresse virtuelle D coupage de l espace virtuel en pages virtuelles pages logiques de taille fixe Une adresse virtuelle peut tre interpr t e comme un couple n de page virtuelle d placement dans la page Si les pages font 2 octets et s il y a 2 pages virtuelles une adresse virtuelle fait m v bits organis s de la mani re suivante 18 Adresse virtuelle num ro page d placement virtuelle v bits m bits On notera une adresse virtuelle pv d uniquement pour plus de lisibilit en r alit c est une simple suite de bits Remarque 12 L ensemble des pages virtuelles constitue un espace d adressage unique le dernier mot de la page est suivi du premier mot de la page 1 Par exemple si une page fait octets et s il y a pages l adresse a 2 255 est suivie de l emplacement d adresse a 1 3 0 a 000010 11111111 a 1 000011 00000000 Adresse virtuelle exemple Syst me avec pages de 28 256 octets 26 pages Adresses virtuelles 000000 00000000 page 0 000000 11111111 000001 00000000 Adresse virtuelle page 1 3 2 000010 00000000 2 000011 00000010 page 000011 00000010 E NO page 3 M moire virtuelle Adresse physique D coupage de la m moire
8. Espace virtuel de P1 M moire physique Espace virtuel de P2 Cas consid rer R f rence O est une adresse virtuelle directement utilis e par le m canisme de pagination adressage direct R f rence O utilise un adressage calcul qui ne fournira l adresse virtuelle finale qu l ex cution ex adressage bas Adressage direct pour r f rences entre objets 59 10 1 44 10 1 44 Table des pages de P1 Table des pages de P2 Espace virtuel de P1 44 EU Espace virtuel de P2 M moire physique Adressage direct pour r f rences entre objets Interpr tation correcte gt O doit tre la m me adresse virtuelle dans tous les processus gt Partage non modulaire le partage de l objet O n cessite de conna tre les objets utilis s par O N est pas un m canisme de partage g n ral Utilisable dans des cas particuliers partage de code entre processus ex cutant le m me code Adressage calcul pour r f rences entre objets 2 1 44 2 0 15 17 16 1 44 20 1 7 Table des pages de P1 Table des pages de P2 15 0 Le Es Espace virtuel de P1 44 1 Espace virtuel de P2 M moire physique 16 0 B pour P2 O 2 0 B pour P1 0 Adressage calcul pour r f rences entre objets
9. R seau Proc pes Proc Proc LE Proc MPR Abstraction de la m moire virtuelle r partie Mise en oeuvre de la MVP 1 Syst mes de gestion de fichiers r partis Acc s l information distante Non transparent utilisation de commandes r alisant une copie locale avant utilisation ftp rcp etc ftp nom machine get nom fich distant nom fich local quit lt acc s au fichier local gr ce au SGF local gt Transparent m canismes semblables aux acc s fichiers locaux syst me de gestion de fichier r parti ex NFS noyau de noyau de communication communication Liaison Principe d un SGF r parti Stations peuvent tre sp cialis es dans le stockage des fichiers serveurs de fichier Fonction de syst me de gestion de fichiers assure la transparence d acc s en engageant un dialogue avec le serveur de fichiers changes de messages via un noyau de communications 84 Usager SGFR serveur SGFR client SGF i local noyau de noyau de communication communication Messages Site client Site serveur 1 1 Propri t s d un SGF r parti Propri t s d un SGF r parti Transparence la distribution Transparence d acc s toutes les op rations applicables aux
10. Relancer l instruction D faut de page en criture sur page p Site gestionnaire Site propri taire m moire 3 m moire 4 m moire 2 m moire 1 prop 4 copies 2 4 Acc s la page en criture par processeur 1 ite propri taire Site gestionnaire m moire 1 m moire 2 m moire 3 m moire 4 prop 1 copies 1 93 Septi me partie Virtualisation 94 1 D finition et int r t Virtualisation En g n ral Interface ressources Syst me ou composant a Interface ressources Virtualisation Exemples M moire virtuelle virtualisation de la m moire physique Virtual Machines virtualisation de la machine physique JVM Autres jeux d instructions virtualis s CLI Fichier virtualisation du disque Syst me d exploitation virtualisation de la machine physique gt Un concept aussi vieux que l informatique Virtualisation Machines virtuelles Principe de virtualisation appliqu e la machine enti re API Application Programming Interface ABI Application Binary Interface ISA Instruction Set Architecture Classification des machines virtuelles Smith amp Nair 2005 Process based la machine virtuelle ex cute un processus unique abstraction au niveau ABI ou API JVM NET
11. System based fournit un support pour un syst me d exploitation et son ensemble de pro cessus abstraction au niveau ISA Xen KVM VMware VirtualBox Virtualisation Int r ts Abstraction Ajout de fonctionalit s Diff rents services sur une m me machine avec partage des ressources physiques Isolation Spatiale Temporelle Ex cution d applications sur des syst mes architectures plus maintenues Facilit d inspection et contr le Tol rance aux fautes 95 Sauvegarde migration re d marrage de la machine virtuelle Pas de risque de crasher la machine Objectifs de la pr sentation Faire cohabiter plusieurs syst mes d exploitation sur la m me machine Utilisation de la virtualisation abstraire la machine physique pour la partager entre plusieurs syst mes d exploitation Virtualisation system based Concept assez ancien Architecture of Virtual Machines R P Goldberg 1973 Diff rentes techniques de virtualisation Support mat riel pour la virtualisation 2 Techniques de virtualisation Principe g n ral Machine virtuelle couche logicielle mulant la plateforme processeur mat riel s ex cutant sur la machine h te Syst me d exploitation invit guest s ex cute au dessus de la machine virtuelle simul e Techniques de virtualisation Localisation machine virtuelle Type I native bare metal couche logicielle de virtualisa
12. Action sur le nombre de processus se partageant la m moire objectif liminer les processus quand leur nombre est trop important Action sur l espace m moire Remplacement local ou global Pages sur lesquelles s applique l algorithme de remplacement de pages Remplacement global choix effectu sur l ensemble des pages physiques quel qu en soient les processus propri taires risque d accaparation de la m moire par un processus au d triment des autres comp tition peut emp cher tous les processus de s ex cuter dans de bonnes conditions Remplacement local choix parmi les pages physiques poss d es par le processus faisant le d faut 39 gt N cessit de contr ler la m moire disponible pour chaque processus Partition fire nombre de pages divis entre les processus Peu adapt volution des besoins m moire au cours du temps manque d quit Partition variable re calcul p riodique de la taille de l espace m moire affect chaque processus Action sur l espace m moire Evaluation espace de travail gt Directe valuation pr cise trop co teuse approximation avec les bits U et une horloge Indirecte valuation du taux de d faut de page par processus P si taux lt Dmin on enl ve une page physique P si taux gt Dmax on alloue une page physique suppl mentaire P Contr le de la charge par processus Principe On tente de conserv
13. Qemu compilation dynamique Fonctions C correspondantes et code natif g n r void op movl_T0_r1 void TO env gt regs 1 mov 0x4 ebp ebx extern int op_paraml void op add TO _im void TO TO long amp _op_paraml add Oxfffffff0 ebx 3 void op mov_r1_T0 void env gt regs 1 TO mov ebx 0x4 ebp Qemu compilation dynamique Le compilateur dynamique traduit les blocs de base au fur et mesure de leur ex cution Les blocs d j traduits sont conserv s dans une table de hachage cache 2 4 Hardware assisted virtualization Hardware assisted virtualization Intel Virtualization technology VT x and AMD AMD V Pacifica Niveau de protection suppl mentaire pour la machine virtuelle descripteurs pour tat de la machine virtuelle Tables des pages de l OS invit g r es par mat riel et plus mul es Tagged TLB entries VPIDs Virtual Processor IDs pour les machines virtuelles 99
14. Pas d adresses virtuelles dans le code des programmes gt pas de contrainte sur le place ment des objets partag s Contenu du registre de base diff rent par processus se partageant l objet Partage modulaire si registre de base diff rent par objet partag 60 Segments de m moire partag s UNIX Interface Cr ation int shmget key_t key int size int shmflg Attachement void shmat int shmid void shmaddr int shmflg D tachement int shmdt void shmaddr Propri t s Partage des donn es contenues dans le segment sans interpr tation par le syst me Deux processus peuvent voir le segment deux adresses virtuelles diff rentes 1 4 Etude de cas partage et fork Unix Etude de cas partage et fork Unix Interface pitt fork void S mantique duplication de l espace d adressage du processus appelant code data pile partage des fichiers ouverts Objectif mise en uvre efficace du fork Hypoth ses Table des pages hi rarchiques Swap allou es au chargement R alisation basique Etat initial avant fork Filesystem Swap p P V prot pr Disque rx ex cutable V prot pr Liz 1 irx 1 rw M moire physique Table des pages data Tables de traduction processus P 61 Filesystem Swap
15. Marquage de tout objet non marqu r f renc par un objet marqu Parcours du graphe des r f rences Balayage lib ration de la m moire de tout objet non marqu 53 iim Quatri me partie Liaison et partage des objets dans un programme 55 1 Partage d objets 1 1 D finitions et motivations D finitions Definition 33 Partager Sens commun Poss der avec d autres mettre en commun petit Larousse Sens informatique ne pas dupliquer de l information utile plusieurs processus disque m moire Motivations Interfaces utilisateur graphique son biblioth ques d ex cution de langages gt Mise du code dans des biblioth ques volumineuses gt Int gration des biblioth ques dans les ex cutables disque de moins en moins raison nable Code ex cutable potentiellement partag entre plusieurs processus gt Duplication de ce code en m moire inutile Objets partag s Modules typiquement biblioth ques Objets au sens de la programmation objets Modules Proc dures Variables locales dur e de vie de la proc dure 1 copie par appel en cours Param tres formels Variables globales dur e de vie gt proc dure en g n ral en un seul exemplaire Objets externes d finis l ext rieur du module Module M1 biblioth que int g1 g2 globaux extern void pl int x void p2 int
16. plusieurs niveaux Interpr tation d une adresse virtuelle hp pv d bit de pr sence de l entr e hp de la table des hyperpages vaut 0 d faut d hyperpage bit de pr sence de l entr e pv de la table des pages de l hyperpage hp vaut 0 d faut de page 39 Table des pages page physique 120 1 120 5 di Table des hyperpages o EE 110 2 10 1 2 12 1 25 1 26 0 9 d2 2 10 1 0 W1 amp 11 0 no hyperpage 2 10 1 Eu page physique 65 Exemple 25 Exemple pr c dent avec hyperpages de 21 pages et pages de 21 pages acc s 0 0 d1 fournit l adresse physique 120 d1 emplacement bleu acc s 25 10 d2 fournit l adresse physique 65 d2 emplacement rose acc s 25 11 d8 provoque un d faut de page acc s 26 50 d4 provoque un d faut d hyperpage Tables des pages plusieurs niveaux Traitement d un d faut d hyperpage 1 V rification du caract re licite de l adresse 2 Recherche d une page physique libre pp pour la table des pages manquante 3 Initialisation de cette table des pages En g n ral tous les bits de pr sence sont faux Il faut ventuellement transf rer vers la page physique pp l image disque de la table des pages manquante 4 R ex cuter l instruction qui va probablement provoquer un d faut de page Tables des page
17. 1 rx Tirx rx l Tirw rw Table des pages text V prot pr nu D pr prot V Table des livres IF E er T Table des livres 1 r Ire gt E cr M moire physique Table des pages data Table des pages data Tables de traduction processus P Tables de traduction processus fork Apr s acc s en criture par le processus fork Filesystem Swap Disque V prot pr E swap P T rx J V prot DA DE C prot V Irx rx Jrxx Tirw lt rwll Table des pages text V prot pr UE pr prot V Table des livres F ME TW Table des livres T Z Irt J ha H cr TI M moire physique Table des pages data Table des pages data Tables de traduction processus P Tables de traduction processus fork Autres utilisations du copy on write Recopie paresseuse de messages M morisation de points de reprise checkpoint incr mentale Ramasse miettes copiants etc 63 2 Edition de liens dynamique un survol Rappels sur la liaison Objets logiques variables proc dures fichiers Objets physiques valeurs emplacements m moire Liaison passage du nom de l objet logique identificateur de variable pro
18. Choix du bloc r quisitionner politique de remplacement Pas de strat gie optimale sans connaissance de l avenir on ne peut pas savoir coup s r quelle information sera r utilis e dans le futur LRU Least Recently Used r quisition du bloc acc d le moins r cemment Random choix al atoire Limiter la dur e de remplacement en vitant de r quisitionner des cases modifi es on vite ainsi la phase de recopie avant le chargement Complexit de mise en uvre influence le choix d une strat gie de remplacement 2 4 Caches mat riels Caches mat riels tat du cache Unit de transfert des informations depuis la m moire bloc de quelques octets Adressage d un bloc adresse m moire Contraintes sur le placement d un bloc dans le cache Un seul emplacement possible correspondance directe direct mapped N importe o dans le cache caches totalement associatifs fully associative Dans un nombre fixe limit d emplacements associatif par ensemble set associative Correspondance directe Fonction de correspondance Emplacement MOD nb_blocs Bits validit du bloc V modification M Etiquette tag indication du contenu Pr sence dans le cache V 1 et tag recherch e Adresse poids fort index offset Etiquette tag Bits poids fort Ligne Totalement associatifs Blo
19. quentiels Fichiers lus int gralement si leur taille est inf rieure un certain seuil Gestion des caches Caches clients en m moire un pour les r pertoire un pour les fichiers Caches organis s en blocs estampill s avec une date de derni re modification Recopie retard e des caches p riodiquement toutes les 30 s l ouverture d un fichier contenu en cache v rification de la validit de la copie Invalidation p riodique des blocs 30 s Recopie la fermeture et flush gt Pas de s mantique de coh rence pr cise Andrew File System AFS G n ralit s Con u par l universit de Carnegie Mellon dans le d but des ann es 90 1000 serveurs en 1996 20000 clients r partis dans 10 pays Ensemble de stations de travail avec disque connect es un r seau de serveurs de fichiers Station O g R seau de Station serveurs Station Andrew File System AFS Nommage et localisation Hi rarchie de fichiers unique int grant tous les fichiers accessibles 89 Noms internes uniques fid Localisation dynamique Base de donn es dupliqu e utilis e pour localiser les fichiers Protocole pour assurer la coh rence des copies de cette base Andrew File System AFS Gestion des acc s et caches Serveurs avec tat Disque local des clients utilis comme cache S mantique d acc s de type session Transfert du fichier complet e
20. s logique n entra ne pas d acc s physique Permet les politiques de pr chargement en cas d acc s s quentiel Politique de recopie recopie imm diate E S physiques inutiles mais disque toujours jour recopie retard e moins d E S physiques mais disque n est pas toujours jour gt probl mes en cas de d faillance d utilisation de fichiers pour communiquer gt compromis recopies p riodiques fonctions de vidage sync Politique de remplacement taille du cache disque espacement des acc s on peut envisager une politique LRU 1 3 D signation D signation Propri t s des noms Dur e de vie permanent ou temporaire Port e globale ou locale Nature de l utilisation utilisateur ou syst me Types de noms utilis s dans un SGF Nom externe nom donn par l utilisateur permanent global utilisateur Nom interne nom utilis par le syst me pour d signer l ensemble des informations du fichier permanent global syst me Nom logique nom utilis par l utilisateur pour d signer le fichier ouvert temporaire local utilisateur 73 Nom local identification syst me du bloc de contr le d entr e sortie temporaire local syst me Types de noms utilis s dans un SGF Nom global Nom local permanent temporaire Utilisateur Nom externe Nom logique Syst me Nom interne Nom local Exemple 44 Exempl
21. un processus doit r sider en m moire physique acc d e par l UGM Adressage clairsem trous parmi les zones licites Si on a un espace virtuel par processus il y a une table des pages par processus Conserver en m moire uniquement la table des pages du processus actif trop co teux re chargement lors des changements de contexte gt on laisse donc en m moire physique les tables des pages des processus pr sents en m moire gt Volume m moire occup par les tables est un r el probl me Solutions possibles 37 Tables des pages plusieurs niveaux d coupage des tables en un arbre de tables on ne conserve en m moire que les niveaux utiles un instant donn Table des pages inverse on stocke les DPV dans la table des pages r elles Tables des pages plusieurs niveaux Principe D coupage de la table des pages en pages On conserve en m moire uniquement les morceaux de tables pages utiles un instant donn uniquement pour les zones licites D tection d une page de la table des pages manquante second niveau de pagination per mettant de savoir si elle est pr sente et si oui quelle adresse physique elle est implant e Table des pages M moire virtuelle de niveau 1 0 l page 0 Table des pages 0 S de niveau 2 Tee ea O 1 0 ue page 1 page non pr sente en m moire physique
22. une page Adresse s de l objet partag sur une fronti re de page Deux DPV r f rencent la m me page r elle Impact sur l algorithme de remplacement de page Duplication inutile de l information information contenue dans les DPV M canisme de partage Mise en uvre table des pages hi rarchiques Principe Partage non seulement des pages en m moire mais des DPV les d crivant Mise en uvre Table des hyperpages livres priv e chaque processus Pour la r gion partag e pages des tables des pages partag es par les processus se partageant l objet 58 a a 4 11 7 10 I 50 add0 15 1 7 Table livres P1 11 0 add1 Tee P priv e 12 1 4 add2 ee av1 4 10 0 Table des pages partag e av2 15 10 0 avl 4 Espace virtuel de P1 Espace virtuel de P2 o 50 M moire physique Remarques 35 Adresses des objets partager sur des fronti res d hyperpages livres Un seul DPV par page r elle gt Pas d impact sur l algorithme de remplacement de page M canisme de partage Partage d un objet contenant une r f rence Si O est partag la r f rence O l est galement gt La r f rence doit pouvoir tre interpr t e correctement par tous les processus utilisant O avi avi
23. Exemple de Qemu 2 4 Hardware assisted virtualization Premi re partie G n ralit s sur la gestion des 84 AS 7 nr 85 KUE AN A Me 86 M S E E E 88 90 d EV e n h TE 90 sR Ps TT TR S 91 NT DR d RS E N PS N R 92 94 informations 1 Mod le pour la d signation et la liaison 1 1 Terminologie Objets logiques objets d finis par l utilisateur variables fichiers Objets physiques correspondance physique des objets logiques secteur disque emplacement m moire Nom r les d un nom identification d un objet permet de le distinguer des autres permettre l acc s l objet le retrouver et le manipuler on parle g n ralement d identificateur pour les objets logiques d adresses pour les objets physiques Relation de d signation fait correspondre un objet un nom Liaison tablissement de la correspondance entre nom et objet d sign 1 2 Syst me de d signation D finition 1 Un syst me de d signation permet de d crire les associations nom objet d sign Remarque 2 Les associations nom objet d sign peuvent varier au cours du temps ajout suppression de noms changement d objet d sign par exemple les variables locales dans un programme El ments constitutifs d un syst me de d signation un domaine de d signation l ensemble des objets pouvant tre d sign s un ensemble des noms l ensemble des n
24. R2000 Adresses virtuelles et physiques de 32 bits pages de 512 octets 4 Ko Le CPU contient un TLB de 64 entr es Il n y a pas de table de pages g r e par le mat riel Table des pages g r e par logiciel Sur d faut de TLB d routement vers le syst me d ex ploitation qui parcourt la table des pages pour savoir si c est r ellement un d faut de page puis met jour le TLB 4 2 M moire virtuelle et cache Index et Tags adresses virtuelles ou r elles D coupage adresse pour pagination nv bits nop bits D coupage adresse pour acc s cache tag index off_lig nt bits ni bitsnol bits Index pv offset_page gt d faut dans le TLB la page peut tre en m moire physique pr offset_page np bits nop bits Si ni nol lt nop index cache identique avant et apr s traduction d adresse Indexation en virtuel parall lisme indexation cache acc s TLB Tags En virtuel on peut acc der au cache sans attendre la translation d adresse Probl mes synonymes ou alias pages logiques projet es sur la m me page physique plusieurs copies de la m me donn e dans le cache probl me de coh rence En g n ral 32 Cache L1 instructions tags et index en virtuel ou index en virtuel et tag en r el Cache L1 data index en virtuel tag en r el Cache L2 tout en r el 4 3 cr
25. Segmentation Variation de l adressage par registre de base Segment unit de structuration partage et protection de l information Adresse segment e couple nom_segment d placement Descripteur de segment contient les informations de taille protection et l adresse d im plantation du segment Biblioth que amorce Code ex cutable du programme Biblioth que charg e Tentative d acc s invalide droits longueur gt d routement vers le syst me d exploitation 67 adresse logique s d num ro de segrkent d placement dans segment d taille droits adresse 71 Descripteur de segment segment s Table des descripteurs de segments Remarque 39 Un segment constitue un espace d adressage ind pendant de l espace d adres sage des autres segments Pas de rapport entre le dernier emplacement du segment i et le premier emplacement du segment i 1 3 2 Organisation de la table des segments Objectifs Partager les segments gt ne pas dupliquer l information commune taille adresse d im plantation Permettre d exprimer des droits d acc s diff rents selon les processus Organisations possibles Table unique Tables multiples Organisation mixte Organisation de la table des segments Table unique Environnement de d signation universel Nom de segment nom unique identique pour tous les utilisateurs Descri
26. acc s en criture sur tous les processeurs sont termin s acc s une variable ordinaire lecture ou criture n est permis que quand tous les acc s aux variables de synchronisation sur tous les processeurs sont termin s Coh rence la lib ration distinction de l acquisition des verrous de leur lib ration Aquisition attente de la propagation des modifications Rel chement propagation des modifications locales aux autres machines 2 3 El ments de mise en oeuvre Unit de transfert Variable ou objet n cessit d un support langage pour d tecter l absence d une variable de la m moire Page l absence d une page peut tre d tect e par le m canisme de d faut de page risque de faux partage donn es non reli es peuvent tre allou e dans la m me page gt probl me de performance effet ping pong R plication et migration Duplication duplication de la donn e pour autoriser les manipulations parall les sur des processeurs diff rents Migration la donn e migre dans la m moire du site demandeur M moire cache de la m moire virtuelle r partie Classification des MVP SRSW Single Reader Single Writer pas de duplication Efficacit limit e car aucune parall lisation des acc s concurrents sur des n uds diff rents MRSW Multiple Reader Single Writer acc s concurrents en lecture autoris s mais pas en criture MRMW Multiple Rea
27. calcul de i tel que 271 lt T lt 2 adr trouver_trou 2 return adr char trouver_trou 2 if i gt max return 1 if liste i vide ad trouver_trou 2 1 if ad 1 diviser ce trou en 2 trous de taille 2 placer ces 2 trous 2 dans la liste i else return 1 adresse_trou extraire _ler_trou _liste i retour adresse_trou 52 3 Ramasse miettes Danger de la lib ration manuelle de m moire free Oubli de lib ration Double lib ration Utilisation d une zone apr s lib ration gt Lib ration automatique de la m moire Ramasse miettes Garbage Collection Objet racine utile par d finition ex pile Objets utiles accessibles directement ou indirectement partir de l objet racine via une cha ne de r f rences Remarque 31 N cessite de distinguer les r f rences des donn es simples dans les objets Comptage de r f rences Reference Counting Compteur de r f rences par objet Ajout d une r f rence incr mentation du compteur Retrait d une r f rence d cr mentation du compteur Destruction de l objet quand son compteur de r f rences atteint 0 Utilis dans les SGF pour la destruction des fichiers liens physiques Remarque 32 Ne lib re pas les structures cycliques Marquage et balayage mark and sweep Marquage Marquage des objets racines
28. ce qui est strictement n cessaire utilit pour les pages de pile On peut optimiser les d placements du bras en pla ant intelligemment les donn es sur disque Instants de lib ration de l image disque Fin de programme Strat gie de recopie Recopie imm diate write through beaucoup trop co teux et inutile information en m moire n est pas permanente D o Recopie diff r e write back Quand recopier Lors d un remplacement de page quand une page est supprim e de la m moire et qu elle est modifi e gt Deux E S disque pour le traitement du d faut de page recopie de la page requi sitionn e si modifi e lecture de la page manquante depuis le disque De mani re d corr l e avec le remplacement de page par un processus ind pendant gt On peut r quisitionner uniquement les pages non modifi es gt On risque d effectuer des recopies inutiles Remplacement de page Forte probabilit qu au bout d un certain temps il n y ait plus de page physique disponible dans le syst me Il faut alors lors d un d faut de page r quisitionner une page pour l attribuer au processus en d faut remplacement de page Chronologie d faut sur page pul 1 S lection de la victime pr r quisition la page pr va tre vid e La m moire tant pleine pr supporte d j une page virtuelle pu2 24 2 On note dans son descripteur que pv2 n est plus pr sente 3 Recopie de p
29. de recopie Types de recopie Recopie simultan e write through on recopie l information chaque criture dans le cache Recopie diff r e write back on recopie l information plus tard mais dans tous les cas avant de l effacer de la m moire rapide lors d un remplacement Types d allocation Allocation en criture write allocate une criture s effectue dans le cache charge ment puis criture Ecriture sans allocation nowrite allocate le bloc est directement modifi dans le niveau inf rieur Combinaisons courantes write allocate write back ou nowrite allocate write through Caches mat riels r partition des caches Hi rarchies de caches Caches d instructions et caches de donn es s par s ou unifi s en r gle g n rale caches L1 s par s Probl mes de coh rence en caches en multiprocesseurs 14 2 5 Caches logiciels Omnipr sents Caches du contr leur disque viter les acc s disque Caches du SGF local viter les acc s disque notamment sur les r pertoires Caches d un SGF r seau ex NFS Network File System viter la latence r seau et les acc s disque Caches Web M moire virtuelle et pagination la demande etc 15 Deuxi me partie Adressage virtuel et pagination 16 1 Introduction Objectifs Premier semestre l ments charg s de g rer le processeur et les entr es
30. des pages lin aire Repr sentation de l tat de la m moire lente disque Politique de recopie quelle strat gie adopter pour la recopie des pages modifi es Politique de remplacement quelle page supprimer du cache quand il est plein 23 3 2 El ments de mise en uvre Repr sentation de l image sur disque Principe associer une image sur disque chaque page virtuelle Utilit Savoir quel emplacement lire une page virtuelle lors de son chargement d faut de page Savoir quel emplacement recopier une page virtuelle modifi e recopie Emplacements possibles de stockage de l adresse disque Dans le descripteur de page virtuelle table des pages Dans une table s par e ayant une entr e par page virtuelle Zones du disque d di es au stockage de l image disque des pages virtuelles Zones non modifiables fichier ex cutable Zones modifiables zone d changes ou swap partition fichier Instants de mise en correspondance d une page virtuelle et de son image disque Correspondance statique au chargement au chargement d un programme on alloue l image de toutes ses pages virtuelles modifiables dans la zone d changes Correspondance dynamique l ex cution on tablit la correspondance au plus tard lors de la recopie d une page virtuelle sur disque Int r ts de la correspondance dynamique On n alloue sur disque que
31. fichiers locaux sont applicables aux fichiers distants Transparence la localisation les utilisateurs voient un espace de noms uniforme les fichiers peuvent tre d plac s sans changer de noms externes S ret de fonctionnement Fiabilit aucune donn e ne sera perdue ou corrompue suite la d faillance d un serveur Disponibilit le service de fichiers sera toujours disponible en d pit de la d faillance d un serveur Transparence aux d faillances la d faillance d un serveur sera transparente ses clients Gestion des acc s concurrents Coh rence stricte lecture retourne la derni re criture Facile assurer pour les syst mes sans caches Plus probl matiques dans les syst mes avec cache lt D H Lecture E N Ecriture B Lecture A lt c2 pa C2 CI ts Coh rence de session copie locale du fichier louverture modifications visibles aux autres uniquement la fermeture Coh rence faible une op ration de lecture retournera une valeur ayant t crite au pr alable au m me emplacement sans savoir laquelle 85 1 2 SGF r parti l ments de mise en oeuvre Probl mes li s la r partition d un SGF Localisation d terminer sur quelle machine se trouve un fichier Constitution de l espace des noms externes quelle est la structure de l espace des noms vue par un util
32. le mieux adapt Coh rence stricte N cessite un protocole particulier Sprite invalidation des caches client quand il existe au moins un crivain sur un fichier d tect l ouverture Echo protocole invalidation n jetons de lecture ou un jeton unique en criture 1 3 Exemples Network File System NFS G n ralit s 88 Con u par SUN en 1985 version 2 et 3 en 1989 et 1994 Serveur sans tat gt le serveur ne g re pas les acc s concurrents Montage distance gt pas n cessairement d espace de nommage unique Communication client serveur par appel de proc dure distance RPC Remote Procedure Call quivalent RMI Remote Method Invocation NFS d finit le protocole de communication client serveur pas l implantation des clients serveur gt haute disponibilit d pendante de l implantation gt la gestion des caches n est pas d finie dans le protocole Client Serveur fichier local inode inode local local inodes inode file handle Network File System NFS Mise en uvre SUN Mise en uvre des acc s Majorit des requ tes idempotentes m me r sultat si ex cut es plusieurs fois gt envoi r p t des requ tes au serveur s il ne r pond pas NFS server not responding still trying Transferts de donn es par blocs de grande taille 8Ko Lecture avec anticipation pour optimiser les acc s s
33. ro page 20 Pi w virtuelle 100 20 Table des pages directe Table des pages inverse Tables des pages inverse Traduction d adresse 1 Cache de traduction 2 Si absent recherche dans la table des pages r elles d une entr e Pi pv on ne travaille plus par indexation acc l ration des acc s techniques de dispersion hachage 3 Si absent de la table des pages en m moire d faut de page que l on r sout comme d habitude sauf identification des adresses disque Fonctions de pagination Tables des pages directes un seul niveau lin aires plusieurs niveaux hi rarchiques Tables des pages inverses Caches de traduction Variations non tudi es Pagination automatique des tables des pages en les mettant dans l espace virtuel super viseur 41 6 Gestion m moire et gestion du processeur Objectifs examiner les liens entre gestion m moire et gestion processeur lien entre unit d ex cution processus thread et espaces virtuels Mod le d ex cution Un processus par espace virtuel Lien un un entre unit d ex cution et espace virtuel On parle de processus lourd Protection des processus les uns par rapports aux autres acc s m moire incorrects inten tionnellement ou non Mise en uvre Registre contenant l adresse de la table des pages courantes dans l UGM Sauvegarde de ce registre lors des changements de contexte Vidage du TLB l
34. s pouvant tre retourn es par une op ration de lecture pas d hor loge commune Garanties fournies au programmeur Garanties fortes gt latence des acc s m moire lev e Garanties faibles latence plus faible Protocole de coh rence Implantation particuli re d un mod le de coh rence Un mod le de coh rence peut tre implant par plusieurs protocoles de coh rence Mod les de coh rence Coh rences fortes Coh rence stricte toute op ration de lecture d une variable partag e retourne la derni re valeur crite dans cette variable Demande l existence d un ordre total entre v nements pour que le sens de derni re soit bien d fini Le maintien de cet ordre total est tr s co teux Coh rence s quentielle le r sultat de toute ex cution est le m me que si les op rations de tous les processeurs taient ex cut es dans un ordre s quentiel donn et que les op rations de chaque processus apparaissent dans cette ex cution dans l ordre du programme Reformulation tous les acc s la m moire partag e seront vus dans le m me ordre par tous les processus Mod les de coh rence Coh rences faibles Coh rence faible distinction des acc s de synchronisation et des acc s ordinaires 91 les acc s aux variables de synchronisation sont s quentiellement coh rents acc s une variable de synchronisation n est permis que quand tous les
35. sorties Deuxi me semestre l ments charg s de g rer la m moire Accent mis sur les points suivants m moires pagin es liens existants avec gestion processeur et E S Concepts et notations Espace virtuel ou espace logique ensemble des informations accessibles par un processeur virtuel ex cutant un processus Adresse virtuelle adresse dans l espace virtuel d un processus Exemple 10 Adresse virtuelle Un processeur 32 bits peut acc der 4 Go d espace m moire ind pendamment de la capacit de m moire physique disponible Les adresses virtuelles vont de 0 232 1 Adresse physique ou r elle adresse dans la m moire vive de la machine Exemple 11 Adresse physique Les adresses physiques sur un processeur dot de 128 Mo de m moire vont de 0 227 1 Objets manipul s par les programmes objets logiques variables proc dures objets Mise en uvre finale de ces objets logiques en utilisant des objets physiques emplacement en m moire physique Passage des objets logiques aux objets physiques en deux phases implantation des objets logiques dans l espace virtuel liaison logique i e attribution d adresses virtuelles voir partie 4 mise en uvre de cet espace virtuel sur des supports physiques adresses physiques disque C est l objectif de ce chapitre Objets logiques Espace virtuel M moire physique liaison logique Transformation d adr
36. y int u v void p3 void int w 56 1 2 Propri t s attendues d un m canisme de partage Connaissance de l interface du module uniquement Pas de connaissance de la mise en uvre du module variables et proc dures internes utilisation d autres modules de son utilisation par d autres processus adresse d implantation 1 3 Partage dans un espace pagin Cadre Processus dot s d espaces virtuels lin aires pagin s Espaces d adressages priv s une table des pages par processus Objet partager objet O form de pages contigu s r gion R gion de code Biblioth que M canisme de partage Implantation de O dans les espaces virtuels des processus le partageant Les adresses d implantation peuvent tre diff rentes Les contenus des tables de pages doivent tre identiques avi E Espace virtuel de P1 M moire physique Espace virtuel de P2 M canisme de partage Mise en uvre table des pages lin aires 57 10 1 50 add0 11 10 add1 15 17 50 add0 avl 10 0 RUE ME ai Table des pages P1 Table des pages P2 av2 15 0 av2 Espace virtuel de P1 Espace virtuel de P2 50 D M moire physique Remarques 34 Objets partager ont une taille multiple de la taille d
37. P2 pour P2 pv1 O addpv1 n j table des M moire physique pages physiques RE pr P2 pv2 Remplacement de page Exemple tat apr s d faut Espace virtuel Espace virtuel de P1 de P2 table des disque table des disque pages de PI pour P1 pages de P2 pour P2 pvl U pr addpv1 o table des M moire physique pages physiques m pr PI pyl Remplacement de page Algorithme de remplacement de page 26 Definition 15 Algorithme de remplacement de page On nomme algorithme de remplacement de page ARP l algorithme de s lection d une page r quisitionner lors d un d faut de page lorsqu il n existe plus aucune page disponible Mesure de l efficacit de l ARP taux de d fauts de page nombre de d fauts nombre de r f rences ARP optimal algorithme de Belady n est pas r alisable en pratique n cessite de conna tre le futur Algorithmes utilis s utilisent les r f rences pass es et les propri t s de localit des programmes Remplacement de page Algorithmes de remplacement de page classiques FIFO First In First Out s lection de la page la plus anciennement charg e ne respecte pas le principe de localit une page souvent r f renc e sur une longue p riode fini
38. RIVATE fd descripteur du fichier ouvert Exemple 50 f open toto O_RDWRITE char ad mmap 0 1024 PROT WRITE MAP SHAREDf 0 for i 0 i lt 1014 i adli i 81 ue 100 101 102 T 5 H Sixi me partie Gestion de l information dans les syst mes r partis 82 Architecture des syst mes r partis Machines connect es par un r seau Pas de m moire commune Pas d horloge commune Moyen de communication entre processeurs changes de messages m moire 1 m moire 2 m moire 3 processeur 1 processeur 2 processeur 3 Message r seau Gestion m moire dans les syst mes r partis Quelle machine virtuelle offrir l utilisateur Envoi de messages Outils diff rents des outils habituels Manipulation diff rentes des informations locales et distantes sockets RPC RMI etc Cacher les envois de messages manipulation de donn es classiques identiques pour les informations locales et distantes Fichiers syst mes de gestion de fichiers r partis M moire m moire virtuelle r partie Syst me de gestion de fichiers SGF r parti R seau Proc e Proc Proc v Proc SGF SGF local SGF local SGF r parti Abstraction du DS id OS er SGF r parti Mise en oeuvre du SGF r parti M moire virtuelle r partie 83
39. SGM Syst mes d exploitation Gestion de la m moire Master S T S mention informatique premi re ann e Isabelle Puaut Septembre 2011 Table des mati res 1 G n ralit s sur la gestion des informations 1 D signation et liaison Talk lerminologie ORO R oao rpa i e ce D E an en a tue ati ER G 12 Syst me de d signation 1 3 R solution des noms TAs Exemplet SGE 208 8 300 and NE nent A due 30 T BA en dt on du 2 Hi rarchies m moire 2 1 Notion de hi rarchie m moire 2 2 Principe g n ral du m canisme de cache 2 3 El ments de mise en uvre 24 Caches mat riels 2 2 4488 42 02247 83 he Pas mirent SHARE Sd Res us 2 5 Gaches logiciels 422 2 48 108 arts Mantes une a Mes eh sont hou 4 8 IT Adressage virtuel et pagination 1 Introduction 2 Pagination 2 1 Adresse virtuelle et adresse physique 2 2 Fonction de pagination s sarsari deal on Re don ne a ne spam R o pe 3 Pagination la demande JL Principe a Se A Re ue 71 E Ie E ne A ME Ed A MEN ls Mir sn 3 2 El ments de mise en uvre 4 4444444444 eee 4 Am lioration des performances 4 1 Caches de traduction 4 444444 4444 44e eee 4 2 M moire virtuelle et cache 4 444444 ee 4 3 Ecroulement du syst me
40. adaptation du programme une volution de son environnement d ex cution Plus la liaison est tardive plus les informations n cessaires la liaison devront tre conserv es longtemps Edition de liens statique tous les identificateurs ont t traduits avant ex cution m me si la liaison n est pas tout fait termin e Edition de liens dynamique il reste des identificateurs de r f rences externes non r solus au d but de l ex cution Edition de liens statique Tous les identificateurs ont t transform s en adresses avant ex cution 64 10000 i call 20000 Code du programme main f10 Fonction de B call 20020 f2 Fonction de B 20000 20020 RSR pinot Biblioth que B Limites de l dition de liens statique Liaisons inutiles quand des objets sont li s et non utilis s appels conditionnels Gestion des volutions difficile versions corrections de bugs N cessit de refaire l dition de liens pour b n ficier d une nouvelle version Consommation d espace disque et m moire inutiles pour les copies des objets li s 2 2 Edition de liens dynamique Edition de liens dynamique Instants possibles de la liaison Au chargement du module contenant une r f rence externe ou la premi re r f rence un objet externe Remarque 37 Edition de liens dynamique va de pair avec partage des biblioth ques gt les bibli
41. at riel h te Syst mes d exploitation h te et invit ne sont pas modifi s Excellente isolation entre les machines virtuelles et le syst me h te Tr s bonnes performances quand les processeurs de l h te et de l invit sont identiques Possibilit de m morisation de l tat de la machine virtuelle Full virtualization inconv nients Forte p nalit sur les performances lorsque les processeurs de l h te et de l invit sont diff rents gt Compilation dynamique de binaire binaire just in time Full virtualization exemples VMWare Bochs Microsoft Virtual PC VirtualServer VirtualBox Qemu 2 2 Paravirtualization Paravirtualisation Objectif am liorer la performance de la full virtualization Paravirtualisation Hyperviseur Noyau all g et sp cialis dans la virtualisation 97 D portation dans l hyperviseur les op rations trop lentes effectuer dans l environnement virtualis ex gestion du temps gestion d interruptions drivers Hyperviseur tourne directement sur la machine h te Les noyaux invit s sont conscients d tre virtualis s et font appel l hyperviseur pour traiter les appels syst me Paravirtualization int r ts Performances sup rieures la full virtualisation Tr s bonne isolation Paravirtualization inconv nients N cessite de modifier le syst me invit L architecture des syst mes
42. c n importe quel emplacement du cache Recherche dans tous les emplacements du cache en parall le Etiquette contient quasiment toute l adresse 12 En pratique caches de petite capacit recherche associative Adresse poids fort offset Etiquette tag Valeurs Bits poids fort Ligne v Recherche totalement associative Associatifs par ensemble Ensemble set groupe de blocs dans le cache Degr d associativit associativity degree nombre de blocs par ensemble Si n blocs dans un ensemble on parle de caches associatifs par ensemble de 2 voies n way set associative Fonction de correspondance 1 s lection de l ensemble soit en g n ral ensemble MOD nb_ensembles 2 recherche en parall le du bloc dans l ensemble Tr s utilis en pratique Cache associatif par ensemble de 2 voies 13 Adresse poids fort index offset Recherche associative dans l ensemble 4 L Etiquette tag Valeurs Bits Etiquette tag Valeurs Bits poids fort Ligne poids fort Ligne Ensemble Voie way Caches mat riels politique de remplacement Politiques les plus courantes LRU Least Recently Used remplacement du bloc qui a t acc d depuis le plus longtemps FIFO First In First Out Random Caches mat riels politique
43. c dure sa repr sentation concr te au moins les noms des objets physiques supportant cette repr sentation Logiciels contribuant la liaison vus en licence Traducteur compilateur ou assembleur Traduction de code source en code machine Traduction des identificateurs d objets dans une repr sentation interne Editeur de liens regroupement du code et des donn es de plusieurs modules en r solvant les r f rences externes Chargeur initialisation de la machine processeur m moire pour que le programme puisse tre ex cut 2 1 Edition de liens statique vs dynamique Instant ou les identificateurs sont associ s des adresses A l criture du programme Nom des objets physiques dans le texte source g n ralement assembleur l dition de liens L adresse d implantation des programmes est fix e par l diteur de liens et pas par le chargeur Syst mes pagination l adresse d implantation est une adresse virtuelle Syst mes adressage r el l adresse d implantation est une adresse r elle Au chargement l adresse d implantation est fix e au chargement pas ne change pas pendant l ex cution l ex cution liaison dynamique les adresses sont fix es l ex cution le programme ne contient plus aucune adresse et peut donc toujours tre d plac en cours d ex cution Moment de la liaison Remarques 36 Plus la liaison est tardive meilleure sera l
44. der Multiple Writer acc s concurrents en lecture et criture au toris s Gestion de la localisation et des acc s Structures de donn es n cessaires Propri taire n ud ayant crit en dernier sur la page Gestionnaire n ud qui connait le propri taire d une page et qui est charg de g rer les acc s en criture la page Ensemble de copies ensemble des n uds poss dant des copies de la page Protocole de Li amp Hudak gestionnaire centralis MRSW Multiple Reader Single Writer n exemplaires en lecture ou un seul en criture Mod le de coh rence s quentielle Protocole de coh rence invalidation sur criture Gestionnaire unique par page partag e D faut de page en lecture sur page p 92 Obtenir une copie de p aupr s du gestionnaire de p qui contacte le propri taire Relancer l instruction D faut de page en lecture sur page p Site gestionnaire Site propri taire m moire 2 m moire 3 m moire 4 prop 4 copies 2 4 m moire 1 3 Acc s la page en lecture par processeur 1 Site gestionnaire Site propri taire m moire 1 m moire 2 m moire 3 m moire 4 prop 4 copies 1 2 4 D faut de page en criture sur page p Obtenir une copie de p aupr s du gestionnaire de p qui contacte le propri taire Invalider les autres copies de p Changement de propri taire
45. ditions PATH LD LIBRARY PATH CLASSPATH Liaison liaison un contexte quand on int gre un fichier un r pertoire cr ation copie d placement 2 Hi rarchies de m moire caches 2 1 Notion de hi rarchie m moire Supports divers de stockage d information Capacit de stockage et temps d acc s tr s h t rog ne En g n ral plus le temps d acc s un support est rapide plus sa capacit est faible Definition 6 Hi rarchie de m moire Organisation des supports de stockage par temps d acc s croissants ou taille croissante Notion de hi rarchie m moire exemple Processeur Registres Se apacit croissante M moire s cache Capacit anit Temps d acc s croissant M moire centrale DRAM Disque V Registres m moire tr s rapide directement accessible au processeur en un cycle capacit de quelques dizaines quelques centaines d octets M moire cache interne L1 m moire rapide int gr e au processeur accessible en quelques cycles de capacit de quelques dizaines de Koctets par exemple 16 Koctets M moires cache externes L2 L3 m moires moins rapides que le cache L1 mais plus volumineux M moire centrale Dynamic Random Access Memory capacit plusieurs Goctets temps d acc s de l ordre de plusieurs dizaines de cycles du processeur 100 300ns Disque capacit de
46. e Distinction entre zones libres et zones occup es gt Structure de donn es adapt e Allocation parcours de la structure de donn es pour trouver une zone libre Lib ration r int gration du bloc dans la structure de donn es Fragmentation Fragmentation externe Au fil des allocations lib rations l espace m moire est constitu d un m lange de zones libres et occup es Fusion de trous adjacents en m moire lors de la lib ration La place prise par les zones libres peut tre perdue si les zones libres sont de trop petite taille Fragmentation interne Taille allou e gt taille demand e multiple d une taille minimum de bloc Tmin ou autres contraintes sur tailles de blocs Motivation limitation taille de structures de donn es Cons quence place perdue taille_allou e taille demand e 48 Zones libres Zones occup es Taille demand e quelconque HE Fragmentation interne Taille allou e multiple de Tmin Fragmentation externe Zone A Lib ration de la zone A Trous regrouper 2 Algorithmes d allocation dynamique 2 1 Classes d algorithmes d allocation dynamique Classes d algorithmes d allocation dynamique Bitmap table de bits 1 bit par bloc Sequential fits structure de liste stock e dans les trous Indexed fits autre structure de donn es e g arbre stock e dans les trous Buddy sys
47. e d Unix Noms et liaison des noms dans Unix Programme utilisateur Syst me main Nom logique f fopen udd puaut toto r par ouverture fread buf 1 10 f Nom externe Y fclose f Nom interne Nom local 2 Le partage des fichiers 2 1 Contr le des acc s simultan s Probl me Ex cution parall le ou pseudo parall le des processus Les processus peuvent acc der au x m me s fichier s gt Coh rence du contenu des fichiers gt Synchroniser les acc s aux fichiers Exemple 45 FILE f fopen toto r for int i 0 i lt N i fread buf 1 sizeof int f fclose f FILE f fopen toto w for int i 0 i lt N i fwrite amp i 1 sizeof int f fclose f Classes de politiques de contr le Contr le l ouverture vs contr le lors des acc s l mentaires lecture criture 74 Politique de contr le syst matique ex lecteur r dacteur vs politique de contr le laiss e l utilisateur verrous Exemples de politiques de contr le Politique syst matique l ouverture interdire deux ouvertures simultan es du m me fichier Politique utilisateur au niveau des acc s l mentaires en utilisant des verrous sur des portions du fichier UNIX 2 2 Protection Propri t s assurer Confidentialit emp cher la divulgation des informations sans autori
48. e de d signation Commande mount gt Possible que deux utilisateurs n aient pas la m me hi rarchie de fichiers 76 A A Syst me de fichiers A Syst me de fichiers B 7 d1 d2 A Hi rarchie apr s montage de B sous le r pertoire d2 du syst me de fichiers A Repr sentation permanente des fichiers Inode Informations de propri t et droits d acc s Taille Table d implantation Nom interne d un fichier couple n volume n inode R pertoire m morise la correspondance entre nom externe et inode i type de fichier nombre de liens uid du propri taire gid du propri taire Taille octets date cr ation date du dernier acc s 128 date derni re modification octets droits num ros des 12 premiers blocs Bloc d indirection simple Bloc d indirection double Bloc d indirection triple _ i node Contenu du volume contenant le syst me de gestion de fichiers bin NE dev etc TT rep courant 2 rep p re nil R pertoire bin k racine dev rep courant 7 rep p re 2 R pertoire bih Fichier de code de Is Re
49. e fera lors des d fauts de page bit pr sent 0 toutes les pages sont absentes initialisation des adresses disque pour r f rencer la zone d changes initialisation des registres du processeur SP PC 28 Trois types de zones vis vis du chargement code son image reste dans le fichier ex cutable non modifiable donn es initialis es leur tat initial doit tre obtenu partir du fichier ex cutable mais leur image sera ensuite sur la zone d change une copie par processus donn es non initialis es et pile pas d tat initial fix leur image sera tout le temps dans la zone d change Chargement d un programme Solution simple Principe allocation statique au chargement de l image disque initialisation de la partie de la zone d changes correspondant aux donn es initialis es Chronologie 1 r servation d espace virtuel table des pages pour les diff rentes zones code data bss stack 2 r servation disque dans la zone d changes pour data bss stack 3 recopie de l tat initial des donn es initialis es fichier ex cutable vers la partie de la zone d change correspondante 4 initialisation de la table des pages V 0 et la table des adresses disques Fichier ex cutable Table des pages Table disque 7 HH pile Espace virtue
50. er Remarques 30 Il faut r soudre le probl me d implantation d un segment dans l espace lin aire cf gestion m moire par zones Plus de table des pages par segment Deux segments diff rents peuvent tre situ s dans la m me page et se partagent alors le m me DPV gt int ressant si on a beaucoup de petits segments 46 Troisi me partie Allocation de la m moire par zone 47 Allocation dynamique de m moire Objectif Demande de m moire suppl mentaire l ex cution Tailles et dur es d utilisation des zones de m moire quelconques Interface typique void malloc size t size demande d une zone de m moire de taille size et retour de son adresse void free void ptr lib ration d une zone de m moire allou e au pr alable rq on ne passe pas la taille en param tre Domaines d utilisation Syst mes sans pagination allocation de m moire r elle Syst mes avec pagination allocation de zones dans l espace d adressage virtuel utilisateur allocation en m moire physique pour le syst me d exploitation Allocation dynamique de m moire Terminologie Zone suite d emplacements m moire contigus de taille non fix e a priori Zone caract ris e par son adresse de d but et sa taille Zone libre trou zone de m moire non allou e par le syst me Zone occup e partie de m moire allou e un processus 1 Probl mes r soudre Probl mes r soudr
51. er pour chaque processus son ensemble de travail en m moire Si on n y arrive pas c est qu il y a trop de processus gt on r quisitionne toutes les pages physiques poss d es par un processus le moins prioritaire par exemple R gulation globale de la charge Choix empirique d un indicateur de fonctionnement du syst me permettant de savoir si on est dans la zone optimale ou la zone d croulement Exemples d indicateurs taux de d faut de page temps moyen entre d fauts de page taux d occupation du contr leur disque Mesure r guli re de cet indicateur Ajustement du degr de multiprogrammation pour maintenir le facteur dans une fourchette acceptable r quisition de tout l espace m moire d un processus 5 Limitation de la consommation m moire 5 1 Influence de la taille des pages Impacts de l augmentation de la taille des pages p sur la consommation m moire du syst me Positifs Diminition taille de la table des pages espace virtuel de taille gale moins de pages Diminution temps de transfert disque amortissement du temps de positionnement sur une piste N gatifs Fragmentation interne espace perdu venant du fait qu un programme de fait pas un nombre entier de pages En moyenne p 2 par r gion Taille optimale pour limiter la consommation m moire Soient p la taille d une page v la taille de l espace virtuel 36 d la taille d un descript
52. ers SGF Gestion et acc s des informations stock es en dehors de la m moire centrale Supports assurant la persistance de l information Fichier Definition 40 Fichier R servoir d informations stock es sur un support de stockage permanent R les stockage permanent conservation d informations sur une longue dur e communication change d informations entre usagers ou entre programmes Syst me de gestion de fichiers SGF Interface Cr ation destruction Ouverture ou fermeture session de travail sur le fichier Positionnement dans le fichier Lecture et criture Gestion des r pertoires et des droits d acc s Interface syst me biblioth que des langages ex E S tamponn es dans la biblioth que standard C Probl mes r soudre Gestion de l espace disque cr ation allongement Gestion des acc s au contenu Gestion de l ensemble des fichiers nommage hi rarchie de fichiers contr le d acc s 1 1 Gestion de l espace disque Unit d allocation bloc ou granule suite de secteurs cons cutifs de la m me piste Bloc plus petite unit allouable Cri res de choix de la taille d un bloc performances de l allocation de bloc temps d allocation taille de la structure repr sentant l tat du disque fragmentation interne performance des acc s disque Exemple 41 Pistes de 128 Ko rotation en 8 ms positionnement b
53. es selon le niveau Soient deux niveaux contigus de la hi rarchie m moire m moire rapide et m moire lente Adressage adressage de la m moire lente mais acc s toujours r alis s sur la m moire rapide Acc s si l information voulue n est pas pr sente dans la m moire rapide il y a d faut de cache Il faut alors la transf rer de la m moire lente vers la m moire rapide chargement criture criture dans la m moire rapide recopie de l information en m moire lente ventuellement de mani re diff r e recopie D faut de cache quand la memoire rapide est pleine enlever au pr alable une informa tion de la m moire rapide remplacement en essayant de maintenir en m moire rapide les informations les plus utiles politique de remplacement criture lecture M moire rapide cache criture lecture recopie chargement M moire lente M moire lente Abstraction Mise en oeuvre la m moire rapide joue le r le de cache pour la m moire lente la m moire rapide contient la partie utile de la m moire lente L efficacit du cache peut tre valu par le taux de d faut le rapport entre le nombre d acc s provoquant un d faut et le nombre d acc s total d pend fortement des programmes 2 3 El ments de mise en uvre Quel que soit le niveau de la hi rarchie o on se place les probl mes r so
54. esse g rer l allocation des emplacements logiques sur les supports physiques disque m moire centrale g rer les transferts entre les diff rents supports r aliser la correspondance entre adresses virtuelles et adresses physiques 2 M canisme de pagination Introduction au m canisme de pagination D coupage de l espace virtuel en morceaux de taille fix e nomm s pages Adresse virtuelle couple n de page virtuelle d placement dans la page virtuelle Le m canisme d adressage remplace chaque acc s le num ro de page virtuelle par un num ro de page physique 17 j M canismes Adresse virtuelle finale Instruction d adressage logique pv depl Fonction de pagination pr Table des pages Adresse r elle pr depl Int r ts du m canisme de pagination Permet la r implantation dynamique des programmes Utilisation de programmes dont la taille camul e d passe celle de la RAM Permet le va et vient RAM disque automatique par page L R implantation partir A l de la page 1000 FOUT 2 1002 3 1003 4 1004 Table des pages Table des pages Pr sentation des notions 1 Cas simples espace virtuel lin aire fonction de pagination simple simple table de correspondance 2 Extensions fonctions de pagination plus labor es
55. eur de page virtuelle la taille occup e par la table des pages est d on suppose une seule r gion par processus Place totale perdue par processus d y Quand p croit cette fonction commence par d cro tre puis croit Taille optimum quand d riv e nulle savoir p V2dv Taille optimale pour limiter la consommation m moire Exemple 21 d 8 Optimum atteint pour une taille de page entre 24 et 212 p place perdue place perdue 256 16 512 3 1 512 8448 1 6 1024 4608 0 8 2048 3072 0 6 4096 3062 0 6 8192 4608 0 8 Remarques 22 La place perdue reste limit e par rapport une gestion par zone une demi page par r gion Le calcul pr c dent ne tient pas compte de l am lioration des transferts disque avec des grosses pages Taille typique des pages de 512 octets 8Ko 5 2 Fonctions de pagination adapt es Limitation de la consommation m moire par utilisation de fonctions de pagination adapt es Constat plus l espace virtuel est grand plus la table des pages est grande Exemple 23 taille de DPV de 32 bits espace virtuel de 32 bits tables lin aires taille des pages taille table nombre pages octets des pages octets table des pages 512 275 32 Mo 216 65 536 1024 22 16 Mo 214 16 384 2048 223 8 Mo 212 4 096 4096 222 4 Mo 210 1 024 Limitation de la consommation m moire par utilisation de fonctions de pagination adapt es Table des pages d
56. eux d fauts chute brusquement 34 Cons quences contr leur disque satur ce qui ralentit d autant le traitement des d fauts de page pendant les E S on ex cute les autres processus mais eux m me d clenchent des d fauts de page etc Calcul du taux de ralentissement de l UC p d au m canisme de pagination Soient t le temps moyen d ex cution d une instruction p la probabilit d un d faut de page T le temps moyen de r solution d un d faut de page T gt gt t facteur minimum de 10000 t 1 P HT PT Facteur ayant un impact important p T gt Pour que p soit le plus proche possible de 1 il faut que p soit le plus petit possible gt Tl faut qu un processus ait assez de place pour loger son ensemble de travail Taux de ralentissement de UC p en fonction du degr de multiprogrammation Degr faible pas assez de processus ex cuter pendant les d fauts de page Zone optimale Ecroulement pas assez de m moire pour loger les ensembles de travail rho 1 degr de gt multiprogrammation 4 4 La zone optimale croulement Solutions au ph nom ne d croulement Objectif faire en sorte que chaque processus dispose d assez de m moire pour y loger son ensemble de travail Moyens Action sur l espace m moire allou chaque processus objectif allouer chaque pro cessus son espace de travail et ou
57. h te et modifi doivent tre les m mes Paravirtualization exemples Xen Denali Full virtualization vs paravirtualisation Full virtualization developpement fiabilit Para virtualization performance 2 3 Exemple de Qemu Qemu caract ristiques Full virtualization type II Fonctionne de mani re stable sur les architectures suivantes x86 Linux Windows et Mac OSX x86 64 Linux PowerPC Linux et Mac OSX Emule de mani re stable les plateformes suivantes x86 x86 64 ARM PowerPC Mips Sparc Son code source a t repris dans diff rents autres projets VirtualBox KVM Qemu compilation dynamique Chaque instruction de l architecture invit e est d compos e en micro instructions Micro instruction instruction ultra simplifi e mode d adressage tr s simple Chaque micro instruction est programm e en C comme une fonction capable d effectuer le calcul en question Compilation de chacune des fonctions vers un fichier objet pour l architecture h te gcc 98 Qemu compilation dynamique Traduction de l instruction PowerPC suivante vers l architecture x86 addi r1 r1 16 rl r1 16 Les micro instructions associ es sont movl_T0_r1 TO rl addl_ TO0_im 16 TO TO 16 movl r1_TO rl TO TO est une variable temporaire dont on pr cise GCC qu elle doit tre stock e dans un registre du processeur h te
58. he chargement dans le cache partir de la m moire lente en tenant jour la structure de donn e d crivant l tat du cache puis acc s dans le cache Mise en uvre politique de recopie Constat si on modifie un l ment du cache il y une diff rence entre la version de la donn e correspondante dans le cache et en m moire lente version en cache la plus r cente On dit dans ce cas que la version en cache est modifi e Pourquoi recopier rendre les modifications durables anticiper l viction de ce bloc du cache Types de recopie Recopie simultan e write through on recopie l information chaque criture dans le cache Recopie diff r e write back on recopie l information plus tard mais dans tous les cas avant de l effacer de la m moire rapide lors d un remplacement Mise en uvre politique de remplacement Pourquoi remplacer le cache est plus petit que la m moire lente il va se remplir rapidement Que faire lors d un d faut de cache lorsque le cache est plein charger la donn e manquante dans un emplacement occupp auparavant par une autre donn e 1 r quisitionner un bloc du cache recopie de l information en m moire lente si n cessaire plus modification de la structure de donn es d crivant l tat du cache 2 charger l information manquante plus modification de la structure de donn es d crivant l tat du cache 11
59. is pour toute avant l ex cution R solution dynamique correspondance entre nom et objet re calcul e chaque acc s Distinction bien connue pour traduction et ex c de programmes Compilation remplacement des noms des objets logiques par les objets physiques corres pondants adresses avant ex cution Interpr tation on d termine lors de chaque acc s un objet logique l objet physique cor respondant Interpr tation iqentificateur adresse emplacement interpr teur processeur pendant l ex cution PERS identificateur adresse j emplacement Compilation i E j compilateur diteur de liens processeur pendant l ex cution avant l ex cution Exemple 4 int x x 0 Sch ma compil on va d cider avant ex cution d implanter l objet x une certaine adresse ex 1020 et le programme ex cutable contiendra une instruction dont l op rande sera l adresse 1020 ex mov ax 1020 Sch ma interpr t l affectation se fera via un appel de l interpr teur de type affecter x 0 qui d terminera l emplacement associ x pendant l ex cution R solution des noms cha ne d acc s En g n ral passage de l identificateur d objet logique l objet physique est indirect utili sation de noms ou objets interm diaires R solution compl te du nom parcourir de cette cha ne d acc s en utilisant diff rents m canismes Un descripte
60. isateur par quel m canismes est il construit Mode d acc s aux informations comment est r alis e une lecture une criture comment minimiser les transferts comment g rer les caches Disponibilit comment faire face aux fautes mat rielles quel est l impact de la duplication sur l acc s aux fichiers comment g rer les r pliques S curit comment assurer la confidentialit et l int grit en pr sence de machines sur les quelles on peut manipuler le mat riel et le logiciel comment authentifier un usager Choix g n raux de conception Stations banalis es toute station peut a priori tre serveur de fichier ou client Stations sp cialis es une station ne peut pas tre client et serveur de fichiers la fois permet de d finir des r gles de s curit adapt es exemple serveurs de fichiers dans des locaux s rs confiance dans le mat riel et le logiciel install s Serveurs avec tat le serveur stocke des informations sur les clients en cours d utilisation des fichiers Moins d informations transiter dans les requ tes Facilit de lectures avec anticipation Possible de g rer des verrous d acc s au fichier D faillance du client et du serveur peuvent laisser le syst me dans un tat malsain ses sions jamais ferm es sessions ferm es de mani re autoritaire Serveurs sans tat le serveur ne m morise rien sur ses clients Exemple NFS E
61. l M moire physique Chargement d un programme Am liorations Allocation dynamique d espace disque pour les donn es non initialis es et la pile Allocation au plus tard lors du remplacement de page Allocation paresseuse d espace disque pour les donn es initialis es Tant qu une page de cette zone n est pas modifi e en m moire on continue utiliser l image disque du fichier ex cutable Allocation d espace disque au plus tard lors de la recopie 29 L lecture seule CE copie sur criture PI pas d image sur disque Table des pagesTable disque 7 pile Espace virtuel Zones licites vs illicites Fichier ex cutable OSS L 0 1 7 CE Zone d changes swap EUSE A PI G 777774 PI M moire physique Disque Definition 16 Zone illicite Zone d adresses virtuelles dont l acc s entra ne une erreur l ex cution Zone licite zone pour laquelle les tables des pages sont allou es Rep rage des zones illicites Bits non g r s par le mat riel dans les DPV Test lors de d fauts de page R capitulatif contenu typique d un DPV V U M npp V test de r sidence U pour remplacement de page M pour recopie npp emplacement en m moire hachur ignor par MMU test si licite copy on write etc R capitula
62. lles gt Chargement d une page en m moire physique que si elle est r f renc e pagination la demande gt Au lieu d un va et vient global sur tout le programme on peut effectuer un va et vient au niveau de la page en fonction des besoins Principe du cache m moire lente espace virtuel dont on a l image sur disque m moire rapide cache m moire principale de la machine demande d acc s 4 l espace virtuel Na r d faut de page m canisme de pagination l ENDAH i 1 l mise 1 M moire physique en oeuvre de l espace virtuel 1 hargement logiciels de gestion de la pagination la demande recopie Image de l espace virtuel sur disque Initialement aucune page en m moire physique espace virtuel sur disque cache vide Acc s une page non pr sente gt d routement pour d faut de page La routine ex cut e doit rendre possible l ex cution de l instruction fautive 1 trouver une page physique disponible 2 la remplir avec l image disque de la page virtuelle 3 modifier la table des pages pour noter la pr sence de la page virtuelle en m moire physique 4 r ex cuter l instruction fautive l ments de mise en uvre Identiques aux probl mes r soudre pour les m moires cache Repr sentation de l tat du cache support e par structure de donn e de la fonction de pagination au plus simple table
63. locs de f1 EN 1141 W P1 1 Blocs de f2 fd1 open f1 R fd2 open f W 1 0 RW fd3 open f1 RW compte Iseek fd2 4 SEEK_SET cpt pt dr inode Remarques 48 fdl fd2 et fd3 sont des noms logiques ils n existent pas en dehors du programme l sont locaux au processus Ces structures de donn es permettent de partager les inodes m moire entre processus Contr le des acc s concurrents Initialement aucun contr le d acc s concurrents pr vu Ajouts ult rieurs via l appel syst me fentl Verrous Possibles sur des parties de fichiers offset taille Verrous exclusifs ou partag s Politique de contr le la charge de l utilisateur gt possibilit s d interblocages Protection Repr sentation simplifi e des droits liste de taille fix e Trois domaines d utilisation possibles pour un fichier propri taire groupe autres Trois droits possibles pour chaque fichier normal lire crire ex cuter gt 9 bits suffisent pour d crire tous les droits associ s au fichier 79 Processus P1 groupe g1 fopen toto r Processus P2 groupe g1 nn fopen toto w Rejet M canisme de contr le d acc s Droits sur toto Id prop P1 Gr prop g1 LE L ls 1 affiche rw r gt _ Remarque 49 Pas possible de dire facilement que dans un groupe gl seul ul a ce
64. n cache l ouverture Acc s enti rement locaux apr s ouverture Recopie des donn es vers le serveur la fermeture la fermeture le client conserve une copie Le serveur m morise les clients ayant une copie Demande d invalidation envoy e quand le serveur re oit une nouvelle version du fichier fermeture par un autre client Andrew File System AFS Client 1 Serveur Client 2 Cache i Cache i Ouv 1 criture lt Ouv 1 Fermeture d criture Ouv 2 lt Fermeture db Fermeture mw Ouv 3 2 M moires virtuelles r parties 2 1 Principe Principe des m moires virtuelles r parties Manipulation des donn es comme si elles taient dans une m moire unique partag e par tous les processeurs 90 d2 0 processeur 2 diei d1 0 processeur 1 processeur 3 di E d2 H M moire En r alit la m moire partag e est mise en uvre en utilisant les m moires des processeurs constituant le syst me 2 H a DM m moire 1 m moire 2 m moire 3 d1 0 d2 0 di 1 processeur 1 processeur 2 processeur 3 r seau 2 2 Mod le de coh rence Coh rence dans les m moires virtuelles r parties Mod le de coh rence D finit la les valeur
65. namique mais pas de va et vient par bloc va et vient global seulement X RW 1 MOV X DS 1 MOV DS X 2 7 2 Adressage segment Adressage segment sans pagination Variation de d adressage par registre de base Segment unit de structuration partage et protection de l information Descripteur de segment contient les informations de taille protection et l adresse physique d implantation du segment R implantation dynamique modification du descripteur de segment changement adresse d implantation adresse logique s d num ro de segihent d placement dans segment d taille droits adresse Descripteur de segment segment s Table des descripteurs de segments 7 3 Segmentation et pagination Pagination facilite l implantation des programmes en m moire physique d un espace virtuel lin aire Segmentation offre l utilisateur un espace virtuel compos de plusieurs espaces lin aires ind pendants r sout les probl mes de partage protection gestion des donn es de taille variable gt Ces m canismes sont compl mentaires et peuvent tre utilis s de mani re conjointe Mani res de combiner segmentation et pagination Paginer chaque segment Implantation des segments dans un grand espace lin aire que l on pagine ensuite Paginer les segments Principe Chaque segment est un espace lin aire que l on
66. ne seconde fois lors de l acc s l op rande Transformation d adresse l ex cution lors de chaque acc s gt liaison n est termin e qu au dernier moment gt permet la r implantation dynamique simple mise jour des tables de traduction Un programme peut tre partiellement pr sent en m moire physique certaines pages sont effectivement pr sentes en m moire centrale d autres ne le sont pas Les espaces virtuels et physiques n ont pas forc ment la m me taille Si on a 2 pages virtuelles et 2 pages physiques Si v gt p l espace virtuel ne tient pas enti rement en m moire physique On verra que l on peut ex cuter quand m me de tels programmes Si v lt p on peut mettre plus d un espace virtuel en m moire physique un seul accessible la fois mais plusieurs peuvent tre r sidents Protection l ex cution espaces m moire s par s 3 Pagination la demande 3 1 Principe Fonction de pagination non contiguit gt Allocation m moire simplifi e Il suffit de trouver n pages quelles que soient leurs adresses gt Mise en uvre d un m canisme de va et vient global ais e changement contenu tables de traduction 22 Constats Localit des applications gt un instant donn une application n a besoin que d un sous ensemble de ses informations Le m canisme de pagination permet de n avoir en m moire qu un sous ensemble des pages virtue
67. nes La matrice des droits est grosse et vide gt il faut trouver un moyen de stocker uniquement les cases pleines Par colonne par objet m canisme de liste de contr le d acc s liste de couples domaine droits Par ligne par domaine m canisme de capacit liste d objets accessibles par domaines 75 3 Exemple le SGF d UNIX Fichiers UNIX Suite d octets Appels syst mes lecture criture de s quences d octets positionnement dans le fichier Structure de fichiers tr s simple D finition de structures plus complexes notion d article acc s index laiss e au niveau utilisateur directement biblioth que Interface fichier utilis e pour tout objet ayant un nom externe visible dans la hi rarchie des fichiers p riph riques tubes etc Volume Repr sentation bas niveau d un disque ou d une partie de disque Organis logiquement comme une suite de blocs de taille fixe Constitue le support d un syst me de gestion de fichiers Notion de superbloc Bloc sp cial d crivant un volume Contenu d un superbloc Taille du syst me de fichiers Nombre de blocs libres Liste des blocs libres Nombre d inodes libres Liste des inodes libres Superbloc I Zone des inodes m lt Zone des fichiers V Structure d un volume UNIX Montage Op ration permettant d int grer plusieurs syst mes de fichiers dans une seule hi rarchi
68. nomsimple2 contexte environnement de d signation associe des noms simples des objets Un r pertoire est un objet particulier qui repr sente un contexte c est un environnement de d signation Il fait la correspondance entre nom externe et nom interne i node dans le cas d UNIX R pertoire nom externe nom interne chier fl r pertoire d1 d1 ai R seau de d signation la structure de la hi rarchie des fichiers constitue le r seau de d signation Dans le cas d une structure arborescente un r pertoire peut contenir la description d un fichier ou d autres r pertoires r pertoire particulier racine N est d crit dans aucun autre r pertoire f1 f3 A Environnement racine rl ee Environnement rl fl f2 d Environnement r2 fl f3 K R gle d interpr tation des noms un fichier peut tre d sign sans ambiguit en donnant le nom simple du fichier le nom du r pertoire le contenant environnements utilisables sans les nommer explicitement r pertoire racine pour les chemins d acc s absolus et r pertoire de travail pour les chemins d acc s relatifs r gles de recherche PATH permettent de d finir un ensemble de chemins d acc s utiliser dans certaines con
69. oms autoris s des contextes de d signation une relation entre un ensemble de noms lexique et un en semble d objet un r seau de d signation d finit les liens entre les contextes Op rations sur les noms Lier lier un objet O un nom N dans un contexte C R soudre r soudre un nom N dans un contexte C chercher l objet associ N dans C Exemple d signation dans le 8086 Exemple 3 domaine de d signation ensemble des octets de la m moire physique ensemble des noms adresses relatives dans l intervalle 0 216 1 contexte de d signation si le programme est implant l adresse 10000 DS 10000 0 gt 10000 1 10001 etc Environnements de d signation limit s et illimit s Environnements limit s nombre limit a priori de noms Il faut se pr occuper de la gestion des noms allocation lib ration car au cours du temps le m me nom sera utilis des fins diff rentes Exemple adresses m moire Environnements illimit s tr s grand nombre de noms On n a pas se pr occuper de la ges tion des noms Exemples noms externes de fichiers adresses m moire dans des processeurs 64 bits 1 3 R solution des noms R solution des noms statique vs dynamique R solution d un nom dans un contexte retrouver l objet associ au nom dans ce contexte Types de r solution R solution statique correspondance entre nom et objet effectu e une fo
70. ors des changements de contexte sauf champ ASID gt Changements de contexte plus longs que sans pagination rechargement TLB registre de plus sauvegarder M moire partag e ne peut pas tre utilis e directement pour communiquer Table des pages de P1 UGM Descr PI es actif Registre table des pages Descr P2 Table des pages de P2 Mod le d ex cution Plusieurs processus se partageant le m me espace virtuel Deux notions diff rentes Processus l ger thread T che comprend un espace virtuel et un ensemble de thread Pas de protection entre threads de la m me t che protection entre threads de t ches diff rentes gt change les moyens de communication entre threads partage de m moire par construction Mise en uvre Pas de contexte m moire registre de d but de table des pages dans un thread gt changement de contexte entre threads l ger Changement de contexte entre threads de t ches diff rentes plus lourd sauvegarde restauration du contexte m moire vidage du TLB Mod le d ex cution Un espace virtuel pour tous les processus Utilis dans les architectures grands espaces d adressage 64 bits 42 Jamais de changement d espace virtuel gt partage des objets en m moire tr s simple En l absence de segmentation protection des objets en m moire difficile assurer 7 Au
71. oth ques partag es doivent tre r entrantes Edition de liens dynamique gt les symboles non r solus doivent tre conserv s plus long temps qu avec une dition de liens statique R solution des liens inconnus plus tardive Principe Edition de liens statique avec une biblioth que amorce qui contient un l ment par fonction non r solue Initialisation de cette table au chargement du programme utilisant la biblioth que Exemple DLL Dynamic Link Library des syst mes Windows Production d une DLL 65 B lib p Noms des biblioth que amorce k objets export s B c PO Compilation q0 dition de liens sis ident dans dll B dll code de la biblioth que Production d un programme utilisant une DLL B lib biblioth que amorce utilisateur exe dll ident l h B dll p Ta Table d import indirection utilisateur c Compilation extern pQ dition de liens main call indir p gt pas d incorporation de la biblioth que au programme ex cutable Liaison au chargement du programme Implantation de la biblioth que dans l espace d adressage du processus r servation table des pages Chargement biblioth que si c est le premier processus l utiliser Chargement partie r sidente Initialisation table des pages pou
72. oulement du syst me Ph nom ne d croulement Premiers syst mes multiprogramm s diminution brutale des performances quand le nombre d usagers d passe un certain seuil ph nom ne dit d croulement trashing Le syst me passe tout son temps traiter des d fauts de page plut t que d ex cuter les programmes utilisateur Comportement des programmes Caract ristiques communes ind pendantes des programmes Non uniformit des r f rences aux pages la fr quence de r f rence aux pages varie d une page l autre Un petite partie des pages du programme totalise la plus grande partie des r f rences ordre de grandeur 75 des r f rences concernent moins de 20 des pages Localit temporelle pendant une p riode d ex cution un processus utilise un sous ensemble r duit de ses pages Ce sous ensemble est stable sur la p riode consid r e gt Phases de stabilit relativement longues utilisant un sous ensemble r duit de pages s par es par des phases de transition pendant lesquelles le sous ensemble des pages utilis es change brusquement Application Espresso th se S Johnstone 1997 768 576 mrn TET Us i a Rl F 193 ekkri dlm _ amme Re Heap Address Ln Kilobytes RE TEE L z o EET T t Mn Lt nn y 23 D ICB Li Z k 13 x FCO 08 9ES Number S ln struction s ln Millions Comportement des programme
73. pagine A4 Une table des pages ou hi rarchie de tables par segment Descripteur de segment contient hors taille droits l adresse physique de la table des pages du segment Adresse virtuelle nom_segment d placement_segment d placement segment interpr t comme un couple num ro page d placement_page Paginer les segments P s pv dp dresse virtuell segment e pv s V prot taille tab pg 1 pr Pages du segment 1 Descripteurs de segments Table des pages du segment Remarques 29 Force chaque segment a avoir sa propre table des pages inefficace pour les petits segments La segmentation rend inutile l allocation de la table des pages pour la taille adressable maxsi male d un segment Une adresse de num ro de segment s ne permet d acc der qu s gt bien que l on ait deux niveaux de tables il ne s agit pas d une pagination deux niveaux Partage d un segment possible en partageant sa table des pages Paginer l espace o sont implant s les segments Principe Implantation des segments dans un espace lin aire Pagination de cet espace lin aire 45 lg v base segment b Table des descripteurs lg de segments b d num segment d pl segment S d Adresse virtuelle Espace lin aire pagin
74. physique en pages physiques pages r elles de taille fixe Une adresse physique adresse r elle peut tre interpr t e comme un couple n de page physique d placement dans la page Si les pages font 2 octets et s il y a 2 pages physiques une adresse physique fait m p bits organis s de la mani re suivante 19 Adresse physique num ro page physique d placement p bits m bits Remarque 13 En g n ral On av Z p et v gt gt p Taille des adresses virtuelles gt gt taille des adresses r elles Espace virtuel adressable gt gt espace physique disponible 2 2 Fonction de pagination Mise en uvre par mat riel Unit de Gestion m moire UGM Memory Management Unit MMU Transforme chaque acc s m moire un num ro de page virtuelle en num ro de page physique Fonction non totale il peut y avoir des adresses virtuelles non traduites par la fonction de pagination Il s agit alors d une exception signal e au syst me d faut de page Deux issues lors d un appel la fonction de pagination la traduction est possible retourne l adresse physique r sultat sinon d routement pour d faut de page Num ro de page physique Num ro de Fonction de m si pas de d faut irtuell UNE PAES pagination gt Indicateur de d faut de page R num ro num ro page page physique vir
75. plusieurs centaines de Goctets temps d acc s de plusieurs dizaines de ms Notion de hi rarchie m moire objectif Objectif offrir l utilisateur l espace de la m moire la plus grande avec le temps d acc s de la m moire la plus rapide Principe on conserve tout instant l information la plus utilis e dans la m moire la plus rapide Pourquoi a marche principe de localit Definition 7 Principe de localit Localit spatiale si un l ment est r f renc un ins tant donn les emplacements voisins ont de fortes probabilit s d tre r f renc s dans un futur proche acc s a t gt probabilit forte d acc s a d t e Localit temporelle un l ment r f renc un instant a une forte probabilit d tre nouveau r f renc dans un futur proche acc s a t gt probabilit forte d acc s a t e 2 2 Principe g n ral du m canisme de cache Principe g n ral du m canisme de cache ant m moire Origine du terme la m moire rapide introduite entre le processeur et la m moire proprement dit caches mat riels Dans les faits m canisme g n ral que l on retrouve plusieurs niveaux de la hi rarchie de m moire g r enti rement par mat riel ou par logiciel ou conjointement par mat riel et logiciel comme dans la pagination la demande Principes g n raux de mise en uvre existent mais strat gies de mise en uvre diff rent
76. pr sentation des fichiers utilis s ouverts Inode m moire global tous les processus Copie de l inode disque Compteur d utilisation Verrou acc s exclusif l inode p Superbloc Zone des inodes Zone des fichiers Table des fichiers table syst me globale tous les processus contient pour chaque fichier ouvert Pointeur sur inode m moire Compteur d utilisation Droits d acc s pour cette ouverture Pointeur de fichier caract re courant Table des descripteurs de fichiers table utilisateur propre un processus Pour chaque fichier ouvert pointe sur une entr e de la table des fichiers Indices 0 1 et 2 r serv s stdin stdout stderr Ouverture d un fichier fonction open chaine nomfich acces m resultat n descripteur debut Utilise nomfich pour retrouver l inode disque et le copie en m moire si fichier inexistant ou acc s demand interdit alors r sultat erreur sinon alloue une entr e dans la table des fichiers et l initialise alloue un descripteur de fichier et l initialise 78 r sultat num ro du descripteur allou fsi fin Exemple 47 Structures de donn es lors de l ouverture d un fichier Utilisateur Syst me Table des Table des fichiers inodes m moire descripteurs 3 de fichiers 4 er 5 E 1J OI R r 7 2 B
77. pteur de segment unique gt m mes droits d acc s pour tous les utilisateurs Segment partag gt m me adresse virtuelle dans les processus le partageant Segment i Nom global i dr lg adresse Segment j Table des segments 68 Organisation de la table des segments Tables multiples Plusieurs environnement de d signation en g n ral un par processus Nom de segment nom local l environnement de d signation Segment partag peut tre vu deux adresses virtuelles diff rentes Env dr1 lg adresse Table des segments Segment i Segment j Env B T lg adresse Table des segments Organisation de la table des segments Organisations mixtes Informations ind pendantes de l environnement longueur adresse dans un descripteur cen tral unique Une table par environnement donnant les caract ristiques propres l environnement droits d acc s Ke sl drl Env Table locale des segments ka Env B Table locale des segments dr2 69 lg Table centrale des segments Segment i Segment j Cinqui me partie Syst me de gestion de fichiers 70 1 Rappels sur les SGF Syst me de gestion de fichi
78. r partie pagin e Remplissage de la table d importation avec les informations du fichier DLL Code ex cutable du programme Remarques 38 Liaison des biblioth ques m me si elles ne sont pas utilis es pendant l ex cution Solution dans les syst mes Windows liaison explicite des biblioth ques pas de liaison statique avec la biblioth que amorce ni table d indirection fonctions syst me LoadLibrary GetProcAddress FreeLibrary effort de programmation Fonctions appel es au chargement et d chargement des biblioth ques Fonctions similaires dans les syst mes UNIX dlopen diclose dlsym dlerror Principe 66 Edition de liens statique avec une biblioth que amorce qui contient un l ment par fonction non r solue Chaque r f rence externe provoque une exception pour d faut de lien d faut de page d routement vers le superviseur R solution du d faut de liens dans la routine de traitement de cette exception Chargement de la biblioth que si n cessaire Remplacement du code d clenchant l exception par un code d appel Avant appel d une fonction de la biblioth que call indir Biblioth que amorce Code ex cutable du programme Apr s appel et ventuel chargement de la biblioth que call indir 3 Espace virtuel segment 3 1 Segment
79. ra par tre la plus ancienne et donc sera vid e facile mettre en uvre LRU Least Recently Used la page victime est celle dont la derni re r f rence est la plus ancienne utilise la propri t de localit les pages utilis es r cemment ne sont pas vid es difficile mettre en uvre il faudrait maintenir une liste des pages virtuelles pr sentes tri e par date de derni re r f rence liste mise jour chaque r f rence Algorithme de la seconde chance horloge approximation de l algorithme LRU qui choisit comme victime une page non r f renc e r cemment pas n cessairement la plus ancienne ment r f renc e Utilisation du bit U mis 1 chaque r f rence la page U 1 signifie que la page a t r f renc e r cemment Si t1 on remet O le bit U de la page i la valeur de ce bit t2 gt t1 permet de d cider si la page a t utilis e ou non entre t1 et t2 tl t2 ss Ufi 0 test U i U i 0 gt page i pas r f renc e entre t1 et t2 Ufi 1 gt page r f renc e entre t1 et t2 on ordonne les pages physiques circulairement par rapport leur num ro en conservant le num ro not derni re de la derni re page vid e lors d une demande de remplacement parcours de la liste des pages physiques partir de derni re jusqu avoir trouv une page dont le bit U est 0 Pour toutes les pages entre derni re et la vic
80. ras en 10 ms fichiers de la taille moyenne 1 Ko 71 E D bit Kb sec Utilisation pourcents Taux de transfert Kb s 6 utilisation du disque 6 128 256 512 1024 2048 4096 8192 Taille de bloc octets Allocation des fichiers sur disque Allocation contigu blocs cons cutifs de la m me piste et ou pistes adjacentes diminution des nombres de mouvements du bras structure d implantation d un fichier simple d but taille difficult d allocation de l espace disque idem gestion de m moire par zones de taille quelconque Allocation non contigu blocs disque r partis sans contrainte allocation de l espace disque simple zones de taille fixe description de l implantation d un fichier sur disque est plus complexe risque d avoir plus de mouvements du bras gt d fragmentation Exemple 42 La FAT File Allocation Table MS DOS Table unique contenant les blocs disque libres les listes des blocs disque des fichiers Con u l origine pour les disquettes de 320K passe mal l chelle ne peut plus tre stock e int gralement en m moire Exemple 43 La FAT File Allocation Table MS DOS taille disque EOF 13 2 9 8 FREE Fichier A 6 _ 8 4 9 Fichier B S 9 Le 12
81. rtain droits gt comment faire 4 Pagination et gestion de fichiers Syst me de gestion de fichiers Syst me de pagination Transfert disque gt m moire explicites Transferts disque gt m moire implicites fread fwrite x y 4 i V Cache M moire E E disque centrale Pages Disque Fichiers mapp s Taille de bloc disque taille d une page virtuelle Primitive mmap UNIX tablissant une correspondance entre Une zone de m moire virtuelle Un fichier Utilisation de la zone de m moire virtuelle comme une zone standard C est l algorithme de remplacement de page qui met en uvre le cache disque 80 fonction de pagination Espace virtuel 50 51 52 pages disque 50 1144 100 5110 101 52 117 5 102 Espace virtuel Acc s la page 51 gt d faut de page Fichiers mapp s Interface UNIX void mmap void ad size_t l int prot int fl int fd off t of ad adresse de visibilit 0 gt le syst me choisit 1 longueur zone rendre visible of offset dans le fichier prot droits d acc s fl indique si en cas de modification le fichier lui m me est modifi MAP_SHARED ou si Table des Table ad Fichier M moire physiq Fichier M moire physique les modifications sont priv es au processus MAP P
82. rtuelle pr sent V indique si une page physique est associ e la page virtuelle droit bits sp cifiant les droits d acc s la page lecture criture ex cution pphys num ro de la page physique associ e si pr sent 1 et d autres informations vues plus loin Code de la fonction de pagination r alis e par mat riel type adVirt v bits pv m bits d adPhys p bits pp m bits d DPV bit present bits droit p bits pphys typeAcces lire crire var 0 2 1 DPV tpages table des pages adresse dans registre MMU function pagination adVirt adv typeAcces acces resultat adPhys begin if acces incompatible avec tpages adv pv droit then d routement pour violation de protection m moire else if tpages adv pv present 0 then d routement pour d faut de page else return tpages adv pv pphys adv d 21 end if end if end Contiguit des pages en m moire Remarque 14 Des pages contigu s dans l espace virtuel ne le sont pas obligatoirement dans l espace physique num ro num ro page page virtuelle physique 3 EE gt 6 1 3 15 M moire virtuelle M moire physique Dans le cas d un adressage indirect avec relais en m moire le relais contient une adresse virtuelle Pour acc der l op rande final on passe donc deux fois par le m canisme de pagination une premi re fois lors de l acc s au relais u
83. s plusieurs niveaux Volume occup par les tables Remarques 26 Si on utilise tout l espace virtuel avec pages de 4Ko pagination un niveau 220 x 2 22 octets de tables 4Mo pagination deux niveaux il faut en plus 2 2 octets table des hyperpages mais seuls ces 4 Ko doivent r sider en permanence en m moire physique les autres sont soumis au va et vient Si on n utilise qu une partie de l espace virtuel la pagination deux niveaux permet de ne d crire compl tement que la partie utile de cet espace exemple marqueur dans la table des hyperpages pour les zones illicites Tables des pages inverse Volume des tables directes lin aires plusieurs niveaux proportionnelles la taille des espaces virtuels adressables 40 Incompatible avec les architectures grands espaces d adressage 64 bits Table des pages inverse on stocke les informations de traduction d adresse dans la table des pages physiques Tables des pages inverse Structures de donn es pour une page physique p identification de l espace virtuel auquel elle appartient num ro de processus s il y a un espace virtuel par processus ou marqueur si page disponible num ro de la page virtuelle dans cet espace virtuel Tables des pages inverse Structures de donn es Table des pages inverse Table des pages du processus Pi du syst me 9 num ro page physique num
84. s Notion d ensemble de travail Definition 19 Ensemble de travail Un ensemble de travail working set un instant t est l ensemble des pages diff rentes r f renc es entre t T et t T repr sente la largeur de la fen tre de 33 calcul de l ensemble de travail E W T en nombre de pages T en r f rences gt gt Quand on augmente la taille de la fen tre de calcul T le nombre de pages diff rentes r f renc es croit rapidement puis tend se stabiliser Remarque 20 Si T est bien choisi assez grand pour correspondre la partie asymptotique de la courbe W t T volue en g n ral lentement et est une bonne approximation des pages qui seront utilis es dans un futur proche Origine du ph nom ne d croulement Mesure du temps moyen entre d fauts en fonction de l espace m moire disponible 4 Temps moyen entre d fauts nb r f rences Nombre de pages allou es La Met Augmentation rapide jusqu un palier Palier espace m moire suffisant pour loger l ensemble de travail Augmentation de l espace m moire au del de ce seuil est quasiment inutile 4 Temps moyen entre d fauts nb r f rences Nombre de pages allou es Met Augmentation du nombre de processus gt diminution de l espace m moire disponible par processus Si m moire disponible pour un processus passe en dessous de son Met alors l intervalle entre d
85. sation Int grit emp cher la corruption des donn es par des fautes accidentelles ou intention nelles Disponibilit l utilisateur peut acc der au service offert Fiabilit le service rendu est correct gt Domaine g n ral de la s ret de fonctionnement ici on s int ressera principalement la confidentialit et l int grit El ments n cessaires pour assurer la confidentialit et l int grit M canisme d authentification moyens de s assurer de l identit d un usager ex mot de passe M canisme de contr le d acc s moyens de limiter les acc s aux objets Politique de s curit r gles sur la fa on d accorder des droits aux usagers gt Accent mis par la suite sur les m canismes de contr le d acc s Domaines et droits d acc s Sujet entit poss dant des droits d acc s processus s ex cutant pour le compte d un uti lisateur au sens large Objet entit prot ger fichier zone de m moire etc Domaine de protection ensemble d objets accessibles un instant donn et droits d acc s associ s couples objets droits Matrice de droits droits i j ensemble des droits sur l objet j quand on est dans le domaine i Exemple 46 f1 f2 f3 imprimante Domaine 1 lire crire crire Domaine 2 lire crire lire crire Domaine 3 lire crire utiliser Repr sentation des domai
86. space des noms externes A Inclusion du nom du serveur dans les noms externes serveur usr fich Localisation du fichier triviale Migration difficile pas de transparence la localisation B Montage distance 86 Syst me de fichiers local de A Syst me de fichiers export par B 7 moi partag a A TN 7 fl f2 J f3 f4 J 7 Hi rarchie apr s montage distance de a sous le moi partag le r pertoire partag de A NT fl f2 f3 f4 Liaison nom externe localisation dynamique re calcul e chaque montage Localisation relativement simple Migration possible avec modification des s quences de montage C Espace de nommage unique ind pendant de la localisation Localisation recalcul e dynamiquement au moins chaque ouverture Migration dynamique possible gt Localisation plus complexe Localisation Noms internes doivent permettre de d signer le fichier dans tout le syst me distribu gt identificateurs uniques UID Unique Identifiers Le nom unique peut contenir une aide la localisation exemple site de cr ation Gestion des caches Envoi syst matique d une requ te au serveur inefficace latence r seau disque gt utilisation de caches Abstraction Mise en oeuvre Client1 Client2 lect ecr lect ecr lect ecr lect ecr charg recopie charg recopie Fichier f
87. t1 t2 t3 4 a p a L Sequential fits Strat gies courantes de recherche d un bloc First fit liste des trous tri e par adresse recherche du premier trou de la liste de taille gt la taille demand e Nert fit variation du first fit ou on g re la file circulairement en repartant lors de la recherche de la derni re zone allou e Best fit on recherche la plus petite zone convenable paradoxalement mauvaise utilisation de la m moire due une multiplicit de petits trous r sidus 2 4 Indexed fits Structure de donn es labor e pour m moriser les blocs libres Arbre binaire quilibr permettant de trier les blocs par taille Arbre cart sien tri la fois selon la taille des trous et leur adresse Stock e dans les trous eux m mes Segregated fits structure de donn es et algorithme d allocation diff rent par taille de bloc 51 2 5 Buddy systems On n alloue que certaines tailles de blocs Binary buddy puissances de deux Fibonacci buddy taille membres d une suite de Fibonacci Chaque bloc a son bloc compagnon buddy adjacent qui est le seul bloc avec qui il peut tre fusionn en cas de lib ration Gros taux de fragmentation interne cause des choix de tailles de blocs 8 Tmin 2 max 4 Tmin lt gt Buddies 2 Tmin Tmin 2 min Liste de trous de taille 2 Initialement listes vides sauf 274 char allouer int T
88. tems Politiques hybrides d pendante de la taille de bloc demand e 49 2 2 Bitmap Allocation par multiple de bloc de taille fix e Tmin Un bit par bloc 1 bloc occup 0 bloc libre Tmin 1111010110110000000 Bitmap Allocation Arrondir la taille demand e au Tmin Sup rieur gt taille allou e n Tmin Recherche de n blocs cons cutifs 0 puis mise 1 Lib ration V rification dans la bitmap que la lib ration correspond bien une zone allou e bits 1 Mise des bits concern s 0 11110101001100000 malloc 30 Tmin 16 11110101111100000 free p p 11110101001100000 2 3 Sequential fits Cha nage des trous dans une liste M morisation de la structure de liste dans les trous 50 Libre Allocation parcours de la liste des blocs libres Lib ration insertion dans liste des blocs libres fusion avec blocs adjacents si applicable Organisation de la liste Par adresse croissantes facilite le regroupement des zones en cas de lib ration Par taille croissante facilite la recherche d un bloc d une taille donn e Sequential fits technique pour la fusion Boundary tags pour tout bloc libre ou occup Ent te header et prologue footer contenant la taille du bloc l tat du bloc libre 0 ou occup 1
89. tif contenu typique d un DPR tat Prop tat tat d allocation libre occupp verrouill prop espace d adressage propri taire de la page pv num ro de la page dans l espace d adressage prop pv forment un lien inverse pour acc s DPV 30 PV 4 Am lioration des performances 4 1 Caches de traduction Introduction du m canisme de pagination gt ralentissement important des acc s m moire chaque acc s acc s m moire proprement dit lecture du descripteur de la page vir tuelle plusieurs cycles m moire peuvent tre utiles selon sa taille Am lioration possible bas e sur la propri t de localit et le principe du cache appliqu la table des page pendant une p riode assez longue le programme va r f rencer un petit sous ensemble de ses pages Definition 17 Cache de traduction d adresses Un cache de traduction d adresses ou TLB Trans lation Lookaside Buffer est une m moire cache mat rielle contenant les correspondances page vir tuelle page physique les plus utilis es D roulement d un acc s une page virtuelle pv 1 Recherche dans le TLB Si trouv on obtient directement le num ro de la page physique associ e pp 2 Sinon recherche dans la table des pages pour trouver la page physique associ e pp et stockage du couple pv pp dans le TLB la place d un autre couple si le TLB est plein pv trouv e
90. time choisie on remet le bit U 0 ce qui assure que l algorithme fournira bien une r ponse dans tous les cas Exemple d ex cution de l algorithme de l horloge Vk fi j 1 U k 1 27 i Ujj i U i 1 1 derni re 4 i 1 U i 1 0 derni re jl Een U j 0 U j 1 1 U jj 1 U0 11 0 victime Avant ex cution de l ARP Apr s ex cution de l ARP Remplacement de page Performances des algorithmes Performances obtenues sur des cha nes de r f rences provenant d applications r elles Taux de d fauts de pages i Taille m moire Chargement d un programme Contenu d un fichier ex cutable Description adresse en m moire et contenu des zones contenant du code et des donn es initialis es Description adresse en m moire et taille des zones contenant des donn es non initialis es Objectif du chargement Initialiser la m moire pour que le programme puisse commencer s ex cuter Sans pagination travail directement en adresse physique consiste implanter le pro gramme en m moire partir du fichier ex cutable r servation de m moire pour les diff rentes zones remplissage de ces zones partir du disque initialisation des registres du processeur SP PC Avec pagination la demande pas de chargement en m moire avant le d but de l ex cution mais la place initialisation des tables des pages Le chargement s
91. tion hyperviseur directement sur la machine h te Type II hosted couche logicielle de virtualisation au dessus du syst me h te Conformit la machine r elle Fulkvirtualization la couche de virtualisation de plateforme est suffisamment compl te pour ex cuter un syst me invit non modifi souvent type IT Para virtualization couche de virtualisation adapt e pour de meilleures performances type D 2 1 Full virtualization Full virtualization Simulation compl te d une plateforme mat rielle processeur p riph riques Couche de virtualisation au dessus du syst me h te 96 Full virtualization Principes de r alisation Processeur de l h te Z processeur de l invit simulation par logiciel du jeu d instruction de l invit lent Processeur de l h te processeur de l invit viter la simulation des instructions standard load store instructions arithm tiques et logiques simuler l ex cution des instructions non s res op rations privil gi es VMWare Transformation binaire la vol e du code x86 pour remplacer le code des instructions non s res par une simulation l int rieur de la machine virtuelle Note Sur x86 demande de placer un niveau de virtualisation sous l OS anneau de protec tion 0 pour ex cuter les instructions privil gi es Full virtualization int r ts Permet d muler un processeur diff rent de celui du m
92. tres m canismes permettant le va et vient 7 1 Adressage par registre de base Adressage par registres de base Definition 27 Adressage par registre de base sans pagniation Toutes les adresses figu rant dans les instructions ou manipul es par les instructions sont des adresses relatives Les m canismes d adressage logique indirection indexation produisent une adresse re lative adresse relative finale Seul le registre de base contient une adresse physique qui est ajout e l adresse relative finale pour produire l adresse physique i MECS Adresse relative finale Instruction d adressage logique M canismes d adressage physique adresse physique de base Registre de base Adresse physique adresse relative finale adresse physique de base D placement programme en cours d ex cution de adphys1 adphys2 modification contenu du registre de base adphys2 _ ou 10000 R implantation en 20000 code 0 20000 code 0 Registre Registre de base 19099 de base 20000 Remarques 28 On peut avoir plusieurs registres de base comme sur le 8086 CS DS SS ES 43 L existence de registres de base ne garantit pas pour autant que tout programme peut tre r implant il faut les utiliser correctement exemple ci dessous avec une r implantation entre 1 et 2 Permet la r implantation dy
93. tuelle gt fonction de j pagination eooo P Nr 23 24 10 gre la 25 d faut de page M moire virtuelle M moire physique 20 Fonction de pagination mise en uvre par table des pages lin aire Tableau avec une entr e par page virtuelle n page indice du tableau Bit de pr sence bit V indiquant si une page physique est associ e la page virtuelle sinon d routement pour d faut de page Table stock e en m moire On parle de table des pages lin aire z num ro numero Table des pages page page physique virtuelle 0 1 24 111 26 1 23 10 1 23 1110 24 10 25 V pr 11 10 d 23 d 26 adresse virtuelle adresse physique 11 d d faut de page M moire virtuelle M moire physique adresse virtuelle Ralentissement de l ex cution par rapport un syst me sans adressage virtuel Pour chaque acc s une adresse virtuelle au moins deux acc s la m moire physique 1 Un acc s la table des pages situ e en m moire pour r cup rer le num ro de page physique 2 Un acc s l emplacement contenant l information proprement dite Table des pages en m moire gt probl me d espace m moire occup et de temps d acc s M canismes de traitement de ces probl mes vus plus loin Format typique d une entr e de la table des pages DPV descripteur de page vi
94. udre sont du m me type par contre les solutions apport es peuvent tre assez diff rentes El ments consid rer Repr sentation de l tat du cache Politique de recopie Politique de remplacement Mise en uvre repr sentation de l tat du cache Division du cache et de la m moire lente en blocs de la m me taille Chargement dans le cache de blocs constitu s d emplacements contigus de la m moire lente tire partie de la localit spatiale Un m me bloc peut se trouver un instant donn la fois dans le cache et dans la m moire lente Exemple 8 Caches mat riels blocs de quelques octets Caches disques blocs de quelques secteurs 10 0 1 2 3 M moire rapide cache M moire lente less H 0 1 2 3 4 5 6 Num ro de bloc Fonction de correspondance permettant de savoir o se trouve un bloc dans le cache et s il y est charg Exemple 9 Caches mat riels fonction de correspondance simple acc s en un cycle voir plus loin Caches logiciels fonctions de correspondance peuvent tre plus complexes structures de donn es telles que des arbres des tables de hachage etc D roulement d un acc s l information la donn e demand e appartient au cache on y acc de directement dans le cache en lecture ou criture la donn e demand e n appartient pas au cac
95. ur est une structure de donn e de taille fixe qui contient la fois des informations sur la localisation de l objet nom et sur son mode d emploi protection d signation des fonctions d acc s R pertoire Table d implantation De dl fich FT add1 add2 Descripteur de fichier disque bloc disque Exemple 5 Cha ne d acc s un fichier le passage du nom externe du fichier l adresse du descripteur est r alis par l algorithme de recherche dans le r pertoire l adresse du descripteur rep re le descripteur adresse disque est obtenue par acc s au contenu de la table d implantation figurant dans le descripteur l acc s au bloc se fait partir de l adresse disque gr ce au mat riel de contr le du disque Adresse Adresse Nom i descripteur Descripteur disque externe Bloc Calcul Rep re Contient Rep re 1 4 Exemple SGF Exemple syst me de gestion de fichiers SGF Domaine de d signation fichiers et autres objets sous UNIX r pertoires fichiers sp ciaux tels que p riph riques caract re ou bloc liens symboliques tubes pipes Ensemble des noms noms dont se sert l utilisateur On parle de nom externes pour les distinguer des noms utilis s par le syst me internes Deux types de noms sous UNIX noms simples cha nes de caract res sans chemins d acc s nomsimplel nomsimple2 ou nomsimplel
96. v2 si n cessaire d pend de la strat gie de recopie 4 Reste du traitement de d faut de page pr est maintenant disponible Remplacement de page Structures de donn es N cessaire d avoir un tat d allocation des pages physiques occup es ou libres et si occup es o se trouvent les informations relatives la page virtuelle support e descripteur adresse disque Ces informations sont dans un descripteur de page physique contenant Un lien inverse vers le descripteur de page virtuelle support e pointeur ou couple processus propri taire num ro de page virtuelle Un bit de modification M indiquant si la page a t modifi e depuis son chargement en m moire un bit d utilisation U indiquant si la page a t r f renc e Remplacement de page Exemple lt O OS R N M L ARP choisit la page physique pr pour faire le remplacement l entr e pr de la table des pages physiques fournit P2 pv2 on met l entr e pv2 de la table des pages de P2 0 l entr e pui de la tables des adresses disque de P1 fournit addpv1 on fait une lecture disque depuis addpv1 vers la page physique pr on met l entr e pv1 de la table des pages de P1 1 pr on met l entr e pr de la table des pages r elles P1 pui Remplacement de page Exemple tat avant d faut 25 Espace virtuel Espace virtuel de P1 de P2 table des disque table des disque pages de P1 pour P1 pages de
97. ynamique 3 Espace virtuel segment 3 1 Segment are eue SU mat a a di Ru mes ee Sn Me dd 3 2 Organisation de la table des segments V Syst me de gestion de fichiers 1 Rappels sur les SGF 1 1 Gestion de l espace disque 1 2 Mise en uvre des acc s 1 32 D signation 19 v 4 R 079742 rebond al fn Rihanna ati E 8 me Lo 2 Le partage des fichiers 2 1 Contr le des acc s simultan s 2 28 PTOL CLIOIL G mar LR D PR AR MES Rs LA NE a RE DA l ais Ber Tae 0 16 3 Exemple le SGF d UNIX 4 Pagination et gestion de fichiers VI Gestion de l information dans les syst mes r partis 47 48 49 49 50 50 51 52 53 55 56 56 57 57 61 64 64 65 67 67 68 70 71 71 73 73 74 74 75 76 80 82 Syst mes de gestion de fichiers r partis 1 1 Propri t sd unSGFtr partti 1 2 SGF r parti l ments de mise en oeuvre 153 Exemples s 24 Les d ee 28 eh a st ete M moires virtuelles r parties 2 1 7 Principe x ha RTR sans hr BT e Lite n ape 2 2 Mod le de coh rence 2 3 El ments de mise en oeuvre VII Virtualisation 1 2 D finition et int r t Techniques de virtualisation 2 1 Full virtualization 2 2 Paravirtualization 2 3

Isabelle Puaut Septembre 2011

Contents

Download Pdf Manuals

Related Search

Related Contents