En un sistema operativo que utiliza la paginación para la administración de la memoria, se necesita un algoritmo de reemplazo de página para decidir qué página debe reemplazarse cuando ingresa una nueva página.
Error de página: un error de página ocurre cuando un programa en ejecución accede a una página de memoria que está asignada al espacio de direcciones virtuales pero que no está cargada en la memoria física. Dado que la memoria física real es mucho más pequeña que la memoria virtual, ocurren fallas de página. En caso de una falla de página, es posible que el sistema operativo deba reemplazar una de las páginas existentes con la página que se necesita recientemente. Diferentes algoritmos de reemplazo de página sugieren diferentes formas de decidir qué página reemplazar. El objetivo de todos los algoritmos es reducir el número de errores de página.
Algoritmos de reemplazo de página:
1. Primero en entrar, primero en salir (FIFO): este es el algoritmo de reemplazo de página más simple. En este algoritmo, el sistema operativo realiza un seguimiento de todas las páginas en la memoria en una cola, la página más antigua está al frente de la cola. Cuando es necesario reemplazar una página, se selecciona la página que está al frente de la cola para eliminarla.
Ejemplo 1: Considere la string de referencia de página 1, 3, 0, 3, 5, 6, 3 con 3 marcos de página. Encuentre el número de fallas de página.
Inicialmente, todos los espacios están vacíos, por lo que cuando aparecen 1, 3, 0, se asignan a los espacios vacíos -> 3 fallas de página.
cuando llega 3, ya está en la memoria, por lo que —> 0 Fallos de página. Luego viene 5, no está disponible en la memoria, por lo que reemplaza la ranura de página más antigua, es decir, 1. —> 1 Fallo de página. 6, tampoco está disponible en la memoria, por lo que reemplaza la ranura de página más antigua, es decir, 3 —> 1 Falla de página. Finalmente, cuando vienen 3 no está disponible por lo que reemplaza 0 1 fallo de página.
La anomalía de Belady demuestra que es posible tener más fallas de página al aumentar el número de marcos de página mientras se usa el algoritmo de reemplazo de página Primero en entrar, primero en salir (FIFO). Por ejemplo, si consideramos las strings de referencia 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4 y 3 ranuras, obtenemos 9 fallas de página en total, pero si aumentamos las ranuras a 4 , obtenemos fallas de 10 páginas.
2. Reemplazo óptimo de página: en este algoritmo, se reemplazan las páginas que no se utilizarán durante el mayor tiempo posible en el futuro.
Ejemplo-2: considere las referencias de página 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 con un marco de 4 páginas. Encuentra el número de error de página.
Inicialmente, todas las ranuras están vacías, por lo que cuando se asignan 7 0 1 2 a las ranuras vacías —> 4 fallas de página
, 0 ya está allí, entonces —> 0 falla de página. cuando llegue el 3, ocupará el lugar del 7 porque no se utilizará durante la mayor cantidad de tiempo en el futuro.—> 1 Error de página. 0 ya está allí, así que —> 0 Error de página. 4 tendrá lugar de 1 —> 1 Fallo de página.
Ahora, para la siguiente string de referencia de página —> 0 Error de página porque ya están disponibles en la memoria.
El reemplazo de página óptimo es perfecto, pero no es posible en la práctica ya que el sistema operativo no puede conocer las requests futuras. El uso del reemplazo de página óptimo es establecer un punto de referencia para que otros algoritmos de reemplazo puedan analizarse en comparación con él.
3. Usado menos recientemente: en este algoritmo, se reemplazará la página que se usó menos recientemente.
Ejemplo-3: considere la string de referencia de página 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 con 4 marcos de página. Encuentra el número de fallas de página.
Inicialmente, todas las ranuras están vacías, por lo que cuando se asignan 7 0 1 2 a las ranuras vacías —> 4 fallas de página
, 0 ya es su error de página, entonces —> 0 falla de página. cuando llegó 3, ocupará el lugar de 7 porque es el que se usó menos recientemente —> 1 Error de página
0 ya está en la memoria, así que —> 0 Error de página .
4 tendrá lugar de 1 —> 1 Fallo de página
Ahora para la siguiente string de referencia de página —> 0 Fallo de página porque ya están disponibles en la memoria.
4. Utilizado más recientemente (MRU): en este algoritmo, se reemplazará la página que se haya utilizado recientemente. La anomalía de Belady puede ocurrir en este algoritmo.
Preguntas de GATE CS Corner
Practicar las siguientes preguntas te ayudará a poner a prueba tus conocimientos. Todas las preguntas se han hecho en GATE en años anteriores o en pruebas simuladas de GATE. Es muy recomendable que los practiques.
- Gestión de memoria | Pregunta 1
- Gestión de memoria | Pregunta 10
- GATE CS 2014 (Conjunto-1), Pregunta 65
- GATE CS 2012, Pregunta 40
- GATE CS 2007, Pregunta 56
- GATE CS 2007, Pregunta 82
- GATE CS 2007, Pregunta 83
- GATE CS 2014 (Conjunto-3), Pregunta 65
- GATE CS 2002 Pregunta 23
- GATE CS 2001, Pregunta 21
- GATE CS 2010, Pregunta 24
Referencia: anomalía de Bélády
Este artículo ha sido mejorado por RajshreeSrivastava . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA