Capítulo dos

ADMINISTRACIÓN DE LA MEMORIA, -PRIMEROS SISTEMAS

La administración de la memoria principal es vital. De hecho, el desempeño de todo sis­tema ha dependido de dos cosas: cuánta memoria esté disponible y de qué manera se utiliza mientras se procesan los trabajos o tareas.

Este capítulo presenta el administrador de la memoria y cuatro tipos de esquemas de asignación de memoria: sistemas de un usuario, particiones fijas, particiones diná­micas y particiones dinámicas relocalizables. Empezamos con la más sencilla, que es la utilizada en las primeras generaciones de sistemas de cómputo.

Estos primeros esquemas de administración de la memoria rara vez se utilizan e: los sistemas operativos actuales; pero su estudio es importante porque cada uno intro­dujo conceptos fundamentales que ayudaron a la evolución de la administración de la

— - - m«mnr¡a Para ver cómo los sistemas operativos de hoy día administran la memoria, consulte las secciones de administración de la memoria en los capítulos 12-16.

18

ESQUEMA CONTIGUO DE USUARIO ÚNICO

Esquema contiguo de usuario único 19

^ per f — s e ?

< o

A / :

El primer esquema de asignación de memoria funcionaba como sigue: cada programa que se iba a procesar se cargaba completo en memoria y se le asignaba tanto espacio contiguo como necesitase. Las palabras clave eran completo y contiguo. Si el programa era demasiado grande y no cabía en el espacio de memoria disponible, no se podía eje­cutar. A pesar de que las primeras computadoras eran físicamente grandes, tenían muy poca memoria.

Esto demuestra un factor limitante significativo de todas las computadoras: tienen una cantidad finita de memoria y si un programa no cabe, hay que incrementar el ta­maño de la memoria principal o modificar el programa. Por lo general éste se reduce o se usan métodos que permiten la superposición de segmentos de programa (particio­nes del programa). "Superponer" es transferir segmentos de un programa de un alma­cenamiento secundario a la memoria principal para su ejecución, por lo que dos o más segmentos pueden ocupar por turno las mismas localidades de memoria.

Los sistemas de un solo iiÁuarin funcionan de la misma manera. Se da acceso a ca­da usuario a toda la memoria principal disponible para cada^area y estas se procesan en secuencia, una después de la otra. Para asignar memoria, el sistema operativo utiliza un algoritmo simple:

ALGORITMO PARA CARGAR UNA TAREA EN UN SISTEMA DE USUARIO Ú N I C O

1 Almacene la primera localidad de memoria del programa en el registro base (para protec­ción de la memoria)

2 Ponga el contador de programa (contiene la dirección de la siguiente instrucción que se va a ejecutar) igual que la dirección de la primera 1 oca 1 i dad de Benoria

3 Lea la primera instrucción del programa 4 Incremente el contador de programa en el número de bytes que ocupa la instrucción 5 ¿Ha llegado a la última instrucción?

Si es así, pare la carga del programa Si no es así, continúe con el paso 6

6 ¿El contador de programa es más grande que el tamaño de la memoria? Y Si es así, deje de cargar Si no es así. continúe con el paso 7

7 Cargue la instrucción en la memoria 8 Lea la siguiente instrucción del programa 9 Vaya al paso 4

Note que la cantidad de trabajo ejecutado por el administrador de ta memoria del sistema operativo es mínima. El código para llevar a cabo las funciones es directo y la lógica es demasiado sencilla. Bastan dos elementos de hardware: un registro para alma­cenar la "dirección base" y un "acumulador" para controlar el tamaño del programa conforme se lee en la memoria. Una vez que éste se encuentra en la memoria, perma­nece allí hasta completar la ejecución, ya sea a través de una terminación normal o por la intervención del sistema operativo.

Uno de los problemas principales con este tipo de asignación de memoria es que no apoya la multiprogramación (analizada en detalle en el capítulo 4); sólo puede ma­nejar una tarea a la vez. Cuando se pusieron a disposición del público por primera vez a

f

20 Capítulo 2/Administración de la memoria, primeros sistemas

fines de los 40 y principios de los 50, estas configuraciones de un solo usuario se usaron en las instituciones de investigación, pero no le sirvieron a la comunidad empresarial —no había una relación costo beneficio adecuada cuando había que gastar casi 200 000 dólares por una pieza de equipo que sólo podía utilizar una persona a la vez—. Por lo tanto, a fines de los 50 y a principios del decenio siguiente, se necesitaba de un nuevo esquema para administrar la memoria.

El diseño siguiente utilizaba particiones para aprovechar los recursos del sistema de la computadora superponiendo operaciones independientes.

PARTICIONES FUAS

El primer intento para posibilitar la multiprogramación fue la creación de particiones fijas (o particiones estáticas) en la memoria principal: una partición para cada tarea. Dado que el tamaño de cada partición se especficaba al encender el sistema, cada parti­ción sólo podía reconfigurarse apagando, reconfigurando o reiruciando el sisiemu de la computadora. Por lo que una vez que el sistema estaba en operación, el tamaño de las particiones quedaba fijo.

Este esquema introdujo un factor esencial: la protección del espacio de memoria para la tarea. Una vez asignada una partición a una tarea, no se permitía que ninguna otra tarea entrara en sus fronteras, ya sea de manera accidental o intencional. Este pro­blema de "intrusión en las particiones" no se presentaba en los esquemas de asignación contigua de un solo usuario, porque en cualquier momento sólo había una tarea en la memoria principal , por lo que bastaba proteger la porción del sistema operativo que residía en la memoria principal. Sin embargo, en los esquemas de asignación de parti­ción fija era obligatoria la protección de cada partición presente en la memoria princi­pal. Esto quedaba a cargo del hardware de la computadora y del sistema operativo (Madnick & Donovan, 1974).

El algoritmo para almacenar tareas en la memoria requiere unos cuantos pasos adi­cionales al utilizado en el sistema de un solo usuario, porque el tamaño de la tarea debv coincidir con el tamaño de la partición para asegurarse que quepa. Así pues, cuando se localiza un bloque de tamaño suficiente, debe revisarse el estado de la partición para ver si está disponible.

>.YO

ALGORITMO PARA CARGAR UNA TAREA O TRABAJO EN UNA PARTICIÓN FIJA ^ 1 Determine el tamaño de memoria solicitado por la tarea

" < ^ « - 3 < í " ^ " ^ J C ? 2 Si el tamaño de la tarea es > la partición más grande Entonces rechace la tarea

y f * \ " S * ^ Imprima un mensaje apropiado para el operador Vaya ai paso i para manejar ia siguiente tarea en línea

¡>o¿^ J Si no continúe con el paso 3

3 Ponga el contador en 1 4 Mientras el contador <= número de particiones en memoria . . . . .

Si ei tamaño de la tarea > tamaño de la partición de memoria (contador) Entonces contador = contador + 1

Si no

Particiones pjas ¿ i

Si el estado de partición de la memoria (contador) = "libre" Entonces cargue la tarea en la partición de memoria (contador)

Cambie el estado de partición de memoria (contador) a "ocupado" Vaya al paso 1

Si no contador = contador + 1

Fin mientras No hay una partición disponible en este momento: coloque la tarea en la cola de espera Vaya al paso 1

Este esquema de partición es más flexible que el de usuario único porque permite que varios programas estén en memoria al mismo tiempo. Sin embargo, aun así, requiere que se almacene el programa completo de manera contigua y en la memoria desde el principio hasta el fin de su ejecución. A fin de asignar espacios de memoria a tareas, el administrador de la memoria del sistema operativo debe mantener una tabla como la tabla 2.1, mostrando el tamaño de cada partición de memoria, su dirección, restric­ciones de acceso y estado actual (libre u ocupado) para el sistema que se ilustra en j a figura 2.1.

TABLA 2.1 Una tabla de memoria

de partición fija simplificada. K signi­

fica kilobyte: 1024 bytes. (Un análisis más a fondo de este tema se presenta en

el capítulo 8.)

Tamaño de la partición

Dirección en memoria Acceso

Estado de la partición

100K 200K Tarea 1 Ocupado 25K 300K Tarea 4 Ocupado 25K 325K Libre 50K 350K Tarea 2 Ocupado

FIGURA 2.1 Uso de la memoria

principal durante ¡a asignación de la parti­

ción fija de la tabla 2 . 1 . Im tarea 3 debe esperar,

aun cuando existen 70K de espacio dispo­

nible en la partición 1 , donde ¡a tarea 1 sólo

ocupa 30K de los 100K disponibles. Se

asigna espacio a ¡as tareas con base en la

"primera partición disponible del tamaño

requerido".

Lista de tareas J1 30K J2 50K J3 30K J4 25K ' Después de

la aceptación Estado original de la tarea

V T a r e a í f \ 3 q K ) ; -

Part ic ión 1 100K

Part ición 2 25K lililí Partición 3 25K

Part ic ión 4 50K

Part ición 1

Part ición 2

Part ic ión 3

Part ición 4

Memoria principal Memoria principal

22 Capitulo 2/Administración de la memoria, primeros sistemas

Cuando termina cada tarea, el estado de su partición de memoria pasa de ocupa­do a libre, de manera que es posible asignarle una tarea que llegue.

El esquema de partición fija funciona bien, si todas las tareas que se ejecutan en el sistema son del mismo tamaño o si los tamaños se conocen por anticipado y no varían entre recónfiguraciones. Idealmente, esto requeriría un conocimiento previo preciso de todas las tareas que se van a ejecutar en el sistema en las horas, días o semanas futuras. Sin embargo, a menos que el operador pudiera predecir el futuro con precisión, el tamaño de las particiones se determina de manera arbitraria y pueden resultar demasia­do pequeñas o grandes para las tareas que lleguen.

Si el tamaño de las particiones es demasiado pequeño, se presentarán consecuen­cias significativas: las tareas más grandes serán rechazadas o tendrán que esperar si las particiones grandes están ocupadas. Como resultado, estos trabajos deberán lene) un tiempo de realización más largo, ya que tienen que esperar que se liberen parti­ciones del tamaño adecuado, o quizá jamás se ejecuten.

Por otro lado, si las particiones son demasiado grandes, se desperdicia memoria. Si una tarea no ocupa toda ia partición, ia memoria ño utilizada de la misma permanece ociosa; no se le puede dar otra tarea porque a cada partición sólo se asigna una tarea a la vez. Es una unidad indivisible. La figura 2.1 demuestra esta circunstancia.

Este fenómeno del uso parcial de las particiones fijas y la creación coincidente de espacios sin utilizar en la partición se conoce como fragmentación interna y es uno de los inconvenientes más importantes del esquema de asignación de memoria en par­ticiones fijas.

PARTICIONES DINÁMICAS

Con las particiones dinámicas, la memoria disponible aún se conserva en bloques con­tiguos, pero a las tareas nada más se les da la memoria que solicitan cuando se cargan para su procesamiento. Aunque es una mejoría significativa en relación con las parti­ciones fijas —porque no se desperdicia memoria en la partición—, no elimina el proble­ma (Fig. 2.2).

Según se puede observar en la figura 2.2, un esquema de partición dinámica utiliza toda la memoria a! cargar las primeras tareas. Pero conforme entran nuevas tareas en el sistema, que no son del mismo tamaño de las que acaban de salir de la memoria, se acomodan en los espacios disponibles de acuerdo con su prioridad. La figura 2.2 demuestra la prioridad de "primero en llegar, primero en recibir atención". Por lo tanto, la asignación subsecuente de la memoria crea fragmentos de memoria libre entre bloques de memoria asignada (Madnick & Donovan, 1974). Estos problemas se cono­cen como fragmentación externa e, igual que en el caso de la fragmentación interna, dan lugar al desperdicio de memoria.

En la ultima instantánea, (e), de la figura 2.2, existen tres particiones libres de 5K 10K y 20K a 35K en total, suficientes para aceptar la tarea 8, que sólo requiere 30K. Sin embargo, no z¿r. jci-.ti^".:":, y dr.do qv? !?.s í?.-!1?" <r> cargan juntas, este esquema obliga a que la tarea 8 espere.

Antes que pasemos al siguiente esquema de asignación, examinemos la forma en que el sistema operativo controla las secciones libres de la memoria.

Particiones amamicus co

FIGURA 2.2 Uso y fragmentación de la memoria principal durante la asignación de las partiáones dinámicas. Cinco instan­táneas de la memoria principal conforme se someten ocho trabajos para su procesamiento y se asigna espacio según "primero en llegar, primero en recibir atención". La tarea 8 tiene que esperar ¡parte (e)] aun cuando existe suficiente memoria libre entre particiones para poder aceptarla.

Lista de trabajos J1 lOk J2 15K J3 20K J4 50K

Sistema operaWQ>v ,-..;:,\v;r.-«**^ 10K

Trabajo 1 (10K)

Trabajo 2 (15K)

Trabajo 3 (20K)

Trabajo 4 (50K)

20K

35K Trabajo 1 termina

Trabajo 4 termina

55K

105K

•̂ stemirjjperátiv'p, -

Trabajo 2 (15K)

20K

35K Trabajo 5 (5K) llega

Trabajo 6 (30K) llega

Sistema operatiyo.̂ Trabajo 5 (5K)

Trabajo 2 (15K)

Trabajo 3 (20N;

105K

Trabajo 6 (30K)

¿0 x-

10K 15K 20K

35K

S5K

85K

I05K

Ubicación inicial del trabajo en la memoria

(a)

Después de que los trabajos 1 y 4

han terminado (b)

Después de que los trabajos 5 y 6 fueron aceptados

(c)

..•Sistema operativo?.

Trabajo 5 (5K)

trabajo 3 termina Trabajo 2 (15K)

Trabajo 6 (30K)

10K

15K 20K

35K Trabajo 7(1 OK) llega

Trabajo 8(30K) ¡lega

55K

85K

105K

Trabaje 5 (5K)

5 * Trabajo 2 (15K)

Trabajo 7 (10K)

Trabajo 6 (30K)

10K 15K 20K

35K Trabajo 8 debe esperar

45K

55K

85K

Después de que el trabajo 3 ha terminado

(d)

Después de que el trabajo 7 fue aceptado

(e)

!

24 Capítulo 2/Administración de la memoria, primeros sistemas

ASIGNACIÓN DE MEJOR AJUSTE EN COMPARACIÓN CON PRIMER AJUSTE

Para los esquemas de asignación fija y de memoria dinámica, el sistema operativo debe mantener listas de cada localidad de memoria, anotando cuáles están libres y cuáles están ocupadas. Luego, conforme entran nuevas tareas en el sistema, las particiones l i ­bres se deben asignar.

Estas particiones se pueden asignar según la técnica del primer ajuste (la primera partición que llena los requisitos) o del mejor ajuste (la participación más pequeña que

Í £ { o 1 J S it llena los requisitos). Para ambos esquemas el administrador de la memoria organiza las listas de particiones libres y utilizadas (libres/ocupadas), ya sea por tamaño o localidad. La asignación de mejor ajuste mantiene las listas libres/ocupadas en orden por tamaño, desdeja más pequeña a la más grande. El método del primer ajuste organiza las listas libres/ocupadas por localidades de memoria, de bajo orden hasta alto orden. Cada una tiene sus ventajas, dependiendo de las necesidades del esquema particular de asigna­ción —por lo geneial el mejor ajuste aprovecha el mejor uso del espacio de memoria; el

c ^ c¡eS v primer ajuste es más rápido para asignar. A fin de comprender los pros y los contras, imagine que ha convertido su colección

o~^j)<z /e-. c ¿ j ^ 'P-S de libros en una biblioteca que los presta. Digamos que usted tiene libros de todos ^ tamaños y formas y que existe una corriente continua de personas que toman libros, se

los llevan y los traen de regreso, aunque siempre hay alguien esperando. Está claro que usted siempre estará ocupado, y eso es bueno, pero nunca tendrá tiempo de reorgani­zar los estantes.

Necesita un sistema. Su estantería tiene particiones fijas con unos cuantos espacios altos paca libros grandes, varias repisas para libros de bolsillo y mucho espacio para libros de texto. Necesitará saber cuáles espacios están llenos y dónde tiene hueco pa­ra más. Para los fines de nuestro ejemplo, llevaremos dos listas: una libre, para mostrar los espacios disponibles, y una ocupada, para los espacios llenos. Cada lista incluirá el tamaño y localización de cada espacio.

Cada que uno de los libros sale de su repisa, usted actualiza ambas listas: elimina el espacio de la lista ocupado y lo agrega en la lista de libres. Entonces, conforme le devuel­ven los libros y los coloca de regreso en los estantes, tendrá que actualizar de nuevo ambas listas.

Existen dos maneras de organizar sus listas: por tamaño o localización. Si opta por el tamaño, los espacios para los libros más pequeños estarán en la parte superior de la lista y en la parte inferior los más grandes. Cuando se organizan por localización, los espacios más cercanos a su escritorio de préstamos estarán en la parte superior de la lista, y las áreas más alejadas, en la parte inferior. ¿Qué opción es la mejor? Dependerá de lo que desea optimizar: espacio o velocidad de asignación.

Si organiza las listas por tamaño, optimiza su espacio en las estanterías: conforme llegan los libros, podrá colocarlos en los espacios donde se acomoden mejor. Es un es­quema de mejor ajuste. Si le devuelven un libro de bolsillo, lo colocará en la estantería con los demás de bolsillo, o por lo menos con otros libros pequeños. En forma similar, acomodará los libros grandes en estanterías con otros libros grandes. Sus listas facilitan encontrar el espacio disponible vacío donde quepa el libro. La desventaja de este siste­ma es que se desperdicia tiempo buscando el espacio más adecuado. Los demás clientes deberán esperar a que ponga el libro en su lugar, por lo que no será capaz de procesar tantos clientes como podría hacerlo con otro tipo de lista.

En el segundo caso, una lista organizada por localización de estantería, usted opti­miza el tiempo que le toma colocar de regreso los libros en la estantería. Es un esquema de primer ajuste. El sistema ignora el tamaño del libro que está devolviendo a la estan­tería. Si regresa el mismo libro de bolsillo, puede encontrar un espacio vacío con rapidez. De hecho, cualquier espacio varío cercano será suficiente, si es lo suficientemente grande, incluso puede utilizar una estantería de enciclopedias si está a su alcance, porque está optimizando el tiempo que tarda en volver a colocar los libros en las estanterías.

Se trata de un método rápido para colocarlos libros en las repisas y si la velocidad es de importancia, es la mejor de ambas alternativas. No es una buena elección si su es­pacio de estantería es limitado o si le devuelven muchos libros grandes, ya que éstos tendrán que esperar a que se desocupen espacios grandes. Si todos los espacios gran­des están llenos con libros pequeños, los clientes que devuelvan libros grandes deberán esperar hasta que se libere un espacio adecuado. (Al cabo del tiempo tendrá que reor­ganizar los libros y compactar su colección.)

La tabla 2.2 muestra cómo una tarea grande puede tener problemas con una lista de asignación, de memoria de primer ajuste. Las tareas 1, 2 y 4 se pueden introducir en el sistema e iniciar su ejecución, mientras que la tarea 3 tiene que esperar, aunque si se sumaran lo fragmentos de memoria, habría espacio más que suficiente para aceptarla. El primer ajuste es rápido en su asignación, pero no siempre es eficiente.

Por otra parte, con un esquema de mejor ajuste, la misma lista de tareas utilizaría la memoria con mayor eficiencia, según se puede observar en la tabla 2.3. En este caso, un esquema de mejor ajuste resultaría en una.mejor utilización de la memoria.

TABLA 2.2 Con un esquema libre de primer ajuste, la tarea 1 ocupa el primer espacio disponible. La tarea 2, exige la pri­mera partición lo suficientemente grande para entrar, pero al hacerlo ocupa el último bloque lo bastante grande para acomodar a la tarea 3 Pw lo tanto, la torea 3 (indicada por el asterisco) debe esperar hasta que se halla un bloque grande, aunque existan 75K de espacio de memoria sin utilizar (fragmentación interna y memoria no utilizada). Observe que la lista está ordenada de acuerdo con la localidad de la memoria.

Lista de tareas: Número Memoria de tarea solicitada

J1 10K J2 20K J3 30K* J4 I0K

Lista de memoria: Localidad Tamaño del bloque Número

de memoria de memoria de tarea Tamaño de tarea Estado Fragmentación interna

10240 30K • Jl 10K Ocupado 20K 40960 15K J4 10K Ocupado 5K 56320 50K/ ?.0K, Ocupado 30K 107520 20K Libre

Total 115K Total 40K disponible utilizado

2G Capítulo 2/Administración de la memoria, primeros sistemas

TABLA 2.3 Lista de mejorajusí£.dc participaciones Ubres. La tarca 1 se asigna a la partición libre más adecuada, igual que las tareas 2 y 3. La tarea 4 se asigna a la única partición libre aunque no sea la más funcional. En este esquema se atendieron las cuatro tarcas sin pérdida de tiempo. Observe que la lista se ordena de acuerdo con el tamaño de la memoria. Este esquema utiliza la memoria de una manera más eficiente, pero su tmplementación es más lenta.

Lista de tareas: Número Memoria de tarea solicitada

Jl 10K J2 20K J3 30K J4 10K

Lista de memoria: % Localidad Tamaño del bloque Número

de memoria de memoria de tarea Tamaño de tarea Estado Fragmentación interna

40960 15K 107520 20K 10240 30K

56320 50K Total 115K

disponible

Jl 10K J2 20K J3 30K J4 10K

Total 70K utilizado

Ocupado Ocupado Ocupado Ocupado

5K Ninguno Ninguno

40K

El uso de la memoria se ha incrementado, pero el proceso de asignación de la memoria toma más tiempo. Lo que es más, aunque se ha disminuido la fragmentación interna, no se ha eliminado.

El algoritmo de primer ajuste asume que el administrador de la memoria mantiene dos listas, uno para los bloques de memoria libres y otra para los bloques de memoria ocupados. La operación consiste en un ciclo simple, que compara el tamaño de cada

J<^^ tarea con el tamaño de cada bloque de memoria, hasta hallar un bloque lo suficiente­mente grande para la tarea. A continuación, ésta se almacena en ese bloque de memo­ria y el administrador de la memoria sale del ciclo para tomar la siguiente tarea de la cola de entrada. Si busca en vano en toda Id lista, deja la tarea en una cola de espera, toma la siguiente tarea y repite el proceso (Madnick & Donovan, 1974).

Los algoritmos para mejor ajuste y primer ajuste son muy diferentes. A conti­nuación aparece la forma en que se implementa el de primer ajuste.

ALGORITMO DE PRIMER AJUSTE

1 Ponga el contador e 1 2 Mientras el contador <= a: número de bloques en memoria

Si el tamaño del bloque > tamaño de memoria (contador) entonces el contador = contador + 1

Si no cargue el trabajo en el tamaño de memoria (contador) ajuste las listas libre y ocupado de la memoria

Asignación de mejor ajuste en comparación con primer ajuste c i

vaya al paso 4 Fin mientras

3 Coloque la tarea en la cola de espera 4 Vaya a recoger la siguiente tarea

En la tabla 2.4 se ha dado al administrador de la memoria una solicitud de 200 espacios. (Los espacios pueden ser palabras, bytes o cualquier otra unidad que maneje el sistema.) El administrador de la memoria parte de la parte superior de la lista y usa el algoritmo de primer ajuste para localizar el primer bloque de memoria lo suficiente­mente grande para aceptar el trabajo, que es la localidad 6785. El trabajo se carga, arrancando en la localidad 6785 y ocupa los siguientes 200 espacios. El siguiente paso es ajustar la lista libre para indicar que el bloque de memoria libre inicia en la localidad 6985 (no 6785 como antes) y que contiene sólo 400 espacios (no 600 como antes).

TABLA 2.4 Estas instantáneas de la memoria muestran el estado de cada bloque de memoria antes y después de una solicitud utilizando el algoritmo de primer ajuste. (Nota: todos lo valores están en notación decimal, a menos que se diga lo contrario.)

A n t e s de l a s o l i c i t u d D e s p u é s d e la s o l i c i t u d

T a m a ñ o d e l b l o q u e T a m a ñ o d e l b l o q u e

D i r e c c i ó n de i n i c i o de m e m o r i a D i r e c c i ó n de i n i c i o d e m e m o r i a

4075 105 4075 105 5225 5 5225 5 6785 600 •6985 400 7560 20 7560 20 7600 205 7600 205

10250 4050 10250 4050 15125 230 15125 230 24500 1000 24500 1000

El algoritmo para el mejor ajuste es un peco más complicado, ya que el objetivo es encontrar el bloque de memoria más pequeño en que quepa una tarea (Madnick & Donovan, 1974).

ALGORITMO DE MEJOR AJUSTE 1 Inicial ice el bloque de niemoriaCO) = 99999 1 Calcule el desperdicio inicial de memoria = bloque de memoria(O) - tamaño de la tarea 3 Inicial i ce el subíndice = 0 4 Ponga el contador en 1 5 Mientras el contador <= número de bloques en memoria

Si el tam*ño de la tarea > tamaño de la memcria{contador) Entonces contador = contador + 1

Si no desperdicio de memoria = tamaño de memoria(contador) - tamaño de la tarea Si el desperdicio inicial de la memoria > desperdicio de la memoria

Entonces subíndice = contador desperdicio inicial de la memoria = desperdicio de la memoria

. contador = contador + 1 Fin de mientras

28 Capítulo 2/Admuiistración de la memoria, primeros sistemas

6 Si subíndice • O Coloque la tarea en la cola de espera

Si no Cargue la tarea en el tamaño de la memoria(subindice) ajuste las listas de memoria 1ibres/ocupadas

7 Vaya a tomar la siguiente tarea

\o le^vwP^S ^ n 0 ^ e ^ o s P r ° b i e m a s c o n ei algoritmo delmejor ajuste es que se debe buscar toda la tabla, antes de poder efectuar la asignación, porque los bloques de memoria están almacenados en secuencia, de acuerdo con su ubicación en la memoria (y no en función a tamaños de bloque de la memoria, como en la tabla 2.3). El sistema puede ejecutar un algoritmo para volver a organizar continuamente la lista en orden ascendente por ta­maño de bloque de memoria; pero esto agregaría más carga general y quizás a la larga el uso del tiempo de procesamiento no resulte eficiente.

El algoritmo de mejor ajuste ilustrado anteriormente muestra nada más la lista de los bloques de memoria libres. La tabla 2.5 presenta la lista libre antes y después de asignar el lote de mejor ajuste a la solicitud presentada en la tabla 2.4. * En la tabla 2.5, se acaba de dar una solicitud de un bloque de 200 espacios ai admi­

nistrador de la memoria. El administrador de la memoria utiliza el algoritmo de mejor ajuste para buscar en toda la lista a partir de la parte superior de la misma a fin de localizar un bloque de memoria que se inicia en la localidad 7600, el bloque más pe­queño, pero lo bastante grande para aceptar el trabajo. La elección de este bloque mi­nimiza el espacio desperdiciado (sólo se desperdician cinco espacios, que es menos que en los otros cuatro bloques opcionales). El trabajo se almacena a partir de la localidad 7600 y ocupa los 200 espacios siguientes. Ahora debe ajustarse la lista libre para mostrar que el bloque de memoria libre se inicia en la localidad 7800 (no 7600 como antes) y que sólo contiene cinco espacios (no 205 como antes).

¿Qué es mejor, el primer o ei mejor ajuste? Durante muchos años no había manera de responder una pregunta tan general., porque el desempeño depende de la mezcla de-tareas. Observe que en tanto el mejor ajuste da una ocupación más adecuada, también da lugar (y así ocurre en el caso general) a un espacio "libre" más pequeño (cinco espa­cios) que se conoce como una "astilla".

En los ejercicios al final del capítulo se exploran dos esquemas de asignación hipo­téticos: siguiente ajuste, que empieza la búsqueda a partir del último bloque asignado

TABLA 2.5 Estas instantáneas de la memoria muestran el estado de cada bloque de memoria, antes y después de efectuar una solicitud mediante el algoritmo de mejor ajuste.

Antes de la solicitud Después de la solicitud Tamaño del bloque Tamaño del bloque

Dirección de inicio de memoria Dirección de inicio de memoria

9

4075 105 4075 105 5225 5 5225 5 6785 600 6785 600 7560 20 7560 20 7A00 205 _ 7800 . 5

10250 4050 10250 4050 15125 230 15125 230 24500 1000 24500 1000

para el siguiente bloque disponible cuando llega la nueva tarea; y peor ajuste, que asig­na el bloque disponible más grande libre a la nueva tarea. El peor ajuste es lo opuesto al mejor ajuste, pero, aunque se trata de una buena manera de explorar la teoría de la asignación de la memoria, pudiera no ser la mejor elección para un sistema real.

En años recientes los tiempos de acceso se han hecho tan rápidos que el esquema que ahorra el recurso más valioso, el espacio de memoria, puede ser el mejor en algunos casos. La investigación continúa concentrada en encontrar el esquema óptimo de asig­nación. Esto incluye el tamaño óptimo de página, un esquema de asignación tija, que trataremos en el siguiente capítulo y que es la clave para mejorar el desempeño del esquema de asignación de la mejor adecuación.

DESASIGNACIÓN

Hasta ahora sólo hemos considerado el problema de cómo se asignan los bloques de memoria, pero terminará por llegar el momento de liberar o desasignar el espacio de memoria.

Para un sistema de partición fija, el proceso es bastante sencillo. Cuando se termi-J na la tarea, el administrador de memoria restablece el estado del bloque de memoria,

donde se asignó la tarea, como "libre". Puede utilizarse cualquier código —por ejem­plo, valores binarios, donde el 0 significa libre y el 1 indica ocupado—, por lo que la tarea mecánica de liberar un bloque de memoria esTelativamente sencilla.

Un sistema de partición dinámica utiliza un algoritmo más complicado, ya que éste trata de combinar áreas libres de memoria siempre que sea posible. Por lo tanto, el sis­tema debe estar preparado para tres posibles situaciones (Madnick & Donovan, 1974).

^'Caso 1. Cuando el bloque que se va a'iiberar o desasignar está junto a otro bloque libre. Caso 2. Cuando el bloque por liberar se encuentra entre dos bloques libres. Caso 3. Cuando el bloque que se va a liberar se encuentra aislado de otros bloques libres. El algoritmo de liberación se prepara para las tres posibilidades, con un juego de con­

dicionales anidadas. E¡ siguiente algoritmo se basa en que las localidades de memoria se listan utilizando el esquema de dirección de más bajo a más alto. Habría que modificar el algoritmo para aceptar una organización diferente de localidades de memoria.

ALGORITMOS PARA LIBERAR BLOQUES DE MEMORIA

1 Si la ubicación de la tarea se encuentra junto a uno o más bloques libres Entonces Si la ubicacón de la tarea está entre dos bloques libres

Entonces combine los tres bloques en uno tamaño de la memoria(contador-1) = tamaño de la memoria(contador-l) + tamaño de la

tarea * tamaño de la memoriaícontador+1) Fije el estado del tamaño de la menicriaícontador+l) en entrada nula

Si no combine ambos bloques en uno tamaño de la memori a(contador -1) • tamaño de la memoria(contador-l) + tamaño de la tarea

30 Capítulo 2¡Administración de la memoria, primeros sistemas

Si no busque una entrada nula en la lista de memoria libre introduzca el tamaño de la tarea y la dirección de inicio en el lugar de entrada nula

Fije su estado en "libre"

Caso 1, unión de dos bloques libres

La tabla 2.6 muestra cómo ocurre la desasignación en un sistema de asignación de me moría dinámico, cuando la tarea que termina está junto a un bloque de memoria libré

Ésta es la lista libre ori­ginal antes de la desa-signacion ael caso i. El

asierisco indica el bloque de memoria libre vecino

al bloque de memoria que pronto se "liberará".

D i r e c c i ó n d e i n i c i o T a m a ñ o d e l b l o q u e de m e m o r i a E s t a d o

4075 105 Libre 5225 5 Libre 6785 • 60U Libre 7560 20 Libre

(7600) (200) ( O c u p a d o )

*7800 4 Libre 10250 4050 Libre 15125 230 Libre 24500 1000 Libre

1 Los números entre paréntesis no aparecen en la lista libre; pero se incluyeron por razones de claridad. El tamaño de la tarea es 200 y su localidad de inicio es 7600.

Después de desasignar, la lista libre se ve como la que se muestra en la tabla 2.7

TABLA 2.7 Dirección de inicio Caso 2. Lista libre

después de la desasig­nación. El asterisco

indica la localidad donde se efectuaron

cambios en el bloque de memoria libre.

Tamaño del bloque de memoria E s t a d o

4075 5225 6785 7560

•7600 10250 15125 24500

105 5

600 20

205 ^ 4050

230 1000

Libre Libre Libre Libre Libre Libre Libre Libre

El sistema usa el algoritmo de desasignación anterior y ve que la memoria por Li­berar está junto a un bloque de memoria libre, que se inicia en la localización 780C Entonces se debe modificar la lista para reflejar la dirección de inicio del nuevo blo Iib:C, 76CS, que era la dirección de la primera instrucción de la tarea que acaba de libe­rarlo. Además, el tamaño del bloque de memoria para este nuevo espacio libre se d< modificar para mostrar su nuevo tamaño; esto es, el total combinado de las dos parti­ciones libres (200 + 5).

Caso 2, unión de tres bloques libres

Cuando el espacio de memoria liberado está entre dos bloques de memoria libre, el proceso es similar (tabla 2.8).

El sistema utiliza el algoritmo de desasignación y descubre que la memoria que se va a liberar está entre dos bloques libres de memoria. Por lo tanto, se debe combinar el tamaño de las tres particiones libres (20 + 20 + 205) y el total se almacena con la direc­ción de inicio más pequeña, 7560.

TABLA 2.8 Caso 2. Lista libre origi­

nal antes de la desasig­nación. Los asteriscos

indican los dos bloques de memoria libre veci­

nos al bloque de memo­ria aue vronto se va a

D i r e c c i ó n d e i n i c i o T a m a ñ o d e l b l o q u e de m e m o r i a E s t a d o

4075 105 Libre 5225 5 Libre 6785 600 Libre

•7560 20 Libre (7580) r ( 2 o ) ( (Ocupado)1

• *7600 205 ) T i U r a

10250 4050 Libre 15125 230 Libre 24500 1000 Libre

1 Los números entre paréntesis no aparecen en la lista libre; pero se incluyen aquí por razone de claridad.

Dado que la entrada en la localidad 7600 se combinó con la entrada anterior, deb< mos "vaciar" esta entrada. Lo hacemos cambiando el estado a entrada nula, sin direccic de inicio ni tamaño de bloque de memoria, según indica el asterisco de la tabla 2.9. Es' vuelve innecesario tener que rearreglar la lista a expensas de la memoria.

TABLA 2.9 Dirección de inicio Tamaño del bloque de memoria Estado Case 2. Lista libre

después de que una 4075 105 Libre tarea ha liberado 5225 5 Libre

memoria. 6785 • 6nn Libre 7560 245 Libre

(entrada nu 10250 4050 Libre 15125 230 Libre 24500 1000 Libre

Casa 3, desasignación áe un bloque aislado

La tercera opción es cuando el espacio por liberar está aislado de las demás ai libres.

Para este ejemplo necesitamos saber más sobre la forma en que está configurac lista de memoria "ocupada". Para simplificar las cosas veamos la lista de ocupado } el área de memoria entre las localidades 7560 y 10250. Recuerde que en 7560 comu

32 Capítulo 2/Administración de la memoria, primeros sistemas

un bloque de memoria libre de 245, por lo que el área de memoria ocupada incluye todo desde la localidad 7805 (7560 + 245) hasta 10250, la dirección del siguiente bloque libre. Las listas libre y ocupada aparecen en las tablas 2.10 y 2.11.

TABLA 2.10 Caso 3. Lista libre ori­

ginal antes de la desasignación. El

bloque de memoria que pronto se liberará no

está junto a algún bloque libre.

D i r e c c i ó n d e i n i c i o T a m a ñ o d e l b l o q u e d e m e m o r i a E s t a d o

/ TABLA 2.11

Caso 3. Lista de memo­ria ocupada antes de la desasignación. La tarea

que se va a desasignar es del tamaño 445 y

empieza en la localidad 8805. El asterisco indi­

ca el bloque de memoria que "pronto será libre".

4075 105 Libre 5225 5 Libre 6785 600 Libre 7560 245 Libre

(entrada nula) 10250 4050 Libre 15125 230 Libre 24500 1000 Libre

D i r e c c i ó n d e i n i c i o

•

T a m a ñ o d e l b l o q u e de m e m o r i a E s t a d o

7805 .

1000 Ocupado w *8805 . 445 Ocupado

9250 1000 Ocupado

El sistema usa el algoritmo de desasignación para descubrir que el bloque de memoria que se va a liberar no se encuentra junto a ningún bloque de memoria libre; está entre dos áreas ocupadas. Por lo tanto, debe buscar una entrada nu!,¡ e>: la tabla.

El esquema presentado en este ejemplo crea durante el proceso de asignación o desasignación de la memoria entradas nulas tanto en la lista ocupada como en la lista libre. En el caso 2 se presentó un ejemplo de una entrada nula resultante de una desasig­nación. Se da una entrada nula en la lista ocupada cuando se devuelve; a la lista libre un bloque de memoria que se encuentra entre otros bloques ocupados (tabla 2.12). Este mecanismo asegura que todos los bloques se coloquen en las listas de acuerdo con la dirección de inicio de sus localidades de memoria, desde el más pequeño hasta el más grande.

TABLA 2.12 Dirección de inicio Tamaño del bloque de memoria Estado Caso 3. Lista ocupad" ~"

después de que la tarca 7805 1000 Ocupado liberó su memoria. El * (entrada nula I

asterisco indica la 9250 1000 Ocupado nueva entrada nula en • 1 • '

la lista ocupada.

Cuando se encuentra la entrada nula, la localidad de memoria de inicio del traba­jo que está terminando se introduce en la columna de dirección de inicio, el tamaño de la tarea se introduce en la columna del tamaño del bloque de memoria y el estado cam­bia de entrada nula a libre para indicar que un nuevo bloque de memoria está dispo­nible (tabla 2.13).

TABLA 2.13 Caso 3. Lista libre

después de que la tarea libera su memoria. El

asterisco indica la entrada "nuevo bloque libre" que reemplaza a

la entrada nula.

D i r e c c i ó n d e i n i c i o T a m a ñ o d e l b l o q u e d e m e m o r i a E s t a d o

4075 105 Libre 5225 5 Libre 6785 600 Libre 7560 245 Libre

•8805 445 Libre 10250 4050 Libre 15125 230 Libre 24500 1000 Libre

PARTICIONES DINÁMICAS RELOCALIZABLES

Los esquemas de asignación de memoria fijo y dinámico descritos hasta ahora comp; ten algunas características inaceptables de fragmentación que había que resolver ani que el número de tareas en espera de ser aceptadas se hiciera difícil de manejar. Adem existía una necesidad creciente de utilizar todas las "astillas" de memoria que quedab a menudo.

La solución a ambos problemas fue el desarrollo de particiones dinámicas reloc; zables. Con este esquema de asignación de memoria, el administrador de memc relocaliza los programas para reunir los bloques vacíos y compactarlos para hacer bloque de memoria lo bastante grande para aceptar algunas o todas las tareas en esp de entrar.

El sistema operativo compacta la memoria, proceso conocido a veces corno " r t lección de basura" o "desfragmentación", para recuperar secciones fragmentadas espacio de memoria. Recuerde nuestro ejemplo de la biblioteca de préstamo: si det: el préstamo de libros durante unos momentos y los reorganiza en el orden más ef< vo, está compactando su colección. Pero esto demuestra &u desventaja: se trata ds proceso de carga general, por lo que mientras se ejecuta la compactación, todo lo de debe esperar.

La compactación no es una tarea sencilla. Primero, todos los programas en mí ría se deben relocalizar, de manera que queder contiguos; luego, hay que ajusfar dirección y cada reterencia a una dirección en todo programa para tomar en consk ción la nueva localización del programa en la memoria. Sin embargo, hay que res] los demás valores dentro del programa (como los valores de los datos). En otras pala el sistema operativo debe distinguir entre direcciones y valores de datos, y las dif cico ÚÜ JOli obvias una vez que se carga el programa en la memoria.

Para evaluar la complejidad de la relocalización, veamos un programa t Recuerde, todos los números se almacenan en la memoria como valores binarios

34 Capítulo 2/'Administración de la memoria, primeros sistemas

¿ir

cualquier instrucción de programa no resulta raro encontrar direcciones y valores de datos. Por ejemplo, un programa de lenguaje ensamblador puede incluir la instrucción de agregar el entero 1 a I . La instrucción del código fuente se ve como sigue:

AODI I . 1

Sin embargo, una vez traducido el código real se vería como sigue (para mayor le­gibilidad, los valores se representan en código octal y no binario):

271 01 0

No salta a la vista cuáles son direcciones y cuáles son códigos de instrucción o valo­res de datos. De hecho, la dirección es ei número a la izquierda (000007). A continua­ción aparece el código de instrucción (271) y el valor de los datos está a la derecha (000001).

El sistema operativo puede reconocer la función de cada grupo de dígitos por su ubicación en la línea y en el código de operación. Sin embargo, si el programa sejnuevc a otro lugar de la memoria, hay que identificar cada dirección; es decir, se le pone una bandera. Luego se añade (o resta) la cantidad de localidades de memoria que el pro­grama ha sido desplazado a todas sus direcciones originales.

Esto adquiere particular importancia cuando el programa incluye secuencias de ciclo (o iteraciones), secuencias de decisión, secuencias de ramificación y referencias de datos. Si, por azar, no todas las direcciones se ajustan al mismo valor, el programa se ramificaría hacia una sección equivocada del mismo, hacia una sección de otro pro­grama o haría referencia a datos equivocados.

El programa en las figuras 2.3 y 2.4 muestra la forma en que el sistema operativo pone banderas en ias direcciones, de manera que se puedan ajusfar, si se reubica un programa.

Internamente, las direcciones se marcan mediante un símbolo especial (indicado en la figura 2.4 mediante apóstrofos) y el administrador de la memoria sabrá ajusfarlos según el valor almacenado en el registro de relocalización. Los demás valores (valores de datos) no están marcados y no se deben cambiar después de ia relocalización. Otros números en el programa, los que indican instrucciones, registros o constantes utiliza­dos en la instrucción, también se dejan sin tocar.

FIGURA 2.3 Programa en lenguaje

ensamblador que ejecu­ta una operación simple

incremental. Esto es lo que el programador

somete al ensamblador.

Los programas se muestran a la izquierda

y los comentarios que explican cada comando

aparecen a la derecha después de los puntos y

comas.

A: EXP 132. 144. 125. 110 .: 1 os valores de datos BEG1N: MOVEI 1.0 ¡inicializar registro 1

MOV El 2.0 ¡inicializar registro 2 LOOP: ADD 2.AÜ) ¡agregar (A + reg 1) a reg 2

A00I 1.1 ¡agregar 1 a reg 1 CAIG 1.4-1 ;es el reg i > 4-1? JUMPA LOOP :si no. vaya a Loop MOVE 3.2 ;si sí . mueva reg 2 a reg 3 IDIVI 3.4 ¡divida reg 3 entre 4.

¡el residuo se va al registr EXIT ¡fin ENO

Particiones dinámicas rciocauzames

FIGURA 2.4 Programa original en

lenguaje ensamblador

después de ser procesa­

do por el ensamblador.

Para ejecutar el progra­

ma, el ensamblador lo

traduce en código legi­

ble por la máquina (a la

izquierda) con todas las

direcciones marcadas

con un símbolo especial

(mostrado aquí como

un apóstrofo) para dis­

tinguir ¡as direcciones

de los valores de datos.

(Este programa de

cjtmpiu *c coi nú en un

sistema DEC triproce-

sador 1099 con un

monitor TOPS-10 y

sistema operativo ver­

sión 7.OIA.)

000000* 000000 000132 A: EXP 132. 144. 125 000001* 000000 000144 000002* 000000 000125 000003" 000000 000110

000004* 201 01 0 00 000000 BEGIN: MOVEI 1.0 000005' 201 02 0 00 000000 HQVEI 2.0 000006* 270 02 0 01 000000' LOOP: ADD 2.AC1) 000007' 271 01 0 00 000001 A00I 1.1 000008' 307 01 0 00 000003 CAIG 1.4-1 000009' 324 00 0 00 000006' JUMPA LOOP 000010' 200 03 0 00 000002 M0VE 3.2 000011' 231 03 0 00 000004 10IVI 3.4 000012' 047 00 0 00 000012 EXII

000000 END

La figura 2.5 ilustra lo que ocurre a un programa en la memoria durante la com­pactación y relocalización.

Nuestro análisis lleva a tres preguntas:

1. ¿Qué pasa tras bambalinas cuando ocurre la relocalización y la compactación? 2. ¿Qué controla cuan lejos se desp'azó cada tarea de su área original de almacena­

miento? 3. ¿Qué listas se deben actualizar?

La última pregunta es la más rápida de resolver. Después de la relocalización y la compactación, se actualizan las listas libre y ocupada. La primera se cambia para mostrar la partición del nuevo bloque de memoria libre: la formada como resultado de la compactación, que se localizará en la memoria a partir de la última localidad ut i ­lizada por el último trabajo. La lista ocupada se cambia a fin de mostrar las nuevas localidades de las tareas en proceso que se reubicaron. Cada tarea tendrá una nueva dirección, excepto las que residan en las localidades de memoria más bajas.

Para responder las otras dos preguntas debemos aprender más sobre los componen­tes de hardware de una computadora, en especial sobre los registros. Se utilizan regis­tros de uso especial para ayudar con la reloc^'ización. Algunas computadoras tienen dos registros especiales reservados para esta finalidad: el registro de límites y el de relocali­zación.

El registro de límites se utiliza para almacenar la localidad más alta (o la más baja) dependiendo del sistema en memoria accesible por cada programa. Esto asegura que durante la ejecución e! programa no intentará tener acceso a localidades de memoria que no le correspondan; esto es, que están "fuera de límite". El registro de relocalizacion

3G Capítulo 2/Administración de la memoria, primeros sistemas

Tres instantáneas de la memoria, antes y después de la compactación. Cuando la tarea 6 llega y requiere 84K, la FIGURA 2.5 disposición inicial de la memoria a) muestra fragmentación externa, con un total de 96K de espacio. En seguida

de la compactación b), se ha eliminado la fragmentación externa y hay espacio para la tarea 6 c).

Sistema operativo

Tarea 1 (8K)

Tarea 4 (32K)

Tarea 2 (16K)

Tarea 5 (48K)

10K 18K

30K

Í 5 6 K

210K

Diagrama inicia! de memoria (a)

Sistema operativo

Tarea 1 (8K)

Tarea 4 (32K)

Tarea 2 (16K)

Tarea 5 (48K)

10K 18K

50K

66K Ahora e! trabajo 6 puede ser acomodado

114K

210K

Diagrama de memoria después de la compactación

Sistema operativo

Tarea 1 (8K)

Tarea 4 (3 2 K)

Tarea2(16K)

Tarea 5 (48K)

Tarea 6 (84K)

Diagrama de la memoria después que el trabajo 6 fue cargado

(0

contiene el valor que d°be agregarse a cada una de las direcciones referidas en el pro­grama, de manera que puedan tener acceso a las direcciones correctas de memoria después de la relocalización. Si el programa no se reubica, el valor almacenado en su registro de relocalización es cero.

La figura 2.6 ilustra lo que ocurre durante la relocalización utilizando el registro de relocalización (todos los valores se muestran en forma decimal).

Originalmente, la Tarea 4 se cargó en la memoria a partir de la localidad de memo­ria 30K. (K significa kilobyte, que es igual a 1024 bytes. Por lo tanto, la dirección exac­ta de inicio es 30 * 1024 = 30 720.) Se requirió un bloque de memoria con 32K (o 32 * 1024 = 32 768) localidades dirigibles. Por lo tanto, cuando se cargó en un inicio, el Tra­bajo ocupaba el espacio de la localidad de memoria 30720 a la 63488-1. Ahora suponga que en el programa, en la localidad de memoria 31744, existe una instrucción que se ve como sigue:

LOAD 4. ANSWER

Particiones dinámicas relocalizables 37

FIGURA 2.6 Registro de. rclocaliza-

aón y un acercamiento del área de memoria de

la Tarca 4, a) antes de la rcubicación, y b) después de la relocali­

zación y compactación.

31744-

53248-

Registro de relocalización

00000

Sistema operativo

Tarea 1 (8K)

Load 4, 53248

37

Tarea 2 (16K)

10K 18K

30K

62K

92K

19456

40960-

TAREA 4 A'b (32K)

Registro de relocalización

-12288

Sistema operativo Tarea 1 (8K)

Load 4. 53248

37

Tarea 2 (16K)

Tarea 5 (48K)

10K 18K ,

50K

65K

TAREA 4-At (32K)

(a) (b)

Este comando de lenguaje ensamblador pide que el valor de datos conocid*© come ANSWER se cargue en el registro 4, para algún cálculo posterior. ANSWER, el valor 37, esté almacenado en la localidad de memoria 53248. (En este ejemplo, el registro 4 es un re gistro de trabajo/cálculo, diferente de los registros de relocalización y de límites.)

Después de la relocalización, laTarea 4 ha pasado a una nueva dirección de memo ria de inicio de 18K (en realidad 18 * 1024 = 18 432). La Tarea conserva sus 32K de loca lidades dirigibles, por lo que ahora ocupa memoria desde la localidad 18432 hasta h 51200-1 y, gracias al registro de relocalización, todas las direcciones se ajustaron d< acuerdo con lo anterior.

¿Que contiene el registro de relocalización? En este ejemplo, el valor-12288. Seguí se calculó, 12288 es el tamaño de un bloque libre "movido hacia delante" hacia un extre mo alto de dirección de memoria. El signo es negativo porque la Tarea 4 se "movió haci; atrás", más cerca al extremo bajo de dirección de memoria, según se observa en la part« superior de la figura 2.6 b).

Sin embargo, la instrucción de programa (LOAD 4 .ANSWER) no ha cambiado. La direc ción original 53248 donde se almacenó ANSWER sigue igual en el programa, sean cuanta sean las veces que se relocalice. Ahora bien, antes de ejecutar la instrucción, hay qu calcular la dirección "verdadera", sumando el valor almacenado en el registro de re localización a la dirección en que se encuentra dicha instrucción. Si las direcciones n-se ajustan con el valor almacenado en el registro de relocalización, entonces a pesar d que ¡a localidad de memoria 31744 aún sea parte del conjunto accesible de localidade de memoria de la tarea, ya no contendría el comando LOAD. No sólo eso, sino que ahor la localidad 53248 está "fuera del límite". La instrucción que originalmente estaba e 31744 ha pasado a la localidad 19456. Esto se debe a que todas las instrucciones de est programa se han "movido hacia atrás" 12K (12 * 1024 - 12 288), el tamaño del bloqu libre. Por lo tanto, la localidad 53248 se desplazó-12288 y ANSWER. el valor de datos 3!-ahora se encuentra en la dirección 40960.

En efecto, mediante la relocalización y la compactación, el administrador de la m< moría optimiza el uso de la memoria, con lo que mejora la producción —una de las mea das de rendimiento del sistema—. Un efecto colateral desafortunado es que se incun en más carga general que en el caso de los dos esquemas anteriores de asignación d

38 Capítulo 2/Administración de la memoria, primeros sistemas

memoria. El factor crucial aquí es la periodicidad de la compactación: cuándo y con qué frecuencia debe efectuarse. Existen tres opciones.

Una opción es realizarla cuando cierto porcentaje de la memoria queda ocupado, digamos 75 por ciento. La desventaja es que el sistema incurriría en una carga general innecesaria si no hay tareas esperando utiltóar ese 25 por ciento restante.

Un segundo procedimiento es compactar la memoria sólo cuando hayan tareas en espera de entrar. Esto significaría una revisión constante de la cola de entrada, lo que puede resultar en una carga general innecesaria y en la reducción de la velocidad del procesamiento de las tareas incluidas en el sistema.

La tercera opción es compactar después de un lapso preestablecido. Si el periodo elegido es demasiado breve, el sistema utilizará más tiempo en compactación que en procesamiento. Si es demasiado grande, se acumularán demasiadas tareas en la cola de espera y se perderán las ventajas de la compactación.

Como puede ver, cada opción tiene puntos buenos y malos. El diseñador del sis­tema operativo decide la mejor elección para cualquier sistema. Este especialista inten­ta optimizar el tiempo de procesamiento y el uso de 1? memoria, además de mantener al mismo tiempo las cargas generales tan bajas como sea posible, con base en la mezcla de tareas y otros factores.

CONCLUSIÓN DEL CAPÍTULO 2

En este capítulo se presentaron cuatro técnicas de administración de la memoria: siste­mas de un solo usuario, particiones fijas, particiones dinámicas y particiones dinámicas reiüoalizables. Tienen tres puntos en común: todas requieren que la totalidad del pro­grama 1) quede cargado en la memoria, 2) quede almacenado junto y 3) permanezca en la memoria hasta que se complete la tarea.

En consecuencia, cada técnica impone fuertes restricciones en el tamaño de las ta­reas, porque sólo pueden ser tan grandes como la partición más grande en memoria.

Estos esquemas resultaron suficientes para las tres primeras generaciones de compu­tadoras, que procesaban las tareas en el modo por lotes. El tiempo de retorno se medía en horas, o a veces en días; pero hubo un tiempo en que los usuarios aceptaban este plazo entre el momento en que sometían sus tareas y la recepción de la salida. Como veremos en el siguiente capítulo, apareció una nueva tendencia con las computadoras de la tercera generación de fines de los 60 y principios de los 70: los usuarios pudieron conectarse directamente con la unidad de procesamiento central vía estaciones remotas de entrada de tareas y cargar sus tareas desde terminales en línea que podían interac-tuar con el sistema de un modo más directo. Para poder atenderlos se necesitaron nuevos métodos de administración de la memoria.

Veremos que los esquemas de asignación de la memoria que siguieron tenían dos aspectos nuevos en común. Primero, los programas no tenían que quedar almacenados en localidades contiguas de la memoria: se podían dividir en "segmentos" de tamaño variable o en "páginas" de tamaño igual. Cada página o segmento podía almacenarse en Cualquier Iu 6 ar dor.de existiera un bloque vacío con capacidad para aceptarlo. Se­gundo, no todas las páginas o segmentos tenían que residir en la memoria durante la ejecución de la tarea. Éstos fueron avances significativos para los diseñadores, operado­res y usuarios de los sistemas.