Diferencia entre revisiones de «Solución ejercicio 1 memoria virtual»
De Wiki de Sistemas Operativos
(→LFU) |
(→Sustitución por envejecimiento) |
||
| Línea 250: | Línea 250: | ||
= Sustitución por envejecimiento = | = Sustitución por envejecimiento = | ||
| − | + | Periodo = 4 | |
| + | Registro R de 3 bits. | ||
| + | En caso de empate = FIFO por orden de carga | ||
| − | + | Acceso | |
| − | + | a 1 1 1 2 - 3 4 5 3 - 1 2 3 4 | |
| − | + | página | |
| − | + | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | |
| − | + | Marco 1 | 1 | = | = | = | = | = | = | 5 | = | = | = | = | = | 4 | | |
| − | + | Bit R | 100 | = | = | = | 010 | = | = | 100 | = | 010 | = | = | = | 100 | | |
| − | + | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | |
| − | + | Marco 2 | | | | 2 | = | = | = | = | = | = | 1 | = | = | = | | |
| − | + | Bit R | | | | 100 | 010 | = | = | = | = | 001 | 100 | = | = | = | | |
| − | + | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | |
| − | + | Marco 3 | | | | | | 3 | = | = | = | = | = | 2 | = | = | | |
| − | + | Bit R | | | | | | 100 | = | = | = | 010 | = | 100 | = | = | | |
| − | + | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | |
| − | + | Marco 4 | | | | | | | 4 | = | = | = | = | = | 3 | = | | |
| − | + | Bit R | | | | | | | 100 | = | = | 010 | = | = | 100 | = | | |
| − | + | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | |
| − | + | Fallo | | | | | | | | | | | | | | | | |
| − | + | de | x | | | x | - | x | x | x | | - | x | x | x | x | | |
| − | + | página | | | | | | | | | | | | | | | | |
| − | + | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | |
| + | |||
| + | Tiempo 1 2 3 4 - 5 6 7 8 - 9 10 11 12 | ||
| + | |||
| + | Periodo 4 3 2 1 0 4 3 2 1 0 4 3 2 1 | ||
| + | |||
| + | nº fallos de página 9 | ||
| + | Tasa de fallos de página = --------------------- = ---- = 0,75 | ||
| + | nº accesos a páginas 12 | ||
Revisión del 17:50 30 dic 2015
FIFO
Acceso
a 1 1 1 2 3 4 5 3 1 2 3 4
página
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 2 | | | | 2 | = | = | = | = | 1 | = | = | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 3 | | | | | 3 | = | = | = | = | 2 | = | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 4 | | | | | | 4 | = | = | = | = | 3 | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Fallo | | | | | | | | | | | | |
de | x | | | x | x | x | x | | x | x | x | x |
página | | | | | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Tiempo 1 2 3 4 5 6 7 8 9 10 11 12
nº fallos de página 9
Tasa de fallos de página = --------------------- = ---- = 0,75
nº accesos a páginas 12
NRU
Considere que el periodo de puesta a cero del bit R tiende a infinito, es decir, nunca se pone a cero.
En caso de empate, se emplea LRU(Least Recently Used): elegimos la página que más tiempo lleve sin ser accedida
Acceso
a 1(R) 1(R) 1(W) 2(R) 3(R) 4(R) 5(R) 3(W) 1(W) 2(W) 3(R) 4(R)
página
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 | = | = | = | = | = | = | = | = | = | = | = |
Marco 1 | R=1 | = | = | = | = | = | = | = | = | = | = | = |
| M=0 | = | M=1 | = | = | = | = | = | = | = | = | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | 2 | = | = | 5 | = | = | = | = | 4 |
Marco 2 | | | | R=1 | = | = | R=1 | = | = | = | = | R=1 |
| | | | M=0 | = | = | M=0 | = | = | = | = | M=0 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | 3 | = | = | = | = | = | = | = |
Marco 3 | | | | | R=1 | = | = | = | = | = | = | = |
| | | | | M=0 | = | = | M=1 | = | = | = | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| | | | | | 4 | = | = | = | 2 | = | = |
Marco 4 | | | | | | R=1 | = | = | = | R=0 | = | = |
| | | | | | M=0 | = | = | = | M=1 | = | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Fallo | | | | | | | | | | | | |
de | x | | | x | x | x | x | | | x | | x |
página | | | | | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Tiempo 1 2 3 4 5 6 7 8 9 10 11 12
nº fallos de página 7
Tasa de fallos de página = --------------------- = ---- = 0,5833333333333333
nº accesos a páginas 12
Pregunta: Creo que hay un error en el paso 10 cuando cargamos la pagina 2, en el criterio NRU comenzamos por el primer marco y buscamos la pagina victima, en este caso creo que seria la pagina 5 que esta cargada en el marco 2 y tienen R=1, M=0 no la pagina 4 como pone en el ejercicio.
Respuesta: No, es un empate. Por lo que aplicamos el criterio LRU entre 4 y 5, y 4 es la que lleva más tiempo sin usarse.
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 | 3 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | 1 | = | 0 | 1 | = | 0 | 1 | 0 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | 4 | = | = | 2 | = | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | | 1 | 0 | = | = | 1 | = | 0 |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | | X |
página -------------------------------------------------------------------------------------------------
contenido | 1 | 1 | 1 | 1-2 | 1-2-3 |1-2-3-4|2-3-4-5|2-3-4-5|3-4-5-1|5-1-3-2|5-1-3-2|1-3-2-4|
de la cola -------------------------------------------------------------------------------------------------
tiempo ->
nº fallos de página 8
Tasa de fallos de página = --------------------- = ---- = 0,6666666666666667
nº accesos a páginas 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
He puesto el orden de la cola para que se vea más claro. Cuando el candidato tiene R=1 se pone a 0 y se inserta al final. Es por eso que cuando se accede por última vez a la página 2, al estar 3 la primera, se pone su bit R a 0 se inserta al final (no estaba en la solución anterior) y la siguiente (4, con R=0) es la página víctima.--Alexrdp 09:37 14 jun 2011 (UTC)
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 | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | 1 | = | 0 | 1 | 0 | 1 | 0 | 0 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | 4 | = | = | = | 3 | 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
Esta segunda solución creo que no está del todo correcta.
Cuando llega el cuarto acceso a 1 (donde se produce el sexto fallo de página), el contenido de la cola es el siguiente:
2 (R=0) - 3 (R=1) - 4 (R=0) - 5 (R=1)
Con lo cual, la víctima es el 2, pero sin poner a 0 el resto de los bits R, ya que el primer elemento de la cola tiene el bit R=0 y no hace falta seguir iterando sobre ésta.
De acuerdo a este último comentario, quedaría de la siguiente manera:
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 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | 1 | = | = | = | = | = | 1 | = | = | = | = | 0 |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 2 | = | 1 | = | = | 1 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | 1 | = | = | 0 | = | 1 | = | = | 0 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | 3 | 3 | = | 3 | 3 | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | 1 | = | 0 | 1 | = | 0 | 1 | 1 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | 4 | = | = | 2 | = | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | | 1 | 0 | = | = | 1 | = | 0 |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | | X |
página -------------------------------------------------------------------------------------------------
talla de fallos de página = 8 / 12
Existia un fallo en el acceso número 10, donde no se ponía el bit R del marco 3 a 0 y en el último acceso, que se puso la página 4 en el marco 1, pero no es así, cuando llegamos a este acceso la cola es |3|5|1|2|, por tanto el que será reemplazado será el 3, porque será el primero en encontrarnos con el bit R a 0. Corregido por --Cripolgon
LRU
Acceso
a 1 1 1 2 3 4 5 3 1 2 3 4
página
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 2 | | | | 2 | = | = | = | = | 1 | = | = | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 3 | | | | | 3 | = | = | = | = | = | = | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 4 | | | | | | 4 | = | = | = | 2 | = | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Fallo | | | | | | | | | | | | |
de | x | | | x | x | x | x | | x | x | | x |
página | | | | | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Tiempo 1 2 3 4 5 6 7 8 9 10 11 12
nº fallos de página 8
Tasa de fallos de página = --------------------- = ---- = 0,6666666666666667
nº accesos a páginas 12
LFU
En caso de empate, se emplea LRU(Least Recently Used): elegimos la página que más tiempo lleve sin ser accedida
Acceso
a 1 1 1 2 3 4 5 3 1 2 3 4
página
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 1 | 1 | = | = | = | = | = | = | = | = | = | = | = |
Contador | C=1 | C=2 | C=3 | = | = | = | = | = | C=4 | = | = | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 2 | | | | 2 | = | = | 5 | = | = | = | = | 4 |
Contador | | | | C=1 | = | = | C=1 | = | = | = | = | C=1 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 3 | | | | | 3 | = | = | = | = | = | = | = |
Contador | | | | | C=1 | = | = | C=2 | = | = | C=3 | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 4 | | | | | | 4 | = | = | = | 2 | = | = |
Contador | | | | | | C=1 | = | = | = | C=1 | = | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Fallo | | | | | | | | | | | | |
de | x | | | x | x | x | x | | | x | | x |
página | | | | | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Tiempo 1 2 3 4 5 6 7 8 9 10 11 12
nº fallos de página 7
Tasa de fallos de página = --------------------- = ---- = 0,5833333333333333
nº accesos a páginas 12
Observación: al quitar un elemento se resetea su contador
Sustitución por envejecimiento
Periodo = 4 Registro R de 3 bits. En caso de empate = FIFO por orden de carga
Acceso
a 1 1 1 2 - 3 4 5 3 - 1 2 3 4
página
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 1 | 1 | = | = | = | = | = | = | 5 | = | = | = | = | = | 4 |
Bit R | 100 | = | = | = | 010 | = | = | 100 | = | 010 | = | = | = | 100 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 2 | | | | 2 | = | = | = | = | = | = | 1 | = | = | = |
Bit R | | | | 100 | 010 | = | = | = | = | 001 | 100 | = | = | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 3 | | | | | | 3 | = | = | = | = | = | 2 | = | = |
Bit R | | | | | | 100 | = | = | = | 010 | = | 100 | = | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Marco 4 | | | | | | | 4 | = | = | = | = | = | 3 | = |
Bit R | | | | | | | 100 | = | = | 010 | = | = | 100 | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Fallo | | | | | | | | | | | | | | |
de | x | | | x | - | x | x | x | | - | x | x | x | x |
página | | | | | | | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Tiempo 1 2 3 4 - 5 6 7 8 - 9 10 11 12
Periodo 4 3 2 1 0 4 3 2 1 0 4 3 2 1
nº fallos de página 9
Tasa de fallos de página = --------------------- = ---- = 0,75
nº accesos a páginas 12
