Prácticamente el único mecanismo que se usa hoy en día para
implementar espacios de direcciones virtuales es paginamiento. En
este mecanismo una página es un bloque de memoria de taman o fijo y
potencia de 2 (típicamente 4 KB u 8 KB). La idea es que el espacio
de direcciones virtuales y el espacio de direcciones reales se
particionan en páginas del mismo taman o (ver figura 
).
Figure: Particionamiento de los espacios de direcciones en páginas.
Una página siempre se procesa como un todo, si se otorga a un proceso, se otorga la página completa, en ningún caso una fracción de la página. Cada página del espacio de direcciones virtuales puede residir en cualquiera de las páginas del espacio de direcciones reales, siempre y cuando allí haya memoria física.
En el descriptor de cada proceso se guarda una tabla de páginas que
consiste en una arreglo que indica en qué página de la memoria real
se ubica cada página del espacio de direcciones virtuales (ver figura
). Para ello se enumeran las páginas virtuales y las
páginas reales de 0 en adelante. De esta forma en la fila v de la
tabla de páginas se indica en que número de página real se
encuentra la página virtual número v.
Figure: La tabla de páginas de un proceso.
Los atributos de una página son un conjunto de bits que indican qué operaciones es válido realizar en cada página del proceso. Estos bits son:
El hardware del procesador posee usualmente un registro que indica la dirección en la memoria real de la tabla de páginas del proceso en ejecución. Este registro necesariamente contiene una dirección real pues de ser una dirección virtual, caeríamos en una ciclo infinito al tratar de determinar en qué lugar de la memoria real se encuentra.
Durante un cambio de contexto es necesario cambiar el espacio de direcciones virtuales por el del proceso entrante, por lo que este registro se modifica con la dirección de la tabla de páginas que se encuentra en el descriptor del proceso entrante.
Si las direcciones son de 32 bits y las páginas son de 
bits,
significa que la tabla de páginas debe poseer 
filas. Esto
da 512 K-filas, si las páginas son de 8 KB. Por lo tanto se
requerirían 2 MB sólo para almacenar la tabla si se destinan 4 bytes
por cada fila, lo que es obviamente excesivo.
Este problema lo resolveremos temporalmente restringiendo el espacio de direcciones virtuales a 1024 páginas u otra cantidad razonable. Por ende el taman o de la tabla de páginas necesita sólo 1024 filas o 4 KB. Los accesos a la página 1024 o una página superior causan una interrupción.
El hardware del microprocesador se encarga de traducir las direcciones virtuales que accesa un proceso a direcciones reales. Para efectuar esta traducción el hardware determina el número de la página virtual a partir de la dirección virtual accesada por el proceso y la traduce al número de la página real en donde reside esa página virtual.
Si las páginas son de 
bytes y las direcciones de 32 bits, es
muy fácil determinar el número de una página en una dirección.
Basta observar que todas las direcciones que caen en la misma página
v tienen un mismo prefijo de 32-k bits que corresponde
precisamente a v, los últimos k bits en la dirección son el
desplazamiento de la palabra accesada dentro de la página.
El mecanismo de traducción de direcciones se observa en la figura
. De la dirección virtual se extraen los bits que
corresponden al número de página virtual (v). Con ellos se
subindica la tabla de páginas y se determina en qué página real
(r) se encuentra la palabra accesada, además se verifica que los
atributos presentes en esa posición en la tabla autorizan la
operación solicitada (lectura o escritura). Finalmente, la
dirección real se forma a partir del número de la página real y el
desplazamiento o dentro de la página que se extrae de la dirección
virtual.
Figure: Traducción de direcciones virtuales a direcciones reales
por medio de la tabla de páginas.
El paginamiento permite implementar espacios de direcciones virtuales y por lo tanto protección entre procesos. También permite realizar todas las optimizaciones del uso de la memoria que ofrece la segmentación:
Cuando un proceso desborda su pila, el núcleo puede asignarle una nueva página en forma transparente para el proceso.
Cuando el proceso solicita la extensión de los datos invocando la llamada al sistema sbrk, el núcleo asigna las páginas necesarias según la memoria pedida.
Cuando la memoria escasea, el núcleo puede llevar procesos a disco: sus datos, su código, su pila y sus tablas de páginas.
Los procesos semi-ligeros comparten la porción del espacio de direcciones que corresponde al código y los datos, pero poseen una porción no compartida en donde se ubica la pila. Con esto es posible implementar extensión automática de la pila en caso de desborde.
Pero además, el mecanismo de paginamiento permite realizar mejor algunas optimizaciones que en segmentación.
Se dice que la fragmentación asociada a la segmentación es una fragmentación externa porque se pierden trozos de memoria fuera de la memoria asignada a los procesos. Este problema no existe en paginamiento: se puede otorgar a un proceso un conjunto de páginas reales que ocuparán una porción contigua del espacio de direcciones virtuales, aún cuando estas páginas reales no forman un bloque contiguo en la memoria real del computador.
La administración de páginas de taman o fijo es un problema simple de resolver eficientemente. Las páginas disponibles se organizan en una lista enlazada simple. La extracción y la devolución de páginas toma tiempo constante y requiere unas pocas instrucciones. Cuando un proceso solicita explícitamente o implícitamente más memoria, se le otorga tantas páginas como sea necesario para completar la memoria requerida, sin importar que las p'aginas disponibles estén diseminadas por toda la memoria.
Aunque no hay fragmentación externa sí puede haber fragmentación interna. Este último tipo de fragmentación ocurre cuando a un proceso se le otorga más memoria de la que él solicita. En efecto, al otorgar un grupo de páginas, es usual que la última página contenga un sobrante que el proceso no ha solicitado. Este sobrante existe porque en paginamiento no se pueden otorgar fracciones de página. En todo caso, los estudios indican que la fragmentación interna significa una pérdida de memoria inferior a la fragmentación externa.
Es el intérprete de comandos el que típicamente llama a fork para crear una copia de sí mismo. Esta copia invoca de inmediato exec del binario de un comando ingresado por el usuario. En un esquema segmentado esto requiere duplicar los segmentos de datos y de pila del intérprete de comandos, para que luego se destruyan de inmediato. Esto es un uso muy ineficiente del tiempo de procesador.
En un esquema de paginamiento, fork se puede implementar
eficientemente haciendo uso de la técnica copy-on-write (copia
al escribir). La idea es no duplicar de inmediato las páginas de
datos y de pila, sino que sólo duplicar la tabla de página del
proceso que invoca fork (ver figure ).
Inicialmente los procesos padre e hijo comparten todas sus páginas,
pero se protegen contra escritura.
: Optimización de fork a través de copy-on-write.
Al retomar estos procesos cualquier escritura del padre o del hijo genera una interrupción. El núcleo duplica entonces la página que se modifica y se le coloca permiso de escritura. De esta forma se retoma el proceso interrumpido en forma transparente, sin que se dé cuenta del cambio de página.
La ganancia se obtiene cuando el fork va seguido prontamente por un exec, puesto que será necesario duplicar sólo unas 2 o 3 páginas, lo que resulta ser mucho más económico que duplicar todas las páginas.
En una esquema de paginamiento se puede implementar todo el rango de
``pesos'' de los procesos (ver figura ). En esta
categorización los procesos se distinguen por la amplitud del espacio
de direcciones que comparten. Mientras más espacio comparten, más
ligeros son.
: Clasificación de los procesos según la porción compartida
del espacio de direcciones.
Los procesos semi-pesados se ubican a mitad de camino entre los semi-ligeros y los pesados. Los procesos semi-pesados tienen dos porciones del espacio de direcciones para datos:
Los procesos semi-pesados mejoran los procesos semi-ligeros porque no es necesario reescribir los procedimientos de biblioteca que invocan malloc y free. Esto porque los procesos semi-pesados no necesitan sincronizarse para llamar a malloc o free.
Observe que un proceso semi-pesado puede enviar a otro proceso semi-pesado un puntero a una estructura que pidió con shared_malloc, pero es un error mandar un puntero a una estructura que se pidió con malloc.
Por último, el paginamiento permite realizar una optimización sobre el uso de la memoria que no se puede realizar en un esquema de segmentación: paginamiento en demanda.
En este esquema el núcleo lleva a disco las páginas virtuales que no han sido accesadas por un período prolongado y, a pesar de todo, el proceso propietario de esas páginas puede continuar corriendo, si no las accesa.
El paginamiento en demanda será estudiado en profundidad en la siguiente sección.
Observe que conceptualmente, cada vez que se realiza un acceso a la memoria, es necesario realizar un acceso a memoria adicional para realizar la traducción. De implementarse de esta forma, estaríamos doblando el tiempo de ejecución de cualquier programa, lo que sería inaceptable para los usuarios. A continuación examinamos como se resuelve este problema en casos reales.
En una Sun 3/50 las páginas son de 8 KB (k=13) y la tabla de páginas posee 1024 filas por lo que el espacio de direcciones virtuales se restringe a 8 MB. Es interesante estudiar este esquema de paginamiento, pues permite apreciar las restricciones de los esquemas primitivos.
La tabla de páginas del proceso en ejecución se guarda en una memoria estática de tiempo de acceso muchísimo más rapido que la memoria dinámica en donde se almacenan datos y programas (la Sun 3/50 no poseía memoria cache). De esta forma la penalización en tiempo de ejecución al realizar la traducción de la dirección virtual es razonable (del orden de un 10% de tiempo adicional en cada acceso a la memoria).
Este mecanismo presenta los siguientes inconvenientes:
En esta familia de procesadores, las páginas son de 4 KB (k=12) y
el espacio de direcciones virtuales es de 4 GB (
bytes). Una
tabla de páginas está restringida a 1024 filas, pero un proceso
puede tener hasta 1024 tablas distintas. Cada tabla de páginas sirve
para traducir las direcciones de un bloque contiguo de 4 MB de memoria
en el espacio de direcciones virtuales.
Además de las tablas de páginas, existe un directorio que indica que tablas posee el proceso en ejecución y cuál es su dirección real en la memoria del computador. El directorio y las tablas de páginas ocupan cada uno una página completa.
El proceso de traducción se observa en la figura . La
organización del directorio es similar a la de una tabla de páginas,
sólo que en vez de indicar la traducción de una página, indica la
dirección de una tabla de páginas para traducir la páginas que
pertenecen a un bloque de 4 MB (una especie de super página).
Además en cada fila del directorio hay atributos similares a los de
una tabla de páginas. Por ejemplo si el bit V está en 0, quiere
decir que todo un bloque de 4 MB en el espacio virtual no está
asignado en la memoria real.
Figure: Traducción de direcciones virtuales en un procesador
Intel 386/486/Pentium.
El gasto en páginas de memoria para implementar los procesos de un sistema operativo como Unix son los siguientes:
El directorio y las tablas de páginas se almacenan en memoria real en una Intel 386. Con esto, se reduce el tiempo para realizar un cambio de contexto, pero se multiplica por 3 el costo del acceso a la memoria virtual. En efecto cada acceso a la memoria virtual requiere un acceso real en el directorio para determinar la tabla de páginas, otro acceso real en la tabla de páginas y finalmente el acceso real de la palabra solicitada por el proceso. Este nuevo sobrecosto es escandalosamente inaceptable.
Para acelerar los accesos a la memoria, el hardware del computador
posee una TLB (de translation look-aside buffer). La TLB es una
pequen a memoria asociativa (similar a una memoria caché) de muy
rápido acceso que almacena la traducción y los atributos de 32 a 128
páginas virtuales accesadas recientemente (ver figura ).
Figure: Estructura de la TLB: Translation-Lookaside-Buffer.
Cuando se accesa una página cuya traducción se encuentra en la TLB, el sobrecosto es bajísimo. En cambio si la traducción no se encuentra en la TLB, sólo entonces se visitan el directorio y la tabla de páginas en la memoria real, con un sobrecosto de 2 accesos adicionales a la memoria. La traducción de esta página se coloca en la TLB para que los futuros accesos a esta página sean eficientes. Sin embargo, eventualmente será necesario suprimir una traducción previamente existente en la TLB, debido a su taman o limitado.
Empíricamente se ha determinado que más del 99% de los accesos a memoria corresponde a páginas cuya traducción y atributos se encuentran en la TLB.
Una restricción usual es que la TLB mantiene sólo la traducción de páginas pertenecientes al proceso en ejecución. Durante un cambio de contexto es necesario invalidar la TLB, para que no se encuentren en la TLB traducciones que corresponden erróneamente al proceso anterior. Este es un costo escondido del cambio de contexto: el proceso que recibe el procesador encuentra la TLB vacía, la que se irá poblando a medida que el proceso accesa sus páginas virtuales. Para cargar 64 filas de la TLB se habrán requerido 128 accesos adicionales. De todas formas, este sobrecosto es muy inferior al del cambio de contexto en una Sun 3/50.
De esta forma se resuelven los dos problemas de los mecanismos de paginamiento primitivos: el espacio de direcciones virtuales crece a 4 GB y el costo del cambio de contexto se reduce. La mayoría de los procesadores modernos emplean esquemas similares a la excepción de los PowerPC que poseen tablas de páginas invertidas, que por problemas de espacio no podemos discutir este documento.
