Внешняя фрагментация¶

Внешняя фрагментация — это явление в компьютерных системах, при котором свободная память (оперативная или дисковая) разбита на множество мелких, не смежных друг с другом участков, что делает невозможным выделение непрерывного блока памяти запрошенного размера, несмотря на то, что суммарный объём свободной памяти достаточен для удовлетворения запроса. Внешняя фрагментация является одной из основных проблем управления памятью, особенно в системах с динамическим распределением.

¶Причины возникновения

Внешняя фрагментация возникает в результате многократных операций выделения и освобождения блоков памяти разного размера. Когда процесс запрашивает память, система выделяет ему непрерывный участок. После завершения работы процесса этот участок освобождается, но его размер может не совпадать с размерами соседних свободных участков. Со временем между занятыми блоками образуются небольшие свободные «дыры», которые невозможно объединить в один большой блок, так как они разделены занятой памятью.

¶Типичные сценарии

• Динамическое распределение памяти (например, куча в C/C++ при использовании malloc/free).
• Файловые системы (фрагментация свободного пространства на жёстком диске).
• Управление оперативной памятью в операционных системах (сегментация).

¶Отличие от внутренней фрагментации

Внешнюю фрагментацию часто путают с внутренней. При внутренней фрагментации выделенный процессу блок памяти больше, чем ему требуется, и часть блока не используется (например, из-за выравнивания границ). При внешней фрагментации свободная память существует, но не может быть использована из-за своей разрозненности. Внутренняя фрагментация — это потеря памяти внутри выделенного блока, внешняя — потеря возможности использовать свободные блоки.

¶Пример

Предположим, что в системе имеется 100 МБ свободной памяти, распределённой следующим образом:

• Свободно 10 МБ, затем занято 20 МБ, затем свободно 30 МБ, затем занято 10 МБ, затем свободно 60 МБ.
• Суммарно свободно 100 МБ.
• Если процесс запрашивает 40 МБ непрерывной памяти, система не сможет удовлетворить запрос, так как самый большой непрерывный свободный участок — 60 МБ (последний), но он расположен после занятых блоков, и для выделения 40 МБ потребовалось бы переместить занятые блоки. В данном случае внешняя фрагментация налицо: свободной памяти достаточно, но она фрагментирована.

¶Методы борьбы

¶Компактизация (дефрагментация)

Один из основных методов — перемещение занятых блоков памяти таким образом, чтобы все свободные участки оказались смежными, образуя один большой блок. В оперативной памяти это требует остановки процессов и перезаписи их адресов (динамическая переадресация), что сопряжено с высокими накладными расходами. В файловых системах дефрагментация выполняется специальными утилитами (например, дефрагментатор диска в Windows).

¶Страничная организация памяти

Страничная память (paging) позволяет избежать внешней фрагментации в оперативной памяти, так как физическая память делится на блоки фиксированного размера (страницы), а виртуальное адресное пространство процесса отображается на эти страницы. При этом свободные страницы могут быть расположены в любом порядке, и процессу не требуется непрерывный участок физической памяти. Однако страничная организация может приводить к внутренней фрагментации (последняя страница процесса может быть заполнена не полностью).

¶Сегментно-страничная организация

Комбинирует сегментацию (логические блоки переменного размера) и страничную организацию. Сегменты делятся на страницы, что позволяет избежать внешней фрагментации на уровне физической памяти, сохраняя логическую структуру.

¶Алгоритмы распределения памяти

Использование специальных алгоритмов для выбора свободного блока при выделении памяти может снизить степень фрагментации:

• First-fit (первый подходящий) — быстрый, но может создавать много мелких фрагментов.
• Best-fit (наилучший подходящий) — выбирает блок, наиболее близкий по размеру к запрошенному, что уменьшает потери, но увеличивает время поиска.
• Worst-fit (наихудший подходящий) — выбирает самый большой блок, оставляя крупные остатки, что может быть полезно для последующих крупных запросов.
• Buddy system (система двоичных блоков) — память делится на блоки размером степени двойки; при выделении блок делится пополам, при освобождении — объединяется с соседним блоком того же размера. Этот метод эффективен для управления фрагментацией.

¶Сборка мусора (Garbage Collection)

В языках с автоматическим управлением памятью (Java, C#, Go) сборщик мусора может выполнять компактизацию кучи, перемещая живые объекты и объединяя свободное пространство. Это один из наиболее эффективных способов борьбы с внешней фрагментацией в долгоживущих приложениях.

¶Влияние на производительность

Внешняя фрагментация может приводить к:

• Увеличению времени выделения памяти (алгоритмы поиска подходящего блока становятся менее эффективными).
• Невозможности выполнить запрос на выделение памяти, что может вызвать сбой программы или системы.
• Росту накладных расходов на управление памятью (например, на дефрагментацию).
• Снижению пропускной способности ввода-вывода в файловых системах (из-за разброса данных по диску).

¶Примеры в реальных системах

• Операционные системы: ранние версии Windows (до внедрения виртуальной памяти) страдали от внешней фрагментации в куче. В современных ОС проблема решается за счёт страничной организации.
• Файловые системы: FAT32 и NTFS подвержены внешней фрагментации, особенно при частом создании и удалении файлов разного размера. Для борьбы используются дефрагментаторы.
• Базы данных: внешняя фрагментация может возникать в таблицах и индексах, что замедляет запросы. Для её устранения применяются операции реорганизации (например, ALTER INDEX ... REORGANIZE в SQL Server).
• Встраиваемые системы: в системах с ограниченной памятью (микроконтроллеры) внешняя фрагментация может быть критичной, поэтому часто используются пулы памяти фиксированного размера.

¶Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание). — СПб.: Питер, 2015.
• Сильбершац А., Гэлвин П., Гэгн Г. «Операционные системы: внутреннее устройство и принципы проектирования» (9-е издание). — М.: Вильямс, 2016.
• Кнут Д. «Искусство программирования». Том 1: Основные алгоритмы. — М.: Вильямс, 2010.
• Документация Microsoft по управлению памятью в Windows (MSDN).