Курынин Р.В., Машечкин И.В., Терехин А.Н. - Конспект лекций по ОС (1114685), страница 53
Текст из файла (страница 53)
Среди атрибутов может быть атрибут присутствия/отсутствия страницы,атрибут режима защиты страницы (чтение, запись, выполнение), флаг модификации содержимогостраницы, атрибут, характеризующий обращения к данной странице, чтобы иметь возможностьопределения «старения» страницы, атрибут блокировки кэширования и т.д. Итак, в каждой записиможет присутствовать целая совокупность атрибутов, которые аппаратно интерпретируемы:например, при попытке записать данные в страницу, закрытую на запись, произойдет прерывание.εδγβαНомер физической страницыРис. 125.Модельная структура записи таблицы страниц.
Здесь: α — присутствие/отсутствие; β — защита (чтение, чтение/запись, выполнение); γ — изменения; δ — обращение (чтение,запись, выполнение); ε — блокировка кэширования.В качестве одного из первых решений оптимизации работы с памятью стало использованиет.н. TLB-таблиц (Translation Look-aside Buffer — таблица быстрого преобразования адресов, 5.4).Данный метод подразумевает наличие аппаратной таблицы относительно небольшого размера(порядка 8 – 128 записей).
Данная таблицы концептуально содержит три столбца: первыйстолбец — это номер виртуальной страницы, второй — это номер физической страницы, вкоторой находится указанная виртуальная страница, а третий столбец содержит упомянутые вышеатрибуты.Теперь, имея виртуальный адрес, состоящий из номера виртуальной страницы (VP) исмещения в ней (offset). Страница изымает из этого адреса номер виртуальной страницы иосуществляет оптимизированный поиск (т.е.
поиск не последовательный, а параллельный) этогономера по TLB-таблице. Если искомый номер найден, то система автоматически на уровнеаппаратуры осуществляет проверку соответствия атрибутов, и если проверка успешна, топроисходит подмена номера виртуальной страницы номером физической страницы, и, такимобразом, получается физический адрес.Если же при поиске происходит промах (номер виртуальной странице не найден), то в этомслучае система обращается в программную таблицу, выкидывает самую старую запись из TLB,загружает в нее найденную запись из программной таблицы, и затем вычисляется физическийадрес. Таким образом, получается, что TLB-таблица является некоторым КЭШем.Модели отработки промаха могут быть различными.
Возможна организация отработкипромаха без прерываний, когда система самостоятельно, имея регистр начала программнойтаблицы страниц, обращается к этой таблице и осуществляет в ней поиск. Возможна модель спрерыванием, когда при промахе возникает прерывание, управление передается операционнойсистеме, которая затем начинает работать с программной таблицей страниц, и т.д. Заметим, чтовторая модель менее эффективная, поскольку прерывания ведут к увеличению накладныхрасходов.204Вирт. адресVPФизическаяпамять:offsetTLBвирт.
стр.физ. стр.hitФиз. адресFPoffsetmiss……Таблицастраниц:Рис. 126.TLB-таблица (Translation Look-aside Buffer).Итак, рассмотренная модель использования TLB-таблиц является реальной по сравнению стой моделью, которая была описана в начале курса. Одной из главных проблем этого подходаявляется проблема, связанная с большим размером таблицы страниц. Отметим, что большойразмер этой таблицы плох по двум причинам: во-первых, при смене контекста система так илииначе обязана поменять эту таблицу, а также содержимое TLB, т.к. это все хранит информацию ободном процессе, а во-вторых, это проблема, связанная с организацией мультипроцессирования —необходимо решать, где размещать все таблицы различных процессов.Одним из решений, позволяющих снизить размер таблицы страниц, является модельиерархической организации таблицы страниц (5.4).
В этом случае информация о страницепредставляется не в виде одного номера страницы, а в виде совокупности номеров, используякоторые посредством обращения к соответствующим таблицам, участвующим в иерархии (этоможет быть 2-х-, 3-х- или даже 4-хуровневая иерархия), можно получить номер соответствующейфизической страницы.Пускай имеется 32-разрядный виртуальный адрес, который в свете рассмотренной ранеемодели может, например, содержать 20-разрядный номер виртуальной страницы и 12-разрядногозначения смещения в ней.
Если же используется двухуровневая иерархическая организация, тоэтот же виртуальный адрес можно трактовать, к примеру, как 10-разрядный индекс во «внешней»таблице групп, или кластеров, страниц, 10-разрядное смещение в таблице второго уровня и,наконец, 12-разрядное смещение в физической странице. Соответственно, чтобы получить номерфизической страницы необходимо по индексу во «внешней» таблице групп страниц найтинеобходимую ячейку, содержащую начальный адрес таблицы второго уровня, затем по этомуадресу и по значению смещения в виртуальном адресе находится нужная запись в таблице страницвторого уровня, которая уже и содержит номер соответствующей физической страницы.205VPoffset2012VP1VP2offset101012Смещение поИндекс постранице,«внешней» таблицегрупп (кластеров) указанной черезVP1страницРис.
127.VP1VP2«Внешняя»таблица групп(кластеров)страницТаблицыстраниц второгоуровняФизическаяпамятьИерархическая организация таблицы страниц.Используя данный подход, может оказаться, что всю таблицу страниц хранить в памятивовсе необязательно: из-за принципа локализации будет достаточно хранить сравнительнонебольшую «внешнюю» таблицу групп страниц и некоторые таблицы второго уровня (они такжеимеют незначительные размеры), все необходимые таблицы второго уровня можно подкачиватьпо мере надобности.Подобные рассуждения можно распространить на больше число уровней иерархии, но,начиная с некоторого момента, эффективность системы начинает сильно падать с ростом числауровней иерархии (из-за различных накладных расходов), поэтому обычно число уровнейограничено четырьмя.Существует иное решение, позволяющее также обойти проблему большого размератаблицы страниц, которое основано на использовании хеширования (использования т.н. хештаблиц), базирующееся, в свою очередь, на использовании хеш-функции, или функциирасстановки (5.4).
Эти функции используются в следующей задаче: пускай имеется некотороемножество значений, которое необходимо каким-то образом отобразить на множествофиксированного размера. Для осуществления этого отображения используют функцию, которая повходному значению определяет номер позиции (номер кластера, куда должно попасть этозначение).
Но эта функция имеет свои особенности: при ее использовании возможны коллизии,связанные с тем, что различные значения могут оказаться в одном и том же кластере.VPoffsetVP1FP1VP2FP2F(VP)FPoffset…Хеш-функцияVPFP…ФизическаяпамятьХеш-таблицаРис. 128.Использование хеш-таблиц.206Модель преобразования адресов, основанная на хешировании, достаточно проста. Извиртуального адреса аппаратно извлекается номер виртуальной страницы, который подается навход некоторой хеш-функции, отображающей значение на аппаратную таблицу (т.н.
хеш-таблицу)фиксированного размера. Каждая запись в данной таблице хранит начало списка коллизий, гдекаждый элемент списка является парой: номер виртуальной страницы — соответствующий емуномер физической страницы. Итак, перебирая соответствующий список коллизии, можно найтиномер исходной виртуальной страницы и соответствующий номер физической страницы.Подобное решение имеет свои достоинства и недостатки: в частности, возникают проблемы сперемещением списков коллизий.Еще одним решением, позволяющим снизить размер таблицы страниц, является модельиспользования т.н. инвертированных таблиц страниц (5.4).
Главной сложностью данногорешения является требование к процессору на аппаратном уровне работать с идентификаторамипроцессов (их PID). Примерами таких процессоров могут служить процессоры из линеек SPARC иPowerPC.PIDVPoffsetFPoffsetFPPIDVPпоискТаблица страницРис. 129.Инвертированные таблицы страниц.В этой модели виртуальный адрес трактуется как тройка значений: PID процесса, номервиртуальной страницы и смещение в этой странице.
При таком подходе используетсяединственная таблица страниц для всей системы, и каждая строка данной таблицы соответствуетфизической страницы (с номером, равным номеру этой строки). При этом каждая запись даннойтаблицы содержит информацию о том, какому процессу принадлежит данная физическаястраница, а также какая виртуальная страница этого процесса размещена в данной физическойстранице. Итак, имея пару PID процесса и номер виртуальной странице, производится поиск ее втаблице страниц, и по смещению найденного результата определяется номер физическойстраницы.К достоинствам данной модели можно отнести наличие единственной таблицы страниц,обновление которой при смене контекстам сравнительно нетрудоемкое: операционная системапроизводит обновление тех строк таблицы, для которых в соответствующие физические страницыпроисходит загрузка процесса. Отметим, что «тонким местом» данной модели являетсяорганизация поиска в таблице.
Если будет использоваться прямой поиск, то это приведет ксущественным накладным расходам. Для оптимизации этого момента возможно надстройка надэтим решением более интеллектуальных моделей — например, модели хеширования и/илииспользования TLB-таблиц.Революционным достоинством страничной организации памяти стало то, что исполняемыйв системе процесс может использовать очень незначительную часть физического ресурса памяти,а все остальные его страницы могут размещаться во внешней памяти (быть откачанными).Очевидно, что и страничная организация памяти имеет свои недостатки: в частности, этопроблема фрагментации внутри страницы. В связи с использованием страничной организациипамяти встает еще одна проблема — это проблема выбора той страницы, которая должна быть207откачана во внешнюю память при необходимости загрузить какую-то страницу из внешнейпамяти.
Эта задача имеет множество решений, некоторые из которых будут освещены ниже.Первым рассмотрим алгоритм NRU (Not Recently Used — не использовавшийся впоследнее время). Этот алгоритм основан на том, что с любой страницей ассоциируются двапризнака, один из которых отвечает за обращение на чтение или запись к странице (R-признак), авторой — за модификацию страницы (M-признак), когда в страницу что-то записывается.Значение этих признаков устанавливается аппаратно. Имеется также возможность посредствомобращения к операционной системе обнулять эти признаки.Итак, алгоритм NRU действует по следующему принципу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
