В компьютерном хранилище фрагментация — это явление, при котором дисковое пространство, например, память компьютера или жесткий диск , используется неэффективно, что снижает емкость или производительность, а часто и то, и другое. Точные последствия фрагментации зависят от конкретной системы распределения памяти и конкретной формы фрагментации. Во многих случаях фрагментация приводит к тому, что дисковое пространство «тратится впустую», и программы будут работать неэффективно из-за нехватки памяти.
При фрагментации основной памяти, когда компьютерная программа запрашивает блоки памяти из компьютерной системы, блоки выделяются кусками. Когда компьютерная программа заканчивает работу с куском, она может освободить его обратно в систему, сделав его доступным для последующего выделения другой или той же программе. Размер и время, в течение которого кусок удерживается программой, варьируются. В течение своего жизненного цикла компьютерная программа может запрашивать и освобождать много кусков памяти.
Фрагментация может возникнуть, когда блок памяти запрашивается программой и выделяется этой программе, но программа его не освободила. [1] Это приводит к тому, что теоретически «доступная», неиспользуемая память помечается как выделенная, что уменьшает объем глобально доступной памяти, затрудняя для программ запрос и доступ к памяти.
При запуске программы свободные области памяти длинные и непрерывные. Со временем и по мере использования длинные непрерывные области фрагментируются на все более мелкие непрерывные области. В конце концов, программа может не иметь возможности получать большие непрерывные куски памяти.
Существует три различных, но связанных формы фрагментации: внешняя фрагментация, внутренняя фрагментация и фрагментация данных, которые могут присутствовать изолированно или в сочетании. Фрагментация часто принимается в обмен на улучшение скорости или простоты. Аналогичные явления происходят и для других ресурсов, таких как процессоры; см. ниже.
Память подкачки создает внутреннюю фрагментацию, поскольку будет выделен весь кадр страницы независимо от того, требуется ли столько памяти. [2] Из-за правил, регулирующих выделение памяти , иногда выделяется больше памяти компьютера , чем необходимо. Например, память может быть предоставлена программам только частями (обычно кратными 4 байтам), и в результате, если программа запросит, возможно, 29 байтов, она фактически получит часть в 32 байта. Когда это происходит, избыточная память пропадает. В этом сценарии неиспользуемая память, известная как резервное пространство , содержится в выделенной области. Такое расположение, называемое фиксированными разделами, страдает от неэффективного использования памяти — любой процесс, независимо от того, насколько он мал, занимает целый раздел. Эти отходы называются внутренней фрагментацией . [3] [4]
В отличие от других типов фрагментации, внутреннюю фрагментацию трудно исправить; обычно лучший способ ее устранить — это изменить дизайн. Например, при динамическом распределении памяти пулы памяти радикально сокращают внутреннюю фрагментацию, распределяя издержки пространства по большему количеству объектов.
Внешняя фрагментация возникает, когда свободная память разделяется на небольшие блоки и перемежается с выделенной памятью. Это слабость некоторых алгоритмов распределения памяти, когда они не могут эффективно упорядочить память, используемую программами. Результатом является то, что, хотя свободное хранилище доступно, оно фактически непригодно для использования, поскольку разделено на части, которые по отдельности слишком малы, чтобы удовлетворить потребности приложения. Термин «внешний» относится к тому факту, что неиспользуемое хранилище находится за пределами выделенных областей.
Например, рассмотрим ситуацию, когда программа выделяет три непрерывных блока памяти, а затем освобождает средний блок. Распределитель памяти может использовать этот свободный блок памяти для будущих выделений. Однако он не может использовать этот блок, если выделяемая память больше по размеру, чем этот свободный блок.
Внешняя фрагментация также происходит в файловых системах, поскольку создается много файлов разного размера, изменяет размер и удаляется. Эффект становится еще хуже, если файл, разделенный на множество мелких частей, удаляется, поскольку это оставляет такие же небольшие области свободного пространства.
Фрагментация данных происходит, когда набор данных в памяти разбивается на множество частей, которые не находятся близко друг к другу. Обычно это результат попытки вставить большой объект в хранилище, которое уже подверглось внешней фрагментации. Например, файлы в файловой системе обычно управляются в единицах, называемых блоками или кластерами . Когда создается файловая система, есть свободное место для хранения блоков файлов вместе непрерывно . Это позволяет выполнять быстрое последовательное чтение и запись файлов. Однако по мере добавления, удаления и изменения размера файлов свободное пространство становится внешне фрагментированным, оставляя только небольшие дыры для размещения новых данных. Когда записывается новый файл или когда существующий файл расширяется, операционная система помещает новые данные в новые несмежные блоки данных, чтобы они поместились в доступные дыры. Новые блоки данных обязательно разбросаны, замедляя доступ из-за времени поиска и задержки вращения головки чтения/записи, а также влекут за собой дополнительные накладные расходы для управления дополнительными расположениями. Это называется фрагментацией файловой системы .
При записи нового файла известного размера, если есть какие-либо пустые дыры, которые больше, чем этот файл, операционная система может избежать фрагментации данных, поместив файл в любую из этих дыр. Существует множество алгоритмов для выбора, в какую из этих потенциальных дыр поместить файл; каждый из них является эвристическим приближенным решением проблемы упаковки в контейнеры . Алгоритм «наилучшего соответствия» выбирает наименьшее отверстие, которое достаточно велико. Алгоритм «наихудшего соответствия» выбирает наибольшее отверстие. Алгоритм « первого соответствия » выбирает первое отверстие, которое достаточно велико. Алгоритм «следующего соответствия» отслеживает, где был записан каждый файл. Алгоритм «следующего соответствия» быстрее, чем «первое соответствие», которое в свою очередь быстрее, чем «наилучшее соответствие», которое имеет ту же скорость, что и «наихудшее соответствие». [5]
Так же, как сжатие может устранить внешнюю фрагментацию, фрагментация данных может быть устранена путем перераспределения хранилища данных таким образом, чтобы связанные части были близко друг к другу. Например, основная задача инструмента дефрагментации заключается в перераспределении блоков на диске таким образом, чтобы блоки каждого файла были смежными. Большинство утилит дефрагментации также пытаются уменьшить или устранить фрагментацию свободного пространства. Некоторые перемещающиеся сборщики мусора , утилиты, которые выполняют автоматическое управление памятью, также перемещают связанные объекты близко друг к другу (это называется сжатием ) для повышения производительности кэша.
Есть четыре типа систем, которые никогда не подвергаются фрагментации данных — они всегда хранят каждый файл непрерывно. Все четыре типа имеют существенные недостатки по сравнению с системами, которые допускают хотя бы некоторую временную фрагментацию данных:
По сравнению с внешней фрагментацией, накладные расходы и внутренняя фрагментация приводят к небольшим потерям в плане неиспользуемой памяти и снижения производительности. Она определяется как:
Фрагментация 0% означает, что вся свободная память находится в одном большом блоке; фрагментация составляет 90% (например), когда имеется 100 МБ свободной памяти, но наибольший свободный блок памяти для хранения составляет всего 10 МБ.
Внешняя фрагментация, как правило, представляет собой меньшую проблему в файловых системах, чем в системах хранения первичной памяти (ОЗУ), поскольку программы обычно требуют, чтобы их запросы на хранение в ОЗУ выполнялись непрерывными блоками, но файловые системы обычно проектируются так, чтобы иметь возможность использовать любую коллекцию доступных блоков (фрагментов) для сборки файла, который логически выглядит непрерывным. Поэтому, если сильно фрагментированный файл или много маленьких файлов удаляются из полного тома, а затем создается новый файл с размером, равным вновь освобожденному пространству, новый файл просто повторно использует те же фрагменты, которые были освобождены при удалении. Если был удален один файл, новый файл будет таким же фрагментированным, как и старый файл, но в любом случае не будет никаких препятствий для использования всего (сильно фрагментированного) свободного пространства для создания нового файла. С другой стороны, в оперативной памяти используемые системы хранения часто не могут собрать большой блок для удовлетворения запроса из небольших несмежных свободных блоков, и поэтому запрос не может быть выполнен, а программа не может продолжить выполнение того, для чего ей нужна эта память (если только она не сможет повторно выдать запрос в виде ряда более мелких отдельных запросов).
Самая серьезная проблема, вызванная фрагментацией, — это сбой процесса или системы из-за преждевременного исчерпания ресурсов: если необходимо сохранить непрерывный блок, но его невозможно сохранить, происходит сбой. Фрагментация приводит к тому, что это происходит, даже если ресурса достаточно, но не непрерывного объема. Например, если у компьютера 4 ГиБ памяти и 2 ГиБ свободны, но память фрагментирована в чередующейся последовательности 1 МиБ используется, 1 МиБ свободен, то запрос на 1 непрерывный ГиБ памяти не может быть удовлетворен, даже если всего 2 ГиБ свободны.
Чтобы избежать этого, распределитель может вместо сбоя запустить дефрагментацию (или цикл уплотнения памяти) или другое восстановление ресурсов, например, цикл сборки мусора, в надежде, что затем он сможет удовлетворить запрос. Это позволяет процессу продолжиться, но может серьезно повлиять на производительность.
Фрагментация приводит к снижению производительности по ряду причин. В основном фрагментация увеличивает работу, необходимую для выделения и доступа к ресурсу. Например, на жестком диске или ленточном накопителе последовательное чтение данных происходит очень быстро, но поиск по другому адресу происходит медленно, поэтому чтение или запись фрагментированного файла требует многочисленных поисков и, таким образом, происходит намного медленнее, в дополнение к большему износу устройства. Кроме того, если ресурс не фрагментирован, запросы на выделение могут быть просто удовлетворены путем возврата одного блока с начала свободной области. Однако он фрагментирован, запрос требует либо поиска достаточно большого свободного блока, что может занять много времени, либо выполнения запроса несколькими меньшими блоками (если это возможно), что приводит к фрагментации этого выделения и требует дополнительных накладных расходов для управления несколькими частями.
Более тонкая проблема заключается в том, что фрагментация может преждевременно исчерпать кэш, вызывая пробуксовку из-за того, что кэши содержат блоки, а не отдельные данные. Например, предположим, что программа имеет рабочий набор размером 256 КБ и работает на компьютере с кэшем размером 256 КБ (скажем, кэш инструкций L2+данных), поэтому весь рабочий набор помещается в кэш и, таким образом, выполняется быстро, по крайней мере, с точки зрения попаданий в кэш. Предположим далее, что у нее есть 64 записи буфера поиска трансляции (TLB), каждая для страницы размером 4 КБ : каждый доступ к памяти требует виртуального в физический перевод, что быстро, если страница находится в кэше (здесь TLB). Если рабочий набор не фрагментирован, то он поместится ровно на 64 страницы ( рабочий набор страницы будет составлять 64 страницы), и все поиски в памяти могут быть выполнены из кэша. Однако если рабочий набор фрагментирован, то он не поместится в 64 страницы, и выполнение замедлится из-за перегрузки: страницы будут многократно добавляться и удаляться из TLB во время работы. Таким образом, размер кэша в проекте системы должен включать запас для учета фрагментации.
Фрагментация памяти — одна из самых серьезных проблем, с которой сталкиваются системные администраторы. [ требуется цитата ] Со временем это приводит к снижению производительности системы. В конечном итоге фрагментация памяти может привести к полной потере (пригодной для использования приложением) свободной памяти.
Фрагментация памяти — это проблема уровня программирования ядра . Во время вычислений приложений в реальном времени уровень фрагментации может достигать 99% и может приводить к сбоям системы или другим нестабильностям. [ требуется цитата ] Такого типа сбоя системы может быть трудно избежать, поскольку невозможно предвидеть критический рост уровня фрагментации памяти. Однако, хотя система может оказаться неспособной продолжать выполнять все программы в случае чрезмерной фрагментации памяти, хорошо спроектированная система должна быть способна восстанавливаться из состояния критической фрагментации, перемещая некоторые блоки памяти, используемые самой системой, чтобы обеспечить консолидацию свободной памяти в меньшее количество более крупных блоков, или, в худшем случае, завершая некоторые программы, чтобы освободить их память, а затем дефрагментируя полученную сумму свободной памяти. Это, по крайней мере, позволит избежать настоящего сбоя в смысле отказа системы и позволит системе продолжать выполнять некоторые программы, сохранять данные программ и т. д.
Фрагментация — это явление, присущее проектированию системного программного обеспечения; разное программное обеспечение будет подвержено фрагментации в разной степени, и можно разработать систему, которая никогда не будет вынуждена завершать работу или уничтожать процессы из-за фрагментации памяти.
Хотя фрагментация наиболее известна как проблема распределения памяти, аналогичные явления происходят и с другими ресурсами , в частности, с процессорами. [6] Например, в системе, которая использует разделение времени для вытесняющей многозадачности , но не проверяет, заблокирован ли процесс, процесс, который выполняется в течение части своего временного среза, но затем блокируется и не может продолжиться в течение оставшейся части своего временного среза, тратит время впустую из-за результирующей внутренней фрагментации временных срезов. Что еще более важно, само разделение времени вызывает внешнюю фрагментацию процессов из-за их запуска во фрагментированных временных срезах, а не в одном непрерывном запуске. Результирующая стоимость переключения процессов и повышенное давление на кэш из-за нескольких процессов, использующих одни и те же кэши, могут привести к снижению производительности.
В параллельных системах , особенно распределенных системах , когда группа процессов должна взаимодействовать для продвижения вперед, если процессы запланированы на разное время или на разных машинах (фрагментированы по времени или машинам), время, потраченное на ожидание друг друга или на общение друг с другом, может серьезно ухудшить производительность. Вместо этого производительные системы требуют совместного планирования группы. [6]
Некоторые файловые системы флэш-памяти имеют несколько различных видов внутренней фрагментации, включающих «мертвое пространство» и «темное пространство». [7]
