UNIDAD I. ADMINISTRACION DE LA MEMORIA
1.1
Políticas y filosofía de administración de
memoria.
La memoria es
tal vez el recurso más importante de una computadora pues su estructura y
manejo tienen una incidencia muy grande en el uso de los demás recursos y el
buen desempeño de la computadora. Para que un programa pueda ser ejecutado en
una computadora, tanto él como los datos que vaya a manejar deben estar
almacenados en la memoria principal o física.
Para mejorar
el rendimiento del procesador y su capacidad de proceso, se pueden repartir los
servicios del mismo entre varios programas que necesitan estar simultáneamente
cargados en la memoria, por tanto se hace “compartir”
la misma.
En el
funcionamiento de una computadora podemos considerar la memoria principal como
el recurso central, ya que tanto el procesador como los dispositivos de E/S
acceden a ella para leer y/o grabar la información que manejen, observe figura
# 1:
Figura # 1. Funcionamiento
de una computadora.
El procesador
leerá de la memoria una instrucción para ejecutarla, y a su vez tomará de la
misma los datos que necesiten para al final depositar el posible resultado
también en la memoria.
Esta
operación se repite constantemente, por ello la velocidad a la que se realicen
estos accesos, tanto de lectura como de escritura, condicionarán la rapidez y
eficacia de la computadora.
Se consideran
importantes dos parámetros relacionados con la velocidad de lectura y escritura
de datos de la memoria principal:
·
Tiempo de
acceso de memoria. El tiempo que transcurre entre el inicio y el final de una
operación de lectura o de escritura sobre la misma.
·
Tiempo de
ciclo de memoria. Marca el retraso que impone el hardware entre el fin de una
operación y el principio de la siguiente.
Ambos factores marcan la velocidad de
la memoria principal.
Son
muchos los factores que hay que tener en cuenta para definir las políticas de
manejo de la memoria.
Analizaremos algunos de ellos:
·
Las necesidades de los usuarios inciden directamente en las
características y la complejidad de los sistemas: es diferente construir un
manejador de memoria para una
microcomputadora (monousuario sin
memoria virtual ni mecanismos de protección) que para una computadora grande de
propósito general (para tiempo compartido y multiprogramación, con mecanismos
de protección sofisticados, memoria virtual, etc.). En la micro el
administrador de la memoria es casi inexistente, mientras en los sistemas
grandes es uno de los más importantes.
·
El hardware en el que se debe correr el sistema define en gran
medida las características y complejidad del administrador de la memoria. Su
estructura puede conducir a que existan
ciertas restricciones (por ejemplo, en el tamaño de las peticiones de memoria)
o a que deben construirse componentes especiales (manejo de memoria virtual).
·
Es importante tener en cuenta que la administración de la memoria
puede llegar a tener una gran relación con la del procesador lo cual hace que
en los sistemas grandes el diseño de estos dos componentes se haya
integradamente.
·
Podemos distinguir dos aspectos en relación con la administración
de la memoria: los locales o relacionados con el manejo de la memoria dentro de
un programa y los globales, que tienen que ver con los mecanismos de asignación
y compartición de la misma entre los distintos usuarios.
La organización y administración de la “memoria
principal ”, “memoria primaria” o “memoria real” de un
sistema ha sido y es uno de los factores más importantes en el diseño de los S.
O
Los términos “memoria” y “almacenamiento”
se consideran equivalentes.
Los programas y datos deben estar en el
almacenamiento principal para:
Se considera “almacenamiento
secundario” o “almacenamiento auxiliar” al generalmente soportado en
discos.
Los hechos demuestran que generalmente los
programas crecen en requerimientos de memoria tan rápido como las memorias:
La parte del S. O. que
administra la memoria se llama “administrador de la memoria”:
1.2
Mecanismos de asignación.
Administración de la memoria dentro de un
programa para su ejecución en una computadora, todo programa debe pasar por
ciertas etapas: codificación, compilación , encadenamiento, carga, en la
mayoria de los casos la relocalización en la memoria, y ejecución. La forma y
el tiempo de realizar estos procesos varían
de una computadora a otra.
Muestra de estos procesos en un sistema
tradicional.
Figura # 2.
Algoritmo Codificación Prog. Fuente Compilación Programa compilado
(Modulo objeto)
Encadenamiento y Relocalización parcial
Programa Carga y
Relocalización Programa
Encadenado
listo para
(Modulo cargable) ejecutar.
Figura #
2. Encadenamiento de un programa.
El encadenamiento
consiste
en juntar en un mismo espacio de direcciones los distintos modulos o procedimientos que constituyen el programa
y resolver las referencias externas, que son las que hace un modulo a otro (que
pueden haber sido compilados separadamente). El almacenamiento lo puede hacer
el usuario o el sistema operativo.
La
carga consiste en colocar el programa en la memoria con el fin de que
pueda ser ejecutado. Esta etapa va
acampañada de la relocalización, la cual consiste en ajustar el programa para
que pueda ser ejecutado en cualquier sitio de la memoria.
Supongamos
que se tiene el siguiente trozo de programa escrito en lenguaje ensamblador: Figura
# 3.
CARGUE 1,f
SUME 1,g
100 GUARDE 1,f
f: DC 0
104
g: DC 1
Figura # 3.
Para
su ejecución en la computadora el programa se debe traducir a lenguaje de
máquina. Sin embargo, el ensamblador no
conoce el sitio en donde va a ser
cargado el programa, y por lo tanto no puede traducir adecuadamente la
referencia a la memoria.
Por ejemplo si el programa fuera cargado
en la posición 0, y suponiendo que la variable f y y están en las
posiciones 100 y 104 respectivamente, con respecto al comienzo del programa, el
programa generado en lenguaje ensamblador sería: Figura # 4.
Posición 0 cargue
1,100
Sume 1,104
Guarde
1,100
100
104
0
1 constantes
Figura # 4.
Sin
embargo el programa fuera cargado en la posición 100, el código generado sería:
Figura # 5.
Posición 100 cargue 1,200
Sume 1,204
Guarde 1,200
100
104
0
1
constante
Figura # 5.
Para resolver el problema anterior, y
teniendo en cuenta que en un sistema de multiprogramación es inadmisible que se
fije el sitio de carga desde la compilación ( o ensamblaje) de un programa, se
deben diseñar mecanismos de relocalización adecuados.
la
“asignación contigua” cada programa ocupa un bloque contiguo y sencillo de
localizaciones de almacenamiento.
En la “asignación no contigua” un programa
se divide en varios bloques o “segmentos” que pueden almacenarse en
direcciones que no tienen que ser necesariamente adyacentes, por lo que es más
compleja pero más eficiente que la asignación continua.
Asignación Contigua de
Almacenamiento de Un Solo Usuario
Se consideran S. O. que ya poseen desarrollado el “sistema
de control de entrada / salida”: IOCS: input / output control system
El tamaño de los programas está limitado por la
cantidad de memoria principal, pero se puede superar este límite con técnicas
de “recubrimientos”, con las siguientes características.
Protección en los sistemas de un
solo usuario
El usuario tiene un completo control sobre la
totalidad del almacenamiento principal:
Procesamiento por
lotes de flujo único
Los sistemas de un solo usuario se dedican a un
trabajo durante más tiempo del que toma su ejecución.
Los trabajos requieren de:
Durante la instalación
y descarga de los trabajos la cpu no está ejecutando dichos trabajos
requeridos, por lo cual:
En el “procesamiento
por lotes de flujo único” los trabajos se agrupan en “lotes”
encolándose para su ejecución.
El “procesador de flujos de trabajos”:
1.3
Estrategias de
asignación.
Para poder correr programas más largos que
la memoria disponible puede usarse el método llamado de Recubrimiento Automático,
el cual, a pesar de ser engorroso para el usuario, puede ser de gran utilidad.
La idea es que un programa pueda ser dividido en partes de tal manera que una
parte que necesite ejecutarse puede recubrir a otras que no se necesita tener
en la memoria durante su ejecución.
El recubrimiento consiste en que para la ejecución
de un programa sus partes se recubran unas con otras, permitiendo así ejecutar
programas más grandes que la memoria principal disponible.
Para poder realizar lo anterior es
necesario efectuar operaciones de E/S sobre la memoria auxiliar, lo cual
conduce a que el tiempo de ejecución del programa aumente.
El recubrimiento puede
ser total (chaining) o parcial (overlay). En el primer caso un programa recubre
completamente a otro, ocupando toda la memoria asignada por éste, en el segundo,
algunos procedimientos del programa recubren parcialmente a otros.
La idea del recubrimiento total es que en
un programa que no cabe en la memoria disponible para su ejecución sea dividido
en varios programas que se ejecuten excluyentemente. Esto puede ser útil en
caso, por ejemplo, de un programa basado en menús en el cual podemos hacer que
el manejo del menú y las diferentes opciones del mismo se hagan a través de
programas independientes que se recubran entre sí.
La principal limitación del método consiste
en la dificultad de comunicar información entre los diferentes programas, aun
que puede ser separada enviando la información correspondiente a la memoria
auxiliar o usando otros métodos, dependiendo del sistema. Encontramos esta
facilidad, entre otros, en Turbo-Pascal y en Unix.
El recubrimiento parcial consiste en
compartir una misma zona de memoria entre diferentes grupos de procedimientos
que se ejecutan excluyentemente. Supongamos que tenemos un programa con la
estructura siguiente: Figura
# 6.
Programa
Principal
Proc.
A Proc. B Proc. C
Proc. D Proc. E Proc. F Proc. G Proc.
H
Figura # 6. Estructura de un programa.
El programa principal llama a los
procedimientos A, B y C, y el procedimiento A llama a D y E etc. Es posible ejecutar el programa anterior
cargando en la memoria (Además del programa principal), los procedimientos Ay
D, luego Ay E, luego B y F, etc., con lo cual se requerirá memoria para contener
todo el programa, sino únicamente la rama más larga mostrada en el árbol
anterior .
Por razones obvias se impone la limitación
de que no puede haber llamados entre procedimientos de distintas ramas. Para
poder implantar el recubrimiento parcial es necesario que el encadenador y el
cargador conozcan la estructura del programa, y que tengan mecanismos para
manejar el recubrimiento, desempeñando funciones como encadenar las diferentes
ramas del árbol, cargar dinámicamente los procedimientos a medida que se van
necesitando, etc.
La gran ventaja del método es la de
permitir ejecutar programas más grandes que la memoria disponible.
Las principales desventajas son la falta
de transparencia al usuario, la complejidad que introducen en los mecanismos de
encadenamiento y carga y el aumento que producen el tiempo de ejecución del
programa.
Fragmentación
de memoria:
Si un proceso requiere m palabras en memoria principal para correr y se
ejecutan en una partición de n palabras, y si n es mayor que m la diferencia
entre n-m es una fragmentación interna.
Si los programas no ocupan siempre todo el
espacio disponible de memoria se denomina fragmentación Interna.
Fragmentación
Externa. Ocurre cuando una
partición esta disponible y no es usada, es decir es muy pequeña para que pueda
correr un proceso.
Administración
de la memoria en sistemas sin memoria virtual.
La
principal tarea del administrador de la memoria es asignar o distribuir ésta
entre los distintos usuarios. Se utilizan dos técnicas básicas: asignar toda la
memoria disponible para usuarios a cada uno de los programas, por periodos de
tiempo ( en forma similar a como se hace con el procesador), o dividir la
memoria en partes y asignarle una parte a cada programa activo.
Existen
además métodos, combinados que consisten en dividir la memoria en zonas y
compartir algunas de ellas en el tiempo entre varios programas. Existiendo para
esto dos métodos. El primer método se denomina intercambio Global ( o swapping) y el segundo asignación por particiones.
Intercambio
global.
Es
muy útil en sistemas de tiempo compartido. En estos sistemas, cuando se ha
finalizado una transacción con el usuario, se entra en un tiempo de espera
relativamente largo en términos de tiempo de procesador, mientras el usuario
piensa e introduce un nuevo comando. Durante este tiempo se puede cargar un
nuevo programa en la zona asignada al usuario. Para ello se requiere transferir
el primer programa a la memoria auxiliar (swapping) y cargar el nuevo programa
en la zona. Una vez que este último finalice su transacción se puede volver a
cargar el primer programa. Observe figura
# 7.
Figura # 7.
Intercambio global.
PROCESADOR
Transacción
Usuario P1 Término
Tiempo
de espera mientras
El
usuario piensa e introduce
Un
nuevo comando.
P2
Termina
Swapping Transferir
P1 a
Mem. Auxiliar
P1 Una
vez finalizada
La
transacción del
P2 P2
se carga P1.
MEM.
AUX.
Si
se utiliza el método, se deben definir políticas para decidir cuáles programas
deben ser transferidos a la memoria auxiliar en un momento dado (por ejemplo
los que acaban de finalizar una transacción, los que llevan un determinado
tiempo de residencia en la memoria y los que piden más memoria que la
disponible en un sistema de memoria virtual), lo cual implica tener en cuenta
muchos factores con el fin de evitar que el número de programas transferidos
por unidad de tiempo sobrepase un cierto umbral, lo cual disminuirá
considerablemente el desempeño del sistema.
Asignación
por particiones.
Otro
método posible de distribuir la memoria entre los usuarios consiste en
dividirla y asignar una zona, o
partición, a cada programa activo. Para ello existen varios métodos, teniendo
en cuenta cuatro aspectos básicos de cualquier manejador de recursos en orden
de complejidad creciente.
·
Guardar información sobre
el recurso.
·
Decidir quien debe usar
el recurso, cuándo y cuánto.
·
Asignar el recurso.
·
Retirar el recurso.
El método más simple de asignación de memoria es:
Asignación sencilla: Que consiste en
asignar la memoria a un solo programa, el cual ocupa todo el espacio disponible
para el usuario. Así se administraba la memoria en las primeras computadoras y
se maneja en las computadoras monousuarios. Por ejemplo el Sistema IBM-OS/PCP,
CP/M Y MS-DOS.
Cuando
se utiliza este método una decisión que debe tomarse es la del sitio en donde
va a ser localizado el sistema operativo, en la parte alta o baja de la
memoria, según la Figura # 8.
0 ALTERNATIVA
1 ALTERNATIVA 2 0
SISTEMA
ZONA OPERATIVO
DEL
USUARIO
ZONA
DEL
USUARIO
SISTEMA
OPERATIVO
DIRECCION
MAXIMA DE
DIRECCION MEMORIA MEMORIA
MEMORIA
MAXIMA
DE MEMORIA
Figura
# 8. Posibles formas de colocar el
sistema operativo en un sistema de asignación sencilla.
La
ventaja de la segunda alternativa sobre la primera es que no es necesario
relocalizar al sistema operativo si se aumenta la capacidad de la memoria.
Un
gran problema de la asignación sencilla es su falta de eficiencia, pues no solo
hace un mal uso del procesador (ya que no tiene un solo programa en la
memoria), si no de la memoria pues usualmente los usuarios no ocupan todo el
espacio disponible.
Particiones
fijas.
Otra forma posible de asignar a la memoria es por zonas de longitud fija. En
este caso se distribuye el espacio disponible para los usuarios en bloques de
tamaño fijo (particiones). Figura #
9.
SISTEMA
OPERATIVO
USUARIO
1
USUARIO
2
. .
USUARIO
N
MEMORIA
Asignación
de particiones múltiples.
En un sistema de multiprogramación, varios
procesos residen en memoria y el CPU conmuta rápidamente entre ellos. El
problema de la administración de memoria consiste en asignar memoria a los
distintos procesos que esperan en la cola de entrada para ser transferidos a
memoria.
Uno
de los esquemas más sencillos para la asignación de memoria consiste en
dividirla en varias particiones de tamaño fijo. Cada partición puede contener
exactamente un proceso. De esta forma, el nivel de multiprogramación está
limitado por el número de particiones.
Cuando una partición está libre, se selecciona un proceso de la cola de
entrada y se carga en la partición libre; cuando el proceso termina, la
partición esta disponible para otro.
Este
esquema se empleo originalmente en el sistema operativo (llamado MFT) de la
computadora IBM OS/360,
pero ya no se utiliza. Este esquema que se describe es una
generalización del esquema de particiones fijas y se usa sobre todo en entornos
de procesamiento por lotes.
Esquema
básico.
El
sistema operativo conserva una tabla que indica qué partes de la memoria están
disponibles y cuáles están disponibles y cuales están ocupadas. Inicialmente
toda la memoria está disponible para los procesos de usuario, y se considera
como un gran bloque de memoria disponible, o un hueco. Cuando llega un proceso
y necesita memoria, se busca un hueco de tamaño suficiente para ese proceso. Si
lo encontramos, sólo asignamos la cantidad de memoria necesaria, quedando
disponible el resto para satisfacer solicitudes ulteriores.
Por
ejemplo, tenemos 2560K de memoria disponible y un sistema operativo residente
de 400K. Esta situación deja 2160K para los procesos de usuario: Figura # 10.
0 Cola de trabajos
Sistema
Operativo Proceso Memoria Tiempo de CPU
400K P1 600K 10
P2 1000K 5
P3 300K 20
2160K P4 700K 8
P5 500K 15
2560K
Figura #
10. Ejemplo de disponibilidad de
memoria.
A
partir de la cola de entrada que se presenta en la figura anterior, así como
una planificación de trabajos PEPS, podemos asignar memoria de inmediato a los
procesos P1,P2 Y P3, creando el mapa de memoria de la figura 11(a). Tenemos un hueco de 260K que no puede usar
ninguno de los procesos restantes de la cola de entrada. Utilizando un
algoritmo de planificación circular del CPU, con un cuanto de una unidad de
tiempo, el proceso P2 terminará en el instante 14, liberando su asignación de
memoria. Esta situación se ilustra en la figura 11(b). Entonces volvemos a la cola de trabajo e
iniciamos el siguiente proceso, P4, obteniendo el mapa de memoria de la figura 11(c). El proceso P1 terminará
en el instante 28 y producirá la situación que se presenta en la figura 11(d);
luego se inicia el proceso P5, que da como resultado la figura 11(e).
Este
ejemplo ilustra varios puntos. En general, en cualquier momento hay un conjunto de huecos de distintos tamaños
y dispersos por toda la memoria. Cuando llega un proceso y necesita memoria,
buscamos en este conjunto un hueco con el tamaño suficiente para el proceso. Si
el hueco es demasiado grande, se divide en dos: una parte se asigna al proceso
que llega y la otra se devuelve al conjunto de huecos. Cuando termina un
proceso, libera su bloque de memoria, el cual se coloca de nuevo en el conjunto
de huecos. Si el nuevo hueco es adyacente a otros, los fusionamos formando uno
mayor. Al llegar a ese punto, necesitaríamos comprobar si hay procesos
esperando memoria y si esta nueva memoria liberada y recombinada puede
satisfacer las solicitudes de algunos de estos procesos. Figura # 11.
Figura #
11. Asignación de memoria y planificación a largo plazo.
Se
trata de una aplicación específica del problema general de asignación
dinámica de almacenamiento, es decir cómo satisfacer una solicitud de
tamaño n a partir de una lista de huecos libres. Existen muchas solicitudes
para este problema. Se busca en el conjunto de huecos para determinar cuál es
el mejor hueco para la asignación. Las estrategias de primer ajuste, mejor ajuste, y
peor ajuste son las más comunes para seleccionar un hueco libre de un
conjunto de huecos disponibles.
Primer ajuste. Asignar el primer hueco que tenga el tamaño
suficiente. La búsqueda puede comenzar en el inicio del conjunto de huecos a
partir de donde termino la búsqueda del primer hueco anterior. Podemos dejar de
buscar en el momento en que encontremos un hueco libre de tamaño suficiente.
·
Mejor ajuste. Asignar el hueco más
pequeño que tenga el tamaño suficiente. Debemos recorrer toda la lista, a menos
que ésta se mantenga ordenada por tamaño. Esta estrategia produce el hueco
sobrante más pequeño.
·
Peor ajuste. Asignar el hueco más
grande. Una vez más, debemos buscar en toda la lista, a menos que esté ordenada
por tamaño. Esta estrategia produce el hueco sobrante más grande, el cual puede
ser más útil que el hueco sobrante más pequeño producido por la estrategia del
mejor ajuste.
El
primer ajuste como el mejor ajuste son los mejores que el peor ajuste en cuanto
a la reducción del tiempo y de la utilización del almacenamiento. Ni el primer
ajuste ni el mejor ajuste son definitivamente superiores uno respecto al otro
en relación con la utilización del almacenamiento, pero por lo general el
primer ajuste es más rápido.
Estos
algoritmos padecen fragmentación externa: conforme los procesos se cargan y
extraen de la memoria, el espacio de memoria libre se divide en pequeños
pedazos.
La
fragmentación externa se presenta cuando el espacio de memoria es suficiente para
atender una solicitud, pero no es contiguo; el almacenamiento está fragmentado
en varios huecos pequeños. Dependiendo de la cantidad total de memoria y del
tamaño promedio de los procesos, la fragmentación externa puede ser un problema
mayor o menor.
Compactación.
Una solución para el problema de la
fragmentación externa es la compactación. El objetivo consiste en desplazar el
contenido de la memoria para colocar junta toda la memoria libre en un solo
bloque de gran tamaño. Por ejemplo el siguiente mapa de memoria de la Figura # 12, que puede compactarse.
Figura #
12. Compactación.
Los
tres huacos de 100K, 300K y 260K pueden compactarse en un hueco de 660K. La
compactación no siempre es posible. En la figura 12 se han movido los procesos
P4 y P3. Para que estos procesos puedan ejecutarse en sus nuevas posiciones,
hay que relocalizar todas las
direcciones internas. Si la relocalización
es estática y se efectúa durante el ensamblado, o la carga, la
compactación sólo es posible si la relozalización es dinámica y se efectúa en
el momento de la ejecución.
Estrategias de
Administración del Almacenamiento
Están dirigidas a la obtención del mejor uso
posible del recurso del almacenamiento principal.
Se dividen en las siguientes categorías:
Las “estrategias de
búsqueda” están relacionadas con el hecho de cuándo obtener el siguiente
fragmento de programa o de datos para su inserción en la memoria principal.
En la “búsqueda por demanda” el siguiente
fragmento de programa o de datos se carga al almacenamiento principal cuando
algún programa en ejecución lo referencia.
Se considera que la “búsqueda anticipada”
puede producir un mejor rendimiento del sistema.
Las “estrategias de colocación” están
relacionadas con la determinación del lugar de la memoria donde se colocará
(cargará) un programa nuevo.
Las “estrategias de reposición” están
relacionadas con la determinación de qué fragmento de programa o de datos
desplazar para dar lugar a los programas nuevos.
1.4
Concepto de memoria
virtual.
La memoria
virtual es una técnica de gestión que, combinando hardware y software, permite
la ejecución de programas parcialmente cargados en memoria real.
Esta
forma de trabajar aporta ventajas importantes:
·
Si los programas se pueden ejecutar por partes, la memoria lógica
puede ser mayor que la real disponible.
·
Puesto que cada programa ocupa menos memoria real se puede elevar
el índice de multiprogramación, y por tanto, la eficiencia del sistema se
incrementa.
·
Al cargar menos cantidad de cada programa, se necesitan menos
operaciones de E/S para las operaciones de carga e intercambio de los mismos.
Las
diferentes partes de un programa se van cargando en memoria a medida que se
necesitan, y por ello, esta técnica debe considerar tres aspectos importantes:
Carga: Las particiones del programa se
cargan cuando se necesitan (petición de
Pagina)
o bien se pueden cargar por adelantado (anticipación o
prepaginación).
Colocación: Los sistemas de memoria virtual que
utilicen segmentación deben decidir, al
cargar
un nuevo segmento, si lo hacen en el hueco más adecuado o bien en el
primero
posible.
Sustitución: La norma será que toda la memoria real
esté ocupada, y cuando se necesite
cargar
una nueva parte de un programa habrá que reemplazar alguna de las
existentes.
Es importante definir la selección de la parte a reemplazar.
Está técnica
es difícil de llevar a la practica. Los sistemas que la utilizan son complejos,
pero a la vez, deben ser muy eficientes. De lo contrario, la ejecución de los
programas puede empeorar notablemente.
Hay
dos motivaciones principales para la introducción de la memoria virtual:
liberarse de las restricciones físicas y hacer un mejor uso de los recursos de
la máquina.
Las
dos principales limitaciones que tiene la memoria física de una computadora son
su tamaño y su unidimencionalidad. La primera de ellas hace que no se puedan
correr programas más grandes que la memoria principal, o que para hacerlo se
requieran mecanismos sofisticados e incómodos para el usuario. La segunda
constituye un nuevo “lecho de procusto”, pues forza a representar en forma
unidimensional estructuras que no lo son.
La
memoria virtual permite hacer un mejor uso de los recursos de la máquina, pues
hace posible cargar en la memoria más programas de los que se pueden cargar en
un sistema tradicional y con esto la memoria y el procesador se utilizan más
eficientemente. La idea en este caso consiste en no cargar todas las partes de los programas sino
únicamente las que se necesitan, y hacer esto en forma automática (por eso se dice que la memoria virtual es un
sistema de recubrimiento automático).
Otro
componente que un sistema de memoria virtual debe manejar, es la memoria auxiliar. Los problemas típicos
que deben ser resueltos en él son los de asignación, migraciones y
políticas de servicio en las diferentes unidades de soporte de
paginación.
El
primero se refiere a la distribución de la memoria auxiliar entre las
diferentes partes del espacio virtual.
.
El tiempo de transferencia de las páginas incide directamente en la eficiencia
del sistema.
.
la información a guardar puede tener características especiales (por ejemplo
bloques de tamaño fijo, como las
páginas).
.
Debe manejarse una tabla de correspondencia entre espacio virtual y la memoria
auxiliar.
La
asignación del espacio difiere considerablemente si se trata de un sistema con paginación (y eventualmente
segmentación) o con segmentación pura.
En un sistema
con paginación los bloques son de longitud fija y por consiguiente su manejo es
más sencillo pues cualquier bloque puede albergar cualquier página del espacio
virtual. Las decisiones que se deben tomar en estos casos son:
* Si
la asignación de los bloques a las páginas se hace estática o dinámicamente, y
si se utilizan diferentes dispositivos físicos (eventualmente de distintos
tipos) como soporte de paginación (y en ese caso, cómo manejarlos, cómo hacer
transferencias entre ellos, etc.)
* La
representación del espacio disponible (y del asignado) se puede hacer
fácilmente utilizando una cadena de bits (con un bit asociado a cada página de
la memoria) pues los bloques son de longitud fija.
* En
un sistema con segmentación pura la administración de la memoria auxiliar es
más compleja pues se deben manejar bloques de longitud variable, con todos los
problemas que ello implica: representación de bloques libres, búsqueda de un
bloque adecuado, etc. Los sistemas con segmentación pura deben entonces
resolver los mismos problemas de los sistemas con paginación, más el del manejo
de bloques de longitud variable.
Deducción a la Organización del
Almacenamiento Virtual
“Almacenamiento virtual ” significa
la capacidad de direccionar un espacio de almacenamiento mucho mayor que el
disponible en el almacenamiento primario de determinado sistema de computación
Esta tecnología apareció en 1960 en la Universidad
de Manchester (Inglaterra), en el sistema “Atlas”.
Los métodos más comunes de implementación
son mediante:
Las direcciones
generadas por los programas en su ejecución no son, necesariamente, aquellas
contenidas en el almacenamiento primario (memoria real), ya que las direcciones
virtuales suelen seleccionarse dentro de un número mucho mayor de
direcciones que las disponibles dentro del almacenamiento primario.
La evolución en las organizaciones de
almacenamiento puede resumirse como sigue:
Conceptos Básicos de
Almacenamiento Virtual
La clave del concepto de memoria (almacenamiento)
virtual esta en la disociación:
Los principales
conceptos son los siguientes:
Los procesos hacen
referencia a direcciones virtuales pero éstas deben
ejecutarse en el almacenamiento real:
Existen varios medios
para asociar las direcciones virtuales con las reales
Los mecanismos de “traducción dinámica de
direcciones” (dat) convierten las direcciones virtuales en reales al
ejecutarse el proceso.
Las direcciones contiguas dentro del espacio de
direcciones virtuales de un proceso no tienen por qué ser contiguas dentro del
almacenamiento real, a esto se denomina “contigüidad artificial ”
1.5
MECANISMOS
DE RELOCALIZACION
Existen dos mecanismos
de relocalización:
Relocalización
estática.
La relocalización estática se
inicializa desde el momento de encender el equipo de cómputo.
Relocalización dinámica.
La relocalización dinámica efectúa la
relocalización cada vez que lo requiere.
1.6
IMPLANTACION
DE MECANISMOS DE MEMORIA VIRTUAL
Base Límite.
Como
varios procesos pueden residir en memoria al mismo tiempo, ésta se debe
proteger. Esta protección es proporcionada utizando registros base y límite. Figura # 13.
Lo
que se necesita para separar el espacio de memoria de cada programa es la
capacidad de determinar el intervalo de direcciones legales a las que pueda
tener acceso un programa, y proteger la memoria fuera de ese espacio.
0
monitor
256000
trabajo
1
300040 300040 registro base
trabajo
2
420940 120900 registro límite
trabajo
3
880000
trabajo
4
1024000
Figura #
13. Un registro base y un registro límite definen un espacio de direcciones.
El
registro base contiene la menor dirección de memoria física permitida, y el
registro límite el tamaño del intervalo.
Por
ejemplo, si el registro base contiene 300040 y el registro límite es 120900,
entonces el programa puede tener acceso legalmente a todas las direcciones
entre 300040 y 420940, inclusive.
El
hardware del CPU logra esta protección comparando cada una de las direcciones
generadas en modo usuario con los registros.
Existen
tres formas básicas de direccionamiento utilizadas en los sistemas de memoria
virtual:
·
Segmentación.
·
Paginación.
·
Segmentación – Paginación.
Segmentación.
La
segmentación es una técnica distinta de gestión de memoria que pretende
acercarse más al punto de vista del usuario. Este esquema permite que el
usuario vea la memoria en modulos.
El
espacio de direcciones lógicas es una colección de segmentos y c/u de ellos
tiene un nombre del segmento y el desplazamiento. El sistema se encarga de
construir automáticamente los segmentos. La segmentación de un programa
la realiza el compilador y en ella cada dirección lógica se expresará mediante
dos valores: número de segmento(s) y desplazamiento (d). Calculo de la
segmentación. Figura # 14.
Figura #
14. Ejemplo de segmentación.
Mecanismo utilizado en sistemas con segmentación.
Figura
# 15.
s d
dirección virtual
s
L dir
dir
Tabla
de segmentos
Dirección en Memoria
real
Figura # 15. Segmentación.
La
dirección virtual se compone de segmento y desplazamiento. La primera sirve
para indizarse dentro de la llamada tabla de segmentos, en donde se encuentra
la dirección del segmento correspondiente. A ésta se le suma el desplazamiento
para obtener la dirección en la memoria real. Dentro de cada entrada de la
tabla de segmentos se encuentra también un campo que indica la longitud del
segmento, el cual permite verificar que no se hagan referencias fuera del
segmento. En caso de que esto ocurra se produce una interrupción.
Ventaja:
. Evita la fragmentación interna.
Desventaja:
. Conduce a tener fragmentación externa.
. El manejo de bloques de longitud
variable es muy engorroso tanto en la memoria
principal como auxiliar.
Paginación.
Se
considera como la transformación de bloques de tamaño físico. La memoria física
se divide en bloques de tamaño fijo llamados frames, y la memoria lógica
también es dividida en bloques del mismo tamaño. Llamadas páginas, el disco
también se divide en bloques del mismo tamaño que los frames.
El
sistema operativo mantiene internamente una tabla de paginas donde relaciona
cada pagina cargada en memoria con el frame que la contenga es decir, su
dirección inicial en memoria real. Figura
# 16. Calculo de una
segmentación.
MEMORIA LOGICA TABLA DE PAG. MEMORIA
FISICA
P1 1 F1 F0
P2 2 F4 F1 P1
P3 3 F3 F3 P3
P4 4 F7 F4 P2
F5
F6
F7 P4
Figura
# 16. Asignación de paginas.
Cada
dirección que genere el procesador será interpretada y dividida en dos
componentes, un número de página (p) y un desplazamiento en la página (d).
Utilizando p como índice, gestor de memoria del sistema correrá la tabla de
páginas hasta localizar dicha página, y a continuación sumará d a la dirección
de carga correspondiente, obteniendo así la dirección real adecuada. Figura
# 17.
Dirección Virtual
P d
P
Dir
*
Tabla de paginas dir.
Dirección
En
Mem. Real.
Mem. Real
Figura # 17. Paginación.
Estructura
del mecanismo de traducción de direcciones en un sistema con paginación pura.
En
este caso no existe campo de longitud en la tabla, llamada ahora tabla de
paginas. Esto hace que los bloques denominados paginas tengan longitud fija, e
igual a la del máximo posible. La gran ventaja de este método es que evita la
fragmentación externa pues los bloques en la memoria real son de longitud fija
y por consiguiente en cualquiera de ellos puede colocarse la pagina de la
memoria virtual.
Lo anterior
presenta dos inconvenientes:
·
Como
las paginas son de longitud fija y arbitrarias, no corresponde ahora a ninguna
entidad lógica y por consiguiente no puede asociársele ninguna protección:
·
Al
asignar a un programa una cantidad entera de páginas de longitud fija se
produce la fragmentación interna, la cual consiste en que un programa no puede
utilizar todo el espacio que le sea asignado.
Segmentación
– Paginación.
Es
la combinación de la segmentación y la
paginación. Figura # 18.
DIRECCION
VIRTUAL
S p d
S
L dir P
Dir
TABLA
DE SEG.
TABLA DE PAG. d
DIRECCION
EN LA MEM. REAL.
Figura # 18. Segmentación –Paginación.
Las
direcciones virtuales se componen de 3 partes:
segmento, página y
desplazamiento.
·
El
segmento sirve para indizarse en una tabla de segmentos en la cual se encuentra
la longitud y dirección de la tabla de páginas.
·
La
página sirve para indizarse en la tabla de páginas, en donde se encuentra la dirección
de la página correspondiente; se puede llegar a la dirección en memoria real.
s diferentes organizaciones
de almacenamiento virtual generalmente implementadas son [7, Deitel]:
Las
estrategias para la administración de sistemas de almacenamiento virtual
condicionan la conducta de los sistemas de almacenamiento virtual que operan
según esas estrategias.
Se consideran
las siguientes estrategias:
En los sistemas de “segmentación” un
programa y sus datos pueden ocupar varios bloques separados de almacenamiento
real (ver Figura 3.26 [7,
Deitel]).
Los bloques:
Se complica la
protección de bloques de memoria de un proceso de usuario.
Es más difícil limitar el rango de acceso de
cualquier programa [7,
Deitel].
Un esquema posible de protección es el uso de claves
de protección del almacenamiento (ver Figura 3.27 [7,
Deitel]):
Una dirección virtual es un par ordenado v=(s,d)
(ver Figura 3.28 [7,
Deitel]):
Un proceso solo puede ejecutarse si su segmento
actual (como mínimo) está en el almacenamiento primario.
Los segmentos se transfieren del almacenamiento
secundario al primario como unidades completas.
Un nuevo segmento puede ser colocado en una serie
disponible de posiciones contiguas del almacenamiento primario de tamaño
suficiente para alojar al segmento.
La traducción dinámica de direcciones utiliza una “tabla
de mapa de segmentos”.
Control de
Acceso en Sistemas de Segmentación
Se le otorga a
cada proceso ciertos derechos de acceso a todos los segmentos y se le niega
completamente el acceso a muchos otros.
Si un proceso
tiene “acceso de lectura” a un segmento, puede obtener cualquier
elemento de información contenido en ese segmento.
Si un proceso tiene
“acceso de escritura” a un segmento, puede modificar cualquier contenido
del segmento y puede introducirle información adicional, incluso destruir toda
la información del segmento.
Un proceso con “acceso
de ejecución” de un segmento puede ejecutarlo como si fuera un programa.
Un proceso con “acceso
de adición” puede escribir información adicional al final del segmento,
pero no puede modificar la información existente.
En base a los “tipos
de control de acceso” indicados pueden crearse distintos “modos de
control de acceso”.
Ejemplos de
combinación de los accesos de lectura, escritura y ejecución para producir
modos de protección útiles se dan en la Tabla 3.1 y en la Tabla 3.2 [7,
Deitel].
|
Modo |
Lectura |
Escritura |
Ejecución |
Explicación |
|
0 |
N |
N |
N |
No
hay permiso de acceso |
|
1 |
N |
N |
S |
Solo
ejecución |
|
2 |
S |
N |
N |
Solo
lectura |
|
3 |
S |
N |
S |
Lectura
/ ejecución |
|
4 |
S |
S |
N |
Lectura
/ escritura pero no ejecución |
|
5 |
S |
S |
S |
Acceso no limitado |
|
Tabla 3.1: Ejemplo de
combinación de accesos. |
||||
|
Modo |
Aplicación |
|
0 |
Seguridad |
|
1 |
Un
programa disponible a los usuarios, que no pueden copiarlo ni modificarlo,
pero sí ejecutarlo |
|
2 |
Recuperación
de información |
|
3 |
Un
programa puede ser copiado o ejecutado, pero no puede ser modificado |
|
4 |
Protege
los datos contra un intento erróneo de ejecutarlos |
|
5 |
Este acceso se concede
a los usuarios de confianza |
|
Tabla 3.2: Ejemplo de
aplicaciones de la combinación de accesos. |
|
Compartimiento
en un Sistema de Segmentación
Una de las ventajas
de la segmentación sobre la paginación es que se trata más de un hecho
lógico que físico:
Dos
procesos pueden compartir un segmento con solo tener entradas en sus tablas generales
que apunten al mismo segmento del almacenamiento primario.
EJERCICIOS
INTERCAMBIO DE MEMORIA
Multiprogramación con particiones variables.
|
|
|
|
|
C |
|
C |
|
|
|
|
|
E |
E |
|||||
|
B |
B |
B |
B |
|||||
|
A |
A |
|
|
D |
||||
|
S.O. |
S.O. |
S.O. |
S.O. |
S.O. |
Se le da prioridad a los procesos más grandes, y se pueden eliminar dos o más procesos dependiendo del espacio que se necesite.
Administración con mapa de bits.
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
0
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
16 17 18
19 20 21
22 23 24 |
|||||||||||||||||||||||||
11111100
11111111
10000111
10000000
Administración con listas ligadas.
P = Proceso.
H = Espacios vacíos de memoria (huecos).
|
P |
0 |
6 |
|
H |
6 |
2 |
|
P |
8 |
9 |
|
H |
17 |
4 |
|
|
|
|
|
|
|
|
B |
|
Pila B |
|
|
|
A |
|
S.O. |
|
A |
X |
B |
|
A |
X |
|
|
|
||||||
|
A |
X |
|
|
|
X |
|
|
|
||||||
|
|
X |
|
|
|
|
|
Administración con sistemas asociados.
|
|
|
|
||||
|
0 |
|
0 |
1 |
0 |
|
1 |
|
1 |
|
0 |
0 |
1 |
1 |
|
|
|
1 |
1 |
0 |
1 |
||
|
3 |
|
0 |
0 |
0 |
|
1 |
|
4 |
1 |
0 |
0 |
|
1 |
|
|
5 |
|
0 |
1 |
1 |
1 |
|
|
6 |
|
0 |
0 |
0 |
|
0 |
|
7 |
|
0 |
0 |
0 |
|
0 |
|
8 |
|
0 |
0 |
0 |
|
0 |
|
9 |
|
1 |
0 |
1 |
1 |
|
|
10 |
0 |
0 |
0 |
|
0 |
|
|
11 |
1 |
1 |
1 |
1 |
||
|
12 |
|
0 |
0 |
0 |
|
0 |
|
13 |
|
0 |
0 |
0 |
|
0 |
|
14 |
|
0 |
0 |
0 |
|
0 |
|
15 |
|
0 |
0 |
0 |
|
0 |
(A) FIFO con tres marcos de página, (B) FIFO con cuatro marcos de página. Las letras P muestran cuales referencias provocan fallas de página.
Todos los marcos están vacíos al
principio
|
|
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
4 |
|
|
|
Página más reciente |
|
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
4 |
|
|
|
|
|
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
|
|
Página más antigua |
|
|
|
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
|
|
Fallo de página |
|
P |
P |
P |
P |
P |
P |
P |
|
|
P |
P |
P |
|
|
|
||||||||||||||
|
|
|
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
4 |
|
Página más reciente |
|
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
4 |
|
|
|
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
|
|
|
|
|
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
|
|
Página más antigua |
|
|
|
|
0 |
1 |
2 |
3 |
3 |
3 |
4 |
0 |
1 |
|
|
P |
P |
P |
P |
|
|
P |
|
|
P |
P |
|
|
|
|
|
||||||||||||
|
Cadena de referencias |
0 |
2 |
1 |
3 |
5 |
4 |
6 |
3 |
7 |
4 |
7 |
3 |
3 |
5 |
5 |
3 |
1 |
1 |
1 |
7 |
2 |
3 |
4 |
1 |
||
|
Memoria Física |
1 |
|
0 |
2 |
1 |
3 |
5 |
4 |
6 |
3 |
7 |
4 |
7 |
3 |
3 |
5 |
5 |
3 |
1 |
1 |
1 |
7 |
2 |
3 |
4 |
1 |
|
2 |
|
|
0 |
2 |
1 |
3 |
5 |
4 |
6 |
3 |
7 |
4 |
7 |
7 |
3 |
3 |
5 |
3 |
3 |
3 |
1 |
7 |
2 |
3 |
4 |
|
|
3 |
|
|
|
0 |
2 |
1 |
3 |
5 |
4 |
6 |
3 |
3 |
4 |
4 |
7 |
7 |
7 |
5 |
5 |
5 |
3 |
1 |
7 |
2 |
3 |
|
|
4 |
|
|
|
|
0 |
2 |
1 |
3 |
5 |
4 |
6 |
6 |
6 |
6 |
4 |
4 |
4 |
7 |
7 |
7 |
5 |
3 |
1 |
7 |
2 |
|
|
Memoria Virtual |
5 |
|
|
|
|
|
0 |
2 |
1 |
1 |
5 |
5 |
5 |
5 |
5 |
6 |
6 |
6 |
4 |
4 |
4 |
4 |
5 |
5 |
1 |
7 |
|
6 |
|
|
|
|
|
|
0 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
6 |
6 |
6 |
6 |
4 |
4 |
5 |
5 |
|
|
7 |
|
|
|
|
|
|
|
0 |
0 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
6 |
6 |
6 |
6 |
|
|
8 |
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
Fallo de página |
|
P |
P |
P |
P |
P |
P |
P |
P |
|
P |
|
|
|
|
P |
|
|
P |
|
|
|
P |
|
P |
P |
Distancias
de la cadena 
Si el número a recorrer se encuentra en la memoria virtual produce un fallo de página; si se encuentra en la memoria física no produce fallo de página.
|
Cadena de referencias |
0 |
3 |
2 |
4 |
5 |
4 |
6 |
3 |
7 |
4 |
7 |
4 |
4 |
5 |
5 |
4 |
1 |
1 |
1 |
6 |
2 |
3 |
4 |
1 |
||
|
Memoria Física |
1 |
|
0 |
3 |
2 |
4 |
5 |
4 |
6 |
3 |
7 |
4 |
7 |
4 |
4 |
5 |
5 |
4 |
1 |
1 |
1 |
6 |
2 |
3 |
4 |
1 |
|
2 |
|
|
0 |
3 |
2 |
4 |
5 |
4 |
6 |
3 |
7 |
4 |
7 |
7 |
4 |
4 |
5 |
4 |
4 |
4 |
1 |
6 |
2 |
3 |
4 |
|
|
3 |
|
|
|
0 |
3 |
3 |
3 |
5 |
4 |
6 |
3 |
3 |
3 |
3 |
7 |
7 |
7 |
5 |
5 |
5 |
4 |
1 |
6 |
2 |
3 |
|
|
4 |
|
|
|
|
0 |
2 |
2 |
3 |
5 |
4 |
6 |
6 |
6 |
6 |
3 |
3 |
3 |
7 |
7 |
7 |
5 |
4 |
1 |
6 |
2 |
|
|
Memoria Virtual |
5 |
|
|
|
|
|
0 |
0 |
2 |
2 |
5 |
5 |
5 |
5 |
5 |
6 |
6 |
6 |
3 |
3 |
3 |
7 |
5 |
4 |
1 |
6 |
|
6 |
|
|
|
|
|
|
|
0 |
0 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
6 |
6 |
6 |
3 |
7 |
5 |
5 |
5 |
|
|
7 |
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
2 |
2 |
2 |
3 |
7 |
7 |
7 |
|
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
Fallo de página |
|
|
P |
P |
P |
P |
P |
|
P |
P |
P |
|
|
|
|
P |
|
|
P |
|
|
P |
P |
P |
P |
P |
Distancias de la cadena
EJERCICIOS:
a) Administración con mapa de bits y administración con lista ligada.
A – 4 D – 2 G – 3 J – 1 M
– 2
B – 3 E – 1 X – 1 K – 4 X – 1
X – 1 F – 2 X – 1 L
– 3 I – 1
|
|
|
|
A |
|
|
B |
|
|
D |
E |
|
F |
|
|
G |
|
|
J |
|
|
|
K |
|
|
L |
|
M |
|
I |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
|
|
|
|
0 |
4 |
|
P |
4 |
3 |
|
H |
7 |
1 |
|
P |
8 |
2 |
|
P |
10 |
1 |
|
P |
11 |
2 |
|
P |
13 |
3 |
|
H |
16 |
1 |
|
H |
17 |
1 |
|
P |
18 |
1 |
|
P |
19 |
4 |
|
P |
23 |
3 |
|
P |
26 |
2 |
|
H |
28 |
1 |
|
P |
29 |
1 |
11111110 à 254
Mapa de bits
11111111 à 255
00111111 à 63
11110100 à 244
b) Si la CPU asigna 12 segundos en ejecución a cada proceso y 48 segundos en espera. ¿Cuántos minutos tardará la CPU en cada proceso?
A à 5 min.
B à 4 min.
C à 3 min.
c) Convertir direcciones virtuales a direcciones físicas
·
12120
0010111101011000 0010=2
110111101011000 28504
·
24420
0101111101100100 0101=5
011111101100100 16228
·
32120
0111110101111000 0111=7
000110101111000 3448
·
8125
0001111110111101 0001=1
001111110111101 8125
·
20430
0100111111001110 0100=4
100111111001110 20430
·
48570
1011110110111010 1011=11
111110110111010 23994
·
56300
1101101111101100 1101=13
000101111101100 3052
PAGINA PRINCIPAL
