Sistemas operativos modernos

Como mencionamos antes, el conjunto de trabajo es el conjunto de páginas que se usaron en las k referencias más recientes a la memoria (algunos autores usan las k referencias más re­ cientes a páginas, pero esta decisión es arbitraria). Para implementar cualquier algoritmo de conjunto de trabajo, debe escogerse por adelantado el valor de k. Una vez seleccionado un va­ lor, el conjunto de páginas usadas por las k referencias previas a la memoria quedará determi­ nado de manera única después de cada referencia a la memoria. Desde luego, tener una definición operativa del conjunto de trabajo no implica que haya una forma eficiente de supervisarlo en tiempo real, durante la ejecución del programa. Imaginemos un registro de desplazamiento de longitud k. Cada referencia a la memoria lo desplaza una posición a la izquierda e inserta a la derecha el número de la página a la que se hizo referencia más recientemente. El conjunto de k números de página contenidos en el regis­ tro de desplazamiento sería el conjunto de trabajo. En teoría, al presentarse un fallo de página, el contenido del registro de desplazamiento podría leerse y ordenarse. Después de eliminar las páginas repetidas, el resultado sería el conjunto de trabajo. Sin embargo, mantener el registro de desplazamiento y procesarlo en cada fallo de página tendría un costo prohibitivo, por lo que esta técnica nunca se usa. En vez de eso, se emplean diversas aproximaciones. Una muy común consiste en desechar la idea de contar hacia atrás k referencias a la memoria, y mejor usar el tiempo de ejecución. Por ejemplo, en lugar de definir el conjunto de trabajo como las páginas que se usaron duran­ te los úlümos 10 millones de referencias a la memoria, podemos definirlo como el conjunto de páginas empleadas durante los últimos 100 milisegundos de tiempo de ejecución. En la prácti­ ca, tal definición es tan safisfactoria como la otra y mucho más fácil de usar. Cabe señalar que para cada proceso, sólo cuenta su propio tiempo de ejecución. Por tanto, si un proceso comien­ za a ejecutarse en el tiempo Ty ha tenido 40 milisegundos de tiempo de CPU en el tiempo real 7 + 1 0 0 ms, para los fines del conjunto de trabajo su tiempo será 40 milisegundos. El tiempo de CPU que ha consumido en realidad un proceso desde que se inició se conoce como su tiem­ po virtual actual. Con esta aproximación, el conjunto de trabajo de un proceso es el conjunto de páginas a las que ha hecho referencia durante los úlfimos x segundos de tiempo virtual. Ahora examinemos un algoritmo de reemplazo de páginas basado en el conjunto de traba­ jo. La idea fundamental es hallar una página que no esté en el conjunto de trabajo y desalojar­ la. En la figura 4-21 vemos una porción de la tabla de páginas de alguna máquina. Dado que sólo las páginas que están en la memoria se consideran candidatas para el desalojo, el algorit­ mo ignora las páginas ausentes. Cada entrada contiene (por lo menos) dos elementos de infor­ mación: el tiempo aproximado en que ocurrió el último uso de la página y el bit R (Solicitada). El rectángulo vacío simboliza los demás campos que no se necesitan con este algoritmo, como el número de marco de página, los bits de protección y el bit M (Modificada). El algoritmo funciona como sigue. Se supone que el hardware se encarga de encender los bits R y M, como mencionamos anteriormente. También se supone que una interrupción de re­ loj periódica causa la ejecución de software que apaga el bit Solicitada en cada tic del reloj. En cada fallo de página, la tabla de páginas se explora en busca de una apropiada para desalojar. Conforme se procesa cada entrada, se examina el bit R. Si es l, se escribe el tiempo vir­ tual actual en el campo Tiempo del último uso en la tabla de páginas, para indicar que la pági­ na se estaba usando cuando se presentó el fallo. Puesto que se hizo referencia a la página