Diferencia entre revisiones de «Solución ejercicio 1 memoria virtual»

De Wiki de Sistemas Operativos
Saltar a: navegación, buscar
(Respuesta a duda)
(LRU: Corrección del ejercicio, fallo en el tiempo 10 y 11)
 
(No se muestran 46 ediciones intermedias de 11 usuarios)
Línea 1: Línea 1:
 
= FIFO =
 
= FIFO =
                                          accesos a páginas
+
 
                -------------------------------------------------------------------------
+
Acceso
                |  1 1 1 2 3 4 5 3 1 2 3 |
+
  a        1     1     1     2     3     4     5     3     1     2     3     4
        ---------------------------------------------------------------------------------
+
  página
        |  1   |  1  |  =  |  =  |  =  |  =  |  =  |  5  |  =  |  =  |  =  |  =  |  4  |
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        ---------------------------------------------------------------------------------
+
Marco 1 |  1  |  =  |  =  |  =  |  =  |  =  |  5  |  =  |  =  |  =  |  =  |  4  |
  marcos |  2  |    |    |    |  2  |  =  |  =  |  =  |  =  |  1  |  =  |  =  |  =  |
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        --------------------------------------------------------------------------------
+
  Marco 2 |    |    |    |  2  |  =  |  =  |  =  |  =  |  1  |  =  |  =  |  =  |
        |  3   |    |    |    |    |  3  |  =  |  =  |  =  |  =  |  2  |  =  |  =  |
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        ---------------------------------------------------------------------------------
+
Marco 3 |    |    |    |    |  3  |  =  |  =  |  =  |  =  |  2  |  =  |  =  |
        |  4   |    |    |    |    |    |  4  |  =  |  =  |  =  |  =  |  3  |  =  |
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        ---------------------------------------------------------------------------------
+
Marco 4 |    |    |    |    |    |  4  |  =  |  =  |  =  |  =  |  3  |  =  |
  fallo          X |    |    |  X X X X |    |  X X X X |
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
  página         -------------------------------------------------------------------------
+
  Fallo    |    |    |    |    |    |    |    |    |    |    |    |    | 
 +
  de      x |    |    |  x x x x |    |  x x x x |
 +
  página   |    |    |    |    |    |    |    |    |    |    |    |    |
 +
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 
   
 
   
                                              tiempo ->
+
Tiempo      1    2    3    4    5    6    7    8    9    10    11    12
 
   
 
   
 
   
 
   
                                9
+
                              nº fallos de página    9
talla de fallos de página = ------ = 0.75
+
  Tasa de fallos de página = --------------------- = ---- = 0,75
                                12
+
                              nº accesos a páginas    12
  
 
= NRU =
 
= 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''
  
En caso de empate, se emplea LRU.
+
Acceso
                                          accesos a páginas
+
  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
                |  r  |  r  |  w  |  r  |  r  |  r  |  r  |  w  |  w  |  w  |  r  |  r  |
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
                -------------------------------------------------------------------------------------------------
+
          | 1 | = | = | = | = | = | = | = | = | = | = | = |
                |  1   |  1   |  1  |  2   |  3   |  4   |  5   |  3   |  1   |  2   |  3   |  4   |
+
Marco 1  | R=1 | | = | = | | | = | = | = | = | = | = |
        ---------------------------------------------------------------------------------------------------------
+
          | M=0 | = | M=1 | = | = | = | = | = | = | = | = | = |
        |   1   |   1  |  =   |   =   |   =   |   =   |   =   |   =   |   =   |   =   |   =   |   =   |   =   |
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        |      |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
+
          |     |     |     | 2 | = | = | 5 | = | = | = | = | 4 |
        | R | M | 1 | 0 | = | = | 1 | 1 | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = |
+
Marco 2  |     |     |     | R=1 | | | R=1 | | | | | R=1 |
        ---------------------------------------------------------------------------------------------------------
+
          |     |     |     | M=0 | = | = | M=0 | = | = | = | = | M=0 |
marcos  |   2  |       |       |       |  2   |   =   |   =   |   5   |   =   |   =   |   =   |   =   |   4   |
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
+
          |     |     |     |     | 3 | = | = | | = | = | = | = |
        | R | M |  |  |  |  |  |  | 1 | 0 | = | = | = | = | 1 | 0 | = | = | = | = | = | = | = | = | 1 | 0 |
+
Marco 3  |     |     |     |     | R=1 | | | | | | | |
        ---------------------------------------------------------------------------------------------------------
+
          |     |     |     |     | M=0 | = | = | M=1 | = | = | = | = |
        |   3  |       |       |       |       |  3   |   =   |   =   |   3  |   =   |   =   |   =   |   =   |
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
+
          |     |     |     |     |     | 4 | = | = | = | 2 | = | = |
        | R | M |   |   |  |  |  |  |  |  | 1 | 0 | = | = | = | = | 1 | 1 | = | = | = | = | = | = | = | = |
+
Marco 4  |     |     |     |     |     | R=1 | | | | R=1 | | |
        ---------------------------------------------------------------------------------------------------------
+
          |     |     |     |     |     | M=0 | = | = | = | M=1 | = | = |
        |   4  |       |       |       |       |       |  4   |   =   |   =   |   =   |   2   |   =   |   =   |
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
+
  Fallo    |    |    |    |    |    |    |    |    |    |    |    |    |
        | R | M |   |   |   |  |  |  |  |  |  |  | 1 | 0 | = | = | = | = | = | = | 1 | 1 | = | = | = | = |
+
   de      |  x  |     |     | | | | |     |     | |     | |
        ---------------------------------------------------------------------------------------------------------
+
  página   |    |    |    |    |    |    |    |    |    |    |    |    |
  fallo          |       |       |   X  |   X  |   X  |   X  |       |       |   X  |       |   X  |
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
  página         -------------------------------------------------------------------------------------------------
 
 
   
 
   
                                              tiempo ->
+
Tiempo      1    2    3    4    5    6    7    8    9    10    11    12
 
   
 
   
                                7
+
                              nº fallos de página    7
talla de fallos de página = ------ = 0.583
+
  Tasa de fallos de página = --------------------- = ---- = 0,5833333333333333
                                12
+
                              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 =
 
= NRU con 2º oportunidad =
Línea 74: Línea 83:
 
         |  3  |      |      |      |      |  3  |  =  |  3  |  3  |  =  |  =  |  3  |  3  |
 
         |  3  |      |      |      |      |  3  |  =  |  3  |  3  |  =  |  =  |  3  |  3  |
 
         |      |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
 
         |      |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
         |  R  |      |      |      |      |  1  |  =  |  0  |  1  |  =  |  =  |   1   |  0  |
+
         |  R  |      |      |      |      |  1  |  =  |  0  |  1  |  =  |  =  | 1(=) |  0  |
 
         ---------------------------------------------------------------------------------------------------------
 
         ---------------------------------------------------------------------------------------------------------
 
         |  4  |      |      |      |      |      |  4  |  4  |  =  |  =  |  2  |  =  |  2  |
 
         |  4  |      |      |      |      |      |  4  |  4  |  =  |  =  |  2  |  =  |  2  |
Línea 80: Línea 89:
 
         |  R  |      |      |      |      |      |  1  |  0  |  =  |  =  |  1  |  =  |  0  |
 
         |  R  |      |      |      |      |      |  1  |  0  |  =  |  =  |  1  |  =  |  0  |
 
         ---------------------------------------------------------------------------------------------------------
 
         ---------------------------------------------------------------------------------------------------------
  fallo          |  |      |      |  |   X  |      |   X  |   X  |      |   X  |
+
  fallo          |  AF  |      |      |  AF  AF  AF  | 5R1  |      | 1R2  | 2R4  |      | 4R5  |
 
  página          -------------------------------------------------------------------------------------------------
 
  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 ->
 
                                               tiempo ->
+
 
                                8
+
                              nº fallos de página    8
talla de fallos de página = ------  
+
  Tasa de fallos de página = --------------------- = ---- = 0,6666666666666667
                                12
+
                                                      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.[[Usuario:Jherrera|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 --[[Usuario:DvS 013|DvS 013]]
 
  
 
= LRU =
 
= LRU =
  
                                      accesos a páginas
+
Acceso
                -------------------------------------------------------------------------
+
  a         1     1     1     2     3     4     5     3     1     2     3     4
                |  1 1 1 2 3 4 5 3 1 2 3 |
+
  página
        ---------------------------------------------------------------------------------
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        |  1   |  1  |  =  |  =  |  =  |  =  |  =  |  5  |  =  |  =  |  =  |  =  |  4  |
+
Marco 1 |  1  |  =  |  =  |  =  |  =  |  =  |  5  |  =  |  =  |  =  |  =  |  4  |
        ---------------------------------------------------------------------------------
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
  marcos |  2  |    |    |    |  2  |  =  |  =  |  =  |  =  |  1  |  =  |  =  |  =  |
+
  Marco 2 |    |    |    |  2  |  =  |  =  |  =  |  =  |  1  |  =  |  =  |  =  |
        --------------------------------------------------------------------------------
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        |  3   |    |    |    |    |  3  |  =  |  =  |  =  |  =  |  = |  =  |  =  |
+
Marco 3 |    |    |    |    |  3  |  =  |  =  |  =  |  =  |  2 |  =  |  =  |
        ---------------------------------------------------------------------------------
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        |  4   |    |    |    |    |    |  4  |  =  |  =  |  =  |  2 = |  =  |
+
Marco 4 |    |    |    |    |    |  4  |  =  |  =  |  =  |  = 3 |  =  |
        ---------------------------------------------------------------------------------
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
  fallo          X |    |    |  X X X X |    |  X X |     X |
+
  Fallo    |    |    |    |    |    |    |    |    |    |    |    |    | 
  página         -------------------------------------------------------------------------
+
  de      x |    |    |  x x x x |    |  x x | x |
 +
  página   |    |    |    |    |    |    |    |    |    |    |    |    |
 +
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 
   
 
   
                                              tiempo ->
+
Tiempo      1    2    3    4    5    6    7    8    9    10    11    12
 
   
 
   
+
                            nº fallos de página    9
                                8
+
  Tasa de fallos de página = --------------------- = ---- = 0,75
  talla de fallos de página = ------  
+
                            nº accesos a páginas    12
                                12
 
  
 +
= LFU =
  
= LFU =
+
En caso de empate, se emplea LRU(Least Recently Used): ''elegimos la página que más tiempo lleve sin ser accedida''
  
                                                  accesos a páginas
+
  Acceso
   
+
  a        1     1     1     2     3     4     5     3     1     2     3     4
                |  r  |  r  |  w  |  r  |  r  |  r  |  r  |  w  |  w  |  w  |  r  |  r  |
+
página
                -------------------------------------------------------------------------------------------------
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
                |  1   |  1   |  1   |  2   |  3   |  4   |  5   |  3   |  1   |  2   |  3   |  4   |
+
Marco 1 | 1 | | | = | = | = | = | = | | = | = | |
        ---------------------------------------------------------------------------------------------------------
+
Contador | C=1 | C=2 | C=3 | = | = | = | = | = | C=4 | = | = | |
        |  1   |   1   |   1  |   1  |   =   |   =   |   =   |   =   |   =   |   1  |   =   |   =   |   1  |
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        |      |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
+
  Marco 2 |     |     |     | 2 | = | = | 5 | = | = | = | = | 4 |
        |  C   |  1   |   2   |   3   |   =   |   =   |   =   |   =   |   =   |   4   |   =   |   =   |   4  |
+
Contador |     |     |     | C=1 | = | = | C=1 | = | = | = | = | C=1 |
        ---------------------------------------------------------------------------------------------------------
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
  marcos |   2  |       |       |       |  2   |   =   |   =   |   5   |   =   |   =   |   =   |   =   |   4   |
+
Marco 3 |     |     |     |     | 3 | = | = | | = | = | | |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
+
Contador |     |     |     |     | C=1 | = | = | C=2 | = | = | C=3 | |
        |  C   |      |      |      |  1   |   =   |   =   |   1   |   =   |   =   |   =   |   =   |   1   |
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        ---------------------------------------------------------------------------------------------------------
+
Marco 4 |     |     |     |     |     | 4 | = | = | = | 2 | = | |
        |  3   |       |       |       |       |   3   |   =   |   =   |   3  |   =   |   =   |   3  |   3  |
+
Contador |     |     |     |     |     | C=1 | = | = | = | C=1 | = | |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
        |  C   |      |      |      |      |  1   |   =   |   =   |   2   |   =   |   =   |   3   |   3  |
+
  Fallo    |    |    |    |    |    |    |    |    |    |    |    |    |
        ---------------------------------------------------------------------------------------------------------
+
   de      |  x  |     |     | | | | |     |     | |     | |
        |  4   |       |       |       |       |       |   4   |   =   |   =   |   =   |   2   |   =   |   2  |
+
  página   |    |    |    |    |    |    |    |    |    |    |    |    |
        |      |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
        |   C   |      |      |      |      |      |  1   |   =   |   =   |   =   |   1   |   =   |   1  |
 
        ---------------------------------------------------------------------------------------------------------
 
  fallo          |       |       |   X  |   X  |   X  |   X  |       |       |   X  |       |   X  |
 
  página         -------------------------------------------------------------------------------------------------
 
 
   
 
   
                                              tiempo ->
+
Tiempo      1    2    3    4    5    6    7    8    9    10    11    12
 
   
 
   
                                7
+
                            nº fallos de página    7
  talla de fallos de página = ------  
+
  Tasa de fallos de página = --------------------- = ---- = 0,5833333333333333
                                12
+
                            nº accesos a páginas    12
  
 
Observación: al quitar un elemento se resetea su contador
 
Observación: al quitar un elemento se resetea su contador
 
  
 
= Sustitución por envejecimiento =
 
= Sustitución por envejecimiento =
Periodo de 4, registro R de 3 bits, desempate: FIFO (por orden de carga)
+
Periodo = 4
 
 
    _________________accesos a página__________________
 
    |_1_|_1_|_1_|_2_||_3_|_4_|_5_|_3_||_1_|_2_|_3_|_4_|
 
  ======================================================
 
  1 | 1 | = | = | = || 1 | = | 5 | 5 || 5 | = | = | 4 |
 
    |100| = | = | = ||010| = |100|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
 
----------------------------------
 
En este ejercicio hay un error cuando en la iteraccion 8 entra el 3, se ha puesto 5 100
 
 
 
  
    _________________accesos a página__________________
+
Registro R de 3 bits.
    |_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 || 3 | = | 3 | = |
 
s  |  |  |  |  ||100| = | = |110||011| = |111| = |
 
  ---|---|---|---|---||---|---|---|---||---|---|---|---|
 
  4 |  |  |  |  ||  | 4 | = | = || 4 | 2 | = | = |
 
    |  |  |  |  ||  |100| = | = ||010|100| = | = |
 
  --------------------------------------------------------> t
 
      x          x    x  x  x        x  x  x  x
 
  
Esta seria la solucion creo --[[Usuario:Luidela1|Luidela1]] 19:07 7 jun 2011 (UTC)
+
En caso de empate = FIFO por orden de carga
  
Yo creo que esta solución no es correcta, la correcta es la de arriba. En el segundo acceso al 3, se activaría el bit más significativo del registro R que ya está activado, luego no se activa. No entiendo porqué se activa el bit 2 del registro.
+
Acceso
--[[Usuario:Robertomartin|Robertomartin]] 19:17 7 jun 2011 (UTC)
+
  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 actual del 12:03 21 dic 2017

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  |  =  |  =  |  =  |  =  |  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

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