Preguntas y respuestas sobre la asignación de memoria del sistema operativo # 3

Question:¿Cuándo ocurre un error de página? Explicar varias estrategias / algoritmos de reemplazo de páginas.

Answer:En la técnica de gestión de memoria de paginación a demanda, si una página solicitada para ejecución no está presente en la memoria principal, se produce un error de página. Para cargar la página en demanda en la memoria principal, se busca un marco de página libre en la memoria principal y se asigna. Si ningún marco de página está libre, el administrador de memoria tiene que liberar un marco intercambiando su contenido al almacenamiento secundario y así dejar espacio para la página requerida. Para intercambiar páginas se utilizan muchos esquemas o estrategias.

Varias estrategias / algoritmos de reemplazo de página

  1. The Optimal Page Replacement Algorithm- Este algoritmo reemplaza la página que no se utilizará durante un período de tiempo más largo. En el momento en que ocurre el error de página, algún conjunto de páginas está en la memoria. Se hará referencia a una de estas páginas en la siguiente instrucción. Es posible que no se haga referencia a otras páginas hasta 10,100 o quizás 1000 instrucciones. Esta información se puede almacenar con cada página en la PMT (Tabla de mapa de páginas).

    PAGS# base Compensar MISC
    1     10
    2     NULO
    3     1000
    ...
    10     100

    El algoritmo de página óptimo simplemente elimina la página con el mayor número de instrucciones de este tipo, lo que implica que será necesaria en el futuro más lejano. este algoritmo se introdujo hace mucho tiempo y es difícil de implementar porque requiere un conocimiento futuro del comportamiento del programa. Sin embargo, es posible implementar un reemplazo de página óptimo en la segunda ejecución utilizando la información de referencia de la página recopilada en la primera ejecución.

  2. NRU(Not Recently Used) Page Replacement Algorithm- Este algoritmo requiere que cada página tenga dos bits de estado adicionales 'R' y 'M' llamados bit de referencia y bit de cambio respectivamente. El bit de referencia (R) se establece automáticamente en 1 siempre que se hace referencia a la página. El bit de cambio (M) se establece en 1 siempre que se modifica la página. Estos bits se almacenan en el PMT y se actualizan en cada referencia de memoria. Cuando ocurre una falla de página, el administrador de memoria inspecciona todas las páginas y las divide en 4 clases basadas en bits R y M.

    • Class 1: (0,0) - ni usado ni modificado recientemente - la mejor página para reemplazar.

    • Class 2: (0,1) - no utilizado recientemente pero modificado - la página deberá estar escrita antes de ser reemplazada.

    • Class 3: (1,0) - usado recientemente pero limpio - probablemente se volverá a usar pronto.

    • Class 4: (1,1) - usado y modificado recientemente - probablemente se usará nuevamente, y será necesario escribirlo antes de reemplazarlo.

    Este algoritmo elimina una página al azar de la clase no vacía con el número más bajo.

    Ventajas:

    • Es fácil de entender.

    • Es eficiente de implementar.

  3. FIFO (First in First out) Page Replacement Algorithm- Es uno de los algoritmos de reemplazo de página más simples. Se elige y se reemplaza la página más antigua, que ha pasado más tiempo en la memoria. Este algoritmo se implementa con la ayuda de la cola FIFO para mantener las páginas en la memoria. Se inserta una página al final de la cola y se reemplaza al principio de la cola.

    En la fig., La cadena de referencia es 5, 4, 3, 2, 5, 4, 6, 5, 4, 3, 2, 6 y hay 3 cuadros vacíos. Las primeras 3 referencias (5, 4, 3) provocan errores de página y se colocan en marcos vacíos. La siguiente referencia (2) reemplaza la página 5 porque la página 5 se cargó primero y así sucesivamente. Después de 7 fallas de página, la siguiente referencia es 5 y 5 ya está en la memoria, por lo que no hay fallas de página para esta referencia. De manera similar para la siguiente referencia 4. Las marcas + muestran la entrada de una página, mientras que el círculo muestra la página elegida para su eliminación.

    Ventajas

    • FIFO es fácil de entender.

    • Es muy fácil de implementar.

    Desventaja

    • No siempre es bueno en el desempeño. Puede reemplazar una página activa para traer una nueva y, por lo tanto, puede causar una falla de página de esa página inmediatamente.

    • Otro efecto secundario inesperado es la anomalía FIFO o la anomalía de Belady. Esta anomalía dice que la tasa de errores de página puede aumentar a medida que aumenta el número de marcos de página asignados.

    Por ejemplo, la siguiente figura presenta el mismo seguimiento de página pero con una memoria más grande. Aquí el número de marcos de página es 4.

    Aquí los errores de página son 10 en lugar de 9.

  4. LRU(Least Recently Used) Algorithm- El algoritmo de uso menos reciente (LRU) reemplaza la página que no se ha utilizado durante un período de tiempo más largo. Se basa en la observación de que las páginas que no se han utilizado durante mucho tiempo probablemente permanecerán sin utilizar durante más tiempo y deberán ser reemplazadas.

    Inicialmente, 3 marcos de página están vacíos. Las primeras 3 referencias (7, 0, 1) provocan errores de página y se introducen en estos marcos vacíos. La siguiente referencia (2) reemplaza la página 7. Dado que la siguiente referencia de página (0) ya está en la memoria, no hay ningún error de página. Ahora, para la siguiente referencia (3), el reemplazo de LRU ve que, de los tres cuadros en la memoria, la página 1 se usó menos recientemente y, por lo tanto, se reemplazó. Y así continúa el proceso.

    Ventajas

    • El algoritmo de reemplazo de página LRU es silencioso y eficiente.

    • No sufre de la anomalía de Belady.

    Desventajas

    • Su implementación no es muy sencilla.

    • Su implementación puede requerir una asistencia sustancial de hardware.