SOP U-4 Algoritmos de Reemplazo de Páginas Flashcards
ALGORITMO DE REEMPLAZO DE PÁGINAS DE SEGUNDA OPORTUNIDAD
Este es una mejora del FIFO. Antes de quitar la página me fijo el valor de R, si el mismo es igual
a 1 no la quito, la pongo al final de la fila y reinicio R a 0. Si es 0 si la quito. Una página de
mucho uso permanecerá siempre en la memoria RAM
Imagina una cola en un supermercado con una regla especial:
Personas en la cola: Representan las páginas en memoria.
Llegar a la cola: Es como cargar una nueva página en la memoria.
Salir de la cola: Es como sacar una página de la memoria.
La regla especial:
Cada persona en la cola tiene un pequeño cartel. Si el cartel está levantado (R=1), significa que esa persona acaba de comprar algo y necesita un poco más de tiempo para guardar sus cosas. Si el cartel está bajado (R=0), significa que ya terminó de comprar.
¿Cómo funciona la cola con esta regla?
Cuando llega el turno de alguien, el cajero revisa el cartel. Si el cartel está levantado, la persona vuelve al final de la cola y se baja el cartel. Si el cartel está bajado, la persona sale de la cola.
¿Por qué esta regla es útil?
Esta regla evita que las personas que acaban de comprar algo sean las primeras en salir de la cola. De esta manera, se asegura de que las personas que necesitan más tiempo tengan una segunda oportunidad de comprar.
En el contexto de las computadoras:
El cartel: Es como un bit (R) que indica si una página ha sido usada recientemente.
Vuelta al final de la cola: La página se mueve al final de la lista de páginas en memoria.
¿Por qué es mejor que FIFO?
El algoritmo de segunda oportunidad evita que las páginas que se usan con frecuencia sean sacadas de la memoria, lo que mejora el rendimiento del sistema.
ALGORITMO DE REEMPLAZO DE PÁGINAS DEL RELOJ
ALGORITMO DE REEMPLAZO DE PÁGINAS DEL RELOJ
→ Mantiene todas las páginas en una lista circular parecida a un reloj, y un puntero a la página
más antigua.
→ Cuando se presenta un fallo de página, se examina la página a la que apunta el puntero.
→ Si su bit R es 0, dicha se desaloja, la nueva se inserta en su lugar y el puntero se adelanta.
→ Si R es 1, se cambia a 0 y se desplazan los punteros.
→ Es utilizada en Linux
Imagina un reloj con números y cada número representa una página en la memoria:
El reloj: Es una lista circular de páginas.
Las manecillas del reloj: Son como un puntero que señala la página que se va a evaluar.
Los números: Representan las páginas en memoria.
Un pequeño interruptor en cada número: Es el bit R. Si está encendido (1), significa que la página ha sido usada recientemente. Si está apagado (0), significa que no ha sido usada.
¿Cómo funciona este reloj?
Fallo de página: Cuando necesitamos una página que no está en la memoria, el reloj empieza a girar.
Revisar la página señalada: El puntero señala una página. Si el interruptor de esa página está apagado (0), significa que no se ha usado recientemente, así que podemos sacarla y poner la nueva página en su lugar.
Si el interruptor está encendido: Si el interruptor está encendido (1), significa que la página se ha usado recientemente, así que la dejamos por ahora. Pero para la próxima vez, apagamos el interruptor y seguimos girando el reloj.
ALGORITMO DE REEMPLAZO DE PÁGINAS FIFO
El SO mantiene una lista con las páginas en memoria más antiguas al principio de la lista y la
más nueva al final. Al presentarse un fallo de página, se desaloja la página que está al principio
de la lista y la nueva se anexa al final.
Desventaja: puede que se quiten páginas que se acceden frecuentemente
Imagina una cola en un banco:
Personas en la cola: Representan las páginas en memoria.
Llegar a la cola: Es como cargar una nueva página en la memoria.
Salir de la cola: Es como sacar una página de la memoria.
¿Cómo funciona la cola del banco?
La primera persona en hacer fila es la primera en ser atendida. Si llega alguien nuevo, se pone al final de la cola.
¿Cómo funciona el algoritmo FIFO?
El algoritmo FIFO funciona exactamente igual. La primera página que llega a la memoria se coloca al principio de una lista. Cuando se necesita espacio, se saca la página que está al principio de la lista (la más antigua).
¿Cuál es el problema con este método?
Imagina que hay una persona que entra y sale del banco constantemente. Con el sistema FIFO, esta persona siempre estará al final de la cola y podría pasar mucho tiempo esperando. Lo mismo pasa con las páginas: una página que se usa con frecuencia podría ser sacada de la memoria aunque sea muy necesaria.
ALGORITMO DE REEMPLAZO DE PÁGINAS NO USADAS RECIENTEMENTE
El SO examina todas las páginas y las divide en cuatro categorías con base a los valores
actuales de sus bits R (página con referencia reciente o no) y M (modificada o no):
✓ Clase 0: No solicitada, No modificada.
✓ Clase 1: No solicitada, Modificada
✓ Clase 2: Solicitada, No modificada
✓ Clase 3: Solicitada, Modificada.
Este algoritmo, reemplaza primero las de clase 0. Si no hay continúa a la clase siguiente y así
sucesivamente.
Imagina una biblioteca que quieres mantener ordenada y con espacio suficiente para nuevos libros:
Libros: Representan los programas que estás ejecutando.
Estantes: Son como las ubicaciones de memoria en tu computadora (marcos físicos).
¿Cómo decides qué libro sacar cuando la biblioteca está llena?
El algoritmo NRU te ayuda a tomar esta decisión de una manera inteligente. Imagina que cada libro tiene dos etiquetas: una que dice si lo has leído recientemente (bit R) y otra que dice si has hecho anotaciones en él (bit M).
Las cuatro categorías de libros:
Libros no leídos y sin anotaciones (Clase 0): Son los libros que hace mucho que no tocas y no has modificado. Son los candidatos ideales para sacar.
Libros no leídos pero con anotaciones (Clase 1): Estos libros los has modificado, así que antes de sacarlos tendrías que guardar los cambios.
Libros leídos recientemente pero sin anotaciones (Clase 2): Los has leído hace poco, así que es probable que los vuelvas a necesitar.
Libros leídos recientemente y con anotaciones (Clase 3): Estos son los libros más importantes, ya que los has usado recientemente y has hecho cambios. Son los últimos en ser considerados para ser sacados.
¿Cómo funciona el algoritmo NRU?
El algoritmo NRU empieza buscando un libro en la categoría 0. Si encuentra uno, lo saca. Si no hay libros en la categoría 0, pasa a la categoría 1 y así sucesivamente hasta encontrar un libro que pueda sacar.
ALGORITMO DE REEMPLAZO DE PÁGINAS ÓPTIMO
Cada página se rotula con el número de instrucciones que se ejecutarán antes de que se haga
la primera referencia a esa página. Este algoritmo dice que debe eliminarse la página con el
rótulo más grande. No es factible, debido a que, en un fallo de página, el SO no sabe cuándo
se volverá a hacer referencia a una página determinada.
Imagina una biblioteca muy pequeña con pocos estantes y muchos libros:
Libros: Estos representan los programas que quieres ejecutar.
Estantes: Son como las ubicaciones de memoria en tu computadora (marcos físicos).
¿Qué pasa cuando la biblioteca está llena y necesitas un nuevo libro?
Tendrás que sacar uno de los libros que ya está ahí para hacer espacio. Pero, ¿cuál libro sacas? Aquí es donde entra en juego el algoritmo óptimo.
El algoritmo óptimo:
Imagina que cada libro tiene una etiqueta que dice “Este libro no se va a usar durante X minutos”. El algoritmo óptimo dice que debes sacar el libro con la etiqueta más grande, es decir, el libro que no se va a usar durante más tiempo.
¿Por qué es óptimo?
Porque al sacar el libro que menos vas a necesitar a corto plazo, estás maximizando el tiempo que podrás usar los otros libros sin tener que volver a buscarlos.
¿Por qué no se usa en la práctica?
Porque para saber cuánto tiempo va a pasar antes de usar un libro, necesitarías un futuro perfecto. Es decir, tendrías que saber exactamente qué vas a hacer en los próximos minutos, segundos o incluso nanosegundos. Esto es imposible de predecir.
Algoritmos de Reemplazo de Páginas
Cuando se produce un fallo de página, si la memoria está llena, se debe desalojar una página de
RAM, para hacer espacio para la nueva página
Se debe analizar que página conviene extraer de la memoria y el bit M de la página a desalojar:
Si M=1 → guardar los cambios en disco
Si M=0 → se libera la zona de memoria
Imagina una biblioteca muy grande con un número limitado de estantes:
Libros: Estos representan los programas que quieres ejecutar.
Estantes: Son como las ubicaciones de memoria en tu computadora (marcos físicos).
Etiquetas en los libros: Estas etiquetas son las direcciones virtuales.
¿Qué pasa cuando la biblioteca está llena?
Si quieres sacar un nuevo libro de la biblioteca pero todos los estantes están ocupados, tendrás que sacar un libro que ya esté ahí para liberar espacio.
¿Cómo decides qué libro sacar?
Aquí es donde entran en juego los algoritmos de reemplazo de páginas. Son como diferentes estrategias para decidir qué libro sacar de la biblioteca cuando está llena.
El bit M:
Imagina que cada libro tiene una pequeña pegatina. Si la pegatina es azul (M=1), significa que has hecho anotaciones en el libro y necesitas guardar esos cambios. Si la pegatina es roja (M=0), significa que no has hecho cambios y puedes sacar el libro sin problemas.
Algoritmos de reemplazo:
Existen diferentes algoritmos, cada uno con sus propias reglas para elegir qué libro sacar:
FIFO (Primero en entrar, primero en salir): Sacas el libro que llegó primero a la biblioteca. Es como hacer una cola: el primero en llegar es el primero en salir.
LRU (Menos recientemente usado): Sacas el libro que menos has usado recientemente. Es como limpiar tu escritorio: guardas los papeles que usas más a menudo y tiras los que no has tocado en mucho tiempo.
Óptimo: Este es un algoritmo ideal pero imposible de implementar en la práctica. Consiste en sacar el libro que no se va a usar durante el mayor tiempo posible.
Almacenamiento de respaldo
Se reserva un espacio en disco para el intercambio de páginas. Es el área de intercambio o
Swap
Imagina una biblioteca muy grande y con poco espacio en las estanterías:
Biblioteca: Es la memoria RAM de la computadora.
Libros: Son las páginas de memoria.
Estanterías: Son los marcos de página.
Almacén: Es el espacio de intercambio (swap).
¿Qué pasa cuando la biblioteca está llena y llega un nuevo lector con un libro muy grande?
El bibliotecario necesita hacer espacio para el nuevo libro. Para ello, puede:
Pedir a otro lector que devuelva un libro: Esto sería como eliminar una página de la memoria RAM.
Guardar un libro en el almacén: El bibliotecario puede guardar un libro que no se esté usando actualmente en el almacén. Esto es lo que ocurre con el espacio de intercambio.
Aspectos de Implantación
Demonios de paginación: proceso que garantiza la existencia de marcos de página libres.
Duerme, se despierta, ejecuta un algoritmo de reemplazo de páginas y se duerme
nuevamente. Detecta si la página se modificó y establece M = 1.
Imagina una biblioteca con un bibliotecario muy organizado:
Biblioteca: Es la memoria de la computadora.
Libros: Son las páginas de memoria.
Estanterías: Son los marcos de página.
Bibliotecario: Es el demonio de paginación.
El bibliotecario (demonio de paginación) trabaja así:
Descansa: El bibliotecario pasa la mayor parte del tiempo leyendo un libro o tomando un café (duerme).
Se despierta: Cuando alguien necesita un libro que no está en la biblioteca (fallo de página), el bibliotecario se despierta.
Organiza los libros: El bibliotecario revisa todas las estanterías para encontrar un espacio libre para el nuevo libro. Si no hay espacio, tiene que sacar un libro de una estantería y poner el nuevo en su lugar (algoritmo de reemplazo de páginas).
Marca los libros: Si un libro ha sido modificado (escrito en él), el bibliotecario pone una pequeña marca (M=1) para saber que el libro debe guardarse en la estantería y no puede ser eliminado fácilmente.
Vuelve a descansar: Una vez que ha encontrado un lugar para el nuevo libro, el bibliotecario vuelve a su libro o café (se duerme).
Bloqueo de páginas en memoria
No eliminar páginas que están realizando operaciones de entrada-salida
Imagina una biblioteca muy ocupada con muchos usuarios:
Biblioteca: Es la memoria de la computadora.
Libros: Son las páginas de memoria.
Usuarios: Son los procesos.
Bibliotecario: Es el sistema operativo.
¿Qué pasa cuando un usuario está copiando información de un libro a otro (operación de entrada-salida)?
Si el bibliotecario quisiera guardar el libro que el usuario está utilizando en un almacén (disco duro), interrumpiría al usuario en medio de su tarea, lo cual sería muy molesto y podría causar pérdidas de información.
Para evitar esto, el bibliotecario decide “bloquear” el libro mientras el usuario lo está utilizando:
Bloquear el libro: Significa que el bibliotecario no puede mover el libro de su estante mientras el usuario lo está utilizando.
Manejo de fallos de página
▪ El hardware hace un trap al kernel, se guarda el contador de programa en la pila
▪ El S.O. detecta un fallo de página se comprueban los bits de protección
▪ Se verifica si existen marcos disponibles, de lo contrario se ejecuta el algoritmo de reemplazo
de páginas. Si la página extraer posee el bit M en 1, se graba en disco
▪ Se realiza una conmutación de contexto, suspendiendo el proceso que produjo el fallo de
página. Se busca la página solicitada en el disco (mientras, se puede ejecutar otro proceso)
▪ Cuando la página está en memoria RAM → se actualiza la tabla de páginas
▪ Se continúa con la ejecución del proceso que originó el fallo → se recuperan los registros y el
valor del contador de programa
Imagina una biblioteca muy grande con un bibliotecario muy eficiente:
Biblioteca: Es la memoria de la computadora.
Libros: Son las páginas de memoria.
Estanterías: Son los marcos de página.
Lectores: Son los procesos.
Bibliotecario: Es el sistema operativo.
¿Qué pasa cuando un lector necesita un libro que no está en la estantería (fallo de página)?
El lector pide ayuda: El lector le dice al bibliotecario que necesita un libro específico (trap al kernel).
El bibliotecario busca el libro: El bibliotecario busca el libro en las estanterías (comprueba los bits de protección).
Si no encuentra el libro: Si el libro no está en la biblioteca, el bibliotecario tiene que hacer espacio. Busca una estantería vacía o decide qué libro sacar de una estantería ocupada (algoritmo de reemplazo de páginas). Si el libro que va a sacar tiene anotaciones importantes (bit M en 1), lo guarda en un almacén (disco).
El bibliotecario va al almacén: Mientras tanto, el bibliotecario puede ayudar a otros lectores (conmutación de contexto). Va al almacén a buscar el libro solicitado (disco).
El libro llega a la biblioteca: Cuando el bibliotecario trae el libro, lo coloca en una estantería vacía (actualiza la tabla de páginas).
El lector continúa leyendo: El bibliotecario le devuelve el libro al lector y este puede continuar leyendo desde donde lo dejó (se recuperan los registros y el contador de programa).
Modelo de conjunto de trabajo
Reducir los fallos de página
Llevar el registro del conjunto de trabajo de los procesos y garantizar que sus páginas estén en
memoria RAM antes de comenzar su ejecución (prepaginación)
El conjunto de trabajo de un proceso cambia durante su ejecución (puede aumentar o disminuir su
tamaño)
Para poder implementarlo el sistema operativo debe llevar el registro de las páginas que forman el
conjunto de trabajo de cada proceso
✓ Paginación con demanda → las páginas se cargan a memoria RAM sólo cuando se necesitan.
✓ Prepaginación → cargar las páginas de un proceso en RAM antes que comience a ejecutarse.
✓ Sobrepaginado o thrashing → cuando se producen demasiados fallos de página con relación
a la cantidad de instrucciones que se ejecutan.
✓ Localidad de referencia → durante la ejecución, el proceso hace referencia sólo a una
pequeña fracción de sus páginas.
✓ Conjunto de trabajo → es el conjunto de páginas que utiliza un proceso en un momento
determinado sin producir demasiados fallos de página
Imagina que eres un chef y estás preparando una cena especial:
Recetas: Son como los procesos en una computadora. Cada receta tiene una serie de ingredientes (páginas).
Cocina: Es la memoria RAM de la computadora.
Refrigerador: Es el disco duro, donde se almacenan todos los ingredientes.
El modelo del conjunto de trabajo es como planificar tu cocina antes de empezar a cocinar:
Identificar los ingredientes esenciales: Antes de empezar a cocinar, revisas la receta y anotas todos los ingredientes que vas a necesitar. Esto es como identificar el conjunto de trabajo de un proceso.
Sacar los ingredientes del refrigerador: Antes de empezar a cocinar, sacas todos los ingredientes del refrigerador y los pones en la mesa. Esto es como la prepaginación: cargar todas las páginas del conjunto de trabajo en la memoria antes de que el proceso empiece a ejecutarse.
Cocinar: Mientras cocinas, puedes necesitar otros ingredientes que no habías previsto. Esto es normal, y es como cuando un proceso necesita una página que no estaba en su conjunto de trabajo inicial.
Evitar el caos: Si sacas demasiados ingredientes del refrigerador y no los usas, tu cocina se llenará y te será difícil trabajar. Esto es como el sobrepaginado o thrashing: cuando hay demasiadas páginas en memoria y el sistema pasa más tiempo moviendo páginas entre la memoria y el disco que ejecutando programas.
Organizar tu cocina: Si trabajas de manera organizada y solo sacas los ingredientes que necesitas, cocinar será mucho más fácil y eficiente. Esto es como la localidad de referencia: los procesos suelen acceder a un conjunto limitado de páginas durante un periodo de tiempo.
Políticas de asignación local vs. global
Se utiliza para saber que pagina extraer de la memoria cuando se produce un fallo de página
Política de asignación local:
→ Se selecciona una página del mismo proceso que ocasionó el fallo de página y se asigna
una cantidad fija de memoria a cada proceso.
→ Si el conjunto de trabajo crece puede provocar catástrofe y si se encoge puede desperdiciar
espacio.
Política de asignación global:
→ Se selecciona una página entre todas las páginas de la memoria y se asigna memoria a
cada proceso en forma dinámica.
→ Funciona mejor porque se adapta a los cambios de tamaño del conjunto de trabajo.
→ El sistema debe decidir constantemente cuánta memoria asignarle a cada proceso
Imagina una biblioteca con muchos estudiantes:
Biblioteca: Es la memoria de la computadora.
Estudiantes: Son los procesos.
Libros: Son las páginas de memoria.
Mesas: Son las particiones de memoria asignadas a cada proceso.
Política de asignación local:
Cada estudiante tiene su propia mesa: Cada proceso tiene una cantidad fija de memoria asignada.
Si un estudiante necesita más libros: Tendrá que sacar un libro de su propia mesa.
Problemas: Si un estudiante necesita muchos libros (conjunto de trabajo grande), su mesa se llenará y no podrá trabajar. Si un estudiante necesita pocos libros (conjunto de trabajo pequeño), desperdiciará espacio en su mesa.
Política de asignación global:
Los estudiantes comparten todas las mesas: Todos los procesos comparten la memoria.
Si un estudiante necesita más libros: Puede tomar un libro de cualquier mesa que esté disponible.
Ventajas: El espacio se utiliza de manera más eficiente. Si un estudiante necesita muchos libros, puede tomar libros de otras mesas que estén desocupadas.
Desventajas: La biblioteca debe decidir constantemente cuántos libros asignar a cada estudiante.
Tamaño de páginas
Página grande: se produce fragmentación interna en la última página. Además, hace que partes no
utilizadas del programa estén en memoria.
Páginas pequeñas: implica que los programas van a necesitar muchas y, por lo tanto, una tabla
más grande.
Imagina que estás organizando libros en cajas:
Libros: Son como las instrucciones de un programa.
Cajas: Son como las páginas de memoria.
Cajas grandes (páginas grandes):
Problema del espacio sobrante: Si tienes cajas muy grandes y no todos los libros caben justo, te quedará espacio vacío en la última caja. Esto es como la fragmentación interna: parte de la última página de memoria queda sin utilizar.
Problema de llevar libros innecesarios: Si las cajas son muy grandes, podrías meter libros que no necesitas para un viaje corto. Esto es como tener partes de un programa en memoria que no se están utilizando en este momento.
Cajas pequeñas (páginas pequeñas):
Muchas cajas: Si las cajas son muy pequeñas, necesitarás muchas cajas para guardar todos tus libros. Esto es como tener muchas páginas de memoria para un programa.
Más trabajo de organización: Con muchas cajas, tendrás que llevar un registro de qué libro está en qué caja. Esto es como tener una tabla de páginas más grande para mantener un seguimiento de todas las páginas de memoria.
