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 |  4  |
+
  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  |     |     | x  | x  | x  | x  |     |     | x  |     | x  |
−
        ---------------------------------------------------------------------------------------------------------
+
  página   |    |    |    |    |    |    |    |    |    |    |    |    |
−
  fallo          |  X  |       |       |   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  |   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 |  4  |
+
  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  |  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  |     |     | x  | x  | x  | x  |     |     | x  |     | x  |
−
        |  4   |       |       |       |       |       |   4   |   =   |   =   |   =   |   2   |   =   |   2  |
+
  página   |    |    |    |    |    |    |    |    |    |    |    |    |
−
        |      |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
+
          +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 
−
        |   C   |      |      |      |      |      |  1   |   =   |   =   |   =   |   1   |   =   |   1  |
 
−
        ---------------------------------------------------------------------------------------------------------
 
−
  fallo          |  X  |       |       |   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 13: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
Obtenido de «https://1984.lsi.us.es/wiki-ssoo/index.php?title=Solución_ejercicio_1_memoria_virtual&oldid=3850»