mémoire  

virtuelle

1
l Définition

l Mémoire  virtuelle =  support de  l'ensemble  des

informations  potentiellement accessibles.

l Ensemble  des  emplacements  dont  l'adresse  peut  être

engendrée par le processeur.

l L'espace  d'adressage  d'un  processus,  généré  par  les    

compilateurs  constitue  la  mémoire  virtuelle  du  processus  
ou  espace  d'adressage  logique.
Mémoire  physique =  Ensemble  des  emplacements
RAM  physiquement  présents  dans  l'ordinateur.
Pourquoi  une  mémoire  virtuelle  ?
Mémoire  physique coûteuse.Mémoire  secondaire
(disques,  mémoire  étendue,  ...)  peu  coûteuse.

Programmes  gourmands  en  mémoire  et  qui  ne  "tiennent  

pas"  toujours  en  RAM.

Utiliser  la  mémoire  secondaire  "comme"  mémoire  RAM.  

Donc  La  mémoire  virtuelle  est  une  technique  qui  
permet  d'exécuter  des  programmes  dont  la  taille  excède  
la  taille  de  la  mémoire  réelle  :  

à le  SE  conserve  en  mémoire  centrale  les  parties  

utilisées  des  processus  et  stocke,  si  nécessaire,  le  reste  
sur  disque  

5
Sans  recours  à  la  mémoire  virtuelle,  un  processus  est  
entièrement  chargé  à  des  adresses  contiguës

Avec  le  recours  à  la  mémoire  virtuelle,  un  processus  

peut  être  chargé  dans  des  pages   non  contiguës.

6
 La  pagination

•   La  mémoire  virtuelle  et  la  mémoire  physique  sont  structurées  

en  unités  d’allocations  

(pages pour  la  mémoire  virtuelle  

et
cases  ou  cadres pour  la  mémoire  physique).

7
•   La  taille  d’une  page  est  fixe  et  égale  à  celle  d’une  case.  
Elle  varie  (en  générale)    entre  512  octets  et  8  Ko.

Le  format  de  l’adresse  virtuelle  est  :

(numéro  de  page,  déplacement  dans  la  page)

8
•   Il  n’y  a  pas  de  fragmentation  externe  car  toutes  les  
pages  sont  de  même  taille.

•   Par  contre,  il  peut  y  avoir  une  fragmentation  interne  si  la  
dernière  page  de  l’espace  d’adressage   logique  n’est  pas
pleine.

9
 Adresses    

Adresse  d'une  information  :

Chaque  information  est  repérée  par  son  adresse,  c'est  à  
dire  le  numéro  de  son  premier
octet.  

Cet  adressage  en  termes  d'octets  permet  d'adresser,  de  

repérer,  en  mémoire  tous  types  d'information,  quelque  soit  
leur  taille.  

On  peut  ainsi  adresser  un  simple  octet

(un  char  en  langage  C),  un  mot  sur  deux  octets  (un  short  en  langage  
C),  etc.

10
 Table  des  pages

• La  correspondance   entre  les  pages  et  les  cases  est  

mémorisée  dans  une  table  appelée  table  des  pages.  

• Le  nombre  d’entrées  dans  la  table  est  égal  au  nombre  

de  pages  virtuelles.

11
• La  table  des  pages  d’un  processus  doit  être  (en  
totalité  ou  en  partie)  en  mémoire  centrale  lors  de  
l’exécution  du  processus.  

• Elle  est  nécessaire  pour  la  conversion  des  

adresses  virtuelles  en  adresses  physiques.

12
• Chaque  entrée  de  la  table  des  pages  est  
composée  de  plusieurs  champs,  notamment  :

13
• Les  bits  de  protection,  définissent  le  niveau  de  protection  de  la  
page,  en  particulier  si  elle  est  partagée  et  quels  sont  ses  droits  
d’accès

• Le  bit  de  présence,  positionné  si  la  page  est  présente  en  MC

• Le  bit  de  référence,  positionné  à  chaque  accès  à  la  page  et  

remis  à  0  à  chaque  interruption  d'horloge

• Le  bit  de  modification  (M),  indique  que  la  page  a  été  modifiée  
par  rapport  à  sa  version  sur  disque

• Le  numéro  de  case  dans  la  MC  correspondant   à  la  page

14
 Conversion  d’adresses  virtuelles  
l La  relation  entre  les  
adresses  virtuelles  et  
physiques  est  
indiquée  dans  la table  
des  pages

l Dans  l’exemple,  un  

ordinateur  peut  produire  
des  adresses  sur  16  bits  
(64  Ko)  mais  il  n’y  a  que  
32  Ko  de  mémoire  
physique.

l La  mémoire  virtuelle  est  

divisée  en  pages  de  4K

l La  mémoire  physique  est  

divisée  en  cadre  de  4k  
(page  frame)
15
L’adresse  virtuelle  
20500=5*4096+20  
est  transformée  en  adresse  physique  
12308=3*4096+20
Fonctionnement  interne  d'une  MMU  avec  16  pages de  4Ko  
et  une  RAM  de  32  ko

La  MMU  reçoit,  en  entrée  une  adresse  virtuelle  et  envoie  en  
sortie  l'adresse  physique ou  provoque  un  déroutement.

Dans  la  figure  précédente,  nous  avons  16  pages virtuelles  

de  4096 octets  chacune  à les  adresses  virtuelles  varient  
de  0  à  
16x4096-­1=24x212-­1   =216 -­1à l’adressage  se  fait  sur  16
bits

4  bits  pour  le  numéro  de  la  page  à 24 =  16  pages
12  bits  pour  adresser  l’ensemble   des  4096  octets  d’une  
17
page
• Pour  les  adresses  physiques:  nous  avons  8
pages  de  4096 octets  chacune  :  soit  23 x  212 =  215  
adresses  à l’adressage  se  fait  sur  15  bits.

18
L’adresse  virtuelle  sur  16  bits  qui  arrive  au  MMU  
est  divisée  en  deux  parties:  un  numéro  de  page  
sur  4 bits  et  un  décalage  sur  12 bits

19
• La  MMU  examine  l'entrée  dans  la  Table  de  
pages  correspondant  au  numéro  de  page,

• Si  le  bit  de  présence  est  à  0,  la  page  n'est  pas  
en  mémoire  MC    alors  le  MMU  provoque  un  
déroutement  et  le  processeur  est  rendu  au  SE.  

• Le  SE  charge  la  page  demandée

20
• Si  le  bit  de  présence  est  à  1, Rappelons  l’adresse  
physique  est  sur  15  bits

• il  détermine  l'adresse  physique  en  recopiant  dans  les  3  

bits  de  poids  le  plus  fort  le  numéro  de  case  
correspondant  au  numéro  de  page  virtuel  (  3  bits  car  le  
nombre  de  pages  physiques  8=23)  auxquels  sont  ajoutés  
les  12  bits  de  décalage,  qui  sont  copiés  à  partir  de  
l’adresse  virtuelle  sans  être  modifiés

à Ils  forment  ensemble  une  adresse  physique  sur  15  bits

21
• L'adresse  virtuelle  8196=0010 0000  00000100 (en  binaire)  

Donc page  Virtuelle  =  2=010  chargée  dans  la  case  6=110

Donc  l'adresse  physique =  110  0000  00000100  =  24580

22
 Algorithmes  de  remplacement  de  page

• A  la  suite  d'un  défaut  de  page,  le  système  d'exploitation   doit  
ramener  en  mémoire  la  page  manquante  à  partir  du  disque.  

• S'il  n'y  a  pas  de  cadres  libres  en  mémoire,  il  doit  retirer  une  
page  de  la  mémoire  pour  la  remplacer  par  celle  demandée.  

• Si  la  page  à  retirer  a  été  modifiée  depuis  son  chargement  en  

mémoire,  il  faut  la  réécrire  sur  le  disque.  

23
• Quelle  est  la  page  à  retirer  de  manière  à  minimiser  le  
nombre  de  défauts  de  page  ?  

24
 Algorithme  de  remplacement  optimal  (Algorithme  de  
Belady)

• Cet  algorithme  et  le  meilleur  possible,  car  il  minimise  le  nombre  de  
défauts  de  page

• Le  SE  indexe  chaque  page  par  le  nombre  d'instructions  qui  seront  
exécutées  avant  qu'elle  ne  soit  référencée.  

• En  cas  de  nécessité,  le  SE  retire  la  page  d'indice  le  plus  élevé,  c'est  à  
dire  la  page  qui  sera  référencée  dans  le  futur  le  plus  lointain.

• Cet  algorithme  est  pratiquement  impossible  à  appliquer  (comment  

calculer  les  indices  des  pages  ?).  

• Toutefois,  avec  un  simulateur,  on  peut  évaluer  les  performances  de  cet  
algorithme  et  s'en  servir  comme  référence  pour  les  suivants  
25
 Exemple: Soit  un  système  avec  3  cases  de  RAM  et  une  
suite  de  références  w  =    {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}.
La  suite  de  références  est  constituée  de  la  liste  des  numéros  des  
pages  virtuelles  accédées  dans  le  temps,

Représentation  de  la  RAM

Chaque  élément  de  ligne  i  et  colonne  j  montre  la  page  chargée  dans  la  
case  i  après  avoir  été  référencée.  

26
 Remplacement  de  la  page  non  récemment  utilisée  
(NRU,  Not  Recently  Used)

• Cet  algorithme  utilise  les  bits  R  et  M  associés  à  chaque  page  pour  
déterminer  les  pages  non  récemment  utilisées.

• Le  bit  R  est  positionné  à  1  chaque  fois  qu'une  page  est  référencée  

(accédée)  .  Le  bit  R  est  remis  à  0  à  chaque  interruption  d'horloge

• Le  bit  M  est  positionné  lorsque  la  page  est  modifiée  (elle  n'est  plus  
identique  à  sa  copie  sur  disque).

27
• Lorsqu'un  défaut  de  page  se  produit,  l'algorithme  NRU  
sélectionne  la  page  à  retirer  en  procédant  comme  suit  :

-­ Il  vérifie  s'il  existe  des  pages  non  référencées  et  non  

modifiées  (R=0 et  M=0).  Si  c'est  le  cas,  il  sélectionne  une  
page  et  la  retire.

-­ Sinon,  il  vérifie  s'il  existe  des  pages  non  référencées  et  
modifiées  (R=0 et  M=1).  Si  c'est  le  cas,  il  sélectionne  une  
page  et  la  retire  (une  sauvegarde   sur  disque  de  la  page  
retirée  est  nécessaire).

-­ Sinon,  il  vérifie  s'il  existe  des  pages  référencées  et  non  
modifiées  (R=1 et  M=0).  Si  c'est  le  cas,  il  sélectionne  une  
page  et  la  retire.

-­ Sinon,  il  sélectionne  une  page  référencée  et  modifiée  et  la  
retire  (R=1  et  M=1).  Dans  ce  cas,  une  sauvegarde  sur  disque  
28
de  la  page  retirée  est  nécessaire.
On  peut  organiser  l’ensemble   des  pages  ainsi:

• Classe  0:  Non  référencée,  non  modifiée

• Classe  1:  Non  référencée,  modifiée
• Classe  2:  Référencée,  non  modifiée
• Classe  3:  Référencée,  modifiée

L’algorithme  NRU  enlève  une  page  au  hasard  dans  la  

classe  la  plus  basse  non  vide

29
 Remplacement  de  page  FIFO

• Il  mémorise  dans  une  file  FIFO  les  pages  

présentes  en  mémoire.

• Lorsqu'un  défaut  de  page  se  produit,  il  retire  la  plus  
ancienne,  c'est  à  dire  celle  qui  se  trouve  en  tête  de  
file.

• Ce  n’est  pas  une  bonne  stratégie  : Son  critère  

n’est  pas  fondé  sur  l’utilisation  de  la  page

30
• Anomalie  de  Belady  (  contre  exemple  de  belady)
pour  FIFO

• Intuitivement,  on  peut  imaginer  que  plus  il  existe  de  

cadres,  moins  il  y’a  de  défauts  de  pages.

• On  réalité,  on  peut  rencontrer  des  exemples  où  en  

augmentant  le  nombre  de  cadres  on  augmente  le  
nombre  de  défauts  de  page  au  lieu  de  le  diminuer.

31
Anomalie  de  Belady:
Exemple  avec  3  cadres

Nombre  d'accès:  20

Fautes  de  page:  15
(75%)

Exemple  avec  4    cadres

Nombre  d'accès:  20

Fautes  de  page:  16
(80%)

32
 Remplacement  de  la  page  la  moins  récemment  utilisée  
(LRU  =  Least  Recently  Used)

• Remplace  la  page  dont  la  dernière  référence  remonte  au  

temps  le  plus  lointain      (le  passé  utilisé  pour  prédire  le  futur)

• En  raison  de  la  localité  des  références,  il  s’agit  de  la  
page  qui  a  le  moins  de  chance   d’être  référencée

33
Exemple  LRU  avec  3  cases

7012  0304  2303  2120  1701

Nombre  d'accès:  20
Fautes  de  page:  12  
(60%)

Même  exemple  avec  FIFO

Nombre  d'accès:  
20
Fautes  de  page:  
15
(75%)

34
 Algorithme  de  l’horloge  (seconde  chance)

• Semblable  à  FIFO,  mais  les  cadres  qui  viennent  d’être  utilisés  (bit=1)  ne  sont  
pas  touchés  (deuxième  chance)

• les  pages  en  mémoire  sont  mémorisées  dans  une  liste  circulaire  en  
forme  d'horloge

• Un  indicateur  pointe  sur  la  page  la  plus  ancienne

• Lorsqu’un  défaut  de  page  se  produit,  les  pages  sont  examinées,  une  
par  une,  en  commençant  par  celle  pointée  par  l’indicateur.

• La  première  page  rencontrée  ayant  son  bit  de  référence  R  à  0  est  

remplacée.  Le  bit  R  de  la  page  ajoutée  est  à  1.

• Si  le  bit  R  d’une  page  examinée  est  1,  il  est  mis  à  0.

35
36
 Écroulement  du  système

• Si  le  système  passe  plus  de  temps  à  traiter  les  défauts  de  page  qu'à
exécuter  des  processus  on  peut  avoir  des  problème  de  l'écroulement  du
système.

• Si  le  nombre  de  processus  est  trop  grand,  

à l'espace  propre  à  chacun  sera  insuffisant    à ils  passeront  alors  leur  
temps  à  gérer  des  défauts  de  pages.  

C'est  ce  qu'on  appelle  l'écroulement  du  système.

37
• On  peut  limiter  le  risque  d'écroulement  en  surveillant  le  
nombre  de  défauts  de  page  provoqués  par  un  processus  

• Si  un  processus  provoque  trop  de  défauts  de  pages  (au-­

dessus  d'une  limite  supérieure)   on  lui  allouera  plus  de  
pages  ;;  au-­dessous  d'une  limite  inférieure,  on  lui  en  
retirera.

• S'il  n'y  a  plus  de  pages  disponibles   et  trop  de  défauts  de  
pages,  on  devra  suspendre  un  des  processus.

38
 La  segmentation

Dans  un  système  paginé,  l'espace  d'adressage  virtuel  d'un  

processus  est  à  une  dimension.

Or  en  général,  un  processus  est  composé  d'un  ensemble  

d'unités  logiques  :
– Les  différents  codes  :  le  programme  principal,  les  procédures,  les  
fonctions  bibliothèques.
– Les  données  initialisées.
– Les  données  non  initialisées.
– Les  piles  d'exécution.(  les  valeurs  de  retour  des  fonctions)

L'idée  de  la  technique  de  segmentation  est  d'avoir  un  

espace  d'adressage  à  deux  dimensions.
39
• Dans  cette  solution,  l'espace  d'adressage  d'un  processus  est  
divisé  en  segments,  générés  à  la  compilation.  

• Chaque  segment  est  repéré  par  son  numéro  S  et  sa  longueur  
variable L.  

• Un  segment  est  un  ensemble  d'adresses  virtuelles  contiguës.

40
• Contrairement  à  la  pagination,   une  adresse  n'est  plus  
donnée  de  façon  absolue  par  rapport  au  début  de  
l'adressage  virtuel;;  une  adresse  est  donnée  par  un  couple  
(S  ,  d),  où  S  est  le  n° du  segment    et  d  le  déplacement  
dans  le  segment,  d  ∈ [0  ,  L  [  .

• Pour  calculer  l'adresse  physique,  on  utilise  une  table  des  

segments :

41
 S d

.............

B L p

descripteur de segment
............

table des segments

B  : adresse  de  base  (adresse  physique  de  début  du  segment)

L  : longueur  du  segment  ou  limite
p  : protection  du  segment

L'adresse  physique  correspondant  à  l'adresse  virtuelle  (S  ,  d)  sera  donc    B  +  d,  si  d  
<=  L

La  segmentation  simplifie  la  gestion  des  objets  communs  (rangés  chacun  dans  un  
42
segment),  notamment  si  leur  taille  évolue  dynamiquement.
• La  segmentation  peut  être  combinée  avec  la  pagination   :
Chaque  segment  est  composé  d’un  ensemble  de  pages.

• Les  adresses  virtuelles  sont  des  triplets  :

(numéro  du  segment,  numéro  de  page,  déplacement  dans  la  page)

43