Reemplazo de páginas

Escribe la cadena de páginas que pide un proceso, elige cuántos marcos tiene y el algoritmo, y mira cómo el sistema operativo decide a quién echar: la traza de los marcos se rellena referencia a referencia, con cada fallo de página, cada acierto y el porqué de cada víctima. Los fallos, la tasa de fallos y la comparativa de FIFO, LRU y el óptimo salen solos. Funciona en el navegador, también en el móvil.

Cómo se usa

  1. Escribe la cadena en cadena.txt: páginas del 0 al 9 separadas por espacios o comas (hasta 30). Empieza con la de gcc, la misma de la teoría.
  2. Elige FIFO, LRU u Óptimo y el número de marcos (de 1 a 7). La orden de la terminal cambia con lo que eliges.
  3. Pulsa Paso para ir de referencia en referencia, o Ejecutar para verlo entero. En cada paso ves qué hay en memoria, la cola, el último uso o el próximo uso de cada página, según el algoritmo, y por qué sale la víctima.
  4. Abajo, los resultados y la comparativa: los tres algoritmos con la misma cadena y una gráfica con los fallos de 1 a 7 marcos. Con Belady cargas la cadena de la anomalía y con Compartir copias un enlace con tu cadena.

Cómo se lee la traza

Cada columna es una referencia de la cadena (arriba, el instante t y la página que se pide) y cada fila, un marco. En coral, la página que acaba de entrar por un fallo de página; en verde, la página pedida que ya estaba (un acierto). La fila fallo marca con una F las columnas que fallan y la fila fuera, la víctima. Es la misma tabla que se pide en el examen.

Las cuentas: tasa de fallos = fallos ÷ referencias y tasa de aciertos = aciertos ÷ referencias. Los fallos obligatorios son la primera vez que se pide cada página: ningún algoritmo los puede evitar, así que todo lo que pase de ahí es culpa del algoritmo.

Los criterios que sigue

  • Los marcos se llenan de arriba abajo y la página nueva ocupa el marco de su víctima.
  • FIFO echa la que entró antes; LRU, la que lleva más tiempo sin usarse (un acierto renueva su último uso).
  • El óptimo echa la que más tarde se volverá a pedir. Si varias no vuelven nunca, sale la primera según el orden de los marcos, como en la teoría.
  • Los números de marco (5, 9, 2…) son los de la teoría: da igual cuáles sean, lo que cuenta es cuántos hay.

Qué algoritmo gana

Con la cadena de gcc y 3 marcos salen 11 fallos con FIFO (tasa del 73,3 %), 9 con LRU (60 %) y 7 con el óptimo (46,7 %); 6 de ellos son obligatorios. El óptimo es imposible en un sistema operativo real porque necesita conocer el futuro, pero sirve de vara de medir: LRU se acerca bastante mirando solo el pasado. Y FIFO tiene una trampa: con la cadena 3, 1, 4, 2, 3, 1, 5, 3, 1, 4, 2, 5 da 9 fallos con 3 marcos y 10 con 4. Es la anomalía de Belady: más marcos, más fallos. Pulsa Belady y mira la gráfica.