Фрагментация памяти: причины и последствия

Введение

Неэффективное использование дискового пространства

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

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

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

Типы

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

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

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

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

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

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

Фрагментация данных возникает, когда набор данных в памяти разбивается на множество несмежных фрагментов. Обычно это результат попытки размещения большого объекта в хранилище, которое уже подверглось внешней фрагментации. Например, файлы в файловой системе обычно управляются единицами, называемыми блоками или кластерами. При создании файловой системы имеется свободное пространство для хранения файловых блоков последовательно. Это обеспечивает быстрые последовательные операции чтения и записи файлов. Однако, по мере добавления, удаления и изменения размера файлов, свободное пространство становится внешне фрагментированным, оставляя лишь небольшие промежутки для размещения новых данных. При записи нового файла или расширении существующего, операционная система помещает новые данные в несмежные блоки данных, чтобы заполнить доступные промежутки. Эти новые блоки данных неизбежно разбросаны, что замедляет доступ из-за времени поиска и задержки вращения головки чтения/записи, а также требует дополнительных накладных расходов на управление дополнительными местоположениями. Это называется фрагментацией файловой системы. При записи нового файла известного размера, если существуют пустые промежутки, превышающие размер файла, операционная система может избежать фрагментации данных, поместив файл в любой из этих промежутков. Существует множество алгоритмов для выбора подходящего промежутка; каждый из них представляет собой эвристическое приближенное решение задачи упаковки контейнеров. Алгоритм "наилучшего соответствия" выбирает наименьший промежуток, который достаточно велик. Алгоритм "наихудшего соответствия" выбирает наибольший промежуток. Алгоритм "первого соответствия" выбирает первый подходящий по размеру промежуток. Алгоритм "следующего соответствия" отслеживает местоположение записи каждого файла. Алгоритм "следующего соответствия" быстрее, чем "первого соответствия", который, в свою очередь, быстрее, чем "наилучшего соответствия", который имеет ту же скорость, что и "наихудшего соответствия". Подобно тому, как компактизация может устранить внешнюю фрагментацию, фрагментацию данных можно устранить путем реорганизации хранения данных таким образом, чтобы связанные фрагменты располагались близко друг к другу. Например, основная задача инструмента дефрагментации — переупорядочить блоки на диске, чтобы блоки каждого файла были смежными. Большинство утилит дефрагментации также пытаются уменьшить или устранить фрагментацию свободного пространства. Некоторые сборщики мусора, выполняющие автоматическое управление памятью, также перемещают связанные объекты ближе друг к другу (это называется компактизацией) для повышения производительности кэша. Существует четыре типа систем, которые никогда не сталкиваются с фрагментацией данных — они всегда хранят каждый файл последовательно. Все четыре типа имеют существенные недостатки по сравнению с системами, допускающими хотя бы временную фрагментацию данных: просто записывать каждый файл последовательно. Если недостаточно непрерывного свободного пространства для хранения файла, система немедленно отказывается его сохранять, даже если существует множество небольших фрагментов свободного пространства, образовавшихся после удаления файлов, которые в сумме превышают необходимый размер. Если недостаточно непрерывного свободного пространства для хранения файла, используйте копирующий сборщик мусора для преобразования множества небольших фрагментов свободного пространства в одну непрерывную область, достаточную для хранения файла. Это занимает гораздо больше времени, чем разбиение файла на фрагменты и размещение этих фрагментов в доступном свободном пространстве. Записывать файл в любой свободный блок через хранилище блоков фиксированного размера. Если программист выбирает слишком маленький размер блока, система не сможет сохранить некоторые файлы — файлы, превышающие размер блока — даже если существует множество свободных блоков, которых в сумме достаточно для хранения файла. Если программист выбирает слишком большой размер блока, значительное пространство будет потрачено на внутреннюю фрагментацию. Некоторые системы полностью избегают динамического выделения памяти, предварительно резервируя (непрерывное) пространство для всех возможных файлов, которые им могут понадобиться. Например, MultiFinder предварительно выделяет фрагмент оперативной памяти для каждого приложения при его запуске в соответствии с объемом оперативной памяти, заявленным программистом этого приложения.

Data fragmentation occurs when a collection of data in memory is broken up into many pieces that are not close together. It is typically the result of attempting to insert a large object into storage that has already suffered external fragmentation. For example, files in a file system are usually managed in units called blocks or clusters. When a file system is created, there is free space to store file blocks together contiguously. This allows for rapid sequential file reads and writes. However, as files are added, removed, and changed in size, the free space becomes externally fragmented, leaving only small holes in which to place new data. When a new file is written, or when an existing file is extended, the operating system puts the new data in new non contiguous data blocks to fit into the available holes. The new data blocks are necessarily scattered, slowing access due to seek time and rotational latency of the read/write head, and incurring additional overhead to manage additional locations. This is called file system fragmentation. When writing a new file of a known size, if there are any empty holes that are larger than that file, the operating system can avoid data fragmentation by putting the file into any one of those holes. There are a variety of algorithms for selecting which of those potential holes to put the file; each of them is a heuristic approximate solution to the bin packing problem. The "best fit" algorithm chooses the smallest hole that is big enough. The "worst fit" algorithm chooses the largest hole. The "first fit algorithm" chooses the first hole that is big enough. The "next fit" algorithm keeps track of where each file was written. The "next fit" algorithm is faster than "first fit," which is in turn faster than "best fit," which is the same speed as "worst fit". Just as compaction can eliminate external fragmentation, data fragmentation can be eliminated by rearranging data storage so that related pieces are close together. For example, the primary job of a defragmentation tool is to rearrange blocks on disk so that the blocks of each file are contiguous. Most defragmenting utilities also attempt to reduce or eliminate free space fragmentation. Some moving garbage collectors, utilities that perform automatic memory management, will also move related objects close together (this is called compacting) to improve cache performance. There are four kinds of systems that never experience data fragmentation—they always store every file contiguously. All four kinds have significant disadvantages compared to systems that allow at least some temporary data fragmentation:
Simply write each file contiguously. If there isn't already enough contiguous free space to hold the file, the system immediately fails to store the file—even when there are many little bits of free space from deleted files that add up to more than enough to store the file. If there isn't already enough contiguous free space to hold the file, use a copying collector to convert many little bits of free space into one contiguous free region big enough to hold the file. This takes a lot more time than breaking the file up into fragments and putting those fragments into the available free space. Write the file into any free block, through fixed size blocks storage. If a programmer picks a fixed block size too small, the system immediately fails to store some files—files larger than the block size—even when there are many free blocks that add up to more than enough to store the file. If a programmer picks a block size too big, a lot of space is wasted on internal fragmentation. Some systems avoid dynamic allocation entirely, pre storing (contiguous) space for all possible files they will need—for example, MultiFinder pre allocates a chunk of RAM to each application as it was started according to how much RAM that application's programmer claimed it would need.

Сравнение

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

Неисправность хранения

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

Ухудшение производительности

Фрагментация приводит к снижению производительности по ряду причин. Прежде всего, фрагментация увеличивает объем работы, необходимый для выделения и доступа к ресурсу. Например, на жестком диске или магнитной ленте последовательное чтение данных выполняется очень быстро, но переход к другому адресу занимает много времени, поэтому чтение или запись фрагментированного файла требует множества переходов и, следовательно, происходит значительно медленнее, а также приводит к большему износу устройства. Более того, если ресурс не фрагментирован, запросы на выделение могут быть удовлетворены простым возвратом одного блока из начала свободной области. Однако, если ресурс фрагментирован, запрос требует либо поиска достаточно большого свободного блока, что может занять продолжительное время, либо выполнения запроса несколькими меньшими блоками (если это возможно), что приводит к фрагментации выделения и требует дополнительных накладных расходов на управление этими частями. Более тонкая проблема заключается в том, что фрагментация может преждевременно исчерпать кэш, вызывая эффект "трешинга" (thrashing), поскольку кэши хранят блоки, а не отдельные данные. Например, предположим, что программа имеет рабочий набор в 256 КБ и работает на компьютере с кэшем в 256 КБ (например, кэш L2 для инструкций и данных), поэтому весь рабочий набор помещается в кэш и, следовательно, выполняется быстро, по крайней мере, с точки зрения попаданий в кэш. Предположим также, что у него есть 64 записи буфера трансляции адресов (TLB), каждая из которых соответствует странице размером 4 КБ: каждый доступ к памяти требует трансляции виртуального адреса в физический, что быстро, если страница находится в кэше (в данном случае в TLB). Если рабочий набор не фрагментирован, он поместится ровно на 64 страницы (рабочий набор страниц будет состоять из 64 страниц), и все запросы к памяти могут быть обработаны из кэша. Однако, если рабочий набор фрагментирован, он не поместится в 64 страницы, и выполнение замедлится из-за эффекта "трешинга": страницы будут многократно добавляться и удаляться из TLB во время работы. Таким образом, при проектировании системы необходимо учитывать запас по размеру кэша для компенсации фрагментации. Фрагментация памяти – одна из наиболее серьезных проблем, с которыми сталкиваются системные администраторы. Со временем это приводит к ухудшению производительности системы. В конечном итоге фрагментация памяти может привести к полной потере доступной для приложений свободной памяти. Фрагментация памяти – это проблема уровня программирования ядра. В процессе вычислений приложений в реальном времени уровень фрагментации может достигать 99%, что может привести к сбоям системы или другим нестабильностям. Избежать такого типа сбоя системы сложно, поскольку невозможно предвидеть критический рост уровня фрагментации памяти. Однако, даже если система не сможет продолжить выполнение всех программ при чрезмерной фрагментации памяти, хорошо спроектированная система должна быть способна восстановиться из критического состояния фрагментации, перемещая некоторые блоки памяти, используемые самой системой, для консолидации свободной памяти в меньшее количество больших блоков или, в худшем случае, завершая некоторые программы для освобождения их памяти и последующей дефрагментации полученного объема свободной памяти. Это, по крайней мере, позволит избежать полного сбоя системы и позволит системе продолжить выполнение некоторых программ, сохранение данных и т.д. Важно также отметить, что фрагментация является особенностью проектирования системного программного обеспечения; различные программные продукты будут подвержены фрагментации в разной степени, и возможно спроектировать систему, которая никогда не будет вынуждена завершать работу или принудительно завершать процессы из-за фрагментации памяти.

Fragmentation causes performance degradation for a number of reasons. Most basically, fragmentation increases the work required to allocate and access a resource. For example, on a hard drive or tape drive, sequential data reads are very fast, but seeking to a different address is slow, so reading or writing a fragmented file requires numerous seeks and is thus much slower, in addition to causing greater wear on the device. Further, if a resource is not fragmented, allocation requests can simply be satisfied by returning a single block from the start of the free area. However it is fragmented, the request requires either searching for a large enough free block, which may take a long time, or fulfilling the request by several smaller blocks (if this is possible), which results in this allocation being fragmented, and requiring additional overhead to manage the several pieces. A subtler problem is that fragmentation may prematurely exhaust a cache, causing thrashing, due to caches holding blocks, not individual data. For example, suppose a program has a working set of 256 KiB, and is running on a computer with a 256 KiB cache (say L2 instruction+data cache), so the entire working set fits in cache and thus executes quickly, at least in terms of cache hits. Suppose further that it has 64 translation lookaside buffer (TLB) entries, each for a 4 KiB page: each memory access requires a virtual to physical translation, which is fast if the page is in cache (here TLB). If the working set is unfragmented, then it will fit onto exactly 64 pages (the page working set will be 64 pages), and all memory lookups can be served from cache. However, if the working set is fragmented, then it will not fit into 64 pages, and execution will slow due to thrashing: pages will be repeatedly added and removed from the TLB during operation. Thus cache sizing in system design must include margin to account for fragmentation. Memory fragmentation is one of the most severe problems faced by system managers. Over time, it leads to degradation of system performance. Eventually, memory fragmentation may lead to complete loss of (application usable) free memory. Memory fragmentation is a kernel programming level problem. During real time computing of applications, fragmentation levels can reach as high as 99%, and may lead to system crashes or other instabilities. This type of system crash can be difficult to avoid, as it is impossible to anticipate the critical rise in levels of memory fragmentation. However, while it may not be possible for a system to continue running all programs in the case of excessive memory fragmentation, a well designed system should be able to recover from the critical fragmentation condition by moving in some memory blocks used by the system itself in order to enable consolidation of free memory into fewer, larger blocks, or, in the worst case, by terminating some programs to free their memory and then defragmenting the resulting sum total of free memory. This will at least avoid a true crash in the sense of system failure and allow the system to continue running some programs, save program data, etc. It is also important to note that fragmentation is a phenomenon of system software design; different software will be susceptible to fragmentation to different degrees, and it is possible to design a system that will never be forced to shut down or kill processes as a result of memory fragmentation.

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

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