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

De Wiki de Sistemas Operativos
Saltar a: navegación, buscar
(Sustitución por envejecimiento: corrección y aclaración)
(NRU con 2º oportunidad)
Línea 93: Línea 93:
  
 
Por favor que alguien explique bien este criterio, que en cada ejercicio se aplica de una forma diferente.Gracias
 
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]]
  
 
= LRU =
 
= LRU =

Revisión del 17:38 7 jun 2011

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

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