Операционные системы: разработка и реализация

Статья познакомит Вас с тем, как устроена система ввода/вывода компьютера, как она применяется в операционной системе. Это позволит не только понять сущность работы компьютера, но и приступить к написанию собственной ОС!

Ввод/вывод в операционных системах

Ввод/вывод
Одна из важнейших функций операционной системы состоит в управлении всеми устройствами ввода/вывода компьютера. Операционная система должна давать этим устройствам команды, перехватывать прерывания и обрабатывать ошибки. Она должна также обеспечить простой и удобный интерфейс между устройствами и остальной частью системы. Интерфейс, насколько это возможно, должен быть одинаковым для всех устройств (для достижения независимости от применяемого оборудования). Программное обеспечение ввода/вывода составляет существенную часть операционной системы. Тому, как операционная система управляет устройствами ввода/вывода, и посвящена эта статья.
Принципы аппаратуры ввода/вывода
Разные специалисты рассматривают аппаратуру ввода/вывода, аппаратное обеспечение ввода/вывода с различных точек зрения. Инженеры-электронщики видят в ней микросхемы, проводники, источники питания, двигатели и прочие физические компоненты. Программисты, в первую очередь, обращают внимание на интерфейс, предоставляемый программному обеспечению, — команды, принимаемые аппаратурой, выполняемые ею функции, ошибки, о которых аппаратура может сообщить.В то же время программирование многих устройств ввода/вывода часто оказывается тесно связанным с их внутренним функционированием.
Устройства ввода/вывода
Устройства ввода/вывода можно грубо разделить на две категории: блочное устройство и символьное устройство. Блочными называются устройства, хранящие информацию в виде адресуемых блоков фиксированного размера. Обычно размеры блоков варьируются от 512 байт до 32 768 байт. Важное свойство блочного устройства состоит в том, что каждый блок может быть прочитан независимо от остальных блоков. Наиболее распространенными блочными устройствами являются диски.
Если приглядеться внимательнее, то окажется, что граница между блочно адресуемыми устройствами и устройствами, к отдельным составляющим которых нельзя адресоваться напрямую, не определена строго. Все согласны с тем, что диск является блочно адресуемым устройством, так как вне зависимости от текущего положения головки дисковода всегда можно переместить ее на определенный цилиндр и затем считать или записать отдельный блок с нужной дорожки. Рассмотрим теперь накопитель на магнитной ленте (магнитофон), применяемый для хранения резервных копий диска. На ленте хранится последовательность блоков. Если магнитофону дать команду прочитать некоторый блок, ему потребуется перемотать ленту и начать читать данные, пока процесс не дойдет до запрашиваемого блока. Эта операция подобна поиску блока на диске с той лишь разницей, что она занимает значительно больше времени. Кроме того, в зависимости от накопителя и формата хранящихся на нем данных не гарантирована запись отдельного произвольного блока в середине ленты. Попытка использовать магнитные ленты в качестве блочных устройств произвольного доступа явилась бы в какой-то степени натяжкой: никто их не использует таким образом.
Другой тип устройств ввода/вывода — символьные устройства. Символьное устройство принимает или предоставляет поток символов без какой-либо блочной структуры. Оно не является адресуемым и не выполняет операцию поиска. Принтеры, сетевые интерфейсные адаптеры, мыши (для указания точки на экране), крысы (для лабораторных экспериментов по психологии) и большинство других устройств, не похожих на диски, можно рассматривать как символьные устройства.
Такая схема классификации не совершенна. Некоторые устройства просто не попадают ни в одну из категорий. Например, часы не являются блочно адресуемыми. Они также не формируют и не принимают символьных потоков. Вся их деятельность сводится к инициированию прерываний в строго определенные моменты времени. Видеопамять также не укладывается в рамки этой модели. И все же классификация на блочные и символьные устройства является настолько общей, что неплохо подходит в качестве основы для достижения независимости от устройств некоторого программного обеспечения операционных систем, имеющего дело с вводом/выводом. Так, файловая система общается с абстрактными блочными устройствами, а зависимую от устройств часть оставляет программному обеспечению низкого уровня, драйверам устройств.
Контроллеры устройств
Устройства ввода/вывода, как правило, состоят из механической части и электронной части. В большинстве случаев эти части можно особо выделить для придания модели более модульного и общего характера. Электронный компонент называется контроллером устройства. В персональных компьютерах он обычно принимает форму печатной платы, вставляемой в слот расширения объединительной платы (ранее некорректно называемой материнской). Механический компонент находится в самом устройстве.
Плата контроллера обычно снабжается разъемом, к которому может быть подключен кабель, ведущий к самому устройству. Многие контроллеры способны управлять двумя, четырьмя или даже восемью идентичными устройствами. Если интерфейс между контроллером и устройством является стандартным, то есть официальным стандартом ANSI, IEEE или ISO, либо фактическим стандартом, это смягчает ограничения выпуска по отдельности контроллеров и устройств, удовлетворяющих данному интерфейсу. Так, многие компании производят жесткие диски, соответствующие интерфейсу IDE или SCSI.
Мы упоминаем о различии между контроллером и устройством потому, что операционная система практически всегда имеет дело с контроллером, а не с самим устройством. У большинства небольших компьютеров взаимодействие с устройствами организуется по модели единой шины, показанной на рис. 1. У больших машин, мэйнфреймов, применяется другая модель с несколькими шинами, которыми заведуют специализированные компьютеры ввода/вывода, называемые каналами ввода/вывода. Такая организация позволяет уменьшить нагрузку на основной процессор.

Рис. 1. Соединение процессора, памяти, контроллеров и устройств ввода/вывода
Интерфейс между устройством и контроллером часто является интерфейсом очень низкого уровня. Например, какой-нибудь жесткий диск может быть отформатирован по 256 секторов на дорожку, с размером секторов по 512 байт. В действительности с диска в контроллер поступает последовательный поток битов, начинающийся с заголовка сектора (преамбулы), за которым следует 4096 бит в секторе и, наконец, контрольная сумма, также называемая кодом исправления ошибок (ECCECC, Error-Correcting Code). Заголовок сектора записывается на диск во время форматирования. Он содержит номера цилиндра и сектора, размер сектора, информацию синхронизации и т. п.
Работа контроллера заключается в преобразовании последовательного потока битов в блок байтов и выполнении коррекции ошибок, если это необходимо. Обычно байтовый блок собирается бит за битом в буфере контроллера. Затем проверяется контрольная сумма блока, и если она совпадает с указанной в заголовке сектора, блок объявляется считанным без ошибок, после чего он копируется в оперативную память.
Контроллер монитора (видеоконтроллер) также работает как бит-последовательное устройство, на таком же низком уровне. Он считывает из памяти байты, содержащие символы, которые следует отобразить, и формирует сигналы, используемые для модуляции луча электронной трубки, заставляющие ее выводить изображение на экран. Видеоконтроллер также формирует сигналы, управляющие горизонтальным и вертикальным перемещениями электронного луча. Если бы не контроллер, программисту пришлось бы делать это самому. В действительности же операционная система всего-навсего инициализирует контроллер, задавая небольшое число параметров, таких как количество символов или пикселов в строке и число строк на экране, а тяжелую работу по управлению разверткой берет на себя контроллер.
У каждого отображаемый на адресное пространство памяти ввод/вывод, отображаемый на память контроллера есть несколько регистров, с помощью которых с ним может общаться центральный процессор. У некоторых компьютеров такие регистры являются частью единого адресного пространства системы. Примером такой системы может служить 680x0. Назначение адреса каждому из устройств производится посредством схем логики декодирования шины и контроллеров устройств. У других систем для устройств ввода/вывода отводится специальное адресное пространство, в котором выделяются адреса для каждого из устройств. Таковы, например, IBM PC-совместимые машины.
В дополнение к портам ввода/вывода, часто используются прерывания, при помощи которых контроллер может сообщить процессору, что его регистры готовы для записи или для чтения. Прерывание, прежде всего, является электрическим сигналом. Линия запроса аппаратного прерывания (IRQIRQ, Interrupt ReQuest line) является одним из физических входов чипа контроллера прерываний. Количество этих входов ограничено. Например, у персональных компьютеров Pentium только 15 IRQ доступны для устройств ввода/вывода. Некоторые из контроллеров встроены в материнскую плату, как, например, контроллер клавиатуры на IBM PC. У тех контроллеров, что вставляются в разъем на объединительной плате, установить соответствие между сигналом IRQ и устройством иногда можно при помощи перемычек или переключателей. Это бывает необходимо для исключения конфликтов, поскольку на современных материнских платах, поддерживающих технологию Plug'n'Play, IRQ назначаются программно. Каждая из линий IRQ связывается с вектором прерываний, который указывает на программу обработки прерывания. В качестве примера в табл. 1 приведены адреса ввода/вывода, IRQ и значения векторов прерываний для нескольких контроллеров IBM PC. В MINIX действуют те же самые значения IRQ, но векторы прерываний назначаются другие.
Операционная система обменивается с устройством информацией, записывая команды в регистры контроллера. Контроллер гибкого диска IBM PC воспринимает 15 различных команд, в том числе READ, WRITE, SEEK, FORMAT и CALIBRATE. У многих команд есть параметры, которые также передаются через регистры контроллера. Передав команду контроллеру, процессор может продолжить свою работу. Затем, когда устройство выполнит команду, контроллер инициирует прерывание, чтобы операционная система вновь получила управление и могла бы проверить результаты операции, которые процессор получает, считывая один или несколько байтов из регистров контроллера.
Таблица 1. Некоторые контроллеры, их адреса ввода/вывода, IRQ
и векторы прерываний для IBM PC, работающей под управлением MS-DOS
Контроллер ввода/вывода Адрес ввода/вывода IRQ Вектор прерывания

Контроллер ввода/вывода	Адрес ввода/вывода	IRQ	Вектор прерывания
Таймер Клавиатура Жесткий диск Дополнительный Принтер Дисковод Основной	040–043 060–063 1F0–1F7 RS232 2F8–2FF 378–37F 3F0–3F7 RS232 3F8–3FF	0 1 14 3 7 6 4	8 9 118 11 15 14 12

Прямой доступ к памяти (DMA)
Многие контроллеры, особенно контроллеры блок-ориентированных устройств, поддерживают прямой доступ к памяти — DMA (Direct Memory Access)прямой доступ к памяти ввод/вывод; прямой доступ к памяти DMA ввод/вывод. Чтобы понять, как работает DMA, познакомимся сначала с тем, как происходит чтение с диска в отсутствие DMA. Сначала контроллер считывает с диска блок (один или несколько секторов) последовательно, бит за битом, пока весь блок не окажется во внутреннем буфере контроллера. Затем контроллер проверяет контрольную сумму, чтобы убедиться, что при чтении не произошло ошибки. После этого контроллер инициирует прерывание. Когда операционная система начинает работу, она может прочитать блок диска побайтно или пословно, в цикле сохраняя считанное слово или байт в оперативной памяти.
Естественно, цикл, байт за байтом считывающий данные с контроллера, расходует процессорное время. Чтобы освободить процессор от низкоуровневой работы, и был изобретен прямой доступ к памяти. При использовании DMA процедура совершенно другая. Сначала центральный процессор программирует DMA-контроллер, устанавливая его регистры и указывая таким образом, какие данные и куда следует переместить (рис. 2). Затем процессор дает команду дисковому контроллеру прочитать данные во внутренний буфер и проверить контрольную сумму. Когда данные получены и проверены контроллером диска, устройство DMA может начинать работу.

Рис. 2. Работа DMA-контроллера
DMA-контроллер начинает перенос данных, посылая дисковому контроллеру по шине запрос на чтение. Этот запрос выглядит как обычный запрос чтения, потому контроллер диска даже не знает, поступил ли он от центрального процессора или от контроллера DMA. Обычно адрес памяти уже находится на адресной шине, соответственно, контроллер диска всегда в курсе, куда нужно переслать следующее слово из своего внутреннего буфера. Запись в память является еще одним стандартным циклом шины. Когда запись закончена, контроллер диска также по шине посылает сигнал подтверждения контроллеру DMA. Затем контроллер DMA увеличивает используемый адрес памяти и уменьшает значение счетчика байтов. После этого шаги со 2-го по 4-й повторяются, пока значение счетчика не станет равно нулю. По завершении цикла копирования контроллер DMA инициирует прерывание процессора, сообщая ему таким образом, что перенос данных завершен. Операционной системе не нужно копировать блок диска в память. Он уже находится там.
Как мы уже упоминали, до начала операции прямого доступа к памяти диск предварительно считывает данные в свой внутренний буфер. Возможно, вы задаетесь вопросом, почему контроллер не помещает данные прямо в оперативную память, по мере получения их с диска. Другими словами, зачем ему нужен внутренний буфер? Тому две причины. Во-первых, при помощи внутренней буферизации контроллер диска может проверить контрольную сумму до начала переноса данных в память. Если значения не совпадают, формируется сигнал об ошибке и перенос данных не производится.
Во-вторых, дело в том, что как только началась операция чтения с диска, биты начинают поступать с постоянной скоростью, независимо от того, готов контроллер диска их принимать или нет. Если контроллер диска попытается писать эти данные напрямую в память, ему придется делать это по системной шине. Если при передаче очередного слова шина окажется занятой каким-либо другим устройством (например, использующим ее в пакетном режиме), контроллеру диска придется ждать. Если следующее слово с диска прибудет раньше, чем контроллер успеет сохранить отложенное, контроллер либо потеряет предыдущее слово, либо ему придется запоминать его где-либо еще. Таким образом, необходимость внутренней буферизации становится очевидной. При наличии внутреннего буфера контроллеру диска шина не нужна до тех пор, пока не начнется операция DMA. В результате устройство контроллера диска оказывается проще, так как при операции прямого доступа к памяти параметр времени не является критичным. (Некоторые древние контроллеры действительно напрямую обращались к памяти, обладая внутренним буфером небольшого размера, что часто приводило к ошибкам перегрузки при занятости шины.)
Описанная выше двухэтапная процедура буферизации имеет важные последствия, касающиеся производительности ввода/вывода. Когда данные передаются от контроллера в память самим контроллером или центральным процессором, под дисковой головкой проходит следующий сектор данных, биты которого поступают в контроллер. Простые контроллеры не умели одновременно считывать и передавать данные, и сектор пропускался.
Как следствие, может быть прочитан любой другой сектор, кроме следующего, а для чтения всей дорожки необходимы два полных оборота диска. Если же время, требуемое для передачи сектора данных в память, превышает время считывания сектора, может потребоваться пропуск двух (или более) блоков.
Пропуск блоков с целью дать контроллеру время для передачи данных в память называется чередованием. При этом во время форматирования секторы нумеруются с учетом фактора чередования. На рис. 3, а показан диск с восемью секторами без чередования. На рис. 3, б вы видите тот же диск с фактором чередования 1. На рис. 3, в фактор чередования равен 2.

Рис. 3. а — диск без чередования; б — фактор чередования 1; в — фактор чередования 2
Идея подобной нумерации блоков в том, чтобы позволить системе читать блоки с последовательными номерами и чтобы аппаратное обеспечение работало с максимальной производительностью. Если бы диск был без чередования, а контроллер не справлялся с чтением последовательных блоков, то для полного последовательного считывания всей дорожки потребовалось бы 8 оборотов диска. (Конечно, проблема решаема и программно, но лучше, чтобы об этом заботился контроллер.)
DMA используется не во всех компьютерах. Главный аргумент против прямого доступа к памяти: центральный процессор обычно значительно превосходит DMA-контроллер по скорости и в состоянии выполнить ту же работу значительно быстрее (если только скорость ограничена не быстродействием устройства ввода/вывода). При отсутствии другой нагрузки у центрального процессора заставлять быстрый центральный процессор ждать, пока медленный контроллер DMA выполнит свою работу, бессмысленно. Кроме того, компьютер без контроллера DMA, с центральным процессором, выполняющим все программно, оказывается дешевле, что крайне важно в производстве компьютеров нижней ценовой категории.
Принципы программного обеспечения ввода/вывода
Перейдем теперь от рассмотрения аппаратуры ввода/вывода к знакомству с программным обеспечением ввода/вывода. Сначала мы проникнемся целями программного обеспечения ввода/вывода, а затем поглядим на различные способы выполнения операций ввода/вывода с точки зрения операционной системы.
Задачи программного обеспечения ввода/вывода
Ключевая концепция разработки программного обеспечения ввода/вывода известна как независимость от устройств. Эта концепция означает возможность написания программ, способных получать доступ к любому устройству ввода/вывода без предварительного указания конкретного устройства. Соответственно, программа, читающая данные из входного файла, должна с одинаковым успехом работать с файлом на дискете, жестком диске или компакт-диске. Причем без каких-либо изменений в программе. Например, должна быть возможность дать команду вроде
sort <input >output
и эта команда должна работать, невзирая на то, что указано в качестве входного устройства — гибкий диск, IDE-диск, SCSI-диск или клавиатура. В качестве выходного устройства также с равным успехом может быть указан экран, файл на любом диске или принтер. Все проблемы, связанные с отличиями этих устройств, должна решать операционная система.
Тесно связан с идеей независимости от устройств принцип единообразного именования. Имя файла или устройства должно быть просто текстовой строкой или целым числом и никоим образом не зависеть от физического устройства. В системе UNIX все диски могут быть произвольным образом интегрированы в иерархию файловой системы, поэтому пользователю не обязательно знать, какое имя какому устройству соответствует. Например, гибкий диск не запрещается смонтировать поверх каталога /usr/ast/backup, вследствие чего копирование файла в каталог /usr/ast/backup/monday автоматически приведет к копированию файлов на гибкий диск. Таким образом, все файлы и устройства адресуются одним и тем же способом: по пути к ним.
Другим важным аспектом программного обеспечения ввода/вывода является обработка ошибок. Ошибки должны обрабатываться как можно ближе к аппаратуре. Если контроллер обнаружил ошибку чтения, он должен попытаться по возможности исправить эту ошибку сам. Если он не в силах это сделать, тогда ошибку обязан обработать драйвер устройства, допустим, попытавшись прочитать этот блок еще раз. Многие ошибки бывают временными, как, например, ошибки чтения, вызванные пылинками на читающих головках. Такие ошибки часто не воспроизводятся при повторной попытке чтения блока. Только если нижний уровень пасует перед проблемой, о ней следует информировать верхний уровень. Во многих случаях восстановление после ошибок предпочтительно делать на нижнем уровне, прозрачно для верхних уровней, то есть так, что вышестоящие уровни даже не будут подозревать о наличии сбоев.
Еще один ключевой вопрос — способ переноса данных: синхронный (блокирующий) против асинхронного (управляемого прерываниями). Большинство операций ввода/вывода на физическом уровне являются асинхронными — центральный процессор запускает передачу данных и забывает о ней, пока не сгенерируется прерывание. Пользовательские программы значительно легче написать, используя блокирующие операции ввода/вывода, — после обращения к системному вызову read программа автоматически приостанавливается до тех пор, пока данные не появятся в буфере. Тем, чтобы операции ввода/вывода, в действительности являющиеся асинхронными, выглядели как блокирующие в программах пользователя, занимается операционная система.
Говоря о программном обеспечении ввода/вывода, нельзя обойти вниманием буферизацию. Часто данные, поступающие с устройства, не могут быть сохранены сразу там, куда они в конечном итоге направляются. Например, когда пакет приходит по сети, операционная система не знает, куда его поместить, пока не изучит его содержимое, для чего этот пакет нужно где-то временно пристроить. Кроме того, для многих устройств реального времени крайне важными оказываются параметры сроков поступления данных (например, для устройств воспроизведения цифрового звука), поэтому полученные данные должны быть помещены в выходной буфер заранее, чтобы скорость, с которой они извлекаются из буфера проигрывателем, не зависела от скорости заполнения буфера. Таким образом удается избежать неравномерности воспроизведения звука. Буферизация подразумевает копирование данных в значительных количествах, что часто является основным фактором снижения производительности операций ввода/вывода.
И последнее — это понятие выделенных устройств и устройств коллективного использования. С некоторыми устройствами ввода/вывода, такими как диски, может одновременно работать большое количество пользователей. При этом не должно возникать проблем, когда несколько пользователей одновременно откроют файлы на одном и том же диске. Другие устройства, такие как накопители на магнитной ленте, должны предоставляться в монопольное владение одному пользователю, пока он не завершит свою работу с этим устройством. Если два или более пользователей одновременно станут писать вперемешку блоки на одну ленту, ничего хорошего не получится. Введение понятия выделенных (монопольно используемых) устройств также привносит целый спектр проблем, таких как взаимоблокировки. Тем не менее операционная система обязана управлять как устройствами общего доступа, так и выделенными устройствами и преодолевать различные потенциальные проблемы самостоятельно.
Эти задачи решаются путем разбиения программного обеспечения ввода/вывода на четыре уровня.
1. Обработчики прерываний (нижний уровень).
2. Драйверы устройств.
3. Независимый от аппаратуры код операционной системы.
4. Пользовательские программы (верхний уровень).
Обработчики прерываний
Хотя программный ввод/вывод иногда бывает полезен, для большинства операций ввода/вывода прерывания являются неприятным, но необходимым фактом. Прерывания должны быть упрятаны как можно глубже во внутренностях операционной системы, чтобы о них знала как можно меньшая ее часть. Лучший способ завуалировать их заключается в блокировке драйвера, начавшего операцию ввода/вывода, вплоть до окончания этой операции и получения прерывания. Драйвер может заблокировать себя сам, выполнив на семафоре процедуру down, процедуру wait на переменной состояния, процедуру receive на сообщении или что-либо подобное.
Когда происходит прерывание, начинает работу обработчик прерываний. По ее окончании он может разблокировать драйвер-инициатор. В некоторых случаях это реализуется через процедуру up на семафоре. В других ситуациях обработчик прерываний вызывает процедуру монитора signal с переменной состояния. Или же он посылает заблокированному драйверу сообщение. В любом случае драйвер разблокируется обработчиком прерываний. Эта схема лучше всего работает в драйверах, являющихся процессами ядра со своим собственным состоянием, стеком и счетчиком команд.
Драйверы устройств
Весь код, зависимый от конкретного устройства, находится в драйверах. Каждый драйвер обслуживает один тип устройств или, как максимум, целый класс сходных устройств. Например, было бы хорошей идеей иметь один драйвер терминала, несмотря на то что система поддерживает несколько различающиеся типы терминалов. С другой стороны, примитивный механический терминал, распечатывающий текст, и интеллектуальный графический терминал с мышью разнятся настолько, что для них предпочтительны персональные драйверы.
Ранее в этой главе мы познакомились с функциями контроллеров устройств ввода/вывода. Как было сказано, у каждого контроллера есть набор регистров, используемых для того, чтобы давать опекаемому устройству команды и читать состояние устройства. Число таких регистров и выдаваемые команды зависят от конкретного устройства. Например, драйвер диска должен знать о секторах, дорожках, цилиндрах, головках, их перемещении и времени установки, двигателях и тому подобных вещах, что необходимо для правильной работы диска.
Вообще говоря, назначение драйвера в том, чтобы воспринимать абстрактные запросы от аппаратно-независимых программ верхнего уровня и сообщать им, что запрос выполнен. При этом, если в момент передачи запроса драйвер бездействовал, он сразу начинает работу. Если же драйвер был занят, запрос обычно помещается в очередь и обслуживается по мере возможности.
Поэтому для управления каждым устройством ввода/вывода, подключенным к компьютеру, требуется специальная программа. Эта программа, называемая драйвером устройства, часто пишется производителем устройства и распространяется в той же коробке. Поскольку для каждой операционной системы требуются специализированные драйверы, производители обычно поставляют драйверы для нескольких наиболее популярных операционных систем.
При обработке запроса на обмен данными драйвер прежде всего преобразует запрос из абстрактного представления в конкретную форму. Скажем, драйвер диска должен выяснить, где находится запрошенный блок данных, проверить, работает ли привод диска, находится ли головка над нужной дорожкой и т. д. Говоря коротко, драйвер должен сам определить свою последовательность действий.
После того как необходимые команды определены, драйвер начинает передавать их устройству через регистры контроллера. Причем с оглядкой на то, что некоторые контроллеры способны воспринимать только по одной команде за раз, а другие — цепочку команд, выполняемых далее без вмешательства операционной системы.
Когда все команды переданы, ситуация развивается по двум сценариям. Во многих случаях драйвер устройства должен ждать, пока контроллер не выполнит для него определенную работу, поэтому он блокируется до поступления прерывания от устройства. В других вариантах операция завершается без задержек, и драйверу не нужно блокироваться. Например, для прокрутки экрана в символьном режиме требуется записать лишь несколько байтов в регистры контроллера. Вся операция занимает несколько наносекунд.
Таким образом, заблокированный драйвер будет либо активизирован прерыванием, либо он вовсе не блокируется. Как бы то ни было, по завершении операции драйвер обязан убедиться, что операция прошла без ошибок. Если все в порядке, драйверу, возможно, придется передать данные (например, только что прочитанный блок) независимому от устройств программному обеспечению. Наконец, драйвер возвращает некоторую информацию вызывающей программе для уведомления той о статусе завершения операции. Если в очереди находились другие запросы, один из них теперь может быть выбран и запущен, иначе драйвер блокируется в ожидании следующего запроса.
Независимое от устройств программное обеспечение ввода/вывода
Хотя некоторая часть программного обеспечения, независимая от устройств ввода/вывода предназначена для работы с конкретными устройствами, другая часть является независимой от устройств. Расположение точной границы между драйверами и независимым от устройств программным обеспечением обусловлено системой (и устройствами), так как некоторые функции, которые могут быть реализованы независимым от устройств образом, часто выполняются прямо в драйверах из различных соображений, в том числе с позиций эффективности. Функции, показанные в табл. 2, обычно реализуются в независимом от устройств программном обеспечении. В MINIX большая часть таких программ является составляющей файловой системы. Здесь дадим только краткий обзор, чтобы продемонстрировать некоторые перспективы и лучше объяснить, как работают драйверы.
Таблица 2. Функции независимого от устройств программного обеспечени

Единообразный интерфейс для драйверов устройств
Именование устройств
Защита устройств
Обеспечение аппаратно-независимого размера блока
Буферизация
Сообщение об ошибках
Выделение места на блочных устройствах
Захват и освобождение выделенных устройств
Обработка ошибок

Основная задача независимого от устройств программного обеспечения заключается в выполнении функций ввода/вывода, общих для всех устройств, и предоставлении единообразного интерфейса для программ уровня пользователя.
Одна из основных задач операционной системы состоит в том, чтобы дать имена таким объектам, как файлы и устройства ввода/вывода. Отображением символических имен устройств на соответствующие драйверы занимаются аппаратно-независимые программы. Например, в UNIX имя устройства /dev/disk0 однозначно указывает i-узел специального файла, а подходящий драйвер определяется по главному номеру устройства. Этот i-узел также содержит младший номер устройства, передаваемый в виде параметра драйверу для указания конкретного диска или раздела диска, к которому относится операция чтения или записи. Все устройства в системе UNIX имеют главный и второстепенный номера, по которым они однозначно идентифицируются. Выбор всех драйверов осуществляется по главному номеру устройства.
С именованием устройств тесно связан вопрос защиты. Как операционная система предотвращает доступ пользователей к устройствам, на который у них нет прав? В UNIX и в Windows 2000 устройства представляются в файловой системе в виде именованных объектов, что дает возможность применять обычные правила защиты файлов к устройствам ввода/вывода. Таким образом, системному администратору легко установить нужные разрешения для каждого устройства.
У различных дисков могут быть разные размеры сектора. Независимое от устройств программное обеспечение должно скрывать этот факт от верхних уровней и предоставлять им единообразный размер блока, например, объединяя несколько физических сегментов в одну логическую сущность. При этом более высокие уровни имеют дело только с абстрактными устройствами, с одним и тем же размером логического блока, не зависящим от размера физического сектора. Некоторые символьные устройства предоставляют свои данные побайтово (например, модемы), тогда как другие выдают их большими порциями (сетевые интерфейсы). Эти различия также могут быть скрыты.
Буферизация также является важным вопросом как для блочных, так и для символьных устройств по самым разным причинам. Для блочных устройств аппаратное обеспечение обычно требует того, чтобы чтение или запись производились большими блоками. Но для пользовательских программ такого ограничения нет, и они вправе передавать любые объемы информации. Поэтому, если пользователь передал только половину блока, операционная система обычно не станет сразу записывать эти данные на диск, а дождется того, когда будет передана оставшаяся часть блока. Что касается символьных устройств, то пользователь может передавать данные быстрее, чем устройство в состоянии их воспринять, таким образом, также необходима буферизация. Не исключено также, что данные, например, от клавиатуры, могут опережать свое считывание, и в этом случае также не обойтись без буфера.
Когда файл создается и заполняется данными, необходимо выделять для него новые блоки на диске. Для этого операционной системе нужен список или карта свободных блоков на диске. Алгоритм обнаружении свободных блоков является аппаратно-независимым и перемещаем с уровня драйвера на более высокий уровень.
Некоторые устройства, например привод CD-RW выделенное устройство ввода/вывода, рассчитаны на монопольное владение в каждый момент времени. Операционная система должна рассмотреть запросы на использование такого устройства и либо принять их, либо отказать в выполнении запроса, в зависимости от доступности запрашиваемого устройства. Простой способ обработки этих запросов заключается в соответствующей реализации системного вызова open по отношению к специальным файлам. Если устройство недоступно, вызов open завершится неуспешно. Обращение к системному вызову close освобождает устройство.
Обработка ошибок, по большей части, производится драйвером. сообщения об ошибках. Многие ошибки являются специфичными для конкретного устройства и должны обрабатываться соответствующей программой, так как только она знает, что делать (например, повторить попытку, игнорировать ошибку или инициировать сбой системы). Типичная ошибка, когда блок на диске поврежден или не может быть прочитан. Драйвер диска пытается несколько раз повторить чтение и, если оно не удается, информирует вышестоящую программу. С этого момента обработка ошибки является аппаратно-независимой. Если ошибка имела место при чтении пользовательского файла, достаточно просто передать сообщение программе, сделавшей вызов. Если же невозможно причитать критическую системную структуру, не исключено, что системе придется вывести информацию об ошибке и завершить свою работу.
Программное обеспечение ввода/вывода пространства пользователя
Хотя большая часть программного обеспечения ввода/вывода пространства пользователя находится в операционной системе, небольшие его порции состоят из библиотек, присоединенных к программам пользователя, или даже целых программ, работающих вне ядра. Системные вызовы, включая системные вызовы ввода/вывода, обычно собраны из библиотечных процедур. Если программа на C содержит вызов
count = write(fd, buffer, nbytes);
библиотечная процедура write будет скомпонована с программой и, таким образом, будет содержаться в двоичном коде, загружаемом в память во время выполнения программы. Набор всех этих библиотечных процедур, несомненно, является частью системы ввода/вывода.
Хотя многие такие процедуры мало что делают, помимо обращения к системному вызову с соответствующими аргументами, есть ряд процедур ввода/вывода, производящих определенную работу. В частности, библиотечными процедурами выполняются операции форматного ввода и вывода. Например, процедура printf языка C, принимающая на входе текстовую строку и, возможно, несколько переменных, создает из нее ASCII-строку, после чего обращается к системному вызову write для непосредственного вывода. Примером сходной процедуры ввода служит scanf, читающая текстовую строку и преобразующая ее в значения переменных в соответствии с форматом, сходным с используемым процедурой printf. Стандартная библиотека ввода/вывода содержит большое количество процедур, включающих операции ввода/вывода и работающих как часть программы пользователя.
Не все программное обеспечение ввода/вывода пространства пользователя состоит из библиотечных процедур. Другая важная категория — это система спулинга. Спулинг (spooling — подкачка, предварительное накопление данных) представляет собой способ работы с выделенными устройствами в многозадачной системе. Рассмотрим типичное устройство, на котором используется подкачка: принтер. В принципе, можно разрешить каждому пользователю открывать специальный символьный файл принтера, однако представьте себе, что процесс открыл его, а затем не обращался к принтеру в течение нескольких часов. Ни один другой процесс в это время не сможет ничего напечатать.
Вместо этого создается специальный процесс, называемый демономдемон, и специальный каталог, называемый каталогом спулинга или каталогом спулера. Чтобы распечатать файл, процесс сначала создает специальный файл, предназначенный для печати, который помещает в каталог спулинга. Этот файл печатает демон, единственный процесс, которому разрешается пользоваться специальным файлом принтера. Таким образом, потенциальная пробка, связанная с тем, что какой-либо процесс на слишком долгий срок захватит принтер, решается при помощи защиты специального файла принтера от прямого доступа пользователей.
Спулинг используется не только для принтеров. Например, передачу файлов по сети также часто осуществляет специальный сетевой демон. Чтобы послать куда-либо файл, пользователь помещает его в каталог сетевого демона. Затем сетевой демон извлекает оттуда файл и посылает по сети. Подобный способ принят в системе сетевых новостей USENET. Эта сеть состоит из миллионов машин по всему миру, общающихся друг с другом по Интернету. Существуют тысячи конференций по самым разным темам. Чтобы послать новое сообщение, пользователь вызывает программу новостей, которая принимает сообщение, а затем помещает его в каталог спулинга для последующей отправки на другие машины. Вся система новостей работает вне операционной системы.
На рис. 4 показана структура системы ввода/вывода, со всеми уровнями и основными функциями каждого уровня. В порядке снизу вверх эти уровни представляют собой: аппаратуру, обработчики прерываний, независимое от устройств программное обеспечение и, наконец, процессы пользователя.

Рис. 4. Уровни и основные функции системы ввода/вывода
Стрелки на рис. 4 изображают поток управления. Например, когда программа пользователя пытается прочитать блок из файла, для обработки вызова запускается операционная система. Независимое от устройств программное обеспечение ищет этот блок в кэше. Если требуемого блока там нет, оно вызывает драйвер устройства, чтобы обратиться к аппаратуре и получить этот блок с диска. Процесс же блокируется до завершения дисковой операции.
Когда диск завершает операцию, аппаратура инициирует прерывание. Обработчик прерываний запускается с целью определить, что случилось, то есть какое устройство требует внимания. Затем он извлекает статус устройства и активизирует “спящий” процесс, чтобы завершить запрос ввода/вывода и предоставить пользовательскому процессу возможность продолжения работы.
Взаимоблокировка
В компьютерных системах существует большое количество ресурсов, каждый из которых в конкретный момент времени может использоваться только одним процессом. В качестве таких примеров можно привести принтеры, накопители на магнитной ленте и элементы внутренних таблиц системы. Появление двух процессов, одновременно передающих данные на принтер, приведет к печати бессмысленного набора символов. Наличие двух процессов, использующих один и тот же элемент таблицы файловой системы, обязательно станет причиной разрушения файловой структуры. Поэтому все операционные системы обладают способностью предоставлять процессу эксклюзивный доступ (по крайней мере, временный) к определенным ресурсам.
Часто прикладной процесс нуждается в исключительном доступе не к одному, а к нескольким ресурсам. Предположим, например, что каждый из двух процессов хочет записать отсканированный документ на компакт-диск. Процесс A запрашивает разрешение на использование сканера и получает его. Процесс B запрограммирован по-другому, поэтому сначала запрашивает устройство для записи компакт-дисков и также получает его. Затем процесс A обращается к устройству для записи компакт-дисков, но запрос отклоняется до тех пор, пока это устройство занято процессом B. К сожалению, вместо того чтобы освободить устройство для записи компакт-дисков, B запрашивает сканер. В этот момент процессы заблокированы и будут вечно оставаться в подвешенном состоянии. Такая ситуация называется тупиком или взаимоблокировкой.
Взаимоблокировки вероятны во множестве других ситуаций помимо запросов выделенных устройств ввода/вывода. В системах баз данных программа может оказаться вынужденной заблокировать несколько записей, чтобы избежать состояния конкуренции. Если процесс A блокирует запись R1, процесс B блокирует запись R2, а затем каждый процесс попытается заблокировать чужую запись, мы также окажемся в тупике. Таким образом, взаимоблокировки появляются при работе как с аппаратными, так и с программными ресурсами.
В этой главе мы рассмотрим тупиковые ситуации более подробно, увидим, как они возникают, и изучим некоторые способы, позволяющие предупредить взаимные блокировки или избежать их. Хотя информация о тупиках представлена в контексте операционной системы, они также могут встретиться в системах баз данных и во множестве других ситуаций, поэтому рассматриваемый материал на самом деле применим к широкому ряду систем, работающих с несколькими процессами. О взаимоблокировках было сложено много книг и статей. Несмотря на то что эти библиографии датируются давними цифрами, так как большая часть работ по взаимоблокировкам была проделана до 1980 года, данные книги полезны до сих пор.
Ресурсы
Система может зайти в тупик, когда процессам предоставляются исключительные права доступа к устройствам, файлам и т. д. Чтобы максимально обобщить рассказ о взаимоблокировках, мы будем называть объекты предоставления доступа ресурсами. Ресурсом может быть аппаратное устройство (например, накопитель на магнитной ленте) или часть информации (закрытая запись в базе данных). В компьютере существует масса различных ресурсов, к которым могут происходить обращения. Кроме того, в системе может оказаться несколько идентичных экземпляров какого-либо ресурса, например три накопителя на магнитных лентах. Если в системе есть несколько экземпляров ресурса, то в ответ на обращение к нему может предоставляться любая из доступных копий. Короче говоря, ресурс — это все то, что вправе использоваться только одним процессом в любой момент времени.
Ресурсы бывают двух типов: выгружаемые и невыгружаемые. Выгружаемый ресурс позволяет безболезненно забирать у владеющего им процесса. Образцом такого ресурса является память. Рассмотрим, например, систему с пользовательской памятью размером 512 Кбайт, одним принтером и двумя процессами по 512 Кбайт, каждый из которых хочет что-то напечатать. Процесс A запрашивает и получает принтер, затем начинает вычислять данные для печати. Еще не закончив расчеты, он превышает свой квант времени и выгружается на диск в область подкачки.
Теперь работает процесс B и безуспешно пытается обратиться к принтеру. В данный момент мы получили потенциальную тупиковую ситуацию, поскольку процесс A оккупирует принтер, а процесс B занимает память, и ни один из них не может продолжать работу без ресурса, удерживаемого другим. К счастью, не запрещено выгрузить (забрать) память у процесса B, переместив его на диск в область подкачки и загрузив с диска в память процесс A. Теперь процесс A может закончить вычисления, выполнить печать и затем освободить принтер. Взаимоблокировки не происходит.
Невыгружаемый ресурс, в противоположность выгружаемому, — это такой ресурс, который нельзя забрать от текущего владельца, не уничтожив результаты вычислений. Если в момент записи компакт-диска внезапно отнять у процесса устройство для записи и передать его другому процессу, то в результате мы получим испорченный компакт-диск. Устройство для записи компакт-дисков не является выгружаемым в произвольный момент времени ресурсом.
Вообще говоря, взаимоблокировки касаются невыгружаемых ресурсов. Потенциальные тупиковые ситуации, в которые вовлечен противоположный вид ресурсов, обычно разрешаемы с помощью перераспределения ресурсов от одного процесса к другому. Поэтому мы сконцентрируем свое внимание на невыгружаемых ресурсах.
Последовательность событий, необходимых для использования ресурса, представлена ниже в абстрактной форме.
1. Запрос ресурса.
2. Использование ресурса.
3. Возврат ресурса.
Если ресурс недоступен, запрашивающий его процесс вынужден ждать. В некоторых операционных системах при неудачном обращении к ресурсу процесс автоматически блокируется и возобновляется только после того, как ресурс становится доступным. В других системах запрос ресурса, получивший отказ, возвращает код ошибки, тогда вызывающий процесс может подождать немного и повторить попытку.
Понятие взаимной блокировки
Определение взаимоблокировки формально можно озвучить так:
Группа процессов находится в тупиковой ситуации, если каждый процесс из группы ожидает события, которое может вызвать только другой процесс из той же группы.
Так как все процессы находятся в состоянии ожидания, ни один из них не будет причиной какого-либо события, которое могло бы активизировать любой другой процесс в группе, и все процессы продолжают ждать до бесконечности. В этой модели мы предполагаем, что процессы имеют только один поток управления и что нет прерываний, способных активизировать заблокированный процесс. Условие отсутствия прерываний необходимо, чтобы предотвратить ситуацию, когда тот или иной заблокированный процесс активизируется, скажем, по сигналу тревоги и затем приводит к событию, которое освободит другие процессы в группе.
В большинстве случаев событием, которого ждет каждый процесс, является возврат какого-либо ресурса, в данный момент занятого другим процессом группы. Другими словами, каждый участник в группе процессов, зашедших в тупик, ожидает доступа к ресурсу, принадлежащему заблокированному процессу. Ни один из процессов не может работать, ни один из них не может освободить какой-либо ресурс и ни один из них не может возобновиться. Количество процессов и количество и вид ресурсов, имеющихся и запрашиваемых, здесь не важны. Результат остается тем же самым для любого вида ресурсов, аппаратных и программных.
Условия взаимоблокировки
Коффман (Coffman et al.) [70] и другие исследователи доказали, что для возникновения ситуации взаимоблокировки должны выполняться четыре условия.
1. Условие взаимного исключения. Каждый ресурс в данный момент или отдан ровно одному процессу, или доступен.
2. Условие удержания и ожидания. Процессы, в данный момент удерживающие полученные ранее ресурсы, вправе запрашивать новые ресурсы.
3. Условие отсутствия принудительной выгрузки ресурса. У процесса нельзя принудительным образом забрать ранее полученные ресурсы. Процесс, владеющий ими, должен сам освободить ресурсы.
4. Условие циклического ожидания. Должна существовать круговая последовательность из двух и более процессов, каждый из которых ждет доступа к ресурсу, удерживаемому следующим членом последовательности.
Для того чтобы произошла взаимоблокировка, должны выполниться все эти четыре условия. Если хоть одно из них отсутствует, тупиковая ситуация невозможна.
Моделирование взаимоблокировок
В [44] Холт (Holt) показал, как можно смоделировать четыре условия возникновения тупиков, используя направленные графы. Графы имеют два вида узлов: процессы, показанные кружочками, и ресурсы, нарисованные квадратиками. Ребро, направленное от узла ресурса (квадрат) к узлу процесса (круг), означает, что ресурс ранее был запрошен процессом, получен и в данный момент используется этим процессом. На рис. 5, а ресурс R в настоящее время отдан процессу A.
Ребро, направленное от процесса к ресурсу, означает, что процесс в данный момент блокирован и находится в состоянии ожидания доступа к этому ресурсу. На рис. 5, б процесс B ждет ресурс S. На рис. 5, в мы видим взаимоблокировку: процесс C ожидает ресурс T, удерживаемый в настоящее время процессом D. Процесс D вовсе не намеревается освобождать ресурс T, потому что он ждет ресурс U, используемый процессом C. Оба процесса будут ждать до бесконечности. Цикл в графе означает наличие взаимоблокировки, циклично включающей процессы и ресурсы (предполагается, что в системе есть по одному ресурсу каждого вида). В этом примере циклом является последовательность C-T-D-U-C.

Рис. 5. Графы распределения ресурсов: а — ресурс занят; б — запрос ресурса;
в — взаимоблокировка
Теперь рассмотрим пример того, как извлечь пользу из графов ресурсов. Представим, что у нас есть три процесса: A, B и C, и три ресурса: R, S и T. Последовательность запросов и возвратов ресурсов для трех процессов показана на рис. 6, а–в. Операционная система может запустить любой незаблокированный процесс в любой момент времени, значит, таковым может оказаться процесс A. Процесс A будет выполняться до тех пор, пока не закончит всю свою работу, затем будет запущен процесс B до его завершения и, наконец, процесс C.
Такой порядок не приводит к взаимоблокировке (не возникает соперничества за использование ресурсов), но здесь также по сути нет параллельной работы. Кроме запросов и возвратов ресурсов, процессы выполняют вычисления и ввод/вывод данных. Когда процессы работают последовательно, нереальна ситуация, при которой один процесс использует процессор, в то время как другой ждет завершения операции ввода/вывода. Таким образом, строго последовательная работа процессов не бывает оптимальной. С другой стороны, если вообще ни один процесс не выполняет операций ввода/вывода, алгоритм “кратчайшая задача — первая” работает эффективнее, чем циклический, поэтому в некоторой обстановке последовательный запуск всех процессов может быть наилучшим.
Теперь предположим, что процессы выполняют как расчеты, так и ввод/вывод, соответственно циклический алгоритм планирования является рациональным. Запросы ресурсов могут происходить в порядке, указанном на рис. 6, г. Если эти шесть запросов будут осуществлены в такой последовательности, в результате мы получим шесть графов, показанных на рис. 6, д–к. После запроса 4 процесс A блокируется в ожидании ресурса S (см. рис. 6, з). На двух следующих шагах также блокируются процессы B и C, в конечном счете приводя к циклу и взаимоблокировке на рис. 6, к.
Однако, как мы упоминали ранее, операционная система не обязана запускать процессы в каком-то особом порядке. В частности, если выполнение отдельного запроса приводит в тупик, операционная система вправе просто приостановить процесс без удовлетворения запроса (то есть не выполняя план процесса) до тех пор, пока это безопасно. На рис. 3.6 операционная система могла бы приостановить процесс B вместо того, чтобы отдавать ему ресурс S, если бы она знала о предстоящей взаимоблокировке. Работая только с процессами A и C, мы могли бы получить порядок запросов ресурсов и их возвратов, продемонстрированный на рис. 6, л, вместо показанного на рис. 6, г. Такая последовательность действий отражена графами на рис. 6, м–с, и она не приводит к тупику.
После шага с процесс B может получить ресурс S, потому что процесс A уже закончил свою работу, а процесс C имеет в своем распоряжении все необходимые ему ресурсы. Даже если затем процесс B, когда он запросит ресурс T, будет заблокирован, система не повиснет. Процесс B всего лишь будет ждать завершения работы процесса C.
Позже в этой главе мы изучим подробный алгоритм для принятия решений о распределении ресурсов, которые не приведут к взаимоблокировке. В данный момент важно понять, что графы ресурсов являются инструментом, позволяющим нам увидеть, станет ли заданная последовательность запросов/возвратов ресурсов причиной тупиковой ситуации. Мы всего лишь шаг за шагом осуществляем запросы и возвраты ресурсов и после каждого шага проверяем граф на содержание циклов. Если они есть, мы зашли в тупик; если нет, значит, взаимоблокировки тоже нет. Хотя мы рассматривали графы ресурсов для случая, когда в системе присутствует по одному ресурсу каждого типа, графы также можно построить для обработки ситуации с несколькими одинаковыми ресурсами [44]. Вообще говоря, при столкновении с взаимоблокировками практикуются четыре стратегии.
1. Пренебрежение проблемой в целом. Если вы проигнорируете проблему, возможно, затем она проигнорирует вас.
2. Обнаружение и восстановление. Позволить взаимоблокировке произойти, обнаружить ее и предпринять какие-либо действия.
3. Динамическое избежание тупиковых ситуаций с помощью аккуратного распределения ресурсов.
4. Предотвращение с помощью структурного опровержения одного из четырех условий, необходимых для взаимоблокировки.
Мы по очереди изучим каждый из этих методов в следующих четырех разделах.

Рис. 6. Пример возникновения взаимоблокировки и способы избежать ее
Страусовый алгоритм
Самым простым подходом является “страусовый алгоритм”: воткните голову в песок и притворитесь, что проблемы вообще не существует. Различные люди отзываются об этой стратегии по-разному. Математики считают ее полностью неприемлемой и говорят, что взаимоблокировки нужно предотвращать любой ценой. Инженеры спрашивают, как часто встает подобная проблема, как часто система попадает в аварийные ситуации по другим причинам и насколько серьезны последствия взаимоблокировок. Если взаимоблокировки случаются в среднем один раз в пять лет, а сбои операционной системы, ошибки компилятора и поломки компьютера из-за неисправности аппаратуры происходят раз в неделю, то большинство инженеров не захотят добровольно уступать в производительности и удобстве для того, чтобы ликвидировать возможность взаимоблокировок.
Для усиления контраста между этими подходами добавим что большинство операционных систем потенциально страдают от взаимоблокировок, которые даже не обнаруживаются, не говоря уже об автоматическом выходе из тупика. Суммарное количество процессов в системе определяется количеством записей в таблице процесса. Таким образом, ячейки таблицы процесса являются ограниченным ресурсом. Если системный вызов fork получает отказ, в силу того что таблица целиком заполнена, разумно будет, что программа, вызывающая fork, подождет какое-то время и повторит попытку.
Теперь предположим, что система UNIX имеет 100 ячеек процессов. Работают десять программ, каждой необходимо создать 12 (под)процессов. После образования каждым процессом девяти процессов 10 исходных и 90 новых процессов заполнят таблицу до конца. Теперь каждый из десяти исходных процессов попадает в бесконечный цикл, состоящий из попыток разветвления и отказов, то есть возникает взаимоблокировка. Вероятность того, что произойдет подобное, минимальна, но это могло бы случиться. Должны ли мы отказаться от процессов и вызова fork, чтобы устранить данную проблему?
Максимальное количество открытых файлов также ограниченно размером таблицы i-узлов, следовательно, когда таблица заполняется целиком, возникает та же самая проблема. Пространство для подкачки файлов на диск является еще одним ограниченным ресурсом. Фактически почти каждая таблица в операционной системе представляет собой ресурс, имеющий пределы. Должны ли мы упразднить их все из-за того, что теоретически ожидаема ситуация, когда в группе из n процессов каждый может потребовать 1/n от целого, а затем попытаться получить еще часть?
Большая часть операционных систем, включая UNIX и Windows, игнорируют эту проблему. Они исходят из предположения, что большинство пользователей скорее предпочтут иметь дело со случающимися время от времени взаимоблокировками, чем с правилом, по которому всем пользователям разрешается только один процесс, один открытый файл и т. д. Если бы можно было легко устранить взаимоблокировки, не возникло бы столько разговоров на эту тему. Сложность заключается в том, что цена достаточно высока, и в основном она, как мы вскоре увидим, исчисляется в наложении неудобных ограничений на процессы. Таким образом, мы столкнулись с неприятным выбором между удобством и корректностью и множеством дискуссий о том, что более важно и для кого. При всех этих условиях трудно найти верное решение.
Обнаружение и устранение взаимоблокировок
Вторая техника представляет собой обнаружение взаимоблокировки и восстановление. Здесь система не пытается предотвратить попадание в тупиковые ситуации. Каждый раз, когда запрашивается или освобождается новый ресурс, то есть когда обновляется граф ресурсов, система проверяет, имеются ли в нем циклы. Если цикл есть, один из входящих в него процессов принудительно завершается. Это повторяется до тех пор, пока взаимная блокировка не будет устранена.
Более грубый метод не анализирует граф ресурсов, а просто проверяет наличие процессов, которые были заблокированы долго, скажем, в течение одного часа. Если такие процессы обнаруживаются, они завершаются.
Стратегия обнаружения и восстановления применяется в больших компьютерных системах, особенно в системах пакетной обработки, где принудительное завершение и повторный запуск обычно приемлемы. Тем не менее необходимо с осторожностью производить восстановление любых модифицированных файлов и устранение любых побочных эффектов, которые могли произойти.
Предотвращение взаимоблокировок
Как мы видели, уклонение от взаимоблокировок, в сущности, невозможно, так как оно требует наличия никому не известной информации о будущих процессах. Тогда возникает справедливый вопрос: как же реальные системы избегают попадания в тупики? Для того чтобы ответить на этот вопрос, вернемся назад к четырем условиям, сформулированным в [11] (см. раздел “Условия взаимоблокировки” данной главы), и посмотрим, дадут ли они нам ключ к разрешению проблемы. Если мы сумеем гарантировать, что хотя бы одно из этих условий никогда не будет выполнено, тогда взаимоблокировки станут конструктивно невозможными [41].
Сначала попробуем атаковать условие взаимного исключения. Если в системе нет ресурсов, отданных в единоличное пользование одному процессу, мы никогда не попадем в тупик. Но в равной степени понятно, что если позволить двум процессам одновременно печатать данные на принтере, воцарится хаос. Используя подкачку выходных данных для печати, несколько процессов могут одновременно генерировать свои выходные данные. В такой модели только один процесс, который фактически запрашивает физический принтер, является демоном принтера. Так как демон не запрашивает никакие другие ресурсы, для принтера тупики исключаются.
К сожалению, не все устройства поддерживают подкачку (свопинг) данных (таблица процессов — дело резидентное). Кроме того, конкуренция за дисковое пространство для подкачки сама по себе чревата тупиком. Что получится, если два процесса заполнили своими выходными данными каждый по половине диска, отведенного под свопинг, и ни один из них не закончил вычисления? Демон может быть запрограммирован так, что начнет печать, не дожидаясь подкачки всех выходных данных, и принтер тогда простоит впустую в том случае, если вычисляющий процесс решил подождать несколько часов после первого пакета выходных данных. По этой причине обычно демоны программируют так, что они начинают печать только после того, как файл выходных данных целиком станет доступен. В этом же случае мы получаем два процесса, каждый из которых обработал часть выходных данных, но не все и не в состоянии продолжать вычисления дальше. Ни один из двух процессов никогда не завершится, то есть имеет место взаимоблокировка на диске.

Дата добавления: 2014-10-15