Fragmentación (informática)

La fragmentación de la memoria puede ser interna o externa . La fragmentación interna se produce cuando la asignación de memoria proporciona más espacio del necesario, lo que provoca un desperdicio de espacio libre. La fragmentación externa se produce cuando la memoria libre está fragmentada, lo que impide la asignación de bloques más grandes y nuevos.

En los sistemas operativos modernos, el programa recibe páginas de tamaño fijo que luego distribuye entre sus diferentes partes (a menudo mediante un asignador como malloc). Como resultado, existen dos niveles de asignación que pueden generar fragmentación interna y externa: uno a nivel del asignador de memoria (por ejemplo, malloc ) y otro a nivel de las páginas. (Los sistemas operativos más antiguos podrían no usar páginas, pero los programas aún tienden a usar un sistema de dos niveles para evitar llamadas excesivas al sistema operativo).

fragmentación interna

Debido a las reglas que rigen la asignación de memoria , a veces se asigna más memoria de la necesaria. Cuando esto sucede, el exceso de memoria se desperdicia. En este caso, la memoria no utilizable, conocida como espacio libre , se encuentra dentro de una región asignada. Esta disposición, denominada particiones fijas, presenta un uso ineficiente de la memoria: cualquier proceso, por pequeño que sea, ocupa una partición completa. Este desperdicio se conoce como fragmentación interna .

• La paginación de memoria crea fragmentación interna porque se asignará un marco de página completo (normalmente de 4 a 64 KiB) independientemente de si se necesita o no esa cantidad de almacenamiento. ^{[ 2 ]} 
• malloc y otros asignadores similares tienden a proporcionar cierto grado de alineación , de modo que la memoria solo se puede proporcionar a los programas en bloques (generalmente un múltiplo de 4 bytes). Como resultado, si un programa solicita, por ejemplo, 29 bytes, en realidad recibirá un bloque de 32 bytes. ^{[ 3 ] [ 4 ]}

La fragmentación interna a nivel del asignador es muy difícil de revertir una vez que se ha producido; por lo general, la mejor manera de eliminarla es mediante un cambio de diseño. Por ejemplo, en la asignación dinámica de memoria , los grupos de memoria reducen drásticamente la fragmentación interna al distribuir la sobrecarga de espacio entre un mayor número de objetos.

La fragmentación interna a nivel de página (que es fragmentación externa a nivel de asignador) se puede recuperar moviendo los bloques asignados. Esto requiere editar los punteros para reflejar el movimiento de los bloques asignados, lo cual es difícil para lenguajes sin recolección de basura. Los recolectores de basura compactadores realizan correcciones de punteros a medida que compactan el espacio de direcciones virtuales. ^{[ 5 ]}

La fragmentación de datos se produce cuando un conjunto de datos en la memoria se divide en muchas partes que no están cerca unas de otras. Los sistemas de archivos interactúan condispositivos de bloques,como las unidades de disco. Estos dispositivos gestionan los datos en unidades pequeñas y de tamaño fijo llamadasbloqueso sectores, que los sistemas de archivos abstraen en sus propias unidades llamadasbloquesoclústeres.

Cuando se crea un sistema de archivos, hay espacio libre para almacenar bloques de archivos de forma contigua . Esto permite lecturas y escrituras de archivos secuenciales y rápidas. Sin embargo, a medida que se agregan, eliminan y modifican los archivos, el espacio libre se fragmenta externamente, dejando solo pequeños huecos para colocar nuevos datos. Esto se denomina fragmentación externa . Los sistemas de archivos se diferencian de la memoria en que están diseñados teniendo en cuenta la fragmentación: cuando se escribe un archivo nuevo o se extiende uno existente, el sistema operativo coloca los nuevos datos en nuevos grupos de clústeres no contiguos ( extensiones ) para que encajen en los huecos disponibles. Los nuevos bloques de datos están necesariamente dispersos, lo que ralentiza el acceso debido al tiempo de búsqueda y la latencia rotacional del cabezal de lectura/escritura, e incurre en una sobrecarga adicional para gestionar ubicaciones adicionales. Esto se denomina fragmentación del sistema de archivos . El efecto es aún peor si se elimina un archivo dividido en muchas partes pequeñas, ya que esto deja regiones igualmente pequeñas de espacio libre.

Al escribir un nuevo archivo de tamaño conocido, si hay espacios vacíos mayores que el archivo, el sistema operativo puede evitar la fragmentación de datos colocando el archivo en cualquiera de esos espacios. Existen diversos algoritmos para seleccionar en cuál de esos espacios potenciales colocar el archivo; cada uno de ellos es una solución heurística aproximada al problema de empaquetamiento de contenedores . El algoritmo de "mejor ajuste" elige el espacio más pequeño que sea lo suficientemente grande. El algoritmo de "peor ajuste" elige el espacio más grande. El algoritmo de " primer ajuste " elige el primer espacio que sea lo suficientemente grande. El algoritmo de "siguiente ajuste" registra dónde se escribió cada archivo. El algoritmo de "siguiente ajuste" es más rápido que el de "primer ajuste", que a su vez es más rápido que el de "mejor ajuste", que tiene la misma velocidad que el de "peor ajuste". ^{[ 7 ]}

Así como la compactación puede eliminar la fragmentación externa, la fragmentación de datos (externa) puede eliminarse reorganizando el almacenamiento de datos para que las partes relacionadas estén cerca unas de otras. Por ejemplo, la función principal de una herramienta de desfragmentación es reorganizar los bloques en el disco para que los bloques de cada archivo sean contiguos. La mayoría de las utilidades de desfragmentación también intentan reducir o eliminar la fragmentación del espacio libre. Algunos recolectores de basura móviles , utilidades que realizan la gestión automática de la memoria, también mueven los objetos relacionados cerca unos de otros (esto se denomina compactación ) para mejorar el rendimiento de la caché.

Cuatro tipos de sistemas nunca experimentan fragmentación de datos (externa); siempre almacenan todos los archivos de forma contigua. Los cuatro tipos presentan desventajas significativas en comparación con los sistemas que permiten al menos cierta fragmentación temporal de datos:

1. Simplemente escribe cada archivo de forma contigua . Si no hay suficiente espacio libre contiguo para almacenar el archivo, el sistema falla inmediatamente al intentar guardarlo, incluso si hay muchos pequeños fragmentos de espacio libre provenientes de archivos eliminados que, en conjunto, son más que suficientes para almacenar el archivo.
2. Si no hay suficiente espacio libre contiguo para almacenar el archivo, utilice un recolector de copias para convertir varios fragmentos de espacio libre en una región libre contigua lo suficientemente grande como para contener el archivo. Esto lleva mucho más tiempo que dividir el archivo en fragmentos y colocarlos en el espacio libre disponible.
3. El archivo se escribe en cualquier bloque libre, mediante el almacenamiento en bloques de tamaño fijo . Si un programador elige un tamaño de bloque fijo demasiado pequeño, el sistema no podrá almacenar algunos archivos (archivos más grandes que el tamaño del bloque), incluso si hay muchos bloques libres disponibles. Si un programador elige un tamaño de bloque demasiado grande, se desperdicia mucho espacio debido a la fragmentación interna.
4. Algunos sistemas evitan por completo la asignación dinámica, almacenando previamente espacio (contiguo) para todos los archivos que puedan necesitar; por ejemplo, MultiFinder preasigna un bloque de RAM a cada aplicación al iniciarse, según la cantidad de RAM que el programador de dicha aplicación haya indicado que necesitaría.

La fragmentación interna rara vez es un problema en los sistemas de archivos porque no tiene un efecto global que empeore la asignación de archivos de todo el sistema. Sí causa una sobrecarga de espacio de almacenamiento y ralentiza el acceso a grandes conjuntos de archivos pequeños afectados (el conjunto en su conjunto puede considerarse "fragmentado"). Para combatir este problema, sistemas de archivos como ext4 y btrfs tienen una función de datos en línea o de archivos en línea para evitar asignar un clúster para estos archivos y, en su lugar, almacenarlos directamente en el inodo (registro de archivo). ^{[ 8 ]}

En comparación con la fragmentación externa, la sobrecarga y la fragmentación interna representan una pérdida mínima en términos de memoria desperdiciada y rendimiento reducido. Se define como:

Fragmentación de memoria externa = 1 - Bloque más grande de memoria libre / Memoria libre total

Una fragmentación del 0% significa que toda la memoria libre se encuentra en un único bloque grande; una fragmentación del 90% (por ejemplo) cuando hay 100 MB de memoria libre, pero el bloque de memoria libre más grande para almacenamiento es de solo 10 MB.

La fragmentación externa suele ser un problema menor en los sistemas de archivos que en los sistemas de almacenamiento de memoria primaria (RAM), ya que los programas generalmente requieren que sus solicitudes de almacenamiento en RAM se satisfagan con bloques contiguos. Sin embargo, los sistemas de archivos suelen estar diseñados para utilizar cualquier conjunto de bloques disponibles (fragmentos) para ensamblar un archivo que lógicamente parezca contiguo. Por lo tanto, si se elimina un archivo muy fragmentado o muchos archivos pequeños de un volumen lleno y luego se crea un nuevo archivo con un tamaño igual al espacio liberado, este nuevo archivo simplemente reutilizará los mismos fragmentos que se liberaron con la eliminación. Si lo que se eliminó fue un solo archivo, el nuevo archivo estará igual de fragmentado que el anterior, pero en cualquier caso no habrá ningún impedimento para utilizar todo el espacio libre (muy fragmentado) para crear el nuevo archivo. En la RAM, por otro lado, los sistemas de almacenamiento utilizados a menudo no pueden ensamblar un bloque grande para satisfacer una solicitud a partir de pequeños bloques libres no contiguos, por lo que la solicitud no se puede satisfacer y el programa no puede continuar con la tarea para la que necesitaba esa memoria (a menos que pueda volver a emitir la solicitud como una serie de solicitudes separadas más pequeñas).

El problema más grave causado por la fragmentación es el fallo de un proceso o sistema debido al agotamiento prematuro de los recursos: si se debe almacenar un bloque contiguo y no se puede, se produce un fallo. La fragmentación provoca esto incluso si hay suficiente recurso, pero no un bloque contiguo . Por ejemplo, si un ordenador tiene 4 GiB de memoria y 2 GiB libres, pero la memoria está fragmentada alternando 1 MiB usado y 1 MiB libre, entonces no se puede satisfacer una solicitud de 1 GiB contiguo de memoria, aunque haya 2 GiB libres en total.

Para evitar esto, el asignador puede, en lugar de fallar, iniciar una desfragmentación (o ciclo de compactación de memoria) u otra recuperación de recursos, como un ciclo de recolección de basura importante, con la esperanza de poder satisfacer la solicitud. Esto permite que el proceso continúe, pero puede afectar gravemente el rendimiento.

La fragmentación provoca una degradación del rendimiento por varias razones. Básicamente, aumenta el trabajo necesario para asignar y acceder a un recurso. Por ejemplo, en un disco duro o una unidad de cinta, la lectura secuencial de datos es muy rápida, pero la búsqueda de una dirección diferente es lenta, por lo que leer o escribir un archivo fragmentado requiere numerosas búsquedas y, por lo tanto, es mucho más lento, además de causar un mayor desgaste en el dispositivo. Asimismo, si un recurso no está fragmentado, las solicitudes de asignación pueden satisfacerse simplemente devolviendo un único bloque del inicio del área libre. Sin embargo, si está fragmentado, la solicitud requiere buscar un bloque libre lo suficientemente grande, lo que puede llevar mucho tiempo, o bien satisfacer la solicitud con varios bloques más pequeños (si esto es posible), lo que provoca que esta asignación esté fragmentada y requiera una sobrecarga adicional para gestionar las distintas partes.

Un problema más sutil es que la fragmentación puede agotar prematuramente una caché, provocando thrashing , debido a que las cachés almacenan bloques, no datos individuales. Por ejemplo, supongamos que un programa tiene un conjunto de trabajo de 256 KiB y se ejecuta en un ordenador con una caché de 256 KiB (por ejemplo, una caché L2 de instrucciones y datos), por lo que todo el conjunto de trabajo cabe en la caché y, por lo tanto, se ejecuta rápidamente, al menos en términos de aciertos de caché. Supongamos además que tiene 64 entradas en el búfer de traducción anticipada (TLB), cada una para una página de 4 KiB : cada acceso a memoria requiere una traducción virtual a física, que es rápida si la página está en la caché (en este caso, el TLB). Si el conjunto de trabajo no está fragmentado, cabrá exactamente en 64 páginas (el conjunto de trabajo de la página será de 64 páginas) y todas las búsquedas de memoria se pueden atender desde la caché. Sin embargo, si el conjunto de trabajo está fragmentado, no cabrá en 64 páginas y la ejecución se ralentizará debido al thrashing: las páginas se añadirán y eliminarán repetidamente del TLB durante la operación. Por lo tanto, el dimensionamiento de la caché en el diseño del sistema debe incluir un margen para tener en cuenta la fragmentación.

La fragmentación de la memoria es uno de los problemas más graves a los que se enfrentan los administradores de sistemas . Con el tiempo, provoca una degradación del rendimiento del sistema. Finalmente, la fragmentación de la memoria puede llevar a la pérdida total de la memoria libre (utilizable por las aplicaciones).

La fragmentación de memoria es un problema de programación a nivel de núcleo . Durante el procesamiento en tiempo real de las aplicaciones, los niveles de fragmentación pueden alcanzar hasta el 99%, lo que puede provocar fallos del sistema u otras inestabilidades. Este tipo de fallo puede ser difícil de evitar, ya que es imposible prever el aumento crítico de los niveles de fragmentación de memoria. Sin embargo, aunque un sistema no pueda seguir ejecutando todos los programas en caso de una fragmentación excesiva de memoria, un sistema bien diseñado debería poder recuperarse de la condición crítica de fragmentación moviendo algunos bloques de memoria utilizados por el propio sistema para permitir la consolidación de la memoria libre en menos bloques, pero de mayor tamaño, o, en el peor de los casos, finalizando algunos programas para liberar su memoria y luego desfragmentando la suma total de memoria libre resultante. Esto, al menos, evitará un fallo total del sistema y permitirá que este continúe ejecutando algunos programas, guardando datos de programas, etc.

La fragmentación es un fenómeno propio del diseño de software de sistemas; los diferentes programas serán susceptibles a la fragmentación en distintos grados, y es posible diseñar un sistema que nunca se vea obligado a apagar o finalizar procesos como resultado de la fragmentación de la memoria.