Antecedentes Memoria virtual – separación de la memoria lógica de la

física Sólo parte del programa necesita estar en memoria en

un momento dado para continuar su ejecución El espacio de direcciones lógicas puede ser mayor que

el espacio de direcciones físicas Permite compartir espacios de direcciones entre

procesos Permite una creación de procesos más eficiente

La memoria virtual suele implementarse usando: Paginación por demanda Segmentación por demanda

Paginación por Demanda Trae una página a memoria sólo cuando hace falta

La E/S se reduce Se requiere menos memoria La respuesta es más rápida Puede haber más procesos en memoria

Se necesita una página la página es referenciada referencia inválida aborta no está en memoria se trae a memoria

“Intercambiador” perezoso – nunca trae una página a memoria salvo si es necesario El intercambiador que trabaja con páginas es un paginador

Bit de Validez En cada entrada de la tabla de páginas hay un bit de validez

(v en memoria, i no en memoria o acceso ilegal) Al comienzo el bit de validez es inicializado a i en todas las

entradas Ejemplo de tabla de páginas:

Durante la traducción de direcciones, si el bit de validez de la entrada de la tabla de páginas es i fallo de página

vvv

v

i

ii

….

# Marco Bit de validez

Tabla de páginas

Fallo de Página La primera referencia a una página producirá una

excepción capturada por el SO: fallo de página1. El SO mira en la tabla de páginas para decidir qué

hacer: Referencia inválida aborta No está en memoria continúa

2. Obtiene un marco libre3. Carga la página en el marco4. Resetea las tablas5. Establece el bit de validez a v6. Reinicia la instrucción que causó el fallo de página

Fallo de Página Instrucciones problemáticas para el reinicio de instrucción

Instrucciones de cadenas

Auto incremento/decremento Soluciones

Comprobar antes de ejecutar la instrucción que no va a producirse un fallo de página

Almacenar los valores antiguos en registros temporales Guardar el estado del microcódigo del procesador

Rendimiento de la Paginación por Demanda Tasa de fallo de páginas 0 p 1

si p = 0, no hay fallo de páginas si p = 1, cada referencia produce un fallo

Tiempo de acceso efectivo (EAT)EAT = (1 – p) x acceso a memoria

+ p (sobrecarga por fallo de página + escribir página + traer página + sobrecarga de reinicio

)

Ejemplo de Paginación por Demanda Tiempo de acceso a memoria = 200 ns

Promedio del tiempo de servicio de un fallo de páginas = 8 ms

EAT = (1 – p) x 200 + p x 8.000.000 = 200 + p x 7.999.800

Si uno de cada 1.000 accesos causa un fallo de páginas EAT = 8,2 μs El tiempo de ejecución se reduce en un factor de 41!!

Qué Pasa Si No Hay Marco Libre?

Reemplazo de páginas – encuentra una página en memoria que no se esté usando y la retira se usa un algoritmo de reemplazo objetivo – minimizar el fallo de páginas

La misma página podría ser traída a memoria varias veces

Reemplazo de Páginas Previene la sobreasignación de memoria modificando la rutina de

fallo de páginas para incluir el reemplazo de páginas

Se usa el bit de modificado (suciedad) para reducir la sobrecarga por transferencias de páginas – sólo las páginas modificadas se escriben a disco

El reemplazo de páginas completa la separación entre la memoria lógica y la memoria física – se puede proporcionar una gran cantidad de memoria virtual sobre una menor memoria física

Reemplazo de Páginas Básico1. Encontrar la ubicación de la página deseada en

disco

2. Encontrar un marco libre: - Si hay un marco libre, usarlo - Si no hay un marco libre, usar un algoritmo de reemplazo para escoger el marco víctima

3. Traer la página deseada al (nuevo) marco libre; actualizar las tablas de páginas y de marcos

4. Continuar con la ejecución del proceso

Algoritmos de Reemplazo de Páginas

El objetivo es una tasa de fallos de página lo más baja posible

Los algoritmos se evalúan ejecutándolos sobre una cadena de referencias a memoria y calculando el número de fallos de página producidos con esa cadena

En todos nuestros ejemplos, la cadena de referencias será

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Algoritmo First-In-First-Out (FIFO) Cadena de referencias: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 marcos (3 páginas en memoria por proceso)

4 marcos

Anomalía de Belady: más marcos más fallos de página

1

2

3

1

2

3

4

1

2

5

3

4

9 fallos de página

1

2

3

1

2

3

5

1

2

4

5 10 fallos de páginas

44 3

Algoritmo Óptimo Reemplaza la página que será usada más tarde Ejemplo con 4 marcos

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

En general, no conocemos los accesos futuros a memoria Este algoritmo se usa para estudiar el rendimiento de otros

1

2

3

4

6 fallos de página

4 5

Algoritmo (LRU, Least Recently Used)

Cadena de referencias: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Implementación con contador Cada entrada de página tiene un contador; cada vez que

la página es referenciada se copia la hora en el contador Cuando una página necesita ser cambiada, se miran los

contadores para determinar cuál se cambia

5

2

4

3

1

2

3

4

1

2

5

4

1

2

5

3

1

2

4

3

Algoritmo LRU Implementación con pila – se mantiene una pila de números de

página: Cuando una página es referenciada:

Se mueve a la cabeza de la pila En el reemplazo se escoge la página de la cola de la pila

Algoritmos de Aproximación al LRU Bit de referencia

Con cada página se asocia un bit, inicialmente puesto a 0

Cuando se referencia una página el bit se pone a 1 Se reemplaza la página con el bit a 0 (si hay alguna)

Esto no permite conocer el orden de uso Algoritmo de segunda oportunidad

Necesitamos un bit de referencia También se denomina algoritmo de reloj Si la página a reemplazar (de acuerdo al orden del

reloj) tiene el bit de referencia a 1: Se pone el bit a 0 Se deja la página en memoria Trata de reemplazar la siguiente página siguiendo el

orden del reloj

Algoritmos de Conteo Se necesita un contador con el número de referencias

que se han hecho a cada página

Algoritmo LFU: reemplaza la página con el valor más bajo en el contador

Algoritmo MFU: reemplaza la página con el valor más alto en el contador Se basa en el argumento de que la página con el

número más pequeño en el contador acaba de ser traída y aún no se usa

Asignación de Marcos Cada proceso necesita un número mínimo de páginas; ese

número depende de la máquina Ejemplo: IBM 370 – se pueden necesitar hasta 6 páginas

para una instrucción SS MOVE: La instrucción ocupa 6 bytes, podría requerir 2 páginas 2 páginas para la cadena origen 2 páginas para el destino

Esquemas principales de asignación Asignación fija Asignación por prioridad

Asignación Fija Asignación equitativa – Por ejemplo, si hay 100 marcos y 5

procesos, se le da a cada proceso 20 marcos Asignación proporcional – Asigna marcos de acuerdo al

tamaño del proceso

mS

spa

m

sS

ps

iii

i

ii

para asignación

marcos de totalnúmero

proceso del tamaño

5964137

127

564137

10

127

10

64

2

1

2

1

a

a

s

s

m

Asignación por Prioridad Usa un esquema de asignación proporcional basado

en las prioridades en lugar del tamaño

Si el proceso Pi produce un fallo de páginas, Escoge para reemplazar uno de sus marcos Escoge para reemplazar un marco de un proceso

con menor prioridad

Asignación Local y Global Reemplazo global – se escoge para reemplazar un

marco de cualquier proceso; un proceso puede tomar un marco de otro

Reemplazo local – se escoge para reemplazar un marco del proceso que necesita la página

Hiperpaginación Si un proceso no tiene suficientes páginas, la tasa de fallos

de página es muy alta. Esto lleva a: Uso bajo de CPU El SO piensa que necesita aumentar el grado de

multiprogramación Otro proceso se añade al sistema

Hiperpaginación un proceso está ocupado trayendo y retirando páginas de memoria

Hiperpaginación

Paginación por Demanda e Hiperpaginación

Por qué funciona la paginación por demanda?Modelo de localidad Los procesos migran de una localidad a otra Las localidades pueden solaparse

Por qué ocurre la hiperpaginación? tamaño de la localidad > tamaño de la memoria

Modelo de Conjunto de Trabajo ventana del conjunto de trabajo un número fijo de

referencias a páginas Ejemplo: 10.000 instrucciones

WSSi (conjunto de trabajo del proceso Pi) =número total de páginas referenciadas en la ventana más reciente (cambia con el tiempo) Si es demasiado pequeño no abarcará toda la

localidad Si es demasiado grande abarcará varias

localidades Si = abarcará el programa entero

D = WSSi total de marcos requeridos Si D > m Hiperpaginación Política si D > m, se suspende un proceso

Siguiendo la Pista al Conjunto de Trabajo

Se aproxima con un temporizador y un bit de referencia Ejemplo: = 10.000

El temporizador interrumpe cada 5000 unidades de tiempo

Se mantienen en memoria 2 bits por página Cuando el temporizador interrumpe copia el bit de

referencia y lo pone a 0 Si uno de los bits en memoria es 1 la página está en

el conjunto de trabajo Mejora: 10 bits e interrumpir cada 1000 unidades de

tiempo

Frecuencia de Fallos de Página Es otra forma de evitar la hiperpaginación Se busca conseguir una tasa de fallos de página aceptable

Si la tasa actual es demasiado baja, el proceso pierde un marco Si la tasa actual es demasiado alta, el proceso gana un marco

Prepaginación Prepaginación

Se usa para reducir el gran número de fallos de página que ocurre al comienzo de un proceso

Consiste en traer a memoria todas o algunas de las páginas que necesitará un proceso antes de que las referencie

La páginas prepaginadas pueden no ser utilizadas, hay gasto de memoria y E/S

Asumimos que s páginas son prepaginadas y una fracción α de esas páginas son usadas Es el coste de los s * α fallos de página ahorrados > o

< que el coste de prepaginar s * (1- α) páginas innecesarias?

Si α es cercano a cero la prepaginación no interesa

Tamaño de las Páginas Para la selección del tamaño de página hay que

tener en cuenta: La fragmentación interna El tamaño de la tabla de páginas La sobrecarga de E/S La localidad

Estructura del Programa Estructura del Programa

int data[128][128]; Cada fila se almacena en una página Programa 1

for (j = 0; j <128; j++) for (i = 0; i < 128; i++) data[i][j] = 0;

128 x 128 = 16,384 fallos de página

Programa 2 for (i = 0; i < 128; i++) for (j = 0; j < 128; j++) data[i][j] = 0;

128 fallos de página

Interbloqueo de E/S Interbloqueo de E/S – A veces las páginas

deben bloquearse en memoria

Las páginas que se están usando para copiar un fichero de un dispositivo deben bloquearse para que no sean escogidas por un algoritmo de reemplazo de páginas

Windows XP Usa paginación por demanda con agrupamiento (clustering). El

clustering trae a memoria páginas adyacentes a la página que falló

A los procesos se les asigna un conjunto de trabajo mínimo y máximo

El conjunto de trabajo mínimo es el mínimo número de páginas del proceso que van a estar con seguridad en memoria

A un proceso se le pueden asignar páginas hasta que llegue a su conjunto de trabajo máximo

Cuando la cantidad de memoria libre en el sistema cae por debajo de un umbral, se hace un recorte automático del conjunto de trabajo para restaurar la cantidad de memoria libre

El recorte del conjunto de trabajo retira páginas de los procesos que tienen un número de páginas mayor que el mínimo

Solaris Mantiene una lista de marcos libres para asignar a los procesos

que fallan Lotsfree – umbral (cantidad de memoria libre) para comenzar la

paginación Desfree – umbral para incrementar la paginación Minfree – umbral para comenzar el intercambio La paginación la realiza el proceso pageout Pageout escanea las páginas usando una variante del algoritmo de

reloj (algoritmo de reloj modificado) Scanrate es la tasa a la que las páginas son escaneadas. Este valor

va entre slowscan y fastscan Pageout se llama más frecuentemente dependiendo de la cantidad

de memoria libre