CAPÍTULO 4

EJERCICIO 4.1

Sea un sistema de paginación con un tamaño de página P. Especifique cuál sería la fórmula matemática que determina la dirección de memoria física F a partir de la dirección virtual D, siendo la función MARCO (x) una que devuelve el numero de marco almacenado en la entrada X de la tabla de páginas.

F = NM(F) + Db(F)

EJERCICIO 4.2

¿ Es siempre el algoritmo de reemplazo LRU mejor que el FIFO? En caso afirmativo, plantee una demostración. En caso negativo, proponga un contraejemplo.

Generalmente, si es mejor el algoritmo LRU que el FIFO. Sin embargo y a pesar de que el LRU no tiene la anomalía de Belady y el FIFO si, este puede presentar un comportamiento mejor en códigos, en los cuales, se referencie con no mucha frecuencia a las mismas páginas de memoria. De este modo, se evitaría que las páginas que se sustituyen en memoria se referenciaran en un corto espacio de tiempo, con lo cual, se minimizarían los fallos de página, obteniendo así un buen rendimiento, posiblemente superior al LRU.

EJERCICIO 4.4

El lenguaje C define el calificador volatile aplicable a variables. La misión de este calificador es evitar problemas de coherencia en aquellas variables que se acceden tanto desde el flujo de ejecución normal como desde flujos asíncronos, como por ejemplo una rutina asociada a una señal POSIX. Analice que tipo de problemas podrían aparecer y proponga un método para resolver los problemas identificados para las variables etiquetadas con este calificador.

La palabra volatile indica que un determinado objeto de datos puede ser modificado por medios externos al programa en que aparece. Debido a esto, podría surgir el problema de que un compilador tratara de alterar el valor de una variable, al comprobar que ha sido utilizada en dos lugares diferentes. Sin embargo, y a través del empleo de volatile, el compilador se daría cuenta que el programa no ha hecho nada por modificar la variable en medio de las dos utilizaciones, es decir, se daría cuenta de que la segunda utilización no corresponde al programa, con lo que, descartaría la posibilidad de tratar de actualizar con el valor de la segunda utilización.

EJERCICIO 4.5

Algunas MMU no proporcionan un BIT de página accedida. Proponga una manera de simularlo. Una pista : se pueden forzar fallos de página para detectar accesos a una página.

Modificando los permisos de lectura de una página.

EJERCICIO 4.6

Algunas MMU no proporcionan un BIT de página modificada. Proponga una manera de simularlo.

se modifican los permisos de escitura.

EJERCICIO 4.9

¿ Por qué una cache que se accede con direcciones virtuales puede producir incoherencias y requiere que el sistema operativo la invalide en cada cambio de proceso y, en cambio, una que se accede con direcciones físicas no lo requiere?

Porqué las direcciones virtuales no corresponden con el mismo dato para procesos distintos, mientras que las direcciones físicas sí.

EJERCICIO 4.10

¿ Por qué una cache que se accede con direcciones virtuales permite que el acceso a la TLB y a la cache se hagan en paralelo y, en cambio, una que se accede con direcciones físicas no lo permite? ¿ Por qué es conveniente que las caches que se acceden con direcciones físicas tengan el mismo tamaño que la página?

Porque en el primer caso ambas direcciones se corresponden y se pueden comparar, mientras que en el segundo caso no podemos comparar dirección física con virtual.

Para poder anular la caché más fácilmente cuando haga cambios en la memoria y así evitamos posibles inconsistencias.

EJERCICIO 4.11

La secuencia que se utiliza típicamente como ejemplo de la anomalía de Belady es la siguiente:

1 2 3 4 1 2 5 1 2 3 4 5

Analice cuántos fallos de página se producen al usar el algoritmo FIFO teniendo 3 marcos y cuántos con 4 marcos. Compárelo con el algoritmo LRU. ¿Qué caracteriza a los algoritmos de reemplazo de pila?

Con 3 marcos y el algoritmo FIFO se tendrían 5 fallos de página, distribuidos en dos fallos para la página 4 y un fallo para las páginas 1, 3 y 5.

Con 4 marcos y el algoritmo FIFO se tendrían 6 fallos de página, distribuidos en dos fallos para la página 5 y un fallo para el resto de las páginas.

Con 3 marcos y el algoritmo LRU se tendrían 7 fallos de página, distribuidos en dos fallos para la página 4 y un fallo para las páginas 1,2, 3 y 5.

Con 4 marcos y el algoritmo LRU se tendrían 2 fallos de página, distribuidos en un fallo para la página 4 y un fallo para las páginas 5.

Como se puede observar el número de fallos de página es mucho inferior en LRU a medida que aumentamos el número de marcos. Sin embargo, este cambio no es tan acusado en el algoritmo FIFO que se mantiene más constante.

Esto se debe a que el algoritmo LRU no sufre la anomalía de Belady, ya que, pertenece a la familia de los algoritmos de pila. La característica principal de estos algoritmos es que las páginas residentes en memoria para un sistema con n marcos de página son siempre un subconjunto de las que habría en un subconjunto de n+1 marcos. Esta propiedad es la que asegura que estos algoritmos no sufran la anomalía de Belady.

EJERCICIO 4.13

Sea un sistema de memoria virtual sin buffering de páginas. Analice la evolución de una página en este sistema dependiendo de la región a la que pertenece. Estudie los siguientes tipos:

- Página de código.

Se lee del fichero de programa original y no se modifica, pudiéndose así, expulsar y volver a leer del fichero.

- Página de datos con valor inicial.

Se lee del fichero y una vez es modificado, se expulsa al swap y se lee de ahí.

- Página de datos sin valor inicial.

No se lee del fichero y al modificarlo se expulsa y se lee del swap.

- Página de un archivo proyectado.

Nunca va al swap y siempre se lee, se escribe y se expulsa del archivo.

- Página de una zona de memoria compartida.

Depende de los procesos. Se libera al liberarse todos los procesos yendo al swap.

EJERCICIO 4.14

Resuelva el ejercicio anterior suponiendo que hay buffering de páginas.

La diferencia cuando hay buffering, es que el sistema operativo reserva una serie de marcos libres en memoria y cuando se produce un fallo de página, asigna un marco libre. Hay un umbral de marcos libres, que cuando es rebasado el SSOO comienza a aplicar el algoritmo de reemplazo hasta que se llega a sobrepasar el umbral de nuevo.

EJERCICIO 4.17

Como se comento en la explicación del algoritmo de reemplazo LRU, el tiempo que se debe usar para seleccionar la página menos recientemente usada es el tiempo lógico de cada proceso y no el tiempo real. Modifique la implementación basada en contadores propuesta en el texto para que tenga en cuenta esta consideración.

Lo único que hay que hacer es usar un contador monótono creciente para dar valor al campo LRU de cada página. Con este contador, que se inicia a 1, cada vez que se toca una página se incrementa en 1 el contador. De esta forma, las páginas más recientes, tienen el contador más alto.

Este contador mide el “tiempo lógico” de un proceso en cuanto a accesos a páginas se refiere y lo relaciona con el tiempo global lógico de todos los procesos del sistema.

EJERCICIO 4.18

Un algoritmo de reemplazo no descrito en el texto es el MFU (menos frecuentemente utilizada). Este algoritmo elige para el reemplazo aquella página que se haya utilizado menos frecuentemente. Analice cuál son los puntos más fuertes y débiles de este algoritmo y plantee una implementación de este algoritmo.

La principal ventaja del algoritmo MFU es que tiene un rendimiento similar a LRU, con la ventaja de que MFU a diferencia de LRU se implementa en software, con lo cual, no necesita que la máquina en la que este implementado posea un hardware específico.

El principal problema del algoritmo MFU es que nunca olvida. Esto en determinadas circunstancias podría llevar a que el sistema operativo elimine las páginas útiles en vez de las que ya no se utilizan. La razón es que si una página se usó muy frecuentemente en el pasado, tendrá un valor de frecuencia alto y no será elegida como víctima, aunque nunca más se vuelva a usar.

Una posible implementación de MFU es usando un contador de valor inicial 0 (a nivel software) asociado a cada página e incrementarlo cada vez que se accede a la página. Para resolver el problema anterior, se podría intentar hacer una mezcla de LRU y MFU usando dos contadores.

EJERCICIO 4.21

En la descripción de la técnica COW se explicó que para implementar esta técnica generalmente se pone la página con una protección de solo lectura. Analice como sería la rutina de tratamiento de la excepción que se produce al escribir en una página de este tipo para implementar la técnica COW.

La excepción que llamaría a la rutina de tratamiento vendría producida por un proceso , que trata de escribir en una región compartida, cuando el SSOO utiliza la técnica COW.

La rutina tendría los siguientes pasos:

- El SO crea una copia privada de la página compartida para el proceso que provocó la excepción.

- El SO decrementa el contador de procesos para la región compartida (ya que el proceso de la excepción , ahora utilizará su copia privada, y por tanto, la región compartida de antes será utilizada por un proceso menos).

- Si el contador llega a 1, se quita la marca de COW, ya que, la página ya no tendrá duplicados.

EJERCICIO 4.26

¿Por qué es necesario mantener al menos una página inválida entre la región de pila y la región que esta situada justo encima?

Para que haya una excepción, caso de que, se salga de la pila antes de entrar en otra región.

EJERCICIO 4.27

Analice qué puede ocurrir en un sistema que usa paginación por demanda si se recompila un programa mientras se esta ejecutando. Proponga soluciones a los problemas que pueden surgir en esta situación.

Dado que se usa el fichero para cargar en memoria, si se modifica, se mezclarán páginas del fichero antiguo con páginas del fichero nuevo y habrá posibles inconsistencias.

EJERCICIO 4.28

En POSIX se define el servicio msync que permite forzar la escritura inmediata de una región al soporte. ¿ En que situaciones puede ser interesante usar esta función?

msync vuelca a disco los cambios hechos en la copia en memoria de un fichero que ha sido mapeado en memoria empleando mmap. Sin la utilización de esta llamada no está garantizado que los cambios se escriban de vuelta

antes de que se llame a munmap. Esto puede ser muy interesante en algunos casos como por ejemplo cuando se cae inesperádamente el sistema, permitiendo tener una rutina que permita a través del servicio msync, guardar todo lo proyectado en memoria, lo más actualizado posible.

EJERCICIO 4.29

Cuando se produce un fallo en una página que pertenece a una región compartida, se trae a memoria secundaria la página y se actualiza la entrada de la tabla de páginas del proceso que causo el fallo. ¿ Cómo se enteran el resto de los procesos que comparten la página de que esta ya esta en memoria?

Se enteran porque al traer a memoria la página, el SO tiene almacenada información de todos los procesos que acceden a esta página compartida y en ese caso el SO se encarga de actualizar el bit de presente/ausente en dichos procesos.

EJERCICIO 4.30

El mecanismo de buffering permite recuperar una página que esta en la lista de libres ya que todavía no se ha reutilizado el marco que la contiene. ¿ Cómo se puede implementar esta búsqueda en la lista para que se haga de forma eficiente ?

Usando la tabla hash con direcciones físicas.

EJERCICIO 4.31

Analice que situaciones se pueden producir en el tratamiento de un fallo de TLB en un sistema que tiene una gestión software de la TLB.

En un sistema cuya TLB va gestionada por Software, y tras producirse un fallo de página ocurre lo siguiente:

- La MMU busca la traducción en la TLB. Si la encuentra la inserta en memoria principal y listo. Pero si no la encontrara se produciría el fallo de página y se activa el SSOO.

- El S. operativo busca en la tabla de páginas “a mano” e inserta en la TLB la traducción, desde donde la MMU, ya sabe introducirla en memoria principal.

EJERCICIO 4.32

Con el uso de la técnica de proyección de archivos se produce una cierta unificación entre el sistema de archivos y la gestión de memoria. Puesto que, como se verá en el capítulo dedicado a los archivos, el sistema de archivos usa una cache de bloques al disco, analice que tipo de incoherencias pueden producirse si se accede a un archivo usando la proyección y las primitivas convencionales del sistema de archivos.

Si se accede a un fichero con proyección y con operaciones de lectura/ escritura, en ocasiones, ocurre que los bloques de datos se almacenan en lugares distintos y se pueden crear incoherencias.