Операционные системы 2011 (1114689), страница 63
Текст из файла (страница 63)
И, так илииначе, это накладные расходы, связанные с компрессией. В одних системах онинесущественны, в других — напротив, имеют большое значение.5.4Страничное распределениеОб этой модели распределения оперативной памяти уже шла речь ранее, но тогдаперед нами стояла задача лишь ввести читателя в курс дела, - в этом же разделе будутобсуждаться более подробно современные подходы страничной организации памяти.Данная модель основывается на том, что все адресное пространство может бытьпредставлено совокупностью блоков фиксированного размера (Рис.
134), которыеназываются страницами. Есть виртуальное адресное пространство — это топространство, с адресами которого оперирует программа, и физическое адресноепространство — это то пространство, которое есть в наличии в компьютере.Соответственно, при страничном распределении памяти существуют программноаппаратные средства, позволяющие устанавливать соответствие между виртуальными ифизическими страницами. Механизм преобразования виртуального адреса в физическийобсуждался ранее, он достаточно прост: берется номер виртуальной страницы и233заменяется соответствующим номером физической страницы. Также отмечалось, что дляэтих целей используется т.н. таблица страниц, которая целиком является аппаратной,что на самом деле является большим упрощением. Если рассмотреть современныемашины с современным объемом виртуального адресного пространства, то окажется, чтоэта таблица будет очень большой по размеру. Соответственно, возникает важный вопрос,как осуществлять указанное отображение виртуальных адресов в физические.Виртуальноеадресное пр-во0123виртуальнаястраницаПространствофизической памяти0123×…K–3K–2K–1…L–1××Рис.
134. Страничное распределение.Ответ на поставленный вопрос, как всегда, неоднозначный и имеет нескольковариантов. Первое решение, приходящее на ум, — это полное размещение таблицыпреобразования адресов в аппаратной части компьютера, но это решение применимо лишьв тех системах, где количество страниц незначительное. Примером такой системы можетслужить машина БЭСМ-6, которая имела 32 виртуальные страницы, и вся таблица с 32строками располагалась в процессоре. Если же таблица получается большой, товозникают следующие проблемы: во-первых, высокая стоимость аппаратной поддержки, аво-вторых, необходимость полной перезагрузки таблицы при смене контекстов.
Но приэтом скорость преобразования оказывается довольно высокой.Альтернативой служит решение, предполагающее хранение данной таблицы воперативной памяти, тогда каждое преобразование происходит через обращение к ОЗУ,что совсем неэффективно. К аппаратуре предъявляются следующие требования: долженбыть регистр, ссылающийся на начало таблицы в ОЗУ, а также должно аппаратноподдерживаться обращение в оперативную память по адресу, хранящемуся в указанномрегистре, извлечение данных из таблицы и осуществление преобразования.Возможно оптимизировать рассмотренный подход за счет использованиякэширования L1 или L2. С одной стороны, поскольку к таблице страниц происходитпостоянное обращение, странички из данной таблицы «зависают» в КЭШе.
Но, если вкомпьютере используется всего один КЭШ и для потока управления, и для потока данных,то в этом случае через него направляется еще и поток преобразования страниц. Посколькуэти потоки имеют свои особенности, то добавление дополнительного потока со своимииндивидуальными характеристиками приведет к снижению эффективности системы.Стоит также отметить, что в современных системах таблицы страниц каждогопроцесса могут оказаться достаточно большими, мультипрограммные ОСподдерживают обработку сотен или даже тысяч процессов, поэтому держать всю таблицустраниц в оперативной памяти также оказывается дорогим занятием. С другой стороны,если в ОЗУ хранить лишь оперативную часть этой таблицы, то возникают проблемы,связанные со сменой процессов: необходимо будет часть таблицы откачивать вовнешнюю память, а часть — наоборот, подкачивать, что является достаточно трудоемкой234задачей.
Соответственно, возникает проблема организации эффективной работы стаблицей страниц, чтобы возникающие накладные расходы не приводили к деградациисистемы.Помимо указанных подходов к размещению таблицы страниц, каждый из которыхимеет свои преимущества и недостатки, в реальности применяют смешанные, илигибридные, решения.Что касается используемых алгоритмов и способов организации данных длямодели страничного распределения памяти, то традиционно применяются решения,связанные с иерархической организацией этих таблиц.Типовая структура записи таблицы страниц (Рис.
135) содержит информацию ономере физической страницы, а также совокупность атрибутов, необходимых дляописания статуса данной страницы. Среди атрибутов может быть атрибутприсутствия/отсутствия страницы, атрибут режима защиты страницы (чтение, запись,выполнение), флаг модификации содержимого страницы, атрибут, характеризующийобращения к данной странице, чтобы иметь возможность определения «старения»страницы, атрибут блокировки кэширования и т.д. Итак, в каждой записи можетприсутствовать целая совокупность атрибутов, которые аппаратно интерпретируемы:например, при попытке записать данные в страницу, закрытую на запись, произойдетпрерывание.εδγβαНомер физической страницыРис.
135. Модельная структура записи таблицы страниц. Здесь: α — присутствие/отсутствие; β — защита (чтение, чтение/запись, выполнение); γ —изменения; δ — обращение (чтение, запись, выполнение); ε — блокировкакэширования.В качестве одного из первых решений оптимизации работы с памятью сталоиспользование т.н. TLB-таблиц (Translation Look-aside Buffer — таблица быстрогопреобразования адресов, Рис. 136). Данный метод подразумевает наличие аппаратнойтаблицы относительно небольшого размера (порядка 8 – 128 записей). Данная таблицыконцептуально содержит три столбца: первый столбец — это номер виртуальнойстраницы, второй — это номер физической страницы, в которой находится указаннаявиртуальная страница, а третий столбец содержит упомянутые выше атрибуты.Виртуальный адрес состоит из номера виртуальной страницы (VP) и смещения вней (offset). Страница изымает из этого адреса номер виртуальной страницы иосуществляет оптимизированный поиск (т.е.
поиск не последовательный, а параллельный)этого номера по TLB-таблице. Если искомый номер найден, то система автоматически науровне аппаратуры осуществляет проверку соответствия атрибутов, и если проверкауспешна, то происходит подмена номера виртуальной страницы номером физическойстраницы, и, таким образом, получается физический адрес.Если же при поиске происходит промах (номер виртуальной странице не найден),то в этом случае система обращается в программную таблицу, выкидывает самую старуюзапись из TLB, загружает в нее найденную запись из программной таблицы, и затемвычисляется физический адрес.
Таким образом, получается, что TLB-таблица являетсянекоторым КЭШем.Модели отработки промаха могут быть различными. Возможна организацияотработки промаха без прерываний, когда система самостоятельно, имея регистр началапрограммной таблицы страниц, обращается к этой таблице и осуществляет в ней поиск.Возможна модель с прерыванием, когда при промахе возникает прерывание, управлениепередается операционной системе, которая затем начинает работать с программнойтаблицей страниц, и т.д. Заметим, что вторая модель менее эффективная, посколькупрерывания ведут к увеличению накладных расходов.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«Внешняя»таблица групп(кластеров)страницТаблицыстраниц второгоуровняРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
