Paginación Trabajo de paginación

[pic 1][pic 2]

[pic 3][pic 4]

Paginación

Principalmente para empezar a hablar de paginación debemos explicar cómo y porqué nació. Por lo general las soluciones nacen a un problema y este caso es la fragmentación de memoria.

¿Qué es la fragmentación de memoria?

La fragmentación de memoria según el libro “Sistemas operativos: teoría y práctica” es un problema que se encuentra muy asociado al uso de las particiones te maño fijo en la memoria. Esto se presenta cuando hay partes de la memoria RAM que no pueden utilizarse.

Además, la fragmentación de memoria está dividida en 2 tipos, interna y externa:

Fragmentación interna

Este tipo se da por una simple razón, al ser fijas las particiones, es muy poco probable que coincidan con la necesidad de memoria de un trabajo con el tamaño de la partición de la memoria al cual va a ser asignado.

Fragmentación externa

Este tipo se puede presentar cuando una petición nueva de memoria para un trabajo específico y aunque exista memoria RAM suficiente “libre” no puede ser utilizada porque pertenece a esas particiones fijas distintas.

Uno de los métodos que dio solución a este problema fue el método ideado por Fotheringgham en 1961 según el libro “Sistemas operativos modernos” actual libro que se está estudiando en clase. Este método se conoce memoria virtual. Lo básico de este método es que el programa tiene su propio espacio de direcciones y este se divide en trozos llamados páginas.

*Técnica llamada paginación

La memoria se divide en bloques de tamaño fijo llamados Marcos de página. A los procesos se los divide en bloques llamados Páginas los cuales tiene el mismo tamaño que los marcos de página. El tamaño de un marco y por ende de una página está determinado por el hardware.

Proceso de paginación

Cuando se carga un proceso en la memoria, el sistema operativo carga cada página en un marco sin usar, los cuales no es necesario que deban estar contiguos, es decir, que los espacios estén uno debajo del otro.

Si un nuevo proceso intenta ingresar y en el marco de páginas no hay espacio para el número de páginas que necesita el proceso, el proceso es puesto en espera hasta que sea finalizado algún otro proceso. Cuando algún proceso es finalizado el proceso en espera es agregado al marco de página en los espacios libre sin importar su continuidad.

Algoritmos de remplazo de páginas

1. Óptimo: Aunque es el mejor algoritmo de remplazo, es imposible de implementar. Un fallo de página sucede cuando una página no se referencia sino hasta 10 o muchas más instrucciones después, es decir, que si un proceso ingresa con 10 páginas puede que solo esté utilizando 5 páginas de esas 10. El algoritmo óptimo de remplazo de páginas “funciona” eliminando las páginas con la referencia más altas, es decir, con la etiqueta más alta. El problema es que, el SO, no puede ver el futuro y no hay manera de hacer que el SO, sepa qué página tiene la etiqueta más alta.
2. No usadas recientemente(NRU):  la mayor parte de las computadoras que implementan memoria virtual tiene 2 bits que está relacionados en cada página, R para referencia, y M para Modificado. estos bits tienen 2 valores 1 y 0.  En R, 1 si ya ha sido referenciado, 0 si aún no lo ha sido. En M, 1 si ha sido modificado el contenido, 0 si no. En los fallos de página, el sistema operativo todas las páginas las divide en 4 categorías en base a sus bits R y M:

[pic 5]

El NRU, elimina una página al azar de la clase de menor numeración que no esté vacía. Es decir, que eliminará una página ya modificado, pero que al menos no haya sido referenciada en algún tiempo. Este algoritmo no siempre puede ser óptimo, pero puede ser el adecuado.

1. FIFO (Primero en entrar, primero en salir): Así cómo en la vida real, el sistema operativo tiene una lista de todas las páginas actuales en la memoria y como en FIFO, la llegada más reciente se coloca en lo último de la lista, y la más antigua está el principio de la lista. En un fallo de página el algoritmo FIFO, borraría la página que se encuentra en al principio de la lista, es decir, la más antigua. El problema es que podría eliminar una página que no se usa, o podría eliminar unas de las más usadas, por esta razón es muy poco frecuente que se utilice FIFO de su manera natural.
2. Segunda Oportunidad: Este algoritmo es una modificación del FIFO, este algoritmo usa los bits R y M. Cuando va a borrar el primero en la lista revisa el bit R, si es 0, quiere decir que la página es antigua y no se ha utilizado, entonces la sustituye. Si es 1, borra el bit, lo coloca en 0 y lo reescribe al final de la lista, es decir, como si acabara de entrar. El algoritmo de segunda oportunidad busca siempre una página antigua y que no haya hecho referencia en el tiempo más recuente. Si todas las páginas han hecho referencia, el algoritmo se convierte en un FIFO puro.
3. Reloj: Éste algoritmo coloca los marcos de página en una lista circular en forma de un reloj, la manecilla única del reloj apunta siempre a la página más antigua. Si ocurre un fallo de página, se inspecciona la página que la manecilla está apuntando y revisa su bit R, si es 0, la página es remplazada inmediatamente, si es 1, desactiva R, es decir lo coloca en 0 y la manecilla avanza y se coloca ahora en el siguiente más antiguo.

[pic 6]

1. Menos usadas recientemente(LRU): Éste algoritmo, cuando hay un fallo de página descarta la página que no se haya utilizado en más tiempo. Para hacer esto posible, se tiene que tener una lista relacionada de todas las páginas en memoria con la página más reciente usado en la parte frontal y la de menos reciente usado en la parte final, para esto se debe actualizar la lista en cada referencia de memoria. Buscar una página en lista, eliminarla y colocarla al inicio. Operación que consume tiempo.

BIBLIOGRAFIA

• Sistemas operativos modernos – Capitulo 3
• Sistemas operativos (Martin Silva) 1ª ed.
• https://lsi.vc.ehu.eus/pablogn/docencia/manuales/SO/TemasSOuJaen/MEMORIAVIRTUAL/4ReemplazodePaginas.htm#algoritmos_reemplazo
• https://www.youtube.com/watch?v=VaYk1m12OOM

...