Conceptos Básicos de Paginación
Frecuentemente se diferencia entre la “paginación pura” y la “combinación de paginación y segmentación.
Las páginas se transfieren del almacenamiento secundario al primario en bloques llamados “marcos de páginas”:
- Tienen el mismo tamaño que las páginas.
- Comienzan en direcciones del almacenamiento real que son múltiplos enteros del tamaño fijo de la página.
- Podrá colocarse una nueva página dentro de cualquier “marco de página” o “celda de página” disponible.
La “traducción dinámica de direcciones” incluye:
- Un proceso en ejecución hace referencia a una dirección virtual “v = (p,d)”
- Un mecanismo de transformación de páginas busca la página “p” en la “tabla de páginas” y determina si la página “p” se encuentra en el marco de página “p ’ ”.
- La dirección de almacenamiento real se forma por la concatenación de “p ’ ” y “d”.
- En caso afirmativo dónde está en la memoria real.
- En caso negativo dónde puede estar en el almacenamiento secundario.
La dirección de almacenamiento primario “a”, donde comienza el marco de pagina “p ’ ” (suponiendo un tamaño de página “p”), está dada por: “a = (p) (p ’)”; se supone marcos de página numerados 0, 1, 2, etc.
Un proceso en ejecución hace referencia a la dirección virtual v = (p,d).
Antes que un proceso comience su ejecución, el S. O. carga la dirección de almacenamiento primario de la “tabla de mapa de páginas” en el “registro origen de la tabla de mapa de páginas”
El número de página es “p”.
La dirección en el almacenamiento primario de la entrada en la tabla de mapa de páginas para la página “p” es “b + p”:
- Indica que el marco de página “p ’ ” corresponde a la página virtual.
- “p ’ ” se concatena con el desplazamiento “d” par formar la dirección real “r”.
“Esto es un ejemplo de transformación directa debido a que la tabla de mapa de páginas contiene una entrada por cada una de las páginas del almacenamiento virtual de este proceso”.
La dirección virtual que se está traduciendo y la dirección base de la tabla de mapa de páginas son mantenidas en un registro de alta velocidad del control del procesador. La tabla de mapa de páginas transformada directamente suele mantenerse en el almacenamiento primario:
- Las referencias a esta tabla requieren un ciclo completo de almacenamiento primario, que generalmente es la parte más larga de un ciclo de ejecución de instrucciones.
- Se requiere otro ciclo de ejecución de almacenamiento primario para la transformación de páginas, lo que puede ocasionar degradación equivalente a un 50%, para lo cual una solución sería tener la tabla completa de mapa de páginas de transformación directa en la “caché” de muy alta velocidad.
Una forma de acelerar la traducción dinámica de páginas consiste en colocar la tabla completa de mapa de páginas en un “almacenamiento asociativo” que tenga un tiempo de ciclo mucho más rápido que el almacenamiento primario.
Una variante es la “transformación asociativa pura”
Un programa en ejecución hace referencia a la dirección virtual v = (p,d).
Cada entrada en el almacenamiento asociativo se busca de forma simultánea para la página “p”:
- Se obtiene “p ’ ” como el marco de página correspondiente a la página “p”.
- Se concatena “p ’ ” con “d” formando la dirección real “r”.
Cada una de las células del almacenamiento asociativo se registra de manera simultánea:
- Hace costoso el almacenamiento asociativo.
- Implementar la transformación asociativa pura resulta demasiado costoso, tal lo ocurrido con la implementación de la transformación directa pura utilizando “caché”.
Se utiliza un almacenamiento asociativo capaz de mantener solo un pequeño porcentaje del mapa completo de páginas para un proceso .
Las entradas de página contenidas en este mapa reducido corresponden solo a las páginas referenciadas recientemente:
- Se presupone que una página recientemente referenciada tendrá posibilidades de serlo de nuevo próximamente.
- Los rendimientos obtenidos con este esquema de mapa asociativo parcial superan aproximadamente en un 100 % a los rendimientos obtenidos con esquemas de mapa asociativo de página completo.
Un programa hace referencia a la dirección virtual v = (p,d).
El mecanismo de traducción de direcciones intenta encontrar la página “p” en el mapa de página asociativo parcial: - Si “p” se encuentra allí:
- El mapa asociativo devuelve “p ’ ” como el número de marco de página correspondiente a la página virtual “p”.
- “p ’ ” se concatena con el desplazamiento “d” para formar la dirección real “r” que corresponde a la dirección virtual v = (p,d).
- Si “p” no se encuentra en el mapa de pagina parcial:
- Se utiliza un mapa directo convencional.
- La dirección “b” del registro de origen de la tabla de páginas se añade a “p” para localizar la entrada apropiada a la página “p” en la tabla de mapa de páginas de transformación directa del almacenamiento primario.
- La tabla indica que “p ’ ” es el marco de página correspondiente a la página virtual “p”.
- “p ’ ” se concatena con el desplazamiento “d” para formar la dirección real “r” correspondiente a la dirección virtual v = (p,d).
En sistemas multiprogramados, especialmente en los de tiempo compartido, es común que más de un usuario estén ejecutando los mismos programas:
- Para optimizar el uso de la memoria real se comparten las páginas que pueden ser compartidas:
- El compartimiento debe ser cuidadosamente controlado para evitar que un proceso modifique datos que otro proceso esta leyendo.
- Los programas se encuentran divididos en áreas separadas de “procedimiento” y “datos”.
- Los procedimientos no modificables se llaman “procedimientos puros reentrantes”.
- Los datos y procedimientos modificables no pueden ser compartidos.
- Los datos no modificables (ej.: tablas fijas) son compartibles.
- Se debe identificar cada página como compartible o no.
- Habrá marcos (celdas) de páginas compartidos por varios procesos.
- Reduce la cantidad de almacenamiento primario necesario para la ejecución eficaz de un grupo de procesos.
- Puede hacer posible que un sistema determinado mantenga una cantidad mayor de usuarios (procesos).
Paginación pura
La paginación pura en el majejo de memoria consiste en que el sistema operativo divide dinámicamente los programas en unidades de tamaño fijo ( generalmente múltiplos de 1 kilobyte ) los cuales va a manipular de RAM a disco y viceversa. Al proceso de intercambiar páginas, segmentos o programas completos entre RAM y disco se le conoce como `intercambio' o `swapping'. En la paginación, se debe cuidar el tamño de las páginas, ya que si éstas son muy pequeñas el control por parte del sistema operativo para saber cuáles están en RAM y cuales en disco, sus direcciones reales, etc; crece y provoca mucha `sobrecarga' (overhead). Por otro lado, si las páginas son muy grandes, el overhead disminuye pero entonces puede ocurrir que se desperdicie memoria en procesos pequeños. Debe haber un equilibrio.
Uno de los aspectos más importantes de la paginación, asi como de cualquier esquema de memoria virtual, es la forma de traducir una dirección virtual a dirección real. Para explicarlo, obsérvese la figura
Como se observa, una dirección virtual `v' = ( b,d) está formada por un número de página virtual `b' y un desplazamiento `d'. Por ejemplo, si el sistema ofrece un espacio de direcciones virtuales de 64 kilobytes, con páginas de 4 kilobytes y la RAM sólo es de 32 kilobytes, entonces tenemos 16 páginas virtuales y 8 reales. La tabla de direcciones virtuales contiene 16 entradas, una por cada página virtual. En cada entrada, o registro de la tabla de direcciones virtuales se almacenan varios datos: si la página está en disco o en memoria, quién es el dueño de la página, si la página ha sido modificada o es de lectura nada mas, etc. Pero el dato que nos interesa ahora es el número de página real que le corresponde a la página virtual. Obviamente, de las 16 virtuales, sólo ocho tendrán un valor de control que dice que la página está cargada en RAM, así como la dirección real de la página, denotada en la figura 4.3 como b' . Por ejemplo, supóngase que para la página virtual número 14 la tabla dice que, efectivamente está cargada y es la página real 2 ( dirección de memoria 8192 ). Una vez encontrada la página real, se le suma el desplazamiento, que es la dirección que deseamos dentro de la página buscada ( b' + d ).
La tabla de direcciones virtuales a veces está ubicada en la misma meoria RAM, por lo cual se necesita saber en qué dirección comienza, en este caso, existe un registro con la dirección base denotada por la letra `a' en la figura 4.3.
Cuando se está buscando una página cualquiera y ésta no está cargada, surge lo que se llama un `fallo de página' (page fault ). Esto es caro para el manejador de memoria, ya que tiene que realizar una serie de pasos extra para poder resolver la dirección deseada y darle su contenido a quien lo pide. Primero, se detecta que la página no está presente y entonces se busca en la tabla la dirección de esta página en disco. Una vez localizada en disco se intenta cargar en alguna página libre de RAM. Si no hay páginas libres se tiene que escoger alguna para enviarla hacia el disco. Una vez escogida y enviada a disco, se marca su valor de control en la tabla de direcciones virtuales para indicar que ya no está en RAM, mientras que la página deseada se carga en RAM y se marca su valor para indicar que ahora ya está en RAM. Todo este procedimiento es caro, ya que se sabe que los accesos a disco duro son del orden de decenas de veces más lentos que en RAM. En el ejemplo anterior se mencionó que cuando se necesita descargar una página de RAM hacia disco se debe de hacer una elección. Para realizar esta elección existen varios algoritmos, los cuales se describen enseguida. _ La primera en entrar, primera en salir: Se escoge la página que haya entrado primero y esté cargada en RAM. Se necesita que en los valores de control se guarde un dato de tiempo. No es eficiente porque no aprovecha ninguna característica de ningún sistema. Es justa e imparcial. _ La no usada recientemente: Se escoge la página que no haya sido usada (referenciada) en el ciclo anterior. Pretende aprovechar el hecho de la localidad en el conjunto de trabajo.
· La usada menos recientemente: Es parecida a la anterior, pero escoge la página que se usó hace más tiempo, pretendiendo que como ya tiene mucho sin usarse es muy probable que siga sin usarse en los próximos ciclos. Necesita de una búsqueda exhaustiva.
· La no usada frecuentemente: Este algoritmo toma en cuenta no tanto el tiempo, sino el número de referencias. En este caso cualquier página que se use muy poco, menos veces que alguna otra.
· La menos frecuentemente usada: Es parecida a la anterior, pero aquí se busca en forma exhaustiva aquella página que se ha usado menos que todas las demás.
· En forma aleatoria: Elige cualquier página sin aprovechar nada. Es justa e imparcial, pero ineficiente.
Otro dato interesante de la paginación es que ya no se requiere que los programas estén ubicados en zonas de memoria adyacente, ya que las páginas pueden estar ubicadas en cualquier lugar de la memoria RAM.
No hay comentarios:
Publicar un comentario