Algoritmos de reemplazo de páginas

Alexis Bolívar Tarupi Tequiz
Mind Map by Alexis Bolívar Tarupi Tequiz, updated more than 1 year ago
Alexis Bolívar Tarupi Tequiz
Created by Alexis Bolívar Tarupi Tequiz over 4 years ago
160
0

Description

Expocicion de algoritmos

Resource summary

Algoritmos de reemplazo de páginas
  1. Los Algoritmos de reemplazo de página son aquellos algoritmos de sistemas operativos que están diseñados para solucionar el problema de decidir qué página de las que reside en memoria bajo un frame o marco debe salir para dejar entrar a otra que está siendo referenciada
    1. Ejemplo: La reducción sustancial de I/O a memoria secundaria.
      1. Paginacíon
        1. La paginación consiste en considerar el espacio de direcciones lógicas de cada proceso como un conjunto de bloques de tamaño consistente llamados páginas
        2. Memoria Virtual
          1. Cuando la memoria física de un computador se hace insuficiente, el sistema operativo puede emular una memoria de mayor tamaño que la memoria real, haciendo que parte de los procesos se mantengan en el disco
            1. A este tipo de memoria se le denomina memoria virtual, pues es una memoria inexistente, pero que para cualquier proceso es indistinguible de la memoria real
          2. Bit Valido- Invalido
            1. En el contexto de paginación, el concepto de válido indica que la página está en memoria; mientras que inválido indica que la página no se encuentra en el espacio lógico de direcciones de proceso o es válida pero no esta actualmente en el disco.
              1. Las páginas residentes en disco se marcan en la tabla de páginas del proceso con el bit valido-invalido como invalida (figura 1), de modo que si el proceso las referencia se produce una interrupción de fallo de página. En la rutina de atención de esta interrupción, se cargará en memoria la página que causó la pagina de falla, por lo que el proceso queda suspendido mientras se realiza la lectura del disco
            2. Tipos de algoritmos
              1. Algoritmo FIFO
                1. El algoritmo FIFO reemplaza las páginas de la forma que el primero que entra es el primero que sale. Asocia a cada página el instante en el que se trajo a la memoria, así cuando se tenga que reemplazar una página, se elige la más antigua
                  1. Anomalía de Belady
                    1. Ésta anomalía fue descubierta y demostrada en 1969 por el científico de la computación Laszlo Belady y consiste en que al aumentar el número de marcos en la memoria física, es posible tener más fallos de página. En la siguiente imagen vemos la diferencia, con el mismo orden de páginas, con tres y cuatro marcos en la memoria.
                2. Algoritmo Óptimo
                  1. El Algoritmo Óptimo, también conocido como OPT se originó luego del descubrimiento de la Anomalía de Belady en la búsqueda de un algoritmo mucho más óptimo. El algoritmo elige la página de la memoria que vaya a ser referenciada más tarde, las páginas se rotulan con el número de instrucciones que se ejecutarán antes de que se haga la primera referencia a ella y, cuando se presenta un fallo de página, se reemplaza la que más instrucciones falten para referenciarla para así ir aplazando lo más que se pueda los fallos de página
                  2. Algoritmo LRU
                    1. La estrategia consiste en llevar a disco la página que ha permanecido por más tiempo sin ser accesada. El fundamento de esta estrategia es que estadísticamente se observa que mientras más tiempo permanece una página sin ser accesada, menos probable es que se accese en el futuro inmediato
                      1. Implementación con Contador
                        1. Es asociada a cada tabla de página un campo de tiempo y el CPU lleva un contador o reloj el cual se incrementa en cada referencia a memoria que se realiza. Al momento de realizar el llamado a una página, este contador es copiado en el campo de tiempo que esta en su tabla correspondiente
                        2. Implementación con Pila
                          1. Se mantiene una pila, con los números en una lista doblemente enlazada. Con esta modalidad ya no se hace necesario realizar una búsqueda, como lo es con el contador, pero se tiene que realizar el cambio en los punteros de la lista. Para ir estructurando la pila, cada página referenciada se va colocando al tope de ésta.
                      2. Aproximaciones a LRU
                        1. Bit de referencia
                          1. Al no existir en todos los computadores soporte de hardware para implementar al costoso LRU, se usan otros algoritmos modificados para acercarse (como por ejemplo modificar FIFO). Otros sistemas intentan dar soporte a LRU con un bit de referencia o bit R, el cual es activado y desactivado por el hardware cuando una página es referenciada, siendo cada bit de referencia asociado con una sola página en la tabla de páginas. Cada bit es iniciado en 0 por el sistema operativo
                          2. Algoritmo de Segunda Oportunidad
                            1. Este es un algoritmo que deriva del algoritmo FIFO. El Algoritmo de Segunda Oportunidad evita deshacerse de una página de uso frecuente, hace uso del bit R inspeccionándolo de tal forma que, si es 0, la página es antigua y no utilizada, por lo que, en caso de fallo de página, es reemplazada de manera inmediata
                            2. Algoritmo NRU
                              1. El algoritmo Not Recently Used (NRU), No utilizado recientemente, Enhanced second-chance o Segunda oportunidad mejorado[1] es uno de los esquemas que intentan aproximarse al algoritmo LRU. Específicamente es una modificación del algoritmo de segunda oportunidad, el cual considera el bit de referencia R y el bit de modificación M como un par ordenado (R, M) respectivamente
                            3. Algoritmos basados en conteo
                              1. En este caso la idea es mantener un contador del numero de referencias que se han hecho a cada página. Acá se enmarcan dos algoritmos que definen a estos contadores: el LFU centrado en reemplazar las páginas menos usadas y el MFU, que reemplaza las páginas mas usadas
                                1. Algoritmo LFU
                                  1. El algoritmo Least frequently used (LFU) o Menos frecuentemente utilizado pide que la página con el menor contador sea reemplazada. Esto se justifica en que una página usada con mucha frecuencia tendrá un contador mas grande. Un problema de este esquema es cuando una página es usada intensamente durante la fase inicial de un proceso y luego no vuelve a ser usada, lo cual genera un contador mucho mayor y la página permanece en memoria sin poder ser sacada
                                  2. Aging
                                    1. Este algoritmo desciende del NFU, mejorándolo al realizar un corrimiento de 1 bit a la derecha antes de aumentar el contador de uso en 1 bit a la izquierda en su forma binaria. Esto provoca que las páginas cuyas referencias son más actuales tengan más importancia que aquellas que fueron referidas hace tiempo, asegurando que páginas usadas recientemente pero no frecuentemente tengan mayor prioridad frente a páginas usadas hace tiempo pero con mayor referencia
                                    2. Algoritmo MFU
                                      1. El algoritmo Most frequently used (MFU) o Mas frecuentemente utilizado, que al contrario del LFU está basado en el argumento de que la página con el menor contador fue probablemente traída hace poco y aún no ha sido usada, por lo que la página con el mayor contador será la «víctima» en este caso.
                                  Show full summary Hide full summary

                                  Similar

                                  MI PLE PORQUE ESCOGÍ LA CARRERA DE PSICOLOGÍA
                                  flor Milena Romero Rayo
                                  fisica
                                  pecblanca
                                  sentido de la vida
                                  Cristian Londoño
                                  equipo interdiciplinario de rehabilitacion
                                  lizeth bello
                                  ¿Estamos en este mundo para servir a los demás?
                                  JuanPGarcía27
                                  Mi aprendizaje sobre PROSOCIALIDAD
                                  Maria Cervantes
                                  ¿Qué es educación ambiental?
                                  Mireya Callahuara Clemente
                                  Villa perro s.a de c.v
                                  sharodriguez
                                  Introduce el texto aquí
                                  paola gonzalez