Diferencia entre revisiones de «Solución ejercicio 1 memoria virtual»
De Wiki de Sistemas Operativos
(Corrección del ejercicio con NRU y 2ª oportunidad.) |
(→Sustitución por envejecimiento) |
||
| Línea 173: | Línea 173: | ||
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | ||
Marco 2 | | | | 2 | = | = | = | = | = | = | 1 | = | = | = | | Marco 2 | | | | 2 | = | = | = | = | = | = | 1 | = | = | = | | ||
| − | Bit R | | | | 100 | 010 | = | = | = | = | 001 | | + | Bit R | | | | 100 | 010 | = | = | = | = | 001 | 011 | = | = | = | |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | ||
Marco 3 | | | | | | 3 | = | = | = | = | = | 2 | = | = | | Marco 3 | | | | | | 3 | = | = | = | = | = | 2 | = | = | | ||
Revisión del 01:55 21 dic 2016
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=1 | = | = |
| | | | | | 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 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | 1 | = | 0 | 1 | = | = | 1(=) | 0 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | 4 | = | = | 2 | = | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | | 1 | 0 | = | = | 1 | = | 0 |
---------------------------------------------------------------------------------------------------------
fallo | AF | | | AF | AF | AF | 5R1 | | 1R2 | 2R4 | | 4R5 |
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
12
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 | 011 | = | = | = |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
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
