¿Que es la paginación?. 30 / julio / 2007

Hace no mucho, mencioné algo llamado ‘Paginación’. Pues bien, hoy voy a explicar que es eso de la paginación, ya que es algo que ocurre siempre en nuestro PC y no sabemos identificarlo.

El concepto de paginación aparece junto con el de memoria virtual, ¿que es eso?. Este método fue creado por Fotheringham y la idea básica es la siguiente.

Cuando ejecutamos un programa este puede caber o no en la memoria física, si se da la situación de que el proceso es mayor que la memoria, el SO se encarga de mantener en memoria las partes del programa que estamos usando y el resto en el disco duro.

Pues bien, la técnica llamada ‘paginación’ se encarga del intercambio de información entre nuestra memoria y el disco duro cuando tiene que pasar información de la memoria al disco duro debido a lo comentado antes, que no hemos cargado el programa entero,los pasos serían los siguientes.

Partimos de la siguiente instrucción en lenguaje ensamblador.

MOV REG, 100

Con esa instrucción en lenguaje ensamblador lo que estamos haciendo es mover el contenido de la dirección 100 al registro REG.

Las direcciones pueden generarse empleando diversos métodos (indización, registros base,…).

Estas direcciones se denominan direcciones virtuales y constituyen el espacio de direcciones virtuales. En ordenadores sin memoria virtual, esta dirección se coloca directamente en el bus de memoria y esto hace que se lea o escriba la palabra física de memoria que tenga esa dirección. Cuando se usa memoria virtual (que es nuestro caso), las direcciones virtuales no se envían directamente al bus, sino a una unidad de administración de memoria, (MMU, memory management unit) que establece una correspondencia entre las direcciones virtuales y físicas de la memoria.

En la imagen anterior vemos un esquema del proceso, aunque vemos que la MMU está fuera de la CPU, en los chips actuales se encuentra dentro de la CPU.

El espacio de direcciones virtuales se divide en unidades llamadas «páginas». Las unidades correspondientes en el disco duro se denominan «marcos de página». Las páginas y los marcos tienen el mismo tamaño.

Así sería el proceso de la paginación, pero leyendo lo anterior podemos pensar, ¿que ocurriría si el programa trata de usar una página que no tiene corespondencia?.

La MMU ve que la página no tiene correspondencia y hace que la CPU salte al SO. Esta interrupción se llama ‘fallo de página’. El SO escoge un marco de página que no se esté usando mucho y vuelve a escribir su contenido en el disco, después de lo cual trae la página a la que se acaba de hacer referencia y la coloca en el marco recién desocupado, modificael mapa y reinicia la instrucción interrumpida.

Y ahora nos surge otra duda, dicho desalojo cuando se produce el fallo de página, ¿se realiza al azar?, ya que si esto se hiciera mal, el SO estaría continuamente reescribiendo el mapa, por lo que se perdería mucho tiempo.

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).

• 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.

Yo he nombrado dos algoritmos, aunque existen muchísimos…, Tipo Reloj, LRU, Conjunto de Trabajo, WSClock,…

Cada uno tiene sus pros y sus contras, ninguno es el mejor de todos.