Capítulo 8 Gestión de Memoria PDF

## Capítulo 8 Gestión de memoria #### **8.1 Antecedentes** En el capítulo 5 mostramos cómo un conjunto de procesos puede compartir la CPU. Un resultado de la planificación de la CPU es que se mejora tanto el aprovechamiento de la CPU como la rapidez con que el computador responde a sus usuarios. S...

## Capítulo 8 Gestión de memoria #### **8.1 Antecedentes** En el capítulo 5 mostramos cómo un conjunto de procesos puede compartir la CPU. Un resultado de la planificación de la CPU es que se mejora tanto el aprovechamiento de la CPU como la rapidez con que el computador responde a sus usuarios. Sin embargo, para lograr este aumento en el desempeño es preciso mantener varios procesos en la memoria; es preciso compartir la memoria. En este capítulo examinaremos varias formas de administrar la memoria. Los algoritmos de gestión de memoria varían desde un enfoque primitivo de "máquina desnuda" hasta las estrategias de paginación y segmentación. Cada enfoque tiene sus ventajas y desventajas. La selección de un esquema de gestión de memoria para un sistema específico depende de muchos factores, principalmente el diseño de hardware del sistema. Como veremos, muchos algoritmos requieren soporte de hardware. #### **8.1.1 Vinculación de direcciones** Normalmente, un programa reside en un disco como archivo binario ejecutable. Es preciso traer el programa a la memoria y colocarlo dentro de un proceso para que se ejecute. Dependiendo de la gestión de memoria empleada, el proceso podría transferirse entre el disco y la memoria durante su ejecución. La colección de procesos que están en el disco esperando que se les transfiera a la memoria para ejecutarse forma la cola de entrada. El procedimiento normal es seleccionar uno de los procesos de la cola de entrada y cargarlo en la memoria. A medida que el proceso se ejecuta, accede a instrucciones y datos de la memoria. Tarde o temprano, el proceso termina, y su espacio de memoria se marca como disponible. La mayor parte de los sistemas permiten a un proceso de usuario residir en cualquier parte de la memoria física. Así, aunque el espacio de direcciones del computador comience en 00000, la primera dirección del proceso de usuario no tiene que ser 00000. Esta organización afecta las direcciones que el programa de usuario puede utilizar. En la mayor parte de los casos, un programa de usuario pasará por varias etapas (algunas de las cuales podrían ser opcionales) antes de ejecutarse (Fig. 8.1). Las direcciones podrían representarse de diferentes maneras en dichas etapas. Las direcciones del programa fuente generalmente son simbólicas (como CUENTA). Un compilador por lo regular vincula tales direcciones simbólicas con direcciones reubicables (como "14 bytes a partir del principio de este módulo"). El editor de enlace o cargador, a su vez, vinculará estas direcciones reubicables con direcciones absolutas (como 74014). Cada vinculación es una transformación de un espacio de direcciones a otro. Tradicionalmente, la vinculación de instrucciones y datos con direcciones de memoria se puede efectuar en cualquier etapa del camino: - **Compilación:** Si en el momento de la compilación se sabe en qué parte de la memoria va a residir el proceso, es posible generar código absoluto. Por ejemplo, si se sabe a priori que un proceso de usuario residirá a partir de la posición R, el código generado por el compilador empezará en esa posición y se extenderá de ahí hacia arriba. Si posteriormente la posición de inicio cambia, será necesario recompilar el código. Los programas con formato .COM de MS-DOS son código absoluto vinculado en el momento de la compilación. - **Carga:** Si al compilar el programa no se sabe en qué parte de la memoria va a residir el proceso, el compilador deberá generar código reubicable. En este caso, la vinculación final se posterga hasta el momento de la carga. Si la dirección de inicio cambia, bastará con volver a cargar el código de usuario para incorporar este valor modificado. - **Ejecución:** Si, durante su ejecución, un proceso se podría pasar de un segmento de la memoria a otro, la vinculación deberá postergarse hasta el momento de la ejecución. Se requiere hardware especial para que este esquema funcione, como veremos en la sección 8.2. Una porción importante de este capítulo se dedicará a mostrar cómo estas distintas vinculaciones se pueden implementar efectivamente en un sistema de computación, y a estudiar el soporte de hardware apropiado. #### **8.1.2 Carga dinámica** Hasta aquí hemos supuesto que todo el programa y todos los datos de un proceso deben estar en la memoria física para que el proceso se ejecute. El tamaño de un proceso está limitado al tamaño de la memoria física. Podemos usar carga dinámica para lograr un mejor aprovechamiento del espacio de memoria. Con esta técnica, las rutinas no se cargan sino hasta que se invocan. Todas las rutinas se mantienen en el disco en un formato de carga reubicable. El programa principal se carga en la memoria y se ejecuta. Cuando una rutina necesita llamar a otra, lo primero que hace es ver si la otra rutina ya se cargó. Si no es así, se invoca el cargador de enlace reubicable para que cargue la rutina deseada en la memoria y actualice las tablas de direcciones del programa de modo que reflejen este cambio. Luego se transfiere el control a la rutina que se acaba de cargar. La ventaja de la carga dinámica es que una rutina que no se utiliza nunca se carga. Este esquema es útil sobre todo cuando se requieren grandes cantidades de código para manejar casos que ocurren muy de vez en cuando, como las rutinas de error. En este caso, aunque el tamaño total del programa podría ser grande, la porción que realmente se usa (y que es la que realmente se carga) podría ser mucho más pequeña. La carga dinámica no requiere soporte especial por parte del sistema operativo; es responsabilidad de los usuarios diseñar sus programas de modo que aprovechen semejante esquema. Sin embargo, los sistemas operativos podrían ayudar al programador ofreciendo rutinas de biblioteca que implementen la carga dinámica. #### **8.1.3 Enlace dinámico** Observe que la figura 8.1 también muestra bibliotecas enlazadas dinámicamente. La mayor parte de los sistemas operativos sólo maneja el enlace estático, en el que las bibliotecas de lenguaje del sistema se tratan como cualquier otro módulo objeto que el cargador combina dentro de la imagen de programa binaria. El concepto de enlace dinámico es similar al de carga dinámica. En lugar de posponer la carga hasta el momento de la ejecución, lo que se pospone es el enlace. Esta característica suele usarse con las bibliotecas del sistema, como las bibliotecas de subrutinas de un lenguaje. Si no se cuenta con este recurso, todos los programas de un sistema requerirán la inclusión de una copia de su biblioteca de lenguaje (o al menos de las rutinas a las que el programa hace referencia) en su imagen ejecutable. Este requisito desperdicia tanto espacio en disco como memoria principal. Con enlace dinámico, se incluye un fragmento (stub) en la imagen por cada referencia a una rutina de biblioteca. Este fragmento es una sección pequeña de código que indica cómo localizar la rutina de biblioteca apropiada, que reside en la memoria, o cómo cargar la biblioteca si la rutina no está ya presente. Cuando este fragmento se ejecuta, verifica si la rutina que necesita ya está en la memoria. Si no es así, el programa la carga en la memoria. De cualquier manera, el fragmento se sustituye a sí mismo por la dirección de la rutina, y ejecuta la rutina. Así, la próxima vez que se llega al segmento de código la rutina de biblioteca se ejecuta directamente, sin incurrir en el costo del enlace dinámico. Con este esquema, todos los procesos que utilizan una biblioteca de lenguaje ejecutan una sola copia del código de la biblioteca. Esta característica se puede extender a la actualización de bibliotecas (como cuando se corrigen errores). Una biblioteca podría sustituirse por una versión nueva, y todos los programas que hagan referencia a la biblioteca usarán automáticamente la nueva versión. Sin enlace dinámico, habría que volver a enlazar todos esos programas para tener acceso a la biblioteca nueva. Para que los programas no ejecuten accidentalmente versiones nuevas e incompatibles de las bibliotecas, se incluye información de versión tanto en los programas como en las bibliotecas. Se podría cargar en memoria más de una versión de una biblioteca, y cada programa utilizará su información de versión para decidir cuál copia de la biblioteca usará. Si los cambios son menores, se conserva el mismo número de versión; si los cambios son importantes, el número de versión se incrementa. Así, sólo los programas que se compilan con la versión nueva de una biblioteca son afectados por los cambios incompatibles incorporados en ella. Los programas que se enlazaron antes de que se instalara la nueva biblioteca seguirán usando la biblioteca vieja. Este sistema se conoce como de bibliotecas compartidas. A diferencia de la carga dinámica, el enlace dinámico generalmente requiere algo de ayuda del sistema operativo. Si los procesos en memoria están protegidos unos de otros (Sec. 8.4.1), el sistema operativo es la única entidad que puede comprobar si la rutina que se necesita está en el espacio de memoria de otro proceso, y puede permitir que múltiples procesos accedan a la misma dirección de memoria. Este concepto se amplía cuando se utiliza junto con la paginación, como veremos en la sección 8.5.5. #### **8.1.4 Superposiciones (Overlays)** Para que un proceso pueda ser mayor que la cantidad de memoria que se le ha asignado, a veces se emplea una técnica llamada de superposiciones. Lo que se busca es mantener en la memoria sólo las instrucciones y datos que se necesitan en cualquier momento dado. Si se requieren otras instrucciones, se cargan en un espacio que antes estaba ocupado por instrucciones que ya no se necesitan. Por ejemplo, consideremos un ensamblador de dos pasadas. Durante la pasada 1, el ensamblador construye una tabla de símbolos; después, durante la pasada 2, genera código en lenguaje de máquina. Quizá podríamos dividir semejante ensamblador en código de la pasada 1, código de la pasada 2, tabla de símbolos y rutinas de soporte comunes utilizadas tanto por la pasada 1 como por la 2. Supongamos que los tamaños de los componentes son éstos (K significa "kilobyte", que es 1024 bytes): - Pasada 1: 170K - Pasada 2: 280K - Tabla de símbolos: 20K - Rutinas comunes: 30K Para cargar todo a la vez, necesitaríamos 200K de memoria. Si sólo contamos con 150K, no podremos ejecutar nuestro proceso. Observemos, empero, que la pasada 1 y la 2 no tienen que estar en la memoria al mismo tiempo. Así pues, definimos dos superposiciones: la superposición A es la tabla de símbolos, las rutinas comunes y la pasada 1, y la superposición B es la tabla de símbolos, las rutinas comunes, y la pasada 2. Añadimos un controlador de superposiciones (10K) y empezamos con la superposición A en la memoria. Al terminar la pasada 1, saltamos al controlador de superposiciones, el cual lee la superposición B y la coloca en la memoria, sobreescribiendo la superposición A, y luego transfiere el control a la pasada 2. La superposición A sólo necesita 120K, mientras que la B necesita 130K (Fig. 8.2). Ahora podemos ejecutar nuestro ensamblador en los 150K de memoria. La carga será un poco más rápida porque no hay que transferir tantos datos antes de poder iniciar la ejecución, pero el funcionamiento será un poco más lento, a causa de la E/S adicional para leer el código de la superposición B y colocarlo sobre el de la superposición A. El código para las superposiciones A y B se guarda en disco como imágenes de memoria absolutas, y el controlador de superposiciones lo lee según lo va necesitando. Se requieren algoritmos de reubicación y enlace especiales para construir las superposiciones. Al igual que la carga dinámica, las superposiciones no requieren soporte especial por parte del sistema operativo; el usuario las puede implementar en su totalidad empleando estructuras de archivo simples y transfiriendo código de los archivos a la memoria, para luego saltar a esa memoria y ejecutar las instrucciones recién leídas. Lo único que el sistema operativo nota es que hay más E/S que la acostumbrada. #### **8.2 Espacio de direcciones lógico y físico** Una dirección generada por la CPU se denomina dirección lógica, en tanto que la percibida por la unidad de memoria (esto es, la que se carga en el registro de dirección de memoria de la memoria) se conoce como dirección física. Los esquemas de vinculación de direcciones durante la compilación y durante la carga dan pie a un entorno en el que las direcciones lógicas y físicas son las mismas. En cambio, la ejecución del esquema de vinculación de direcciones durante la ejecución produce un entorno en el que las direcciones lógicas y físicas difieren. En este caso, solemos llamar a la dirección lógica dirección virtual. En el presente texto usaremos los términos dirección lógica y dirección virtual indistintamente. El conjunto de todas las direcciones lógicas generadas por un programa es su espacio de direcciones lógico; el conjunto de todas las direcciones físicas que corresponden a esas direcciones lógicas es un espacio de direcciones físico. Así pues, en el esquema de vinculación de direcciones en el momento de la ejecución, los espacios de direcciones lógico y físico difieren. La transformación de direcciones virtuales a físicas en el momento de la ejecución corre por cuenta de la unidad de gestión de memoria (MMU, memory-management unit), que es un dispositivo de hardware. Hay varios esquemas distintos para realizar tal transformación, como veremos en las secciones 8.4.1, 8.5, 8.6 y 8.7. Por lo pronto, ilustraremos dicha transformación con un esquema de MMU sencillo, que es una generalización del esquema de registro base que describimos en la sección 2.4. Como se aprecia en la figura 8.3, este esquema requiere un soporte de hardware un poco diferente de la configuración que analizamos en la sección 2.4. El registro base ahora se llama registro de reubicación, y el valor que contiene se suma a todas las direcciones generadas por un proceso de usuario en el momento en que se envían a la memoria. Por ejemplo, si la base está en 14000 y el usuario intenta direccionar la posición 0, la dirección se reubicará dinámicamente a la posición 14000; un acceso a la posición 346 se transforma en la posición 14346. El sistema operativo MS-DOS que se ejecuta en la familia de procesadores Intel 80X86 utiliza cuatro registros de reubicación al cargar y ejecutar procesos. Cabe señalar que el programa de usuario nunca ve las direcciones físicas reales. El programa puede crear un puntero a la posición 346, almacenarlo en memoria, manipularlo, compararlo con otras direcciones, etc., todo como el número 346. Só-lo cuando este número se usa como dirección de memoria (digamos en una carga o un almacenamiento indirecto) se le reubica relativo al registro base. El programa de usuario maneja direcciones lógicas. El hardware de transformación de memoria convierte direcciones lógicas en direcciones físicas. Esta forma de vinculación en el momento de la ejecución se explicó en la sección 8.1.1. La posición final de una dirección de memoria a la que se hace referencia no se determina sino hasta que se hace dicha referencia. Observe también que ahora tenemos dos tipos de direcciones distintos: direcciones lógicas (en el intervalo 0 a máx) y direcciones físicas (en el intervalo R + 0 a R + máx si el valor base es R). El usuario genera únicamente direcciones lógicas y piensa que el proceso se ejecuta en las posiciones de 0 a máx. El programa de usuario proporciona direcciones lógicas, las cuales deben transformarse en direcciones físicas antes de usarse. El concepto de espacio de direcciones lógico que se vincula a un espacio de direcciones físico independiente es fundamental para una gestión de memoria adecuada. #### **8.3 Intercambio** Un proceso tiene que estar en la memoria para ejecutarse, pero podría intercambiar-se temporalmente de la memoria a un almacenamiento auxiliar y luego traerse otra vez a la memoria para continuar su ejecución. Por ejemplo, supongamos un entorno de multiprogramación con un algoritmo de planificación de la CPU por turno circular. Cuando un cuanto expira, el administrador de memoria intercambia a disco el proceso que acaba de terminar e intercambia a la memoria otro proceso, colocándolo en el espacio que se acaba de desocupar (Fig. 8.4). Mientras tanto, el planificador de la CPU asigna una porción de tiempo a algún otro proceso que está en la memoria. Cuando un proceso termina su cuanto, se intercambia con otro proceso. Idealmente, el administrador de memoria puede intercambiar procesos con la suficiente rapidez como para que siempre haya procesos en la memoria, listos para ejecutarse, cuando el planificador de la CPU desea reasignar la CPU. Además, el cuanto debe tener la duración suficiente para realizar un trabajo de cómputo razonable entre cada intercambio. En los algoritmos de planificación por prioridad se utiliza una variante de esta política de intercambio. Si un proceso con prioridad más alta llega y quiere servicio, el administrador de memoria puede intercambiar a disco el proceso de menor prioridad para poder cargar y ejecutar el de mayor prioridad. Cuando el proceso de prioridad más alta termina, el de prioridad más baja puede intercambiarse de vuelta a la memoria y reanudarse. Esta variante del intercambio se conoce como rodar hacia afuera, rodar hacia adentro (roll out, roll in). Normalmente, un proceso que se intercambia a disco se intercambiará de regreso al mismo espacio de memoria que ocupó previamente. Esta restricción depende del método de vinculación de direcciones. Si la vinculación se efectúa durante el ensamblado o durante la carga, el proceso no podrá transferirse a una posición distinta; si se usa vinculación durante la ejecución, será posible intercambiar un proceso a un espacio de memoria diferente, ya que las direcciones físicas se calculan en el momento de la ejecución. El intercambio requiere un almacenamiento auxiliar, que comúnmente es un disco rápido. Este almacenamiento debe tener el tamaño suficiente para dar cabida a copias de todas las imágenes de memoria de todos los usuarios, y debe proporcionar acceso directo a dichas imágenes. El sistema mantiene una cola de procesos listos que consiste en todos los procesos cuyas imágenes de memoria están en el almacenamiento auxiliar o en la memoria y que están listos para ejecutarse. Cada vez que el planificador de la CPU decide ejecutar un proceso, llama al despachador. Éste comprueba que el siguiente proceso de la cola esté en la memoria; si no es así, y no hay una región de memoria libre, el despachador intercambia a disco un proceso que sí está en la memoria y trae el proceso deseado. A continuación, el despachador vuelve a cargar los registros como siempre y transfiere el control al proceso seleccionado. Es obvio que el tiempo de conmutación de contexto en semejante sistema de intercambio es relativamente alto. Para darnos una idea de la magnitud de ese tiempo, supongamos que el proceso de usuario ocupa 100K y que el almacenamiento auxiliar es un disco duro estándar con una tasa de transferencia de un megabyte por segundo. La transferencia real del proceso de 100K a o de la memoria tarda 100K / 1000K por segundo = 1/10 segundos = 100 milisegundos. Si suponemos que la cabeza del disco no necesita moverse y que la latencia promedio es de 8 milisegundos, el intercambio tardará 108 milisegundos. Dado que se efectúa un intercambio en cada sentido, el tiempo de intercambio total es de 216 milisegundos. Para un aprovechamiento eficiente de la CPU, es deseable que el tiempo de ejecución de cada proceso sea grande en comparación con el tiempo de intercambio. Por ejemplo, en un esquema de planificación de la CPU por turno circular, el cuanto de tiempo debe ser mucho mayor que 0.216 segundos. Cabe señalar que la parte principal del tiempo de intercambio es el tiempo de transferencia. El tiempo de transferencia total es directamente proporcional a la cantidad de memoria que se intercambia. Si tenemos un sistema de computación con una memoria principal de un megabyte y un sistema operativo residente que ocupa 100K, el tamaño máximo de un proceso de usuario será 900K. Por otra parte, podría haber muchos procesos de usuario más pequeños, digamos de 100K. Un proceso de 100K podría intercambiarse a disco en 108 milisegundos, en comparación con los 908 milisegundos que tardaría el intercambio de 900K. Por tanto, sería útil saber exactamente cuánta memoria está usando realmente un proceso de usuario, no simplemente cuánta podría estar usando. Así, sólo necesitaríamos intercambiar lo que se está usando realmente, y el tiempo de intercambio se reduciría. Para que este esquema sea efectivo, el usuario debe mantener al sistema informado de cualesquier cambios que haya en las necesidades de memoria. Un proceso con necesidades de memoria dinámicas tendría que emitir llamadas al sistema (solicitar memoria y liberar memoria) para informar al sistema operativo de los cambios en sus necesidades de memoria. El intercambio tiene otras restricciones. Si queremos intercambiar un proceso, deberemos estar seguros de que está totalmente inactivo. Lo más importante es que no tenga E/S pendiente. Si un proceso está esperando una operación de E/S, tal vez querríamos intercambiarlo para desocupar su memoria, pero si la E/S está accediendo a la memoria de usuario de manera asincrónica porque maneja buffers de E/S, el proceso no podrá intercambiarse. Supongamos que la operación de E/S estaba encolada porque el dispositivo estaba ocupado. Si entonces intercambiáramos a disco el proceso P₁ e intercambiáramos a la memoria el proceso P2, la operación de E/S podría intentar usar memoria que ahora pertenece a P2. Las dos soluciones principales a este problema son (1) nunca intercambiar un proceso que tiene E/S pendiente, o (2) ejecutar las operaciones de E/S sólo con buffers del sistema operativo. Así, sólo ocurrirán transferencias entre la memoria del sistema operativo y la de un proceso cuando el proceso se intercambie a la memoria. El supuesto de que el intercambio no requiere, o requiere muy poco, movimiento de la cabeza del disco (búsqueda) merece mayor explicación. Pospondremos el análisis de esta cuestión hasta el capítulo 13, donde tratamos la estructura del almacenamiento secundario. En general, el espacio de intercambio se asigna como un área independiente del disco, aparte del sistema de archivos, con objeto de que su uso sea lo más rápido posible. Actualmente, el intercambio estándar se emplea en pocos sistemas, pues requiere demasiado tiempo de intercambio y ofrесе muy poco tiempo de ejecución como para ser una solución de gestión de memoria razonable. En muchos sistemas se emplеan versiones modificadas de la tècnica de intercambio. Una modificación del intercambio se usa en muchas versiones de UNIX. El intercambio normalmente está desactivado, pero se inicia si hay muchos procesos en ejecución y están ocupando una cantidad umbral de memoria. El intercambio se suspende otra vez si la carga del sistema disminuye. La gestión de memoria en UNIX se describe con detalle en la sección 21.6. Los primeros PC carecían de hardware avanzado (o de sistemas operativos que aprovecharan el hardware) para implementar métodos de gestión de memoria más sofisticados, pero se usaban para ejecutar múltiples procesos de gran tamaño empleando una versión modificada del intercambio. Un ejemplo importante es el sistema operativo Microsoft Windows 3.1, que apoya la ejecución concurrente de procesos en la memoria. Si se carga un proceso nuevo y no hay suficiente espacio en la memoria principal para él, un proceso viejo se intercambia a disco. Este sistema operativo no ofrece intercambio con todas las de la ley, porque es el usuario, no el planificador, el que decide cuándo se debe desalojar un proceso para dar cabida a otro. Cualquier proceso que se haya intercambiado a disco permanecerá ahí (sin ejecutarse) hasta que el usuario lo escoja. Los sistemas operativos de Microsoft posteriores, como Windows NT, aprovechan características de MMU avanzadas que ahora se encuentran incluso en los PC. En la sección 8.7.2 describiremos el hardware de gestión de memoria con que cuenta la familia de procesadores Intel 386 que se usan en muchos PC. En esa sección describiremos también la gestión de memoria que otro sistema operativo avanzado para PC, el IBM OS/2, emplea en la misma CPU. #### **8.4 Asignación contigua** La memoria principal debe dar cabida tanto al sistema operativo como a los diversos procesos de usuario. Generalmente, la memoria se divide en dos particiones, una para el sistema operativo residente y otra para los procesos de usuario. Es posible colocar el sistema operativo en memoria baja o alta. El factor principal que afecta esta decisión es la ubicación del vector de interrupciones. Puesto que dicho vector suele estar en la memoria baja, es más común colocar el sistema operativo en esa misma área. Por ello, sólo examinaremos la situación en la que el sistema operativo reside en memoria baja (Fig. 8.5). El tratamiento de la otra situación es similar. #### **8.4.1 Asignación con una sola partición** Si el sistema operativo reside en memoria baja y los procesos del usuario se ejecutan en memoria alta, necesitamos proteger el código y los datos del sistema operativo para que los procesos del usuario no los modifiquen (sea por accidente o con mala intención). También necesitamos proteger los procesos del usuario unos de otros. Podemos ofrecer tal protección utilizando un registro de reubicación, como se explicó en la sección 8.2, junto con un registro límite, como se explicó en la sección 2.5.3. El registro de reubicación contiene el valor de la dirección física más pequeña; el registro límite contiene el intervalo de direcciones lógicas (por ejemplo: reubicación = 100040 y límite 74600). Si se usan registros de reubicación y límite, toda dirección lógica debe ser menor que el registro límite; la MMU transforma la dirección lógica dinámicamente sumándole el valor que está en el registro de reubicación. Esta dirección transformada se envía a la memoria (Fig. 8.6). Cuando el planificador de CPU selecciona un proceso para ejecutarlo, el despachador carga los registros de reubicación y límite con los valores correctos como parte de la conmutación de contexto. Dado que cada dirección generada por la CPU se coteja con estos registros, podemos proteger tanto el sistema operativo como los programas y datos de otros usuarios contra una modificación por parte del proceso que está en ejecución. Cabe señalar que el esquema de registro de reubicación ofrece un mecanismo efectivo para poder variar dinámicamente el tamaño del sistema operativo. Esta flexibilidad es deseable en muchas situaciones. Por ejemplo, el sistema operativo contiene código y espacio de buffer para controladores de dispositivos. Si un controlador (u otro servicio del sistema operativo) no se usa comúnmente, no conviene mantener su código y sus datos en la memoria, pues podríamos aprovechar el espacio para otros fines. El código de este tipo se denomina código transitorio del sistema operativo, ya que viene y va según se necesita. El empleo de tal código modifica el tamaño del sistema operativo durante la ejecución de los programas. #### **8.4.2 Asignación con múltiples particiones** Dado que, en general, es deseable que varios procesos de usuario residan en la memoria al mismo tiempo, necesitamos considerar el problema de cómo repartir la memoria disponible entre los diversos procesos que están en la cola de entrada esperando ser transferidos a la memoria. Uno de los esquemas de asignación de memoria más sencillos consiste en dividir la memoria en varias particiones de tamaño fijo. Cada partición puede contener exactamente un proceso, y el grado de multiprogramación está limitado por el número de particiones. Si una partición está desocupada, se escoge un proceso de la cola de entrada y se carga en esa partición. Cuando el proceso termina, la partición queda disponible para otro proceso. Este esquema se utilizó originalmente en el sistema operativo IBM OS/360 (llamado MFT), pero ya no se usa. El esquema que describiremos a continuación es una generalización del esquema de particiones fijas (llamado MVT) y se emplea primordialmente en los entornos por lotes. Cabe señalar, empero, que muchas de las ideas que se presentan aquí también son aplicables a un entorno de tiempo compartido en el que se emplea segmentación pura para administrar la memoria (Sec. 8.6). El sistema operativo mantiene una tabla que indica cuáles partes de la memoria están disponibles y cuáles están ocupadas. Inicialmente, toda la memoria está disponible para los procesos de usuario, y se considera como un bloque grande de memoria disponible, o hueco. Cuando un proceso llega y necesita memoria, buscamos un hueco con el tamaño suficiente para ese proceso; si lo hallamos, asignamos sólo la memoria que se necesita, y el resto se deja disponible para satisfacer solicitudes futuras. Por ejemplo, supongamos que tenemos 2560K de memoria disponible y un sistema operativo residente de 400K. Esta situación deja 2160K para los procesos de usuario, como se muestra en la figura 8.7. Dada la cola de entrada de la figura, y planificación de trabajos FCFS, podemos asignar de inmediato memoria a los procesos P1, P2 y P3, para crear el mapa de memoria de la figura 8.8(a). Tenemos un hueco de 260K que ninguno de los procesos que quedan en la cola de entrada puede usar. Si empleamos planificación de la CPU por turno circular con un cuanto de una unidad de tiempo, el proceso P₂ terminará en el tiempo 14, y desocupará su memoria. Esta situación se ilustra en la figura 8.8(b). A continuación examinamos la cola de trabajos y planificamos el siguiente proceso, P4, para producir el mapa de memoria de la figura 8.8(c). El proceso P₁ terminará en el tiempo 28 para producir la figura 8.8(d); entonces, se planificará el proceso P5 y tendremos la figura 8.8(e). Este ejemplo ilustra la estructura general del esquema de asignación. A medida que los procesos ingresan en el sistema, se colocan en una cola de entrada. El sistema operativo considera las necesidades de memoria de cada proceso y la cantidad de memoria disponible, para determinar a cuáles procesos se les asignará memoria. Una vez que se asigna espacio a un proceso, se carga en la memoria y puede competir por la CPU. Cuando un proceso termina, libera su memoria, que el sistema operativo puede entonces llenar con otro proceso de la cola de entrada. En cualquier instante dado, tenemos una lista de los tamaños de bloque disponibles y la cola de entrada. El sistema operativo puede ordenar la cola de entrada según un algoritmo de planificación. Se asigna memoria a los procesos hasta que, finalmente, no es posible satisfacer las necesidades de memoria del proceso que sigue; no hay un bloque de memoria disponible (hueco) con el tamaño suficiente para contener ese proceso. El sistema operativo puede entonces esperar hasta que se libere un bloque suficientemente grande, o saltarse procesos en la cola de entrada para ver si es posible satisfacer las necesidades de algún otro proceso con el espacio disponible. En general, en un instante dado hay un conjunto de huecos, de diversos tamaños, dispersos en la memoria. Cuando un proceso llega y necesita memoria, buscamos en este conjunto un hueco con el tamaño suficiente para ese proceso. Si el hueco es demasiado grande, se divide en dos: una parte se asigna al proceso que llegó; la otra se devuelve al conjunto de huecos. Cuando un proceso termina, libera su bloque de memoria, que se coloca en el conjunto de huecos. Si el nuevo hueco está adyacente a otros, se fusionan los huecos adyacentes para formar un hueco mayor. En este punto, podría ser necesario determinar si hay procesos que esperan memoria y si esta memoria recién liberada y recombinada podría satisfacer las necesidades de cualquiera de los procesos que esperan. Este procedimiento es un caso particular del problema general de asignación dinámica de almacenamiento: cómo satisfacer una solicitud de tamaño n a partir de una lista de huecos libres. El problema tiene muchas soluciones. Se examina el conjunto de huecos para determinar cuál hueco conviene más asignar. Las estrategias de primer ajuste, mejor ajuste y peor ajuste son las que más se usan para seleccionar un hueco del conjunto de huecos disponibles. - **Primer ajuste:** Asignar el primer hueco que tenga el tamaño suficiente. La búsqueda puede iniciarse al principio del conjunto de huecos o en el punto en que terminó la búsqueda de primer ajuste anterior. Podemos dejar de buscar tan pronto como encontremos un hueco suficientemente grande. - **Mejor ajuste:** Asignar el hueco más pequeño que tenga el tamaño suficiente. Es preciso examinar toda la lista, a menos que ésta se mantenga ordenada por tamaño. Esta estrategia produce el hueco remanente más pequeño. - **Peor ajuste:** Asignar el hueco más grande. Una vez más, hay que examinar toda la lista, a menos que esté ordenada por tamaño. Esta estrategia produce el hueco remanente más grande, que podría ser más útil que el hueco pequeño que queda cuando se usa un enfoque de mejor ajuste. Se ha demostrado por medio de simulaciones que el primer ajuste y el mejor ajuste son mejores que el peor ajuste en términos tanto de reducción del tiempo como de aprovechamiento de la memoria. No hay una superioridad clara entre el primer ajuste y el mejor ajuste en términos de aprovechamiento de la memoria, pero el primer ajuste suele ser más rápido. #### **8.4.3 Fragmentación externa e interna** Los algoritmos que describimos en la sección 8.4.2 adolecen de fragmentación externa. A medida que se cargan procesos en la memoria y salen de ella, el espacio de memoria libre se divide en trozos pequeños. Hay fragmentación externa cuando se cuenta con suficiente espacio de memoria total para satisfacer una solicitud, pero el espacio no es contiguo; la memoria está fragmentada en un gran número de huecos pequeños. Si examinamos otra vez la figura 8.8, veremos dos situaciones de este tipo. En la figura 8.8(a) hay una fragmentación externa total de 260K, lo cual no alcanza para satisfacer las necesidades de ninguno de los dos procesos restantes, P4 y P5. En cambio, en la figura 8.8(c) tenemos una fragmentación externa de 560K (= 300K + 260K). Este espacio sería suficiente para ejecutar el proceso P5 (que necesita 500K), excepto que esta memoria libre no es contigua. El espacio libre está fragmentado en dos trozos, ninguno de los cuales es suficiente, por sí solo, para satisfacer la solicitud de memoria del proceso P5. Este problema de fragmentación puede ser grave. En el peor de los casos, podríamos tener un bloque de memoria libre (desperdiciada) entre cada dos procesos. Si toda esta memoria estuviera en un solo bloque libre, tal vez podríamos ejecutar varios procesos más. La selección de primer ajuste o mejor ajuste puede afectar el grado de fragmentación. (El primer ajuste es mejor en algunos sistemas; el mejor ajuste es preferible en otros.) Otro factor es cuál extremo de un bloque libre debe asignarse. (¿Cuál será la porción sobrante: la de arriba o la de abajo?) Sea cual sea el algoritmo que se use, la fragmentación externa será un problema. Dependiendo de la cantidad total de memoria y del tamaño promedio de los procesos, la fragmentación externa podría ser un problema importante o secundario. El análisis estadístico del enfoque de primer ajuste, por ejemplo, revela que, incluso con algo de optimación, si hay N bloques asignados, otros 0.5N bloques se perderán por fragmentación. Es decir, jun tercio de la memoria podría quedar inutilizado! Esta propiedad se conoce como regla del 50%. Otro problema que surge cuando se usa el esquema de asignación de múltiples particiones se ilustra en la figura 8.9. Consideremos el hueco de 18464 bytes. Supongamos que el siguiente proceso solicita 18462 bytes. Si asignamos exactamente el bloque solicitado, nos quedará un hueco de dos bytes. El gasto extra que implica seguir la pista a este hueco será mucho mayor que el hueco mismo. La estrategia general es asignar los huecos muy pequeños como parte de la solicitud. Así, la memoria asignada podría ser un poco mayor que la solicitada. La diferencia entre estos dos números es la fragmentación interna: memoria que está dentro de una partición, pero no se usa. Una solución al problema de la fragmentación externa es la compactación. El objetivo es desplazar el contenido de la memoria hasta tener toda la memoria libre junta en un solo bloque grande. Por ejemplo, el mapa de memoria de la figura 8.8(e) podría compactarse como se muestra en la figura 8.10. Los tres huecos de 100K, 300K y 260K podrían compactarse para tener un hueco de 660K. La compactación no siempre es posible. Observe que, en la figura 8.10, desplazamos los procesos P4 y P3. Para que estos procesos puedan ejecutarse en sus nuevas posiciones, es preciso reubicar todas las direcciones internas. Si la reubicación es estática y se efectúa durante el ensamblado o la carga, no puede haber compactación; ésta sólo es posible si la reubicación es dinámica y se efectúa en el momento de la ejecución. Si las direcciones se reubican dinámicamente, esto sólo requiere cambiar de lugar el programa y los datos y luego modificar el registro base para que refleje la nueva dirección base. Si la compactación es posible