Revisión del 15:35 20 dic 2016

Contenido

1 FIFO
2 NRU
3 NRU con 2º oportunidad
4 LRU
5 LFU
6 Sustitución por envejecimiento

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

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

Revisión del 15:35 20 dic 2016

Contenido

FIFO

NRU

NRU con 2º oportunidad

LRU

LFU

Sustitución por envejecimiento

Menú de navegación

Vistas

Herramientas personales

Navegación

Buscar

Herramientas

@@ Línea 81: / Línea 81: @@
           |   R   |       |       |       |   1   |   =   |   =   |   0   |   =   |   1   |   =   |   =   |   0   |
           ---------------------------------------------------------------------------------------------------------
-          |   3   |       |       |       |       |   3   |   =   |   3   |   3   |   =   |   3   |   3   |   3   |
+          |   3   |       |       |       |       |   3   |   =   |   3   |   3   |   =   |   =   |   3   |   3   |
           |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
-          |   R   |       |       |       |       |   1   |   =   |   0   |   1   |   =   |   0   |   1   |   0   |
+          |   R   |       |       |       |       |   1   |   =   |   0   |   1   |   =   |   =   |  1(=) |   0   |
           ---------------------------------------------------------------------------------------------------------
           |   4   |       |       |       |       |       |   4   |   4   |   =   |   =   |   2   |   =   |   2   |
@@ Línea 89: / Línea 89: @@
           |   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          -------------------------------------------------------------------------------------------------
   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|
@@ Línea 98: / Línea 98: @@
                                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.[[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]]
---
-Respuesta : La fifo almacena el tiempo que una página lleva cargada en memoria, por lo que es por orden de carga. [[Usuario : JCGarrido|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.--[[Usuario:Alexrdp|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 ->
- talla de fallos de página =  ------
-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:
-(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 --[[Usuario:Cripolgon|Cripolgon]]
 = LRU =