En el almacenamiento informático , la fragmentación es un fenómeno en el que el espacio de almacenamiento, almacenamiento principal o almacenamiento secundario , se utiliza de manera ineficiente, reduciendo 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 que se utilice y de la forma particular de fragmentación. En muchos casos, la fragmentación conduce a que se "desperdicie" espacio de almacenamiento, y en ese caso el término también se refiere al espacio desperdiciado en sí.
En la fragmentación de la memoria principal, cuando un programa informático solicita bloques de memoria del sistema informático, los bloques se asignan en fragmentos. Cuando el programa de computadora termina con un fragmento, puede liberarlo nuevamente al sistema, haciéndolo disponible para luego asignarlo nuevamente a otro o al mismo programa. El tamaño y la cantidad de tiempo que un programa retiene un fragmento varía. Durante su vida útil, un programa informático puede solicitar y liberar muchos fragmentos de memoria.
Cuando se inicia un programa, las áreas de memoria libre son largas y contiguas. Con el tiempo y el uso, las largas regiones contiguas se fragmentan en áreas contiguas cada vez más pequeñas. Con el tiempo, puede resultar imposible para el programa obtener grandes porciones de memoria contiguas.
Hay tres formas de fragmentación diferentes pero relacionadas: fragmentación externa, fragmentación interna y fragmentación de datos, que pueden estar presentes de forma aislada o en conjunto. A menudo se acepta la fragmentación a cambio de mejoras en velocidad o simplicidad. Fenómenos análogos ocurren con otros recursos como los procesadores; vea abajo.
La paginación de la memoria crea fragmentación interna porque se asignará un marco de página completo, se necesite o no tanto almacenamiento. [1] 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 sólo 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, adolece de un uso ineficiente de la memoria: cualquier proceso, por pequeño que sea, ocupa una partición completa. Este desperdicio se llama fragmentación interna . [2] [3]
A diferencia de otros tipos de fragmentación, la fragmentación interna es difícil de recuperar; Normalmente la mejor forma de eliminarlo es con 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 el espacio sobrecargado entre una mayor cantidad de objetos.
La fragmentación externa surge cuando la memoria libre se separa en pequeños bloques y se intercala con la memoria asignada. Es 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 gratuito disponible, en la práctica no se puede utilizar 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 se encuentra 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 de memoria libre para asignaciones futuras. Sin embargo, no puede utilizar este bloque si la memoria a asignar es mayor que este bloque libre.
La fragmentación externa también ocurre en los sistemas de archivos, ya que se crean muchos archivos de diferentes tamaños, cambian de tamaño y se eliminan. El efecto es aún peor si se elimina un archivo que está dividido en muchos fragmentos pequeños, porque esto deja regiones igualmente pequeñas de espacios libres.
La fragmentación de datos ocurre cuando una colección de datos en la memoria se divide en muchas partes que no están muy juntas. Generalmente es el resultado de intentar insertar un objeto grande en el almacenamiento que ya ha sufrido una fragmentación externa. Por ejemplo, los archivos de un sistema de archivos suelen gestionarse 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 secuenciales rápidas de archivos. Sin embargo, a medida que se agregan, eliminan y cambian de tamaño archivos, el espacio libre se fragmenta externamente, dejando sólo pequeños huecos en los que colocar nuevos datos. Cuando se escribe un archivo nuevo, 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 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 administrar ubicaciones adicionales. Esto se llama fragmentación del sistema de archivos .
Al escribir un nuevo archivo de un tamaño conocido, si hay huecos 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 huecos. Existe una variedad de algoritmos para seleccionar en cuál de esos posibles agujeros colocar el archivo; cada uno de ellos es una solución heurística aproximada al problema del embalaje del contenedor . 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 "siguiente ajuste" realiza un seguimiento de dónde se escribió cada archivo. El algoritmo de "siguiente ajuste" es más rápido que el "primer ajuste", que a su vez es más rápido que el "mejor ajuste", que es la misma velocidad que el "peor ajuste". [4]
Así como la compactación puede eliminar la fragmentación externa, la fragmentación de datos se puede eliminar reorganizando el almacenamiento de datos de modo que las piezas relacionadas estén muy juntas. Por ejemplo, la tarea 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 en movimiento , utilidades que realizan administración automática de memoria, también acercarán los objetos relacionados (esto se llama compactación ) para mejorar el rendimiento de la caché.
Hay cuatro tipos de sistemas que nunca experimentan fragmentación de datos: siempre almacenan cada archivo 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 sobrecarga y la fragmentación interna representan poca pérdida 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 RAM se cumplan con bloques contiguos, pero los sistemas de archivos generalmente están diseñados para poder usar cualquier colección. de bloques disponibles (fragmentos) para ensamblar un archivo que lógicamente aparece contiguo. Por lo tanto, si se elimina un archivo muy 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 mediante la eliminación. Si lo que se eliminó fue un archivo, el archivo nuevo estará tan fragmentado como lo estaba el archivo antiguo, pero en cualquier caso no habrá ninguna barrera para usar todo el espacio libre (altamente fragmentado) para crear el archivo nuevo. En la 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, por lo que la solicitud no puede cumplirse y el programa no puede proceder a hacer aquello para lo que necesitaba esa memoria (a menos que puede 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 provocar que un proceso o sistema falle debido al agotamiento prematuro de los recursos: si un bloque contiguo debe almacenarse y no puede almacenarse, 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 2 El total de GiB es gratuito.
Para evitar esto, el asignador puede, en lugar de fallar, desencadenar una desfragmentación (o 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 al 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 en 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 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 pueden satisfacerse simplemente devolviendo un único bloque desde el inicio del área libre. Independientemente de cómo esté fragmentada, la solicitud requiere buscar un bloque libre lo suficientemente grande, lo que puede llevar mucho tiempo, o completar la solicitud con varios bloques más pequeños (si esto es posible), lo que resulta en que esta asignación se fragmente y requiera recursos adicionales. gastos generales para gestionar las distintas piezas.
Un problema más sutil es que la fragmentación puede agotar prematuramente un caché, provocando ataques , debido a que los 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 un caché de 256 KiB (por ejemplo, caché de datos e instrucciones L2), por lo que todo el conjunto de trabajo cabe en el 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 de virtual a física, que es rápida si la página está en caché (aquí TLB). Si el conjunto de trabajo no está fragmentado, cabrá exactamente en 64 páginas (el conjunto de trabajo de páginas será de 64 páginas) y todas las búsquedas de memoria se podrán realizar desde la memoria caché. Sin embargo, si el conjunto de trabajo está fragmentado, no cabe en 64 páginas y la ejecución se ralentizará debido a la agitación: las páginas se agregarán y eliminarán repetidamente del TLB durante la operación. Por lo tanto, el tamaño 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 que enfrentan los administradores de sistemas . [ cita necesaria ] Con el tiempo, conduce a la degradación del rendimiento del sistema. Con el tiempo, 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 a nivel de programación del kernel . Durante la computación de aplicaciones en tiempo real , los niveles de fragmentación pueden alcanzar hasta el 99% y pueden provocar fallas del sistema u otras inestabilidades. [ cita necesaria ] 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 caso de una fragmentación excesiva de la memoria, un sistema bien diseñado debería poder recuperarse de la condición de fragmentación crítica 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, finalizando algunos programas para liberar su memoria y luego desfragmentando la suma total resultante de memoria libre. Esto al menos evitará una verdadera falla en el sentido de falla del sistema y permitirá que el sistema continúe ejecutando algunos programas, guarde datos de programas, etc. También es importante tener en cuenta que la fragmentación es un fenómeno del diseño del software del sistema; software diferente será susceptible a la fragmentación en diferentes grados, y es posible diseñar un sistema que nunca se verá obligado a cerrar o finalizar procesos como resultado de la fragmentación de la memoria.
Si bien la fragmentación es más conocida como un problema en la asignación de memoria, ocurren fenómenos análogos con otros recursos , en particular los procesadores. [5] Por ejemplo, en un sistema que utiliza el tiempo compartido para la multitarea preventiva , pero que no verifica si un proceso está bloqueado, un proceso que se ejecuta durante parte de su intervalo de tiempo pero luego se bloquea y no puede continuar durante el resto de su tiempo compartido. El intervalo de tiempo desperdicia tiempo debido a la fragmentación interna resultante de los intervalos de tiempo. Más fundamentalmente, el tiempo compartido en sí mismo provoca una fragmentación externa de los procesos debido a que se ejecutan en intervalos de tiempo fragmentados, en lugar de en una única ejecución ininterrumpida. El costo resultante del cambio de procesos y el aumento de la presión de la caché debido a que múltiples procesos utilizan las mismas cachés pueden provocar una degradación del rendimiento.
En sistemas concurrentes , particularmente 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 (fragmentadas en tiempo o máquinas), el tiempo dedicado a esperarse unos a otros o comunicarse entre sí pueden degradar gravemente el rendimiento. En cambio, los sistemas de desempeño requieren una programación conjunta del grupo. [5]
Algunos sistemas de archivos flash tienen varios tipos diferentes de fragmentación interna que involucran "espacio muerto" y "espacio oscuro". [6]
