Глава 4 (1085728), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

Кучей (heap) называется область памяти, выделяемая программе для динамически размещаемых структур данных.

Р
ис. 4.6. Предоставление пространства для роста области данных (а);

предоставление пространства для роста стека и области данных (б)

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

Если память выделяется динамически, этим процессом должна управлять опера­ционная система. Существует два способа учета использования памяти: бито­вые массивы, иногда называемые битовыми картами, и списки свободных участ­ков. В этом и следующем разделах мы по очереди рассмотрим оба метода.

При работе с битовым массивом память разделяется на единичные блоки раз­мещения размером от нескольких слов до нескольких килобайт. В битовой карте каждому свободному блоку соответствует один бит, равный нулю, а каждому за­нятому блоку — бит, установленный в 1 (или наоборот). На рис. 4.7 показана часть памяти и соответствующий ей битовый массив. Черточками отмечены единичные блоки памяти. Заштрихованные области (0 в битовой карте) свободны.

Размер единичного блока представляет собой важный вопрос стадии разработ­ки системы. Чем меньше единичный блок, тем больше потребуется битовый мас­сив. Однако даже при маленьком единичном блоке, равном четырем байтам, для 32 битов памяти потребуется 1 бит в карте. Тогда память размером в 32n будет ис­пользовать n битов в карте, таким образом, битовая карта займет всего лишь 1/33 часть памяти. Если выбираются большие единичные блоки, битовая карта стано­вится меньше, но при этом может теряться существенная часть памяти в послед­нем блоке каждого процесса (если размер процесса не кратен размеру единичного блока).

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

Р
ис. 4.7. Часть памяти с пятью процессами и тремя свободными областями (а);соответствующая битовая карта (б); та же информация в виде списка (в)

Управление памятью с помощью связных списков

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

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

Соседями могут быть процессы или свободные фрагмен­ты, что приводит к четырем комбинациям, показанным на рис. 4.8. процессов для завершившегося процесса обычно будет непосредственно указывать на запись в списке для этого процесса, возможно, удобнее иметь список с двумя связями, чем с одной (последний показан на рис. 4.7, в). Такая структура упрощает поиск предыдущей записи и оценку возможности соединения.

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

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

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

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

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

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

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

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

не имеет смысла.

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

Еще один алгоритм распределения называется «быстрый подходящий», он поддерживает отдельные списки для некоторых из наиболее часто запрашиваемых размеров. Например, могла бы существовать таблица с n записями, в которой пер­вая запись указывает на начало списка свободных фрагментов размером 4 Кбайт, вторая запись является указателем на список незанятых областей размером 8 Кбайт, третья - 12 Кбайт и т. д. Свободный фрагмент размером, скажем, 21 байт, мог бы располагаться или в списке областей 20 Кбайт или в специальном списке участков дополнительных размеров. При использовании правила «быстрый под­ходящий» поиск фрагмента требуемого размера происходит чрезвычайно быстро. Но этот алгоритм имеет тот же самый недостаток, что и все схемы, которые сорти­руют свободные области по размеру, а именно: если процесс завершается или вы­гружается на диск, поиск его соседей с целью узнать, возможно ли их соединение, является дорогой операцией. А если не производить слияния областей, память очень скоро окажется разбитой на огромное число маленьких свободных фрагмен­тов, в которые не поместится ни один процесс.

Виртуальная память

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

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

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

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

Страничная организация памяти

Большинство систем виртуальной памяти используют технику, называемую стра­ничной организацией памяти (paging), которую мы сейчас опишем. На любом ком­пьютере существует множество адресов в памяти, к которым может обратиться программа. Когда программа использует следующую инструкцию

Характеристики

Список файлов книги