Способы разрешения проблемы фрагментации памяти

Механизм разделения центральной памяти. Распределение памяти с разделами фиксированного размера. Распределение памяти с разделами переменного размера. Проблема фрагментации памяти и ее решение

Методы распределения оперативной памяти разделены на два класса: методы, в которых используется перемещение сегментов процессов между оперативной памятью и диском, и методы, в которых внешняя память не привлекается

Распределение памяти фиксированными разделами

Очередной новый процесс, поступивший на выполнение, помещается либо в общую очередь (рис. 2.11, а), либо в очередь к некоторому разделу (рис. 2.11, 6).

Подсистема управления памятью в этом случае выполняет следующие задачи:

• Сравнивает объем памяти, требуемый для вновь поступившего процесса, с размерами свободных разделов и выбирает подходящий раздел;
• Осуществляет загрузку программы в один из разделов и настройку адресов.

Распределение памяти динамическими разделами

В этом случае память машины не делится заранее на разделы. Сначала вся память, отводимая для приложений, свободна. Каждому вновь поступающему на выполнение приложению на этапе создания процесса выделяется вся необходимая ему память (если достаточный объем памяти отсутствует, то приложение не принимается на выполнение и процесс для него не создается). После завершения процесса память освобождается, и на это место может быть загружен другой процесс. Таким образом, в произвольный момент времени оперативная память представляет собой случайную последовательность занятых и свободных участков (разделов) произвольного размера. На рис. 2.12 показано состояние памяти в различные моменты времени при использовании динамического распределения. Так, в момент t₀ в памяти находится только ОС, а к моменту t₁ память разделена между 5 процессами, причем процесс П4, завершаясь, покидает память. На освободившееся от процесса П4 место загружается процесс П6, поступивший в момент t₃.

Функции операционной системы, предназначенные для реализации данного метода управления памятью, перечислены ниже.

• Ведение таблиц свободных и занятых областей, в которых указываются начальные адреса и размеры участков памяти.
• При создании нового процесса — анализ требований к памяти, просмотр таблицы свободных областей и выбор раздела, размер которого достаточен для размещения кодов и данных нового процесса. Выбор раздела может осуществляться по разным правилам, например: «первый попавшийся раздел достаточного размера», «раздел, имеющий наименьший достаточный размер» или «раздел, имеющий наибольший достаточный размер».
• Загрузка программы в выделенный ей раздел и корректировка таблиц свободных и занятых областей. Данный способ предполагает, что программный код не перемещается во время выполнения, а значит, настройка адресов может быть проведена единовременно во время загрузки.
• После завершения процесса корректировка таблиц свободных и занятых областей.

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

Проблема фрагментации памяти и способы ее разрешения.

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

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

Так как программы перемещаются по оперативной памяти в ходе своего выполнения, то в данном случае невозможно выполнить настройку адресов с помощью перемещающего загрузчика. Здесь более подходящим оказывается динамическое преобразование адресов.

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

Источник

Борьба с фрагментацией памяти

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

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

В настоящее время все множество реализаций виртуальной памяти может быть представлено тремя классами.

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

2. Сегментная виртуальная память предусматривает перемещение данных сегментами — частями виртуального адресного пространства произвольного размера, полученными с учетом смыслового значения данных.

3. Сегментно-страничная виртуальная память использует двухуровневое деление: виртуальное адресное пространство делится на сегменты, а затем сегменты делятся на страницы. Единицей перемещения данных здесь является страница.

Источник

Большая Энциклопедия Нефти и Газа

Проблема — фрагментация

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

Проблема фрагментации памяти может решаться и решается различными способами. [2]

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

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

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

Схема распределения памяти страницами решает проблему фрагментации без необходимости переорганизации разделов после окончания некоторого задания. Например, на рис. 9.13 показано 2000 байтов неиспользуемой памяти, но они не образуют непрерывную область. [7]

Страничная организация памяти представляет собой другое решение проблемы фрагментации . [8]

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

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

Представленная на рис. 9.12 схема распределения памяти перемещаемыми разделами является одним из решений проблемы фрагментации . [11]

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

Распределение памяти страницами решает проблему фрагментации памяти без необходимости перемещения разделов после окончания некоторого задания. Оно позволяет рассматривать адресное пространство задания как непрерывное. Требуемые заданию страницы могут загружаться в основную память не одновременно, а по мере необходимости. Для программиста память однородна. [13]

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

Было бы крайне привлекательно объединить достоинства всех ранее рассмотренных методов. Сегментация может использоваться для совместного использования и организации защиты программных ресурсов; страничная организация решает проблемы фрагментации и перекомпоновки; распределение страницами по запросам устраняет ограничения на размер адресного пространства. На рис. 9.19 показана система адресации с использованием сегментирования, в которой для каждого сегмента предусмотрена своя таблица страниц. [15]

Источник

Если данные не помещаются в память. Простейшие методы

Самка трубкозуба с детёнышем. Фото: Scotto Bear, CC BY-SA 2.0

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

Проблема в нехватке памяти. Если у вас 16 гигабайт ОЗУ, вы не сможете туда загрузить стогигабайтный файл. В какой-то момент у ОС закончится память, она не сможет выделить новую, и программа вылетит.

Что делать?

Ну, можете развернуть кластер Big Data, всего-то:

• Найти кластер компьютеров.
• За неделю его настроить.
• Изучить новый API и переписать свой код.

Это дорого и неприятно. К счастью, зачастую и не нужно.

Нам требуется простое и лёгкое решение: обрабатывать данные на одном компьютере, с минимальной настройкой и максимальным использованием уже подключенных библиотек. Почти всегда это возможно с помощью простейших методов, которые иногда называют «вычислениями вне памяти» (out-of-core computation).

В этой статье обсудим:

• Зачем нам вообще нужна оперативная память.
• Самый простой способ обработать данные, которые не помещаются в память — потратить немножко денег.
• Три основных программных метода обработки чрезмерных объёмов данных: сжатие, разбиение на блоки и индексирование.

В будущих статьях на практике покажем, как применять эти методы с конкретными библиотеками, таким как NumPy и Pandas. Но сначала теория.

Зачем вообще нужна оперативная память?

Прежде чем перейти к обсуждению решений, давайте проясним, почему эта проблема вообще существует. В оперативную память (RAM) можно записывать данные, но и на жёсткий диск тоже, так зачем вообще нужна RAM? Диск дешевле, у него обычно нет проблем с нехваткой места, почему же просто не ограничиться чтением и записью с диска?

Теоретически это может сработать. Но даже современные быстрые SSD работают намного, намного медленнее, чем RAM:

16 000 наносекунд

Чтение из RAM:

100 наносекунд

Для быстрых вычислений у нас не остаётся выбора: данные приходится записывать в ОЗУ, иначе код замедлится в 150 раз.

Самое простое решение: больше оперативной памяти

Самое простое решение проблемы нехватки оперативной памяти — потратить немного денег. Вы можете купить мощный компьютер, сервер или арендовать виртуальную машину с большим количеством памяти. В ноябре 2019 года быстрый поиск и очень краткое сравнение цен даёт такие варианты:

• Купить Thinkpad M720 Tower с 6 ядрами и 64 ГБ оперативной памяти за $1074
• Арендовать в облаке виртуальную машину с 64 ядрами и 432 ГБ оперативной памяти за $3,62/час

Это просто цифры после быстрого поиска. Проведя хорошее исследование, вы наверняка найдёте более выгодные предложения.

Потратить немного денег на аппаратное обеспечение, чтобы данные поместились в ОЗУ, — зачастую самое дешёвое решение. В конце концов, наше время дорого. Но иногда этого недостаточно.

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

Если покупка/аренда большого объёма RAM не решает проблему или невозможна, следующий шаг — оптимизировать само приложение, чтобы оно расходовало меньше памяти.

Техника № 1. Сжатие

Сжатие позволяет поместить те же данные в меньший объём памяти. Есть две формы сжатия:

• Без потерь: после сжатия сохраняется в точности та же информация, что и в исходных данных.
• С потерями: сохраняемые данные теряют некоторые детали, но в идеале это не сильно влияет на результаты расчёта.

Просто для ясности, речь не о файлах ZIP или gzip, когда происходит сжатие данных на диске. Для обработки данных из ZIP-файла обычно нужно распаковать его, а потом загрузить файлы в память. Так что это не поможет.

Что нам нужно, так это сжатие представления данных в памяти.

Предположим, в ваших данных хранится только два возможных значения, и больше ничего: «AVAILABLE» и «UNAVAILABLE» . Вместо сохранения строк с 10 байтами или более на запись, вы можете сохранить их как логические значения True или False , которые кодируются просто одни байтом. Можете сжать информацию даже до одного бита, уменьшив расход памяти ещё в восемь раз.

Техника № 2. Разбиение на блоки, загрузка данных по одному блоку за раз

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

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

Но если книга не помещается в память, можно загрузить её постранично:

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

Техника № 3. Индексация, когда требуется только подмножество данных

Индексирование полезно, если нужно использовать только подмножество данных и вы собираетесь загружать разные подмножества в разное время.

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

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

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

Или можете сразу открыть алфавитный индекс в конце книги — и найти слово «трубкозуб». Там указано, что упоминания слова есть на страницах 7, 19 и 120-123. Теперь можно прочитать эти страницы, и только их, что намного быстрее.

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

Самый простой метод индексирования

Самый простой и распространённый способ индексирования — именование файлов в каталоге:

Если вам нужны данные за март 2019 года, вы просто загружаете файл 2019-Mar.csv — нет необходимости загружать данные за февраль, июль или любой другой месяц.

Дальше: применение этих методов

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

Те же методы используются в различных программных пакетах и инструментах. На них построены даже высокопроизводительные системы Big Data: например, параллельная обработка отдельных фрагментов данных.

В следующих статьях рассмотрим, как применять эти методы в конкретных библиотеках и инструментах, в том числе NumPy и Pandas.

Источник