Solución ejercicio 1 memoria virtual

De Wiki de Sistemas Operativos
Revisión del 23:50 7 jun 2011 de PCamino (discusión | contribuciones) (suposicion segunda oportunidad)
Saltar a: navegación, buscar

FIFO

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

                                              tiempo ->


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

NRU

En caso de empate, se emplea LRU.

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

                                              tiempo ->

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

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           |   X   |       |       |   X   |   X   |   X   |   X   |       |   X   |   X   |       |   X   |
página          -------------------------------------------------------------------------------------------------

                                              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


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   |
        |       |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
        |   R   |       |       |       |       |   1   |   =   |   0   |   1   |   0   |   =   |   1   |   0   |
        ---------------------------------------------------------------------------------------------------------
        |   4   |       |       |       |       |       |   4   |   4   |   =   |   =   |   2   |   =   |   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


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