Фрагментация (вычисления)

В компьютерном хранилище фрагментация — это явление, при котором пространство хранения, основное или дополнительное хранилище , такое как память компьютера или жесткий диск , используется неэффективно, что снижает емкость или производительность, а часто и то, и другое. Точные последствия фрагментации зависят от конкретной используемой системы распределения памяти и конкретной формы фрагментации. Во многих случаях фрагментация приводит к «трате» места хранения, и в этом случае этот термин также относится к самому потраченному впустую пространству.

Основной принцип

При фрагментации основной памяти, когда компьютерная программа запрашивает блоки памяти у компьютерной системы, блоки распределяются порциями. Когда компьютерная программа завершает работу с часком, она может освободить его обратно в систему, сделав его доступным для последующего повторного использования в другой или той же программе. Размер и время, в течение которого программа удерживает фрагмент, различаются. За время своего существования компьютерная программа может запрашивать и освобождать множество участков памяти.

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

Типы

Существует три разные, но связанные формы фрагментации: внешняя фрагментация, внутренняя фрагментация и фрагментация данных, которые могут присутствовать изолированно или вместе. Фрагментация часто принимается в обмен на повышение скорости или простоты. Аналогичные явления происходят и с другими ресурсами, такими как процессоры; см. ниже.

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

Пейджинг памяти создает внутреннюю фрагментацию, поскольку весь страничный фрейм будет выделен независимо от того, требуется ли такой большой объем памяти. Из-за правил, регулирующих распределение памяти больше компьютерной памяти, , иногда выделяется чем необходимо. Например, память может предоставляться программам только частями (обычно кратными 4 байтам), и в результате, если программа запрашивает, возможно, 29 байт, то на самом деле он получит кусок размером в 32 байта. Когда это происходит, лишняя память тратится впустую. В этом сценарии непригодная для использования память, известная как свободное пространство , содержится в выделенной области. Такое расположение, называемое фиксированными разделами, страдает от неэффективного использования памяти: любой процесс, даже самый маленький, занимает целый раздел. Эти потери называются внутренней фрагментацией .

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

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

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

Например, рассмотрим ситуацию, когда программа выделяет три непрерывных блока памяти, а затем освобождает средний блок. Распределитель памяти может использовать этот свободный блок памяти для будущих выделений. Однако он не может использовать этот блок, если выделяемая память больше по размеру, чем этот свободный блок.

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

0x0000	0x1000	0x2000	0x3000	0x4000	0x5000	Комментарии
						Начните со всей доступной памяти для хранения.
А	Б	С				Выделено три блока A, B и C размером 0x1000.
А		С				Освобожденный блок B. Обратите внимание, что память, которую использовал B, не может быть включена в блок, размер которого превышает размер B.
А	С					Блок C переместился в пустой слот блока B, позволяя использовать оставшееся пространство для более крупного блока размером 0x4000.

Фрагментация данных

Фрагментация данных возникает, когда набор данных в памяти разбивается на множество частей, расположенных не близко друг к другу. Обычно это результат попытки вставить в хранилище большой объект, который уже подвергся внешней фрагментации. Например, файлы в файловой системе обычно управляются в единицах, называемых блоками или кластерами . При создании файловой системы появляется свободное пространство для последовательного хранения файловых блоков . Это обеспечивает быстрое последовательное чтение и запись файлов. Однако по мере добавления, удаления и изменения размера файлов свободное пространство становится внешне фрагментированным, оставляя лишь небольшие дыры для размещения новых данных. Когда записывается новый файл или когда существующий файл расширяется, операционная система помещает новые данные в новые несмежные блоки данных, чтобы они поместились в доступные отверстия. Новые блоки данных обязательно разбросаны, что замедляет доступ из-за времени поиска и задержки вращения головки чтения/записи, а также приводит к дополнительным накладным расходам на управление дополнительными местоположениями. Это называется фрагментация файловой системы .

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

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

Существует четыре типа систем, в которых никогда не происходит фрагментации данных — они всегда хранят все файлы последовательно. Все четыре типа имеют существенные недостатки по сравнению с системами, допускающими хотя бы некоторую временную фрагментацию данных:

1. Просто напишите каждый файл последовательно . Если непрерывного свободного места для хранения файла недостаточно, система сразу же не сможет сохранить файл — даже если в удаленных файлах имеется много маленьких кусочков свободного пространства, которых в сумме более чем достаточно для хранения файла.
2. Если непрерывного свободного места для хранения файла недостаточно, используйте копирующий сборщик , чтобы преобразовать множество маленьких кусочков свободного пространства в одну непрерывную свободную область, достаточно большую для хранения файла. Это занимает гораздо больше времени, чем разбиение файла на фрагменты и размещение этих фрагментов в доступном свободном пространстве.
3. Запишите файл в любой свободный блок через хранилище блоков фиксированного размера . Если программист выберет слишком маленький фиксированный размер блока, система сразу же не сможет сохранить некоторые файлы — файлы, размер которых превышает размер блока, — даже если имеется много свободных блоков, которых в сумме более чем достаточно для хранения файла. Если программист выбирает слишком большой размер блока, много места тратится на внутреннюю фрагментацию.
4. Некоторые системы полностью избегают динамического выделения, предварительно сохраняя (непрерывное) пространство для всех возможных файлов, которые им могут понадобиться — например, MultiFinder предварительно выделяет часть ОЗУ каждому приложению при его запуске в зависимости от того, сколько ОЗУ заявил программист этого приложения. понадобится.

Сравнение

По сравнению с внешней фрагментацией, накладные расходы и внутренняя фрагментация приводят к небольшим потерям в виде ненужной траты памяти и снижения производительности. Он определяется как:

${{\text{External Memory Fragmentation}}=1-}{\frac {\text{Largest Block Of Free Memory}}{\text{Total Free Memory}}}$

Фрагментация 0% означает, что вся свободная память находится в одном большом блоке; фрагментация составляет 90% (например), когда имеется 100 МБ свободной памяти, но самый большой свободный блок памяти для хранения составляет всего 10 МБ.

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

Проблемы

Сбой хранилища

Самая серьезная проблема, вызванная фрагментацией, — это сбой процесса или системы из-за преждевременного исчерпания ресурсов: если непрерывный блок должен быть сохранен, но не может быть сохранен, происходит сбой. Фрагментация приводит к тому, что это происходит, даже если ресурса достаточно, но не непрерывно . Например, если компьютер имеет 4 ГиБ памяти и 2 ГиБ свободны, но память фрагментирована в чередующейся последовательности: 1 МБ используется, 1 МБ свободно, то запрос на 1 непрерывный ГиБ памяти не может быть удовлетворен, даже если 2 ГиБ памяти не могут быть удовлетворены. Всего ГиБ бесплатны.

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

Снижение производительности

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

Более тонкая проблема заключается в том, что фрагментация может преждевременно исчерпать кэш, что приведет к его перегрузке из-за того, что кэши содержат блоки, а не отдельные данные. Например, предположим, что программа имеет рабочий набор размером 256 КиБ и работает на компьютере с кешем 256 КиБ (скажем, инструкции L2 + кеш данных), поэтому весь рабочий набор помещается в кеш и, таким образом, выполняется быстро, по крайней мере, в с точки зрения попаданий в кэш. Предположим далее, что он имеет 64 записи резервного буфера трансляции размером 4 КиБ (TLB), каждая для страницы : каждый доступ к памяти требует трансляции из виртуальной в физическую, которая выполняется быстро, если страница находится в кеше (здесь TLB). Если рабочий набор нефрагментирован, то он поместится ровно на 64 страницы ( рабочий набор страниц будет состоять из 64 страниц), и все запросы к памяти могут выполняться из кеша. Однако если рабочий набор фрагментирован, то он не уместится в 64 страницы, и выполнение замедлится из-за перебора: страницы будут неоднократно добавляться и удаляться из TLB во время работы. Таким образом, размер кэша при проектировании системы должен включать запас для учета фрагментации.

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

Фрагментация памяти — это ядра проблема уровня программирования . Во время вычислений приложений в реальном времени уровень фрагментации может достигать 99% и может привести к сбоям в работе системы или другим нестабильным ситуациям. Такого типа сбоя системы сложно избежать, поскольку невозможно предвидеть критический рост уровня фрагментации памяти. Однако, хотя в случае чрезмерной фрагментации памяти система может оказаться неспособной продолжать выполнение всех программ, хорошо спроектированная система должна иметь возможность восстановиться после критического состояния фрагментации путем перемещения некоторых блоков памяти, используемых самой системой. чтобы обеспечить объединение свободной памяти в меньшее количество блоков большего размера или, в худшем случае, путем закрытия некоторых программ для освобождения их памяти и последующей дефрагментации полученной суммы свободной памяти. Это, по крайней мере, позволит избежать настоящего сбоя в смысле сбоя системы и позволит системе продолжать работу некоторых программ, сохранять данные программ и т. д.

Фрагментация — это явление проектирования системного программного обеспечения; различное программное обеспечение будет в разной степени подвержено фрагментации, и можно спроектировать систему, которая никогда не будет вынуждена завершать работу или завершать процессы в результате фрагментации памяти.

Аналогичные явления

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

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

Некоторые флэш-файловые системы имеют несколько различных типов внутренней фрагментации, включая «мертвое пространство» и «темное пространство».

См. также

• Дефрагментация
• Фрагментация файловой системы
• Управление памятью
• Управление памятью (операционные системы)
• Блок (хранение данных)
• Кластер данных

Источники

• http://www.edn.com/design/systems-design/4333346/Handling-memory-fragmentation
• http://www.sqlservercentral.com/articles/performance+tuning/performancemonitoringbyinternalfragmentationmeasur/2014/
• C++ Footprint и оптимизация производительности, Р. Александер; Дж. Бенсли, издательство Sams Publisher, первое издание, номер страницы: 128, номер ISBN: 9780672319044.
• Там же, стр. №: 129.