Solución ejercicio 1 memoria virtual

De Wiki de Sistemas Operativos
Saltar a: navegación, buscar

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,6923076923076923
                             nº accesos a páginas    13

NRU

En caso de empate, se emplea LRU.

Acceso
  a        1(R)  1(R)  1(W)  2(R)  3(R)  4(R)  5(R)  3(W)  1(W)  2(W)  3(R)  4(R)
página
         +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
         |  1  |  =  |  =  |  =  |  =  |  =  |  =  |  =  |  =  |  =  |  =  |  =  |
Marco 1  | R=1 |  =  |  =  |  =  |  =  |  =  |  =  |  =  |  =  |  =  |  =  |  =  |
         | M=0 |  =  | M=1 |  =  |  =  |  =  |  =  |  =  |  =  |  =  |  =  |  =  |
         +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
         |     |     |     |  2  |  =  |  =  |  5  |  =  |  =  |  =  |  =  |  4  |
Marco 2  |     |     |     | R=1 |  =  |  =  | R=1 |  =  |  =  |  =  |  =  | R=1 |
         |     |     |     | M=0 |  =  |  =  | M=0 |  =  |  =  |  =  |  =  | M=0 |
         +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
         |     |     |     |     |  3  |  =  |  =  |  =  |  =  |  =  |  =  |  =  |
Marco 3  |     |     |     |     | R=1 |  =  |  =  |  =  |  =  |  =  |  =  |  =  |
         |     |     |     |     | M=0 |  =  |  =  | M=1 |  =  |  =  |  =  |  =  |
         +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
         |     |     |     |     |     |  4  |  =  |  =  |  =  |  2  |  =  |  =  |
Marco 4  |     |     |     |     |     | R=1 |  =  |  =  |  =  | R=0 |  =  |  =  |
         |     |     |     |     |     | M=0 |  =  |  =  |  =  | M=1 |  =  |  =  |
         +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Fallo    |     |     |     |     |     |     |     |     |     |     |     |     |
 de      |  x  |     |     |  x  |  x  |  x  |  x  |     |     |  x  |     |  x  |
página   |     |     |     |     |     |     |     |     |     |     |     |     |
         +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+

Tiempo      1     2     3     4     5     6     7     8     9    10    11    12
                             nº fallos de página     7
 Tasa de fallos de página = --------------------- = ---- = 0,5384615384615385
                             nº accesos a páginas    13

--juacascor DUDA: 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. --lorperler Respuesta: No, es un empate. Por lo que aplicamos el criterio LRU entre 4 y 5, y 4 es la que lleva más tiempo sin usarse.

NRU con 2º oportunidad

                                             accesos a páginas

                |   r   |   r   |   w   |   r   |   r   |   r   |   r   |   w   |   w   |   w   |   r   |   r   |
                -------------------------------------------------------------------------------------------------
                |   1   |   1   |   1   |   2   |   3   |   4   |   5   |   3   |   1   |   2   |   3   |   4   |
        ---------------------------------------------------------------------------------------------------------
        |   1   |   1   |   =   |   =   |   =   |   =   |   =   |   5   |   =   |   =   |   =   |   =   |   4   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   R   |   1   |   =   |   =   |   =   |   =   |   =   |   1   |   =   |   =   |   =   |   =   |   1   |
        ---------------------------------------------------------------------------------------------------------
marcos  |   2   |       |       |       |   2   |   =   |   =   |   2   |   =   |   1   |   =   |   =   |   1   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   R   |       |       |       |   1   |   =   |   =   |   0   |   =   |   1   |   =   |   =   |   0   |
        ---------------------------------------------------------------------------------------------------------
        |   3   |       |       |       |       |   3   |   =   |   3   |   3   |   =   |   3   |   3   |   3   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   R   |       |       |       |       |   1   |   =   |   0   |   1   |   =   |   0   |   1   |   0   |
        ---------------------------------------------------------------------------------------------------------
        |   4   |       |       |       |       |       |   4   |   4   |   =   |   =   |   2   |   =   |   2   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   R   |       |       |       |       |       |   1   |   0   |   =   |   =   |   1   |   =   |   0   |
        ---------------------------------------------------------------------------------------------------------
fallo           |   X   |       |       |   X   |   X   |   X   |   X   |       |   X   |   X   |       |   X   |
página          -------------------------------------------------------------------------------------------------
contenido       |   1   |   1   |   1   |  1-2  | 1-2-3 |1-2-3-4|2-3-4-5|2-3-4-5|3-4-5-1|5-1-3-2|5-1-3-2|1-3-2-4|
de la cola      -------------------------------------------------------------------------------------------------
                                              tiempo ->

                                8
talla de fallos de página =  ------ 
                               12
Creo que es asi, pero no me lo tomeis a pies juntillas que no estoy muy seguro.


Por favor que alguien explique bien este criterio, que en cada ejercicio se aplica de una forma diferente.Gracias

Explicación:

El criterio se basa en combinar el NRU (sin bit M) con FIFO. En la cola se van añadiendo las páginas según se cargan con su respectivo valor del bit R. A la hora de sustituir se mira el candidato de la cabecera de la cola. Si su R=1, se le da una segunda oportunidad desplazándolo al final de la cola y poniendo su bit R=0. Si hubiera tenido el R=0, se hubiera tomada esa página como víctima. Eso es lo que sucede cuando llega la página 5. En ese momento la cola es 1 2 3 4 con su bit R=1 en todas las páginas. Se va mirando el candidato si tiene el bit R=0 como no es así, pasa al final de la cola. Llega un momento en el que la página 1 vuelve a la cabecera(en este caso con R=0),por lo que ahora si es sustituida por la página 5.Jherrera

Una Dudilla : la FIFO es por orden de carga o por orden de acceso?¿ Según veo en el ejercicio lo hace por orden de acceso --DvS 013 -- Respuesta : La fifo almacena el tiempo que una página lleva cargada en memoria, por lo que es por orden de carga. JCGarrido


He puesto el orden de la cola para que se vea más claro. Cuando el candidato tiene R=1 se pone a 0 y se inserta al final. Es por eso que cuando se accede por última vez a la página 2, al estar 3 la primera, se pone su bit R a 0 se inserta al final (no estaba en la solución anterior) y la siguiente (4, con R=0) es la página víctima.--Alexrdp 09:37 14 jun 2011 (UTC)

Entonces, sería asi:

                                             accesos a páginas

                |   r   |   r   |   w   |   r   |   r   |   r   |   r   |   w   |   w   |   w   |   r   |   r   |
                -------------------------------------------------------------------------------------------------
                |   1   |   1   |   1   |   2   |   3   |   4   |   5   |   3   |   1   |   2   |   3   |   4   |
        ---------------------------------------------------------------------------------------------------------
        |   1   |   1   |   =   |   =   |   =   |   =   |   =   |   5   |   =   |   5   |   =   |   =   |   4   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   R   |   1   |   =   |   =   |   =   |   =   |   =   |   1   |   =   |   0   |   =   |   =   |   1   |
        ---------------------------------------------------------------------------------------------------------
marcos  |   2   |       |       |       |   2   |   =   |   =   |   2   |   =   |   1   |   1   |   =   |   1   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   R   |       |       |       |   1   |   =   |   =   |   0   |   =   |   1   |   0   |   =   |   0   |
        ---------------------------------------------------------------------------------------------------------
        |   3   |       |       |       |       |   3   |   =   |   3   |   3   |   3   |   2   |   2   |   2   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   R   |       |       |       |       |   1   |   =   |   0   |   1   |   0   |   1   |   0   |   0   |
        ---------------------------------------------------------------------------------------------------------
        |   4   |       |       |       |       |       |   4   |   4   |   =   |   =   |   =   |   3   |   3   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   R   |       |       |       |       |       |   1   |   0   |   =   |   =   |   =   |   1   |   0   |
        ---------------------------------------------------------------------------------------------------------
fallo           |   X   |       |       |   X   |   X   |   X   |    X  |       |   X   |   X   |   X   |   X   |
página          -------------------------------------------------------------------------------------------------

                                              tiempo ->

                                9
talla de fallos de página =  ------ 
                               12


Esta segunda solución creo que no está del todo correcta. Cuando llega el cuarto acceso a 1 (donde se produce el sexto fallo de página), el contenido de la cola es el siguiente:

2 (R=0) - 3 (R=1) - 4 (R=0) - 5 (R=1)

Con lo cual, la víctima es el 2, pero sin poner a 0 el resto de los bits R, ya que el primer elemento de la cola tiene el bit R=0 y no hace falta seguir iterando sobre ésta.

De acuerdo a este último comentario, quedaría de la siguiente manera:

                                             accesos a páginas

                |   r   |   r   |   w   |   r   |   r   |   r   |   r   |   w   |   w   |   w   |   r   |   r   |
                -------------------------------------------------------------------------------------------------
                |   1   |   1   |   1   |   2   |   3   |   4   |   5   |   3   |   1   |   2   |   3   |   4   |
        ---------------------------------------------------------------------------------------------------------
        |   1   |   1   |   =   |   =   |   =   |   =   |   =   |   5   |   =   |   =   |   =   |   =   |   5   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   R   |   1   |   =   |   =   |   =   |   =   |   =   |   1   |   =   |   =   |   =   |   =   |   0   |
        ---------------------------------------------------------------------------------------------------------
marcos  |   2   |       |       |       |   2   |   =   |   =   |   2   |   =   |   1   |   =   |   =   |   1   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   R   |       |       |       |   1   |   =   |   =   |   0   |   =   |   1   |   =   |   =   |   0   |
        ---------------------------------------------------------------------------------------------------------
        |   3   |       |       |       |       |   3   |   =   |   3   |   3   |   =   |   3   |   3   |   4   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   R   |       |       |       |       |   1   |   =   |   0   |   1   |   =   |   0   |   1   |   1   |
        ---------------------------------------------------------------------------------------------------------
        |   4   |       |       |       |       |       |   4   |   4   |   =   |   =   |   2   |   =   |   2   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   R   |       |       |       |       |       |   1   |   0   |   =   |   =   |   1   |   =   |   0   |
        ---------------------------------------------------------------------------------------------------------
fallo           |   X   |       |       |   X   |   X   |   X   |    X  |       |   X   |   X   |       |   X   |
página          -------------------------------------------------------------------------------------------------

talla de fallos de página = 8 / 12
Existia un fallo en el acceso número 10, donde no se ponía el bit R del marco 3 a 0 y en el último acceso, que se puso la página 4 en el  
marco 1, pero no es así, cuando llegamos a este acceso la cola es |3|5|1|2|, por tanto el que será reemplazado será el 3, porque será el  
primero en encontrarnos con el bit R a 0.
Corregido por --Cripolgon

LRU

                                      accesos a páginas
                -------------------------------------------------------------------------
                |  1  |  1  |  1  |  2  |  3  |  4  |  5  |  3  |  1  |  2  |  3  |  4  |
        ---------------------------------------------------------------------------------
        |   1   |  1  |  =  |  =  |  =  |  =  |  =  |  5  |  =  |  =  |  =  |  =  |  4  |
        ---------------------------------------------------------------------------------
marcos  |   2   |     |     |     |  2  |  =  |  =  |  =  |  =  |  1  |  =  |  =  |  =  |
        --------------------------------------------------------------------------------
        |   3   |     |     |     |     |  3  |  =  |  =  |  =  |  =  |  =  |  =  |  =  |
        ---------------------------------------------------------------------------------
        |   4   |     |     |     |     |     |  4  |  =  |  =  |  =  |  2  |  =  |  =  |
        ---------------------------------------------------------------------------------
fallo           |  X  |     |     |  X  |  X  |  X  |  X  |     |  X  |  X  |     |  X  |
página          -------------------------------------------------------------------------

                                              tiempo ->


                               8
talla de fallos de página =  ------ 
                               12


LFU

                                                  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   |   1   |   1   |   =   |   =   |   =   |   =   |   =   |   1   |   =   |   =   |   1   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   C   |   1   |   2   |   3   |   =   |   =   |   =   |   =   |   =   |   4   |   =   |   =   |   4   |
        ---------------------------------------------------------------------------------------------------------
marcos  |   2   |       |       |       |   2   |   =   |   =   |   5   |   =   |   =   |   =   |   =   |   4   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   C   |       |       |       |   1   |   =   |   =   |   1   |   =   |   =   |   =   |   =   |   1   |
        ---------------------------------------------------------------------------------------------------------
        |   3   |       |       |       |       |   3   |   =   |   =   |   3   |   =   |   =   |   3   |   3   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   C   |       |       |       |       |   1   |   =   |   =   |   2   |   =   |   =   |   3   |   3   |
        ---------------------------------------------------------------------------------------------------------
        |   4   |       |       |       |       |       |   4   |   =   |   =   |   =   |   2   |   =   |   2   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   C   |       |       |       |       |       |   1   |   =   |   =   |   =   |   1   |   =   |   1   |
        ---------------------------------------------------------------------------------------------------------
fallo           |   X   |       |       |   X   |   X   |   X   |   X   |       |       |   X   |       |   X   |
página          -------------------------------------------------------------------------------------------------

                                              tiempo ->

                                7
talla de fallos de página =  ------ 
                               12

Observación: al quitar un elemento se resetea su contador


Sustitución por envejecimiento

Periodo de 4, registro R de 3 bits, desempate: FIFO (por orden de carga)
    _________________accesos a página__________________
    |_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 | 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