Download INSTITUTO TECNOLOGICO DE MATEHUALA UNIDAD 4 La

INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
Sistemas Operativos
III. Memoria
La memoria es uno de los recursos más importante de la computadora y en consecuencia la parte
del sistema operativo responsable de tratar con este recurso es el gestor de memoria.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Objetivos del sistema de administración de
memoria
– Ofrecer a cada proceso un espacio lógico propio
– Proporcionar protección entre los procesos
– Permitir que los procesos compartan memoria
– Dar soporte a las distintas regiones del proceso
– Maximizar el rendimiento del sistema
– Proporcionar a los procesos mapas de memoria
muy grandes
El gestor de memoria del sistema operativo debe hacer de puente entre los requisitos de las
aplicaciones y mecanismos que proporcionan, y el hardware de gestión de memoria.
Objetivos del sistema de administración de memoria
En un sistema con multiprogramación, el sistema operativo debe encargarse de realizar un reparto
transparente, eficiente y seguro de los distintos recursos de la máquina entre los diferentes
procesos de forma que cada uno de ellos crea que tiene una máquina para él solo.
En el caso de la memoria, el sistema operativo con el apoyo del hardware de gestión de memoria
del procesador debe repartir el almacenamiento existente proporcionando un espacio de
memoria independiente para cada proceso y evitando la posible interferencia voluntario o
involuntario de cualquier otro proceso.
Se podría considerar que, en el caso del procesador, se realiza un reparto en el tiempo mientras
que de la memoria se trata de un reparto en el espacio.
La acción combinada de estos dos mecanismos ofrece a los programas una abstracción de
procesador virtual que les independiza del resto de los procesos.
A continuación, las siguientes características se pueden destacar como objetivos deseables del
sistema de administración de memoria:






Ofrecer a cada proceso un espacio lógico propio
Proporcionar protección entre los procesos
Permitir que los procesos compartan memoria
Dar soporte a las distintas regiones del proceso
Maximizar el rendimiento del sistema
Proporcionar a los procesos mapas de memoria muy grandes
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Objetivos del sistema de administración de
memoria
Los programas y datos necesitan estar en la memoria principal para ser ejecutados o para poder
ser referenciados.
Los programas o datos que no se necesiten de inmediato pueden guardarse en la memoria
secundaria hasta que se necesiten y en ese momento se transfieren a la memoria principal para
ser ejecutados o referenciados.
Los dispositivos de memoria secundaria son menos caros que la memoria principal y su capacidad
es mayor, sin embargo, generalmente es más rápido el acceso a la memoria principal que a la
secundaria.
En los años 60’s surge otro nivel en la jerarquía de la memoria llamada memoria caché. Es una
memoria de alta velocidad mucho más rápida que la memoria principal, es extremadamente cara
comparada con la memoria principal, por lo que se utiliza en relativamente pequeñas cantidades.
La memoria caché introduce un nivel adicional de transferencia de información en el sistema. Los
programas en memoria principal se pasan a la memoria caché antes de ejecutarse. En memoria
caché se pueden ejecutar mucho más rápido que en la principal.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Espacios lógicos independientes
– Dirección lógica
– Dirección física
– Espacio de direcciones lógicas
– Espacio de direcciones físicas
En un sistema operativo de propósito general no se puede conocer a priori la posición de memoria
que ocupará un programa cuando se cargue en memoria para proceder a su ejecución puesto que
dependerá del estado y la ocupación de la memoria.
El código máquina de un programa contenido en un archivo ejecutable incluirá referencias a
memoria tanto para acceder a sus operandos como parta realizar bifurcaciones en la secuencia de
ejecución. Por lo que será necesario realizar un proceso de traducción (reubicación) de las
direcciones de memoria a las que hacen referencia las instrucciones de un programa (direcciones
lógicas). Para que correspondan a las direcciones de memoria principal asignados al mismo
(direcciones físicas).
Este proceso de traducción crea, por tanto, un espacio lógico o mapa independientemente para
cada proceso, proyectándolo sobre la parte correspondiente de la memoria principal, de acuerdo
con una función de traducción.




Dirección lógica: Direcciones de memoria a las que hacen referencia las instrucciones
de un programa son generadas por el CPU. Conocidas también como dirección virtual.
Dirección física: Designa la posición real de la memoria principal. Corresponde a
aquella cargada en memoria.
Espacio de direcciones lógicas: Conjunto de direcciones generadas por un programa
Espacio de direcciones físicas: Conjunto de posiciones de memoria
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• MMU
MMU es un módulo específico del procesador que traduce las direcciones virtuales a direcciones
de memoria principal. En el esquema del MMU el valor en el registro de relocalización se le suma a
cada dirección generada por un proceso de usuario al momento en que se manda a la memoria. El
programa de usuario se comunica a través de la dirección lógica y nunca ve la dirección física.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• MMU
– Protección
– Compartición
– Soporte de las regiones del proceso
– Maximizar el rendimiento
– Mapas de memoria muy grandes para los
procesos
- Protección
Cada proceso debe protegerse contra interferencias no deseadas de otros procesos, accidentales o
intencionadas. El código de un proceso no puede hacer referencia a posiciones de memoria de
otros procesos sin permiso. Es imposible comprobar las direcciones absolutas de los programas
puesto que se desconoce la ubicación de un programa en memoria principal.
Debe comprobarse durante la ejecución que todas las referencias a memoria generadas por un
proceso para asegurar que solo hacen referencia al espacio de memoria destinado a dicho
proceso.
- Compartición
Cualquier mecanismo de protección debe permitir el acceso de varios procesos a la misma zona de
la memoria principal. Es mejor permitir a cada proceso que acceda a la misma copia del programa
en lugar de tener cada uno su propia copia aparte.
- Soporte de las regiones del proceso
El mapa de un proceso no es homogéneo sino que está formado por distintos tipos de regiones
con diferentes características y propiedades. Dado que el sistema operativo conoce que regiones
incluye el mapa de memoria de cada proceso el gestor de memoria con el apoyo del hardware
deberán dar soporte a las características específicas de cada región.
- Maximizar el rendimiento
El grado de multiprogramación en un sistema influye directamente en el porcentaje de utilización
del procesador y, por tanto, en el rendimiento del sistema.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
Adicionalmente, un mayor grado de multiprogramación implica que puede existir un mayor
número de tareas ejecutándose simultáneamente en el sistema.
El gestor de memoria debe, por tanto, realizar un reparto de la memoria entre los procesos
intentando que quepa el mayor número de ellos en memoria y minimizando el desperdicio
inherente del reparto.
- Mapas de memoria muy grandes para los procesos
En los tiempos en los que la memoria era muy cara y en consecuencia los equipos poseían una
memoria bastante reducida se producían situaciones en las que las aplicaciones se veían limitadas
por el tamaño de la memoria. Para solventar este problema, los programadores usaban la técnica
de los overlays.
Esta técnica consiste en dividir el programa en una serie de fases que se ejecutan sucesivamente
pero estando en cada momento residente en memoria una sola fase. Cada fase se programa de
manera que después de realizar su labor cargue en memoria la siguiente fase y le cede el control.
Por todo esto se ideó la técnica de memoria virtual que permite proporcionar a un proceso de
forma transparente un mapa de memoria considerablemente mayor que la memoria física
existente en el sistema.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Asignación de memoria contigua
Un esquema simple de gestión de memoria consiste en asignar a cada proceso una zona contigua
de memoria para que en ella resida su mapa de memoria. Existen diversas estrategias entre ellos
la gestión continua, basada en particiones dinámicas. Con esta estrategia, cada vez que crea un
proceso en el sistema operativo busca un hueco de memoria de tamaño suficiente para alojar el
mapa de memoria del mismo. El sistema operativo reservará la parte del hueco necesaria, creará
en ella el mapa inicial del proceso y establecerá una función de traducción tal que las direcciones
que genera el programa se corresponderán con la zona asignada.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Mapa de memoria de un proceso
El mapa de memoria de un proceso no es algo homogéneo sino que está formado por distintas
regiones o segmentos. Una región tiene asociada una determinada información (objeto de
memoria). Cuando se activa la ejecución de un programa se crean varias regiones dentro del
mapa. Cada región es una zona contigua que está caracterizada por la dirección dentro del mapa
del proceso donde comienza y por su tamaño.
Las regiones que presenta el mapa de memoria inicial del proceso se corresponden, básicamente
con las secciones del ejecutable más la pila inicial del proceso.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Mapa de memoria de un proceso
– Pila
– Heap
– Archivo proyectado
– Pilas de hilos o Pilas de threads
Pila
Servirá de soporte para almacenar los registros de activación de las llamadas a funciones (las
variables locales, parámetros, dirección de retorno). Se trata, por tanto, de una región de tamaño
variable.
Los sistemas operativos modernos ofrecen un modelo de memoria dinámico en el que el mapa de
un proceso está formado por un número variable de regiones que pueden añadirse o eliminarse
durante la ejecución.
Heap
La mayoría de los lenguajes de alto nivel ofrece la posibilidad de reservar espacio en memoria en
tiempo de ejecución. En el caso de C, se realiza con la función mallloc().
Esta región sirve de soporte para la memoria dinámica que reserva un programa en tiempo de
ejecución. En sistemas POSIX cada programa tendrá un único heap, mientras que en WIN32 se
permite la creación de múltiples heap para un solo proceso.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Mapa de memoria de un proceso hipotético
Código
Datos de valor inicial
Datos sin valor inicial
Heap
XXXXXXXXXXXXXXXXXXXXXXXX
Archivo proyectado f
XXXXXXXXXXXXXXXXXXXXXXXX
Zona de memoria compartida
XXXXXXXXXXXXXXXXXXXXXXXX
Código de biblioteca dinámica
Datos de biblioteca dinámica
XXXXXXXXXXXXXXXXXXXXXXXX
Pila thread 1
XXXXXXXXXXXXXXXXXXXXXXXX
Pila de proceso
Hay que resaltar que dado el carácter dinámico del mapa de memoria de un proceso se crean y se
destruyen regiones, algunas regiones cambian de tamaño, etc.
Existirán, en un determinado instante, zonas sin asignar (huecos) dentro el mapa de memoria.
Hay que recalcar que, dado que el sistema operativo es un programa, su mapa de memoria
contendrá también regiones de código, datos, heap, etc.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de la memoria
• Partición de la memoria
– Partición estática
– Partición dinámica
– Compactación
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de la memoria
• Técnica de intercambio (swapping)
– 1ª Preasignación
– Sin Preasignación
La técnica de intercambio significó, en su momento, una manera de permitir que los sistemas de
tiempo compartido existieran más procesos de los que caben en memoria. Se considera un
mecanismo antecesor de la memoria virtual.
El intercambio se basa en usar un disco o parte de un disco (Dispositivo de swap) como respaldo
de la memoria principal. Cuando no caben en memoria todos los procesos activos se elige un
proceso residente y se copia en swap su imagen de memoria. El criterio de selección puede tener
en cuenta aspectos tales como la prioridad del proceso, el tamaño de su mapa de memoria, el
tiempo que lleva ejecutándose y principalmente, su estado.
En cuanto a los dispositivos de swap hay dos alternativas en la asignación de espacio:
1ª Preasignación: Al crear el proceso ya se reserva espacio de swap suficiente para almacenarlo.
Sin Preasignación: Sólo se reserva espacio de swap cuando se expulsa el proceso.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de la memoria
• Memoria Virtual
En prácticamente todos los sistemas modernos se utiliza la memoria virtual. En un sistema sin
memoria virtual el sistema operativo divide la memoria principal en trozos y asigna una a cada uno
de los programas que están ejecutándose.
La memoria virtual utiliza dos niveles de la jerarquía de memoria: la memoria principal y una
memoria de respaldo (que suele ser el disco, aunque puede ser una memoria expandida). En la
memoria de respaldo se establece un mapa uniforme de memoria virtual. Las direcciones
generadas por el procesador se refieren a este mapa virtual pero, sin embargo, los accesos reales
se realizan sobre la memoria principal.
La gestión de memoria virtual es automática y la realiza el sistema operativo con ayuda del
hardware de la máquina. Esta gestión incluye toda la memoria principal, y una parte del disco que
sirve de respaldo a la memoria virtual.
Los aspectos principales en los que se basa la memoria virtual son:


Las direcciones generadas por las instrucciones-máquina están referidas al espacio virtual,
es decir, forman parte del mapa de memoria virtual.
El mapa virtual asociado a un programa en ejecución está soportado físicamente por una
zona del disco denominado de intercambio o swap y por una zona de memoria principal.
Aunque el programa genera direcciones virtuales para que este pueda ejecutar han de residir en
memoria principal las instrucciones y los datos utilizados en cada momento.
Los espacios virtual y físico se dividen en páginas. Se denominan páginas virtuales a las páginas del
espacio virtual, páginas de intercambio a las páginas residentes en el disco y marcos de página a
los espacios en los que se divide la memoria principal.
Cada marco de página es capaz de almacenar una página virtual cualquiera.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
Existe una unidad hardware llamada MMU (Memory Management Unit) que traduce las
direcciones virtuales a direcciones de memoria principal (físicas)
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Memoria Virtual
– Algunos beneficios de la memoria virtual
Algunos beneficios de la memoria virtual
Se produce un aumento del grado de multiprogramación al no ser necesario que todo el mapa de
memoria de un proceso esté en memoria principal para poder ejecutarlo. Este aumento implica
una mejora en el rendimiento del sistema.
Se pueden ejecutar programas más grandes que la memoria principal disponible.
Es importante mencionar que el uso de memoria virtual NO acelera la ejecución de un programa,
sino que puede incluso la ralentice debido a la sobrecarga asociada a las transferencias entre
memoria principal y secundaria, esto hace que esta técnica no sea apropiada para sistemas en
tiempo real.
De manera general, la técnica de memoria virtual se ocupa de gestionar la transferencia de
información entre la memoria principal y la secundaria.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Paginación
Bit de residencia de
páginas
Dirección en memoria
secundaria
Número de marco de
página
r
s
P’
r=0 si la página no está en memoria principal
r=1 si la página está en memoria principal
Tabla de correspondencia de páginas
Como su nombre lo indica, la mitad básica de este tipo de esquema es la página. La página
corresponde a una zona de memoria contigua de un determinado tamaño. Por razones de
eficiencia en la traducción, este tamaño debe ser potencia de 2 (los tamaños comunes van de 2KB
a 16 KB).
La paginación intenta resolver los problemas que se presentaban con la gestión de memoria
basada en la asignación contigua, mejorando significativamente el uso del hardware de gestión de
memoria del proceso, y aumentando considerablemente la cantidad de información de traducción
que se almacena por cada proceso.
El mapa de memoria de cada proceso se considera dividido en páginas, a su vez, la memoria
principal del sistema se considera dividida en zonas del mismo tamaño que se llaman marcos de
página. Un marco de página contendrá en un determinado instante una página de memoria de un
proceso. La estructura de datos que relaciona cada página con el marco en que está almacenada
es la tabla de páginas.
El procesador emplea el número de página y un desplazamiento para calcular las direcciones
absolutas (físicas)
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Paginación
– Correspondencia Directa
– Errores
• Error de página
• Error por desbordamiento
Correspondencia directa
Este método ayudará a encontrar la dirección real a partir de la dirección virtual utilizando la tabla
de páginas.
La dirección virtual tiene la estructura:
v = (p, d)
p = número de página
d= desplazamiento
Errores
Error de página: Cuando una página no está en memoria principal (r=0).
Error por desbordamiento: Cuando el desplazamiento es mayor que el tamaño de página.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Segmentación
Tabla de correspondencia de segmentos (TCS)
r
Bit de
referencia
del
segmento
s
L
r
w
Dirección
Longitud Bits de protección
en
del
1=si
memoria segmento
0=no
secundaria
x
r=lectura
w=escritura
x=ejecución
a=adición
a
s’
Dirección
base del
segmento
r=0 si el segmento no está en memoria principal
r=1 si el segmento está en memoria principal
Segmentación
Con la paginación, la MMU no sabe nada sobre las distintas regiones de los procesos. Solo
entiende de páginas, el sistema operativo debe guardar para cada proceso una tabla de regiones
que especifique que páginas pertenecen a cada región.
En resumen, lo que le falta al MMU es que sea consciente de la existencia de las regiones y que
permita tratar a una región como a una entidad. La segmentación es una técnica hardware que
intenta dar soporte directo a las regiones, para ello considera el mapa de memoria de un proceso
compuesto de múltiples segmentos, cada región se almacenará en un segmento.
Dado que cada segmento se almacena en memoria de forma contigua este esquema presenta
fragmentación externa. El sistema operativo debe usar una estructura de datos similar a los
utilizados con los esquemas de asignación contigua para conocer que partes de la memoria
principal están libres y cuales ocupadas.
A pesar de dar soporte a los segmentos, la segmentación tal como se ha descrito presenta
numerosas deficiencias que hacen que prácticamente no se use en los sistemas reales.
Las principales deficiencias de esta técnica consiste en que nos e obtiene un buen
aprovechamiento de la memoria, además de que no facilita la implementación de esquemas de
memoria virtual por el tamaño variable de los segmentos y adicionalmente presenta
fragmentación externa. Por último, no contempla adecuadamente el implementar mapas de
memoria muy grandes.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Segmentación
– Correspondencia Directa
– Errores
• Error por segmento
• Error por desbordamiento
Correspondencia directa
Este método ayuda a encontrar la dirección física a partir de la dirección virtual utilizando la
estructura TCS
La dirección virtual tiene la estructura:
V=(s, d)
s=número de segmento
d=desplazamiento
Errores
Error de segmento: Cuando un segmento no está en memoria principal (r=0)
Error por desbordamiento: Cuando el desplazamiento es mayor o igual que la longitud del
segmento.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Paginación y segmentación combinadas
– Protección
– Compartir memoria
– Soporte de las regiones
– Maximizar el rendimiento
– Mapas de memoria grandes
Como su nombre lo indica, esta técnica intenta aunar lo mejor de los dos esquemas anteriores. La
segmentación proporciona soporte directo a las regiones del proceso y la paginación permite un
mejor aprovechamiento de la memoria y una base para construir un esquema de memoria virtual.
Con esta técnica, un segmento está formado por un conjunto de páginas y por tanto no tiene que
estar contiguo en memoria. La MMU utiliza una tabla de segmentos tal que cada entrada de la
tabla apunta a una tabla de páginas.
La dirección virtual estará dada por:
V=(s,p,d)
Donde s es el número de segmento, p el número de página, y d el desplazamiento.
La valoración de esta técnica con respecto a los objetivos de la administración de memoria son:






Espacios lógicos independientes: cada proceso tiene una tabla de segmento por lo que se
logra la independencia.
Protección: La segmentación soporta esta característica.
Compartir memoria: Bajo el control del sistema operativo dos o más procesos pueden
tener un segmento asociado a la misma zona de memoria.
Soporte de las regiones: Lo permite la segmentación.
Maximizar el rendimiento: La paginación proporciona un buen aprovechamiento de la
memoria, además sirve de base para construir un esquema de memoria virtual.
Mapas de memoria grandes: La paginación permite la implementación de un esquema de
memoria virtual.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Reemplazo de páginas
– Reemplazo Global
– Reemplazo Local
Reemplazo de páginas
Cuando un proceso necesita acceder a una página que no está en memoria principal se le
denomina fallo de página. El sistema operativo se encarga de transferirla, entonces, desde la
memoria secundaria, si al intentar traer la página desde memoria secundaria se detecta que no
hay espacio en memoria (que no hay marcos libres) será necesario expulsar una página de
memoria principal y transferirla a la secundaria. El algoritmo parea elegir que página debe ser
expulsada se llama algoritmo de reemplazo.
Las estrategias de reemplazo se pueden clasificar en:


Reemplazo global
Reemplazo Local
Con una estrategia de reemplazo global se puede seleccionar para satisfacer el fallo de página de
un proceso un marco que actualmente tenga asociada una página de otro proceso. La estrategia
de reemplazo local requiere que para servir el fallo de página de un proceso, solo pueden usarse
páginas libres o marcos ya asociados al proceso.
El objetivo básico de cualquier algoritmo de reemplazo es minimizar la tasa de fallos de página,
intentando además que la sobrecarga asociada a la ejecución del algoritmo sea tolerable.
Los siguientes algoritmos pueden utilizarse tanto para estrategias globales como para locales.
Algoritmo de reemplazo óptimo, algoritmo FIFO (First In – First Out), Algoritmo de la segunda
oportunidad o de reloj, Algoritmo LRU (Last Recently Used).
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
3.1 Administración de memoria
• Algoritmos de reemplazo
– Algoritmo de Reemplazo Óptimo
– Algoritmo LRU (Less Recently Used)
– Algoritmo FIFO (First Input, First Output)
– Algoritmo de Reloj
Algoritmo de reemplazo óptimo
Selecciona para reemplazar la página que tiene que esperar una mayor cantidad de tiempo hasta
que se produzca la referencia siguiente. Esta política genera el menor número de fallos de página
pero resulta imposible de implementar pues requiere que el sistema operativo tenga un
conocimiento exacto de los sucesos futuros.
Algoritmo LRU (Less Recently Used)
Reemplaza la página de memoria que no ha sido referenciada desde hace más tiempo. Debido al
principio de cercanía, ésta debería ser la página con menor probabilidad de ser referenciada en un
futuro cercano. El problema de este método es su dificultad de implementación. Una solución
sería etiquetar cada página con el momento de su última referencia; esto tendría que hacerse con
cada referencia a la memoria, tanto para instrucciones como datos. Incluso si el hardware
respaldara este esquema, la sobrecarga resultaría tremenda. Como alternativa, se podría
mantener una pila de referencias a páginas, aunque también con un coste elevado.
Algoritmo FIFO (First Input, First Output)
Trata los marcos asignados a un proceso como un buffer circular y las páginas se suprimen de la
memoria según la técnica de turno rotatorio (round-robin). Todo lo que se necesita es un puntero
que circule a través de los marcos del proceso. Esta es, por tanto, una de las políticas de
reemplazo más sencillas de implementar. La lógica que hay detrás de esta elección, además de su
sencillez, es reemplazar la página que ha estado más tiempo en la memoria: una página
introducida en la memoria hace mucho tiempo puede haber caído en desuso. Este razonamiento,
será a menudo incorrecto, porque habrá regiones del programa o de datos que son muy usadas a
lo largo de la vida de un programa. Con el algoritmo FIFO, estas páginas se cargarán y expulsarán
repetidas veces.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.
INSTITUTO TECNOLOGICO DE MATEHUALA
UNIDAD 4
Algoritmo de reloj
La forma más simple de política de reloj requiere asociar un bit adicional a cada marco,
denominado bit de uso. Cuando se carga una página por primera vez en un marco de memoria el
bit de uso de dicho marco se pone a 0. Cuando se hace referencia a la página posteriormente
(después de la referencia que generó el fallo de página), el bit de uso se pone a 1. Para el
algoritmo de reemplazo de páginas, el conjunto de marcos candidatos a ser reemplazados se
considera como un buffer circular con un puntero asociado. Al reemplazar una página, se hace que
el puntero señale al siguiente marco del buffer. Cuando llega el momento de reemplazar una
página, el sistema operativo recorre el buffer buscando un marco con el bit de uso a 0. Cada vez
que se encuentra un marco con el bit de uso a 1, lo pone a 0. Si algún marco del buffer tiene el bit
de uso a 0 al comienzo de la búsqueda, se elige para reemplazar el primero que se haya
encontrado. Si todos los marcos tienen el bit de uso puesto a 1, el puntero dará una vuelta
completa al buffer, poniendo todos los bits a 0 y se detendrá en la posición inicial, reemplazando
la página de dicho marco. Se puede comprobar que esta política es similar a la FIFO, excepto que
cualquier marco con el bit de uso a 1 se descarta en el algoritmo.
NOTA: Material recopilado únicamente para fines educativo para apoyar el proceso enseñanzaaprendizaje de la materia sistemas operativos I.