Лекция 1. Введение в сетевые ОС (стр. 4 )

Таблицы страниц требуют в памяти по одной записи на каждую виртуальную страницу, так как они индексируются по номеру этой страницы. В случае если архитектура процессора 32-битная, размер таблицы страниц будет составлять 4 Мбайта, но многоуровневые таблицы позволяют ОС не хранить все данные в ОЗУ одновременно. Но в том случае если процессор использует 64-битную архитектуру, таблица страниц займёт 30 Тбайт, что нереально сейчас и не будет реальным в ближайшем будущем. Одним из способов организации 64-битного адресного пространства является инвертированная таблица страниц. В этой модели таблица содержит по одной записи на каждый страничный блок в реальной памяти, а не на страницу в ВАП. Например, при 64-разрядных виртуальных адресах, размере страниц 4 Кбайта и 256 Мбайт ОЗУ таблица страниц потребует только 65 536 элементов. Недостатком инвертированных таблиц является то, что перевод виртуального адреса в физический становится намного сложнее. АО не может более найти физическую страницу используя номер виртуальной страницы как индекс в таблице. Вместо этого необходимо осуществлять поиск по всей таблице. Инвертированные таблицы используются в настоящее время на некоторых рабочих станциях IBM и HP и будут встречаться все чаще, так как 64-битные машины получают все большее распространение.

Буфер быстрого преобразования адресов

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

При страничной организации ВАП процесса делится на равные части автоматически, без учета смыслового значения данных. Такой подход не позволяет обеспечить дифференцированный доступ к разным частям программы (например, запретив запись в область кода программы) или совместно использовать фрагменты программ разными процессами.

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

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

Таблица 5.1. Сравнение страничной организации памяти и сегментации

Вопрос	Страничная память	Сегментация
Нужно ли программисту знать о наличии подобной техники?	Нет	Да
Сколько в системе линейных адресных пространств?	1	Много
Может ли суммарное адресное пространство превышать размеры физической памяти?	Да	Да
Возможно ли разделение кода и данных, а также раздельная защита для них?	Нет	Да
Легко ли размещаются структуры данных с непостоянными размерами?	Нет	Да
Облегчен ли совместный доступ пользователей к процедурам?	Нет	Да
Зачем была придумана эта техника?	Для получения большого линейного адресного пространства без дополнительных затрат на физическую память	Для возможности разбиения программ и данных на логически независимые адресные пространства, облегчения совместного доступа и защиты

На этапе создания процесса во время загрузки его образа в ОЗУ система инициализирует таблицу сегментов процесса (аналогичную таблице страниц), в которой для каждого сегмента указываются базовый физический адрес сегмента в оперативной памяти, размер сегмента, правила доступа к сегменту, признаки модификации, присутствия и обращения к сегменту и т. д.

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

Рис. 5.4. Преобразование виртуального адреса при сегментации

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

Сегментно-страничная организация памяти

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

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

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

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

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

На втором этапе полученный виртуальный адрес представляется в виде пары (номер страницы, смещение в странице). Старшие разряды, содержащие номер виртуальной страницы, заменяются номером физической страницы из таблицы страниц, а младшие разряды (содержащие смещение) остаются без изменения. В процессорах Intel i386, i486, Pentium используется именно такой подход (с тем отличием, что таблицы страниц реализованы двухуровневыми).

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

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

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

На третьем этапе к номеру физической страницы пристыковывается младшая часть виртуального адреса – смещение.

Лекция 6. Организация ввода-вывода в ОС

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

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

Напомним их в контексте, необходимом для последующего изложения.

Классификация устройств ввода-вывода

Устройства ввода-вывода можно условно разделить на две категории: блочные и символьные устройства. Блочными называются устройства, хранящие информацию в виде блоков фиксированного размера, причем у каждого блока имеется адрес. Размер блока обычно варьируется от 512 до 32 768 байт. Важное свойство блочного устройства состоит в том, что каждый его блок может быть прочитан независимо от остальных блоков. Наиболее распространенными блочными устройствами являются диски.

Другим типом устройств ввода-вывода являются символьные устройства, которые принимают или предоставляют поток символов без какой-либо блочной структуры. Эти устройства не являются адресуемыми и не выполняют операцию поиска (например, принтеры, сетевые карты, «мыши» и т. д.).

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

Взаимодействие с устройством

Устройства ввода-вывода обычно состоят из механической и электронной частей. Электронный компонент устройства называется контроллером устройства или адаптером и часто реализуется в виде платы расширения компьютера. Механический компонент находится в самом устройстве.

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

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

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

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

Также существуют различные гибридные схемы с отображаемыми на адресное пространство буферами данных и отдельными портами ввода-вывода (например, в процессорах Intel x86 и Pentium помимо пространства портов с номерами от 0 до 65 535, адресное пространство от 640Kбайт до 1Мбайт зарезервировано под буферы данных устройств ввода-вывода).

Обе схемы обращения к контроллерам имеют свои сильные и слабые стороны. К достоинствам отображаемого доступа относятся следующие особенности:

1) не требуется специальных машинных команд для взаимодействия с портами (IN, OUT);

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

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

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

К недостаткам отображаемого доступа можно отнести две особенности:

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

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

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

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

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

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

Прямой доступ к памяти (DMA)

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

Прерывания устройств

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

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

Задачи ПО ввода-вывода

С точки зрения программной поддержки ввода-вывода в ОС ключевыми вопросами являются:

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

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

· обработка ошибок;

· способ переноса данных: синхронный (блокирующий) или асинхронный (управляемый прерываниями);

· способ буферизации;

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

Программные уровни ввода-вывода

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

Рис. 6.1. Программные уровни ввода-вывода

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

1) запомнить состояние всех регистров, не сохраненных аппаратурой;

2) установить контекст для процедуры обработки прерываний (выполнение этого действия может включать установку TLB, MMU и таблицы страниц);

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

4) выдать подтверждение контроллеру прерываний. Если централизованного контроллера прерываний нет, разрешить прерывания;

5) скопировать содержимое регистров с того места, где они были сохранены (возможно в стеке), в таблицу процессов;

6) запустить процедуру обработки прерываний. Она извлечет информацию из регистров контроллера устройства, инициировавшего прерывание;

7) выбрать процесс, которому нужно передать управление. Если прерывание разблокировало какой-либо высокоприоритетный процесс, он может быть выбран в качестве следующего;

8) установить контекст MMU для следующего работающего процесса. Также может понадобиться определенная установка TLB;

9) загрузить регистры нового процесса и начать его выполнение.

Уровень драйверов устройств отвечает за взаимодействие с внешними устройствами (драйвером называется специальная программа, разработанная для управления устройством ввода-вывода). Для унифицированного взаимодействия с драйверами в большинстве ОС определены стандартные интерфейсы блочного и символьного драйверов. Эти интерфейсы включают набор процедур, которые могут вызываться остальной ОС для обращения к драйверу.

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

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

Независимое от устройств ПО ввода-вывода должно выполнять следующие функции:

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

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

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

4) обеспечить захват и освобождение выделенных устройств;

5) иметь независимый от устройств размер блока.

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

Реальные устройства ввода-вывода

Типовыми устройствами ввода-вывода являются диски (жесткие и гибкие), часы (таймер), клавиатура и дисплей.

Диски

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

Таймер

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