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

Управление основной памятью. Часть 3.

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

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

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

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

1. Расширение размера основной памяти. Например, виртуальная память позволяет расширить размер основной памяти и сделать его значительно превышающим размер реальной оперативной памяти.
2. Упорядочение запросов на участки памяти по времени освобождения. Желательно, чтобы участки памяти, освобождаемые примерно в одно и то же время, располагались в смежных областях. При этом после освобождения участков образуется единая область свободной памяти достаточно большого размера. Такое упорядочение происходит путем классификации запросов и направления их в разные области памяти, что достигается использованием аппарата подпулов, предоставляемого управлением памятью.
3. Упорядочение запросов на участки памяти по размерам. Желательно, чтобы участки памяти одинакового размера располагались в смежных областях памяти. Фрагментация таких областей не вызывает проблем распределения, так как размер запроса совпадает с размером свободных участков (фрагментов) и при наличии последних запрос может быть удовлетворен. При этом аппарат подпулов используется для классификации запросов по размерам и направлению их в разные области памяти.
4. Включение алгоритмов сборки мусора. Во многих задачах, обрабатывающих данные сложной структуры, которые включают кроме самих данных также адресные ссылки, бывает сложно определить момент, когда элемент данных становится ненужным и может освободить занимаемую память. Примером служит обработка многосвязных списков, где допускается непредсказуемое число перестраиваемых ссылок на элементы данных. При этом для определения всех элементов данных, ставших ненужными в текущий момент, включается алгоритм сборки мусора. Этот алгоритм может сочетаться с алгоритмом перестройки структуры данных с целью объединения отдельных свободных фрагментов памяти в общую область.

Источник

Способы борьбы с фрагментацией:

Увеличение размеров ОП.

Упорядочивание запросов на участки памяти по времени освобождения. Желательно одновременное освобождение смежных участков.

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

Включение алгоритмов «сборки мусора». Они позволяют определять нужные элементы и перестроить структуру данных так, чтобы объединить отдельные свободные участки.

Рассмотрим несколько таких алгоритмов.

Слияние – объединение смежных свободных участков памяти. При завершении задания MMU проверяет наличие свободных участков смежных с освобождаемой областью. Если они есть, то они объединяются.

И после слияния остаются дыры. Часто их суммарный размер больше необходимого для размещения процесса. Эта проблема решается при помощи уплотнения.

Уплотнение (или сжатие) – перемещает все занятые участки в сторону старших или младших адресов так, чтобы свободная память образовала единую область.

Отнимает ресурсы системы.

Во время уплотнения система прекращает все работы (в диалоговых системах время ответа ВС может быть непрогнозируемым).

При часто меняющихся заданиях необходимо часто проводить уплотнение. Это может сильно замедлять работу, что может перевесить все преимущества сжатия.

Типы адресов памяти

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

Виртуальные адреса (логические адреса) – адреса, которые вырабатывает транслятор (переводящий программу на машинный язык). Поскольку в общем случае неизвестно, в какое место ОЗУ будет загружена программа, транслятор присваивает адреса, начиная с нуля.

При работе с программой всегда выполняется отображение виртуальных адресов в физические и обратно. Для этого наряду с таблицами страниц в современных ВС существует аппаратное устройство «Буфер быстрого преобразования адресов» TLB (Translation Lookaside Buffer) построенный по ассоциативному принципу. Он находится рядом с каждым ядром процессора. В него загружается часть таблицы страниц, необходимая в данный момент для работы.

Совокупность виртуальных адресов процесса называется виртуальным адресным пространством (ВАП).

Каждый процесс может использовать:

Собственное ВАП (в случае, если транслятор присваивает виртуальные адреса независимо от других процессов),

общее ВАП (в некоторых ОС). В современных ОС, как правило, процессы имеют собственное виртуальное адресное пространство.

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

Учет свободных и занятых областей памяти

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

Существует два способа учета использования памяти:

а) битовые карты;

б) связные списки участков памяти.

Учет памяти с помощью битовых карт

Память разделяется на блоки размером от 512 байт – 4 Кб. Битовая карта – это таблица, в которой каждому занятому блоку соответствует один бит, равный единице, а каждому свободному блоку – бит, равный нулю (или наоборот).

При загрузке нового процесса и его завершении состояние битовой карты изменяется. При загрузке нового процесса размером N блоков ОС должна найти в битовой карте непрерывный участок из N свободных блоков.

Главная проблема такого метода – выбор размера кластера. Чем меньше кластер, тем больше битовый массив, тем медленнее поиск в битовом массиве и вся работа с ним. Но при больших кластерах значительнее потери памяти.

Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.

Источник

Нужно ли бороться с фрагментацией памяти ?Какие методы для этого существуют?

По сравнению с методом распределения памяти фиксированными разделами данный метод обладает гораздо большей гибкостью, но ему присущ очень серьезный недостаток — фрагментация памяти. Фрагментация — это наличие большого числа несмежных участков свободной памяти очень маленького размера (фрагментов). Настолько маленького, что ни одна из вновь поступающих программ не может поместиться ни в одном из участков, хотя суммарный объем фрагментов может составить значительную величину, намного превышающую требуемый объем памяти.Одним из методов борьбы с фрагментацией является перемещение всех занятых участков в сторону старших или младших адресов, так, чтобы вся свободная память образовала единую свободную область (рис. 3.1). В дополнение к функциям, которые выполняет ОС при распределении памяти динамическими разделами в данном случае она должна еще время от времени копировать содержимое разделов из одного места памяти в другое, корректируя таблицы свободных и занятых областей. Эта процедура называется сжатием. Сжатие может выполняться либо при каждом завершении процесса, либо только тогда, когда для вновь создаваемого процесса нет свободного раздела достаточного размера. В первом случае требуется меньше вычислительной работы при корректировке таблиц свободных и занятых областей, а во втором — реже выполняется процедура сжатия.Распределение памяти перемещаемыми разделамиТак как программы перемещаются по оперативной памяти в ходе своего выполнения, то в данном случае невозможно выполнить настройку адресов с помощью перемещающего загрузчика. Здесь более подходящим оказывается динамическое преобразование адресов.Хотя процедура сжатия и приводит к более эффективному использованию памяти, она может потребовать значительного времени, что часто перевешивает преимущества данного метода.Концепция сжатия применяется и при использовании других методов распределенияпамяти, когда отдельному процессу выделяется не одна сплошная область памяти, а несколько несмежных участков памяти произвольного размера (сегментов). Такой подход был использован в ранних версиях OS/2, в которых память распределялась сегментами, а возникавшая при этом фрагментация устранялась путем периодического перемещения сегментов

40.Дайте характеристику распределенной файловой системы Windows 2000. Каковы ее достоинства В каких случаях ее применяют

Распределенная файловая система (DistributedFileSystem, DFS) для Windows 2000 является средством, облегчающим управление данными в сети и их поиск. DFS позволяет объединить файловые ресурсы, находящиеся на различных компьютерах, в одно пространство имен. Теперь вместо того чтобы работать с физической сетью, состоящей из большого количества машин с собственными именами и общими ресурсами, пользователи смогут увидеть структуру логических имен, связанных с общими ресурсами.

В операционных системах Windows для получения доступа к информации, находящейся в файле, пользователю или приложению необходимо указать физический файловый сервер или общий ресурс с помощью универсального соглашения об именах (UniversalNamingConvention, UNC). Имя UNC может быть использовано напрямую или сопоставлено с именем устройства. В последнем случае для получения доступа к данным пользователь должен перейти к каталогам, находящимся ниже корневого устройства. В результате роста корпоративной сети, пользователям приходится работать со все возрастающим количеством разрозненных устройств и общих ресурсов, находящихся на различных серверах сети, что в значительной степени затрудняет поиск нужных данных. Они «теряются» среди обилия различных устройств, которые надо посетить для получения необходимой информации. Подобная проблема может быть эффективно решена с помощью распределенной файловой системы, которая берет на себя заботу о физическом обращении к информации, предоставляя пользователю возможность работать с единым пространством имен, объединяющим все серверы и общие ресурсы сети. Для этого конкретным общим ресурсам даются логические имена DFS, понятные и удобные для пользователей.Пространство имен DFS ≈ это логическое представление дисковых ресурсов сети, обращаясь к которому, пользователь может не беспокоиться о физическом расположении файлов на дисках и компьютерах.

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

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ — конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой.

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

Источник

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

Библиографическая ссылка на статью:
Абдуллаев А.П.о., Ионов А.А., Карпушкин Б.Г. Методы и решения, использованные для борьбы с фрагментацией при разработке дисковой файловой системы в ОС Linux // Современные научные исследования и инновации. 2016. № 8 [Электронный ресурс]. URL: https://web.snauka.ru/issues/2016/08/70354 (дата обращения: 10.11.2021).

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

В настоящее время в ядре Linux присутствует множество как дисковых (minixfs, ext2/3/4[1], xfs, bmfs), так и виртуальных файловых систем(vfs). При этом только в последнее время начали появляться файловые системы со встроенными средствами борьбы с фрагментаций данных. Фрагментация на уровне файловой системы влияет на производительность, как на уровне ядра, так и на уровне приложений пользовательского уровня.

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

1. Виды фрагментации

Существует два основных вида фрагментации, как самих данных, так и метаданных, на уровне файловой системы:

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

— Внешняя фрагментация вызвана проблемами при распределении дисковых блоков между файлами. Как известно, большинство современных персональных компьютеров в качестве устройства постоянного хранения информации используют жесткие диски HDD (hard disk drive), в которых имеется большая разница между скоростью одноблочных и последовательных чтений множества блоков. Поэтому расположение данных одного файла максимально плотным образом позволяет увеличить скорость чтения данных из файла.

Описанные выше проблемы касаются самих данных, но в случае с метаданными в ОС Linux также существуют проблемы, такие как хранение inode-ов (сущностей, хранящих метаинформацию о файле: размер файла, дата последнего изменения и т.д.) и управление элементами директорий (directory entry).

2. Структура разработанной файловой системы

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

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

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

— модуль работы с элементами директорий отвечает за создание, удаление, добавление, переименования, поиск по имени элементов директорий.

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

— модуль адресации блоков файла.

3. Разметка блоков файловой системы

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

1. Первый блок выделен для хранения superblock(суперблока). Суперблок – это главная структура, хранящая метаинформацию о всей файловой системе, в частности – количество свободных и всего блоков на носителе, общее количество inode-ов, кол-во свободных inode, примитивы блокировок для реализации параллельного доступа и изменения суперблока.
2. Дескрипторы групп inode-ов. Для борьбы с фрагментацией на уровне метаданных, а именно inode-ов, было решено объединить inode-ы в группы по 2^16 объектов. Такой способ был в первую очередь продиктован тем, что размер inode-а фиксирован для всех файлов, и группировка inode-ов вместе для последующей борьбы с фрагментацией позволила изменить систему поиска inode-а по номеру. К примеру, inode с номером 1123122 находится в группе inode-ов номер 17 (1123122 div 2^16 = 17) и является 9010 inode-ом в группе. Так как группа inode-ов хранится как непрерывная последовательность блоков, то для считывания информации о местоположении inode-а нет необходимости производить дисковые операции. В каждой группе inode-ов помимо самих inode-ов 2 блока занято под битовую карту группы inode-ов.
3. Дескриптор группы inode-ов хранит информацию о кол-ве свободных inode-ов в группе и номер первого блока группы. Общее кол-во дескрипторов групп inode-ов равно 2^16 степени.
4. Дескрипторы групп блоков. В качестве метода борьбы с фрагментацией на уровне данных файловой системы и для структурирования хранения данных было решено группировать блоки в непрерывные последовательности размером меньше и равно 256 Мб. Такой размер был выбран в первую очередь из расчета на то, что для адресации блока в группе блоков нужно ровно 2 байта. Помимо этого, учитывался тот фактор, что средняя скорость многоблочного чтения и записи современных жестких дисков на персональных компьютерах при 7200 об/с равна 100мб/c, т.е. можно предусмотреть возможность дефрагментации данных на группе блоков путем считывания целиком всей группы блоков в ОЗУ, ее перегруппировки и последующей записи на диск.

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

Общее кол-во дескрипторов групп блоков рассчитывается как целое от деления общего объема в мегабайтах носителя на 256 мегабайт плюс 1. В каждой группе блоков первые 2 блока заняты под битовую карту блоков.

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

4. Алгоритмы дефрагментации данных

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

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

Ниже описаны оба алгоритма аллокации.

4.1. Алгоритм аллокации непрерывной последовательности блоков.

1. Проверка на наличие необходимого количества блоков на диске, если его нет, то выход из подпрограммы.
2. Цикл по всем дескрипторам групп блоков.
3. Проверка, есть ли в группе блоков необходимое кол-во блоков, если нет, то следующая итерация.
4. Читаем битовую карту i-ой группы блоков.
5. Начиная с номера первого свободного блока итерируемся по битовой карте и ищем непрерывную последовательность блоков.
6. Если последовательность найдена, то выдаем номер блока, с которого начинается выделенная непрерывная последовательность блоков, как результат. Иначе продолжаем итерироваться по битовой карте.

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

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

4.2. Поблочный алгоритм аллокации блоков.

1. Проверка на наличие необходимого количества блоков на диске, если нет, то выход из подпрограммы.
2. Цикл по всем дескрипторам групп блоков или до тех пор, пока не выделим нужное нам количество блоков.
3. Проверка, есть ли в группе блоков необходимое количество блоков, если нет, то переход к следующей итерации.
4. Читаем битовую карту i-ой группы блоков.
5. Начиная с номера первого свободного блока, проходим по битовой карте i-ой группы блоков и ищем свободные блоки. Помечаем найденные как занятые.

Заключение

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

Библиографический список

1. Wikipedia. Ext2 filesystem – Wikipedia, The Free Encyclopedia. 2015. Режим доступа: https://ru.wikipedia.org/wiki/Ext2 . (дата обращения: 20.08.2015)
2. Э. Танненбаум. Современные операционные системы. 4-е изд. Питер, 2015.
3. Habrahabr. Пишем файловую систему в ядре Linux – Habrahabr, 2015. Режим доступа: http://habrahabr.ru/company/spbau/blog/218833/ . (дата обращения: 15.09.2015)

Количество просмотров публикации: Please wait

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться:
Регистрация

&copy 2021. Электронный научно-практический журнал «Современные научные исследования и инновации».

Источник