Sistemas operativos modernos

Cadena de referencias 0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 1 3 4 1 0 2 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 1 3 4 1 0 2 1 3 5 4 6 3 7 4 7 7 3 3 5 3 3 3 7 1 3 4 0 2 1 3 5 4 6 3 3 4 4 7 7 7 5 5 5 3 3 7 1 3 0 2 1 3 5 4 6 6 6 6 4 4 4 7 7 7 5 5 5 7 7 0 2 1 1 5 5 5 5 5 6 6 6 4 4 4 4 4 4 5 5 0 2 2 1 1 1 1 1 1 1 6 6 6 6 6 6 6 6 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Fallos de página P P P P P P P P P P Cadena de distancias e o o o c o c o < » o o ( » 4 o o 4 2 3 l 5 l 2 6 1 1 4 2 3 Figura 4-25. Estado del arreglo M, después de procesarse cada elemento de la ca­ dena de referencias. La cadena de distancias se explicará en la siguiente sección. La primera página de la cadena de referencias es O, así que se introduce en la parte supe­ rior de la memoria, como se ve en la segunda columna. La segunda página es la 2, así que se anota en la parte superior de la tercera columna. Esta acción hace que Obaje. En este ejemplo, una página recién cargada siempre se anota en la parte superior, y todo lo demás se desplaza hacia abajo, conforme es necesario. Cada una de las siete primeras páginas de la cadena de referencias causa un fallo de pági­ na. Los primeros cuatro pueden manejarse sin desalojar páginas, pero a partir de la referencia a la página 5 la carga de una nueva página requiere el desalojo de una antigua. La segunda referencia a la página 3 no causa un fallo de página porque esa página ya está en la memoria. No obstante, el intérprete la quita de donde estaba y la coloca en la parte supe­ rior, como se muestra. El proceso continúa durante un tiempo, hasta que se hace referencia a la página 5. Esta página se pasa de la parte inferior de A/ a la superior (es decir, se carga del disco a la memoria). Cada vez que se hace referencia a una página que no está dentro del rec­ tángulo grueso, hay un fallo de página, como indican las P de abajo de la matriz. Ahora resumamos algunas de las propiedades de este modelo. Primera, cuando se hace refe­ rencia a una página, siempre se coloca en la parte superior de M. Segunda, si la página solicita­ da ya estaba en M, todas las páginas que estaban arriba de ella bajan una posición. Una transición del interior del rectángulo hacia afuera de él corresponde al desalojo de una página de la memo­ ria. Tercera, las páginas que estaban abajo de la página solicitada no se mueven. Así, el conteni­ do de M representa con exactitud el contenido del algoritmo LRU. Aunque en este ejemplo usamos LRU, el modelo también funciona bien con otros algoritmos. En particular, hay una clase de algoritmos en especial interesante: los que tienen la propiedad M(m, r) c M{m + 1 , r) donde m varía dentro del intervalo de marcos de página y r es un índice a la cadena de referen­ cias. Esto significa que el conjunto de páginas incluido en la parte superior de M para una me­ moria con m marcos de página después de r referencias a la memoria también está incluido en M para una memoria con m + l marcos de página. En otras palabras, si aumentamos, en un