Ответы 190 страниц, страница 8

Смещение d

Виртуальный адрес V=(p,d)

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

Виртуальный адрес в страничной системе — это упорядоченная пара (p, d), где p — номер страницы в виртуальной памяти, a d — смещение в рамках страницы p, где размещается адресуемый элемент (рис. 8.8). Процесс может выполняться, если его текущая страница находится в первичной памяти. Страницы переписываются из внешней памяти в первичную и размещаются в ней в блоках, называемых страничными кадрами и имеющих точно такой же размер, как поступающие страницы. Страничные кадры начинаются с адресов первичной памяти, кратных фиксированному размеру страницы (рис. 8.9). Поступающая страница может быть помещена в любой свободный страничный кадр.

Динамическое преобразование адресов в системе со страничной организацией осуществляется следующим образом. Выполняющийся процесс обращается по адресу виртуальной памяти V=(p, d). Механизм отображения страниц, показанный на рис. 8.10, ищет номер страницы p в таблице отображения страниц и определяет, что эта страница находится в страничном кадре p'. Адрес реальной памяти формируется затем путем конкатенации p' и d.

Рассмотрим теперь этот процесс более подробно. В частности, поскольку обычно не все страницы процесса находятся в первичной памяти одновременно, таблица отображения страниц должна указывать, есть ли адресуемая страница в первичной памяти, и если есть, то где именно, а если нет, то в каком месте внешней памяти ее можно найти. На рис. 8.11 показана типичная строка таблицы отображения страниц. Бит-признак присутствия страницы r устанавливается в 0, если данной страницы в первичной памяти нет, и в 1, если эта страница есть в первичной памяти. Если страницы нет, to s — ее адрес во внешней памяти. Если страница есть в первичной памяти, то p' — номер ее страничного кадра. Отметим, что p' — это не действительный адрес первичной памяти. Адрес первичной памяти а, с которого начинается страничный кадр p' (если размер страницы равняется p), определяется произведением

а=(p)(p') (если страничные кадры имеют номера 0, 1, 2 и т. д.).

В целях экономии емкости первичной памяти в таблицу отображения страниц можно не включать адреса страниц во внешней памяти.

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

Выполняющийся процесс делает ссылку по виртуальному адресу V=(p, d). Прежде чем процесс начнет выполняться, операционная система загружает адрес первичной памяти для таблицы отображения страниц в регистр начального адреса этой таблицы. Этот базовый адрес b таблицы прибавляется к номеру страницы p, образуя адрес первичной памяти b+p для строки страницы p в таблице. В этой строке указано, что виртуальной странице p соответствует страничный кадр p'. Затем к значению p' приформировывается (путем конкатенации) смещение d, так что образуется реальный адрес r. Такой подход называется способом прямого отображения потому, что таблица отображения страниц содержит отдельную строку для каждой страницы виртуальной памяти данного процесса. Если процесс имеет в виртуальной памяти n страниц, то таблица при прямом отображении для этого процесса содержит последовательные строки для страницы 0, страницы 1, страницы 2, ..., страницы n—1.

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

8.7 Сегментная организация

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

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

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

Рис. 8.17 Защита памяти при помощи ключей в мультипрограммных системах с распределением памяти несмежными блоками. Когда в ЦП для ключа защиты памяти устанавливается значение 2, соответствующее пользователю В, программа этого пользователя может обращаться только к тем блокам памяти, которые имеют именно этот ключ защиты (2). Управление ключами защиты осуществляет только операционная система.

Виртуальный адрес в сегментной системе — это упорядоченная пара V=(s, d), где s — номер сегмента виртуальной памяти, a d — смещение в рамках этого сегмента, где находится адресуемый элемент (рис. 8.18). Процесс может выполняться только в случае, если его текущий сегмент (как минимум) размещается в первичной памяти. Сегменты передаются из внешней памяти в первичную целиком. Все ячейки, относящиеся к сегменту, занимают смежные адреса первичной памяти. Поступающий из внешней памяти сегмент может

Номер сегмента s

Смещение d

Виртуальный адрес V=(s,d)

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

Динамическое преобразование адресов осуществляется следующим образом (рис. 8.19). Выполняющийся процесс выдает адрес виртуальной памяти V=(s, d). Механизм отображения сегментов ищет сегмент s в таблице сегментов и определяет, что этот сегмент находится в реальной памяти, начиная с ячейки s'. Адрес реальной памяти, соответствующий виртуальному адресу V=(s, d), формируется затем путем добавления s' к d. Более подробно эту процедуру мы рассмотрим в нескольких следующих разделах.

8.7.1 Управление доступом в системах с сегментной организацией

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

8.8 Системы с комбинированной странично-сегментной организацией

И сегментная, и страничная организации имеют важные достоинства как способы построения виртуальной памяти. Начиная с систем середины 60-х годов, в частности с информационно-вычислительной системы с разделением времени Multics и системы разделения времени TSS корпорации IBM, во многих вычислительных машинах применяется комбинированная странично-сегментная организация памяти (Da68, De71, Do76). Эти системы обладают достоинствами обоих способов реализации виртуальной памяти. Сегменты обычно содержат целое число страниц, причем не обязательно, чтобы все страницы сегмента находились в первичной памяти одновременно, а смежные страницы виртуальной памяти не обязательно должны оказываться смежными в реальной памяти. В системе со странично-сегментной организацией применяется трехкомпонентная (трехмерная) адресация, т. е. адрес виртуальной памяти V определяется как упорядоченная тройка V=(s, p, d), где s — номер сегмента, p — номер страницы, a d — смещение в рамках страницы, по которому находится нужный элемент (рис. 8.24).

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

Выполняющийся процесс делает ссылку по виртуальному адресу V=(s, p, d). Самые последние по времени обращения страницы имеют соответствующие строки в ассоциативной таблице. Система производит ассоциативный поиск, пытаясь найти строку с параметрами (s, p) в ассоциативной таблице. Если такая строка здесь обнаруживается, то адрес страничного кадра p', по которому эта страница размещается в первичной памяти, соединяется со смещением d, образуя реальный адрес r, соответствующий виртуальному адресу V, — и на этом преобразование адреса завершается.

В обычном случае большинство запросов на преобразование адресов удается удовлетворить подобным ассоциативным поиском. Если же требуемого адреса в ассоциативной памяти нет, то преобразование осуществляется способом полного прямого отображения. Это делается следующим образом: базовый адрес b таблицы сегментов прибавляется к номеру сегмента s, так что образуется адрес b+s строки для сегмента s в таблице сегментов по первичной памяти. В этой строке указывается базовый адрес s' таблицы страниц для сегмента s. Номер страницы p прибавляется к s', так что образуется адрес p+s' строки в таблице страниц для страницы p сегмента s. Эта таблица позволяет установить, что виртуальной странице p соответствует номер кадра p'. Этот номер кадра соединяется со смещением d, так что образуется реальный адрес r, соответствующий виртуальному адресу V=(s, p, d).

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

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

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

На рис. 8.26 показана подробная структура таблиц, необходимых для комбинированной странично-сегментной системы. На самом верхнем уровне этой структуры находится таблица процессов, которая содержит по строке для каждого процесса, известного системе. Строка таблицы процессов, соответствующая конкретному процессу, указывает на таблицу сегментов этого процесса. Каждая строка таблицы сегментов процесса указывает на таблицу страниц соответствующего сегмента, а каждая строка таблицы страниц указывает либо на страничный кадр, в котором размещается данная страница, либо на адрес внешней памяти, где можно найти эту страницу. В системе с большим количеством процессов, сегментов и страниц вся эта табличная структура может занимать значительную долю первичной памяти. Здесь следует учитывать, что преобразование адресов производится во время выполнения быстрее, если все таблицы находятся в первичной памяти. Однако чем больше таблиц в памяти, тем меньшее количество процессов система в состоянии поддерживать в текущий период, а это может приводить к снижению пропускной способности. Разработчики операционных систем должны анализировать многие подобные взаимозависимости и принимать тщательно сбалансированные компромиссные решения — только в этом случае можно обеспечить и эффективную загрузку системы, и оперативное предоставление ее услуг пользователям.

9.2 Стратегии управления виртуальной памятью