1

Memoria Virtual

Capítulo 8

2

Estructuras de Hardware y Control

• Todas las referencias a memoria son direcciones lógicas y son mapeadas a direcciones físicas en tiempo de ejecución – Recordar propiedad de Reubicación

• Un proceso puede ser particionado en páginas o segmentos los cuales no necesariamente están contiguos en memoria

• No todas las páginas o segmentos de un proceso tienen que residir en memoria principal durante su ejecución

3

Ejecución de un programa• El SO trae a memoria principal unos pocos trozos del programa• Este conjunto de páginas o segmentos (o en su defecto direcciones de

memoria) es conocido como conjunto residente • Cuando el proceso intenta accesar una dirección que no se encuentra en el

conjunto residente, se produce una falla de página (page-fault); el SO emite la interrupción apropiada

• El SO pone al proceso en un estado bloqueado y emite un requerimiento para traer los trozos que necesita– El SO emite un requerimiento de I/O a disco – Mientras tanto otro proceso de la cola de listo pasa a ejecución – Cuando el servicio de I/O está listo, el proceso vuelve a la cola de listos

4

Ventajas de este modelo

• Más procesos pueden residir en memoria– Sólo se necesita una porción de cada uno

– Con tantos procesos en memoria principal es muy probable que siempre exista un proceso en la cola de listos

• Un proceso puede ser más grande que toda la memoria principal disponible

• Memoria real– Memoria principal

• Memoria virtual– Visión lógica de la memoria,

– Espacio en disco

– Permite multiprogramación y libera al usuario de las restricciones de memoria real

5

Principio de localidad• Las referencias a lineas de código y datos en un proceso tienden a agruparse

tanto espacial como temporalmente• localidad espacial y temporal

– Ej: si acceso a[i] en tiempo t es muy probable que accese a[i+1] en t+1

• Sólo un pedazo del proceso se necesita en un momento dado• Sería posible tomar desiciones inteligentes acerca de qué pedazo necesitaría

en el futuro cercano• Esto indica que MV puede mejorar la eficiencia

• ¿Pero que pasaría si swapeo-out un pedazo del proceso justo antes de necesitarlo?

• Trashing: el SO pasa la mayor parte del tiempo en swap-in y swap-out en vez de ejecutar instrucciones de los procesos

6

MV con Paginación

• Cada proceso tiene su tabla de páginas

• Cada entrada en la tabla contiene el número de marco en memoria principal donde dicha página fue cargada

• Se usa un bit de precencia (P) (o validez) para indicar si la página está en memoria o no

• Se usa otro bit de modificación (M) (o suciedad) para indicar si la página ha sido modificada o no, desde la útlima vez que se trajo a memoria principal

• Si el bit M no ha sido seteado, entonces no es necesario escribir la página a disco (swap-out)

• Otros bits

7

• Recordar que la tabla se encuentra en memoria las tablas están también bajo el esquema de paginación

Es posible n >m

8

Esquema de tabla de dos niveles

Ej: Sistema de 32 bits, páginas de 4K, largo de cada entrada de página 4 bytes.

9

Tabla invertida de páginas

• En el esquema anterior, el tamaño de la tabla de páginas es proporcional al tamaño del espacio virtual de direcciones

• En el esquema de tabla invertida de páginas el tamaño es proporcional al tamaño del direccionamiento físico, y es independiente del número de procesos o páginas virtuales

• Usado en PowerPC, UltraSPARC, y IA-64

• El número de página es mapeado sobre la tabla invertida por una función de hashing

• Existe una entrada en la tabla invertida por cada marco (memoria física) y contiene – Número de página

– PID

– Bits de control

– Puntero a la cadena de páginas que mapean a la misma posición

10

11

Translation Lookaside Buffer (TLB)

• Cada referencia de memoria virtual puede causar dos accesos a memoria física– Uno para acceder a la tabla de páginas

– Y otro para acceder al dato mismo

• Para solucionar este problema, se usa una memoria cache de alta velocidad que almacena una parte pequeña de la tabla de páginas

• En el contexto de administración de memoria, esta memoria se conoce por TLB

• El TLB almacena el mapeo página marco de las páginas más recientemente usadas

12

TLB

• Dada una dirección virtual, el procesador examina la TLB (mapeo asociativo)

• Si la TLB contiene el mapeo de la página buscada (hit), se recupera el número de marco y se forma la direccioón física

• Si no (miss), se va a buscar a la tabla de páginas

• Luego, se chequea que la página esté en memoria principal, si no, el SO emite una interrupción con page-fault

• Finalmente, se actualiza la TLB para reflejar la nueva página

13

14

15

16

Uso de la Cache

17

Tamaño de páginas• Página pequeña menor fragmentación interna• Página pequeña se requieren más páginas por proceso tablas más grandes• Tablas más grandes una buena porción de la tabla en MV • Memoria secundaria está diseñada para transferir eficientemente grandes bloques de

datos, luego por todo lo anterior podríamos concluir que es mejor tener páginas más grandes

• Página pequeña número grande de páginas en memoria• A medida que el proceso se ejecuta, las páginas en memoria tendrán porciones del

proceso cercanos a referencias recientes• Páginas muy grandes, se pierde la localidad temporal y espacial más page fault

18

19

Segmentación

• Particiona la memoria (virtual y real) en segmentos de tamaño variable

• La partición es desde un punto de vista funcional de los programas.

• Ventajas:– Simplifica el manejo de estructuras de datos dinámicas

– Permite que los programas sean modificados y recompilados independientemente

– Facilita compartición de datos entre procesos

– Facilita protección

20

Tabla de segmentos

• Contiene la dirección en memoria real donde está el segmento

• Cada entrada contiene el largo del segmento

• Se usa un bit para determinar si el segmento está en memoria o no

• Se usa otro bit para indicar si el segmento ha sido modificado desde la última vez que se cargó en memoria principal

21

22

Paginación y segmentación combinadas

• Tanto paginación como segmentación tienen ventajas y desventajas

• Por ejemplo, paginación es transparente al usuario y elimina segmentación externa.

• Segmentación es visible al programador y facilita compartición y protección

• Segmentación con paginación (segmentos paginados) divide la MV en segmentos los cuales son paginados.

• El tamaño y el número de segmentos es generalmente una decisión del programador, pero las páginas son del mismo tamaño que un marco, es decir es una desicón de hardware

23

24

Política de fetch• Determina cuándo una página es cargada en memoria principal• Paginación por demanda: se trae una página a memoria sólo cuando se hace

una referencia a memoria que está dentro de dicha página– Muchos fallos de páginas al comienzo

• Prepaginación: junto con la página que no está, se traen otras páginas– Explota la característica de los dipositivos de I/O que favorece traer bloques

contiguos– Es posible que la (o las) página adicional no se necesite

25

Política de ubicación

• Determina dónde ubicar una página en memoria real

• Es importante en segmentación pues afecta fragmentación externa

• No es tan importante en paginación, pues la fragmentación interna sería la misma independiente del lugar donde se cargue

26

Política de reemplazo

• Determina qué página es reemplazada, cuando no hay marcos libres

• En teoría, debieramos sacar aquella página que minimiza los fallos de página, que corresponde a la página menos probable de ser referenciada en el futuro

• Cerrado de marcos (frame locking):– Cuando un marco está cerrado, no puede ser considerado para reemplazo

– SO, buffers de dispositivos de I/O

– Se usa un bit de cerradura (locking) para indicar si un marco está cerrado o no

27

Algoritmos básico de reemplazo

• Algoritmo óptimo– Selecciona la página para la cual el tiempo hasta la próxima referencia es el más

largo

– Imposible predecir cuándo la página será referenciada en el futuro

– Sirve como referencia para evaluar otros algoritmos de reemplazos

• Least Recently Used (LRU)– Selecciona la página que no ha sido referenciada durante más tiempo

– Por el principio de localidad, la página seleccionada por LRU debiera ser aquella que es menos probable de ser referenciada en el futuro cercano

– La implementación perfecta de LRU requeriría que cada página tenga asociado el tiempo de la última referencia, lo cual sería muy costoso, ¿por qué?

– Una alternativa es mantener un stack de referencia a páginas y reemplazar la que está en el fondo del stack

28

Algoritmos básicos de reemplazo

• FIFO– Se reemplaza la página que lleva más tiempo en memoria

– Uno de los algoritmos más simples de implementar

– Pero cuidado, la página que recien salió puede necesitarse nuevamente (principio de localidad)

– No tiene buen rendimiento respecto de los otros algoritmos de reemplazo

• Política del reloj: – Una forma de aproximar LRU, pero eficientemente

– Se usa un bit de uso para cada marco

– Cuando el marco se carga con una página, se setea el bit en 1

– Cuando la página es referenciada, se setea el bit en 1

– Cuando es necesario reemplazar una página, se busca en orden secuencial el primer marco con bit de uso en 0; dicha página es reemplazada

– Durante la búsqueda los bits de uso en 1 son cambiados a 0

– ¿Qué pasa si todos los bits están en 1?

29

30

* Indica bit de uso en 1

31

Anomalía de Belady

• En ciertas circunstancias, al aumentar el número de páginas disponibles, el número de fallo de páginas aumenta.

• Considere la siguiente secuencia de referencias a páginas:– 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

• Con 2 marcos, se producen 12 fallos de página con FIFO

• Con 3 marcos, 9 fallos

• Con 4 marcos, 10!

• Con 5 marcos, 5.

32

Comparación algoritmos de reemplazo

33

Buffering de página

• La página reemplazada es agregada a una de dos listas dependiendo si fue modificada o no:– Si no fue modificada : a lista de páginas libres (se agrega en la cola)

– Si fue modificada: a lista de páginas modificadas (se agrega en la cola)

• La nueva página se carga en el marco que está en la cabeza de la lista de libres

• Note que la página que se reemplaza permanece en memoria

• Este método hace más eficiente el swap-out de las páginas modificadas, pues se escriben en grupos y no de a una a la vez

• Esto requiere que el SO mantenga siempre un pequeño conjunto de páginas “realmente libres”

34

Tamaño del conjunto residente

• Tamaño fijo– Asigna un número fijo máximo de marcos a un proceso

– Cuando ocurre un fallo de página, se reemplaza una de las páginas de dicho proceso

• Tamaño variable– El número de marcos asignados a un proceso puede cambiar durante la vida de

éste.

– Por ejemplo, si un proceso está experimentando continuamente fallos de páginas, el SO podría hacer crecer su conjunto residente.

– De la misma forma, si un proceso parece no tener fallos de páginas, el SO podría reducir su conjunto residente

35

Reemplazo/Conjunto residente

Reemplazo Local Reemplazo Global

Tamaño conjunto residente fijo

Decidir anticipadamente cuantos marcos asignar a un proceso.

Si el conjunto es muy pequeño alta tasa de fallo de páginas

Si el conjunto es muy grande bajo nivel de multiprogramación

No es posible

Tamaño conjunto residente variable

Un proceso se inicia con un número de marcos basado en tipo de aplicación, prioridades, etc.

Cuando ocurre un fallo de página, se selecciona un marco usado por el mismo proceso

De vez en cuando, aumentar o disminuir el conjunto residente para mejorar el rendimiento global del sistema

Mas simple y popular

Como el marco puede se cualquiera, el conjunto residente de los procesos cambia con el tiempo

36

Política de limpieza

• Indica cuándo una página que ha sido modificada debe escribirse a memoria secundaria

• Limpieza por demanda– Se escribe a disco sólo cuando ha sido seleccionada para reemplazo

– Implica dos transferencias a memoria secundaria por fallo de página

• Pre-limpieza– Se escribe a disco antes que sea seleccionada para reemplazo.

– Varias páginas se escriben a la vez, en lotes

– Es posible que la página se modifique justo después de ser escrita en dico

37

Control de carga y trashing

• Determina el número de procesos que residen en memoria principal, es decir el nivel de multiprogramación

• Si son muy pocos, es muy probable que en algún momento todos estén bloqueados por I/O y el procesador esté inutilizado

• Si son muchos, el tamaño del conjunto residente será muy pequeño causando altas tasas de fallos de páginas. Esto conduce a trashing

38

Suspensión de procesos

• Determina cuál de los procesos residentes es suspendidos y así reducir el nivel de multiprogramación

• Proceso con prioridad más baja – No tiene relación con el rendimiento del sistema

• Proceso que produce el fallo– Es razonable pensar que este proceso no tiene su conjunto de trabajo residente en

memoria principal, por lo tanto será bloqueado de todas maneras

• Último proceso activado– Como este proceso recién comienza, es probable que aún no tenga su conjunto de

trabajo residente en memoria

• Proceso con el conjunto residente más pequeño– Más barato de volver a traer a memoria. ¿Qué pasa si este no es aquel proceso

que produce los fallos?

• Proceso más grande– Obtiene el número más grande de marcos libres

39

UNIX and Solaris Memory Management

• Paging System– Page table

– Disk block descriptor

– Page frame data table

– Swap-use table

40

41

42

43

UNIX and Solaris Memory Management• Page Replacement

– Refinement of the clock policy

44

Kernel Memory Allocator• Lazy buddy system

45

Linux Memory Management

• Page directory

• Page middle directory

• Page table

46

47

48

Windows Memory Management

• Paging– Available

– Reserved

– Committed