Paginación por demanda y Fallos de Páginas

De Departamento de Informatica
Saltar a: navegación, buscar

Contenido

Paginación por demanda

La paginación por demanda es un sistema de paginación con el cual, además de las ventajas de la paginación convencional, se busca disminuir los tiempos de respuesta y aumentar la cantidad de programas en memoria. Para lograr estos objetivos se hace uso de un intercambiador perezoso (llamado paginador) el cual carga a memoria solo las páginas que serán utilizadas por el programa en ejecución, de esta manera se logra un menor tiempo de carga y un ahorro en cuanto a espacio utilizado por dicho programa, ya que, por un lado, no necesitamos que todo el programa este en memoria para comenzar su ejecución mientras que, por otra parte, al no estar el programa completo en memoria, disminuimos considerablemente el espacio que éste ocupa.

Ya que el paginador solo busca las páginas que se necesitan para ejecutar algún programa, debemos agregar un bit que nos diga si las referencias de memoria son válidas o no, de lo contrario, al no encontrar una página no podríamos diferenciar si el paginador aún no la carga o si esta es realmente una referencia inválida.

Paginación por demanda


El proceso que se sigue es el siguiente:

  1. Se intenta leer la página requerida
  2. Si la página requerida ya esta en memoria, simplemente se lee.
  3. Si no está en memoria, revisa si la referencia es válida.
  4. Si la referencia es inválida, se aborta.
  5. Si la referencia es válida, se intenta cargar la página.
  6. Cuando la página sea cargada, se reintenta la instrucción.


Al buscar una página, si esta no está en memoria, necesitará ser cargada. A este proceso se le llama fallo de página.


Al iniciar la ejecución de un programa, la tabla de páginas cuenta con todas sus entradas inválidas por lo cual el paginador fallará hasta tener lo necesario para iniciar el programa. Luego de esta carga inicial se comprobará si la siguiente página a utilizar ya está en memoria, en caso de que la página se encuentre, ésta es leída, pero cuando la página no es encontrada (y es una referencia válida) tenemos dos posibilidades:

  • Si existe un frame libre, se carga y se lee.
  • Si no tenemos frames libres, se intercambia la página de algún frame por la información a utilizar.


El criterio utilizado para seleccionar qué página será intercambiada varía dependiendo de la implementación del sistema. Muchos de los problemas que presenta el sistema de paginación por demanda son debido a los fallos de página y principalmente a saber cuál es la página más conveniente para intercambiar. Esto se debe a que no podemos saber cuales páginas serán utilizadas prontamente y cuales no se volverán a utilizar, existen variados algoritmos que buscan aminorar este problema, los cuales, serán analizados más adelante.


Ventajas

A continuación se verán algunas de las ventajas de utilizar paginación por demanda:

  • Al no cargar las páginas que no son utilizadas ahorra memoria para otras aplicaciones.
  • Al mejorar el uso de la memoria, mejora el grado de multiprogramación.
  • Carga inicial más rápida ya que solo lee del disco lo que se utilizará.
  • Capacidad de hacer funcionar programas que ocupan más memoria que la poseída.
  • COW (Copia en escritura): Permite utilizar las mismas páginas para dos procesos (padre-hijo) hasta que uno de estos las modifique.

Desventajas

La paginación por demanda puede llevarnos a las siguientes situaciones:

  • Debido a la sobre-asignación podemos quedarnos sin frames libres para agregar nuevas páginas, si esto sucede debemos recurrir a un reemplazo.
  • Cada fallo de página requiere cargar a memoria una página a leer, si ocurren muchos fallos de página el rendimiento empeora notablemente.
  • Las páginas que son sacadas de los frames por intercambio pueden volver a ser llamadas, lo que ocasiona que se lea en múltiples ocasiones la misma información.


Como vemos, los grandes problemas del sistema de paginación por demanda son a causa de los fallos de página y como estos son tratados. A continuación profundizaremos sobre estos.


Fallos de páginas

Como hemos visto anteriormente, cuando un proceso requiere una página que no está en memoria se genera un fallo de página. La gran mayoría de las dificultades de la paginación por demanda se deben a cómo los fallos de página son tratados.

Gestión de un fallo de página

En primer lugar, para que los fallos de página puedan ser tratados correctamente necesitamos un sistema que sea capaz de reiniciar una instrucción, de esta manera pasará lo siguiente:

  • Una instrucción necesita una página que no está en memoria.
  • Se genera fallo de página (No se puede satisfacer la instrucción).
  • Se carga a memoria la página requerida.
  • Se reinicia la instrucción

Como vemos en este proceso existe una carga a memoria, éste es uno de los factores determinantes para saber si la paginación por demanda es conveniente o no, puesto que, en el peor de los casos, puede existir una carga en memoria por instrucción lo que nos daría tiempos de ejecución mucho peores que con una paginación regular.

Rendimiento de la paginación por demanda

Para calcular el tiempo de acceso efectivo (tae) de un sistema de paginación por demanda debemos conocer los siguientes datos:

  • p: Probabilidad de que ocurra un fallo de página (0<p<1)
  • am : Tiempo de acceso a memoria. Si no existen fallos de página el tiempo de acceso estará dado solo por el tiempo de acceso a memoria de una paginación normal, que es el doble de un acceso a memoria (un acceso a la tabla de páginas y otro a la dirección de memoria).
  • fp: Tiempo de fallo de página: Si existe un fallo de página se debe leer del disco la página solicitada y luego acceder a ésta, este proceso tiene los siguientes pasos:
  1. Se encuentra la referencia inválida.
  2. Se guarda el contexto del proceso.
  3. Se verifica que la dirección de memoria sea válida.
  4. Se lee del disco la página necesitada.
  5. Se corrige la tabla de página y demás tablas.
  6. Restablecer el contexto y reiniciar la instrucción.

En todo este proceso se puede perder aún más tiempo ya sea por la complejidad de la instrucción, errores de lectura del disco u otros. Debido a esto, la CPU, puede ser asignada a otro proceso mientras ser obtiene la página a utilizar.

Entonces con estos datos tenemos: tae = (1-p)\cdot am + p \cdot fp

Del planteamiento anterior notamos que el tiempo de un fallo de página (mseg) es mucho mayor al tiempo de acceso de memoria (nseg), por lo cual la paginación por demanda, en términos de tiempo, no será conveniente.

Aún a pesar de todas estas dificultades los sistemas de paginación por demanda son muy utilizados puesto que los beneficios que nos dan son mucho mayores a la disminución de velocidad, siempre y cuando podamos mantener el promedio de fallos de paginación a solo uno entre millones de accesos.




Tratamiento de fallos de páginas

Para lograr un rendimiento aceptable del sistema de paginación por demanda debemos mantener la tasa de fallos de página al mínimo. Existen diferentes enfoques para su disminución:

Algoritmos para el reemplazo de páginas

Ejemplo de Algoritmo Óptimo

Cuando debemos cargar una página a memoria pero tenemos todos los frames ocupados necesitamos reemplazar el contenido de alguno de ellos por la información requerida. Para seleccionar cual es la mejor opción para hacer este cambio existen los siguientes algoritmos:


  • Algoritmo óptimo: Consiste en quitar de memoria la página que no será utilizada en más tiempo. Es solo un algoritmo teórico, su implementación es imposible pues no podemos saber el futuro. Sirve para analizar los demás algoritmos al compararlos con este.
    Ejemplo de Algoritmo FIFO


  • FIFO (First in first out): Como su nombre lo indica, la primera página que fue cargada a memoria es la primera en salir de esta. Su implementación es simple e intuitiva, se utiliza una cola para ordenar las páginas pero, al solo priorizar el orden de entrada es ineficiente. La anomalía de Belady nos muestra que al agregar frames pueden ocurrir más fallos de página pues se puede quitar del archivo de paginación información que es fuertemente usada solo por el hecho de haber ingresado antes.
    Ejemplo de Algoritmo LRU


  • LRU (Least recently used): Plantea quitar de memoria las páginas menos usadas recientemente, para ello, ordena las páginas poniendo arriba las que fueron usadas recientemente y va reemplazando por las páginas que se sitúan abajo. Puede ser implementado mediante varios métodos que intentan aminorar los recursos que este método consume, pero, en la actualidad, aunque posea un buen rendimiento teórico, no es conveniente pues consume demasiados recursos.
    Ejemplo de Algoritmo Segunda Oportunidad


  • Segunda oportunidad: Mejora del algoritmo FIFO. Se agrega un bit de referencia a todas las páginas y cuando éstas son utilizadas se fija en 1. El algoritmo consiste en buscar las páginas de la misma manera que lo hacemos en FIFO. Si la página que tenemos al final de la cola tiene su bit de referencia en 0 es reemplazada normalmente, pero si su bit de referencia vale 1 éste es cambiado a 0 y se intenta quitar la siguiente página con el mismo criterio.


  • LFU (Least frequently used): Algoritmo de conteo. El contador aumenta con cada referencia a la página, a la hora de reemplazar elige la página con el menor contador. Es caro de implementar y no se aproxima al algoritmo óptimo.


  • MFU (Most frequently used): Algoritmo de conteo. El contador aumenta con cada referencia. Nos dice que probablemente la página con menor contador será utilizada próximamente y se basa en esto para hacer el reemplazo. Es un algoritmo caro respecto a su implementación y se aleja del algoritmo óptimo.

Asignación de frames

Existen dos esquemas para determinar cual es el número de frames que tendrá cada proceso para su paginación:

  • Asignación fija:
    • igualitaria: Si existe un determinado número de frames m y un número de procesos n a cada proceso le corresponden m / n frames.
    • proporcional: Se asigna una cantidad de frames acorde al tamaño del proceso. Con tn como el tamaño del proceso, stn como la suma del tamaño de todos los proceso y m como el número de frames obtendremos la número de frames para cada proceso mediante: tn\cdot stn/m
  • Asignación por prioridad: Funciona como la asignación por prioridad, pero en vez de utilizar el tamaño de los procesos usa la prioridad de los mismos.


El proceso de reemplazo de página puede darse de manera local o global, es decir, si un proceso necesita hacer un reemplazo el enfoque local le obliga a hacerlo en sus propios frames, mientras que el global le permite usar algún frame de otro proceso con prioridad más baja.

Fuentes

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas