Схема виртуальной памяти на основе таблицы физических страниц.

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

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

Таблицы физических страниц делятся на разделы (до 1024 разделов по 1024 страницы в разделе).

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

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

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

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

Рис. 6.5. Схема виртуальной памяти на основе таблицы физических страниц

 

Одновременно в оперативной памяти должны находиться каталоги и таблицы физических разделов для всех задач. При переключении задач должны активизироваться каталоги и таблицы физических страниц новых задач. Для этого процессор содержит регистр базового адреса таблицы физических страниц БА ТФС. При каждом переключении задач в него записывается базовый адрес каталога новой задачи.

Работа схемы. Схема преобразования адресов содержит два регистра адресов: регистр математического адреса (РМА) и регистр физического адреса (РФА). Регистр математического адреса содержит три поля: номер раздела, номер страницы и номер байта. Регистр физического адреса содержит два поля: номер страницы и номер байта.

Для преобразования математического адреса в физический адрес номер раздела (М) из регистра РМА складывается с базовым адресом каталога из регистра БА ТФС (в МП IA-32 – это CR0) и производится обращение к оперативной памяти по сформированному адресу.

Обращение производится к строке М каталога, в которой записан адрес таблицы физических страниц раздела М и признак доступности. При нулевом значении признака доступности адрес таблицы физических страниц складывается с номером страницы математических страниц (N) и производится второе обращение к оперативной памяти по сформированному адресу.

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

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

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

и за операндом. Это недопустимо много.

Для увеличения быстродействия в механизм виртуальной памяти вводят буфер быстрой переадресации (TLB). Это набор регистров со схемами ассоциативного доступа.

Каждый регистр имеет три поля:

· номера математической страницы (20 бит),

· номера физической страницы (20 бит),

· дополнительной информации.

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

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

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

Буфер быстрой переадресации расположен непосредственно в процессоре, и потери времени на процедуру переадресации соизмеримы с тактом работы процессора.

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

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

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

Согласно рис. 6.5 в оперативной памяти для каждой задачи должны быть сформированы две таблицы: таблица каталога и таблица физических страниц одного раздела. Обмен страниц (подкачка данных и программ из внешней памяти в оперативную память и сохранение модифицированной информации) производится постранично.

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

Основными битами этого поля являются: d – бит присутствия страницы в оперативной памяти; r– бит (обращения) к странице, используется при выборе кандидата на удаление из оперативной памяти; m – бит модификации (записи) страницы, определяет необходимость сохранения содержимого страницы при удалении из оперативной памяти; w – признак прав доступа по записи, определяет разрешение операции модификации данных в странице.

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

В настоящее время наработано множество реализуемых алгоритмов листания. Наиболее известными из них являются алгоритмы:

· случайного замещения,

· удаления страницы, дольше других находившейся в ОП,

· удаления страницы, меньше других находившейся в ОП,

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

Наиболее известными являются варианты алгоритма "рабочий комплект".

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

Вопросы для самопроверки:

1. Использование регистра базового адреса таблицы физических таблиц.

2. Вход в каталог программы.

3. Содержание и использование каталога программы.

4. Вход в раздел таблицы физических страниц.

5. Содержание и использование раздела таблицы физических страниц.

6. Поля строк и назначение TLB.

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

8. Определение страничного промаха.

9. Действия при страничном промахе.

10. Основные биты строк TLB.

11. Алгоритм листания.