Sistemas operativos modernos

Algoritmo Comentarlo Óptimo No implementable, pero sirve para comparar NRU (no usada recientemente) Muy burdo FIFO (primeroen entrar, primeroen salir) Podrfa desalojar páginas importantes Segunda oportunidad Muchomejor que FIFO Reloj Realista LRU (menos recientemente usada) Excelente, perodifícil de implementarcon exactitud NFU (no usada frecuentemente) Aproximación más omenos burda a LRU Envejecimiento Algoritmoeficiente que se aproxima bien a LRU Conjuntode trabajo Implementación algo costosa WSClock Algoritmoeficiente Figura 4-23. Algoritmos de reemplazo de páginas descritos en el texto. FIFO recuerda el orden en que se cargaron las páginas en la memoria, asentándolas en una lista enlazada. Así, es trivial desalojar la página más antigua, pero es posible que esa página to­ davía esté en uso, por lo que FIFO no es una buena opción. El algoritmo de segunda oportunidad es una modificación de FIFO que verifica si se está usando una página o no, antes de desalojarla. Si se está usando, se le perdona la vida. Esta mo­ dificación mejora el desempeño en forma considerable. El algoritmo de reloj no es más que otra implementación del de segunda oportunidad. Tiene las mismas propiedades de desempe­ ño, pero la ejecución del algoritmo es más rápida. LRU es un algoritmo excelente, pero no puede implementarse sin hardware especial. Si no se cuenta con ese hardware, dicho algoritmo no podrá usarse. NFU es un intento burdo por aproximarse a LRU. No es muy bueno. En cambio, el envejecimiento es una aproximación mu­ cho mejor a LRU y puede implementarse con eficiencia. Es una buena opción. Los dos últimos algoritmos emplean el conjunto de trabajo. El algoritmo de conjunto de trabajo tiene un desempeño razonable, pero su implementación es algo costosa. WSClock es una variante que no sólo tiene buen desempeño, sino que también puede implementarse con eficiencia. En síntesis, los dos mejores algoritmos son el de envejecimiento y WSClock. Se basan en LRU y en el conjunto de trabajo, respectivamente. Ambos logran un buen desempeño de pagi­ nación y se pueden implementar con eficiencia. Existen unos cuantos algoritmos más, pero es­ tos dos quizá sean los más importantes en la práctica. 4.5 MODELADO DE ALGORITMOS DE REEMPLAZO DE PÁGINAS Desde hace años se ha tratado de modelar los algoritmos de reemplazo de páginas desde un punto de vista teórico. En esta sección analizaremos algunas de esas ideas, sólo para ver cómo funciona el proceso de modelado.