Si el número de marcos asignados a un proceso de baja prioridad desciende por debajo del número mínimo requerido por la arquitectura del computador, debemos suspender la ejecución de ese proceso. Luego debemos descargar sus páginas restantes, liberando los marcos asignados. En general, cualquier proceso que no cuente con marcos suficientes provocará fallos de página muy frecuentemente. Si se reemplazan páginas que a su vez están activas, estaremos sustituyendo una página que casi de inmediato se volverá a necesitar. Por tanto, pronto vuelve a generarse otro fallo de página, ocurriendo esto una y otra vez. A esta altísima actividad de paginación se le llama hiperpaginación (thrashing). Un sistema está en hiperpaginación si emplea más tiempo paginando que ejecutando.

La hiperpaginación ocasiona severos problemas de rendimiento. Considere la siguiente situación, basada en el comportamiento real de los primeros sistemas de paginación.

El sistema operativo supervisa la utilización de la CPU. Si ésta es demasiado baja, aumentamos el nivel de multiprogramación introduciendo un nuevo proceso en el sistema. Se emplea una algoritmo de reemplazo de páginas global, que reemplaza páginas sin importar a qué procesos pertenezcan. Suponga ahora que un proceso entra en una nueva fase de su ejecución y necesita más marcos. Comienza a generar fallos de página y a tomar páginas de otros procesos. Sin embargo, estos procesos necesitan esas páginas, por lo que también fallan, tomando páginas de otros procesos. Todos estos procesos generando fallos de página deben usar el dispositivo de paginación para intercambiar las páginas. A medida que se colocan en la cola del dispositivo de paginación, la cola procesos listos se vacía. Mientras los procesos están bloqueados en espera del dispositivo de paginación, la utilización de la CPU decrece.

El planificador de la CPU ve disminuir la utilización de ésta y, por tanto, incrementa el nivel de multiprogramación. El nuevo proceso trata de comenzar tomando páginas de los procesos en ejecución, lo que ocasiona más fallos de página y una cola más larga para el dispositivo de paginación. Y se vuelven a repetir los pasos descritos. Ha comenzado la hiperpaginación y se desploma la productividad del sistema. La tasa de fallos de página aumenta tremendamente y, como resultado, se incrementa el tiempo efectivo de acceso a memoria. No se efectúa ningún trabajo porque el sistema operativo está continuamente paginando.

Los efectos de la hiperpaginación se pueden limitar utilizando un algoritmo de reemplazo local (o por prioridades). Con el reemplazo local, si un proceso comienza a hiperpaginar, no puede robar marcos de otro proceso y provocar que este también entre en hiperpaginación. Sin embargo, si los procesos están en hiperpaginación, la mayor parte del tiempo pueden encontrarse en la cola del dispositivo de paginación. El tiempo promedio de servicio de un fallo de página aumenta y, por tanto, el tiempo efectivo de acceso aumenta incluso para un proceso que no esté en hiperpaginación.

Para evitar la hiperpaginación debemos ofrecer a un proceso todos los marcos que necesita; pero, ¿cómo sabemos cuántos necesitan? Para saberlo se utilizan técnicas como el modelo del conjunto de trabajo, que se basa el concepto de localidad de la ejecución de procesos.

El concepto de localidad establece que un proceso, durante su ejecución, pasa de una localidad a otra. Una localidad es un conjunto de páginas que se utilizan conjuntamente. Un programa generalmente está compuesto por varias localidades distintas, las cuales pueden superponerse.

Por ejemplo, al llamar a una subrutina se define una nueva localidad. En ésta se efectúan referencias a memoria de las instrucciones de la subrutina, sus variables locales y un subconjunto de las variables globales. Al salir de la subrutina, el proceso abandona esta localidad. Así, vemos que las localidades están definidas por la estructura del programa y sus estructuras de datos.

Suponga que a un proceso le asignamos suficientes marcos para albergar su localidad actual. Generará fallos de página hasta completar su localidad pero, luego, no habrá más fallos hasta que cambie de localidad. Si asignamos menos marcos que el tamaño de la localidad, el proceso entrará en hiperpaginación, ya que no puede mantener en memoria todas las páginas que está usando en ese momento.

El modelo del conjunto de trabajo (Working Set Model) se basa en el concepto de localidad. El modelo utiliza un parámetro, D , para definir la ventana del conjunto de trabajo activo. La idea es examinar las D referencias más recientes a páginas. El conjunto de páginas en las D referencias constituye el conjunto de trabajo. Si una página está en uso pertenecerá al conjunto de trabajo, y si ya no se usa se descartará tras D unidades de tiempo después de su última referencia. De esta manera, el conjunto de trabajo es una aproximación a la localidad del programa.

 Por ejemplo, dada la serie de referencias a memoria de la figura 10, si D = 10 referencias de memoria, entonces el conjunto de trabajo en el instante t₁ es {1, 2, 5, 6, 7}. En el instante t_2,, habrá cambiado a {3, 4}.

La exactitud del conjunto de trabajo depende de la selección de D . Si D es demasiado pequeño, no abarcará todo el conjunto de trabajo; si es demasiado grande, puede solapar varias localidades. En el caso extremo, si D es infinito, el conjunto de trabajo es todo el programa.

La propiedad más importante de los conjuntos del trabajo es su tamaño. Si calculamos el tamaño del conjunto de trabajo WSS_i, para cada proceso del sistema, podemos considerar D=WSS_i, donde D es la demanda total de marcos. Cada proceso utiliza las páginas de su conjunto de trabajo, por lo que i necesita WSS_i marcos. Si la demanda total es mayor que el número total de marcos disponibles (D > m) se producirá la hiperpaginación, ya que algunos procesos no tendrán marcos suficientes.

El uso del modelo del conjunto de trabajo resulta sencillo. El sistema operativo supervisa el conjunto de trabajo de cada proceso y le asigna marcos suficientes para proporcionarle el tamaño del conjunto activo. Si hay suficientes marcos iniciales, se puede iniciar otro proceso. Si aumenta la suma de los tamaños de los conjuntos activos, excediendo el número total de marcos disponibles, el sistema operativo selecciona un proceso y lo suspende.

Sin embargo, tenemos el problema del seguimiento del conjunto de trabajo. La ventana del conjunto de trabajo es cambiante; cada vez que se hace referencia a la memoria, la nueva referencia aparece en un extremo y del otro extremo desaparece la referencia más antigua. Una página se encuentra en un conjunto activo si existe una referencia a ella en cualquier lugar de la ventana. Podemos aproximarnos al modelo del conjunto de trabajo mediante interrupciones a intervalos fijos de un cronómetro y un bit de referencia.

Por ejemplo, suponga que D es 10000 referencias y podemos producir una interrupción del cronómetro cada 5000 referencias. Cuando recibimos una interrupción del cronómetro, copiamos y borramos los valores de los bits de referencia para cada página, de manera que si ocurre un fallo de página podemos examinar el bit de referencia actual y los dos bits en memoria para determinar si la página ha sido utilizada en los últimos 10000 a 15000 referencias. Si se usó, por lo menos uno de éstos bits estará a uno; de no ser así, todos estarán a cero. Se considerará que todas las páginas que poseen por lo menos un bit a uno están en el conjunto de trabajo. Esta manera de actuar no es totalmente precisa, ya que no podemos decir cuándo ocurrió una referencia dentro de un intervalo de 5000. Es posible reducir la incertidumbre aumentando el número de bits históricos y el número de interrupciones; sin embargo, el servicio de esas interrupciones será proporcionalmente más costoso.

El modelo del conjunto de trabajo tiene bastante éxito, y el conocimiento del conjunto puede resultar útil para la prepaginación, pero parece ser una manera bastante torpe de controlar la hiperpaginación. La estrategia de frecuencia de fallos de página sigue un camino más directo.

Queremos evitar la hiperpaginación, o lo que es lo mismo, la elevada tasa de fallos de página. Cuando es demasiado alta sabemos que un proceso necesita más marcos, y si es demasiado baja, puede ser que el proceso tenga demasiados marcos. Podemos establecer límites superior e inferior para la tasa deseada de fallos de página. Si la tasa de fallos de página excede el límite superior, asignamos otro marco a ese proceso; si la tasa cae por debajo del límite inferior, quitamos un marco al proceso. Así podemos medir y controlar directamente la tasa de fallos de página para evitar la hiperpaginación.

Al igual que ocurre con la estrategia del conjunto de trabajo, posiblemente tenga que suspender un proceso. Si aumenta mucho la tasa de fallos y no hay marcos disponibles, debemos seleccionar un proceso y suspenderlo. Los marcos liberados se distribuyen entre los procesos con tasa elevada de fallos de página.

La selección de un algoritmo de reemplazo y una política de asignación son las principales decisiones que hay que tomar para un sistema de paginación. Existen otros factores que deben considerarse.

Una propiedad evidente de un sistema de paginación por demanda pura es el gran número de fallos de página que ocurren al iniciar un proceso. Esta situación surge al tratar de introducir en memoria la localidad inicial. También, ocurrirá cuando se reanuda un proceso intercambiado. La prepaginación es un intento de evitar este alto nivel de paginación inicial. La estrategia consiste en traer a memoria al mismo tiempo todas las páginas que se necesitarán.

En un sistema que utiliza el modelo del conjunto de trabajo, por ejemplo, con cada proceso debemos conservar una lista de las páginas que forman en un instante el conjunto de trabajo. Por tanto, cuando se un proceso se reanuda (fin de E/S o suficientes marcos libres), automáticamente se incorpora todo el conjunto de trabajo antes de reanudar al proceso.

La prepaginación puede ser una ventaja en algunos casos. La cuestión es sencillamente si el costo de la prepaginación es menor al costo del servicio de los fallos de página correspondientes. Puede ser que ya no se usen muchas de las páginas devueltas a memoria por la prepaginación. Suponga que las páginas están prepaginadas y una fracción a de estas s páginas realmente se usan (0 £ a £ 1). La pregunta es si el costo de las a s fallos de página que se evitan es mayor o menor al costo de la prepaginación de (1-a )s páginas innecesarias. Si a es cercano a 0, pierde la prepaginación; si a es cercano a 1, la prepaginación gana.

Cuando se utiliza la paginación por demanda, en ocasiones tenemos que permitir que algunas páginas se fijen en memoria. Debemos evitar que se produzca la siguiente secuencia de sucesos. Un proceso emite una solicitud de E/S y se coloca en la cola para ese dispositivo de E/S. Mientras tanto, se asigna la CPU a otros procesos. Estos generan fallos de página y, usando un algoritmo de reemplazo global, uno de ellos reemplaza la página que contiene el buffer de memoria del proceso en espera. Más tarde, cuando la solicitud de E/S avanza hasta el inicio de la cola de dispositivo, se efectúa la E/S para la dirección especificada. Sin embargo, este marco se está utilizando ahora para una página que pertenece a otro proceso.

Hay dos soluciones a este problema. Una consiste en no ejecutar nunca la E/S a memoria de usuario, sino copiar los datos entre la memoria del sistema y la de usuario. La E/S sólo se realiza entre la memoria del sistema y el dispositivo de E/S. Esta copia adicional puede generar un tiempo de procesamiento añadido inaceptable. Otra solución consiste en permitir que las páginas se fijen en memoria. A cada marco se asocia un bit de fijación; si se ha fijado el marco, no se puede seleccionar para reemplazo. Cuando termina la E/S, se desactiva la fijación de las páginas.

Otra aplicación del bit de fijación se refiere al reemplazo normal de páginas. Considere la siguiente secuencia de sucesos. Un proceso de baja prioridad genera un fallo. Al seleccionar un marco para reemplazarlo, el sistema de paginación lee en memoria la página requerida. El proceso se encuentra listo para continuar su ejecución cuando reciba la CPU. Pero mientras un proceso de alta prioridad genera un fallo y el sistema de paginación encuentra una página que está en memoria pero que no ha sido ni modificada ni referenciada: la página que acaba de incorporar el proceso de baja prioridad. Esta página parece perfecta para el reemplazo; está limpia y no hay que reescribirla.

Podríamos impedir que un página recién incorporada sea reemplazada para no desperdiciar el costo que ha supuesto el llevar un página a memoria para luego no hacer uso de ella. Sin embargo, el uso del bit de fijación puede ser peligroso si se activa y nunca se desactiva. Se iría poco a poco inutilizando el espacio de memoria.

La paginación por demanda, está diseñada para ser transparente para el programa de usuario. En muchos casos, el usuario no se percata de que la memoria está paginada. Sin embargo, en muchos casos el rendimiento del sistema puede mejorar si se es consciente de la paginación subyacente.

Un ejemplo en el que se pone esto de manifiesto sería el siguiente. Considere un programa en Pascal cuya función es poner a 0 cada elemento de una matriz de 128 por 128 (suponga que las páginas son de 128 palabras). El código sería:

Observe que la matriz está almacenada por filas. Es decir, la matriz se almacena como A[1,1] , A[1,2] , ..., A[2,1] , A[2,2] , ...., A[128,128] . Para páginas de 128 palabras, cada fila ocupa una página. De esta manera, el código anterior asigna ceros a una palabra de cada página, luego otra palabra en cada página, etc. Si el sistema operativo asigna 128 marcos al programa, entonces ocasiona 128 x 128 = 16384 fallos de página. Si cambiamos el código a se asignan ceros a todas las palabras de una página antes de comenzar con la siguiente, reduciendo a 128 el número de fallos de página.

Una cuidadosa selección de las estructuras de datos y de programación puede mejorar la localidad y, por tanto, disminuir la tasa de fallos de página y el número de páginas para un programa. El compilador y el cargador pueden tener un efecto considerable sobre la paginación. Al separar el código y datos y generar código reentrante (no modificable) , las páginas de código pueden ser sólo de lectura y, por tanto, nunca se modificarán. El cargador puede evitar la colocación de rutinas entre páginas, o agrupar las rutinas que se llaman entre sí en una página.