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

О фрагментации файловой системы см. Фрагментация файловой системы.

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

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

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

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

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

Типы

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

Из-за правил, регулирующих выделение памяти, иногда требуется больше компьютерной памяти выделенный чем нужно. Например, память может быть предоставлена ​​программам только частями (кратными 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]

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

Смотрите также

Рекомендации

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

Источники