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

> Н 5 3

> и

Начинается с 18 Длина 2

Свободный фрапиент

Процесс в

Рис. 4.5. а - область памяти с пятью процессами и тремя свободными участками; б - соответствующая битовая карта; а - та же информация в виде списка

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

4.2.2. Управление памятью с помощью списков

Другой способ отслеживания состояния памяти предоставляет поддержка списков занятых и свободных фрагментов памяти, где фрагментом является или процесс, или участок между двумя процессами. Память, показанная на рис. 4.5, а, представлена в виде однонаправленного списка сегментов на рис. 4.5, в. Каждая запись в списке указывает: является ли область памяти свободной (Н, от hole - дыра) или занятой процессом (Р, process); адрес, с которого начинается эта область; ее длину; содержит указатель на следующую запись.

Не совсем продуманное заявление мудрого Таненбаума. На самом деле все не так медленно, если использовать scasb и битовые команды (процессоры Intel). Например, битовые массивы были применены в незаслуженно забытой OS/2 для файловой системы HPFS (самой быстрой из существующих), с целью пометки занятых/свободных секторов. Проблема объема битового массива решалась просто разбиением диска на восьмимегабайтовые (по умолчанию) участки (полосы, bands) и хранением битовой карты (2 К) в конце каждого участка. - Примеч. ред.

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

До завершения X После завершения X

Становится

Становится Становится Становится

Рис. 4.6. Четыре комбинации соседства для завершения процесса X

Если процессы и свободные участки хранятся в списке, отсортированном по адресам, существует несколько алгоритмов для предоставления памяти процессу, создаваемому заново (или для существующих процессов, загружаемых с диска). Допустим, менеджер памяти знает, сколько памяти нужно предоставить. Простейший алгоритм представляет собой выбор первого подходящего участка. Менеджер памяти просматривает список областей до тех пор, пока не находит достаточно большой свободный участок. Затем этот участок делится на два: одна часть отдается процессу, а другая остается неиспользуемой. Так происходит всегда, кроме статистически нереального случая точного соответствия свободного участка и пожеланий процесса. Это быстрый алгоритм, поскольку поиск минимизирован настолько, насколько возможно.

Алгоритм следующего подходящего участка действует с минимальными отличиями от правила первый подходящий . Он работает так же, как и первый алгоритм, но всякий раз, когда находится соответствующий свободный фрагмент, запоминается его адрес. И когда алгоритм в следующий раз вызывается для поиска, он стартует с того самого места, где остановился в прошлый раз, вместо того чтобы снова и снова начинать поиск от головы списка, как это делает алгоритм первый подходящий . Моделирование работы алгоритма по Бэйсу показало, что производительность схемы следующий подходящий несколько хуже, чем первый подходящий [5].

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

За примерами работы алгоритмов первый подходящий и самый подходящий снова обратимся к рис. 4.5. Если необходим блок размером 2, правило первый подходящий предоставит область по адресу 5, а схема самый подходящий разместит процесс в свободном фрагменте по адресу 18.

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

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

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

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

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