Волорова Н.А., Дурович А.С. Архитектура вычислительных систем

Подождите немного. Документ загружается.

уровней привилегий 0, 1 и 2. Пара SS:ESP для уровня 3 не нужны, т.к. не

существует вызова, в котором вызывающая программа менее привилеги-

рованна, чем вызвавшая в кольце 3.

После успешного прохождения командой CALL шлюза вызова без

нарушений правил защиты, процессор должен начать работать с новым

стеком.

Для этого в регистры SS:ESP из сегмента TSS загружаются селектор

сегмента и указатель стека, соответствующий новому уровню привилегий.

Например, если вызвана PL1 – процедура, в регистры SS:ESP загружаются

значения SS1 и ESP1.

После загрузки регистров SS:ESP для адресации нового стека процессор

сразу же включает в новый стек старые селектор сегмента и указатель стека,

которые адресуют вершину старого стека. Затем процессор анализирует поле

счетчика WC дескриптора шлюза вызова и автоматически копирует из

старого стека в новый указанное число двойных слов. Они представляют

собой параметры, передаваемые вызываемой процедуре. Эти параметры

размещаются в новом стеке так же, как и в старом. Наконец, в новый стек

включается адрес возврата CS:EIP. Таким образом, после производства этих

действий новый стек выглядит точно так же, как будто во внутреннем кольце

произведено включение в стек параметров и выполнена команда FAR CALL

(рис. 5.21).

Начальные значения SS:ESP для трех уровней привилегий в TSS только

считываются и никогда не изменяются при работе процессора.

Внешний стек

(PL3)

Внутренний стек

(PL1)

Параметр 1

SS3

Параметр 2

ESP3

Параметр 3

Параметр 1

Параметр 4

SS3:ESP3

Параметр 2

Параметр 3

Параметр 4

EIP

SS1:ESP1

Рис. 5.21.

Для инициирования выполнения вызванной процедуры остается только

загрузить значения селектора и смещения из дескриптора шлюза вызова в

регистры CS:EIP.

При переключении стека процессор осуществляет следующие защитные

проверки:

121

• контролирует задание правильного указателя стека для более

привилегированного уровня;

• проверяет нахождение сегмента стека на правильном уровне

привилегий (например, селектор SS0 должен адресовать сегмент

на уровне 0 и иметь поле RPL=0);

• убеждается в том, что в новом стеке достаточно места для старого

указателя стека (8 байт), копируемых параметров (0-128 байт),

адреса возврата (8 байт) и тех локальных переменных, которые

может включать в стек вызываемая процедура;

Привилегированная процедура осуществляет возврат при помощи

команд FAR RET, FAR RETn. При этом происходит обратное переключение

стека и удаление параметров из обоих стеков.

Виртуальная память UltraSPARC II

UltraSparc II – это 64-разрядная машина, которая поддерживает

виртуальную память со страничной организацией и с 64-битными

виртуальными адресами. Однако, по ряду причин программы не могут

использовать полное 64-битное виртуальное адресное пространство.

Допустимая виртуальная память делится на две зоны по 2

байтов каждая,

одна из которых находится в верхней части виртуального адресного

пространства, а другая – в нижней. Между ними находится «дырка»,

содержащая адреса, которые не используются.

Максимальная физическая память компьютера UltraSPARC II составляет

байт (2200 Гбайт). Поддерживается четыре размера страниц: 8, 64, 512

Кбайт и 4 Мбайта. Отображение этих страниц приведено на рис. 5.22.

Биты 51 13 48 16 45 19 42 22

Номер

виртуальной

ст

аницы К8

смещение

Номер

виртуальной

страницы К64

смещение

Номер

виртуальной

страницы К512

смещение

Номер

виртуальной

страницы М4

смещение

Страничн

ый кадр

К8

смещение

Страничн

ый кадр

К16

смещение

Страничн

ый кадр

К512

смещение

Страничн

ый кадр

М4

смещение

Биты 28 13 25 16 22 19 19 22

Рис. 5.22

Из-за огромного виртуального адресного пространства обычная таблица

страниц (как в Pentium II) не будет практичной. Здесь применяется

122

следующий подход. Устройство управления памятью содержит таблицу TLB

(Translation Lookaside Buffer – буфер быстрого преобразования адреса)

. Эта

таблица отображает номера виртуальных страниц в номера физических

страниц кадров. Для страниц размером в 8 К существует 2

номеров

виртуальных страниц, которые все не могут быть отображены.

Поэтому TLB содержит только номера самых последних используемых

виртуальных страниц. Страницы команд и страницы данных

рассматриваются отдельно. Для каждой из этих категорий в TLB включены

номера 64 последних используемых виртуальных страниц. Каждый элемент

буфера включает номер виртуальной страницы и соответствующий номер

физического страничного кадра. Когда номер процесса вызывает его

контекст, виртуальный адрес в этом контексте передается в контроллер

управления памятью, то он с помощью специальной схемы сравнивает номер

виртуальной страницы со всеми элементами буфера быстрого

преобразования адреса TLB для данного контекста одновременно. Если

обнаружится совпадение, номер страничного кадра в этом элементе буфера

соединяется со смещением, взятым из виртуального адреса, что бы получить

41-битный физический адрес и обработать некоторые флаги. Буфер быстрого

преобразования адреса

изображен на рис. 5.23 а. Если

совпадение не обнаружено

происходит

промах в TLB,

который вызывает ловушку в

операционной системе. Данный

промах отличается от ошибки из-

за отсутствия страницы. Промах

буфера TLB может произойти,

даже если нужная страница

присутствует в памяти.

Теоретически операционная система может сама загрузить новый элемент

этого буфера для нужной виртуальной страницы. Однако для ускорения

данной операции к этой работе подключается аппаратное обеспечение, если

программное обеспечение взаимодействует с ним.

TLB (контроллер управления памятью)

Бит

достоверности

Виртуальная

страница

Контекст

Физическая

страница

лаги

***

Рис. 5.23 а

Операционная система должна сохранять наиболее часто используемые

элементы буфера TLB в таблице под названием буфер хранения

преобразований (

TSB – translation storage buffer). Эта таблица простроена как

кэш-память прямого отображения виртуальных страниц. Каждый 16-байтный

элемент данной таблицы содержит бит достоверности, номер контекста, туг

виртуального адресного пространства, номер физической страницы и

несколько флаговых битов. Если размер кэш-памяти составляет, допустим,

8192 элемента, тогда все виртуальные страницы, у которых младшие 13

битов отображаются в 0000000000000, будут претендовать на элемент 0 в

данной таблице (рис. 5.23 б). Размер таблицы определяется программным

обеспечением и передается в контроллер управления памятью через

специальные регистры, доступные только для операционной системы.

123

При промахе буфера преобразований операционная система проверяет,

содержит ли соответствующий элемент буфера TLB нужную виртуальную

страницу. Контроллер управления памятью вычисляет адрес этого элемента и

помещает его в свой внутренний регистр, доступный для операционной

системы. Если нужный элемент есть в таблице хранения преобразований, то

какой-нибудь элемент удаляется из буфера TLB, а соответствующий элемент

буфера хранения преобразований копируется туда. Аппаратное обеспечение

с помощью алгоритма LRU вы-

бирает, какой именно элемент

нужно выкинуть.

Если нужной виртуальной

страницы нет в кэш-памяти,

операционная система использует

другую таблицу для нахождения

информации о странице, которая

может находится или не

находится в основной памяти.

Таблица, которая применяется для

этого процесса, называется

тран-

слирующей таблицей. Поскольку

здесь аппаратное обеспечение не

участвует в поиске элементов,

операционная система может

использовать любой формат. Если

поиск страницы в таблице

трансляции привел к нахождению

нужной страницы в памяти, то

элемент TSB в кэш-памяти

обновляется. Если в результате поиска обнаружилось, что нужной таблицы

нет в памяти, то происходит стандартная ошибка.

TLB (контроллер управления памятью +

программное обеспечение)

Бит

достоверности

Виртуальная

страница

Контекст

Физическая

страница

лаги

***

Элемент 0

совместно

используется всеми

виртуальными

страницами, ока-

нчивающимися на 0

…00

Элемент 0

совместно

используется всеми

виртуальными

страницами,

оканчивающимися

на 0 …01

Рис. 5.23 б

Сравним схемы разбиения на страницы в Pentium II и UltraSPARC II.

Pentium II поддерживает чистую сегментацию, чистое разбиение на страницы

и сегментацию в сочетании с разбиением на страницы. UltraSPARC II

поддерживает только разбиение на страницы. Pentium II использует

аппаратное обеспечение для перезагрузки буфера TLB только в случае

промаха TLB. UltraSPARC II в случае такого промаха просто передает

управление операционной системе.

Причина этого различия состоит в том, что Pentium II использует 32-

разрядные сегменты, а такие маленькие сегменты (только 1 млн страниц)

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

Pentium II могли бы возникнуть проблемы, если бы программа использовала

тысячи сегментов, но т.к. ни в одной версии Windows или UNIX не

поддерживается более одного сегмента на процесс, никаких проблем не

возникает. UltraSPARC II — 64-битная машина. Она может содержать до 2

млрд страниц, поэтому таблицы страниц не работают. В будущем все

124

машины будут иметь 64-битные виртуальные адресные пространства, и

схема UltraSPARC II станет нормой.

Виртуальная память и кэширование

На первый взгляд виртуальная память и кэширование никак не связаны,

но на самом деле они сходны. При наличии виртуальной памяти вся

программа хранится на диске и разбивается на страницы фиксированного

размера. Некоторое подмножество этих страниц находится в основной

памяти. Если программа главным образом использует страницы из основной

памяти, то ошибки из-за отсутствия страницы будут встречаться редко и

программа будет работать быстро. При кэшировании вся программа хранится

в основной памяти и разбивается на блоки фиксированного размера.

Некоторое подмножество этих блоков находится в кэш-памяти. Если

программа главным образом использует блоки из кэш-памяти, то промахи

будут происходить редко и программа будет работать быстро. Как видно,

виртуальная и кэш-память идентичны, только работают на разных уровнях

иерархии.

Различия в виртуальной и кэш-памяти. Промахи кэш-памяти

обрабатываются аппаратным обеспечением, а ошибки из-за отсутствия

страниц обрабатываются операционной системой. Блоки кэш-памяти обычно

гораздо меньше страниц (64 байта или 8 Кбайт). Кроме того, таблицы

страниц индексируются по старшим битам виртуального адреса, а кэш-

память индексируется по младшим битам адреса памяти. Однако, по

существу, различие существует только в реализации.

5.2. ВИРТУАЛЬНЫЕ КОМАНДЫ ВВОДА-ВЫВОДА

Набор команд уровня архитектуры команд полностью отличается от

набора команд микроархитектурного уровня.

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

команд из уровня архитектуры команд, а также несколько новых, очень

важных команд. Ввод-вывод – это одна из областей в которых два этих

уровня различаются очень сильно. Причины различия.

• Пользователь, способный выполнить команды ввода-вывода уровня

архитектуры команд, может считать конфиденциальную информацию,

которая хранится в системе и может представлять угрозу системе;

• Обычные нормальные программисты не хотят осуществлять ввод-вывод

на уровне команд, поскольку это утомительно.

Вместо этого для осуществления ввода-вывода нужно установить

определенные поля и биты в ряде регистров устройств, затем подождать,

125

пока операция закончится и проверить, что произошло. Диски обычно

содержат биты регистров устройств для обнаружения следующих ошибок:

Аппаратура диска не смогла выполнить позиционирование.

Несуществующий элемент памяти определен как буфер.

процесс ввода-вывода на диск (с диска) начался до ого, как

закончился предыдущий.

Ошибка синхронизации при считывании.

Обращение к несуществующему диску.

Обращение к несуществующему цилиндру.

Обращение к несуществующему сектору.

Ошибка проверки записи после операции записи.

При наличии одной из этих ошибок устанавливается соответсвующий

бит в регистре устройств.

Файлы

Один из способов организации виртуального ввода-вывода –

использование абстракции под названием

файл. Файл состоит из

последовательности байтов, записанных на устройство ввода-вывода. Если

устройство является устройством хранения информации (диск), то файл

можно считать обратно. Эта абстракция позволяет легко организовать

виртуальный ввод-вывод.

Для операционной системы файл является последовательностью байтов.

Ввод-вывод файлов осуществляется с помощью системных вызовов для

открытия, чтения, записи и закрытия файлов. Процесс открытия файлов

позволяет операционной системе найти файл на диске и передать в память

информацию, необходимую для доступа к этому файлу.

После открытия файла его можно считывать. Системный вызов для

считывания должен иметь как минимум следующие параметры:

• Указание, какой именно открытый файл нужно считывать;

• Указатель на буфер в памяти, в который нужно поместить данные;

• Число считываемых байтов.

Данный системный вызов помещает требуемые данные в буфер. Обычно

он возвращает число считанных байтов. Это число может быть меньше

запрашиваемого.

С каждым открытым файлов связан указатель, который сообщает, какой

бит будет считываться следующим.

После команды

read указатель дополняется число считанных байтов,

поэтому последовательные команды

read считывают последовательные

блоки данных из файла. Обычно этот указатель можно установить на особое

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

Когда программа закончила считывание файла, она может закрыть его и

сообщить операционной системе, что она больше не будет использовать этот

файл. Операционная система может освободить пространство в таблице, в

которой хранилась информация об этом файле.

126

В операционных системах универсальных вычислительных машин файл

представляет собой более сложную структуру. Здесь файл может быть

последовательностью логических записей, каждая из которых имеет строго

определенную структуру. Некоторые операционные системы различают

файлы, у которых все элементы имеют одинаковую структуру, и файлы,

содержащие разные типы данных.

Основная виртуальная команда ввода считывает следующую запись из

нужного файла и помещает ее в основную память, начиная с определенного

адреса (рис. 5.24). Чтобы выполнить эту операцию, виртуальная команда

должна получить сведения о том, какой файл считывать и купа поместить

запись. Часто существуют параметры для чтения некоторой записи, которые

определяются или по ее месту в файле, или по ее ключу.

Номер

логической

аписи

огическая запись

для чтения

Основная

память

Запись 18

уфер

огическая запись

для чтения

Основная

память

Запись 19

уфер

Рис. 5.24

Основная виртуальная команда вывода записывает логическую запись из

памяти в файл. Последовательные команды

write производят

последовательные логические записи в файл.

Реализация виртуальных команд ввода-вывода

Основной вопрос в проблеме организации виртуальных команд ввода-

вывода – распределение памяти. Единичным блоком может быть один сектор

на диске, но чаще он состоит из последовательных секторов.

Еще одно фундаментальное свойство реализации системы файлов –

хранится ли файл в последовательных блоках или нет. Восприятие файлов

прикладным программистом сильно отличается от восприятия файла

операционной системой. Программист воспринимает файл как линейную

последовательность байтов или логических записей. Операционная система

127

воспринимает файл как упорядоченную, но необязательно

последовательную, совокупность единичных блоков на диске.

Для того, чтобы операционная система могла доставить байт или

логическую запись n из какого-то файла, она должна пользоваться

некоторым методом для определения местонахождения данных. Если файл

расположен последовательно, то операционная система должна знать только

место начала файла, чтобы вычислить позицию нужной записи.

Если файл расположен на диске непоследовательно, то только по

начальной позиции невозможно определить местоположение требуемой

записи. Чтобы найти произвольный байт или логическую запись, нужна

таблица (так называемый

индекс файла), которая выдает единичные блоки и

их физические адреса на диске. Индекс файла может быть организован либо

в виде списка адресов блоков (UNIX), либо в виде списка логических

записей, для каждой из которых дается адрес на диске и смещение. Иногда

каждая логическая запись имеет

ключ, и программы могут обращаться к

записи по этому ключу, а не по номеру логической записи. В этом случае

каждый элемент таблицы должен содержать не только информацию о

местонахождении записи на диске, но и ее ключ. Такая структура обычно

применяется в универсальных вычислительных машинах.

Альтернативный метод нахождения блоков файлов – организовать файл

в виде связного списка. Каждый единичный блок содержит адрес

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

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

Например, для диска с 64 К блоками операционная система должна иметь в

памяти таблицу из 64 К элементов, в каждом из которых дается индекс

следующего единичного блока. Так, если файл занимает блоки 4, 52, 19, то

элемент 4 таблицы будет содержать число 52, элемент 52 – число 19, а 19

элемент – специальный код, указывающий на конец файла. Так работают

файловые системы в MS DOS, Windows 95 b Windows 98. Windows NT

поддерживает эту систему файлов, но и кроме того имеет свой собственную

систему, которая больше похожа на файловую систему UNIX.

Сравнение двух типов расположения файлов.

Последовательно расположенными файлами легко управлять, но если

максимальный размер файла не известен заранее, эту технологию нельзя

использовать. Если файл располагается непоследовательно, то проблем с

поиском связного пространства не возникает.

С другой стороны, если максимальный размер файла известен заранее,

то программа может заранее определить серии секторов, точно

соответствующих размерам различных файлов.

Чтобы распределить пространство на диске для файла, операционная

система должна следить, какие блоки доступны, а какие уже заняты другими

файлами. При записи на компакт-диск такие вычисления производятся один

раз и навсегда, а на жестком диске файлы постоянно записываются и

удаляются. Один из способов – сохранить список всех «дырок». Этот список

называется

списком свободной памяти.

128

Рассмотрим размер единичного блока. Здесь играют роль несколько

факторов.

Время поиска и время, затрачиваемое на вращение диска, затормаживает

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

удельный вес непроизводственных затрат.

Чем меньше размер единичного блока, тем больше их должно быть, что

влечет за собой длинные индексы файлов и большие таблицы в памяти.

Маленькие блоки имеют свои преимущества. В маленьких блоках

меньше потери памяти за счет эффекта фрагментации. Однако, в последнее

время самым важным фактором считается быстрота передачи данных,

поэтому размер блоков постоянно увеличивается.

Команды управления директориями

Информация, доступная компьютеру без вмешательства человека

называется

неавтономной. Автономная информация требует вмешательства

человека (вставить диск).

Неавтономная информация хранится в файлах. Обычно операционная

система группирует неавтономные файлы в директории. Минимально

необходимые системные вызовы для работы с файловой системой

следующие:

создание файла и введение его в директорию;

стирание файла из директории;

переименование файла;

изменение статуса файла.

Применяются различные схемы защиты файлов. Например, пароль.

Виртуальные команды для параллельной обработки

Некоторые вычисления удобно проводить с помощью дух и более

параллельных процессоров, т.е. как будто бы на разных процессорах. Чтобы

несколько процессов могли проистекать параллельно, нужны специальные

виртуальные команды. Повышение производительности компьютеров за счет

развития технологии ограничено законами физики. Единственный путь, не

входящий в противоречие с законами природы – создание параллельных

вычислений.

В компьютере с несколькими процессорами каждый из нескольких

взаимодействующих процессов можно приписать к одному определенному

процессору, чтобы выполнять несколько действий одновременно. Если в

компьютере имеется только один процессор, эффект параллельной обработки

можно смоделировать. Для этого процессы будут выполняться по очереди,

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

несколькими процессами. Но даже в том случае, когда параллельная

обработка моделируется, удобно считать, что каждому процессу

приписывается свой собственный процессор. При моделированной

129

параллельной обработке возникают те же проблемы, что и при реальной

параллельной обработке.

Формирование процесса

Программа работает как часть какого-то процесса. Этот процесс, как и

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

через которое можно получить доступ к программам и данным. Состояние

включает как минимум счетчик команд, слово состояния программы,

указатель стека и регистры общего назначения.

Большинство современных операционных систем позволяют

формировать и прерывать процессы динамически. Для формирования нового

процесса требуется системный вызов. Этот системный вызов может просто

создать клон вызывающей программы или позволить исходному процессу

определить начальное состояние нового процесса, т.е. его программу, данные

и начальный адрес.

В одних случаях исходный процесс сохраняет частичный или полный

контроль над порожденным процессом. Виртуальные команды позволяют

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

завершать подчиненные процессы. В других случаях исходный процесс

никак не контролирует подчиненный, так, что два процесса работают

независимо друг от друга.

Состояние гонок

Во многих случаях параллельные процессы должны взаимодействовать

и их работу нужно синхронизировать. Пусть существует два процесса 1 и 2,

которые взаимодействуют через общий буфер основной памяти. Пусть

процесс 1 –

производитель (producer), а процесс 2 – потребитель (consumer).

Производитель формирует числа и помещает в память, а потребитель

выводит их на печать.

Эти два процесса работают с различной скоростью, печать идет

медленнее, чем производство чисел. Если производитель видит, что буфер

заполнен, то он временно приостанавливает операцию, переходит в режим

ожидания. Кодда потребитель взял число из буфера, он сообщает

производителю, что можно работать дальше. Если потребитель видит, что

буфер пуст, он приостанавливает работу.

При программной реализации рассмотренного случая две программы

выполняют проверку состояния буфера и в зависимости от результатов

проверки либо продолжают работы, либо приостанавливаются. Возможно

ложное поведение процессов в случае параллельной обработки процессов.

Допустим, процесс считал информацию о состоянии буфера. После этого

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

состояние буфера. Первый процесс принимает решение на основе

информации, которая была взята ранее, до изменения состояния буфера, что

может войти в конфликт с текущим его состоянием.

130