§ 5.1.Общиепринципыорганизацииввода-вывода
Обеспечение операций ввода-вывода, наравне с обеспечением непосредственно
вычислительных операций, является одной из основных задач любой операционной сис-
темы. Под операциями ввода-вывода в целом понимается обмен данными между памя-
тью и устройствами, внешними по отношению к памяти и процессору, такими как жест-
кие диски, монитор, клавиатура, мышь, таймер и т.д. Для обеспечения этой возможности
используются аппаратные и программные средства. В основе реализации операций вво-
да-вывода лежит рассмотренный ранее механизм прерываний, который обеспечивает
параллельность работы центрального процессора с устройствами ввода-вывода и други-
ми запущенными процессами. Вообще с точки зрения процессора ввод-вывод информа-
ции так же является процессом.
Следует отметить, что запись или чтение большого количества информации из ад-
ресного пространства ввода-вывода (например, с жесткого диска) приводят к увеличе-
нию количества операций ввода-вывода что, в свою очередь, повышает нагрузку на цен-
тральный процессор. Для освобождения процессора от операций последовательного
вывода данных из оперативной памяти или последовательного ввода в нее реализован
механизм прямого доступа внешних устройств к памяти - ПДП (Direct Memory Access,
DMA). Для технической реализации этого метода применяется специализированный
контроллер прямого доступа к памяти, имеющий несколько спаренных линий - каналов
DMA, которые могут подключаться к различным устройствам. В отличие от прерыва-
ний, где один номер прерывания мог соответствовать нескольким устройствам, каналы
DMA всегда находятся в монопольном владении устройств.
В общем виде система ввода-вывода персонального компьютера представлена на
рис.5.1 [3].
Рис.5.1. Система ввода-вывода ПК
Два нижних уровня этой системы составляет аппаратную часть, т.е. сами устройст-
ва, непосредственно выполняющие операции, и их контроллеры, служащие для органи-
зации совместной работы устройств и остальной вычислительной системы. Следующий
уровень составляют драйверы устройств ввода-вывода, скрывающие от разработчиков
операционных систем особенности функционирования конкретных устройств и обеспе-
чивающие четко определенный интерфейс между аппаратными средствами и следую-
щем уровнем - базовой подсистемой ввода-вывода, которая, в свою очередь, предостав-
ляет механизм взаимодействия между драйверами устройств и ядром операционной
системы.
Управление вводом-выводом осуществляется следующим образом. Центральный
процессор посылает устройству управления команду выполнить некоторое действие для
устройства ввода-вывода. Устройство управления исполняет команду, транслируя сиг-
налы центрального процессора в сигналы, понятные устройству ввода/вывода. К сожа-
лению, быстродействие устройства ввода-вывода намного меньше быстродействия цен-
трального процессора, поэтому сигнал готовности приходилось ожидать достаточно
долго, постоянно опрашивая соответствующую линию интерфейса на наличие или от-
сутствие нужного сигнала. В первых ОС в это время центральный процессор простаи-
вал. В современных ОС во время ожидания сигнала готовности от устройства ввода-
вывода центральный процессор переключается на выполнение другой программы. При
появлении сигнала готовности генерируется прерывание от соответствующего устройст-
ва ввода/вывода. Вышесказанное продемонстрировано на рис.5.2 [2].
Рис.5.2. Механизм управления вводом-выводом
Все системные вызовы, связанные с осуществлением операций ввода-вывода, по
способам реализации взаимодействия процесса и устройства ввода-вывода можно раз-
бить на три группы.
К первой, наиболее привычной для большинства программистов группе относятся
блокирующиесясистемныевызовы. Как следует из самого названия, применение тако-
го вызова приводит к блокировке инициировавшего его процесса, т. е. процесс перево-
дится операционной системой из состояния исполнение в состояние ожидание. Завер-
шив выполнение всех операций ввода-вывода, предписанных системным вызовом,
операционная система переводит процесс из состояния ожидание в состояние готов-
ность. После того как процесс будет снова выбран для исполнения, в нем произойдет
окончательный возврат из системного вызова.
Ко второй группе относятся неблокирующиесясистемныевызовы. В данном слу-
чае системный вызов возвращается немедленно, выполнив предписанные ему операции
ввода-вывода полностью, частично или не выполнив совсем, в зависимости от текущей
ситуации (состояния устройства, наличия данных и т. д.). В качестве примера такого вы-
зова можно привести периодическую проверку на поступление информации с клавиату-
ры при выполнении трудоемких расчетов.
К третьей группе относятся асинхронныесистемныевызовы. Процесс, использо-
вавший асинхронный системный вызов, никогда в нем не блокируется. Системный вы-
зов инициирует выполнение необходимых операций ввода-вывода и немедленно воз-
вращается, после чего процесс продолжает свою регулярную деятельность. Об
окончании завершения операции ввода-вывода операционная система впоследствии ин-
формирует процесс изменением значений некоторых переменных, передачей ему сигна-
ла или сообщения или каким-либо иным способом.
Необходимо четко понимать разницу между неблокирующимися и асинхронными
вызовами. Неблокирующийся системный вызов для выполнения операции чтения вер-
нется немедленно, при этом может быть прочитано как запрошенное количество байтов,
так и меньшее их количество или вообще ничего. Асинхронный системный вызов для
этой операции также вернется немедленно, но требуемое количество байт все равно бу-
дет прочитано в полном объеме.
Для обеспечения операций ввода-вывода достаточно часто используются механиз-
мы буферизации и кэширования. Рассмотрим их более подробно.
Под буфером обычно понимается некоторая область памяти для запоминания ин-
формации при обмене данных между двумя устройствами, двумя процессами или про-
цессом и устройством. Существует три основные причины, приводящие к использова-
нию буферов при выполнении операции ввода-вывода [2].
Первая причина буферизации - это разные скорости приема и передачи информации, ко-
торыми обладают участники обмена. Вторая причина - это разные объемы данных, ко-
торые могут быть приняты или получены участниками обмена единовременно. Третья
причина буферизации связана с необходимостью копирования информации из приложе-
ний, осуществляющих ввод-вывод, в буфер ядра операционной системы и обратно.
Под словом кэш (cash – «наличные») обычно понимают область быстрой памяти,
содержащую копию данных, расположенных где-либо в более медленной памяти, пред-
назначенную для ускорения работы вычислительной системы. В современных системах
для этой задачи обычно используется кэш-память центрального процессора. Не следует
смешивать понятия буферизации и кэширования. Буфер обычно содержит единственный
набор данных, существующий в системе, в то время как кэш по определению содержит
копию данных, существующих где-нибудь еще. Функции буферизации и кэширования
не обязательно должны быть локализованы в базовой подсистеме ввода-вывода. Они мо-
гут быть частично реализованы в драйверах и даже в контроллерах устройств, скрытно
по отношению к базовой подсистеме.
С точки зрения программиста, наиболее часто используемой операцией ввода-
вывода является ввод-вывод на жесткие диски. В этом случае обычно речь идет о работе
с файлами, т.е. о файловом вводе-выводе. Рассмотрим принципы размещения данных на
жестком диске более подробно.
§ 5.2.Общиепринципыразмещенияданныхнамагнитныхдисках
Под файлом понимают набор данных, организованных в виде совокупности запи-
сей одинаковой структуры [2]. В любой ОС работу с файлами обеспечивает файловая
система - набор спецификаций и соответствующее им программное обеспечение, кото-
рые отвечают за создание, уничтожение, организацию, чтение, запись, модификацию и
перемещение файловой информации, а также за управление доступом к файлам и за
управление ресурсами, которые используются файлами. Именно файловая система оп-
ределяет способ организации данных на диске или на каком-нибудь ином носителе дан-
ных. В качестве примера можно привести файловую систему FAT, реализация для кото-
рой имеется в абсолютном большинстве ОС, работающих в современных ПК.
Как правило, все современные ОС имеют соответствующие системыуправления
файлами, которые выполняют несколько задач по работе с файлами[2]. Во-первых, че-
рез систему управления файлами связываются по данным все системные обрабатываю-
щие программы. Во-вторых, с помощью этой системы решаются проблемы централизо-
ванного распределения дискового пространства и управления данными. В-третьих,
благодаря использованию той или иной системы управления файлами пользователям
предоставляются следующие возможности:
• создание, удаление, переименование (и другие операции) именованных наборов
данных (именованных файлов) из своих программ или посредством специальных
управляющих программ, реализующих функции интерфейса пользователя с его дан-
ными и активно использующих систему управления файлами;
• работа с не дисковыми периферийными устройствами как с файлами;
• обмен данными между файлами, между устройствами, между файлом и устройст-
вом;
• работа с файлами с помощью обращений к программным модулям системы управ-
ления файлами;
• защита файлов от несанкционированного доступа.
В некоторых ОС может быть несколько систем управления файлами, что обеспе-
чивает им возможность работать с несколькими файловыми системами. Очевидно, что
системы управления файлами, будучи компонентом ОС, не являются независимыми от
этой ОС, поскольку они активно используют соответствующие вызовы API. С другой
стороны, системы управления файлами сами дополняют API новыми вызовами. Можно
сказать, что основное назначение файловой системы и соответствующей ей системы
управления файлами - организация удобного доступа к данным, организованным как
файлы. Следует различать понятия файловаясистема и системауправленияфайла-
ми.
Под термином «файловаясистема » понимаются, прежде всего, принципы досту-
па к данным, организованным в файлы. Этот же термин часто используют и по отноше-
нию к конкретным файлам, расположенным на том или ином носителе данных. А тер-
мин «системауправленияфайлами » употребляется по отношению к конкретной
реализации файловой системы, то есть это комплекс программных модулей, обеспечи-
вающих работу с файлами в конкретной операционной системе.
Следует заметить, что любая система управления файлами не существует сама по
себе, она разработана для работы в конкретной ОС. В качестве примера [2] можно ска-
зать, что всем известная файловая система FAT (file allocation table) имеет множество
реализаций как система управления файлами. Так, система, получившая это название и
разработанная для первых персональных компьютеров, называлась просто FAT (сейчас
ее называют FAT-12). Ее разрабатывали для работы с дискетами, и некоторое время она
использовалась при работе с жесткими дисками. Потом ее усовершенствовали для рабо-
ты с жесткими дисками большего объема, и эта новая реализация получила название
FAT-16. Это название файловой системы мы используем и по отношению к системе
управления файлами самой MS-DOS. Реализацию же системы управления файлами для
OS/2, которая использует основные принципы системы FAT, называют super-FAT; ос-
новное отличие - возможность поддерживать для каждого файла расширенные атрибу-
ты. Есть версия системы управления файлами с принципами FAT и для Windows 95/98,
для Windows NT и т. д. Другими словами, для работы с файлами, организованными в со-
ответствии с некоторой файловой системой, для каждой ОС должна быть разработана
соответствующая система управления файлами. Эта система управления файлами будет
работать только в той ОС, для которой она и создана; но при этом она позволит работать
с файлами, созданными с помощью системы управления файлами другой ОС, работаю-
щей по тем же основным принципам файловой системы.
Для того чтобы загружать ОС с жесткого диска, а далее с ее помощью и организо-
вать работу той или иной системы управления файлами, были приняты специальные
системные соглашения о структуре диска, которые далее будут рассмотрены более под-
робно. В любом случае в начале магнитного диска всегда располагается информация о
его логической организации и простейшая программа, с помощью которой можно нахо-
дить и загружать программы загрузки той или иной ОС.
Информация на магнитных дисках размещается и передается блоками. Каждый та-
кой блок называется сектором (sector), сектора расположены на концентрических до-
рожках поверхности диска. Каждая дорожка (track) образуется при вращении магнитно-
го диска под зафиксированной в некотором предопределенном положении головкой
чтения/записи. Жесткий диск (раньше он назывался НЖМД - накопитель на жестких
магнитных дисках) содержит один или более дисков, но обычно под термином «жесткий
диск» понимают весь пакет магнитных дисков.
Группы дорожек одного радиуса, расположенных на поверхностях магнитных дис-
ков, образуют так называемые цилиндры (cylinder). Современные жесткие диски могут
иметь по несколько десятков тысяч цилиндров, в то время как на поверхности дискеты
число дорожек (цилиндров), как правило, составляет всего восемьдесят. Вышесказанное
продемонстрировано на рис.5.3 [3].
Рис.5.3. Структура хранения информации на жестком диске
Каждый сектор состоит из поляданных и поляслужебнойинформации, ограни-
чивающей и идентифицирующей его. Размер сектора (точнее - емкость поля данных)
устанавливается контроллером или драйвером. Пользовательский интерфейс DOS под-
держивает единственный размер сектора - 512 байт. BIOS же предоставляет возможно-
сти работы с секторами размером 128, 256, 512 или 1024 байт. Таким образом, если
управлять контроллером жесткого диска непосредственно, а не через программный ин-
терфейс более высокого уровня, можно обрабатывать секторы и с другими размерами.
Однако в большинстве современных ОС размер сектора выбирается равным 512 байт,
аналогично DOS.
При работе диска набор пластин вращается вокруг своей оси с высокой скоростью,
подставляя по очереди под магнитныеголовки (head) соответствующих дорожек все их
сектора. Физический адрес сектора на диске определяется с помощью трех координат [c-
h-s], где с - номер цилиндра, h - номер рабочей поверхности диска (магнитной головки),
a s- номер сектора на дорожке. Номер цилиндра с лежит в диапазоне 0...С-1, где С - ко-
личество цилиндров. Номер рабочей поверхности диска h принадлежит диапазону 0...Н-
1, где Н - число магнитных головок в накопителе. Номер сектора на дорожке s указыва-
ется в диапазоне 1...S, где S - количество секторов на дорожке. Например, триада [1-0-2]
адресует сектор 2 на дорожке 0 (обычно верхняя рабочая поверхность) цилиндра 1.
Обмен информацией между оперативной памятью и дисками физически осуществ-
ляется только секторами. Вся совокупность физических секторов на винчестере пред-
ставляет его неформатированную емкость.
При планировании использования жесткого диска естественным параметром явля-
ется время, которое потребуется для выполнения очередного запроса. Время, необходи-
мое для чтения или записи сектора можно разделить на две составляющие: время обмена
информацией между магнитной головкой и компьютером, которое обычно не зависит от
положения данных и определяется скоростью их передачи (transfer speed), и время, не-
обходимое для позиционирования головки над заданным сектором, - время позициони-
рования (positioning time). Время позиционирования, в свою очередь, состоит из време-
ни, необходимого для перемещения головок на нужный цилиндр - времени поиска (seek
time) и времени, которое требуется для того, чтобы нужный сектор довернулся под го-
ловку - задержки на вращение (rotational latency). Времена поиска пропорциональны
разнице между номерами цилиндров предыдущего и планируемого запросов, и их легко
сравнивать. Задержка на вращение определяется довольно сложными соотношениями
между номерами цилиндров и секторов предыдущего и планируемого запросов и скоро-
стями вращения диска и перемещения головок. Без знания соотношения этих скоростей
сравнение становится невозможным. Поэтому естественно, что набор параметров пла-
нирования сокращается до времени поиска различных запросов, определяемого текущим
положением головки и номерами требуемых цилиндров, а разницей в задержках на вра-
щение пренебрегают.
Существует несколько алгоритмов поиска необходимого сектора [3]. Простейший
из них - First Come First Served (FCFS) - первым пришел, первым обслужен. Все запро-
сы организуются в очередь FIFO и обслуживаются в порядке поступления. Алгоритм
прост в реализации, но может приводить к достаточно длительному общему времени об-
служивания запросов. Более правильным было бы первоочередное обслуживание запро-
сов, данные для которых лежат рядом с текущей позицией головок, а уж затем далеко
отстоящих. Алгоритм Short Seek Time First (SSTF) - короткое время поиска первым как
раз и исходит из этой позиции. Для очередного обслуживания выбирается запрос, дан-
ные для которого лежат наиболее близко к текущему положению магнитных головок.
Естественно, что при наличии равноудаленных запросов решение о выборе между ними
может приниматься исходя из различных соображений, например по алгоритму FCFS.
Следует отметить, что этот алгоритм похож на алгоритм SJN для планирования процес-
сов, если за аналог оценки времени выполнения процесса выбирать расстояние между
текущим положением головки и положением, необходимым для удовлетворения запро-
са.
Еще один вид алгоритмов - алгоритмы сканирования (SCAN, C-SCAN, LOOK, C-
LOOK). В простейшем из алгоритмов сканирования - SCAN головки постоянно переме-
щаются от одного края диска до другого, по ходу дела обслуживая все встречающиеся
запросы. По достижении другого края направление движения меняется, и все повторяет-
ся снова. Если есть информация, что обслужен последний попутный запрос в направле-
нии движения головок, то мы можно не доходить до края диска, а сразу изменить на-
правление движения на обратное. Полученная модификация алгоритма SCAN получила
название LOOK.
Допустим, что к моменту изменения направления движения головки в алгоритме
SCAN, т. е. когда головка достигла одного из краев диска, у этого края накопилось
большое количество новых запросов, на обслуживание которых будет потрачено доста-
точно много времени (не забываем, что надо не только перемещать головку, но еще и
передавать прочитанные данные!). Тогда запросы, относящиеся к другому краю диска и
поступившие раньше, будут ждать обслуживания несправедливо долго. Для сокращения
времени ожидания запросов применяется другая модификация алгоритма SCAN - цик-
лическое сканирование. Когда головка достигает одного из краев диска, она без чтения
попутных запросов перемещается на другой край, откуда вновь начинает движение в
прежнем направлении. Этот алгоритм получил название C-SCAN. По аналогии с C-
SCAN реализован и алгоритм C-LOOK.
Жесткий диск может быть разбит на несколько разделов (partition) которые в
принципе затем могут использоваться либо одной ОС, либо различными ОС. Причем
самым главным является то, что на каждом разделе может быть организована своя фай-
ловая система. Однако для организации даже одной единственной файловой системы
необходимо определить, по крайней мере, один раздел.
Разделы диска могут быть двух типов - primary (обычно этот термин переводят как
первичный) и extended (расширенный). Максимальное число primary-разделов равно
четырем. При этом на диске обязательно должен быть по крайней мере один primary-
раздел. Если primary-разделов несколько, то только один из них может быть активным.
Именно загрузчику, расположенному в активном разделе, передается управление при
включении компьютера и загрузке операционной системы. Остальные primary-разделы в
этом случае считаются «невидимыми, скрытыми» (hidden).
Согласно спецификациям на одном жестком диске может быть только один
ехtended - раздел, который, в свою очередь, может быть разделен на большое количество
подразделов - логическихдисков (logical). В этом смысле термин «первичный» следует
признать не совсем удачным переводом слова primary; можно это слово перевести и как
«простейший, примитивный». В этом случае становится понятным и логичным термин
extended.
Один из primary-разделов должен быть активным, именно с него должна загру-
жаться программа загрузки операционной системы, или так называемый менеджерза-
грузки, назначение которого - загрузить программу загрузки ОС из какого-нибудь дру-
гого раздела, и уже с ее помощью загружать операционную систему. Поскольку до
загрузки ОС система управления файлами работать не может, то следует использовать
для указания упомянутых загрузчиков исключительно абсолютные адреса в формате [с-
h-s].
По физическому адресу [0-0-1] на винчестере располагается главнаязагрузочная
запись (master boot record, MBR), содержащая внесистемныйзагрузчик (non-system
bootstrap - NSB), а также таблицуразделов (partition table, PT). Эта запись занимает
ровно один сектор, она размещается в памяти, начиная с адреса 0:7C00h, после чего
управление передается коду, содержащемуся в этом самом первом секторе магнитного
диска. Таким образом, в самом первом (стартовом) секторе физического жесткого диска
находится не обычная запись boot record, как на дискете, a master boot record.
MBR является основным средством загрузки с жесткого диска, поддерживаемым
BIOS. В MBR находятся три важных элемента:
• программа начальной загрузки (non-system bootstrap). Именно она запускается BIOS
после успешной загрузки в память первого сектора с MBR. Она, очевидно, не пре-
вышает 512 байт и ее хватает только на то, чтобы загрузить следующую, чуть более
сложную программу, обычно - стартовый сектор операционной системы и передать
ему управление;
• таблица описания разделов диска (partition table). Располагается в MBR по смеще-
нию 0x1BE и занимает 64 байта;
• сигнатура MBR. Последние два байта MBR должны содержать число AA55h. По на-
личию этой сигнатуры BIOS проверяет, что первый блок был загружен успешно.
Использование такой сигнатуры выбрано не случайно. Ее успешная проверка позво-
ляет установить, что все линии передачи данных могут передавать и нули, и едини-
цы.
Таблица partition table описывает размещение и характеристики имеющихся на
винчестере разделов. Можно сказать, что эта таблица разделов - одна из наиболее важ-
ных структур данных на жестком диске. Если эта таблица повреждена, то не только не
будет загружаться операционная система (или одна из операционных систем, установ-
ленных на винчестере), но перестанут быть доступными и данные, расположенные на
винчестере, особенно если жесткий диск был разбит на несколько разделов. Упрощенно
структура MBR представлена в таблице 5.1 [2].
Таблица 5.1
Смещение (Off-
set)
+1BEh
+1CEh
+1DEh
+1EEh
+1FEh
Размер (Sise)
(байт)
Содержимое (Contents)
Программа анализа Partition Table и загрузки System
Bootstrap с активного раздела жесткого диска
Partition 1 entry (Описатель раздела)
Partition 2 entry
Partition 3 entry
Partition 3 entry
Сигнатура (АА55h)
Из таблицы видно, что в начале этого сектора располагается программа анализа
таблицы разделов и чтения первого сектора из активного раздела диска. Сама таблица
partition table располагается в конце MBR, и для описания каждого раздела в этой табли-
це отводится по 16 байтов. Первым байтом в элементе раздела идет флаг активности
раздела boot indicator (0 - не активен, 128 (80Н) - активен). Он служит для определения,
является ли раздел системным загрузочным и есть ли необходимость производить за-
грузку операционной системы с него при старте компьютера. Активным может быть
только один раздел. За флагом активности раздела следует байт номера головки, с кото-
рой начинается раздел. За ним следует два байта, означающие соответственно номер
сектора и номер цилиндра загрузочного сектора, где располагается первый сектор за-
грузчика операционной системы. Затем следует кодовый идентификатор System ID
(длиной в один байт), указывающий на принадлежность данного раздела к той или иной
операционной системе и установке на нем соответствующей файловой системы. В табл.
5.2 приведены некоторые (наиболее известные) идентификаторы [2].
