Как бороться с внешней фрагментацией, как пейджинг помогает с внешней фрагментацией?
Я знаю, что есть много вопросов относительно проблемы, на которую я указываю, но я не смог найти никакого сложного ответа (ни в Stackru, ни в других источниках).
Я хотел бы спросить о проблеме фрагментации кучи (RAM).
Как я понял, существует два вида фрагментации:внутренняя - связана с разницей между размером единицы выделения (AU) и размером выделенной памяти AM (неиспользуемая память равна AM % AU),внешняя - связана с непрерывными областями свободной памяти. памяти, поэтому даже если сумма свободных областей памяти может обработать новый запрос на выделение, он завершится неудачей, если не будет области продолжения, которая может обработать его.
Это вполне понятно. Проблемы начинаются, когда появляется "пейджинг".
Иногда я могу найти информацию о том, что подкачка решает проблему внешней фрагментации. Действительно, я согласен, что благодаря подкачке страниц ОС может создавать практически непрерывные области памяти, выделенные процессу, даже если физически части памяти разбросаны.
Но как именно это помогает с внешней фрагментацией? Я имею в виду, предполагая, что размер страницы составляет 4 КБ, и мы хотим выделить 16 КБ, тогда, конечно, нам просто нужно найти четыре пустых фрейма страниц, даже если физически они не являются частью области продолжения.
Но что в случае меньшего распределения? Я считаю, что сама страница все еще может быть фрагментированной и (в худшем случае) ОС все еще должна предоставлять новый кадр, если старый не может использоваться для выделения запрошенной памяти.
Так что, (если предположить наихудший случай) рано или поздно, с подкачкой или без нее, долго работающее приложение, которое выделяет и освобождает память кучи (разных размеров), перейдет в состояние нехватки памяти из-за внешней фрагментации?
Так что вопрос в том, как бороться с внешней фрагментацией? Собственная реализация алгоритма размещения? Пейджинг (как я уже писал, не уверен, что это помогает)? Что-то еще? Предоставляет ли ОС (Windows, Linux) некоторые методы дефрагментации?
Наиболее радикальным решением является запрет использования кучи, но действительно ли это необходимо для платформ с подкачкой, виртуальными адресными пространствами, виртуальной памятью и т. Д., И единственная проблема заключается в том, что приложения должны работать безостановочно в течение многих лет?
Еще одна проблема... является ли внутренняя фрагментация неоднозначным термином? Где-то я заметил определение, что внутренняя фрагментация указывает на часть фрейма страницы, которая тратится впустую, потому что процессу не требуется больше памяти, но один фрейм не может принадлежать более чем одному процессу.
Я выделил вопросы, чтобы люди, которые спешат, могли найти вопрос, не читая все.
С уважением!
1 ответ
"Фрагментация" действительно не очень точный термин. Но мы можем с уверенностью сказать, что когда запущенное приложение нуждается в блоке n
байты и есть n
или больше байтов не используются, но мы не можем получить требуемый блок, тогда "память слишком фрагментирована".
Но как именно это [пейджинг] помогает с внешним распределением [я полагаю, вы имеете в виду фрагментацию]?
Здесь действительно нет ничего сложного. Внешняя фрагментация - это свободная память между выделенными блоками, которая "слишком мала", чтобы удовлетворить любые требования приложения. Это общая концепция. Определение "слишком маленький" зависит от приложения. Тем не менее, если выделенные блоки могут попадать на любую границу, то после многих распределений и откреплений легко получить множество таких фрагментов. Пейджинг помогает с внешней фрагментацией двумя способами.
Во-первых, он подразделяет память на смежные блоки фиксированного размера - страницы, которые "достаточно велики", поэтому они никогда не бесполезны. Опять же определение "достаточно большой" не является точным. Но большинство приложений будут иметь множество требований, удовлетворяемых одной страницей 4k. Поскольку при выделении страницы или меньше не может возникнуть проблем с внешней фрагментацией, проблема была смягчена.
Во-вторых, аппаратное обеспечение подкачки обеспечивает уровень косвенности между страницами приложения и страницами физической памяти. Поэтому любая свободная страница физической памяти может использоваться для удовлетворения любого запроса приложения, независимо от его размера. Например, предположим, что у вас есть 100 физических страниц с выделением каждой другой физической страницы (50 из них). Без оборудования для отображения страниц самый большой запрос на непрерывную память, который может быть удовлетворен, составляет 1 страницу. С картографированием это 50 страниц. (Я игнорирую виртуальные страницы, изначально выделенные без отображенной физической страницы. Это еще одно обсуждение.)
Но что в случае меньшего распределения?
Опять все довольно просто. Если единицей выделения является страница, то любое выделение меньше страницы дает неиспользованную часть. Это внутренняя фрагментация: неиспользуемая память в выделенном блоке. Чем больше вы делаете единицы размещения (они не должны быть одной страницей), тем больше памяти будет неиспользуемым из-за внутренней фрагментации. В среднем это будет стремиться к половине единицы размещения. Следовательно, хотя ОС обычно выделяются в единицах страниц, большинство распределителей памяти на стороне приложения запрашивают у ОС очень небольшое количество (часто один) больших блоков (страниц). Внутри они используют гораздо меньшие единицы выделения: довольно часто встречаются 4-16 байт.
Итак, вопрос в том, как бороться с внешним распределением [я полагаю, вы имеете в виду фрагментацию]? Так что, (если предположить наихудший случай) рано или поздно, с подкачкой или без нее, долго работающее приложение, которое выделяет и освобождает память кучи (разных размеров), перейдет в состояние нехватки памяти из-за внешней фрагментации?
Если я вас правильно понимаю, вы спрашиваете, неизбежна ли фрагментация. За исключением особых условий (например, приложению нужны блоки только одного размера), ответ - да. Но это не значит, что это обязательно проблема.
Распределители памяти используют интеллектуальные алгоритмы, которые довольно эффективно ограничивают фрагментацию. Например, они могут поддерживать "пулы" с разными размерами блоков, используя пул с размерами блоков, наиболее близко соответствующими данному запросу. Это имеет тенденцию ограничивать как внутреннюю, так и внешнюю фрагментацию. Реальный пример, который очень хорошо задокументирован, это dlmalloc. Исходный код также очень понятен.
Конечно, любой распределитель общего назначения может дать сбой при определенных условиях. По этой причине современные языки (C++ и Ada - два, которые я знаю) позволяют вам предоставлять специальные распределители для объектов данного типа. Обычно - для объекта фиксированного размера - они могут просто поддерживать свободный список с предварительно нанесенным покрытием, поэтому фрагментация для этого конкретного случая равна нулю, а распределение / освобождение происходит очень быстро.
Еще одно замечание: можно полностью устранить фрагментацию с помощью копирования / сжатия сборки мусора. Конечно, для этого требуется языковая поддержка, а также счет за производительность. Копирующий сборщик мусора сжимает кучу, перемещая объекты, чтобы полностью исключить неиспользуемое пространство всякий раз, когда он запускается для восстановления хранилища. Для этого он должен обновить каждый указатель в работающей программе на новое местоположение соответствующего объекта. Хотя это может показаться сложным, я реализовал копирующий сборщик мусора, и это не так уж плохо. Алгоритмы очень крутые. К сожалению, семантика многих языков (например, C и C++) не позволяет найти каждый указатель в работающей программе, что необходимо.
Наиболее радикальным решением является запрет использования кучи, но действительно ли это необходимо для платформ с подкачкой, виртуальными адресными пространствами, виртуальной памятью и т. Д., И единственная проблема заключается в том, что приложения должны работать безостановочно в течение многих лет?
Хотя распределители общего назначения хороши, они не гарантированы. Для систем, критичных для безопасности, или систем с жестким ограничением в режиме реального времени весьма обычно избежать полного использования кучи. С другой стороны, когда не требуется абсолютная гарантия, распределитель общего назначения часто в порядке. Есть много систем, которые отлично работают с жесткими нагрузками в течение длительных периодов времени с использованием распределителей общего назначения: фрагментация достигает приемлемого устойчивого состояния и не вызывает проблем.
Еще одна проблема... является ли внутренняя фрагментация неоднозначным термином?
Термин не является двусмысленным, но используется в разных контекстах. Инвариант заключается в том, что он ссылается на неиспользуемую память внутри выделенных блоков.
В литературе по ОС обычно предполагается, что единица выделения - это страницы. Например, Linux sbrk позволяет запрашивать конец сегмента данных где угодно, но Linux выделяет страницы, а не байты, поэтому неиспользуемая часть последней страницы является внутренней фрагментацией с точки зрения ОС.
Обсуждения, ориентированные на приложения, обычно предполагают, что распределение происходит в "блоках" или "кусках" произвольного размера. dlmalloc использует около 128 дискретных размеров чанков, каждый из которых поддерживается в своем собственном свободном списке. Кроме того, он будет произвольно распределять очень большие блоки с помощью системных вызовов отображения памяти ОС, поэтому существует не более размера страницы (минус 1 байт) несоответствия между запросом и фактическим распределением. Очевидно, что это минимизирует внутреннюю фрагментацию. Фрагментация, вызвавшая данное выделение, является разницей между запросом и фактически выделенным фрагментом. Поскольку существует очень много размеров фрагментов, эта разница строго ограничена. С другой стороны, многие размеры чанков увеличивают вероятность проблем с внешней фрагментацией: свободная память может состоять полностью из чанков, которые хорошо управляются dlmalloc, но слишком малы, чтобы соответствовать требованиям приложения.