IIC 2332 -- Sistemas Operativos
Apuntes 17
1er Semestre 1996

Resumen

• Si no hubiera limitaciones de hardware, ¿cuál sería nuestro algoritmo preferido para el reemplazo de páginas? LRU.
• ¿Qué podemos usar en vez de LRU? El algoritmo de reloj, que usa el bit de uso (o incluso también el bit válido).
• Buffers de páginas. Usamos FIFO como nuestra política de reemplazo, pero cuando saquemos un marco de un proceso, no lo asignemos inmediatamente. Mantengamos un depósito de páginas/marcos "libres," y pongamos el marco allí. Asignamos marcos a procesos desde este depósito usando FIFO.
  • Si el proceso desde donde sacamos el marco necesita la misma página otra vez, y la página todavía está en el depósito (el marco no fue reasignado), la podemos recuperar inmediatamente.
  • Podemos escribir las páginas sucias en el depósito al disco asincrónicamente.

Asignación de marcos (OSC 9.6)

• Tenemos que decidir cuantos páginas asignar a un proceso. Hay tres consideraciones:
  • Pocos marcos por proceso implica más procesos en la memoria y entonces más procesos en la cola lista.
  • Muy pocos marcos por proceso implica que los procesos generan muchas fallas, y el rendimiento disminuye. También, la arquitectura del sistema define un número mínimo de marcos (para una instrucción y sus operandos). ¿Qué pasa si un proceso no tiene su mínimo?
  • Después de algún punto, el añadir marcos a un proceso no cambia la frecuencia de fallas significativamente. La razón es la localidad de ejecución y datos.
• Número de marcos. Podemos asignar números iguales de marcos a cada proceso. Desventaja: el desgaste de marcos con procesos pequeños. En vez de esta política, podemos asignar números proporcionales a los tamaños de los procesos (y quizás a las prioridades).
• Reemplazo global o local. Si es local, un proceso debe seleccionar una página solamente de su conjunto. Si es global, procesos pueden crecer usando los marcos de otros procesos. ¿Cuál es la ventaja? El tamaño de un proceso puede cambiar dinámicamente (afecta a otros procesos).

Thrashing (hiperpaginación) (OSC 9.7)

• En general, un proceso tiene un número de páginas que están en uso activo.
• Si el proceso no tiene suficientes marcos asignados, generará muy pronto una falla. Si suponemos que el proceso tiene que reemplazar una de sus páginas actuales con la página que causó la falla, éste fallará otra vez muy pronto (ya que todas las páginas están en uso activo).
• Entonces, el proceso pasa todo su tiempo en paginación (o sea, esperando I/O con el disco).
• En un sistema completo tenemos la siguiente situación:
  • El sistema operativo aumenta el nivel de multiprogramación cuando la utilización de la CPU esté baja algún punto. Más y más procesos entran en el sistema, y la memoria por proceso se disminuye.
  • Supone que estemos usando una política global de reemplazo y que uno de los procesos necesite más marcos. Genera una falla y toma un marco de otro proceso. Pero este proceso ahora no tiene bastante marcos, y falla también. Entonces podemos tener una cadena de fallas de muchos procesos.
  • Porque los procesos fallando están esperando I/O con el dispositivo de paginación (el disco), la cola lista se vacía. La utilización de la CPU se disminuye, ¡así el sistema operativo aumenta el nivel de la multiprogramación al hacer que más procesos entren en el sistema! La situación se empeora. Esto es thrashing. (Dibujo de la utilización vs. el nivel.)
  • Para eliminar el thrashing, tenemos que disminuir el nivel de la multiprogramación.
• Para evitar el thrashing tenemos que asegurar que los procesos tengan tantos marcos como necesiten. Es decir, cada proceso debe tener bastantes marcos para su localidad de datos y código.