En el almacenamiento informático , la fragmentación es un fenómeno en el que el espacio de almacenamiento, como la memoria del ordenador o un disco duro , se utiliza de forma ineficiente, lo que reduce la capacidad o el rendimiento y, a menudo, ambos. Las consecuencias exactas de la fragmentación dependen del sistema específico de asignación de almacenamiento en uso y de la forma particular de fragmentación. En muchos casos, la fragmentación hace que se "desperdicie" espacio de almacenamiento y los programas tenderán a ejecutarse de forma ineficiente debido a la falta de memoria.
En la fragmentación de la memoria principal, cuando un programa informático solicita bloques de memoria al sistema informático, los bloques se asignan en fragmentos. Cuando el programa informático termina con un fragmento, puede liberarlo y enviarlo al sistema, de modo que esté disponible para que luego se asigne nuevamente a otro programa o al mismo programa. El tamaño y la cantidad de tiempo que un programa conserva un fragmento varía. Durante su vida útil, un programa informático puede solicitar y liberar muchos fragmentos de memoria.
La fragmentación puede ocurrir cuando un programa solicita un bloque de memoria y se le asigna, pero el programa no lo ha liberado. [1] Esto hace que la memoria teóricamente "disponible", no utilizada, se marque como asignada, lo que reduce la cantidad de memoria disponible globalmente y dificulta que los programas soliciten y accedan a la memoria.
Cuando se inicia un programa, las áreas de memoria libres son largas y contiguas. Con el tiempo y el uso, las regiones contiguas largas se fragmentan en áreas contiguas cada vez más pequeñas. Con el tiempo, puede resultar imposible para el programa obtener grandes porciones contiguas de memoria.
Existen tres formas de fragmentación diferentes pero relacionadas: fragmentación externa, fragmentación interna y fragmentación de datos, que pueden presentarse de forma aislada o conjunta. La fragmentación suele aceptarse a cambio de mejoras en la velocidad o la simplicidad. Se producen fenómenos análogos con otros recursos, como los procesadores; véase más adelante.
La paginación de memoria crea fragmentación interna porque se asignará un marco de página completo independientemente de que se necesite o no esa cantidad de almacenamiento. [2] Debido a las reglas que rigen la asignación de memoria , a veces se asigna más memoria de la necesaria. Por ejemplo, la memoria solo se puede proporcionar a los programas en fragmentos (normalmente un múltiplo de 4 bytes) y, como resultado, si un programa solicita quizás 29 bytes, en realidad obtendrá un fragmento de 32 bytes. Cuando esto sucede, el exceso de memoria se desperdicia. En este escenario, la memoria inutilizable, conocida como espacio de holgura , está contenida dentro de una región asignada. Esta disposición, denominada particiones fijas, sufre de un uso ineficiente de la memoria: cualquier proceso, sin importar lo pequeño que sea, ocupa una partición entera. Este desperdicio se llama fragmentación interna . [3] [4]
A diferencia de otros tipos de fragmentación, la fragmentación interna es difícil de recuperar; por lo general, la mejor forma de eliminarla es con un cambio de diseño. Por ejemplo, en la asignación de memoria dinámica , los grupos de memoria reducen drásticamente la fragmentación interna al distribuir la sobrecarga de espacio entre una mayor cantidad de objetos.
La fragmentación externa se produce cuando la memoria libre se divide en pequeños bloques y se intercala con memoria asignada. Se trata de una debilidad de ciertos algoritmos de asignación de almacenamiento, cuando no logran ordenar de manera eficiente la memoria utilizada por los programas. El resultado es que, aunque hay almacenamiento libre disponible, es efectivamente inutilizable porque está dividido en partes que son demasiado pequeñas individualmente para satisfacer las demandas de la aplicación. El término "externo" se refiere al hecho de que el almacenamiento inutilizable está fuera de las regiones asignadas.
Por ejemplo, considere una situación en la que un programa asigna tres bloques continuos de memoria y luego libera el bloque del medio. El asignador de memoria puede utilizar este bloque libre de memoria para futuras asignaciones. Sin embargo, no puede utilizar este bloque si la memoria que se va a asignar es de mayor tamaño que este bloque libre.
La fragmentación externa también se produce en los sistemas de archivos, ya que se crean, modifican y eliminan muchos archivos de distintos tamaños. El efecto es aún peor si se elimina un archivo dividido en muchos fragmentos pequeños, ya que quedan zonas de espacio libre igualmente pequeñas.
La fragmentación de datos se produce cuando una colección de datos en la memoria se divide en muchas piezas que no están juntas. Por lo general, es el resultado de intentar insertar un objeto grande en el almacenamiento que ya ha sufrido una fragmentación externa. Por ejemplo, los archivos en un sistema de archivos generalmente se administran en unidades llamadas bloques o clústeres . Cuando se crea un sistema de archivos, hay espacio libre para almacenar bloques de archivos juntos de forma contigua . Esto permite lecturas y escrituras de archivos secuenciales rápidas. Sin embargo, a medida que se agregan, eliminan y cambian de tamaño los archivos, el espacio libre se fragmenta externamente, dejando solo pequeños agujeros en los que colocar nuevos datos. Cuando se escribe un nuevo archivo, o cuando se amplía un archivo existente, el sistema operativo coloca los nuevos datos en nuevos bloques de datos no contiguos para que quepan en los agujeros 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 administrar ubicaciones adicionales. Esto se llama fragmentación del sistema de archivos .
Al escribir un nuevo archivo de un tamaño conocido, si hay agujeros vacíos que sean más grandes que ese archivo, el sistema operativo puede evitar la fragmentación de datos colocando el archivo en cualquiera de esos agujeros. Hay una variedad de algoritmos para seleccionar en cuál de esos agujeros potenciales colocar el archivo; cada uno de ellos es una solución aproximada heurística al problema de empaquetamiento de contenedores . El algoritmo de "mejor ajuste" elige el agujero más pequeño que sea lo suficientemente grande. El algoritmo de "peor ajuste" elige el agujero más grande. El algoritmo de " primer ajuste " elige el primer agujero que sea lo suficientemente grande. El algoritmo de "próximo ajuste" realiza un seguimiento de dónde se escribió cada archivo. El algoritmo de "próximo 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 es la misma velocidad que el de "peor ajuste". [5]
Así como la compactación puede eliminar la fragmentación externa, la fragmentación de datos puede eliminarse reorganizando el almacenamiento de datos de modo que las piezas relacionadas estén más juntas. Por ejemplo, la función principal de una herramienta de desfragmentación es reorganizar los bloques del disco de modo 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 moverán los objetos relacionados más cerca (esto se denomina compactación ) para mejorar el rendimiento de la memoria caché.
Existen cuatro tipos de sistemas que nunca experimentan fragmentación de datos: siempre almacenan todos los archivos de forma contigua. Los cuatro tipos tienen desventajas significativas en comparación con los sistemas que permiten al menos cierta fragmentación temporal de datos:
En comparación con la fragmentación externa, la fragmentación interna y la sobrecarga representan una pérdida mínima en términos de memoria desperdiciada y rendimiento reducido. Se define como:
Una fragmentación del 0% significa que toda la memoria libre está en un único bloque grande; la fragmentación es 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 tiende a ser un problema menor en los sistemas de archivos que en los sistemas de almacenamiento de memoria primaria (RAM), porque los programas generalmente requieren que sus solicitudes de almacenamiento en RAM se satisfagan con bloques contiguos, pero los sistemas de archivos generalmente están diseñados para poder usar cualquier conjunto de bloques disponibles (fragmentos) para ensamblar un archivo que lógicamente parece contiguo. Por lo tanto, si se elimina un archivo altamente fragmentado o muchos archivos pequeños de un volumen completo y luego se crea un nuevo archivo con un tamaño igual al espacio recién liberado, el nuevo archivo simplemente reutilizará los mismos fragmentos que se liberaron con la eliminación. Si lo que se eliminó fue un archivo, el nuevo archivo estará tan fragmentado como el archivo anterior, pero en cualquier caso no habrá ningún obstáculo para usar todo el espacio libre (altamente fragmentado) para crear el nuevo archivo. En RAM, por otro lado, los sistemas de almacenamiento utilizados a menudo no pueden ensamblar un bloque grande para satisfacer una solicitud de pequeños bloques libres no contiguos y, por lo tanto, la solicitud no se puede cumplir y el programa no puede proceder a hacer lo 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 que causa la fragmentación es que un proceso o sistema falla debido al agotamiento prematuro de los recursos: si se debe almacenar un bloque contiguo y no se puede, se produce una falla. La fragmentación hace que esto ocurra incluso si hay suficiente recurso, pero no una cantidad contigua . Por ejemplo, si una computadora tiene 4 GiB de memoria y 2 GiB están libres, pero la memoria está fragmentada en una secuencia alterna de 1 MiB usado, 1 MiB libre, entonces no se puede satisfacer una solicitud de 1 GiB contiguo de memoria aunque haya 2 GiB libres en total.
Para evitarlo, el asignador puede, en lugar de fallar, activar una desfragmentación (o un ciclo de compactación de memoria) u otra recuperación de recursos, como un ciclo importante de recolección de basura, 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, la fragmentación aumenta el trabajo necesario para asignar y acceder a un recurso. Por ejemplo, en un disco duro o una unidad de cinta, las lecturas secuenciales de datos son muy rápidas, 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 provocar un mayor desgaste en el dispositivo. Además, si un recurso no está fragmentado, las solicitudes de asignación se pueden satisfacer simplemente devolviendo un solo bloque desde el comienzo del área libre. Independientemente de cómo esté fragmentado, la solicitud requiere buscar un bloque libre lo suficientemente grande, lo que puede llevar mucho tiempo, o satisfacer la solicitud con varios bloques más pequeños (si esto es posible), lo que da como resultado que esta asignación se fragmente y requiera una sobrecarga adicional para administrar las diversas partes.
Un problema más sutil es que la fragmentación puede agotar prematuramente una caché, causando un colapso , debido a que las cachés contienen bloques, no datos individuales. Por ejemplo, supongamos que un programa tiene un conjunto de trabajo de 256 KiB y se ejecuta en una computadora con una caché de 256 KiB (digamos caché de instrucciones + datos L2), 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 de búfer de búsqueda de traducción (TLB), cada una para una página de 4 KiB : cada acceso a la memoria requiere una traducción virtual a física, que es rápida si la página está en la caché (aquí TLB). Si el conjunto de trabajo no está fragmentado, entonces 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 servir 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 a la fragmentación: se añadirán y eliminarán páginas de la TLB repetidamente 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 . [ cita requerida ] Con el tiempo, conduce a la degradación del rendimiento del sistema. Finalmente, la fragmentación de la memoria puede provocar la pérdida total de la memoria libre (utilizable por la aplicación).
La fragmentación de la memoria es un problema de nivel de programación del núcleo . Durante la computación en tiempo real de las aplicaciones, los niveles de fragmentación pueden alcanzar niveles tan altos como el 99% y pueden provocar fallas del sistema u otras inestabilidades. [ cita requerida ] Este tipo de falla del sistema puede ser difícil de evitar, ya que es imposible anticipar el aumento crítico en los niveles de fragmentación de la memoria. Sin embargo, si bien puede que no sea posible que un sistema continúe ejecutando todos los programas en el caso de una fragmentación excesiva de la 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 más grandes o, en el peor de los casos, terminando algunos programas para liberar su memoria y luego desfragmentando la suma total resultante de memoria libre. Esto al menos evitará una falla real en el sentido de una falla del sistema y permitirá que el sistema continúe ejecutando algunos programas, guarde datos del programa, etc.
La fragmentación es un fenómeno del diseño de software de sistemas; diferentes programas serán susceptibles a la fragmentación en diferentes grados, y es posible diseñar un sistema que nunca se vea obligado a apagar o matar procesos como resultado de la fragmentación de la memoria.
Aunque la fragmentación es más conocida como un problema en la asignación de memoria, se producen fenómenos análogos para otros recursos , en particular los procesadores. [6] Por ejemplo, en un sistema que utiliza el tiempo compartido para la multitarea preventiva , pero que no comprueba si un proceso está bloqueado, un proceso que se ejecuta durante parte de su porción de tiempo pero luego se bloquea y no puede continuar durante el resto de su porción de tiempo pierde tiempo debido a la fragmentación interna resultante de las porciones de tiempo. Más fundamentalmente, el tiempo compartido en sí mismo causa la fragmentación externa de los procesos debido a que se ejecutan en porciones de tiempo fragmentadas, en lugar de en una única ejecución ininterrumpida. El costo resultante de la conmutación de procesos y el aumento de la presión de caché de múltiples procesos que usan las mismas cachés pueden resultar en un rendimiento degradado.
En sistemas concurrentes , en particular sistemas distribuidos , cuando un grupo de procesos debe interactuar para progresar, si los procesos están programados en momentos separados o en máquinas separadas (fragmentados en el tiempo o en las máquinas), el tiempo que se pasa esperando a cada uno o comunicándose entre sí puede degradar gravemente el rendimiento. En cambio, los sistemas de alto rendimiento requieren una coprogramación del grupo. [6]
Algunos sistemas de archivos flash tienen varios tipos diferentes de fragmentación interna que involucran "espacio muerto" y "espacio oscuro". [7]
