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

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

дром. Приведенная на рис. 7.10 основная память содержит только один страничный кадр.

Особенности страничной организации и адресации памяти рассмотрим на конкретном примере. Будем полагать (рис. 7.10), что:

• • виртуальное адресное пространство имеет размер 64 К (IK = 210) и разделено на 16 страниц по 4К каждая;
• • физическое адресное пространство основной памяти имеет размер 32К и содержит 8 страничных кадров по 4К каждый.

Таким образом, необходимо 16-разрядный виртуальный адрес отобразить на 15-разрядный физический адрес основной памяти. В качестве средств для отображения виртуальных адресов на физические адреса следует использовать (рис. 7.11):

• таблицу страниц, каждая строка которой содержит:

¦ бит присутствия, отражающий присутствие/отсутствие (1/0) страницы в основной памяти;

¦ 3-разрядный код, соответствующий одному из восьми номеров (0, 1,…, 7) страничного кадра памяти;

• устройство управления памятью (MMU — Memory Management Unit), в которое входят:

¦ регистр для хранения таблицы страниц;

¦ входной регистр Rn, для хранения 16-разрядного виртуального адреса, который разделяется на две части. Четыре старших разряда адреса представляют собой код виртуальной страницы, который используется для нахождения требуемой страницы. Как показано на рисунке, из регистра RKX считывается код 1011, поэтому из таблицы выбирается виртуальная страница с номером 11. Младшие разряды являются 12-битным смещением внутри этой страницы, поскольку размер страницы равен 4К = 212;

Рис. 7.10. Иллюстрация страничной организации памяти.

Рис. 7.11. Страничная организация и адресация памяти.

• • выходной регистр для хранения 15-разрядного физического адреса. Входы 12 младших разрядов регистра соединены с 12 входами младших разрядов регистра . Три старших разряда физического адреса отводятся для кода страничного кадра, поступающего из регистра таблицы страниц. Как показано на рисунке, из регистра таблицы поступает код 010, соответствующий страничному кадру с номером 2. Так как 12-битное смещение равно 101 (5), формируется 15-разрядный адрес 10 000 000 000 101, который соответствует 8197-й ячейке памяти;
• • не показанные на рисунке демультиплексоры и мультиплексоры для передачи данных между регистрами и другие аппаратные средства.

На рис. 7.11 представлено возможное отображение виртуальных страниц в физические страничные кадры, при этом:

• • виртуальная страница 0 находится в страничном кадре 1 (бит присутствия равен 1);
• • виртуальная страница 1 отсутствует в памяти (бит присутствия равен 0);
• • виртуальная страница 2 отсутствует в памяти;
• • виртуальная страница 3 находится в страничном кадре 0;
• • виртуальная страница 4 отсутствует в основной памяти и т. д.

Принцип адресации проиллюстрирован на рис. 7.11. После поступления в регистр виртуального адреса (код 1011) выбирается страница (11) и проверяется наличие требуемого страничного кадра в памяти.

Если бит присутствия = 1, требуемый страничный кадр в данный момент находится в памяти. В этом случае из выбранной строки таблицы код страничного кадра (010) копируется в старшие три бита 15-битного выходного регистра , а из входного регистра  — младшие 12 битов (101) виртуального адреса (поле смещения страницы). Полученный 15-битный адрес (10 000 000 000 101) отправляется в кэш-память или основную память.

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

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

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

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

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

К таким страницам относится давно неиспользуемая страница, поскольку вероятность того, что она понадобится в текущем рабочем множестве, очень мала. На удалении редко используемых страниц базируется алгоритм LRU (Least Recently Used — наименее используемый в последнее время). Этот алгоритм достаточно хорошо зарекомендовал себя при работе с виртуальной памятью, однако имеются ситуации, в которых он не действует [11].

При другом способе замещения страниц удаляется страница, которая была загружена раньше всех, при этом не учитывается, когда в последний раз производилось к ней обращение. Этот способ соответствует известному алгоритму FIFO (First-In First-Out — первым вошел, первым вышел). При его реализации за каждым страничным кадром основной памяти закрепляется отдельный счетчик. Все счетчики устанавливаются в нулевое исходное состояние. При обращениях к памяти счетчики работают следующим образом:

• • в случае ошибки из-за отсутствия требуемой страницы счетчик каждой страницы, находящейся в памяти, увеличивается на 1;
• • в случае наличия требуемой страницы счетчик только что вызванной страницы принимает значение 0.

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

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