En realidad, examinando programas típicos reales,
se llega a la conclusión de que en muchos casos no es necesario cargar el programa
completo en memoria. Por ejemplo.
Algunos programas tienen rutinas para manejar condiciones de error. Dado que estos problemas casi nunca ocurren, el código de esta rutina es rara vez ejecutado.
Los arreglos,
listas y tablas, son generalmente declarados con
tamaños mucho mayores al que llegan a necesitar, por lo que se
desperdicia memoria.
Ciertas opciones
de algunos programas rara vez son ejecutados.
Aún en el caso en el que el programa entero sea ejecutado,
es posible que no sea necesario cargarlo completo a un mismo tiempo.
La habilidad de ejecutar un programa que está parcialmente
en memoria puede traer muchos beneficios. Por ejemplo.
Un programa
no estaría limitado por la cantidad de memoria
RAM disponible. Los usuarios podrían escribir programas con un
número de instrucciones muy grande.
Dado que cada
usuario podría tomar menos
memoria RAM, más usuarios podrían correr al mismo tiempo, elevando el grado
de multiprogramación y por lo tanto mejorando la utilización
del CPU.
En general, correr un programa que no está enteramente
en memoria, beneficiaría tanto al sistema como al usuario.
Existen dos técnicas que permiten realizar esto:
Overlays y Memoria Virtual.
Es una técnica que permite a un programa ser más
grande que
la cantidad de memoria otorgada a él, sobreponiendo
en una misma área de memoria dos o más subprogramas que no se usan al mismo
tiempo, ni se llaman entre sí.
Cuando se escribe un programa con overlays, el lenguaje
que
Considere dos subprogramas escritos en pascal: Procedure
uno y procedure dos, los cuales son llamados por un programa principal cuyo
nombre es prueba. El programa completo nos queda:
PROGRAM
PRUEBA;
VAR (*Variables del programa prueba*)
-
-
PROCEDURE UNO;
BEGIN
-
-
END;
PROCEDURE
DOS;
BEGIN
-
-
END;
BEGIN (*Programa prueba*)
-
-
-
END. (*Programa prueba*)
El archivo compilado queda formado como se ilustra
en la
Si por ejemplo, el código del programa principal
(prueba) ocupa 100 K y los procedimientos uno y dos ocupan 30 y 50 K respectivamente,
y la memoria asignada al usuario es de solo 150 K, es obvio que el programa
no podrá ser corrido.
PROGRAM PRUEBA;
VAR
(*variables del programa prueba*)
-
-
-
OVERLAY PROCEDURE
UNO;
BEGIN
-
-
-
END;
OVERLAY PROCEDURE
DOS;
BEGIN
-
-
-
END;
BEGIN (*Programa prueba*)
-
-
END. (*Programa prueba*)
Lo anterior crea el mismo archivo prueba pero sin
el códigode los dos subprogramas y un archivo más llamado prueba.000 (archivo
de overlay) con el contenido de ambos subprogramas.
El programa es cargado a memoria colocando el código
del archivo prueba, y dejando un hueco reservado para cargar el código de un
subprograma u otro contenido en el archivo de overlay. Esto se ilustra en la
siguiente figura.
El área de overlay es del tamaño del más grande de
los overlays. Por lo tanto, al correr el programa, sólo el código de uno de
los subprogramas es cargado a la vez en la misma área de memoria, permitiendo
correr el programa como si estuviera cargado en memoria totalmente. Tiene la
desventaja que el programa corre un poco más lento por tener que ir a disco
(principalmente si es diskette).
Es una técnica que permite ejecutar programas que
no están enteramente cargados en memoria, dando al usuario la impresión de que
tiene una memoria mucho mayor a la memoria física de la máquina, por lo que
puede escribir pogramas muy extensos. La memoria virtual en paginación está
constituida por dos subsistemas: El demandador de páginas y el algoritmo de
remplazo de página.
DEMANDADOR DE PAGINAS
En el
demandador de páginas, en lugar de cargar en memoria todas las páginas que componen
el programa, como se hacía en el equema de paginación visto anteriormente, las
páginas se van cargando según lo vaya requiriendo la ejecución de éste; es decir,
que una página nunca será cargada a memoria a menos que
Sin embargo, cuando el CPU trata de usar una página
que no ha sido traída a memoria, traduce una dirección de usuario en una dirección
física utilizando la tabla de páginas, pero como esta dirección no tiene un
cuadro asociado, entonces la dirección es inválida y se genera un error abortando
el programa.
Para evitar este problema, el hardware de paginación
es modificado agregando un bit de validación. De esta manera, si una página
no ha sido traída a memoria, el bit es puesto a 1 ó inválido. Esto se ilustra
en la figura.
De esta manera, cuando se accesa la tabla de páginas, es posible saber si la página está en memoria ó no. Si la página no está cargada en memoria, en lugar de producir una interrupción al sistema operativo del tipo de dirección de memoria ilegal, la cual abortaría el programa, ahora se genera una interrupción de otro tipo indicando que la página no está en memoria. El manejador de esta interrupción procederá a cargar la página faltante y proseguirá la ejecución del programa. Esto se ilustra en la siguiente figura.
El procediminto se resume en los siguientes puntos.
1.- Primero checamos la tabla interna mantenida en
el bloque de control de proceso, para determinar si la referencia es un acceso
a memoria válido o inválido. Si fue inválido, abortar el programa.
2.- Si fue una referencia válida pero aún no hemos
traído la
3.- Encontrar un cuadro libre (buscando en la lista
de cuadros
4.- Hacer una operación de lectura para traer la
página deseada
5.- Cuando la lectura se haya completado, modificar
la tabla
6.- Restablecer la instrucción que fue interrumpida
por la página faltante. El proceso puede ahora accesar la página como si siempre
hubiera estado en memoria.
Hay que hacer notar que al generarse la interrupción,
es necesario guardar el estado del proceso interrumpido (registros, código de
condiciones, contador del programa)
en su PCB correspondiente, de tal
manera que el proceso pueda
ser restablecido después de haber traído la página faltante.
En el caso extremo, nosotros podemos empezar la ejecución
de un programa con cero páginas
en memoria. El
proceso inmediatamente generará una petición de página con la primera
instrucción. Después de que esta página sea traída, el programa continuará ejecutándose
y generando peticiones de páginas (como sea necesario) hasta que cada página
que sea necesaria esté en
Se ha dicho que uno de los principales beneficios
de no cargar completamente los programas, es que nos queda más memoria disponible
y por lo tanto más usuarios pueden ser cargados al mismo tiempo, aumentando
el grado de multiprogramación.
Por ejemplo si tenemos 40 cuadros de memoria física
y un programa que tiene 10 páginas pero solo usa realmente 5, podríamos cargar
hasta 8 programas similares en lugar de 4 si no tuviéramos memoria virtual.
Sin embargo, sí repentinamente los ocho programas
requirieran usar las 10 páginas completas se tendría una demanda de 80 cuadros
cuando solamente se tienen 40.
Aunque esta situación es poco probable, ésta llega
a ser muy factible cuando aumentamos el grado de multiprogramación, al punto
en que la memoria promedio de uso, se aproxima a la memoria física disponible.
Cuando esta situación se presenta, el sistema operativo
tiene varias opciones:
1.- Abortar el programa en cuestión. Sin embargo
dado que la idea de usar memoria virtual es beneficiar tanto al usuario como
al sistema, es obvio que ésta no es la mejor opción.
2.- Reducir el grado de multiprogramación, pasando
a disco a uno de los usuarios (swapping) y liberando así todos sus cuadros de
memoria que ocupaba. Esta es una buena solución más no la mejor.
3.- La mejor opción, es utilizar un algoritmo llamado
remplazo de página (page replacement).
ALGORITMO DE REMPLAZO DE PAGINA
El funcionamiento de este algoritmo es el siguiente:
Si no hay un cuadro libre, encontrar uno que no se
estéusando y desocuparlo escribiendo su contenido a disco, y reflejando el cambio
en la tabla de páginas para indicar que esa página no está más en memoria.
El cuadro libre puede ahora ser utilizado para cargar
la página faltante. Esto se ilustra en la siguiente figura.
Al introducir el algoritmo de remplazo de página,
la rutina del sistema operativo que sirve la interrupción de una página faltante
queda como sigue:
1.- Encontrar la localización en disco de la página
deseada.
2.- Encontrar un cuadro libre
Si hay un cuadro, entonces: usarlo
Sino: Usar un algoritmo de remplazo de página para encontrar un cuadro
víctima.
Escribir la página víctima al disco.
Actualizar la tabla de páginas para reflejar el cambio.
[Fin del condicional]
3.- Leer la página faltante y escribirla en
el cuadro libre.
Cambiar la tabla de páginas.
multiprogramación debe ser escogido adecuadamente.
La combinación del demandador de páginas con el remplazador
de páginas, es la manera en que comúnmente se implementa la memoria virtual,
la cual constituye una separación de la memoria lógica de
la memoria física. La memoria virtual puede ser mucho más grande que
la memoria física.
La memoria virtual también puede ser implementada
en sistemas de segmentación; sin embargo requiere de algoritmos de remplazo
más complejos.
Resulta más fácil implementar memoria virtual segmentada
a través de sistemas de segmentación paginada; es decir, los segmentos divididos
en páginas. De esta forma, el usuario ve un sistema segmentado, pero el S. O.
ve un sistema paginado, por lo que puede utilizar el algoritmo de remplazo de
página.
