Из Википедии, свободной энциклопедии
  (Перенаправлено из внутренней фрагментации )
Перейти к навигации Перейти к поиску
Информацию о фрагментации файловой системы см. В разделе Фрагментация файловой системы .

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

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

Основной принцип [ править ]

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

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

Типы [ править ]

Внутренняя фрагментация [ править ]

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

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

Внешняя фрагментация [ править ]

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

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

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

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

Фрагментация данных [ править ]

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

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

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

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

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

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

Обзор [ править ]

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

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

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

Проблемы [ править ]

Ошибка хранилища [ править ]

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

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

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

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

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

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

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

Аналогичные явления [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ «Разбиение на разделы, размеры разделов и надписи на дисках» . Руководство для ПК. 17 апреля 2001 . Проверено 20 января 2012 .
  2. ^ "Переключатели: Секторная копия" . Symantec. 2001-01-14 . Проверено 20 января 2012 .
  3. ^ Д. Саманта. «Классические структуры данных» 2004. с. 76
  4. ^ a b Ousterhout, JK (1982). «Методы планирования для параллельных систем» (PDF) . Труды Третьей Международной конференции по распределенным вычислительным системам . С. 22–30.
  5. ^ . Адриан Хантер. «Краткое введение в дизайн UBIFS» . 2008. и т. Д. С. 8.

Источники [ править ]

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