Лекция 23. Защита памяти

23.2. Метод граничных регистров

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

Рис.23.1. Защита памяти с помощью граничных регистров

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

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

23.3. Метод ключей защиты

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

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

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

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

- Проверка атрибутов доступа (ключей защиты) перед предоставлением возможности обращения к памяти.

- Кольцевая структура иерархических уровней привилегированности (приоритетов), организованная так, чтобы предотвратить искажение наиболее важных программ, находящихся в центре, ошибками, имеющими место на внешних уровнях, где вероятность их возникновения наиболее высока. Об этом говорит сайт https://intellect.icu . Механизм на базе уровней привилегий обеспечивает достаточно надежную защиту. При этом уровень привилегии задачи равен уровню привилегии активного на текущий момент программного сегмента или активной страницы.

Дескриптор сегмента или страницы включает в себя битовое поле, определяющее один из четырех допустимых уровней привилегий для соответствующего сегмента (рис. 16.3). Нулевой уровень является наиболее привилегированным, т.е. с наиболее ограниченным доступом к сегменту или странице. Уровень привилегии 3 является самым низким и характеризует наиболее доступные сегмент или страницу. Программы могут иметь доступ к данным или программным сегментам только с таким же уровнем привилегий или с менее ограниченным доступом (т.е. с более высокими номерами уровня привилегий).

С помощью этих четырех уровней защиты и системы проверки атрибутов доступа в процессоре организуется многозадачный режим за счет обособления программ друг от друга и от операционной системы. Механизм защиты предотвращает аварийную ситуацию в какой-либо программе при возникновении сбоя в системе. Систему защиты памяти посредством задачно-пользовательских атрибутов и уровней приоритетов, используемую в процессоре I80386, можно изобразить схемой, приведенной на рис. 16.16.

Рис.23.2. Система защиты памяти ЭВМ на процессоре I80386

Функционирование изображенной структуры можно проиллюстрировать следующим примером. Пусть данные хранятся на уровне P=2. Тогда доступ к ним возможен для программ, находящихся на уровнях P=2, 1 или 0. Для программ с P=3 они недоступны. Аналогично программа прикладного сервиса с P=2 может быть вызвана сегментами или процедурами, находящимися на уровнях P=2, 1 или 0, но не на уровне P=3.

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

Таким образом, менее привилегированная процедура может вызвать более привилегированную, обращаясь к ней через дескриптор шлюза вызова, определяющий доступную точку входа. Этот способ обращения использовался также в процессорах I80286 и I80486. Он позволяет программам пользователя обращаться за обслуживанием к ОС. При этом допускаются обращения только к определенным процедурам, которые санкционируются путем введения в систему соответствующего шлюза. Тем самым исключается возможность несанкционированного обращения менее привилегированных процедур к более привилегированным, что позволяет защитить их от возможных искажений.

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

23.4. Алгоритмы управления многоуровневой памятью

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

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

Приведем формализованную модель процесса обмена информацией между верхним и нижним уровнями памяти. Пусть программа вместе с исходными данными состоит из k страниц, которым присвоены номера 1, 2, ..., k, тогда программу можно рассматривать как множество страниц:

Q = {1,2, …, k}.

Все страницы программы постоянно хранятся в памяти нижнего уровня, а, кроме того, r из них могут находиться в памяти верхнего уровня (оперативной памяти), при этом

1 < r < k.

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

q₀, q₁, q₂, …, q_t,

где q_t – случайная дискретная величина, принимающая в момент времени t значение одного из номеров страниц программы (q_t Î Q).

Если S_t – совокупность страниц в памяти верхнего уровня в момент t, причем в любой момент в этой памяти присутствует r страниц программы, то изменение состояния памяти верхнего уровня после обращения q_t описывается следующими соотношениями:

 .

В первом случае обращение производится к странице, которая находится в памяти верхнего уровня, и поэтому состояние этой памяти не меняется.

Во втором случае происходит обращение к странице, отсутствующей в памяти верхнего уровня. Эта ситуация называется страничным сбоем, так как программа не может дальше выполняться, пока нужная страница q_t не будет переписана из памяти нижнего уровня в память верхнего уровня, что сопряжено с потерями времени. Поскольку в памяти верхнего уровня нет свободного места, из нее приходится удалять некоторую страницу v_t с тем, чтобы на ее место можно было поместить страницу q_t. Если во время пребывания страницы v_t в памяти верхнего уровня в нее производилась запись, эта страница при замещении должна переписываться в память нижнего уровня. Такая процедура называется процессом замещения страниц, а правило, по которому при возникновении страничного сбоя выбирается страница v_t Î S_t для удаления из памяти верхнего уровня, – алгоритмом замещения.

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

Оптимизация процесса замещений страниц упрощается, если известно, в каком порядке в будущем будут происходить обращения к памяти или, по крайней мере, вероятности обращений в будущем к отдельным страницам программы. Ясно, например, что в первую очередь из памяти верхнего уровня следует удалить страницу, к которой обращений больше не будет (вероятность обращений в будущем равна 0).

Трудность состоит в том, что, как правило, при выполнении программы отсутствуют информация о потоке обращений или сколько-нибудь достоверные сведения о вероятности обращений к отдельным страницам в будущие моменты времени.

Алгоритмы замещения можно разделить на две группы:

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

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

Физически нереализуемые алгоритмы

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

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

Таким образом, алгоритм Михновского-Шора реализует минимально возможную для данной программы последовательность замещений, поэтому этот алгоритм называют МИН-алгоритмом.

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

Физически реализуемые (эвристические) алгоритмы замещения

Был предложен ряд алгоритмов этого класса.

Алгоритм случайного замещения (СЗ-алгоритм). При возникновении странич­ного сбоя из памяти верхнего уровня с равной вероятностью отсылается любая из находящихся там страниц.

НДИ-алгоритм. Из памяти верхнего уровня отсылается страница, наиболее давно использовавшаяся.

Алгоритм "первый пришел – первый ушел" (ПППУ-алгоритм). Отсылается страница, дольше других находившаяся в памяти верхнего уровня.

Алгоритм "последний пришел – первый ушел". Отсылается страница, позже других поступившая в память верхнего уровня.

Следующие два алгоритма обладают определенными свойствами адаптации к потоку обращений к памяти.

Алгоритм "карабкающаяся страница" (КС-алгоритм). Страницы в памяти верхнего уровня образуют последовательность:

.

При очередном обращении q_tк памяти эта последовательность изменяется по правилу:

При обращении к странице j_m, присутствующей в памяти верхнего уровня, последняя меняется местами с соседней слева страницей, другими словами, "карабкается" к началу последовательности, подальше от ее конца, куда происходит замещение при страничном сбое. Этот процесс иллюстрирует схема на рис. 23.3.

Рис.23.3. Алгоритм замещения ”карабкающаяся страница”

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

- очередь страниц, в которые не вносились изменения, пока они присутствовали в памяти верхнего уровня;

- очередь страниц, в которые вносились изменения.

Замещение при страничном сбое производится по правилу: первый пришел из рабочего комплекта – первый ушел из памяти верхнего уровня. При этом сначала подлежат замещению страницы из первой очереди. Описанный алгоритм использовался еще в компьютерах IBM-360/370.

Предположим, что последовательность обращений q₁, q₂, …, q_tсоответствует последовательности независимых случайных дискретных величин, таких что

, , .

Примем за состояние процесса замещения набор (а в некоторых случаях упорядоченную последовательность) страниц, находящихся в памяти верхнего уровня. Тогда для ряда алгоритмов замещения (СЗ, НДИ, ПППУ и некоторых других) процесс изменения состояния верхнего уровня описывается однородной конечной эргодической цепью Маркова, что указывает на существование стационарных вероятностей пребывания процесса в определенных состояниях и, как следствие этого, стационарных вероятностей страничных сбоев.

В качестве критерия эффективности W_r,k алгоритма замещения А примем стационарную вероятность страничных сбоев:

.

Можно для ряда алгоритмов замещения найти зависимость W_r,k от p₁, p₂, …, p_k и сравнить алгоритмы между собой, а также с физически нереализуемым ОПТ-алго­ритмом. Определить W_r,k для ряда алгоритмов можно, используя метод, основанный на однородных эргодических цепях Маркова.

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

23.5. Контрольные вопросы

1. Варианты дифференцированной защиты при различных операциях с памятью.

2. Защита отдельных ячеек памяти.

3. Метод граничных регистров.

4. Метод ключей защиты.

5. Система защиты памяти ЭВМ на процессоре I80386.

6. Алгоритмы управления многоуровневой памятью.

7. Физически реализуемые (эвристические) алгоритмы замещения.