alejandroD
Cantidad de envíos : 9
Puntos : 23
Reputación : 0
Fecha de inscripción : 14/08/2010
 | | Tema: Alejandro Domínguez Vargas & José Gabriel Hidalgo Farfán Dom Nov 21, 2010 12:34 am | |
| PAGINACION
La paginación consiste en considerar el espacio de direcciones lógicas de cada proceso como un conjunto de bloques de tamaño consistente llamados paginas. Cada dirección lógica manejada para un proceso estará conformada por un par de valores [pagina: desplazamiento].
Cada dirección lógica manejada para un proceso estará conformada por un par de valores (pagina: desplazamiento). La memoria física se administra implementando bloques de tamaño consistente denominados marcos (frames). Por lo general el tamaño designado para los marcos y páginas es pequeño.
El SO internamente mantiene una tabla de páginas donde relaciona cada página cargada en memoria principal con el frame que la contenga. Utilizando el número de página el sistema recorrerá toda la tabla de páginas hasta localizarla, sumará el desplazamiento a la dirección de carga y obtNRU (Not Recently Used, No Usada Recientemente), se desaloja al azar una página de Clase baja que no esté vacía. Este algoritmo presupone que es mejor desalojar una página modificada pero no solicitada en un tic de reloj (20 ms), a una limpia que se esté usando mucho. NRU es fácil de entender, tiene una implementación aceptable y un desempeño eficiente, aunque no es óptimo.
FIFO (First In, First Out – primero en entrar primero en salir), el SO mantiene una lista de todas lás áginas existentes, desde la más antigua hasta la más nueva, cuando se produce el fallo, se desaloja la primera de a lista (la más antigua) y la nueva se coloca al final.endrá la dirección real.
Cada programa se subdivide en páginas, que se cargan en frames libres que no tienen porque ser seguidos. El sistema analizará cada nuevo trabajo para conocer el número de página que ocupa y buscará en la lista de frames libres un número igual de frames; si encuentra suficientes cargará en ellas las páginas del programa y construirá la tabla de páginas.
Método Básico
- La memoria física se compone en bloques de tamaño fijo denominados marcos.
- La memoria lógica también se compone en bloques del mismo tamaño denominados páginas
Una dirección generada por la CPU se divide en:
se usa como índice a una tabla de páginas que contiene la dirección de cada página en la memoria física
- desplazamiento en la página (d)
se combina con la dirección básica para definir la dirección de memoria que se envía a la unidad de memoria
número de página desplazamiento en la página
P D
m-n u
para un espacio de direcciones de 2m y de páginas 2n
Estructura De La Tabla De Páginas
Un apuntador a tabla de páginas se almacena con los demás valores de registro en el bloque de control de procesos.
Cuando se le dice al despachador que inicie un proceso, debe recargar los registros del usuario y definir los valores correctos de la tabla de páginas de hardware a partir de la tabla de páginas de usuario que esta almacenada.
Soporte De Hardware
La tabla se implementa como un conjunto de registros dedicados .
Estos registro se deberán construirse con una lógica de muy alta velocidad para que la traducción de direcciones sea eficiente.
Los registros asociativos se conforman por: una llave y un valor, o buffers de traducción de vista lateral (TLB)
Se utiliza para una búsqueda rápida (cache de hardware especial ).
Si el número de páginas no están en los registros, se debe hacer una referencia de memoria a la tabla de páginas
El uso de los registros para la tabla de páginas es satisfactorio si la tabla es razonablemente pequeña.
Paginacion en Linux
Puesto que hay mucha menos memoria física que memoria virtual, el sistema operativo ha de tener especial cuidado de no hacer un mal uso de la memoria física. Una forma de conservar memoria física es cargar sólo las páginas que están siendo utilizadas por un programa.
Esta técnica de cargar sólo páginas virtuales en memoria conforme son accedidas es conocida como Paginación por Demanda.
Linux utiliza la paginación por demanda para cargar imágenes ejecutables en la memoria virtual de un proceso. Siempre que se ejecuta un proceso, se abre el fichero que la contiene y su contenido se asocia en la memoria virtual del proceso. Esto se hace modificando las estructuras de datos que describen el mapa de memoria del proceso y se conoce como asociación de memoria. Sin embargo, sólo la primera parte de la imagen se copia realmente en memoria física. El resto de la imagen se deja en disco. Conforme se va ejecutando, se generan fallos de página y Linux utiliza el mapa de memoria del proceso para determinar qué partes de la imagen ha de traer a memoria para ser ejecutadas.
Fallo de Página
Veamos, cuando se produce un fallo de página, el SO examina todas las páginas y las divide en cuatro grupos dependiendo del estado de sus bits R (página solicitada) y M (página modificada).
Cuando una página debe ser reemplazada, el sistema operativo divide las páginas en cuatro categorías:
- Clase 0: no solicitada, no modificada.
- Clase 1: no solicitada, modificada.
- Clase 2: solicitada, no modificada.
- Clase 3: solicitada, modificada.
Existen diversos algoritmos para decidir que página desalojamos, los cuales son…
NRU (Not Recently Used, No Usada Recientemente), se desaloja al azar una página de Clase baja que no esté vacía. Este algoritmo presupone que es mejor desalojar una página modificada pero no solicitada en un tic de reloj (20 ms), a una limpia que se esté usando mucho. NRU es fácil de entender, tiene una implementación aceptable y un desempeño eficiente, aunque no es óptimo.
FIFO (First In, First Out – primero en entrar primero en salir), el SO mantiene una lista de todas lás áginas existentes, desde la más antigua hasta la más nueva, cuando se produce el fallo, se desaloja la primera de a lista (la más antigua) y la nueva se coloca al final.
Óptimo, Este algoritmo tiene como finalidad retirar la página que vaya a ser referenciada más tarde, por ejemplo si hay una página A que será usada dentro de 10000 instrucciones, y una página B que será usada dentro de 2800 instrucciones, se debería eliminar de la memoria la página A.
Como se puede deducir, para esto el sistema operativo debería ver en cuánto tiempo será usada cada página en memoria y elegir la que está más distante. El problema de este método es que necesita conocimiento del futuro, por lo que es imposible su implementación. Es un algoritmo teórico. Se utiliza a los efectos comparativos con los algoritmos factibles de ser implementados para ver cuál se aproxima más a éste.
Segunda oportunidad, Es una pequeña modificación al algoritmo FIFO, que funciona bastante mejor que el fifo. En este caso cuando una página debe ser sacada se toma la primera en la cola, y en vez de sacarla, consulta el valor de un bites de referencia. En caso de estar fijado (en 001) se cambia el bites a 99 y se lo coloca al final de la obstrucción, autorizando su tiempo de carga como si recién hubiera llegado al procesador.
De esta forma, se le da una segunda oportunidad. Si el bites se encuentra sin fijar(en 99 ), la página se saca de memoria. Cada vez que la M.U.U accede a una página, fija su bit de referencia a 1. Para esto es necesario soporte para bit de referencia por hardware.
Reloj, Existe una variante de este algoritmo que sobre la misma idea presenta una mejora en la implementación. Es el algoritmo del reloj, que lo que hace es tener una lista circular, de forma que al llegar al último elemento de la lista, pasa automáticamente al primero.
Los elementos no se mueven al final de la cola cuando son accedidos, simplemente se pone su bit de referencia a 1. Esto nos evita tener que hacer movimientos de punteros en el caso de implementarlo con una lista enlazada. De hecho, se puede implementar con un array perfectamente, ahorrando así memoria.
LRU, Este algoritmo difiere del de 'No usada recientemente' en el hecho de que aquel sólo se fija en el intervalo de tiempo desde que se pusieron en 0 los bits de referencia de las páginas, mientras que el algoritmo de 'Menos usada recientemente' intenta proveer un comportamiento casi óptimo mediante la observación de las páginas que menos fueron usadas recientemente. Este tipo de páginas, estadísticamente son las que tienen menor probabilidad de ser usadas nuevamente.
Aunque este algoritmo provee un buen comportamiento en teoría, es caro de implementar, en cuanto a recursos consumidos. Hay varias implementaciones que intentan mantener bajo el costo y lograr un rendimiento considerable. Un método consiste en tener una lista enlazada y ordenada de todas las páginas en memoria. En el final de la lista está la página menos usada recientemente, y al principio la más usada recientemente.
El costo alto de este método es porque cada vez que se referencia una página debe ser movida en la lista, algo que consume mucho tiempo. Otra forma, que requiere soporte de hardware, consiste en tener un contador que es incrementado en cada instrucción del CPU.
Cada vez que una página es accedida, gana el número del contador en ese momento. Cuando una página debe ser retirada de memoria, simplemente hay que buscar cuál es la que tiene el menor número, que es la que fue usada hace más tiempo. En el presente no existen contadores tan grandes para permitir esto. Debido al alto costo del LRU, se proponen algoritmos similares, pero que permiten implementaciones menos costosas, como los que siguen.
| |
|
