8.Memoria Virtual

7/26/2019 8.Memoria Virtual

1/49

Memoria virtual


2/49

2Memoria virtual

Tabla de contenidos (T11)

Introduccin a la M.V. Ventajas

Cuestiones relacionadas con la M.V. Implementacin hardware stado de un proceso en memoria Car!a din"mica #a!inadores

$iperpa!inacin Modelo del conjunto de trabajo de un proceso

%recuencia de &allos de p"!ina Mecanismos de asi!nacin ' liberacin de M# l!oritmos de !estin de la memoria virtual #olticas de asi!nacin

#olticas de ubicacin


3/49

*Memoria virtual

Tabla de contenidos (ii)

#olticas de b+s,ueda #olticas de reempla-o de p"!inas

Cadenas de re&erencia l!oritmo ptimo l!oritmo %I% nomala de /elad' l!oritmo 0(Least Recently Used) l!oritmos de apro3imacin al 0 l!oritmo del reloj !lobal

l!oritmo %I% con se!unda oportunidad l!oritmo 4% (Not Frequently Used) Caso de estudio5

Mach *.6 0inu3 728


4/49

9Memoria virtual

Introduccin a la M.V. (i)

Concepto5 1:;1 < %otherin!ham

#ermite la ejecucin de procesos5 Car!ados parcialmente en memoria principal ' ma'ores ,ue la memoria principal disponible

=e basa en el principio de localidad de lasre&erencias

=lo se mantiene en memoria principal> lain&ormacin ,ue se necesite en cada momento l control lo reali-a el =..


5/49

?Memoria virtual

Introduccin a la M.V. (ii)Ventajas

Transparencia en las trans&erencias5dispositivo de almacenamiento < memoria principal

0os procesos pueden tener un !ran tama@o>limitado por tama@o del espacio dedireccionamiento virtual o el tama@o del disco duro

umenta el !rado de multipro!ramacin>se pueden ubicar m"s procesos en memoria aumento del rendimiento del sistema

educe la A=>

no se car!a todo el pro!rama en memoria principal


6/49

;Memoria virtual

Cuestiones relacionadas con la M.V. (i)

BCmo se detecta si la in&ormacin re&erenciada seencuentra o no en M# /it de presencia en la TD#

=i la in&ormacin no est" en M# Bcmo se locali-aen el disco Tabla de mapa de archivos

=i toda la M# est" ocupada Bdnde se ubica elnuevo blo,ue de in&ormacin sando un al!oritmo de reempla-o cercano al 0

B0a estrate!ia de asi!nacin de -onas de memoriadebe ser local o !lobal 4IE5 Flobal 0inu35 0ocal


7/49GMemoria virtual

Cuestiones relacionadas con la M.V. (ii)Implementacin hardware

=e usan mecanismos de pa!inacin ' se!mentacin n es,uema pa!inado presenta ventajas5

Trans&erencias disco < M# m"s simples> se trabaja conblo,ues de tama@o Hjo

#olticas de ubicacin m"s simples> blo,ues i!uales

e,uerimientos hardware5 Festin de tabla de p"!inas (T0/s> #/T#> 0T#) Festin de bits en los descriptores de p"!ina5

/it de presencia /it de re&erencia /it de modiHcacin (dirty bit)

=oporte para interrumpir instrucciones lmacenamiento secundario para p"!inas de un

proceso


8/49Memoria virtual

1?661

1?6621?66*1?669

JJJ

2G*?62G*?12G*?22G*?*

JJ

Cuestiones relacionadas con la M.V. (iii)stado de un proceso en memoria

spacio de

direccionamiento virtual

/C

D%F$I

KL0

M

spacio de

direccionamiento real

$J

JJ0

5

2

0

6

TD#p

J

J

J

p

J

J

p

JJ

J

p

J

Tabla mapade archivos


9/49:Memoria virtual

?ctuali-ar la

tabla de p"!inas

Cuestiones relacionadas con la M.V. (iv)Car!a din"mica

#ro!rama

=. .

Memoriaprincipal

Marco libre

6 6

Tabla dep"!inas

0D M

1

e&erencia

;einiciar lainstruccin

2

3cepcin

* 0a p"!ina est"en memoria au3iliar

9Car!ar lap"!ina ,ue&alla

Memoriasecundaria

p m


10/4916Memoria virtual

Cuestiones relacionadas con la M.V. (v)Car!a din"mica

%allo de p"!ina5 la p"!ina re&erenciada no est" en M#

0os tiempos ,ue m"s a&ectan a la car!a din"micason5 0os cambios de conte3to

=alvar una p"!ina modiHcada a disco (page out) Car!ar la p"!ina re&erenciada en M# (page in)

ncontrar un marco libre o liberarlo Car!ar la p"!ina de disco a M#

l proceso pasa al estado de blo,ueado mientras se

actuali-a la in&ormacin de disco ' M# va DM

4+mero de marcos

Tasa de &allos de p"!ina

0a tasa de &allos de p"!inadisminu'e cuando aumentael n+mero de marcos



Cuestiones relacionadas con la M.V. (v)#a!inadores

#arte del = ,ue mueve p"!inas5 disco < M# #roporciona las rutinas para hacer las

trans&erencias cuando se produce un &allo =e crean ' se destru'en con el objeto pro'ectado

en MV Tipos de pa!inadores5

(dependiendo de los objetos pro'ectados en M#) De archivos (p. ej.5 mmap> e3ec) De objetos annimos o swap pager(!estin del area

de swap) bjetos ,ue no tienen una ima!en en el sistema de

archivos

De dispositivos (p. ej.5 !estin del frame buer)



$iperpa!inacin (i) (Thrashing)

$iperpa!inacin5 0os procesos robanN los marcos de p"!ina unos a

otros ' el sistema intercambia constamententein&ormacin disco < M#

=oluciones5 educir la multipro!ramacin l!oritmo de reempla-o local o por prioridades si!nar a cada proceso los marcos ,ue necesite

Modelo del cjto. de trabajo strate!ia de la &recuencia de &allos de p"!ina

Frado demultipro!ramacin

$iperpa!inacin

endimientodel sistema


13/49

1*Memoria virtual

$iperpa!inacin (ii)Modelo del conjunto de trabajo de un proceso

Conjunto de p"!inas ,ue deben estar en

almacenamiento primario para la ejecucin eHca-de un proceso

=e basa en la localidad de re&erencias Mantiene alto el !rado de multipro!ramacin %ormado por las p"!inas recientemente accedidas

durante una ventana de tiempo (7)4O de p"!inas enel cjto. de trabajo

Tiempo


14/49

19Memoria virtual

$iperpa!inacin (iii)%recuencia de &allos de p"!ina

=e establece un lmite superior e in&erior para la

#%%

lmite superior

lmite in&erior

Incrementar eln+mero de marcos

Decrementar eln+mero de marcos

4+mero demarcos

%recuencia

de &allosde p"!ina


15/49

1?Memoria virtual

Mecanismos de asi!nacin ' liberacin(i)

si!nacin de M#5 Determinan el n+mero de marcos a asi!nar al

proceso activo l m"3imo est" deHnido por la ar,uitectura /ajo nO marcos muchos &allos de p"!ina>

hiperpa!inacin lto nO marcosdesaprovechamiento de la M#

0iberacin de M# l = mantiene el conjunto de marcos libres ' libera>

a partir de un umbral> los ,ue no son necesarios strate!ias5

eempla-o local eempla-o !lobal


16/49

1;Memoria virtual

Mecanismos de asi!nacin ' liberacin(ii)0iberacin de M# eempla-o local5

=e libera un marco asi!nado al proceso ,ue provoc el &allo Ventaja5 4O de &allos de los pro!ramas es m"s determinista Inconvenientes5

=aber nO de marcos necesario en cada instante por proceso

Desaprovechamiento de la M# si la car!a del sistema es baja jemplos5 VM=> 7indows 4T> 28 ' E#

eempla-o !lobal5 =e libera un marco asi!nado cual,uier proceso del sistema Ventaja5 Mejor aprovechamiento de la M# Inconvenientes5

l nO de &allos de los pro!ramas es menos determinista #uede llevar a la hiperpa!inacin

jemplo5 4IE


17/49

1GMemoria virtual

Mecanismos de asi!nacin ' liberacin(iii)

1

*

*

*

9

*

9

*

1

#2

#1

#1

2?;

1629 Lb

2?;

12

#1

12

12

12 ;9

#2

;9

#2

#2

;9

;9

#9

#9

#*

#*

#*

#*

#*

12

12

12

12

12

?12

?12

?12

?12

?12

?12

?12

1629 Lb

2?;

Inicial

#1 pide G6

#2 pide *?

#* pide 6

Devuelve#1

#9 pide ;6

Devuelve#2

Devuelve#9

Mecanismos para contabili-ar la M# utili-ada '

libre5 Mapa de bits de los marcos de memoria #oco

eHciente 0istas enla-adas de marcos5 libres> modiHcados> con

6s> etc. j. 728

=istema /udd'

/lo,ues libre


18/49

1Memoria virtual

l!oritmos de !estin de la memoriavirtual

#oltica de asi!nacin5 BPuQ cantidad de memoria

real se asi!na a un proceso activo #oltica de ubicacin5 BDnde puede ubicarse un

blo,ue en memoria principal #oltica de b+s,ueda5 BCu"ndo ' ,uQ blo,ues traer

del almacenamiento secundario a M# #oltica de reempla-o5 BPuQ blo,ue debera

sustituirse al traer a memoria principal un nuevoblo,ue si no ha' memoria libre


19/49

1:Memoria virtual

#olticas de asi!nacin

Determinan el n+mero de marcos a asi!nar al

proceso activo l!oritmos5

si!nacin e,uitativa si!nacin proporcional si!nacin prioritaria


20/49

26Memoria virtual

#olticas de ubicacin

MQtodos utili-ados para identiHcar dnde debe

ubicarse un blo,ue en M# #olticas de ubicacin5

n pa!inacin5 Indi&erenteN

n se!mentacin5 First t! el primero ,ue sirva Ne"t t! el si!uiente ,ue sirva #est t! el ,ue mejor se adapte

$orst t! el ,ue peor se adapte


21/49

21Memoria virtual

#olticas de b+s,ueda

Determinan cu"ndo ' ,uQ p"!inas se traen de disco a

M# strate!ias5 #a!inacin por demanda5

=e car!an las p"!inas en M# se!+n se van necesitando Ventajas5

n M# slo ha' lo ,ue se necesita 0a sobrecar!a de la decisin de ,uQ p"!inas traer a M# es

mnima

#a!inacin anticipada o prepa!inacin5 =e car!an la p"!inas en M# se!+n una prediccin Trata de evitar los retardos por &allos de p"!ina Ventajas5

=i la prediccin es buena> el tiempo de ejecucin de losprocesos se reduce considerablemente


22/49

22Memoria virtual

#olticas de reempla-o de p"!inas (i)

Deciden ,uQ pa!inas deben sustituirse en M#

cuando se necesita m"s memoria bjetivo5

Minimi-ar el n+mero total de &allos de p"!ina Tasa de &allos uno por cada 16; < 2 3 16G accesos

btener el m"3imo aprovechamiento de la M#

Criterios para valorar la calidad de los al!oritmosde sustitucin5 /aja sobrecar!a =in ajustes (%No tuning&)' en m",uinas con distintas

conH!uraciones pro3imacin al 0 (menos usada recientemente)

# lti d l d " i (ii)


23/49

2*Memoria virtual

#olticas de reempla-o de p"!inas (ii)Cadenas de re&erencia

0os al!oritmos de reempla-o minimi-an &allos de

p"!ina Cadenas de re&erencia5

0istas de re&erencias a p"!inas para evaluar lacalidad de los al!oritmos de reempla-o

btencin de las cadenas de re&erencia5 rtiHcialmente> de &orma pseudoaleatoria Frabando una tra-a de ejecucin

jemplo (#"!inas de 166h palabras)5 6166> 69*2> 6161> 6;12> 6162> 616*> 6169> 6161>

6;11> 6162> 616*> 6169 6161> 6;16> 6162> 616*>6169> 6161> 6;6:> 6162> 616?

Cadena de re&erencias5 slo se considera el n+mero de p"!ina ' los casos ,ue

pueden causar &allos de p"!ina 1> 9> 1> ;> 1> ;> 1> ;> 1> ;> 1

# lti d l d " i (iii)


24/49

29Memoria virtual

#olticas de reempla-o de p"!inas (iii)l!oritmos de reempla-o de p"!inas

3isten di&erentes al!oritmos> entre ellos5 l!oritmo ptimo l!oritmo %I% l!oritmo 0 l!oritmos de apro3imacin al 05

l!oritmo del reloj !lobal l!oritmo %I% con se!unda oportunidad l!oritmo 4%


25/49


26/49


27/49


28/49

#olticas de reempla o de p"!inas ( iii)


29/49

2:Memoria virtual

#olticas de reempla-o de p"!inas (viii)l!oritmo del reloj !lobal

=e colocan todas las p"!inas ,ue pueden ser

sustituidas en una lista circular n proceso de sistema borra los bits de re&erencia

cada cierto tiempo utili-ando un puntero !iratorio =i en la si!uiente vuelta el bit si!ue desactivado> la

p"!ina puede ser sustituida jemplo5 9.* /=D con 2 punteros

G

2

16

?

26

1; 1

*

9

:#"!inas

#olticas de reempla-o de p"!inas (i3)


30/49

*6Memoria virtual

#olticas de reempla-o de p"!inas (i3)l!oritmo %I% con se!unda oportunidad

mplea un bit de re&erencia asociado a cada

p"!ina #asos del al!oritmo5

1. =e eli!e una p"!ina con criterio %I% ' se e3aminasu bit de re&erencia =i R 1> entonces R 6 ' se trata la p"!ina como si

se acabara de lle!ar a memoria. Volver a 1 =i R 6> se sustitu'e la p"!ina

Feneralmente se implementa mediante una cola

%I% circular con las p"!inas car!adas Ventaja5 Combina sencille- ' buen rendimiento Inconveniente5 #uede de!enerar en un %I% puro si

todas las p"!inas han sido re&erenciadas


31/49

#olticas de reempla-o de p"!inas (3i)


32/49

*2Memoria virtual

#olticas de reempla-o de p"!inas (3i)l!oritmo 4% (Not Frequently Used)

l!oritmo ,ue simula por so&tware el al!oritmo 0 #or cada interrupcin de reloj5

=e incrementa un contador asociado a cada p"!ina si R 1

R 6

=i ha' un &allo de p"!ina se eli!e la p"!ina con elvalor mnimo del contador para su sustitucin

#roblema5 =i una p"!ina se us mucho> no ser"sustituida aun,ue 'a no se acceda a ella

=olucin5 mecanismos ,ue enveje-can los contadores Despla-ar los contadores 1 bit a la derecha antes de

a@adir el bit de re&erencia @adir el bit de re&erencia al bit del e3tremo i-,uierdo

del contador

#olticas de reempla-o de p"!inas (3ii)


33/49

**Memoria virtual

#olticas de reempla-o de p"!inas (3ii)l!oritmo 4% (Not Frequently Used)

1

1 1

6 6 1 11

2

6

6 1 2 * 9 ? ;G

?C

1 6 1 6 6 6 6 6

2 9 * 1 6 6 1

21

1 2 2

6

*

2

6

*

6

*

9

9

2

6 6

*

2

1

2

6

*

6

*

6

*

2

*

6

*

stado Hnal

1

6

*

2

1

G

1

6

G2

6

2

1

6

2

1S interrupcinde reloj


*S interrupcinde reloj


*

6 1 2 * 9 ? ;G

6C

6 6 6 6 6 6 6 6

6 6 6 6 6 6 6

G

6

G

1

6

G

1 1 11 1

1 1 1

6 6 61 16 6 6

2 1 1

: &allos de p"!ina

G 6 1 2 6 * 6 9 2 * 6 * 2 1 26


34/49

*9Memoria virtual

Caso de estudio5 Mach *.6

#osee un al!oritmo %I% con se!unda oportunidad tili-a tres colas de p"!inas5

Cola de p"!inas libres Cola de p"!inas activas Colas de p"!inas inactivas

n demonio denominado pa!eoutN muevep"!inas5 Desde la cola de p"!inas activas a la cola de p"!inas

inactivas Desde la cola de p"!inas inactivas a la de p"!inas

libres


35/49

*?Memoria virtual


0as colas activa e inactiva son %I% 0as p"!inas ,ue est"n en la cola inactiva ' son

re&erenciadas> se pasan a la cola activa

Cola libre

Cola activa Cola inactiva

0ocali-acin #a!eout =can

#a!eout =can

e&erencia


36/49

*;Memoria virtual


Despertar pa!eoutN5

if (free_queue_pages < vm_page_free_min) {

resume pageout;

}

Cdi!o base de pa!eoutN5

while ((free_queue_pages < vm_page_free_target){

if(page->referenced)

move page from inactive queue to active queue

else

move page from inactive queue to free queue

}

while (inactive_queue_pages < vm_page_inactive_target)

{

move page from active queue to inactive queue

and clear the reference bit

}


37/49

*GMemoria virtual

Caso de estudio5 0inu3

4iveles de tablas en 0inu3

4ivel 1 4ivel2 4ivel*Despla-amiento

#"!ina#"!ina

#"!ina

#FD

Tabla dep"!inas

Tabla dep"!inas

Tabla dep"!inas

#"!ina

&sica


38/49

*Memoria virtual


Memoriavirtual

del proceso

Datos

Cdigo

tasstruct

*mareastruct

peraciones dememoria virtual

open ( )close ( )

swapout()swapin

( )

vmUendvmUstartvmUa!svmUinode

vmUops

vmUne3t

vmUendvmUstart

vmUa!svmUinode

vmUops

vmUne3t

*mareastruct

countp!d

mmap

mmstruct

mm


39/49

*:Memoria virtual


Marco 1

Marco 2

Marco 0

Marco 3

Marco 4

Memoria fsica

Marco 5

Libre

Libre

Libre

Libre

Libre

Marco 6

Marco 7

Marco 8

count

age

map_nr= 70

mem_map_t

count

age

map_nr= 4

mem_map_t

3

2

4

1

0

free_area

count

age

map_nr= 0

mem_map_t

map

C d di i


40/49

96Memoria virtual


Apertura proecci!n "e# programa sobre

#as $reas "e memoria %irtua# "e# proceso

&a##o "e p$gina

'Acceso #ega#(

&a##o "e p$gina #ega#

')ntra"a %aca en #a *+(

Acceso i#ega#,

)n%iar se-a#

./.) a#

proceso

'irecci!n #ega#(

o

o

.

*raer p$gina

"es"e e#

arci%o en

"isco

.

*raer p$gina

"es"e e#

$rea "e

intercambio

o

Paginacinbajo

demanda

C d di 0i


41/49

91Memoria virtual


Festin del "rea de intercambio5 n demonio de intercambio (swapd) se encar!a de

mantener suHcientes marcos libres swapd se ejecuta como un hilo del n+cleo

activ"ndose en el arran,ue del sistema swapd cada se!undo comprueba si el n+mero de

marcos libres es demasiado bajo. =i es as> buscamarcos ,ue puedan ser descartados o sustituidos

l!oritmo implementado en el demonio5 al!oritmo deapro3imacin al 0 con envejecimiento

C d t di 0i


42/49

92Memoria virtual


TQcnica de envejecimiento de p"!inas5 l asi!nar un marco de p"!ina se le asocia por

de&ecto edad * 0as p"!inas rejuvenecen al acceder a ellas (edadW*

hasta un m"3imo de 26) Cada ve- ,ue se ejecutaswapd envejece las

p"!inas en 1 si no se usan 0as p"!inas vctimas para los intercambios se eli!en

de entre las p"!inas viejas (edad 6) ' modiHcadas 0a &uncin apuntada por *mops+,swapout>

correspondiente a la re!in de memoria(*mareastruct) > !estionar" el paso de la p"!inavctima a disco.

C d t di 0i


43/49

9*Memoria virtual


=i una p"!ina modiHcada se lleva a disco5 su entrada en la tabla de p"!inas se marca como inv"lida se inclu'e la in&ormacin para su recuperacin posterior ' se libera> a@adiQndola en la freearea

0as p"!inas no modiHcadas no se sustitu'en5 se descarta su contenido

se marcan como libres> a@adiQndolas en la freearea =i se recuperan suHcientes p"!inas del proceso

seleccionado> el demonio dormir" de nuevo =i no se liberan suHcientes p"!inas del proceso

actual> se contin+a con el si!uiente proceso l demonio empe-ar" en la p"!ina si!uiente en una

nueva activacin

C d t di 0i


44/49

99Memoria virtual


+$gina 0

+$gina 1

+$gina 2

+$gina 3

+$gina 0

+$gina 1

+$gina 2

1

2

0

*ab#a "e p$ginas A

BV BR BM

1 0

1 1

1 0

0 0

*ab#a "e p$ginas

+roceso A

+roceso BV BR BM

0 0

3

41 0

1 0

+$gina 0

+$gina 1

+$gina 3

+$gina 1

+$gina 2

Memoria fsica

Marco 0

Marco 1

Marco 2

Marco 3

Marco 4Marco 5

C d t di 0i


45/49

9?Memoria virtual


+$gina 0

+$gina 1

+$gina 2

+$gina 3

+$gina 0

+$gina 1

+$gina 2

1

0

*ab#a "e p$ginas A

BV BR BM

1 0

0 1

1 0

0 0

*ab#a "e p$ginas

+roceso A

+roceso BV BR BM

0 0

3

0 0

1 0

+$gina 0

+$gina 1

+$gina 3

+$gina 1

Memoria fsica

)"a" "e #os marcos "e p$gina

7 0 3 0

0 1 2 3 4

kswapd

sap

1

2

1

0 2 4

free_area

C d t di 72L


46/49

9;Memoria virtual

Caso de estudio5 72L

l !estor de memoria virtual de 74T utili-a un

al!oritmo de reempla-o de p"!inas local tipo %I% 0a poltica de reempla-o sustitu'e la p"!ina m"s

anti!ua del conjunto de p"!inas del proceso ,uecaus el &allo

Conjunto de trabajo ($-)5 n+mero de p"!inas ,ueel proceso tiene !aranti-adas en memoria mientrasse est" ejecutando

+$ginas nue%as +$ginas antiguas 9on:unto

"e

traba:o

C d t di 72L


47/49

9GMemoria virtual


l crearse un proceso se le asi!na un tama@o

mnimo del 7= l !estor vara el tama@o de los 7= de los procesos

se!+n los re,uirimientos de memoria5 Incrementa la memoria libre del sistema (recorte

autom.tico del $-) de un proceso si su tama@o esma'or ,ue el mnimo

Incrementa el tama@o del 7= hasta un m"3imo si elproceso !enera &allos de p"!ina ' la memoria no est"demasiado llena

=i el proceso re,uiere m"s p"!inas> se eliminanp"!inas de su 7= empleando el al!oritmo %I%

C d t di 72L


48/49

9Memoria virtual


0as p"!inas eliminadas del 7= pueden volver a Ql

r"pidamente sin reali-ar lectura del disco #ermanecen en memoria en uno de estos estados5

-tandby5 el proceso utili-a el marco de p"!ina peroha sido eliminado del 7=

/odicado5 R -tandby pero el proceso ha escrito enla p"!ina sin actuali-acin de disco

9on:unto "e traba:o

#ista "e p$ginas

en stan"b o

mo"ifica"as

Caso de estudio 72L


49/49


Lista "e

marcos

.tan"b

Lista "e

marcos

.tan"b

)scritor

"e marcos

mo"ific,

Lista "e

marcos

Mo"ific,

Lista "e

marcos

Mo"ific,

Lista

"e

marcos

#ibres

Lista

"e

marcos

#ibres

;.

"e

procesos

;.

"e

procesos

.ustituci!n

en e# ;.

&ina#i?a e# proceso

Lectura "e p$gina "e# "isco o n@c#eo&a##o "e

p$gina

cero

8.Memoria Virtual

Documents

Transcript of 8.Memoria Virtual