Solución ejercicio 1 memoria virtual
FIFO
accesos a páginas ------------------------------------------------------------------------- | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 | --------------------------------------------------------------------------------- | 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 | --------------------------------------------------------------------------------- marcos | 2 | | | | 2 | = | = | = | = | 1 | = | = | = | -------------------------------------------------------------------------------- | 3 | | | | | 3 | = | = | = | = | 2 | = | = | --------------------------------------------------------------------------------- | 4 | | | | | | 4 | = | = | = | = | 3 | = | --------------------------------------------------------------------------------- fallo | X | | | X | X | X | X | | X | X | X | X | página ------------------------------------------------------------------------- tiempo -> 9 talla de fallos de página = ------ = 0.75 12
NRU
En caso de empate, se emplea LRU.
accesos a páginas | r | r | w | r | r | r | r | w | w | w | r | r | ------------------------------------------------------------------------------------------------- | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 | --------------------------------------------------------------------------------------------------------- | 1 | 1 | = | = | = | = | = | = | = | = | = | = | = | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | R | M | 1 | 0 | = | = | 1 | 1 | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | --------------------------------------------------------------------------------------------------------- marcos | 2 | | | | 2 | = | = | 5 | = | = | = | = | 4 | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | R | M | | | | | | | 1 | 0 | = | = | = | = | 1 | 0 | = | = | = | = | = | = | = | = | 1 | 0 | --------------------------------------------------------------------------------------------------------- | 3 | | | | | 3 | = | = | 3 | = | = | = | = | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | R | M | | | | | | | | | 1 | 0 | = | = | = | = | 1 | 1 | = | = | = | = | = | = | = | = | --------------------------------------------------------------------------------------------------------- | 4 | | | | | | 4 | = | = | = | 2 | = | = | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | R | M | | | | | | | | | | | 1 | 0 | = | = | = | = | = | = | 1 | 1 | = | = | = | = | --------------------------------------------------------------------------------------------------------- fallo | X | | | X | X | X | X | | | X | | X | página ------------------------------------------------------------------------------------------------- tiempo -> 7 talla de fallos de página = ------ = 0.583 12
NRU con 2º oportunidad
accesos a páginas | r | r | w | r | r | r | r | w | w | w | r | r | ------------------------------------------------------------------------------------------------- | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 | --------------------------------------------------------------------------------------------------------- | 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | R | 1 | = | = | = | = | = | 1 | = | = | = | = | 1 | --------------------------------------------------------------------------------------------------------- marcos | 2 | | | | 2 | = | = | 2 | = | 1 | = | = | 1 | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | R | | | | 1 | = | = | 0 | = | 1 | = | = | 0 | --------------------------------------------------------------------------------------------------------- | 3 | | | | | 3 | = | 3 | 3 | = | = | 3 | 3 | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | R | | | | | 1 | = | 0 | 1 | = | = | 1 | 0 | --------------------------------------------------------------------------------------------------------- | 4 | | | | | | 4 | 4 | = | = | 2 | = | 2 | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | R | | | | | | 1 | 0 | = | = | 1 | = | 0 | --------------------------------------------------------------------------------------------------------- fallo | X | | | X | X | X | X | | X | X | | X | página ------------------------------------------------------------------------------------------------- tiempo -> 8 talla de fallos de página = ------ 12
Creo que es asi, pero no me lo tomeis a pies juntillas que no estoy muy seguro.
Por favor que alguien explique bien este criterio, que en cada ejercicio se aplica de una forma diferente.Gracias
Explicación:
El criterio se basa en combinar el NRU (sin bit M) con FIFO. En la cola se van añadiendo las páginas según se cargan con su respectivo valor del bit R. A la hora de sustituir se mira el candidato de la cabecera de la cola. Si su R=1, se le da una segunda oportunidad desplazándolo al final de la cola y poniendo su bit R=0. Si hubiera tenido el R=0, se hubiera tomada esa página como víctima. Eso es lo que sucede cuando llega la página 5. En ese momento la cola es 1 2 3 4 con su bit R=1 en todas las páginas. Se va mirando el candidato si tiene el bit R=0 como no es así, pasa al final de la cola. Llega un momento en el que la página 1 vuelve a la cabecera(en este caso con R=0),por lo que ahora si es sustituida por la página 5.Jherrera
Una Dudilla : la FIFO es por orden de carga o por orden de acceso?¿ Según veo en el ejercicio lo hace por orden de acceso --DvS 013 -- Respuesta : La fifo almacena el tiempo que una página lleva cargada en memoria, por lo que es por orden de carga. JCGarrido
Entonces, sería asi:
accesos a páginas | r | r | w | r | r | r | r | w | w | w | r | r | ------------------------------------------------------------------------------------------------- | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 | --------------------------------------------------------------------------------------------------------- | 1 | 1 | = | = | = | = | = | 5 | = | 5 | = | = | 4 | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | R | 1 | = | = | = | = | = | 1 | = | 0 | = | = | 1 | --------------------------------------------------------------------------------------------------------- marcos | 2 | | | | 2 | = | = | 2 | = | 1 | = | 1 | 1 | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | R | | | | 1 | = | = | 0 | = | 1 | = | 0 | 0 | --------------------------------------------------------------------------------------------------------- | 3 | | | | | 3 | = | 3 | 3 | 3 | = | 2 | 2 | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | R | | | | | 1 | = | 0 | 1 | 0 | = | 1 | 0 | --------------------------------------------------------------------------------------------------------- | 4 | | | | | | 4 | 4 | = | = | 2 | = | 3 | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | R | | | | | | 1 | 0 | = | = | 1 | = | 0 | --------------------------------------------------------------------------------------------------------- fallo | X | | | X | X | X | X | | X | X | X | X | página ------------------------------------------------------------------------------------------------- tiempo -> 9 talla de fallos de página = ------ 12
LRU
accesos a páginas ------------------------------------------------------------------------- | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 | --------------------------------------------------------------------------------- | 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 | --------------------------------------------------------------------------------- marcos | 2 | | | | 2 | = | = | = | = | 1 | = | = | = | -------------------------------------------------------------------------------- | 3 | | | | | 3 | = | = | = | = | = | = | = | --------------------------------------------------------------------------------- | 4 | | | | | | 4 | = | = | = | 2 | = | = | --------------------------------------------------------------------------------- fallo | X | | | X | X | X | X | | X | X | | X | página ------------------------------------------------------------------------- tiempo -> 8 talla de fallos de página = ------ 12
LFU
accesos a páginas | r | r | w | r | r | r | r | w | w | w | r | r | ------------------------------------------------------------------------------------------------- | 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 | --------------------------------------------------------------------------------------------------------- | 1 | 1 | 1 | 1 | = | = | = | = | = | 1 | = | = | 1 | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | C | 1 | 2 | 3 | = | = | = | = | = | 4 | = | = | 4 | --------------------------------------------------------------------------------------------------------- marcos | 2 | | | | 2 | = | = | 5 | = | = | = | = | 4 | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | C | | | | 1 | = | = | 1 | = | = | = | = | 1 | --------------------------------------------------------------------------------------------------------- | 3 | | | | | 3 | = | = | 3 | = | = | 3 | 3 | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | C | | | | | 1 | = | = | 2 | = | = | 3 | 3 | --------------------------------------------------------------------------------------------------------- | 4 | | | | | | 4 | = | = | = | 2 | = | 2 | | |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | C | | | | | | 1 | = | = | = | 1 | = | 1 | --------------------------------------------------------------------------------------------------------- fallo | X | | | X | X | X | X | | | X | | X | página ------------------------------------------------------------------------------------------------- tiempo -> 7 talla de fallos de página = ------ 12
Observación: al quitar un elemento se resetea su contador
Sustitución por envejecimiento
Periodo de 4, registro R de 3 bits, desempate: FIFO (por orden de carga)
_________________accesos a página__________________ |_1_|_1_|_1_|_2_||_3_|_4_|_5_|_3_||_1_|_2_|_3_|_4_| ====================================================== 1 | 1 | = | = | = || 1 | = | 5 | = || 5 | = | = | 4 | |100| = | = | = ||010| = |100| = ||010| = | = |100| m---|---|---|---|---||---|---|---|---||---|---|---|---| a 2 | | | | 2 || 2 | = | = | = || 1 | = | = | = | r | | | |100||010| = | = | = ||100| = | = | = | c---|---|---|---|---||---|---|---|---||---|---|---|---| o 3 | | | | || 3 | = | = | = || 3 | 2 | = | = | s | | | | ||100| = | = | = ||010|100| = | = | ---|---|---|---|---||---|---|---|---||---|---|---|---| 4 | | | | || | 4 | = | = || 4 | = | 3 | = | | | | | || |100| = | = ||010| = |100| = | --------------------------------------------------------> t x x x x x x x x x 9 tasa fallos pág = ---- 12