En un sistema de multiprogramación la memoria debe ser compartida por varios procesos de cara a obtener una mayor utilización de los recursos del ordenador. Esto provoca que la gestión de la memoria se complique sustancialmente. En primer lugar, hay que llevar un recuento de las zonas de memoria ocupadas por los procesos. Así, cuando un nuevo proceso entre en la memoria se le asignará una zona que estaba libre. Otro problema a resolver viene dado por el hecho de que en el momento de escribir un programa no se sabe en qué zona de memoria se ubicará, siendo posible que durante la vida de un proceso éste cambie varias veces de emplazamiento. Habrá que tener en cuenta, también, la protección de las zonas de memoria ocupadas por los procesos, máxime en sistemas multiusuario donde los procesos pueden pertenecer a distintos usuarios.

En lo que resta de este tema, y en el tema siguiente, se estudiarán varias formas de gestión de la memoria utilizadas en sistemas de multiprogramación.

En un esquema de asignación de memoria contigua un proceso se ubica en su totalidad en posiciones consecutivas de memoria. Un ejemplo de este tipo de asignación es el utilizado en los sistemas de monoprogramación vistos previamente. En este apartados se estudian dos métodos de asignación contigua empleados históricamente en sistemas multiprogramados.

Esta forma de gestión consiste en dividir la memoria en varias zonas, pudiendo ser cada zona de un tamaño diferente. Esto se ilustra en la figura 6.3. El tamaño de las zonas podrá ser modificado eventualmente por algún usuario responsable de la administración del ordenador.

Los trabajos se traducían mediante compiladores y ensambladores absolutos, para ejecutarse en una partición específica. Una vez introducido un proceso en una partición, permanece en ella hasta su finalización. Si un trabajo se iniciaba, y la partición para la que estaba compilado estaba ocupada, tenía que esperar, aunque estuvieran libres otras particiones. Esto provoca una pérdida de eficiencia.

De cara a mejorar el rendimiento es preciso que un proceso se pueda cargar en cualquier partición. Para ello, los programas se escriben en términos de direcciones relativas a la dirección de comienzo de carga cero. Sin embargo, los programas no se cargan a partir de la dirección cero, esta circunstancia se debe resolver mediante la reasignación o reubicación, ¿cómo se realiza ésta ?. Una posible implantación viene proporcionada por el hardware. Existe un registro, denominado registro base, en el que el sistema operativo, dentro de la operación de cambio de proceso, escribe la dirección de memoria a partir de la cual se almacenó el proceso. Esta dirección coincidirá con la de comienzo de la partición en que reside, y forma parte de su descriptor(PCB). Cuando la CPU genera una dirección de memoria, ésta es transformada por el hardware antes de ser introducida en el bus del sistema. La transformación consiste en sumarle a la dirección el registro base.

Para clarificar esto, supóngase que la instrucción que actualmente ejecuta la CPU guarda el contenido del acumulador en la dirección relativa 100 de la memoria. Esta dirección, 100, (que podría, por ejemplo, guardar el contenido de una variable de otro proceso) es relativa a una dirección 0 de comienzo del programa. Si el programa se ha cargado en la posición 10000 de la memoria, el registro base contendrá el valor 10000. Cuando la CPU ejecuta la instrucción, genera la dirección 100 de memoria (la cual físicamente pertenece a otro proceso). Sin embargo, el hardware suma 10000 a este valor, introduciéndose 10100 en el bus del sistema, dirección que realmente ocupa la variable. Observe que con este esquema, si se quiere reubicar el proceso a otro lugar de la memoria, sólo hay que desplazarlo de lugar, y modificar el registro base con la nueva dirección de comienzo de carga.

Una solución software al problema de la reasignación consiste en modificar las instrucciones cuando el programa se carga en la memoria. Para que esto ocurra es preciso que el enlazador (el programa que a partir de los ficheros objeto genera un único objeto) incluya en el programa binario una lista que indique qué partes del programa son direcciones a reasignar, y cuáles no (constantes, códigos de operadores u otros elementos que no deban ser reasignados). Con esta solución, cada reubicación en la memoria implica una reasignación de las direcciones de memoria del programa.

Si se tiene el esquema hardware del registro base, para lograr la protección de las zonas de memoria basta con añadir un nuevo registro, denominado registro límite. Este registro guarda la última dirección de la partición, y forma también parte del PCB del proceso. El hardware, después de sumar el registro base a la dirección relativa, comprueba que la dirección obtenida no supere el valor del registro límite. Si se supera el valor, se está intentando acceder a una zona que no corresponde al proceso; en esta situación, el hardware genera una interrupción. El sistema operativo sirve a la interrupción, lo normal es que mande una señal al proceso por violación de memoria. Si el proceso no tiene definido atrapar esa señal, lo cual es lo más probable, se eliminará al proceso.

Cuando un proceso quiera ejecutar código del sistema operativo, por ejemplo, para realizar una E/S, no tiene acceso directo a las rutinas que tiene el sistema operativo en memoria para implementar dicha función, sino que debe realizar una llamada al sistema para no violar la protección. Este esquema es necesario, pues los programas de usuario tienen que avisar al sistema operativo de que le solicitan servicios (al hacer una llamada al sistema), el sistema operativo atenderá las peticiones si son correctas, o si pueden ser factibles en dicho momento (por ejemplo, no se asignará una impresora que está siendo utilizada por otro proceso). Los procesos de usuario no pueden llamar directamente al sistema operativo gracias a la protección de memoria.

Una última observación, al margen de la protección: cuando un proceso se introduce en una partición, lo más probable es que su tamaño no sea el mismo (es decir, sea algo menor) que el de la partición. Esto origina un problema de desperdicio de memoria conocido como fragmentación interna.

En este método se va asignando la memoria dinámicamente a los procesos, conforme se introducen en la memoria. A cada proceso se le asigna exactamente la memoria que necesita.

En la figura 6.4 se ilustra cómo evoluciona la ocupación de la memoria en un sistema de este tipo. Al principio sólo se encuentra el proceso A en la memoria. Después, se insertan los procesos B y C . En la figura 6.4-d A concluye. Luego, D entra y B sale. Por último E entra.

Con este método de gestión de la memoria se evita el problema de la fragmentación interna. Sin embargo, aparece el problema de la fragmentación externa entre particiones, el cual se aprecia en la figura 6.4-f. El problema consiste en que se creen huecos libres demasiado pequeños como para que quepan procesos, aunque la unión de todos esos huecos produciría un hueco considerable, lo que acarrea el desperdicio de la memoria. Una posible solución es la compactación de la memoria, que consiste en desplazar todos los procesos hacia la parte inferior de la memoria mientras sea posible. Como la compactación lleva mucho tiempo, a veces no se realiza, o se hace por la noche, en horas de poco uso del ordenador. Hay que tener en cuenta que el sistema debe detener todas sus actividades mientras realiza la compactación. Ello puede ocasionar tiempos de respuesta irregulares para usuarios interactivos, y podría ser devastador en un sistema de tiempo real. Además, con una combinación normal de trabajos que cambia rápidamente, es necesario compactar a menudo. En este caso, los recursos del sistema que se consumen quizá no justifiquen las ventajas de la compactación.

El esquema de los registro base y límite sigue siendo válido para la reasignación y la protección. Otro tema a tener en cuenta es la cantidad de memoria por asignar a un proceso recién creado. Si los procesos se crean con un tamaño fijo invariante, la asignación es muy sencilla, se asigna exactamente lo que se necesite.

Si, por el contrario, los segmentos de datos de los procesos pueden crecer, como es el caso de la asignación dinámica de memoria a partir de una pila, que ocurre en muchos lenguajes de programación, aparece un problema cuando un proceso intenta crecer. Si hay un hueco adyacente al proceso, éste puede ser asignado, y el proceso podrá crecer hacia el hueco. Sin embargo, si el proceso es adyacente a otro proceso, el proceso de crecimiento deberá ser desplazado a un hueco de la memoria lo suficientemente grande; o bien, habrá que eliminarlo.

Si es de esperar que la mayoría de los procesos crezcan conforme se ejecuten, sería una buena idea asignar un poco de memoria adicional siempre que un proceso pase a la memoria, con el fin de reducir el gasto excesivo asociado con el traslado de procesos que ya no caben en su memoria asignada. En la figura 5-a vemos una configuración de la memoria en la que se asignó a dos procesos el espacio adicional para el crecimiento.

Si los procesos pueden tener dos segmentos de crecimiento, como por ejemplo, el segmento de datos, que se utiliza como una pila, y el stack, se sugiere un método alternativo, el de la figura 5-b. En esta figura se puede ver que cada proceso tiene un stack de crecimiento hacia abajo, en la parte superior de la memoria asignada a él; además, tiene un segmento de datos justo encima del programa, el cual crece hacia arriba. La memoria entre ellos se puede utilizar para cualquiera de los segmentos. Si el espacio se agota, puede ocurrir que el proceso sea desplazado a un hueco con el espacio suficiente; o bien, ser aniquilado.

En el sistema de particiones estáticas es sencillo llevar el registro de la ocupación de la memoria, basta con guardar sobre cada partición si está libre, u ocupada por qué proceso, así como sus direcciones de comienzo y fin de partición. Por contra, con las particiones dinámicas, el número de éstas varía con el tiempo, así como su tamaño. Una forma posible de registrar la ocupación de la memoria es utilizar una lista enlazada de los segmentos de la memoria asignados o libres. La memoria de la figura 6.6-a se presenta en la figura 6-c como una lista enlazada de segmentos. Cada entrada de la lista especifica un hueco (H) o un proceso (P), la dirección donde comienza, su longitud, y un puntero a la siguiente entrada.

En este ejemplo, la lista de segmentos está ordenada por direcciones. Este orden tiene la ventaja de que al terminar un proceso la actualización de la lista es directa. Un proceso que termina, tiene dos vecinos (a menos que se encuentre en la parte superior o inferior de la memoria). Estos pueden ser procesos o huecos, lo que produce las cuatro combinaciones de la figura 6.7. En la figura 6.7-a, la actualización de la lista requiere el reemplazo de una P por una H. En la figura 6.6 (b) y (c), dos entradas se funden en una, y la lista se acorta en una entrada. En la figura 6.6-d tres entradas se fusionan en una. Puesto que en el descriptor del proceso que termina se guardará un puntero a la entrada de la lista enlazada que ocupa dicho proceso, sería conveniente que la lista fuera doblemente enlazada. Esta estructura facilita la búsqueda de la entrada anterior y, por tanto, la verificación de si es posible una fusión.

Figura 6.6. (a) Una parte de la memoria, con cinco procesos y 3 huecos. La marca muestra las unidades de asignación de la memoria. Las regiones sombreadas ( 0 en el mapa de bits) están libres. (b) El mapa de bits correspondiente. (c) La misma información como lista enlazada.

Cuando en un sistema de particiones dinámicas se debe asignar memoria principal para un nuevo proceso, y los procesos y huecos se mantienen en una lista ordenada por direcciones, se pueden utilizar diversos algoritmos para la elección del hueco de memoria donde ubicar al proceso. Supongamos que se conoce la cantidad de memoria por asignar.

El algoritmo más simple es el primero en ajustarse (first fit). Se revisa la lista de huecos hasta encontrar un espacio lo suficientemente grande. El espacio se divide entonces en dos partes, una para el proceso, y otra para la memoria no utilizada, excepto en el caso poco probable de un ajuste perfecto. Este algoritmo es rápido, ya que busca lo menos posible.

Otro algoritmo es el mejor en ajustarse (best fit), el cual busca en toda la lista, y elige el mínimo hueco suficientemente grande como para ubicar al proceso. Este algoritmo intenta que los huecos que se creen en la memoria sean lo más pequeños posible.

Como ejemplo de los algoritmos, retomemos la figura 6.6. Si se necesita un bloque de tamaño 2, el primero en ajustarse asignará el espacio en 5, mientras que el mejor en ajustarse asignará el espacio en 18.

Realizando simulaciones se ha demostrado que el algoritmo del mejor ajuste desperdicia más la memoria, pues al crear huecos demasiado pequeños, éstos no pueden ser utilizados por procesos. Un algoritmo que enfrenta el problema de la manera contraria es el del peor ajuste (worst fit). En este algoritmo se elige el hueco más grande disponible. De esta forma aumenta la probabilidad de que el nuevo hueco creado sea lo suficientemente grande como para albergar un proceso.

  ENLACE A LA SIMULACIÓN ESTRATEGIAS DE COLOCACIÓN

En un sistema con particiones estáticas el número de procesos con posibilidades de estar en estado listo viene determinado por el número de particiones, y en uno de particiones dinámicas por el tamaño de la memoria principal y el tamaño de los procesos, ya que en ambos métodos un proceso permanece en una partición hasta que finaliza. Supongamos un sistema en que dicho número es cinco, es muy probable que en un momento dado los cinco procesos que ocupan las particiones estén bloqueados (por ejemplo, porque esperan la finalización de una operación de E/S). Mientras los cinco procesos permanezcan bloqueados se desperdicia la CPU. Para remediar este inconveniente muchos sistemas operativos optaron por permitir ejecutar concurrentemente más procesos de los que pueden entrar físicamente en la memoria principal del ordenador. Para ello se utiliza la memoria secundaria (generalmente los discos) que, aunque más lenta, tiene mayor capacidad de almacenamiento que la principal. La solución consiste en tener en disco una copia de la parte de la memoria que ocupa todo proceso. En el disco se encuentran todos los procesos, en la memoria sólo unos cuantos. Para que un proceso se pueda ejecutar debe residir en memoria principal.

La razón por la que se aumenta el número de procesos con posibilidades de tener instrucciones en memoria principal es porque cuanto mayor sea este número, es menos probable que se dé la circunstancia de que todos estén bloqueados y, por lo tanto, es menor la posibilidad de que la CPU permanezca inactiva.

Algunos sistemas UNIX utilizaban el intercambio en un sistema de particiones dinámicas. El movimiento de procesos entre la memoria principal y el disco lo realizaba el planificador de nivel medio, conocido como el intercambiador (swapper a medio plazo). El intercambio de la memoria principal al disco (swapping out) se iniciaba cuando el S.O. precisa memoria libre y estaba toda ocupa debido a alguno de los siguientes eventos:

Además, cuando había que recuperar un proceso presente en el disco (swapping in) desde hace mucho tiempo con frecuencia se necesitaba sacar a otro proceso de memoria a disco para disponer de espacio para el primero.

El intercambiador elegía una víctima al examinar los procesos bloqueados en espera de algo (por ejemplo, una entrada del terminal). Es mejor sacar a un proceso bloqueado (pasará a estado suspendido_bloqueado) que sacar a uno listo. Si existían varios procesos bloqueados ubicados en la memoria principal se elegía a uno cuya combinación de prioridad y tiempo de residencia en memoria principal fuera más desfavorable. Así, un buen candidato era un proceso que hubiera consumido mucho tiempo de CPU recientemente, al igual que uno que hubiera permanecido en la memoria durante mucho tiempo, aun cuando durante este tiempo hubiera realizado E/S. Si no se dispone de procesos bloqueados, entonces se elegía a un proceso listo en base a los mismos criterios.

Cada pocos segundos el intercambiador examinaba la lista de procesos intercambiados para ver si alguno estaba listo para su ejecución. En caso de que existiera alguno, se seleccionaba a aquel que hubiese permanecido en el disco durante mucho tiempo. A continuación el intercambiador verificaba si el intercambio sería fácil o difícil. Un intercambio fácil era aquel en el que existiera la suficiente memoria libre, de forma que no había necesidad de sacar a un proceso para hacer espacio para el nuevo. Un intercambio difícil precisaba la eliminación de uno o más procesos. La implantación de un intercambio fácil se llevaba a cabo al traer el proceso a la memoria. Un intercambio difícil se implantaba liberando primero la memoria suficiente sacando a disco a uno o más procesos, y después, cargando en la memoria el proceso deseado.

Este algoritmo se repetía hasta que se cumpliera alguna de estas condiciones: (1) ningún proceso en el disco está suspendido_listo; o (2) la memoria está tan ocupada por procesos recién traídos que no hay espacio para más. Para evitar un trasiego excesivo entre memoria y disco que pudiera afectar al rendimiento no se intercambiaba hacia el disco a un proceso hasta que hubiera permanecido en la memoria durante 2 segundos.

El espacio libre en la memoria principal y en el dispositivo de intercambio se registraba mediante una lista enlazada de huecos. Si se necesitaba espacio en alguno de los dos, el algoritmo del primero en ajustarse leía la lista adecuada de huecos, y devolvía el primer hueco que encontrara y que fuese lo bastante grande, a la vez que eliminaba este espacio de la lista de huecos.