El concepto de almacenamiento a un sólo nivel, en el que la memoria secundaria aparece como una extensión de la memoria principal, se introdujo por primera vez en el ordenador Atlas de la Universidad de Manchester alrededor de 1960, y desde entonces ha ejercido una profunda influencia en el diseño de los ordenadores.

El almacenamiento a un sólo nivel puede llevarse a cabo mediante una técnica llamada paginación, según la cual el espacio de direcciones virtuales se divide en páginas del mismo tamaño (en el Atlas eran de 512 palabras). La memoria principal se divide también en marcos o páginas físicasdel mismo tamaño. Estos marcos son compartidos entre los distintos procesos que haya en el sistema, de forma que en cualquier momento un proceso dado tendrá unas cuantas páginas residentes en la memoria principal (sus páginas activas) y el resto en la memoria secundaria (sus páginas inactivas). El mecanismo de paginación cumple dos funciones:

La primera función se aborda a continuación, y se deja para el siguiente tema la segunda función.

Con el fin de determinar la página a la que hace referencia un programa, los bits de mayor peso de la dirección se interpretan como el número de página, y los bits de menor peso como el número de palabra dentro de esta página. De ahí que si el tamaño de página es 2ⁿ, los n bits finales de la dirección representarán el número de palabra y los bits restantes del principio el número de página. El número total de bits en la dirección es suficiente para direccionar la totalidad de la memoria virtual. Así, por ejemplo, en el Atlas las direcciones de programa tenían 20 bits de longitud, proporcionando una memoria virtual de 2²⁰ palabras; el tamaño de la página era de 512 palabras (2⁹), y de ahí que los 9 bits inferiores representasen el número de palabra y los 11 superiores representasen el número de la página. El número total de páginas en la memoria virtual era por tanto de 2¹¹ (en contraposición a las 32 páginas físicas de que disponía la memoria principal).

Es de destacar el hecho de que la división de la dirección en número de palabra y número de página, es tarea del hardware, y es transparente al programador: por lo que a Jl concierne está programando en un espacio secuencial de direcciones muy grande.

La transformación de número de página y de palabra en la dirección física de memoria se realiza a través de una tabla de páginas, cuyo p-ésimo elemento contiene la posición p' del marco que contiene a la página p (la posibilidad de que la p-ésima página no se encuentre en la memoria principal se abordará dentro de un momento). El número de palabra, w, se suma a p' para obtener la dirección buscada (ver la figura 10).

La transformación de direcciones consiste, pues, en:

donde la dirección de programa, a, el número de página, p, y el número de palabra, w, están relacionados con el tamaño de página Z a través de:

  ENLACE A LA SIMULACIÓN DE MEMORIA PAGINADA

Así pues, cada vez que la CPU genere una dirección de memoria ésta es transformada por una unidad hardware, de forma que en el bus del sistema se introduce la dirección física correspondiente. Es importante observar que la paginación es en sí misma una forma de reubicación dinámica. Cada dirección lógica es transformada en alguna dirección física por el hardware de paginación. Observe también que si el tamaño de página (como es lo usual) es una potencia de dos, el hardware no precisa realizar ninguna división, simplemente sabe que los últimos n bits, si el tamaño de página es de 2ⁿ , representan el desplazamiento, y los primeros bits la página.

Cada proceso debe tener su propia tabla de páginas, y su dirección de comienzo en la memoria principal forma parte de la porción del PCB utilizada para realizar un cambio de proceso.

Como el número de marcos (cantidad de memoria real) asignados a un proceso será normalmente menor que el número de páginas que éste utiliza, es muy posible que una dirección del programa haga referencia a una página que no se encuentre en aquel momento en la memoria principal. En este caso el elemento correspondiente de la tabla de páginas estará vacío, provocando el hardware una interrupción de "fallo de página" si se intenta acceder a ella. Esta interrupción provoca que el control pase al software (al sistema operativo), para que éste inicie la transferencia de la página que falta desde la memoria secundaria a la memoria principal, y actualice de acuerdo con ello la tabla de páginas. El proceso en ejecución se hará no listo hasta que se haya completado esta transferencia. La posición de las páginas en la memoria secundaria puede guardarse en una tabla separada o en la misma tabla de páginas. En este último caso, es necesario un "bit de presencia" en cada elemento de la tabla de páginas, para indicar si la página se encuentra presente o no en la memoria principal, y si el campo de direcciones debe interpretarse como una dirección de marco, o bien como una dirección de la memoria secundaria.

Si no existe ningún marco vacío en el momento en que ocurre un fallo de página, hay que guardar en la memoria secundaria alguna otra página con el fin de hacer sitio a la nueva. La elección de la página que habrá que sacar es el resultado de un algoritmo de reemplazo de página, del cual veremos varios ejemplos en el tema siguiente. Por el momento, vamos a destacar tan sólo el hecho de que la información que necesita el algoritmo de cambio de página, puede estar contenida en algunos bits adicionales que se añaden a cada elemento de la tabla de páginas.

Quizás habría que aclarar, que toda la operación de transformaciones de direcciones la lleva a cabo el hardware, excepto en el caso en que haya que traer una página de la memoria secundaria. En este caso, la aplicación del algoritmo de cambio de página, así como la actualización de la tabla de páginas, las lleva a cabo el software.

La anterior discusión proporciona una visión general de cómo funciona la paginación. En la práctica hay que hacer una serie de modificaciones para llegar a una implementación viable. Una de ellas es que la transformación de dirección virtual a física debe ser rápida.

En el sistema que hemos descrito el tiempo necesario para cada referencia a memoria queda doblado, debido a la necesidad de acceder primero a la tabla de páginas. Una forma de evitarlo podría ser la de tener guardada la tabla de páginas en un conjunto de registros rápidos en lugar de sobre la memoria ordinaria. Sin embargo, el tamaño de la tabla de páginas es proporcional al tamaño del espacio de direcciones virtuales; de ahí que el número de registros necesarios sea demasiado grande para que esta alternativa resulte económicamente viable. La solución al problema consiste en adoptar una técnica diferente para acceder a las páginas activas. Esta técnica representa el tener que incorporar a la máquina una memoria asociativa, que consistirá en un pequeño conjunto de registros de dirección de página (PARs, del inglés page address registers), cada uno de los cuales contiene el número de página de una página activa. Los PARs presentan la propiedad de poderse buscar en ellos de forma simultánea el número de página asociado a una dirección de programa en particular.

Por ejemplo, en la figura 6.11, la dirección de programa 3243 se divide en el número de página 3 y el número de palabra 243 (vamos a suponer, por comodidad, que el tamaño de la página sea 1000). El número de página se compara entonces de forma simultánea con el contenido de todos los PARs, y se encuentra que coincide con el valor del PAR 5. Ello indica que la página 3 ocupa en la actualidad la página física número 5, de forma que la dirección buscada será la 5243.

El empleo de un almacenamiento de tipo asociativo reduce el tiempo empleado en la transformación de direcciones en un orden de magnitud con respecto al caso en el que se guardaba la tabla de páginas sobre memoria principal.

Con el fin de que se pueda hacer referencia a todas las páginas activas a través de un PAR, hay que disponer de tantos como marcos haya en la memoria. Ello es posible en sistemas con una memoria principal reducida (como por ejemplo, el Atlas), pero en sistemas mayores no es viable, desde el punto de vista económico, disponer de todos los PARs necesarios para ello (aunque es de esperar que estos argumentos de tipo económico cambien a medida que se desarrolla la tecnología). Se puede llegar a una solución de compromiso, guardando para cada proceso una tabla de páginas completa en la memoria, y utilizando una pequeña memoria asociativa para referenciar unas pocas páginas asociadas a los procesos activos más recientes. En este caso, el marco al que hará referencia cada PAR, no vendrá implícito por la situación de éste, sino que deberá incluirse como un campo adicional en el mismo PAR. El hardware de direccionamiento de la memoria lleva a cabo, entonces, la operación de transformación de direcciones que se muestra en la figura 6.12. Como antes, sólo se requiere la intervención del software en el caso de que haya que sustituir una página.

Un problema que no ilustra la figura 6.11 es el de distinguir en la memoria asociativa las páginas asociadas al proceso en ejecución de las páginas correspondientes a otros procesos. Una solución consistiría en ampliar los PARs para incluir la identificación de los procesos, junto con el número de la página. Cada dirección que se presente a la memoria asociativa deberá incluir, según esto, el identificador del proceso junto con los bits de la página.

Evidentemente, es de desear que la memoria asociativa contenga los números de las páginas a las que haya mayores posibilidades de acceder. Lamentablemente, no existe ningún algoritmo general que nos asegure que así suceda (véase el siguiente tema). En la práctica se cargan cíclicamente en la memoria asociativa las direcciones de las páginas a las que se ha hecho referencia con más frecuencia recientemente. Este algoritmo, más bien primitivo, es, de hecho, bastante eficaz.

El porcentaje de veces que se encuentra un número de página entre los registros asociativos está relacionado claramente con el número de registros asociativos. Con 8 o 16 registros asociativos, puede obtenerse un porcentaje del 80 al 90%. Un porcentaje del 80% significa que el 80% de las veces encontramos el número de página deseado entre los registros asociativos. Si explorar los registros asociativos lleva 50 nanosegundos, y 750 nanosegundos acceder a memoria, entonces un acceso a memoria "mapeada" lleva 800 nanosegundos cuando el número de página se encuentra en los registros asociativos. Si no conseguimos encontrar el número de página (50 ns), entonces tenemos que acceder a la memoria en primer lugar para buscar el número de marco en la tabla de páginas (750 ns) y entonces acceder a la palabra deseada en memoria (750 ns), dando en total 1550 nanosegundos. Para encontrar el tiempo efectivo de acceso a memoria, tenemos que ponderar cada caso con su probabilidad:

  En este ejemplo, sufrimos un 26,6% de retardo en el tiempo de acceso a memoria (de 750 a 950 nanosegundos).

Otra ventaja de la paginación es la posibilidad de compartir programas de uso corriente. Esto es particularmente importante en un entorno de tiempo compartido. Consideremos un sistema que soporta 40 usuarios, cada uno de los cuales ejecuta un editor de textos. Si el editor de textos consta de 30K de código y 5K de espacio para datos, necesitaríamos 1400K para permitir a los 40 usuarios. No obstante, si el programa es reentrante, podría compartirse como se muestra en la figura 6.13. Aquí vemos un editor de tres páginas que es compartido por tres procesos. Cada proceso tiene su propia página de datos

El código reentrante (también llamado código puro) es un código no automodificable. Si el código es reentrante, entonces nunca cambia durante la ejecución. Así, dos o más procesos pueden ejecutar el mismo código al mismo tiempo. Cada proceso, para su ejecución, tiene su PCB y su memoria para mantener los datos. Por supuesto, los datos de todos esos procesos diferentes varían para cada uno de ellos.

Tan sólo hace falta mantener una copia del editor en la memoria física. Cada tabla de páginas de usuario-proceso hace referencia a la misma copia física del editor, pero las páginas de datos lo hacen a marcos diferentes. Así, para permitir 40 usuarios, precisamos solamente una copia del editor, 30K, más 40 copias del espacio de 5K por usuario. El espacio total requerido es ahora de 230K, en lugar de 1400K, un ahorro significativo.

También pueden compartirse otros programas muy utilizados: compiladores, ensambladores, sistemas de bases de datos, etc. Para que sea compartible, el código tiene que ser reentrante (no automodificable). Este término significa que nunca debería darse una tentativa de almacenar algo en el código, que es de sólo búsqueda o sólo lectura. Obviamente, es crucial que las páginas compartidas sean inamovibles. Si un usuario cambiara una posición, cambiaría para todos los usuarios. La naturaleza de sólo lectura del código compartido no debería dejarse a merced de la corrección del código. El sistema operativo debe reforzar esa propiedad.

La protección de la memoria en un entorno paginado se consigue por medio de unos bits de protección asociados a cada página. Normalmente estos bits se mantienen en la tabla de páginas. Un bit puede definir que una página sea de lectura/escritura o de sólo lectura. Cada referencia a memoria pasa a través de la tabla de páginas para encontrar el número de marco correcto. Al tiempo que se calcula la dirección física, pueden verificarse los bits de protección para asegurar que no se escribe sobre una página de sólo lectura. Una tentativa de escribir sobre una página de sólo lectura ocasiona una excepción hardware al sistema operativo (por violación de acceso a una zona de la memoria principal).

Esta concepción de la protección puede ser extendida fácilmente para obtener una protección más detallada. Podemos disponer de hardware que ofrezca protección de sólo lectura, lectura-escritura o sólo ejecución. O bien, por medio de bits de protección independientes para cada tipo de acceso, puede permitirse cualquier combinación de estos accesos, al tiempo que las tentativas ilegales generan una excepción al sistema operativo.

Un aspecto muy importante de la paginación es la clara separación entre la visión de la memoria que tiene el usuario y la memoria física real. El programa de usuario cree que la memoria es un espacio contiguo, conteniendo solamente ese único programa. En realidad, el programa de usuario está disperso por la memoria física, que también contiene otros programas. La diferencia que existe entre la visión que el usuario tiene de la memoria y la memoria física real se salva por medio del hardware de traducción de direcciones o de transformación (mapping). El hardware de transformación traduce las direcciones lógicas en direcciones físicas. Esta operación permanece oculta al usuario, y la controla el sistema operativo.

Un resultado de la distinción entre direcciones físicas y lógicas es que de hecho pueden no ser iguales. Por ejemplo, en el XDS-940, una dirección lógica es de 14 bits y una dirección física es de 16 bits. Un número de página de 3 bits se usa como índice en la tabla de páginas para seleccionar un número de marco de 5 bits. Así, puede haber hasta 4 veces más memoria física que la que un usuario puede direccionar.

Esta técnica fue adoptada en particular por los fabricantes de miniordenadores. Muchos miniordenadores fueron diseñados en los años 60, cuando la memoria era cara y los programas tenían que ser pequeños. De esta manera las direcciones estaban limitadas a 15 o 16 bits. Con la disponibilidad de la memoria de semiconductores, más barata, se hizo factible aumentar la memoria física de estos miniordenadores. Pero incrementar el tamaño de la dirección para obtener direcciones de 17 o 18 bits, precisas para la memoria física aumentada, significaba, o bien rediseñar el conjunto de instrucciones, o bien extender el tamaño de palabra para acomodar los bits extra. Cualquier solución implicaría un cambio importante, invalidando todos los programas y documentación existentes. La solución que adoptaron la mayoría de los fabricantes fue el mapping de memoria. Las direcciones lógicas (15 o 16 bits), se transforman en direcciones físicas (17 o 18 bits). Multiprogramando el sistema, puede utilizarse toda la memoria. Sin embargo, los usuarios individuales no pueden emplear más memoria que antes, puesto que el espacio para la dirección lógica no ha sido incrementado. No obstante, hay que tener claro que en los sistemas actuales el rango de direcciones virtuales suele ser muy superior al rango de direcciones reales.

El sistema operativo controla esta transformación, y puede activarla para el usuario y desactivarla para el sistema operativo. Puesto que el sistema operativo gestiona memoria física, tiene que estar al tanto de la memoria física: qué marcos están asignados, qué marcos están disponibles, cuántos marcos hay en total, etc. Esta información se mantiene generalmente en una estructura denominada tabla de marcos. La tabla de marcos tiene una entrada para cada marco, que indica si está libre o asignado y, si está asignado, a qué página de qué proceso.

Además, el sistema operativo tiene que conocer qué procesos de usuario operan en el espacio de usuario, y tiene que transformar todas las direcciones lógicas para generar direcciones físicas. Si un usuario realiza una llamada al sistema (para realizar E/S) y da una dirección como parámetro (por ejemplo, un buffer), esa dirección tiene que ser traducida para generar la dirección física correcta. El sistema operativo puede utilizar la dirección de la tabla de páginas del proceso (que se guarda en su descriptor o PCB) para traducir las direcciones lógicas en físicas siempre que tenga que realizar por él mismo la operación.