Востокин С.В.. Операционные системы. Экзаменационные вопросы по разделам дисциплины. Учебник предназначен для студентов специальности Фундамен тальная информатика и информационные технологии
 Скачать 2.09 Mb.
|
|
Раздел V. Организация ввода – вывода Лекция 14. Введение во взаимодействие с внешними устройствами Типы внешних устройств. Способы программного взаимодействия с внешними устройствами: циклический опрос, прерывания, прямой доступ к памяти. Архитектура программного обеспечения ввода- вывода. Файловая система. Логическая организация файлов. Физи- ческая организация файлов. Типы внешних устройств. Устройства ввода-вывода можно разделить на два класса: блок-ориентированные, байт-ориентиро- ванные. Типичным блок-ориентированным устройством является диск. Обмен информацией с дисками и адресация информации вы- полняется блоками. Для байт-ориентированных устройств характер- на потоковая передача информации и отсутствие адресации. Клавиа- тура, манипулятор-мышь, сетевой адаптер представляют данную разновидность внешних устройств. Имеются внешние устройства, которые сложно отнести к какому-либо из перечисленных классов. Например, программируемый таймер и другие устройства, инфор- мирующие компьютер о наступлении внешних событий. Какой программный механизм используется для передачи ин- формации из внешних устройств в операционную систему? У внеш- них устройств имеются специальные регистры, в которые можно записывать и считывать значения. Обращение к регистрам контроллера может выполняться дву- мя способами. Регистры внешних устройств могут отображаться на память компьютера. Программное взаимодействие при этом проис- ходит с использованием команды MOVE и других аналогичных ко- 124 манд пересылки. Достоинством данного способа является удобство программирования. В языках программирования высокого уровня, в которых предусмотрены механизмы обращения к памяти (например, С, C++, Pascal), не требуется никаких специальных механизмов для взаимодействия внешними устройствами с регистрами, отображен- ными на память. Также этот способ взаимодействия подразумевает высокую скорость передачи данных. Типичный пример такого взаи- модействия – видеокарты. Недостатком является необходимость усложнения аппаратуры компьютера по следующим причинам. Тре- буется согласование скорости с внешними устройствами, так как обычно устройства ввода-вывода обладают значительно меньшей пропускной способностью, чем оперативная память. Необходимо определять границы кэшируемых областей памяти, так как отобра- женные на внешние устройства участки памяти кэшировать нельзя. Возникающую неоднородность памяти необходимо поддерживать на уровне микросхем вспомогательной логики: контроллеров- концентраторов памяти и контроллеров-концентраторов ввода- вывода (т.н. северный и южный мосты в архитектуре Intel). Кроме этого сужается диапазон адресуемой физической памяти. Другой возможностью программного взаимодействия является использование специального пространства ввода-вывода, не пересе- кающегося с оперативной памятью. Доступ к регистрам внешних устройств в нем осуществляется специальными командами чтения IN и записи OUT регистров внешних устройств. В данном случае упрощается аппаратная организация взаимодействия с внешними устройствами и несколько усложняется программное взаимодей- ствие. Необходимы ассемблерные вставки в код на языке высокого уровня, поддержка компилятором или специальные функции в биб- лиотеке времени исполнения. Процедура организации взаимодействия с внешними устрой- ствами может организовываться тремя способами. Циклический опрос. Команда на выполнение некоторой опе- рации записывается во входной регистр внешнего устройства. Далее в цикле считывается и анализируется значение выходного регистра до тех пор, пока не будет считан признак завершения операции. Не- достатком данного способа является неэффективное использование процессора и шины памяти (данных). 125 Взаимодействие по прерыванию. Команда на выполнение некоторой операции записывается во входной регистр внешнего устройства. Далее процессор может выполнять другие полезные действия одновременно с работой внешнего устройства или остано- виться, при этом не блокировать системную шину. Когда операция внешнего устройства завершена, внешнее устройство самостоятель- но извещает процессор, инициируя прерывание. В ответ на преры- вание процессор запоминает адрес текущей команды и переходит к выполнению специальной процедуры обработки прерывания. В ней организуется считывание уже готовой информации из выходных регистров внешнего устройства. Далее происходит возврат управле- ния по сохраненному адресу прерванной команды. Этот способ является более эффективным с точки зрения ис- пользования аппаратных ресурсов. Однако он требует сложной про- граммной реализации: специальной настройки таблицы векторов обработки прерывания; нелинейной организации потока управления в программе; некоторого механизма планирования действий процес- сора, чтобы исключить простой процессора в течение ввода-вывода. Взаимодействие с использованием прямого доступа к па- мяти. В данном способе передача информации из внешнего устрой- ства в оперативную память производится не с использованием цен- трального процессора, а напрямую специальным контроллером пря- мого доступа (DMA-контроллер). Контроллер самостоятельно реа- лизует описанную во втором способе процедуру взаимодействия с внешним устройством, а по окончании передачи данных прерывани- ем извещает центральный процессор о завершении взаимодействия. Преимуществом способа является еще большая эффективность, осо- бенно при передаче пакетов данных. Способ позволяет контроллеру обращаться к системной шине, пока сам процессор выполняет ко- манду. Очевидно, что способ требует дополнительных усилий по программированию ввода-вывода. Архитектура программного обеспечения ввода-вывода. Для автоматизации рутинных низкоуровневых процедур в операци- онных системах реализуется специальная подсистема ввода-вывода, примерная архитектура которой показана на рис.13.1. Рассмотрим компоненты, показанные на рисунке. Система об- работки прерываний находится на нижнем уровне иерархии. Управ- 126 ление прерываниями выполняет сама операционная система. При возникновении прерываний происходит вызов драйверов внешних устройств. Драйверы выполняют обработку запросов с уровня поль- зователей или прерываний и имеют доступ к регистрам контролле- ров внешних устройств. Имеется возможность синхронизации рабо- ты драйверов с использованием специальных мьютексов режима ядра. Рис. 13.1. Архитектура подсистемы ввода-вывода В операционных системах имеется независимый от устройств уровень «системы буферизации», типичными функциями которого Приложение Библиотечная функция (RTL) Системные вызовы (API) Система буферизации Драйверы устройств Обработка прерываний пользователь супервизор Обработка системных вызовов 127 являются обеспечение независимого размера блоков данных, защи- та, общий интерфейс к драйверам устройств и их именование, рас- пределение/освобождение устройств, уведомление об ошибках. Этот уровень единообразно подготавливает блоки для передачи запросов драйверам от вышележащих слоев и получения ответа. Обращение к функциям ввода-вывода, как и к другим серви- сам операционной системы, осуществляется посредством системных вызовов. Иногда они задействуются непосредственно или, как в ОС Windows, через функции интерфейса прикладного программирова- ния (OpenFile, CreateFile, WriteFile), служащего для унификации различных версий операционной системы. Выше по иерархии располагается библиотека поддержки вре- мени исполнения (RTL), тоже содержащая функции ввода-вывода (printf, scanf и т.д.). Функции библиотеки RTL используют функции вызовов интерфейсов прикладного программирования API, часто являясь просто их обертками. В C++ функции потокового вывода <<, >> основаны на printf, scanf. Зная о такой организации ввода- вывода в некоторых языках (С, С++), можно сократить размер ис- полняемого файла, работая напрямую с вызовами API операционной системы. Для этого можно использовать функции ввода-вывода API, не компонуя соответствующие функции из RTL. Файловая система. Важнейшими типами внешних устройств являются разнообразные накопители данных. Необходимые удоб- ные абстракции для работы с ними реализуются файловыми систе- мами. Файловая система – часть операционной системы, назначение которой – обеспечить удобный интерфейс для работы с данными, хранящимися на дисках. Файлы – именованный набор данных. Файл может идентифицироваться по имени. Обычно файлы могут иметь одинаковые имена. Уникальность файла определяется составным именем, включающим символьные имена каталогов. Файл может идентифицироваться уникальным дескриптором. Если файловая си- стема представлена в виде сети, файл может находиться в несколь- ких каталогах сразу. Кроме обычных файлов с данными имеются файлы, ассоции- рованные с устройствами ввода-вывода. Это позволяет выполнять ввод-вывод посредством программного интерфейса доступа к фай- лам. Каталоги с файлами также являются специальным видом фай- лов. Каталоги файлов хранят атрибуты файла. Для организации за- 128 щиты файлов от несанкционированного доступа, аналогично другим объектам операционной системы, используется избирательный или мандатный механизм безопасности. Внешние устройства хранения имеют следующий простой ин- терфейс доступа к данным: по указанному адресу можно записать или считать блок данных фиксированного размера (в несколько ки- лобайт). Например, для доступа к блоку на диске требуется указать его физическое положение на поверхности носителя (номер поверх- ности, номер цилиндра (дорожки), номер сектора). Поэтому файло- вая система должна организовывать некоторый произвольный до- ступ, обеспечивая отличные от блочной модели способы работы с данными. Это логическая организация файлов. Также требуется поддерживать некоторую организацию физических блоков внутри файлов. Это физическая организация файлов. Логическая организация файлов. Приведем некоторые рас- пространенные модели файлов. Последовательность байт. Это типовая модель доступа, ис- пользуется как произвольный, так и последовательный доступ к хранимым данным. Последовательность блоков переменной длины. Эта модель позволяет по логическому номеру блока адресовать его содержимое. В некоторых файловых системах используется гибридная модель, когда в файле содержится несколько независимых последовательно- стей байт (потоков данных). Это может оказаться удобным, напри- мер, для хранения видео, звука и субтитров в отдельных потоках средствами файловой системы (рис.13.2). Рис. 13.2. Последовательность блоков переменной длины Упорядоченная или неупорядоченная последовательность ключей. По ключу адресуется ассоциированный с ним блок данных (рис.13.3). Если последовательность ключей упорядочена, то имеет- 1 2 3 номер блока 129 ся возможность выбрать следующий блок по порядку относительно текущего блока. Данная логическая организация удобна для управ- ления и организации доступа к файлами очень больших размеров. Рис. 13.3. Последовательность ключей Физическая организация файлов. Рассмотрим некоторые распространенные приемы физической организации файлов. Последовательность блоков (непрерывное размещение). Бло- ки, принадлежащие файлу, следуют по порядку их физических адре- сов. В каталоге указывается адрес первого блока, количество блоков или последний блок. Достоинство этого способа – простота, а ос- новная проблема – фрагментация блоков. Этот способ, например, находит применение в файловых системах длительного хранения, в частности ленточных запоминающих устройствах. Связанный список блоков. Простейший способ преодолеть фрагментацию (рис.13.4). Рис. 13.4. Связанный список блоков Проблемой является большое время доступа к информации в конце файла. Все блоки нужно последовательно перебрать. Инфор- мация о следующем блоке является частью блока, на это уходит не- которое количество памяти. Ключ Данные 130 Связанный список индексов. Используемый на практике спо- соб организации файловых систем относительно небольшого разме- ра (рис.13.5). Он основан на применении таблицы размещения файла (File Allocation Table, FAT). Файловые системы, использующие этот способ: FAT12, FAT16, FAT32, VFAT. Метод предложен Microsoft. Рис. 13.5. Связанный список индексов Идея заключается в переносе информации о следующем блоке в отдельную таблицу в начальных блоках физического носителя. Индекс блока в таблице и его физическое положение на диске связа- ны линейным преобразованием. Блоки таблицы индексов считыва- ются в оперативную память. Благодаря этому можно быстро пере- брать цепочку индексов блоков файла в памяти и запросить нужный блок на диске. Поэтому эффективность произвольного доступа ока- зывается высокой. Преимуществом также является целостность файловой системы, поддерживаемая несколькими копиями таблицы индексов и хранением информации о состоянии каждого физическо- го блока в таблице индексов. Недостатком является рост размера требуемой служебной информации при увеличении размеров файло- вой системы (фактически предел 8 тебибайт при 2 Кб кластерах). Непосредственное перечисление блоков и способы, использу- ющие сбалансированные деревья (рис.13.6). Это наиболее распространенная группа способов физической организации файлов. Часть физических блоков в произвольной об- ласти дискового пространства отводится под ссылочные структуры для доступа к блокам с данными. Например, на рисунке показана структура таких блоков. В корневом блоке, адрес которого записы- таблица индексов Положение в таблице (индекс блока) однозначно определяет смещение блока на физическом носителе. 131 вается в каталоге, хранится 13 полей, содержащих адреса других блоков. Первые 10 полей непосредственно адресуют блоки файла. Если их недостаточно, то используется следующее поле, адресую- щее блок, в котором может быть записано 256 адресов следующих блоков файла. Если размер файла превышает 266 блоков, то исполь- зуется двенадцатая запись корневого блока, с использованием кото- рой физические блоки адресуются уже с двойным уровнем косвен- ности и так далее. Общее количество физических блоков в файле, таким образом, может достигать 16.843.018. Рис. 13.6. Непосредственное перечисление блоков В настоящее время разработано большое количество файло- вых систем различного назначения и устройства. Помимо логиче- ской и физической организации при рассмотрении архитектур фай- ловых систем обсуждаются методы обеспечения надежности (например, журналирование), повышения скорости доступа (экстен- ты), хранения больших объемов данных (распределенные парал- лельные файловые системы), защиты данных (шифрованные файло- вые системы) и другие. 256 256x256x256 256x256 256 256 10 13 1 1 1 132 Экзаменационные вопросы по разделу V 1. Архитектура программного обеспечения ввода-вывода. Средства программного взаимодействия с внешними устройствами. Архи- тектура программного стека, функции слоев. 2. Общие принципы организации файловых систем и файлов. Идентификация файлов в файловых системах, логическая и фи- зическая организация файлов. 133 БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Бэкон, Дж. Операционные системы: параллельные и распредели- тельные системы / пер. с англ. СПб.: Питер, 2004. 2. Гордеев, А.В. Операционные системы: учеб. для вузов. Изд. 2-е. СПб.: Питер, 2005. 3. Дейтел Х., Дейтел П., Чофнес Д. Операционные системы: 2 т. Т. 1. Основы и принципы / пер. с англ. М.: Бином-Пресс, 2007. 4. Дейтел Х., Дейтел П., Чофнес. Д. Операционные системы: 2 т. Т. 2. Распределенные системы, сети, безопасность / пер. с англ. М.: Бином-Пресс, 2007. 5. Олифер В.Г., Олифер Н.А. Сетевые операционные системы: учеб. для вузов. СПб.: Питер, 2007. 6. Столлингс, В. Операционные системы: внутреннее устройство и принципы проектирования / пер. с англ. М. [и др.]: Вильямс, 2004. 7. Таненбаум Э., Вудхал А. Операционные системы. Разработка и реализация / пер. с англ. СПб.; М.; Нижний Новгород, Питер, 2007. 8. Таненбаум Э., Бос. Х. Современные операционные системы. Изд. 4-е. – СПб.: Питер, 2015. |