Sistemas operativos modernos

Desde hace mucho se sabe que pocos programas hacen referencia a sus espacios de direccio­ nes de manera uniforme; las referencias tienden a concentrarse en un número reducido de páginas. Una referencia a la memoria puede obtener una instrucción, así como leer o almacenar datos. En cualquier instante t existe un conjunto formado por todas las páginas utilizadas por las k referen­ cias más recientes a la memoria. Este conjunto, w(ky t), es el conjunto de trabajo. Puesto que las k = 1 referencias más recientes deben haber usado todas las páginas que usaron las > 1 referen­ cias más recientes, y posiblemente otras, w(k, t) es una función monotónicamente no decreciente de k. El límite de w(A:, t) a medida que k aumenta es finito porque un programa no puede hacer re­ ferencia a más páginas de las que contiene su espacio de direcciones, y pocos programas usan todas y cada una de sus páginas. La figura 4-20 muestra el tamaño del conjunto de trabajo en función de k. Figura 4-20. El conjunto de trabajo es el conjunto de páginas utilizadas por las k re­ ferencias más recientes a la memoria. La función w{k, t) es el tamaño del conjunto de trabajo en el tiempo t. El hecho de que la mayoría de los programas tenga acceso de manera aleatoria a un núme­ ro reducido de páginas, pero que este conjunto cambie en forma lenta con el tiempo, explica la rapidez con que sube al principio la curva y la lentitud con que sube después, cuando k es gran­ de. Por ejemplo, un programa que está ejecutando un ciclo que ocupa dos páginas y utiliza da­ tos de cuatro páginas, podría hacer referencia a las seis páginas cada 1000 instrucciones, pero la referencia más reciente a alguna otra página podría haberse efectuado un millón de instruc­ ciones atrás, durante la fase de inicialización. Debido a este comportamiento asintótico, el con­ tenido del conjunto de trabajo no es sensible al valor de k escogido. Dicho de otro modo, hay una amplia gama de valores de k para los que no cambia el conjunto de trabajo. Dado que el conjunto de trabajo varía despacio con el tiempo, es posible hacer una conjetura razonable res­ pecto a cuáles páginas se necesitarán cuando el programa se reinicie, con base en su conjunto de trabajo en el momento en que se suspendió por última vez. La prepaginación consiste en cargar estas páginas antes de permitir que el proceso reanude su ejecución. Para implementar el modelo de conjunto de trabajo es necesario que el sistema operativo se mantenga al tanto de qué páginas están en él. La posesión de esta información lleva además de manera inmediata a un posible algoritmo de reemplazo de páginas: cuando ocurre un fallo de página, hallar una página que no esté en el conjunto de trabajo y desalojarla. Para implemen­ tarlo necesitamos una forma precisa de establecer cuáles páginas están en el conjunto de traba­ jo y cuáles no, en cualquier instante dado.