Подсистема управления памятью. Страничное распределение

Память является важнейшим ресурсом, требующим тщательного управления со стороны мультипрограммной операционной системы.

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

Функциями ОС по управлению памятью являются:

1. Отслеживание свободной и занятой памяти.

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

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

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

2. Выделение памяти процессам и ее освобождение

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

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

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

3. Вытеснение процессов из оперативной памяти на диск и возвращение их в оперативную память

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

4. Настройка адресов программы на конкретную область физической памяти

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

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

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

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

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

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

5. Защита программ друг от друга.

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

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

При страничном распределении памяти виртуальное адресное пространство каждого процесса делится на части одинакового размера, называемые страницами. Оперативная память делится на части такого же размера — страничные блоки. Размер частей выбирается кратным степени двойки (например, 4 кБайта).

Страничное распределение памяти имеет две важные особенности:

1. Соседним страницам программы не обязательно соответствуют соседние страничные блоки в ОЗУ, т.е. программа не хранится в памяти непрерывно.

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

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

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

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

Для того чтобы определить, в какие страничные блоки загружены страницы данного процесса, используются таблицы страниц (рисунок 4).

Рис 4.

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

Адрес таблицы страниц выполняющейся в данный момент программы хранится в специальном регистре процессора.

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

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

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

 

АЛГОРИТМЫ ЗАМЕЩЕНИЯ СТРАНИЦ

1. NRU — не использовавшаяся в последнее время страница

Таблица страниц содержит два статусных бита, связанных с каждой страницей. Бит R устанавливается в 1 при обращении к странице с целью чтения информации, а бит M устанавливается в 1, если содержимое страницы модифицируется. Когда страница загружается в память, оба бита установлены в 0. Время от времени (по таймеру) бит R сбрасывается в 0, чтобы отличить страницы, к которым обращения происходили недавно. На основе текущих значений R и M страницы делятся на четыре класса (0: R=0, M=0; 1: R=0, M=1; 2: R=1, M=0; 3: R=1, M=1) и для замещения выбирается произвольная страница из класса с наименьшим номером.

2. FIFO — первым прибыл, первым обслужен

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

3. Алгоритм «Вторая попытка»

Представляет собой алгоритм FIFO, но у удаляемой страницы изучается также бит R. Удаляется первая страница, у которой R = 1.

4. Алгоритм LRU — страница, не использовавшаяся дольше всего

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

5. Алгоритм «Рабочий набор»

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

После того, как страница для замещения выбрана, анализируется бит модификации M. Если выталкиваемая страница с момента загрузки была модифицирована, то ее новая версия должна быть переписана на диск. Если нет, то занимаемая ею память может быть просто освобождена.

Виртуальный адрес при страничном распределении может быть представлен в виде пары (p, s), где p — номер виртуальной страницы процесса (нумерация страниц начинается с 0), а s — смещение в пределах виртуальной страницы (см рисунок 5).

Рис. 5

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

При каждом обращении к ОП аппаратными средствами выполняются следующие действия:

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

2. Из этой записи извлекается номер физической страницы.

3. К номеру физической страницы присоединяется смещение (младшие разряды виртуального адреса).

Использование в пункте (3) того факта, что размер страницы равен степени 2, позволяет применить операцию конкатенации (присоединения) вместо более длительной операции сложения, что уменьшает время получения физического адреса, а значит повышает производительность компьютера.