2011. Машбук (1114722), страница 63
Текст из файла (страница 63)
Возможна организацияотработки промаха без прерываний, когда система самостоятельно, имея регистр началапрограммной таблицы страниц, обращается к этой таблице и осуществляет в ней поиск.Возможна модель с прерыванием, когда при промахе возникает прерывание, управлениепередается операционной системе, которая затем начинает работать с программнойтаблицей страниц, и т.д. Заметим, что вторая модель менее эффективная, посколькупрерывания ведут к увеличению накладных расходов.235Вирт.
адресVPФизическаяпамять:offsetTLBвирт. стр.физ. стр.hitФиз. адресFP…offsetmiss…Таблицастраниц:Рис. 136. TLB-таблица (Translation Look-aside Buffer).Итак, рассмотренная модель использования TLB-таблиц является реальной, посравнению с той моделью, которая была описана в начале курса. Одной из главныхпроблем этого подхода является проблема, связанная с большим размером таблицыстраниц. Отметим, что большой размер этой таблицы плох по двум причинам: во-первых,при смене контекста система так или иначе обязана поменять эту таблицу, а такжесодержимое TLB, т.к.
там хранится информацию об одном процессе, а во-вторых, этопроблема, связанная с организацией мультипроцессирования, — необходимо решать, гдеразмещать все таблицы различных процессов.Одним из решений, позволяющих снизить размер таблицы страниц, являетсямодель иерархической организации таблицы страниц (Рис. 137). В этом случаеинформация о странице представляется не в виде одного номера страницы, а в видесовокупности номеров, используя которые, можно получить номер соответствующейфизической страницы, посредством обращения к соответствующим таблицам,участвующим в иерархии (это может быть 2-х-, 3-х- или даже 4-хуровневая иерархия).Пусть имеется 32-разрядный виртуальный адрес, который в свете рассмотреннойранее модели может, например, содержать 20-разрядный номер виртуальной страницы и12-разрядное значение смещения в ней.
Если же используется двухуровневаяиерархическая организация, то этот же виртуальный адрес можно трактовать, к примеру,как 10-разрядный индекс во «внешней» таблице групп (или кластеров) страниц, 10разрядное смещение в таблице второго уровня и, наконец, 12-разрядное смещение вфизической странице. Соответственно, чтобы получить номер физической страницынеобходимо по индексу во «внешней» таблице групп страниц найти необходимую ячейку,содержащую начальный адрес таблицы второго уровня, затем по этому адресу и позначению смещения в виртуальном адресе находится нужная запись в таблице страницвторого уровня, которая уже и содержит номер соответствующей физической страницы.236VPoffset2012VP1VP2offset101012Индекс поСмещение по«внешней» таблицестранице,групп (кластеров) указанной черезстраницVP1VP1VP2«Внешняя»таблица групп(кластеров)страницТаблицыстраниц второгоуровняРис.
137. Иерархическая организация таблицы страниц.ФизическаяпамятьИспользуя данный подход, может оказаться, что всю таблицу страниц хранить впамяти вовсе необязательно: из-за принципа локализации будет достаточно хранитьсравнительно небольшую «внешнюю» таблицу групп страниц и некоторые таблицывторого уровня (они также имеют незначительные размеры); все необходимые таблицывторого уровня можно подкачивать по мере надобности.Подобные рассуждения можно распространить на большее число уровнейиерархии, но, начиная с некоторого момента, эффективность системы начинает сильнопадать с ростом числа уровней иерархии (из-за различных накладных расходов), поэтомуобычно число уровней ограничено четырьмя.Существует иное решение, позволяющее также обойти проблему большого размератаблицы страниц, - оно основано на использовании хеширования (на использовании т.н.хеш-таблиц).
Это решение в свою очередь, базируется на использовании хеш-функции,или функции расстановки (Рис. 138). Эти функции используются в следующей задаче:пусть имеется некоторое множество значений, которое необходимо каким-то образомотобразить на множество фиксированного размера.
Для осуществления этого отображенияиспользуют функцию, которая по входному значению определяет номер позиции (номеркластера, куда должно попасть это значение). Но эта функция имеет свои особенности:при ее использовании возможны коллизии, связанные с тем, что различные значениямогут оказаться в одном и том же кластере.VPoffsetVP1FP1VP2FP2F(VP)FPoffset…Хеш-функцияVPFP…ФизическаяпамятьХеш-таблицаРис.
138. Использование хеш-таблиц.237Модель преобразования адресов, основанная на хешировании, достаточно проста.Из виртуального адреса аппаратно извлекается номер виртуальной страницы, которыйподается на вход некоторой хеш-функции, отображающей значение на аппаратнуютаблицу (т.н. хеш-таблицу) фиксированного размера. Каждая запись в данной таблицехранит начало списка коллизий, где каждый элемент списка является парой: номервиртуальной страницы — соответствующий ему номер физической страницы. Итак,перебирая соответствующий список коллизий, можно найти номер исходной виртуальнойстраницы и соответствующий номер физической страницы. Подобное решение имеет своидостоинства и недостатки: в частности, возникают проблемы с перемещением списковколлизий.Еще одним решением, позволяющим снизить размер таблицы страниц, являетсямодель использования т.н.
инвертированных таблиц страниц (Рис. 139). Главнойсложностью данного решения является требование к процессору на аппаратном уровнеработать с идентификаторами процессов (их PID). Примерами таких процессоров могутслужить процессоры серий SPARC и PowerPC.PIDVPFPoffsetoffsetFPPIDVPпоискТаблица страницРис. 139. Инвертированные таблицы страниц.В этой модели виртуальный адрес трактуется как тройка значений: PID процесса,номер виртуальной страницы и смещение в этой странице. При таком подходеиспользуется единственная таблица страниц для всей системы, и каждая строка даннойтаблицы соответствует физической странице (с номером, равным номеру этой строки).При этом каждая запись данной таблицы содержит информацию о том, какому процессупринадлежит данная физическая страница, а также какая виртуальная страница этогопроцесса размещена в данной физической странице. Итак, имея пару PID процесса иномер виртуальной страницы, производится поиск ее в таблице страниц, и по смещениюнайденного результата определяется номер физической страницы.К достоинствам данной модели можно отнести наличие единственной таблицыстраниц, обновление которой при смене контекстов сравнительно нетрудоемкое:операционная система производит обновление тех строк таблицы, для которых всоответствующие физические страницы происходит загрузка процесса.
Отметим, что«тонким местом» данной модели является организация поиска в таблице. Если будетиспользоваться прямой поиск, то это приведет к существенным накладным расходам. Дляоптимизации этого момента возможна надстройка над этим решением болееинтеллектуальных моделей — например, модели хеширования и/или использования TLBтаблиц.Революционным достоинством страничной организации памяти стало то, чтоисполняемый в системе процесс может использовать очень незначительную частьфизического ресурса памяти, а все остальные его страницы могут размещаться вовнешней памяти (быть откачанными). Очевидно, что и страничная организация памяти238имеет свои недостатки: в частности, это проблема фрагментации внутри страницы.
Всвязи с использованием страничной организации памяти встает еще одна проблема — этопроблема выбора той страницы, которая должна быть откачана во внешнюю память принеобходимости загрузить какую-то страницу из внешней памяти. Эта задача имеетмножество решений, некоторые из которых будут освещены ниже.Первым рассмотрим алгоритм NRU (Not Recently Used — не использовавшийся впоследнее время). Этот алгоритм основан на том, что с любой страницей ассоциируютсядва признака, один из которых отвечает за обращение на чтение или запись к странице (Rпризнак), а второй — за модификацию страницы (M-признак), когда в страницу что-тозаписывается. Значение этих признаков устанавливается аппаратно. Имеется такжевозможность посредством обращения к операционной системе обнулять эти признаки.Итак, алгоритм NRU действует по следующему принципу. Изначально для всехстраниц процесса признаки R и M обнуляются.
По таймеру или по возникновениюнекоторых событий в системе происходит программное обнуление всех R-признаков.Когда системе требуется выбрать какую-то страницу для откачки из оперативной памяти,это осуществляется следующим образом. Все страницы, принадлежащие данномупроцессу, делятся на 4 категории в зависимости от значений признаков R и M.Класс 0: R = 0, M = 0. Это те страницы, в которых не происходило обращение впоследнее время и в которых не сделано ни одно изменение.Класс 1: R = 0, M = 1. Это те страницы, к которым в последний период не былообращений (поскольку программно обнулен R-признак), но в этой странице в своевремя произошло изменение.Класс 2: R = 1, M = 0.
Это те страницы, из которых за последний таймаут читаласьинформация.Класс 3: R = 1, M = 1. Это те страницы, к которым за последнее время былиобращения, в т.ч. обращения на запись, т.е. это активно используемые страницы.Соответственно, алгоритм предлагает выбирать страницу для откачиванияслучайным способом из непустого класса с минимальным номером.Следующий алгоритм, который мы рассмотрим, — это алгоритм FIFO.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
