7067998
Description
Mind Map by Alexis Bolívar Tarupi Tequiz, updated more than 1 year ago
|
Created by Alexis Bolívar Tarupi Tequiz
about 8 years ago
|
|
Algoritmos de reemplazo de páginas
- 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
- Ejemplo: La reducción sustancial de I/O a memoria secundaria.
- Paginacíon
- 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
- 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
- Memoria Virtual
- 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
- 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
- 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
- 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
- Bit Valido- Invalido
- 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.
- 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
- 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
- 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.
- Tipos de algoritmos
- Algoritmo FIFO
- 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
- Anomalía de Belady
- É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.
- É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.
- Anomalía de Belady
- 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
- Algoritmo Óptimo
- 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
- 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
- Algoritmo LRU
- 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
- Implementación con Contador
- 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
- 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
- Implementación con Pila
- 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.
- 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.
- Implementación con Contador
- 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
- Aproximaciones a LRU
- Bit de referencia
- 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
- 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
- Algoritmo de Segunda Oportunidad
- 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
- 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
- Algoritmo NRU
- 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
- 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
- Bit de referencia
- Algoritmos basados en conteo
- 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
- Algoritmo LFU
- 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
- 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
- Aging
- 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
- 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
- Algoritmo MFU
- 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.
- 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.
- 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
- Algoritmo FIFO
Media attachments
Want to create your own Mind Maps for free with GoConqr? Learn more.