Sistemas Operativos

Los requerimientos hardware para que un sistema operativo pueda soportar la paginación bajo demanda son:

Indudablemente, el rendimiento de un sistema con paginación bajo demanda se ve afectado por el número de fallos de páginas. En el peor de los casos, en cada instrucción un proceso puede intentar acceder a una página distinta, empeorando notablemente el rendimiento. Sin embargo, esto no ocurre, puesto que los programas tienden a tener localidad de referencia (véase el Apartado 17.6).

Tanto en los sistemas POSIX como en Windows API el archivo a mapear hay que abrirlo con la llamada al sistema destinada a ello. Por ejemplo, en sistemas POSIX:

En la API POSIX con esto es suficiente para usar la llamada al sistema mmap() y mapear el archivo en memoria:

Una vez mapeado el archivo, si no se van a crear más mapeos, se puede cerrar el descriptor de archivo con close(). Y la región de memoria mapeada se puede liberar, al terminar, con munmap().

En mapped-files.c se puede ver un ejemplo de un programa que cuenta el número de líneas, palabra y caracteres de un archivo. Para acceder al archivo, primero lo mapea en memoria, para así poder acceder a su contenido sin tener que leerlo usando read(). Una vez ha terminado, libera la memoria mapeada.

El ejemplo en mapped-files.cpp es identico al de mapped-files.c, pero desarrollado en C++. Usa la clase definida en memory_map.hpp para abstraer la gestión del mapeo del archivo, por lo que en la implementación de sus métodos, obviamente, se utilizan las mismas llamadas al sistema que en mapped-files.c. Este ejemplo es algo más complejo porque también muestra como manejar el puntero a la memoria mapeada de forma que sea liberada automáticamente cuando ya no es necesaria, siguiendo las pautas recomendadas en C++.

Con Windows API el proceso requiere un paso más. Primero hay que usar el manejador del archivo abierto para crear un objeto de mapeo de archivo con CreateFileMapping(). Después, el manejador devuelto por CreateFileMapping() es usado con MapViewOfFile() para mapear el archivo en la memoria del proceso.

Para liberar la memoria mapeada, se utiliza UnmapViewOfFile(). Mientras que para cerrar el manejador del objeto de mapeo de archivo se usa CloseHandle(), como es habitual.

Algunos sistemas operativos ofrecen el servicio de mapeo de archivos en la memoria solo a través de una llamada al sistema concreta, permitiendo utilizar las llamadas estándar —read(), write(), etc.— para hacer uso de la E/S tradicional. Sin embargo, muchos sistemas modernos utilizan el mapeo en la memoria independientemente de que se pidan o no.

Por ejemplo, en los sistemas POSIX, si un proceso utiliza llamada al sistema mmap() es porque explícitamente pide que el archivo sea mapeado en memoria. Por tanto, el núcleo mapea el archivo en el espacio de direcciones del proceso.

Pero en Linux, Microsoft Windows y otros sistemas operativos modernos, adicionalmente, cuando un archivo es abierto con la llamada al sistema estándar —como open— el archivo es mapeado en el espacio de direcciones del núcleo y las llamadas read y write son traducidas en accesos a la memoria en dicha región. No importa como sea abierto el archivo. Estos sistemas tratan toda la E/S a archivos como mapeada en memoria, permitiendo que el acceso a los mismos, tenga lugar a través del eficiente componente de gestión de la memoria.

Hay muchos algoritmos de reemplazo de página. La cuestión es cómo seleccionar uno en particular, sabiendo que debe tener la menor tasa posible de fallos de página.

Existen otros procedimientos que pueden ser utilizados, junto con alguno de los algoritmos de reemplazo comentados, con el objetivo de mejorar su eficiencia. Estos procedimientos se agrupan dentro de lo que se denomina algoritmos de buffering de páginas.

Cuando un proceso necesita un marco, el algoritmo de reemplazo puede, tanto extraerlo de cualquier proceso, como ser obligado a considerar solo aquellas páginas que pertenecen al proceso que generó el fallo. Eso permite clasificar los algoritmos de reemplazo en dos categorías:

Generalmente, el reemplazo global proporciona mayor rendimiento, por lo que es el método más utilizado.

En los primeros sistemas multiprogramados que implementaron la paginación bajo demanda, era posible que se diera el siguiente caso:

El fenómeno comentado se ilustra en la Figura 61, donde se muestra el uso de la CPU frente al número de procesos cargados en el sistema. Cuando esto último aumenta, el uso de la CPU aumenta hasta alcanzar un máximo. Si el grado de multiprogramación supera dicho punto, el sistema comienza a hiperpaginar, por lo que el uso de la CPU disminuye bruscamente. Por lo tanto, si el sistema está hiperpaginando, es necesario reducir el grado de multiprogramación con el objetivo de liberar memoria.

En los sistemas operativos modernos ocurre algo parecido a lo descrito para los sistemas multiprogramados, aunque sin el efecto en cadena ocasionado por el intento del planificador de largo plazo de maximizar el uso de la CPU, ya que estos sistemas carecen de dicho planificador. Sea como fuere, en ambos casos, los procesos hiperpaginan si no se les asigna un número suficiente de marcos, haciendo que sea imposible utilizarlos.

Para el problema de la hiperpaginación existen diversas soluciones:

Para entender el modelo de conjunto de trabajo es necesario comenzar definiendo el modelo de localidad. El modelo de localidad establece que:

Por ejemplo, cuando se invoca una función se define una nueva localidad. En esta localidad las referencias a la memoria se realizan: al código de la función, a las variables locales de la misma y a algunas variables globales del programa.

Supongamos que proporcionamos a un proceso suficientes marcos como para alojar toda su localidad en un momento dado. Entonces, el proceso generará fallos de página hasta que todas las páginas de su localidad estén cargadas. Después de eso no volverá a fallar hasta que no cambie a una nueva localidad. Sin embargo, si damos al proceso menos marcos de los que necesita su localidad, este hiperpaginará.

El modelo de conjunto de trabajo es una estrategia que permite obtener una aproximación de la localidad del programa y consiste en lo siguiente:

Por ejemplo, dada la siguiente lista de referencias a páginas en la memoria:

si Δ = 10 referencias a la memoria, entonces el conjunto de trabajo en t₁ es {1, 2, 5, 6, 7}. Mientras que en t₂ el conjunto de trabajo es {1, 2, 3, 4}.

Obviamente, la precisión del conjunto de trabajo como aproximación de la localidad del programa depende del parámetro Δ. Por ejemplo:

El uso del conjunto de trabajo es bastante sencillo:

Donde el tamaño del conjunto de trabajo WSS es la suma del tamaño de los conjuntos de trabajo WSS_i para cada proceso i:

y representa la demanda total de marcos. Por eso, si WSS es mayor que el número de marcos disponibles, habrá hiperpaginación.

El sencillo algoritmo anterior permite evitar la hiperpaginación. Sin embargo, el problema está en cómo mover la ventana del conjunto de trabajo en cada referencia, con el fin de volver a calcular el conjunto de trabajo. Una posible aproximación sería utilizar un temporizador que periódicamente invocase a una función encargada de examinar el bit de referencia de las páginas en la ventana Δ. Es de suponer que las páginas con el bit de referencia a 1 forman parte de la localidad del programa y por tanto serán el conjunto de trabajo a lo largo del siguiente periodo.

El prepaginado es una técnica que consiste en cargar múltiples páginas junto con la página demandada en cada fallo de página.

Esas otras páginas se escogen especulativamente bajo la hipótesis de que van a ser necesitadas por el proceso en un corto espacio de tiempo. De manera que si la predicción es acertada, la tasa de fallos de página se reduce significativamente. Esta técnica puede ser utiliza, por ejemplo, en las siguientes situaciones:

En general, el único inconveniente del prepaginado es que debe ser ajustado para que el coste del mismo sea inferior al de servir los fallos de página.

Algunas aplicaciones, cuando acceden sus datos a través de los mecanismos de memoria virtual del sistema operativo, ofrecen peor rendimiento del que conseguirían si este mecanismo no existiera.

El ejemplo típico, son los gestores de bases de datos, que conocen sus necesidades de memoria y disco mejor que cualquier sistema operativo de propósito general, por lo que salen beneficiadas si implementan sus propios algoritmos de gestión de la memoria y de buffering de E/S.

Por eso muchos sistemas operativos modernos permiten que los programas que lo soliciten puedan acceder a los discos en modo RAW. En el modo RAW no hay sistema de archivos, ni paginación bajo demanda, ni bloqueo de archivos, ni prepaginación, ni muchos otros servicios del sistema operativo; por lo que dichas aplicaciones deben implementar sus propios algoritmos de almacenamiento y gestión de la memoria.

Sin embargo, hay que valorar muy bien las necesidades del programa antes de optar por este modo. La mayor parte de las aplicaciones siempre funcionan mejor utilizando los servicios convencionales ofrecidos por el sistema operativo.

Como ya comentamos al estudiar el método básico de paginación (véase el Capítulo 16), una decisión de diseño importante es escoger el tamaño adecuado para las páginas:

En la actualidad, el tamaño de página más común es de 4 KiB en sistemas de 32 bits y 8 KiB en los de 64 bits, ya que son adecuados para la mayor parte de las aplicaciones. Sin embargo, muchos sistemas modernos soportan el uso simultáneo de múltiples tamaños de página. Esto permite que la mayor parte de las aplicaciones utilicen el tamaño estándar, mientras las que hacen un uso intensivo de la memoria —como es el caso de los gestores de bases de datos— puedan utilizar páginas de mayor tamaño.

Los programas creados considerando la localidad de referencia pueden mejorar su rendimiento en los sistemas con paginación bajo demanda.

Vamos a ilustrarlo con el siguiente ejemplo de un programa que inicializa a 0 un array de 128 por 128 elementos.

Un array como el indicado es almacenado en filas:

De manera que si suponemos que el tamaño de cada página es de 128 bytes, en el mejor de los casos cada fila estará almacenada en una página. Por lo tanto:

Sin embargo, el ejemplo sería diferente si el bucle interno del programa recorriera las columnas del array y no las filas:

Pues se podrían a 0 primero todos los bytes de una misma página antes de empezar con la siguiente. Esto reduciría el número de fallos de página a 128, aunque el sistema operativo solo asigne un marco al proceso.

Por lo tanto se puede concluir que:

Supongamos que un proceso solicita una operación de E/S sobre el contenido de alguna de las páginas de su espacio de direcciones y que, antes de que la operación sea realizada, la página es reemplazada mientras el proceso está esperando. En ese caso, la operación de E/S se podría acabar realizando sobre una página que pertenece a un proceso diferente. Para evitarlo existen diversas soluciones:

Además los bits de bloqueo se pueden utilizar en otras muchas situaciones:

Los procesos pueden utilizar diversas ubicaciones dentro de su espacio de direcciones virtual para almacenar los datos que necesitan para su ejecución (véase la Figura 62):

Cada lenguaje de programación, debe proporcionar —a través de su librería estándar— un mecanismo en espacio de usuario, adecuado para la gestión en tiempo de ejecución de la memoria del montón del proceso. Para eso, cada lenguaje puede utilizar su propia implementación de dicho mecanismo o bien recurrir a la proporcionada por la librería del sistema.

Por ejemplo, en los sistemas POSIX, la librería del sistema proporciona su propia implementación, accesible a través de las funciones malloc() y free(), que es utilizada directamente por los programas escritos en C. Esta implementación hace uso de mmap(), pero ofrece mayor control sobre la cantidad de memoria que podemos reservar, como veremos en el Apartado 17.8.2.

Otros lenguajes de programación tienen otras interfaces para gestionar la memoria, pero utilizan internamente las funciones malloc() y free() de la librería del sistema. Sin embargo, este no es el caso ni de C++ ni de Java ni de algunos otros lenguajes. En C++, los operadores new y delete utilizan sus propios algoritmos de gestión de la memoria del montón, más optimizados que malloc() y free() para la creación y destrucción de objetos de cualquier tamaño de manera eficiente.

En Windows API ocurre algo similar. La librería del sistema proporciona su propia gestión de la memoria del montón, que es accesible para cualquier programa a través de las funciones HeapAlloc() y HeapFree(), y que se implementa sobre VirtualAlloc(). La librería estándar de C utiliza, a su vez, esas funciones para implementar malloc() y free(). Lo mismo ocurre en otros lenguajes, aunque no en todos, ya que algunos optan por implementar algoritmos más eficientes para sus casos de uso directamente sobre VirtualAlloc().

Para ilustrar cómo se puede gestionar la memoria del montón utilizaremos como ejemplo el mecanismo empleado por la librería del sistema de los sistemas POSIX —accesible a través de las funciones malloc() y free(). Sin embargo, es importante tener en cuenta que esta tarea se realiza de manera muy similar en las implementaciones de otros sistemas operativos y lenguajes de programación.

El funcionamiento básico de malloc() sigue las siguientes reglas:

La función calloc() permite obtener memoria del montón inicializada a 0, por lo que sigue las mismas reglas que malloc(). Cuando la petición es pequeña, obtiene la memoria del montón —extendiéndolo si fuera necesario— para luego ponerla manualmente a 0 antes de retornar de la función. Si la cantidad es grande —mayor de 128 KiB en sistemas GNU/Linux, como hemos comentado— obtiene la memoria llamando directamente a mmap(), que ya la devuelve inicializada a 0 y que usa técnicas como el copy-on-write para ahorrar memoria física, retrasando la asignación de marcos hasta el momento en el que el proceso comienza a escribir realmente en la memoria reservada.

La estrategia comentada sufre de fragmentación interna. En las peticiones grandes, mmap() reserva en múltiplos de tamaño de página, por lo que siempre se puede perder cierta cantidad, aunque pequeña en comparación al tamaño de la región reservada. En las peticiones pequeñas, la memoria se asigna en múltiplos de una unidad mínima —por ejemplo, 16 o 32 bytes— por lo que también se puede perder cierta cantidad de memoria.

Además sufre de fragmentación externa, porque después de que el proceso lleva un tiempo en ejecución, liberando y reservando memoria, el espacio puede comenzar a quedar fraccionado en un gran número de pequeños huecos, obligando a la librería a buscar más espacio para el montón, aunque en suma haya suficiente espacio en los huecos libres.

Esto representa un reto para los desarrolladores de aplicaciones, que previsiblemente vayan a ejecutarse durante periodos muy largos de tiempo. En esos casos, es común optar por librerías externas, que implementen gestores de memoria que fragmenten menos la memoria, o soluciones basadas en alguna forma de referencias indirectas y recolección de basura, para ocasionalmente poder compactar la memoria del montón. Esto último, es lo que hace la máquina virtual de Java.