Espacios de direcciones y traducción de direcciones

Un programa en ejecución trabaja con un espacio de direcciones: su propia vista de la memoria, con ubicaciones de bytes numeradas. El sistema operativo coloca la memoria del programa en la máquina y hace que sus direcciones lleguen a los bytes físicos correctos. La organización que ve el programa y la organización en el hardware son cosas distintas.

Por qué varios programas permanecen en memoria

Los primeros sistemas podían mantener un programa junto al sistema operativo. Por ejemplo, el sistema operativo podía ocupar los primeros 64 KB y el programa la memoria restante. La multiprogramación mantenía listo más de un proceso, de modo que la CPU podía trabajar mientras otro proceso esperaba una entrada o salida. El tiempo compartido cambiaba la CPU entre procesos con suficiente frecuencia para atender a usuarios interactivos.

Guardar en disco toda la memoria de un proceso en cada cambio haría que los cambios fueran demasiado lentos. Mantener varios procesos en la memoria física evita esa copia, pero crea un problema de protección. Una dirección generada por un proceso no debe permitirle sobrescribir el sistema operativo ni un proceso vecino.

Los tamaños de memoria aquí siguen la convención binaria usada en estos modelos: 1 KB son 1024 bytes, también expresados como 1 KiB; 1 MB son 1024 KB. Un espacio de direcciones de 16 KB tiene 16 384 ubicaciones de bytes, numeradas de 0 a 16 383. El número 16 384 es el límite final, no una dirección de byte válida.

Código, datos, montículo y pila

En una organización didáctica clásica de 16 KB, el código usa las direcciones bajas, desde 0 hasta el límite de 1 KB. El montículo comienza por encima del código y crece hacia arriba. La pila comienza en el límite superior y crece hacia abajo. El espacio libre entre ambos da a las dos regiones margen para crecer. Las organizaciones reales varían; por ejemplo, cada hilo tiene su propia pila. Las funciones de las regiones siguen siendo útiles incluso cuando cambian sus posiciones.

Sigue un puntero hasta la memoria correcta

Una dirección virtual identifica un byte en el espacio de direcciones de un proceso. Una dirección física identifica un byte en el hardware de memoria de la máquina. Cuando el código C imprime printf("%p", (void *) &x), imprime una dirección virtual. El puntero impreso no revela el byte físico que almacena x.

Supón que dos procesos usan ambos la dirección virtual 1000. Cada dirección se interpreta dentro del espacio de direcciones de su proceso, por lo que los accesos pueden llegar a bytes físicos diferentes. Del mismo modo, el código en la dirección virtual 0 no tiene por qué ocupar la dirección física 0. El sistema operativo puede colocarlo en otro lugar y configurar la traducción por hardware para acceder a él.

El procesador traduce las búsquedas de instrucciones, las cargas y los almacenamientos. El sistema operativo elige y gestiona las correspondencias, incluido el cambio de ubicaciones físicas mientras mantiene estables las direcciones virtuales del programa.

Un sistema de memoria debe hacer más que traducir correctamente un número. Debe permitir que los programas ordinarios se ejecuten sin gestionar la ubicación física, mantener bajo el coste de la traducción y hacer cumplir los límites que permiten compartir la memoria de forma segura. Estos requisitos son la transparencia, la eficiencia y la protección.

Mantén la vista del programa

La transparencia significa que un programa se ejecuta como si tuviera memoria privada. Usa sus propias direcciones para el código y los datos sin tener que seguir qué otros procesos están presentes ni dónde se encuentran sus bytes. El sistema operativo y el hardware mantienen esta vista de forma transparente. Mover un proceso en la memoria física no debería exigir que el proceso reescriba sus punteros.

La ilusión no requiere una copia física distinta de cada byte para cada proceso. Por ejemplo, el código protegido de solo lectura puede compartirse. Lo que importa es que la compartición mantenga el comportamiento y los derechos de acceso que corresponden a cada proceso.

Ten en cuenta ambos tipos de coste

Cada búsqueda de instrucción, carga y almacenamiento necesita traducción. Ejecutar una rutina del sistema operativo para cada acceso haría que la ejecución ordinaria fuera demasiado lenta. El hardware realiza las operaciones frecuentes; el código del sistema operativo se ocupa de la configuración, los cambios y los fallos.

La eficiencia en espacio también importa. Un mecanismo de traducción pequeño y rápido puede aun así desperdiciar una cantidad considerable de memoria. Una sola región de base y límite reserva el espacio sin usar entre el montículo y la pila. La segmentación evita asignar memoria física a ese espacio, pero introduce regiones físicas de tamaño variable y huecos entre ellas. Los metadatos, el espacio reservado sin usar y los huecos afectan a la cantidad de trabajo útil que cabe en la memoria.

Detén un acceso no permitido en el límite

Sin protección, un puntero erróneo en un editor de texto podría sobrescribir otro proceso o el núcleo. El daño podría aparecer mucho más tarde en código sin relación aparente. Cuando se hacen cumplir los límites, el hardware rechaza un acceso fuera de la región permitida y genera una excepción. El sistema operativo gestiona la excepción y suele terminar el proceso defectuoso, normalmente comunicando un fallo de segmentación.

La protección aísla los procesos entre sí. No hace que el uso de la memoria en C sea seguro dentro de una región permitida del montículo. Una escritura que sobrepasa un bloque asignado puede alcanzar otro bloque del mismo proceso. Los límites de los procesos y los límites de los bloques del asignador son distintos.

Separa la operación de la decisión

Un mecanismo es la forma de realizar una operación. Sumar el valor de un registro base y comprobar un registro límite son mecanismos. Una política elige entre las acciones posibles: dónde colocar un proceso, qué hueco libre usar o cuándo mover un segmento.

Mantenerlos separados permite al sistema operativo cambiar su estrategia de colocación y conservar la misma traducción por hardware. La virtualización de memoria comienza con esta vista privada y protegida; no se define por el uso del disco como memoria adicional.

Una variable puntero y la memoria a la que apunta son objetos separados. Comprender sus tiempos de vida es el punto de partida para la API de memoria de C. Las variables locales ordinarias suelen usar almacenamiento automático en la pila, los bloques del montículo duran hasta que se liberan y las variables globales y locales static tienen almacenamiento durante toda la ejecución del programa.

Sigue la asignación, no solo el puntero

void f(void) {
    int x;
    int *p = malloc(sizeof(int));
}

En la organización habitual de la pila, x y p pertenecen a esta llamada a f. El entero solicitado pertenece al montículo. El retorno elimina la variable puntero local, pero no libera el bloque del montículo. Si no queda ninguna copia de la dirección, el programa ha perdido el acceso a un bloque asignado vigente: una fuga de memoria.

malloc(size) solicita al menos esa cantidad de bytes y devuelve un puntero, o NULL cuando no puede atender la solicitud. Sus bytes no están inicializados para el programa. Para 10 enteros, usa malloc(10 * sizeof(int)); donde un entero ocupa 4 bytes, eso solicita 40 bytes. Para una cadena, reserva espacio para sus caracteres más un byte para el carácter nulo de terminación: malloc(strlen(s) + 1).

sizeof(a) mide el objeto llamado a. Si a es un puntero, da el tamaño del puntero, no el de la asignación. Un puntero de 8 bytes puede referirse a un bloque de 40 bytes.

Conoce qué hace cada operación de la biblioteca

free recibe el puntero devuelto, sin un argumento de tamaño. El asignador conserva metadatos de tamaño, normalmente en una cabecera antes del bloque. Pasa el puntero devuelto para un bloque actualmente asignado; un puntero al interior del bloque no es un sustituto válido. free(NULL) es válido y no hace nada. Estas funciones son rutinas de la biblioteca C, no llamadas al sistema.

Reconoce el error por el tiempo de vida o el límite

Un puntero sin una asignación válida no puede usarse como si ya apuntara a un espacio de almacenamiento. Leer bytes recién asignados antes de inicializarlos es una lectura de memoria sin inicializar. Escribir más allá del final asignado es un desbordamiento de búfer; omitir el byte de terminación de una cadena puede causarlo.

Después de free, los punteros antiguos al bloque quedan colgantes. Acceder mediante uno de ellos es un uso después de la liberación. Liberar el bloque de nuevo es una doble liberación de memoria. Liberar una dirección que el asignador no devolvió para un bloque vigente es una liberación no válida. Perder un bloque por una fuga es distinto: el bloque permanece asignado, pero el programa deja de liberarlo cuando debería.

Comprende qué puede comprobar el hardware

La compilación puede tener éxito pese a todos estos errores. El hardware suele comprobar las regiones y los permisos del proceso, no cada asignación de la biblioteca. Cruzar el límite de un bloque mientras se permanece dentro del montículo permitido del proceso puede tener un comportamiento indefinido sin provocar un fallo inmediato. El programa puede corromper datos, fallar más tarde, leer valores sin sentido o parecer que funciona. Valgrind y AddressSanitizer pueden detectar muchos de estos errores durante la ejecución.

La biblioteca C y el sistema operativo gestionan la memoria a distintas escalas. El sistema operativo establece regiones en el espacio de direcciones de un proceso y les proporciona memoria física. El asignador divide la memoria disponible del montículo en bloques, registra los bloques libres y los reutiliza entre llamadas.

Mueve el límite del montículo

El límite del montículo es la dirección situada justo después del final del montículo tradicional. brk establece ese límite en una dirección elegida. sbrk(n) lo desplaza un incremento de bytes y, si tiene éxito, devuelve el límite anterior. sbrk(0) indica el límite actual sin moverlo.

Supón que el límite es 40 960 y que el asignador llama correctamente a sbrk(8192). El valor devuelto es 40 960. El nuevo límite es:

Los bytes añadidos ocupan las direcciones virtuales de 40 960 a 49 151. El nuevo límite, 49 152, está justo después de la región añadida. Confundir el valor devuelto con el nuevo límite desplaza todos los cálculos posteriores de colocación.

Las aplicaciones usan la biblioteca de asignación en lugar de mover el límite directamente. La biblioteca lleva el registro de las partes de su región que le pertenecen. Los cambios independientes en ese límite pueden invalidar sus registros.

Obtén un mapeo separado

mmap puede crear una región anónima: memoria no asociada a un archivo, inicialmente llena de bytes de valor cero. munmap elimina un mapeo. Un asignador puede usar mapeos separados para asignaciones grandes y devolver esos mapeos al sistema operativo cuando se liberan.

En glibc, el umbral inicial predeterminado para esta vía es de 128 KB, o 131 072 bytes, y puede aumentar. Una asignación suficientemente grande suele mapearse por separado si no puede atenderse con el espacio libre existente. Esta es una política de la biblioteca, no un límite universal del lenguaje C.

Libera a nivel de biblioteca o de sistema operativo

Una llamada a free suele devolver un bloque pequeño a la reserva de la biblioteca. Por ello, el proceso puede mostrar después la misma ocupación de memoria. La memoria está disponible para reutilizarse sin otra solicitud al sistema operativo.

La terminación del proceso recupera incluso las asignaciones que el programa perdió por fugas. Sin embargo, durante la vida de un servidor de larga duración, las fugas repetidas siguen consumiendo su memoria disponible. Recuperar la memoria al terminar no evita esa presión mientras se ejecuta.

Relaciona el crecimiento del montículo con la traducción

En el modelo de segmentación, el montículo es un segmento físico contiguo. Ampliarlo requiere bytes físicos libres justo encima de él. Si esos bytes están ocupados, el sistema operativo puede mover el segmento a un hueco mayor y actualizar su estado de traducción. Si no hay una región adecuada disponible, la ampliación falla. Si el asignador no puede obtener suficiente espacio, malloc devuelve NULL.

La reubicación dinámica traduce direcciones mientras se ejecuta un programa. En el modelo de base y límite, un proceso ocupa una región física contigua. Comienza con espacios de direcciones del mismo tamaño que caben en la memoria física; un par de registros describe entonces la región del proceso que se ejecuta en ese momento.

Comprueba primero la dirección virtual

El registro base contiene la dirección física del primer byte de la región. El registro límite contiene el tamaño de la región en bytes. Para una dirección virtual no negativa, la regla es:

Si se supera la comprobación:

De lo contrario, el hardware genera una excepción. Un tamaño es una cantidad, por lo que la dirección igual al límite ya está fuera de la región. Las direcciones virtuales negativas también son inválidas.

Recorre los límites de bytes

Considera un espacio de direcciones de 8 KB con base 20 480 y límite 8192. Sus bytes virtuales van de 0 a 8191. La dirección virtual 1000 supera la comprobación y accede al byte físico 21 480. El último byte virtual permitido, 8191, accede a 28 671. La dirección 9000 falla porque es al menos 8192; el hardware debe rechazarla antes de realizar el acceso físico.

Las búsquedas de instrucciones usan la misma traducción que los datos. Si una instrucción en la dirección virtual 128 carga desde la dirección virtual 3000, la búsqueda accede a la dirección física 20 608 y la carga accede a 23 480. Son dos accesos a memoria con dos direcciones traducidas, no una única traducción compartida para toda la instrucción.

Distingue las convenciones del límite

La misma región de 8 KB tiene el límite físico final 28 672. Ambas convenciones permiten exactamente los bytes de 20 480 a 28 671. Comparar la dirección física 21 480 con el tamaño 8192 mezcla las dos convenciones y rechaza incorrectamente un acceso permitido.

Mueve la memoria sin cambiar los punteros

La MMU, o unidad de gestión de memoria, realiza las comprobaciones y la suma. El sistema operativo puede pausar un proceso, copiar su región a otro lugar y cambiar la base. El proceso sigue usando las mismas direcciones virtuales, por eso la reubicación es dinámica.

En la reubicación estática, en cambio, un cargador reescribe las direcciones incorporadas al cargar el código. Reescribir una referencia de 1000 a 21 480 registra una ubicación física en el programa. Moverlo más tarde requiere nuevas reescrituras, y la reescritura por sí sola no impide que un programa construya una dirección fuera de su región.

Suma la base solo a una dirección virtual. Sumarla a una dirección física ya traducida desplaza la ubicación por segunda vez y destruye la correspondencia.

El hardware mantiene los registros de traducción del proceso que se ejecuta en una CPU. El sistema operativo conserva el estado guardado de los procesos que esperan. La protección depende de que solo el código privilegiado del sistema operativo tenga capacidad para cambiar ese estado.

Proporciona las operaciones de hardware

La CPU necesita los modos usuario y núcleo, un par de base y límite en su MMU y circuitos para la comprobación y la suma. También necesita operaciones privilegiadas para cambiar el par e instalar manejadores de excepciones. Las direcciones no permitidas y los intentos de ejecutar instrucciones privilegiadas en modo usuario deben generar excepciones.

Si un programa de usuario pudiera cambiar su base, podría redirigir sus direcciones al núcleo o a otro proceso. Las comprobaciones de límite protegerían entonces la región equivocada. Restringir las actualizaciones forma parte, por tanto, del mecanismo de protección, no es solo una comodidad administrativa.

Crea y ejecuta un proceso

Durante el arranque, el sistema operativo instala sus manejadores de trampas y excepciones, inicia el temporizador de interrupciones y prepara sus registros de memoria libre. Cuando comienza un proceso, el sistema operativo encuentra una ranura física para su espacio de direcciones. Con ranuras de igual tamaño, una lista de bloques libres puede simplemente registrar cuáles están sin usar.

El sistema operativo marca la ranura elegida como ocupada, registra la base y el límite del proceso, carga los registros y entra en modo usuario. El proceso se ejecuta entonces directamente en la CPU. El hardware traduce los accesos ordinarios sin llamar al sistema operativo por cada byte.

Restaura el par correcto en un cambio de contexto

Una interrupción del temporizador transfiere el control al sistema operativo. Este guarda los registros del proceso anterior, incluidos la base y el límite, en su bloque de control de proceso y después restaura los valores del siguiente proceso antes de volver al modo usuario.

Supón que la base de A es 20 480 y la de B es 40 960, ambas con límite 8192. La dirección virtual 1000 de A accede a 21 480. Después de cambiar a B, el mismo número virtual accede a 41 960. Restaurar los registros de la CPU sin restaurar el estado de traducción haría que B accediera a la región de A usando los punteros de B.

La CPU tiene el par activo; cada proceso tiene su propio par guardado. No imagines un único par permanente para toda la máquina ni supongas que los pares de todos los procesos están activos simultáneamente en una CPU.

Mueve, gestiona fallos y termina

Para mover A a la dirección física 49 152, el sistema operativo retira A de la ejecución, copia su región de 8 KB y actualiza la base guardada de A. Una vez que A se reanuda con esa base instalada, la dirección virtual 1000 accede a 50 152. Sus valores de puntero virtual no necesitan cambios.

Ante un acceso no válido, el hardware genera una excepción y transfiere la ejecución al modo núcleo en el manejador registrado. El sistema operativo suele terminar el proceso que causó el acceso. Al terminar, devuelve la ranura a la lista de bloques libres y libera los registros del proceso.

Base y límite cumple dos objetivos con poco coste: la traducción es transparente y cada dirección se comprueba frente a la región asignada. Su principal debilidad es la relación entre esa región y los bytes que el proceso usa realmente.

Reserva toda la extensión

El hardware solo necesita una suma y una comparación en la ruta frecuente. Un asignador de ranuras de tamaño fijo también puede elegir rápidamente una ranura libre. Ninguna de estas ventajas significa que la ranura esté llena de datos útiles.

En la organización clásica, el código y el montículo están cerca de un extremo y la pila cerca del otro. Un par de base y límite traduce todo el intervalo. El espacio sin usar entre el montículo y la pila ocupa memoria física igual que las partes útiles.

Para un espacio de direcciones de 16 KB que usa 1 KB de código, 2 KB de montículo y 1 KB de pila:

El desperdicio es fragmentación interna: bytes sin usar dentro de una región ya asignada a un proceso. No se debe a que el asignador del montículo elija mal un bloque. Incluso un montículo de 2 KB perfectamente aprovechado deja reservado el gran espacio intermedio.

Distingue tres cuestiones de tamaño

La extensión del espacio de direcciones, los bytes usados actualmente y la memoria física disponible son cantidades distintas. Un espacio de 32 bits direccionado por bytes abarca $2^{32}$ bytes, o 4 GB. Reservarlo como un solo bloque físico requiere los 4 GB completos aunque el proceso solo use actualmente unos pocos megabytes.

Hacer que las ranuras tengan tamaños variables elimina la restricción de igual tamaño, pero no elimina la necesidad de un hueco contiguo. También crea un problema de colocación: el sistema operativo debe elegir entre huecos libres de distintos tamaños. Reducir una ranura no puede mantener tanto las direcciones bajas del código como una dirección alta y distante de la pila si toda la extensión debe seguir siendo válida en el mismo mapeo sencillo.

Reubica las regiones por separado

El código, el montículo y la pila no tienen que ser vecinos en la memoria física para mantener la vista del programa. Dar a cada uno su propia base y límite permite al sistema operativo asignar solo sus extensiones usadas y dejar el espacio virtual sin memoria física asignada. Esto es la segmentación, la generalización de un par de reubicación a varias regiones lógicas.

Para la organización de 16 KB anterior, las tres regiones usadas solo necesitan 4 KB en total antes de su propia sobrecarga de gestión. El ahorro de espacio procede de cambiar lo que se reubica como una unidad, no de hacer más rápida la suma del registro base.

Un segmento es una región contigua de un espacio de direcciones con un propósito. En el modelo clásico, el código, el montículo y la pila reciben cada uno un par de base y tamaño. Sus regiones físicas pueden colocarse de forma independiente aunque el proceso conserve su organización virtual habitual.

Asigna memoria física solo a las extensiones usadas

Usa un espacio de direcciones de 16 KB con las siguientes ubicaciones. Los tamaños usan KB binarios, o KiB.

El código y el montículo crecen hacia direcciones mayores; la traducción de la pila usa su límite superior y un desplazamiento negativo. Las tres regiones físicas usan solo 7 KB en total. Los huecos virtuales entre ellas no necesitan almacenamiento físico. Cada segmento sigue siendo contiguo; lo que ya no requiere adyacencia es la relación entre segmentos.

Traduce un segmento que crece hacia arriba

Primero identifica el segmento. Después calcula el desplazamiento desde su comienzo virtual. Comprueba que el desplazamiento no sea negativo y que sea menor que su tamaño actual; luego súmalo a la base física:

Para la dirección virtual 500, el desplazamiento dentro del código es 500. Es menor que 2048, por lo que el acceso llega a la dirección física 41 460.

Para la dirección virtual 5000, el desplazamiento dentro del montículo es:

La comprobación del tamaño se supera porque 904 es menor que 3072. El resultado es:

Sumar la dirección virtual completa a la base del montículo produciría 31 624. Eso incorpora por error la posición inicial virtual del montículo a un cálculo que solo necesita la distancia dentro del segmento.

Comprueba el segmento, no solo la extensión del espacio de direcciones

La dirección virtual 7500 cabe en 14 bits, pero eso no significa que esté permitida. Su desplazamiento dentro del montículo es 3404, fuera de la extensión actual de 3072 bytes. El hardware genera una excepción. Una dirección puede estar, por tanto, dentro de la extensión total del espacio de direcciones y aun así fuera de todas las regiones válidas.

El término fallo de segmentación se originó con los accesos segmentados no válidos y sigue usándose para accesos no permitidos en sistemas con otros esquemas de traducción. El nombre del error por sí solo no identifica el mecanismo de traducción de la máquina.

Antes de que el hardware pueda usar la base y el tamaño de un segmento, debe decidir a qué segmento se refiere un acceso. Un diseño explícito sitúa esa elección en bits de la dirección. Un diseño implícito la deduce de la forma en que la CPU creó la dirección.

Divide una dirección de 14 bits

Asigna los dos bits superiores al número de segmento y los doce bits inferiores al desplazamiento. El campo de dos bits tiene cuatro valores posibles. Usa 00 para código, 01 para montículo y 11 para pila; deja 10 sin usar.

El campo de desplazamiento puede representar 4096 valores distintos, de 0 a 4095. Por tanto, la ventana virtual máxima de cada segmento es de 4 KB, incluso cuando la extensión válida actual del segmento es menor. La capacidad máxima y el tamaño actual son límites distintos.

Para la dirección virtual 5000, la representación de 14 bits es:

01 0011 1000 1000

El 01 inicial selecciona el montículo. El 0011 1000 1000 restante es 904 en decimal. Con un tamaño de montículo de 3072 y una base física de 26 624, el desplazamiento supera la comprobación de tamaño y llega a la dirección física 27 528.

Usa una máscara y un desplazamiento de bits

La misma división puede expresarse como código:

segment = (va & 0x3000) >> 12;
offset = va & 0x0FFF;

La máscara 0x3000 conserva los dos bits selectores; desplazarlos doce posiciones los mueve a las posiciones inferiores para obtener el número de segmento. La máscara 0x0FFF pone a cero esos bits selectores y conserva el desplazamiento. Para va = 0x1388, los resultados son el segmento 1 y el desplazamiento 0x388, o 904.

No sumes 0x1388 directamente a la base del montículo. Ese valor incluye tanto el selector de segmento como el desplazamiento. El selector elige los registros; solo el desplazamiento interviene en la traducción dentro del segmento. La dirección física resultante no necesita conservar el patrón de bits del selector.

Reconoce el coste de la división

Un selector de dos bits crea cuatro ventanas. Dejar 10 sin usar hace que una cuarta parte de la extensión virtual de 16 KB no esté disponible. Ningún segmento puede crecer más allá de su ventana de 4 KB solo porque quede libre más memoria física. Otros diseños pueden usar una división distinta; combinar el código y el montículo en un segmento permite que un solo bit selector lo distinga de la pila.

Deja que el tipo de acceso elija

En un diseño implícito, las búsquedas de instrucciones usan el segmento de código porque su dirección procede del contador de programa. Las referencias basadas en el puntero de pila o en el puntero de marco usan el segmento de pila. Los demás accesos usan el segmento de montículo en este modelo simplificado.

La pila crece hacia direcciones menores. Su traducción necesita un bit de dirección de crecimiento además de una base y un tamaño. En este modelo, 1 indica crecimiento hacia arriba y 0 crecimiento hacia abajo. Los permisos de acceso añaden otra comprobación independiente: un byte puede estar dentro de los límites y aun así no permitir la operación solicitada.

Trata la base de la pila como un límite superior

En un segmento que crece hacia arriba, la base identifica su primer byte físico. En un segmento que crece hacia abajo, la base identifica el límite situado justo después de su byte físico de dirección más alta. En la organización del ejemplo, una base de pila de 53 248 y un tamaño de 2048 abarcan los bytes físicos de 51 200 a 53 247.

Para la ventana de pila de 4 KB seleccionada por 11, convierte el campo de desplazamiento de doce bits en un desplazamiento negativo:

El campo va de 0 a 4095, por lo que este desplazamiento siempre es negativo. Es válido cuando su magnitud no supera el tamaño actual de la pila. Después suma el desplazamiento con signo a la base.

Resuelve un acceso permitido a la pila

La dirección virtual 15 500 selecciona la pila. Su ventana comienza en la dirección virtual 12 288, por lo que su campo de desplazamiento es 3212. Convierte el campo:

La profundidad 884 está dentro del tamaño 2048. La traducción da:

Sumar el valor positivo 3212 a la base apuntaría por encima de la pila. El campo todavía no es el desplazamiento necesario para un segmento que crece hacia abajo.

La dirección virtual 13 000 da, en cambio, el campo 712 y el desplazamiento −3384. Su profundidad supera 2048, por lo que el hardware genera un fallo. Si el sistema operativo amplía la pila correctamente, el aumento de su tamaño puede hacer que más direcciones bajas sean válidas.

Incluye el extremo inferior

Un desplazamiento de −2048 llega al byte de dirección más baja de la pila, 51 200, y está permitido. Un desplazamiento de −2049 queda fuera. La comprobación para crecimiento hacia abajo incluye, por tanto, la magnitud igual al tamaño. Esto coincide con el número de bytes de la regla para crecimiento hacia arriba, aunque esa regla excluye un desplazamiento igual al tamaño: la base para crecimiento hacia arriba es un byte, mientras que la base para crecimiento hacia abajo es un límite final.

Comprueba la operación solicitada

Los bits de protección registran los permisos de lectura, escritura y ejecución. El código suele ser de lectura y ejecución; el montículo y la pila suelen ser de lectura y escritura. Una escritura en código de lectura y ejecución provoca un fallo incluso cuando su desplazamiento es válido. Ejecutar datos también provoca un fallo cuando no hay permiso de ejecución.

El código de solo lectura puede compartirse. El sistema operativo puede hacer que los segmentos de código de dos procesos apunten a la misma región física y denegar la escritura en ambos. Los bytes de instrucciones ocupan una sola copia física, mientras cada proceso conserva un montículo y una pila separados.

La segmentación sustituye una región grande por varias más pequeñas. Esto evita asignar memoria física a los huecos virtuales vacíos, pero ahora el sistema operativo debe colocar y ampliar regiones de distintos tamaños mientras conserva el estado de traducción de cada proceso.

Guarda todas las partes del mapeo

En un cambio de contexto, la base y el tamaño ya no bastan. El sistema operativo guarda y restaura la base, el tamaño, la dirección de crecimiento y los permisos de cada segmento. Restaurar una pila con la dirección equivocada o código con permisos incorrectos cambiaría el significado de direcciones por lo demás idénticas.

Cuando un asignador necesita más espacio de montículo, el sistema operativo debe ampliar el segmento físico del montículo. Los bytes libres situados justo encima permiten el crecimiento directo. De lo contrario, el sistema operativo puede moverlo a un hueco mayor adecuado y actualizar su base. Si no puede obtener una región adecuada, la ampliación falla.

Elige la granularidad

Multics usaba segmentación de grano fino. Más segmentos permiten unidades de control más pequeñas, pero requieren más metadatos de traducción y gestión.

Encuentra un hueco suficientemente grande

Los segmentos físicos de tamaño variable dejan huecos libres de distintos tamaños cuando los procesos comienzan, crecen y terminan. La fragmentación externa ocurre cuando hay suficientes bytes libres en total, pero ningún hueco por sí solo puede contener el segmento solicitado.

Supón que los huecos libres son de 8 KB, 6 KB y 10 KB. Su total es 24 KB. Un segmento de montículo de 12 KB sigue sin caber: el hueco disponible más grande es de solo 10 KB. Unir los huecos sobre el papel no hace que sus direcciones físicas sean adyacentes.

La compactación puede corregir esta organización. El sistema operativo pausa los procesos, copia los segmentos uno junto a otro y actualiza sus bases. Las direcciones virtuales siguen funcionando porque la traducción oculta los movimientos físicos. El resultado es una región libre grande y contigua, pero la copia es costosa y las nuevas asignaciones pueden volver a fragmentar la memoria.

Las políticas de colocación, como el primer ajuste y el mejor ajuste, intentan limitar los sobrantes inadecuados sin copiar. Ninguna política de colocación de tamaños variables elimina la fragmentación externa para todas las secuencias de solicitudes. Un único segmento grande también puede desperdiciar espacio dentro de su propia extensión cuando solo se usan partes dispersas.

Reconoce el modelo en los sistemas modernos

La paginación divide la memoria en piezas de tamaño fijo y evita exigir que cada región lógica ocupe un solo hueco físico. El modelo de segmentación sigue siendo útil para comprender las regiones, la protección y la compartición. En el modo de 64 bits de x86-64, las bases ordinarias de segmentación de código, datos y pila actúan como cero y sus límites no se comprueban; FS y GS conservan bases útiles para datos por hilo o por CPU. Un mensaje de acceso no permitido llamado fallo de segmentación no significa que el modelo clásico de tres segmentos esté activo.

La gestión del espacio libre registra la memoria disponible y elige dónde colocar cada solicitud. Las solicitudes de igual tamaño pueden usar una lista de bloques intercambiables. Los tamaños variables son más difíciles: tanto un asignador del montículo como un sistema operativo que coloca segmentos deben encontrar un bloque contiguo suficientemente grande para la siguiente solicitud.

Localiza la fragmentación externa

Considera una región de 60 bytes con los bytes 0–19 libres, un bloque asignado en 20–39 y los bytes 40–59 libres. Hay cuarenta bytes libres, pero ninguno de los huecos libres puede contener una solicitud de 25 bytes. El bloque vigente del medio impide tratar esos huecos como una sola región.

Esto es fragmentación externa: hay capacidad libre fuera de los bloques asignados, pero su disposición la hace inutilizable para una solicitud contigua concreta. Los bytes libres no han desaparecido. Aún pueden atender solicitudes más pequeñas o resultar útiles cuando se liberan los bloques intermedios.

Localiza la fragmentación interna

Un asignador que redondea las solicitudes a múltiplos de 16 entrega un bloque de 32 bytes para una solicitud de 20 bytes. Los 12 bytes adicionales están dentro de una asignación ya entregada. Ese desperdicio es fragmentación interna.

El espacio sin usar entre el montículo y la pila en una ranura de base y límite es otro ejemplo. La asignación por bloques compañeros introduce el mismo tipo de desperdicio al redondear a potencias de dos. El nivel de gestión es distinto, pero la ubicación del espacio sin usar es la característica que lo define.

Un mismo asignador puede sufrir ambas. Redondear una solicitud puede desperdiciar bytes dentro de su bloque mientras otros bloques libres permanecen separados en otra parte.

Fusiona vecinos libres sin mover datos vigentes

La fusión de bloques libres adyacentes une bloques libres físicamente adyacentes. Si se libera el bloque del medio de la región de 60 bytes, las tres partes pueden unirse en un hueco de 60 bytes. Si el bloque del medio sigue asignado, la fusión no puede atravesarlo. La fusión reduce la fragmentación externa, pero no garantiza un hueco suficientemente grande para cada solicitud.

Añadir más memoria a un montículo puede aliviar la presión, pero no cambia las direcciones de los bloques vigentes. Su colocación aún puede dejar pequeños huecos inutilizables.

Explica por qué el sistema operativo puede compactar segmentos

El sistema operativo puede copiar segmentos físicos y actualizar sus bases. Los programas conservan las direcciones virtuales, por lo que el mapeo puede ocultar esos movimientos. Un asignador general del montículo de C carece de una capa de traducción entre los punteros devueltos y las ubicaciones dentro del montículo. Un programa puede haber copiado un puntero en muchos objetos y el asignador no puede descubrir ni reescribir cada copia.

Mover un bloque vigente del montículo por sí solo dejaría esos punteros apuntando a su ubicación anterior. Por ello, la gestión ordinaria de malloc mantiene los bloques vigentes en las direcciones devueltas hasta que se liberan. Debe gestionar la fragmentación mediante la colocación, la reutilización, la división y la fusión del espacio libre.

Una lista de bloques libres registra los bloques libres por dirección y tamaño. La asignación divide un bloque o lo elimina de la lista; la liberación devuelve un bloque y puede fusionarlo con sus vecinos. La convención de tamaño importa: un tamaño registrado puede indicar la carga útil utilizable o el bloque completo con sus metadatos.

Divide y fusiona intervalos sencillos

Ignora primero las cabeceras. En una región de 60 bytes con entradas libres (0, 20) y (40, 20), una solicitud de 8 bytes colocada al comienzo devuelve la dirección 0. Las entradas restantes son (8, 12) y (40, 20).

Partiendo de nuevo de la organización original, libera los bytes asignados del medio, 20–39. Sin fusión, tres entradas de 20 bytes siguen sin poder atender individualmente una solicitud de 30 bytes. Fusionar los intervalos adyacentes produce (0, 60), que sí puede atenderla. El orden por dirección ayuda al asignador a reconocer los vecinos; la adyacencia en la lista por sí sola no basta si sus intervalos físicos no se tocan.

Recupera la cabecera a partir del puntero del usuario

free(ptr) no recibe un tamaño. Un asignador sencillo guarda una cabecera de tamaño justo antes de la carga útil, a veces con un valor de comprobación o número mágico. Restar la longitud de la cabecera permite encontrar los metadatos.

Con una cabecera de 16 bytes, una solicitud de 96 bytes ocupa 112 bytes en total. El programa recibe un puntero situado 16 bytes después del comienzo del bloque. Al liberarlo se devuelve toda la extensión de 112 bytes, incluida la cabecera, para su gestión futura. La alineación puede añadir redondeo; los tamaños de estos ejemplos ya cumplen una alineación de 16 bytes.

Sigue una lista de bloques libres integrada

Supón que un montículo de 4096 bytes comienza en 32 768. Un nodo libre usa 16 bytes y registra los bytes utilizables después del nodo. Inicialmente registra 4080 bytes utilizables.

Tres solicitudes de 96 bytes consumen 112 bytes cada una:

El nodo libre restante comienza en 33 104. Su tamaño utilizable es de 3744 bytes. La contabilización es:

Liberar el puntero 32 896 permite encontrar la cabecera en 32 880. Ese bloque se convierte en un nodo libre con 96 bytes utilizables. No puede unirse al nodo final en 33 104 porque la tercera asignación está entre ambos. Cuando se liberan y fusionan las tres asignaciones, un solo nodo vuelve a describir 4080 bytes utilizables. Al absorber las antiguas cabeceras interiores, sus bytes quedan disponibles dentro de la extensión fusionada.

Mantén los registros dentro de la región gestionada

Los nodos integrados de la lista están en la propia memoria libre, por lo que gestionar la lista no requiere una asignación separada para cada entrada. El nodo contiene un tamaño y un enlace al siguiente bloque libre. Si ningún bloque sirve, el asignador puede solicitar más memoria con sbrk o mmap; si no consigue suficiente memoria, devuelve NULL.

Un desbordamiento puede sobrescribir una cabecera o un nodo vecino. Esto explica por qué el fallo visible puede producirse durante una llamada posterior a malloc o free, después de la escritura que dañó la lista.

Una política de colocación elige entre los bloques suficientemente grandes para una solicitud. Las distintas elecciones dejan huecos diferentes para solicitudes futuras. El tiempo de búsqueda importa junto con la fragmentación, y ninguna política gana para todas las cargas de trabajo.

Compara las reglas de búsqueda

Para el mejor y el peor ajuste, una lista sencilla sin ordenar necesita una búsqueda completa. Otras estructuras pueden encontrar tamaños adecuados más rápidamente. Primer ajuste significa primero en el orden elegido para la lista, lo que no tiene por qué significar la dirección más baja, salvo que la lista esté ordenada por dirección.

Sigue la primera solicitud

Considera bloques libres de 30, 12, 50 y 20 bytes en orden de dirección. Ignora las cabeceras y supón que la división puede conservar cada sobrante. Una solicitud de 18 bytes cambia la lista de la siguiente manera:

• El mejor ajuste usa 20 y deja 30, 12, 50, 2.
• El peor ajuste usa 50 y deja 30, 12, 32, 20.
• El primer ajuste usa 30 y deja 12, 12, 50, 20.
• El siguiente ajuste, si comienza en el cuarto bloque, usa 20 y deja 30, 12, 50, 2.

El siguiente ajuste necesita una posición inicial para determinar su elección. El nombre por sí solo no implica que sea la primera entrada de la lista. Un seguimiento debe conservar ese estado de búsqueda entre solicitudes.

Observa por qué la siguiente solicitud cambia la evaluación

Una solicitud posterior pide 45 bytes. El mejor ajuste y el primer ajuste conservaron el bloque de 50 bytes, por lo que ambos tienen éxito. El bloque restante más grande del peor ajuste es de 32 bytes, por lo que falla pese a tener 94 bytes libres en total:

Este fallo es fragmentación externa. La decisión anterior dividió el único hueco suficientemente grande. Por otra parte, el mejor ajuste dejó un fragmento de 2 bytes que puede ser demasiado pequeño para solicitudes futuras útiles. Un resto pequeño inmediato no demuestra que una política vaya a usar bien el espacio durante toda la secuencia de solicitudes.

Equilibra la política y la estructura de datos

Recorrer miles de entradas puede ser costoso incluso cuando cada colocación es buena. Los asignadores prácticos agrupan los bloques por tamaño o usan estructuras que facilitan la búsqueda, como árboles equilibrados. Una lista ordenada por dirección también facilita la fusión al hacer que los vecinos físicos sean más fáciles de encontrar.

El mecanismo de asignación (buscar, dividir, actualizar metadatos) puede seguir siendo el mismo mientras cambia la política. Para comparar políticas de forma justa, sigue las mismas solicitudes y liberaciones, mantén fijas las reglas de sobrecarga y ten en cuenta tanto los huecos resultantes como la cantidad de búsqueda.

La búsqueda general en una lista de bloques libres es flexible, pero puede ser costosa. Los asignadores especializados hacen que las solicitudes frecuentes sean predecibles al agrupar tamaños, conservar objetos reutilizables o restringir los tamaños de bloque a potencias de dos.

Reutiliza tamaños frecuentes y objetos inicializados

Las listas segregadas mantienen listas de bloques libres separadas para los tamaños frecuentes, con un asignador general para las demás solicitudes. Atender un tamaño habitual puede consistir en tomar un bloque directamente de su lista. Los bloques de igual tamaño no crean fragmentación externa entre sí, pero dividir la capacidad entre listas es una decisión de política: los bloques sobrantes de un tamaño pueden no servir para otro.

Un asignador por bloques de objetos mantiene una caché de objetos para un tipo de objeto del núcleo que se usa repetidamente, como un inodo, un cerrojo o un descriptor de proceso. Un bloque de objetos se divide en objetos de ese tipo. La caché obtiene más bloques cuando los necesita y puede devolver un bloque completamente libre a un asignador general. Jeff Bonwick diseñó este enfoque para Solaris.

La caché conserva los objetos liberados en un estado inicializado, evitando la configuración y destrucción repetidas. Esto ahorra tiempo además del de la búsqueda.

Divide una región de bloques compañeros

Un asignador binario por bloques compañeros comienza con una región de tamaño potencia de dos y redondea cada solicitud a un tamaño de bloque que sea potencia de dos. Divide repetidamente un bloque libre en mitades iguales hasta que una mitad tiene el tamaño justo. Las dos mitades de una división son bloques compañeros.

Para una solicitud de 5 KB en una región de 64 KB, redondea 5 KB a 8 KB. Divide 64 en dos bloques de 32 KB, después el bloque elegido de 32 en dos bloques de 16 KB y luego el bloque elegido de 16 en dos bloques de 8 KB. Devolver el primer bloque de 8 KB deja bloques compañeros libres en los desplazamientos 8 KB, 16 KB y 32 KB, con tamaños de 8 KB, 16 KB y 32 KB respectivamente.

La asignación desperdicia 3 KB dentro de su bloque de 8 KB. Esto es fragmentación interna, aceptada a cambio de una división y fusión regulares.

Encuentra el único compañero válido para la fusión

Usando desplazamientos medidos desde el comienzo de la región gestionada:

La operación O exclusiva invierte el bit correspondiente al tamaño del bloque. Para un bloque de 8 KB en el desplazamiento 0, su compañero está en el desplazamiento 8192. Para un bloque de 16 KB en el desplazamiento 16 384, su compañero está en 0.

Cuando se libera el primer bloque de 8 KB, se fusiona con su compañero libre de 8 KB. El bloque de 16 KB resultante puede fusionarse con su compañero libre y, después, el bloque de 32 KB resultante puede volver a fusionarse. La fusión se detiene si el compañero necesario del mismo tamaño está en uso. Estar adyacentes y libres no basta cuando dos bloques no son compañeros de la misma división.

Una solicitud de 20 KB recibe 32 KB y desperdicia 12 KB, o el 37,5 % del bloque. Linux combina la asignación por bloques compañeros de memoria física con cachés de objetos de tipo slab. Los asignadores multihilo también usan cachés locales o varias arenas para reducir la espera por un único cerrojo compartido de asignación; glibc, jemalloc y tcmalloc usan variantes de estas ideas.