\section{Вызов функций драйвера}

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

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

Системный вызов включает в себя переключение
контекста между пользовательской программой и ядром. В системах с виртуальной
памятью во время такого переключения процессор переходит из 
<<пользовательского>> режима, в котором запрещены или ограничены доступ к 
регистрам диспетчера памяти, операции ввода/вывода и ряд других действий, в 
<<системный>>, в котором все ограничения снимаются. Обычно системные вызовы
реализуются с использованием специальных команд процессора, чаще всего --
команды программного прерывания.

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

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

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

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

{\small
Например, в \machname{VAX} пользовательские адреса целиком отображаются в
системное адресное пространство. При этом пользовательская программа может
использовать только первые два гигабайта из четырех, которые можно
адресовать 32-битовым адресом. Вторые два гигабайта зарезервированы для 
системы. Исполняя системный вызов, ядро отображает в свое адресное 
пространство всю память программы, сделавшей вызов, и, таким образом, 
получает прямой доступ ко всем пользовательским данным. Подробнее изучить 
архитектуру виртуальной памяти системы \sysname{VAX} можно по работам
\cite{VAX2, VAX1}.
}

Обработку запроса можно разделить на три фазы: предобработки, собственно 
исполнения запроса и постобработки. Пользовательская программа запрашивает 
операцию, исполняя соответствующий системный вызов. В ОС семейства
\sysname{Unix} это будет системный вызов
\verb"read(int file, void * buffer, size_t size)".

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

Фаза предобработки включает:
\begin{itemize}

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

\item возможно, копирование или отображение данных из
пользовательского адресного пространства в системное.

\item возможно, преобразование выводимых данных.
Например, в системах семейства \sysname{Unix} при выводе на терминал система
может заменять символ горизонтальной табуляции на соответствующее число пробелов
(если терминал не поддерживает горизонтальную табуляцию)
и преобразовывать символ перевода строки. Дело в том, что внутри системы
в качестве разделителя строк используется символ новой строки \verb"'\n'"
(ASCII NL), а различные модели терминалов и принтеров могут использовать
также \verb"'\r'" (ASCII RET, возврат каретки) или последовательности
\verb"'\r>>\n'" или \verb"'\n>>\r'";

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

\item Передача запроса драйверу.
Некоторые системы реализуют передачу запроса как простой вызов
соответствующей функции драйвера, но чаще используются более сложные
асинхронные механизмы, которые будут обсуждаться ниже. 
\end{itemize}

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

Некоторые системы на этой фазе также делают преобразование введенных
данных. В качестве примера можно вновь привести системы семейства
\sysname{Unix}, которые при вводе с терминала выполняют трансляцию
символа перевода строки и ряд других операций по редактированию,
например, стирание последнего введенного символа по запросу пользователя.
Разбиение потока терминальных данных на строки в этих системах
также происходит на фазе постобработки.

В той или иной форме эти три фазы обработки запроса ввода/вывода
присутствуют во всех многопроцессных системах.

Сейчас нас интересует гораздо более простой, на первый взгляд, вопрос:
каким образом процедура предобработки обращается к драйверу?
И каким образом драйвер потом передает результат исполнения запроса
процедуре постобработки? Ответ на эти вопросы далеко не так прост.

\subsection[Синхронный ввод/вывод в однозадачных системах]
{Синхронный ввод/вывод\\в однозадачных системах}

Самым простым механизмом вызова функций драйвера был бы косвенный
вызов соответствующих процедур, составляющих тело драйвера, подобно
тому, как это делается в \sysname{MS~DOS}.

Например, программа, желающая прочитать строку с клавиатуры,
вызывает  функцию \verb"read" драйвера консоли.
Функция \verb"read" анализирует состояние клавиатуры;
если была нажата клавиша, запоминает ее код в буфере;
при нажатии клавиши <<конец ввода>> или заполнении буфера
функция возвращает управление программе.
Такой метод очень прост в реализации, но, как показывает более
внимательный взгляд на проблему, совершенно неадекватен, даже для
однопрограммных однопользовательских систем.

{\small
Справедливости ради следует отметить, что даже \sysname{MS~DOS}
использует описанный метод для обмена с блочными устройствами
(да и то если не загружен дисковый кэш), но клавиатуру обрабатывает
более разумным методом с использованием \term{прерываний}.
}

Начнем с того, что пользователь может нажимать клавиши в любой момент,
а не только когда программа попросила его что-то ввести.
Например, многие пользователи командных интерпретаторов любят режим
\term{type ahead} (дословно переводится как \term{печать вперед}),
когда система исполняет одну команду, а пользователь набирает следующую,
не дожидаясь приглашения. Понятно, что реализовать такой режим путем опроса
клавиатуры невозможно.

Дочитав до этого места, средний досовский хакер должен воскликнуть:
<<Но какой же [подставьте ваше любимое ругательство] будет опрашивать
клавиатуру? Ведь для этого и придуманы прерывания!>>

Действительно, прерывания помогают реализовать режим type ahead
и решить много других проблем. Например, если клавиатура генерирует
прерывание при каждом нажатии на клавишу, мы можем реализовать
драйвер клавиатуры следующим образом:

\begin{example}\label{kbd_driver1}
\small\begin{verbatim}

// Пример драйвера клавиатуры.
// (C) Дмитрий Иртегов, 1995.

char buffer[1024];
int last_char, first_char;
int count; // Счетчик символов в буфере

// Эта функция считывает код нажатой клавиши
// из физического порта клавиатуры.
extern char get_char();

interrupt keyboard_handler() {
  // Считать код нажатой клавиши
  // и поместить его в кольцевой буфер.
  if (last_char == first_char) return;
  buffer[last_char] = get_char();
  last_char = (last_char+1) & 1023;
  count++;
}

void init_driver() {
  set_interrupt_handler(KEYBOARD, keyboard_handler);
  last_char = 0;
  first_char = 1023;
  count = 0;
}

int read(char * where, int how_much) {
  // Копирует содержимое буфера куда скажут.
  // Возвращает количество скопированных символов
  // и сбрасывает счетчик
  int i = how_much;
  int tmp;

  disable_interrupts();

  if (i < count) i = count;
  // Мы не можем считать больше символов, чем есть в буфере
  tmp = i;
  for (; i; i--) {
    *where = buffer[first_char];
    first_char = (first_char+1) & 1023;
    count--;
  }
  enable_interrupts();
  return tmp;
}

int write(char * what, int how_much) {
  return -1;
  // Не умеем записывать данные в клавиатуру.
}
\end{verbatim}
\end{example}

Программа \ref{kbd_driver1} максимально упрощена.
Например, функция чтения возвращает все, что накопилось в буфере
к моменту вызова, тогда как <<настоящие>> драйверы терминала обычно
осуществляют ввод по строкам, и т.д.

Тем не менее программа \ref{kbd_driver1} иллюстрирует основную идею
программ такого рода:
\begin{itemize}
\item накапливать вводимые данные в буфере по мере их поступления,
\item отдавать содержимое буфера прикладной программе, когда она попросит
\end{itemize}

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

Казалось бы, теперь все хорошо.
Но при более внимательном рассмотрении мы обнаруживаем вторую проблему.

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

Если читатель внимательно читал всю книгу, на этом месте он должен сказать:
<<Но мы это уже проходили!>>.
Действительно, подобная ситуация рассматривалась в разделе \ref{interrupts},
и там было показано, что проверка флага или другого условия, устанавливаемого
обработчиком прерывания, с блокировкой при невыполнении условия, создает
неприятные проблемы.

В однопроцессной системе мы можем позволить себе роскошь циклически
опрашивать значение счетчика байтов, накопленных в буфере. Это снимает
проблему, с которой мы столкнулись в примере \ref{signal1}, но само по
себе превращается в проблему, когда мы переходим в многопроцессную среду.

{\small
Такие проблемы, например, возникают при исполнении программ
для \sysname{MS~DOS} в DOS-эмуляторе \sysname{OS/2} или под управлением
\sysname{DesqView}. Обе эти системы вынуждены использовать нетривиальные
алгоритмы для выявления программ, циклически опрашивающих клавиатуру
или последовательный порт, потому что такие программы сильно и плохо
влияют на поведение всей системы.
Для призвания к порядку программ, не выявляемых такими алгоритмами,
существует специальная утилита с характерным названием \progname{tame} --
<<приручить>>, использующая еще более изощренные методы. Обсуждение этих
методов увело бы нас далеко от основной темы.
}

Даже если мы будем использовать для синхронизации что-то типа семафора,
останется очень серьезная трудность: функция \verb"read" вызывается из
ядра системы, поэтому, заблокировав эту функцию, мы заблокируем ядро, что
совершенно недопустимо в многопроцессной системе.

Еще хуже ситуация с запоминающими устройствами типа лент или дисководов.
При чтении данных драйвер такого устройства должен:
\begin{itemize}
\item если речь идет о дискете, то включить мотор дисковода и дождаться,
пока диск разгонится до рабочей скорости.
\item дать устройству команду на перемещение считывающей головки.
\item дождаться прерывания по концу операции перемещения.
\item запрограммировать ПДП и инициировать операцию чтения.
\item дождаться прерывания, сигнализирующего о конце  операции чтения.
\end{itemize}
Лишь после этого можно будет передать данные программе.
В обоих промежутках между инициацией запроса и окончанием операции
драйвер должен отдавать управление системе, иначе обращения к дисководу
будут надолго блокировать все остальные процессы в системе.

{\small Например, \sysname{Windows 3.x} в \verb'enhanced' режиме предоставляет
вытесняющую многозадачность для
\termint{VDM}{Virtual DOS Machine}{Виртуальная машина [для] \sysname{DOS}},
однако сама \sysname{Windows 3.x} использует \sysname{DOS} для обращения к
дискам и дискетам. Ядро однозадачной \sysname{DOS} не умеет отдавать
управление другим процессам во время исполнения запросов ввода/вывода.  В
результате во время обращения к диску все остальные задачи оказываются
заблокированы. У современных \machname{PC} время исполнения операций над
жестким диском измеряется десятыми долями секунды, поэтому фоновые обращения
к жесткому диску почти не приводят к нарушениям работы остальных программ.
Однако скорость работы гибких дисков осталась достаточно низкой, поэтому
работа с ними в фоновом режиме блокирует систему на очень заметные промежутки
времени.

Эффектная и убедительная демонстрация этой проблемы очень проста: достаточно
запустить в фоновом режиме форматирование дискеты или просто команду
\verb'COPY C:\TMP\*.* A:', если в директории \verb'C:\TMP' достаточно много
данных. При этом работать с системой будет практически невозможно: во время
обращений к дискете даже мышиный курсор не будет отслеживать движений мыши,
будут теряться нажатия на клавиши и т.д.

\sysname{Windows 95} использует несколько методов обхода \sysname{DOS}
при обращениях к диску, поэтому пользователи этой системы не всегда
сталкиваются с описанной проблемой. Однако при использовании блочных
драйверов реального режима система по прежнему использует \sysname{DOS}
в качестве подсистемы ввода/вывода и работа с дискетами в фоновых задачах
также нарушает работу задач первого плана.
}

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

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

{В качестве примера такого консерватизма можно привести подсистему
ввода/вывода \sysname{OS/2}. Совместный проект фирм \entname{IBM}
и \entname{Microsoft}, \sysname{OS/2 1.x} разрабатывалась как
операционная система для семейства персональных компьютеров
\machname{Personal System/2}. Младшие модели семейства были основаны на
16-разрядном процессоре \sysname{80286}, поэтому вся ОС была полностью
16-битной.

Позднее разработчики фирмы \entname{IBM} реализовали
32-битную \sysname{OS/2 2.0}, но для совместимости со старыми драйверами
им пришлось сохранить 16-битную подсистему ввода/вывода. Все точки
входа драйверов должны находиться в 16-битных (\verb|`USE16'|) сегментах
кода; драйверам передаются только 16-разрядные {\verb|`far'|) указатели
и т.д. По утверждению фирмы \entname{IBM}, они рассматривали возможность
реализации также и 32-битных драйверов, но их измерения не показали
значительного повышения производительности при переходе к 32-битной
модели.

Так или иначе, \sysname{OS/2 2.x} и последующие версии системы
по-прежнему используют 16-битные драйверы последовательных, блочных,
координатных и сетевых устройств. Ряд ключевых модулей ядра в этих
системах по прежнему использует 16-битный код. Благодаря этому сохраняется
возможность использовать драйверы, разработанные еще в конце 80-х
и рассчитанные на \sysname{OS/2 1.x}. Эта возможность оказывается
особенно полезна при работе со старым оборудованием.

Напротив, разработчики фирмы \entname{Microsoft} отказались от
совместимости с 16-битными драйверами \sysname{OS/2 1.x} в создававшейся
ими 32-битной версии \sysname{OS/2}, называвшейся 
\sysname{OS/2 New Technology}. Фольклор утверждает, что именно
это техническое решение оказалось причиной разрыва партнерских отношений
между \entname{Microsoft} и \entname{IBM}, в результате которого
\sysname{OS/2 NT} вышла на рынок под названием \sysname{Windows NT 3.1}.

Трудно сказать, было ли это решение оправданным. За чисто 32-битное ядро 
пришлось расплачиваться потерей совместимости со старыми драйверами и 
резким сужением набора поддерживаемых внешних устройств, а наблюдаемых 
технических преимуществ чистая 32-битность не дала. Во всяком случае, 
по производительности и потребляемым ресурсам \sysname{Windows NT} 
значительно уступает 32-разрядным версиям \sysname{OS/2}.
}

Фактически, совместимость со старыми драйверами часто оказывается
по важности сопоставима с совместимостью со старыми приложениями.
Отказ от такой совместимости на практике означает <<брошенное>>
периферийное оборудование и, как следствие, <<брошенных>> пользователей,
которые оказываются вынуждены либо отказываться от установки новой
системы, либо заменять оборудование. Оба варианта, естественно, не
улучшают отношения пользователей к поставщику ОС, поэтому многие
поставщики просто не могут позволить себе переделку подсистемы
ввода/вывода.

Именно из-за этого, например, фирма
\entname{Apple} до сих пор не может реализовать вытесняющую
многозадачность в \sysname{MacOS}. По этой же причине фирма
\sysname{Microsoft} так долго держалась за кооперативную многозадачность
в различных вериях \sysname{MS Windows} и даже в \sysname{Windows 95} им
не удалось полностью преодолеть наследие однозадачной \sysname{DOS}.

Однако нужно отметить, что ряд однозадачных ОС, например
\sysname{RT-11SJ} фирмы \entname{DEC}, использует реентерабельную
подсистему ввода/вывода, пригодную для реализации вытесняющей
многозадачности. Такое проектирование <<на вырост>> представляется
очень удачной технической политикой, так как упрощает разработчикам
и пользователям переход к более мощным версиям системы.

\subsection[Синхронный ввод/вывод в многозадачных системах]
{Синхронный ввод/вывод\\ в многозадачных системах}

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

В <<классических>> версиях \sysname{Unix} и некоторых других
системах этого семейства, например в \sysname{Linux}, драйвер
последовательного устройства исполняется в рамках того процесса, который
издал запрос, хотя и с привилегиями ядра. Ожидая реакции устройства,
драйвер переводит процесс в состояние ожидания и вызывает функцию
ядра
\verb"schedule()". Эта функция аналогична обсуждавшейся в п.
\ref{ProcessSwitch} функции переключения процессов: она передает
управление первому активному процессу, стоящему в очереди с наивысшим
приоритетом. Она возвращает управление только тогда, когда до процесса
вновь дойдет очередь. Когда устройство генерирует прерывание, оповещающее
о завершении операции, обработчик прерывания выводит процесс из состояния
ожидания. Для перевода процесса в состояние ожидания и обратно используются
реентерабельные сервисы ядра.

Ниже приводится скелет функции \verb"write()" драйвера последовательного
устройства в системе \sysname{Linux}. Текст цитируется по
документу \cite{khg}.

\begin{example}\label{Linux_driver}
\par\small\begin{verbatim}

static int foo_write(struct inode * inode, struct file * file,
                     char * buf, int count)
{
    unsigned int minor = MINOR(inode->i_rdev);
    unsigned long copy_size;
    unsigned long total_bytes_written = 0;
    unsigned long bytes_written;
    struct foo_struct *foo = &foo_table[minor];

    do {
        copy_size = (count <= FOO_BUFFER_SIZE ?
                                     count : FOO_BUFFER_SIZE);
        memcpy_fromfs(foo->foo_buffer, buf, copy_size);

        while (copy_size) {
        /* initiate interrupts */

            if (some_error_has_occured)  {
               /* handle error condition */
            }

            current->timeout = jiffies + FOO_INTERRUPT_TIMEOUT;
         /* set timeout in case an interrupt has been missed */
            interruptible_sleep_on(&foo->foo_wait_queue);
            bytes_written = foo->bytes_xfered;
            foo->bytes_written = 0;
            if (current->signal & ~current->blocked) {
                if (total_bytes_written + bytes_written)
                    return total_bytes_written + bytes_written;
                else
                  return -EINTR; /* nothing was written, system
                             call was interrupted, try again */
            }
        }

        total_bytes_written += bytes_written;
        buf += bytes_written;
        count -= bytes_written;

    } while (count > 0);

    return total_bytes_written;
}

static void foo_interrupt(int irq)
{
    struct foo_struct *foo = &foo_table[foo_irq[irq]];

 /* Here, do whatever actions ought to be taken on an interrupt.
    Look at a flag in foo_table to know whether you ought to be
    reading or writing. */

 /* Increment foo->bytes_xfered by however many characters were
    read or written */

    if (buffer too full/empty)
        wake_up_interruptible(&foo->foo_wait_queue);
}
\end{verbatim}\end{example}

Эта программа сложнее, чем приведенная в примере \ref{kbd_driver1}.
Например, предполагается, что драйвер \ref{Linux_driver} способен 
обслуживать несколько устройств.
Номер устройства, к которому сейчас осуществляется обращение, определяется
значением переменной \verb"minor", которая, в свою очередь, определяется
на основании содержания идентификационной записи устройства --
его \termin{инода}{i-node}. Указатель на инод передается первым
параметром.

Тем не менее, структуры программ \ref{kbd_driver1} и \ref{Linux_driver} 
очень близки. Основное отличие состоит в том, что в \ref{kbd_driver1}
мы обошли стороной проблему освобождения процессора на время
обработки запроса, пример же \ref{Linux_driver} показывает,
как эта проблема может быть решена, если ядро системы предоставляет
соответствующие сервисы.

Перечислим по порядку все сервисы ядра, к которым обращается драйвер.

\verb"memcpy_fromfs(char * dst, const char * src, size_t size)"
используется для передачи данных из пользовательского адресного
пространства в системное.
При этом \verb"src" -- это адрес в системном пространстве,
а \verb"dst" -- в пользовательском.
Устройство принимает по \verb"copy_size" символов за раз и генерирует
прерывание, когда оказывается готово принять следующий блок данных.
Знатоки архитектуры \machname{x86} могут догадаться, что селектор
пользовательского адресного пространства передается драйверу в регистре
\verb"FS".

\note{Драйвер копирует данные из пользовательского сегмента
в свой внутренний буфер. Это необходимо потому, что функция
{\tt memcpy\_fromfs} может приводить к возникновению страничных
отказов, обработка которых может занимать непредсказуемое время.
Поэтому {\tt memcpy\_fromfs} нельзя вызывать из обработчика прерывания.}

Использование внутреннего буфера приводит к увеличению ядра системы
и накладным расходам на копирование. Альтернативой такому
копированию могло бы служить динамическое отображение данных из
пользовательского адресного пространства в системное. При этом
данные нужно не только отображать, но и блокировать в физической
памяти, чтобы обработчик прерывания мог без опасения работать с
ними. Разработчики оригинальной системы \sysname{Unix}, а вслед за 
ними и Линус Торвальдс (разработчик \sysname{Linux}) сочли, что 
такое отображение чрезмерно усложнило бы механизм управления 
виртуальной памятью.

\verb"void interruptible_sleep_on(struct wait_queue ** p)"
устанавливает процесс в заданную очередь ожидания и вызывает \verb"schedule()".
Соответственно, эта функция возвращает управление только когда процесс
вернется в активное состояние.
Обратная ей функция\\
\verb"void wake_up_interruptible(struct wait_queue ** p)"
переводит первый процесс из очереди в активное состояние
и устанавливает  его  в  конец  активной очереди соответствующего
приоритета.

\note{Обратите внимание,  что  кроме  инициализации   устройства
драйвер перед засыпанием еще устанавливает <<будильник>> -- таймер,
который должен разбудить процесс через заданный интервал времени.
Это необходимо на случай, если произойдет аппаратная ошибка и устройство не
сгенерирует прерывания. Если бы такой будильник не устанавливался, драйвер
в случае ошибки мог бы заснуть навсегда, заблокировав при этом пользовательский
процесс.}

Еще одна особенность синхронных драйверов в ОС семейства \sysname{Unix}
состоит в том, что все операции ввода/вывода, а также все остальные операции,
переводящие процесс в состояние ожидания, могут быть прерваны
\term{сигналом}\footnote{Понятие сигнала кратко обсуждалось в
\ref{interrupts}.}. При этом системный вызов возвращает код ошибки
\verb'EINTR', говорящий о том, что вызов был прерван и, возможно, операцию
следует повторить.   Например, пользовательский процесс может использовать
сигнал \verb'SIGALARM' для того, чтобы установить свой собственный будильник,
сигнализирующий, что операция над устройством исполняется подозрительно
долго.

{\small\label{SCOHorrorStoryPart1}
Если драйвер не установит своего будильника и не станет отрабатывать сигналы,
посланные процессу, может возникнуть очень неприятная ситуация.  Дело в том,
что в \sysname{Unix} все сигналы, в том числе и сигнал безусловного убийства
\verb"SIGKILL", обрабатываются процедурой постобработки системного вызова.
Если драйвер не передает управления процедуре постобработки, то и сигнал,
соответственно, оказывается необработанным, поэтому процесс остается висеть.
Других средств, кроме посылки сигнала, для уничтожения процесса в системах
семейства \sysname{Unix} не предусмотрено. Поэтому процесс, зависший внутри
обращения к драйверу, оказывается невозможно прекратить ни изнутри, ни извне.
Один из авторов столкнулся с этим при эксплуатации многопроцессорной версии
системы \sysname{SCO Open Desktop 4.0}.

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

Из-за наличия неубиваемого процесса оказывалось невозможно выполнить
нормальное закрытие системы; в частности, оказывалось невозможно
размонтировать файловые системы, где зависший процесс имел открытые файлы.
Выполнение холодной перезагрузки системы с неразмонтированными файловыми
томами приводило к неприятным последствиям для этих томов. Одна из аварий, к
которым это привело, подробно описывается в разделе
\ref{SCOHorrorStoryPart2}.}

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

Синхронная модель драйвера очень проста в реализации, но имеет существенный
недостаток -- приведенный в примере \ref{Linux_driver} драйвер нереентерабелен.
Предполагается, что такой драйвер позволяет работать с устройством
только одному процессу, а на обращения со стороны остальных процессов
отвечает <<устройство занято>>. Такое поведение было бы разумным для
лентопротяжек или печатающих устройств, но неудобно для терминалов
и совершенно недопустимо для дисков. Поэтому даже в полностью монолитных
системах семейства \sysname{Unix}, таких как \sysname{Linux} и 
\sysname{FreeBSD}, драйверы блочных устройств используют асинхронную
модель (см. \ref{block_devices}), а синхронные драйверы терминалов 
гораздо сложнее примера \ref{Linux_driver}.

\subsection{Асинхронный ввод/вывод}\label{async_drv}

Иной подход используется в микроядерных системах:
в таких ОС <<синхронная>> часть драйвера выделяется в отдельный процесс,
взаимодействующий с остальной системой через операции \verb"send/receive".

Ниже приведен пример такого драйвера, написанный на псевдокоде.
Псевдокод представляет собой язык \progname{C}, расширенный аналогом
оператора \verb"select" языка \progname{Ada}.
Этот оператор позволяет ожидать данные одновременно из нескольких портов;
при приходе данных из какого-либо порта исполняется соответствующий код.
Синтаксис оператора аналогичен оператору \verb"switch()" языка \progname{C}.

Предполагается, что микроядро поддерживает следующие операции:

\verb"send(Port port, char * data, int data_size)":
  послать данные в порт.

\verb"receive(Port port, char * data, int data_size)":
  получить данные из порта. Если \verb"data == 0", данные игнорируются.

\verb"when(Port port, char * data, int data_size)":
  аналогично \verb"receive", но используется в операторе \verb"select"
  при ожидании данных из нескольких портов.

\begin{example}\label{ukernel_kbd_driver}
\small\begin{verbatim}

// Пример драйвера клавиатуры в микроядерной системе.
// (С) Дмитрий Иртегов 1995

// Порт для обмена данными с ядром ОС.
extern Port OS_port;

// Порт для синхронизации с обработчиком прерываний
static Port internal_port;

char buffer[1024];
int last_char, first_char;
int count; // Счетчик символов в буфере

// Эта функция считывает код нажатой клавиши
// из физического порта клавиатуры.
extern char get_char();

interrupt keyboard_handler() {
  // Считать код нажатой клавиши
  // и отдать его <<синхронному" процессу
  char ch;
  ch = get_char();
  send(internal_port, &ch, 1);
}

void driver_body() {
  char ch;
  int i;

  while(1) {
    select(internal_port, OS_port) {
      when (internal_port, &ch, 1):
      // Получить символ от обработчика прерывания
      // и поместить его в кольцевой буфер.
      // Если буфер полон, издать звуковой сигнал.
        if (last_char != first_char) {
          buffer[last_char] = ch;
          last_char = (last_char+1) & 1023;
          count++;
        } else beep();
      continue;

      when (OS_port,
            &request_header,
            sizeof(request_header)):

        switch(request_header.rq_type) {
  case RQ_READ:
    // Сформировать заголовок.
    request_header.rq_result-code = READ_OK.
    if (count == 0) {
              // Если буфер пуст, считать хотя бы один символ.
      receive(internal_port, &ch, 1);
              buffer[last_char] = ch;
              last_char = (last_char+1) & 1023;
              count++;
    }

            if (request_header.data_size > count)
      request_header.data_size = count;
    // Отправить заголовок в порт.
    send(OS_port,
         &request_header,
         sizeof(request_header));

    i = request_header.data_size;
    // Послать данные из буфера в порт.
    for (; i; i--) {
      send(OS_port, &buffer[first_char], 1);
      first_char = (first_char+1) & 1023;
      count--;
    }

  break;

  case RQ_SHUTDOWN: // Завершить работу драйвера:
    return;

  case RQ_WRITE:
  default:
    // Не умеем выполнять другие запросы:
    request_header.rq_result_code =
                COMMAND_NOT_SUPPORTED;
    receive(OS_port, 0, request_header.rq_data_size);
    send(OS_port,
         &request_header,
         sizeof(request_header));
  break;
} // end case
      continue;
    } // end select
  } // end while
}

void init_driver() {
  set_interrupt_handler(KEYBOARD, keyboard_handler);
  create_port(internal_port);

  last_char = 0;
  first_char = 1023;
  count = 0;

  process_start(driver_body);
}
\end{verbatim}
\end{example}

Приведенный пример также считывает только данные, уже
находившиеся в буфере на момент запроса.
Впрочем, сейчас уже относительно легко реализовать
чтение по строкам: начав обработку запроса чтения,
мы можем остановиться и подождать новых символов, используя операцию
\verb"receive(internal_port, ...)", пока не встретим конец строки.
Или же мы можем возложить разбиение потока данных на строки на программу
постобработки, как это сделано в системах семейства \sysname{Unix}.

\note{ Здесь возникает интересный вопрос: обязана ли
пользовательская программа ожидать окончания операции?
Вообще говоря, не обязана, но этот вопрос подробнее будет обсуждаться
в п. \ref{QIO}.
}

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

В нашем примере приводится только код самого драйвера.
Читателю предлагается самостоятельно представить себе код программ
пред- и постобработки.

{\small
Любопытно, что в транспьютере подобный драйвер был бы еще проще:
мы избавились бы от обработчика прерывания. Вместо этого мы просто
считывали бы данные из физического линка операцией \verb"get".
}

Основанная на микроядре асинхронная модель драйвера решает проблему
реентерабельности. Основным недостатком данной модели являются относительно
большие накладные расходы -- примитивы \verb'send/receive' нашего
микроядра осуществляют копирование данных; кроме того, эти примитивы
сопровождаются б\'{о}льшими накладными расходами, чем прямые вызовы в синхронной
модели. Однако, как показывает практика \sysname{QNX} и \sysname{VxWorks}, 
в действительности эти расходы невелики (например, в монолитных системах
семейства \sysname{Unix} тоже происходит копирование данных в системные
буфера) и оптимально реализованное микроядеро не уступает по 
производительности монолитным системам или даже превосходит их. 

\subsection[Асинхронный ввод/вывод в системах с монолитным ядром]
{Асинхронный ввод/вывод\\ в системах с монолитным ядром}

Ряд систем с монолитным ядром также реализуют асинхронный ввод/вывод,
используя вместо прямого вызова функций драйвера установку запроса
в очередь. Пожалуй, наиболее поучительна в этом смысле
структура драйвера в операционной системе \sysname{VAX/VMS}.

{\small
С точки зрения планировщика драйвер представляет собой процесс
с укороченным контекстом, так называемый \term{fork-процесс}.
Укорочение заключается в том, что драйвер может работать
только с одним банком виртуальной памяти из трех; таким образом,
при переключении контекста задействуется меньше регистров диспетчера памяти.
Fork-процесс имеет более высокий приоритет, чем все пользовательские
процессы, и может быть вытеснен только более приоритетным fork-процессом.
Вместо обычного дескриптора процесса (\verb"PCB" -- Process Control Block)
используется \verb"UCB" -- Unit Control Block, блок управления устройством.

Драйвер получает запросы на ввод/вывод через очередь запросов.
Элемент очереди называется \termint{\verb"IRP"}{Input[-Output] Request
Packet}{пакет запроса ввода/вывода}. Обработав первый запрос в очереди, 
драйвер начинает обработку следующего. Операции над очередью запросов
выполняются специальными командами процессора \machname{VAX} и являются
атомарными. Если очередь пуста, fork-процесс 
завершается. При появлении новых запросов система вновь создаст fork-процесс.

\verb"IRP" содержит: код операции (чтение, запись или код
\verb"SPFUN"\footnote{Специальная функция, подобная \verb"ioctl" в
системах семейства \sysname{Unix}.}); адрес блока данных, которые
должны быть записаны, или буфера, куда данные необходимо поместить;
информацию, используемую при постобработке, такую как
идентификатор процесса, запросившего операцию.

В зависимости от кода операции драйвер запускает соответствующую
подпрограмму. В \sysname{VAX/VMS} адрес подпрограммы выбирается из таблицы
\verb"FDT": Function Definition Table. Подпрограмма инициирует операцию
и приостанавливает fork-процесс, тем самым возвращая управление системе.
Затем, когда происходит прерывание, его обработчик возобновляет
исполнение fork-процесса. Как и в примере \ref{Linux_driver}, приостановка
и возобновление исполнения fork-процесса выполняются соответствующими 
сервисами ядра.

В некоторых случаях обработчику прерывания приходится решать
более сложную задачу: определять, какой из fork-процессов необходимо
активизировать. Например, терминальный мультиплексор обслуживает несколько
(некоторые модели -- до 64) последовательных каналов, но
имеет только одно прерывание. С каждым из каналов ассоциирован свой
\verb"UCB" и соответственно свой fork-процесс. Обработчик прерывания
должен определить, какой из каналов вызвал событие, и активизировать
процесс, связанный с этим каналом.

Окончив обработку запроса, fork-процесс драйвера вызывает
\verb"AST", сигнализируя программе постобработки об окончании запроса.

Более подробно организация подсистемы ввода/вывода в \sysname{VAX/VMS}
описана в работах \cite{VAX1} и \cite{Deitel1}.
}

Аналогичным образом устроены драйверы в \sysname{OS/2}.
Даже элемент очереди запросов там называется \verb"IRP".
Точнее, модель драйвера в \sysname{OS/2} похожа на наше описание
работы драйвера в \sysname{VAX/VMS}, но структура самого драйвера
отличается. Драйвер в \sysname{VAX/VMS} состоит из набора таблиц
фиксированной структуры, задающих точки входа в подпрограммы обработки,
и самих этих подпрограмм. Напротив, драйвер в \sysname{OS/2} представляет
собой загрузочный модуль с единственным обязательным элементом: заголовком
драйвера, который задает точки входа инициализационной программы драйвера
и программы fork-процесса, которая называется \termin{стратегической функцией
устройства}{device strategy function}.

\label{block_devices}
Термин \term{device strategy function} унаследован из систем семейства
\sysname{Unix}. Хотя во многих системах этого семейства используется полностью
синхронная модель работы с последовательными устройствами,
блочные устройства с самого  начала  использовали асинхронную
модель,  основанную на очереди запросов. Запросы обрабатываются
стратегической функцией, которая представляет собой кооперативный процесс.
Так же, как fork-процесс в \sysname{VAX/VMS}, стратегическая функция
завершается при опустошении очереди запросов. При появлении новых
запросов ядро перезапускает ее. Буферизация запросов
и формирование очереди осуществляется специальным модулем системы,
который называется \term{дисковым кэшем}. Принцип работы дискового кэша
будет обсуждаться в п. \ref{disk_cache}.

В \sysname{Unix System V} существует модуль \progname{STREAMS},
который осуществляет буферизацию и <<асинхронизацию>> запросов к
последовательным устройствам.
Драйверы, рассчитанные на работу с этим модулем,
также предоставляют стратегическую функцию вместо
непосредственно вызываемых функций \verb"read/write".
\sysname{Unix System V Release 4} имеет микроядерную архитектуру,
поэтому в ней все драйверы являются асинхронными.

Модель драйвера, основанную на форк-процессах или стратегических функциях
можно считать переходной между монолитным ядром и микроядром, а операции
над очередью запросов можно считать реализацией примитивов 
\verb'send/receive'. Поэтому можно говорить о непрерывном спектре более или 
менее монолитных (или более или менее микроядерных) архитектур ядра, с 
полностью микроядерными системами (напр., \sysname{QNX}) на одном конце
спектра и полностью монолитными -- на другом. При этом даже монолитный
<<классический>> \sysname{Unix} будет иметь некоторые микроядерные черты;
полностью монолитной можно считать, разве что \sysname{MS DOS}, да и то
при отсутствии асинхронного дискового кэша.

\subsection[Асинхронная модель В/В]{Асинхронная модель ввода/вывода\\
с точки зрения приложений}
\label{QIO}\label{lazy_write}

В п. \ref{async_drv}, обсуждая асинхронную модель драйвера,
мы задались вопросом: должна ли прикладная программа, сформировав
запрос на ввод/вывод, дожидаться его завершения? Ведь система, приняв
запрос, передает его асинхронному драйверу, который инициирует операцию
на внешнем устройстве и освобождает процессор. Сама система не ожидает
завершения запроса. Так должна ли программа ожидать его?

Если было запрошено чтение данных, то ответ, на первый взгляд,
очевиден: должна. Ведь если данные запрошены, значит они сейчас будут
нужны программе.

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

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

Напротив, при записи, казалось бы, нет необходимости дожидаться
физического завершения операции. При этом мы получаем режим, известный
как \termint{отложенная запись}{lazy write}{<<ленивая>> запись, если
переводить дословно}. Однако такой режим создает две специфические проблемы.

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

Если система копирует записываемые данные из пользовательского адресного
пространства в системное, то эта же проблема возникает внутри ядра; внутри
ядра проблема решается использованием многобуферной схемы, и все относительно 
просто. Однако копирование приводит к дополнительным затратам времени и 
требует выделения памяти под буфера. Наиболее остро эта проблема встает 
при работе с дисковыми и сетевыми устройствами, с которыми система 
обменивается большими объемами данных. Проблема управления дисковыми 
буферами подробнее обсуждается в \ref{disk_cache}.

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

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


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

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

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

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

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

Например, в системах \sysname{RSX-11} и \sysname{VAX/VMS} фирмы
\entname{DEC} для синхронизации используется \termin{флаг локального
события}{local event flag}. Как говорилось в п. \ref{AST},
флаг события в этих системах представляют собой аналог двоичных семафоров
Дийкстры, но с ним также может быть ассоциирована процедура \verb"AST".

Системный вызов ввода/вывода в этих ОС называется \verb"QIO"
(Queue Input/Output [Request] -- установить в очередь запрос ввода/вывода)
и имеет две формы: асинхронную \verb"QIO" и синхронную \verb"QIOW"
(Queue Input/Output and Wait -- установить запрос и ждать [завершения]).
С точки зрения подсистемы ввода/вывода эти вызовы ничем не отличаются,
просто при запросе \verb"QIO" ожидание конца запроса выполняется
пользовательской программой <<вручную>>, а  при \verb"QIOW" выделение флага
события и ожидание его установки делается системными процедурами пред- и
постобработки.

В ряде систем реального времени, например, в \sysname{OS-9} и \sysname{RT-11},
используются аналогичные механизмы.

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

Возможно, это объясняется идейным влиянием ОС \sysname{Unix}.
Набор операций ввода/вывода, реализованных в этой ОС, стал общепризнанным
стандартом де-факто и основой для нескольких официальных стандартов.
Например, набор операций ввода/вывода в \sysname{MS~DOS}
является прямой копией \sysname{Unix}; кроме того, эти операции входят
в стандарт \entname{ANSI} на системные библиотеки языка \progname{C}
и стандарт \standname{POSIX}.

Некоторые системы, например \sysname{Unix System V R4}, разрешают
программисту выбирать между отложенной записью по принципу
\termin{Fire And Forget}{выстрелил и забыл} и полностью синхронной,
выбирая между этими режимами вызовом \verb"fcntl" с соответствующим
кодом операции.

{Разработчики приложений для \sysname{OS/2} и \sysname{Win32}
(\sysname{Windows NT} и \sysname{Windows 95})
часто сталкиваются с необходимостью асинхронного исполнения запросов
ввода/вывода. Разработчикам предлагается самостоятельно имитировать
асинхронный обмен, создавая для каждого асинхронно исполняемого
запроса свой процесс (\termin{нить}{thread} в принятой в этих
системах терминологии). Обычно нить, исполняющая запрос, тем или иным
способом сообщает основной нити о завершении операции. Для этого чаще всего
используются штатные средства межнитевого взаимодействия -- семафоры и
др.

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

Любопытно, что <<нитевая>> оптимизация неинтерактивных приложений,
ориентированных на интенсивный ввод/вывод (серверов транзакций и др.)
не приводит к столь впечатляющим результатам: тесты показывают, что
приложения такого типа для систем семейства \sysname{Unix} оказываются
быстрее или, во всяком случае, не медленнее, чем эквивалентные
приложения для \sysname{OS/2} или \sysname{NT}, несмотря на то, что
большинство систем семейства \sysname{Unix} не имеют ничего даже
отдаленно похожего на нити или асинхронный ввод/вывод.

Как \sysname{OS/2}, так и \sysname{Win32} не предоставляют
системных вызовов для асинхронного ввода/вывода, что несколько
удивительно, так как обмен данными с драйвером \sysname{OS/2} и
\sysname{Windows NT} происходит асинхронно, путем установки
запроса в очередь.

В \sysname{Windows NT} существует средство организации асинхронного
ввода/вывода -- так называемые \termin{порты завершения [операции]}%
{completion ports}. Однако это средство не поддерживается в
\sysname{Windows 95}, возможно из-за синхронной организации
ввода/вывода в этой системе, поэтому большинство разработчиков избегают
использования портов завершения.
}

Синхронная модель ввода/вывода проста в реализации и использовании
и, как показал опыт систем семейства \sysname{Unix} и его идейных
наследников\footnote{\sysname{MS~DOS}, как уже говорилось, использует
прямую копию модели \sysname{Unix}, а \sysname{OS/2} и
\sysname{Windows~NT} во многих отношениях являются наследниками
\sysname{MS~DOS}, в том числе и по используемой модели ввода/вывода.},
вполне адекватна большинству приложений общего назначения. Однако, как
уже было показано, она не очень удобна (а иногда и просто непригодна)
для задач реального времени.

\subsection{Дисковый кэш}\label{disk_cache}

Функции и принципы работы дискового кэша существенно отличаются
от общих алгоритмов кэширования, обсуждавшихся в п. \ref{swapping}.
Дело в том, что характер обращения к файлам обычно существенно отличается
от обращений к областям кода и данных задачи. Например, компилятор
\progname{C} и макропроцессор \TeX\ рассматривают входные и выходные
файлы как потоки данных. Входные файлы прочитываются строго последовательно
и полностью, от начала до конца. Аналогично выходные файлы полностью
перезаписываются, и перезапись тоже происходит строго последовательно.
Попытка выделить аналог рабочей области при таком характере обращений
обречена на провал независимо от алгоритма, разве что рабочей областью
будут считаться все входные и выходные файлы.

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

\begin{enumerate}
\item Размещение в памяти структур файловой системы -- каталогов,
\verb"FAT" или таблицы инодов\footnote{Эти понятия подробнее обсуждаются
в гл. \ref{FileSystems}.} и т.д. Это основной источник повышения
производительности
при использовании дисковых кэшей под \sysname{MS/DR~DOS}.

\item Отложенная запись. Само по себе откладывание записи не повышает
скорости обмена с диском, но позволяет более равномерно распределить 
загрузку канала.

\item Группировка запросов на запись. Система имеет пул буферов отложенной
записи, который и называется дисковым кэшем. При поступлении запроса на
запись, система выделяет буфер из этого пула и ставит его в очередь к
драйверу. Если за время нахождения буфера в очереди в то же место на
диске будет произведена еще одна запись, система может дописать данные
в имеющийся буфер вместо установки в очередь второго запроса. Это
значительно повышает скорость, если запись происходит массивами,
не кратными размеру физического блока на диске.

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

\item Опережающее считывание. При последовательном обращении к данным
чтение из какого-либо блока значительно повышает вероятность того,
что следующий блок также будет считан. Теоретически опережающее чтение
должно иметь тот же эффект, что и отложенная запись, т.е. обеспечивать
более равномерную загрузку дискового канала и его работу параллельно с
центральным процессором. На практике, однако, часто оказывается, что
считанный с опережением блок оказывается никому не нужен, поэтому
эффективность такого чтения заметно ниже, чем у отложенной записи.

\item Сортировка запросов по номеру блока на диске. По идее, такая
сортировка должна приводить к уменьшению времени позиционирования головок
чтения/записи. Кроме того, если очередь запросов будет отсортирована,
это облегчит работу алгоритмам кэширования, которые производят поиск буферов
по номеру блока. Во всяком случае вреда от сортировки нет, а польза
теоретически возможна, поэтому многие системы выполняют такую сортировку.

В работе \cite{Deitel2} подробно описываются различные подходы к
сортировке запросов. Авторы не имеют данных,
которые подтверждали бы повышение производительности за счет сортировки
на современных дисковых устройствах.
\end{enumerate}

Кэширование значительно повышает производительность дисковой подсистемы, 
но создает ряд проблем, причем некоторые из них довольно неприятного свойства.

Первая из проблем -- та же, что и у отложенной записи вообще.
При использовании отложенной записи программа не знает, успешно ли
завершилась физическая запись. Однако многие современные файловые
системы поддерживают так называемый \termin{hotfixing}{горячую починку}
-- механизм, обеспечивающий динамическую замену <<плохих>> логических
блоков на <<хорошие>>, что в значительной мере компенсирует эту проблему.

Вторая проблема гораздо серьезнее и тоже свойственна всем механизмам
отложенной записи: если в промежутке между запросом и физической записью
произойдет сбой всей системы, то данные будут потеряны. Например,
пользователь сохраняет отредактированный файл и, не дождавшись окончания
физической записи, выключает питание -- содержимое файла оказывается потеряно
или повреждено.
Другая ситуация, до боли знакомая всем пользователям
\sysname{DOS/Windows~3.x/Windows~95}: пользователь сохраняет файл, и
в это время система зависает -- результат тот же.
Аналогичного результата можно достичь, не вовремя достав дискету
или другой удаляемый носитель из дисковода.

{\small
Очень забавно наблюдать как пользователь, хотя бы раз имевший неприятный
опыт общения с дисковым кэшем \verb"SMARTDRV", копирует данные с чужого
компьютера на дискету. Перед тем, как извлечь ее из дисковода, он
оглядывается на хозяина машины и с опаской спрашивает: <<У тебя там
никаких кэшей нет?>>.
Авторам доводилось наблюдать такое поведение у нескольких десятков людей.
}

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

\note{
Методы обеспечения целостности данных при системном сбое подробнее
обсуждаются в п. \ref{FaultTolerance}. Находившиеся в кэше данные
при фатальном сбое гибнут всегда, но существуют способы
избежать повреждения системных структур данных на диске
без отказа от использования отложенной записи.
}

Третья проблема, связанная с дисковым кэшем -- это выделение памяти под него.
Уменьшение кэша приводит к снижению производительности дисковой
подсистемы, увеличение же кэша отнимает память у пользовательских программ.
В системах с виртуальной памятью это может привести к увеличению дисковой
активности за счет увеличения объема подкачки, что ведет к снижению как
дисковой, так и общей производительности системы. Перед администратором
системы встает нетривиальная задача: найти точку оптимума. Положение этой
точки зависит от:
\begin{itemize}
\item объема физической памяти;
\item скорости канала обмена с диском, а также от того, работает этот
канал с использованием центрального процессора,
как \machname{IDE}-контроллеры у \machname{IBM PC} или же по ПДП;
\item скорости центрального процессора;
\item суммы рабочих наборов программ, исполняющихся в системе;
\item интенсивности и характера обращений к диску.
\end{itemize}

При этом зависимость количества страничных отказов от объ\-ема памяти,
доступной приложениям, имеет существенно нелинейный вид. Это же утверждение
справедливо для связи между размером дискового кэша и соответствующей
экономией обращений к диску. Таким образом, задача подбора оптимального
размера кэша является задачей нелинейной оптимизации.
Самым неприятным является то, что ключевой исходный параметр --
{\it характер} обращений  к диску -- является не количественным,
а качественным; точнее сказать, его можно измерить лишь при помощи очень
большого числа независимых количественных параметров.

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

Возникает вполне естественное желание возложить подбор размера кэша на
саму систему, т.е. менять размер кэша динамически в зависимости
от рабочей нагрузки. Кроме упрощения работы администратора, такое решение
имеет еще одно большое преимущество: система начинает <<автомагически>>
подстраиваться под изменения нагрузки.

Но далеко не все так просто. Если объем памяти в системе превосходит
потребности прикладных программ, то динамический дисковый кэш может
формироваться по очень простому <<остаточному>> принципу -- все, что не
пригодилось приложениям, отдается под кэш. Однако оперативная память
до сих пор относительно дорог\'{а} и представляет собой дефицитный ресурс,
поэтому наибольший практический интерес представляет ситуация, когда
памяти не хватает даже приложениям, не говоря уже о кэше. Тем не
менее кэш обычно нужен.

Разумной политикой была бы подстройка кэша в зависимости от количества
страничных отказов: если число отказов становится слишком большим, система
уменьшает кэш; если же число отказов мал\'{о}, а идут интенсивные обращения к
диску, система увеличивает кэш. Получается саморегулирующаяся система
с отрицательной обратной связью. Однако, если вдуматься, то видно, что
вместо одной произвольной переменной (объема статического кэша) мы
вынуждены ввести как минимум три:
\begin{itemize}
\item количество страничных отказов, которое считается слишком большим;
\item количество отказов, которое считается достаточно малым;
\item величину, на которую следует увеличить или уменьшить кэш в этих
случаях.
%\item минимальный размер кэша.
\end{itemize}

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

Кроме того, читатель, знакомый с теорией управления, должен знать,
что неудачный подбор параметров у системы с отрицательной обратной связью
может приводить к колебательному процессу вместо саморегуляции.
В дискуссиях USENET news приводились примеры развития таких колебаний
в динамическом кэше системы \sysname{Windows~NT} при компиляции
большого проекта в условиях недостатка памяти.

Вполне возможно, что низкая производительность \sysname{Windows~NT}
на системах с <<небольшим>> (8 - 16 Мб) количеством памяти объясняется
вовсе не  низким качеством реализации и даже не секретным сговором между
фирмой \entname{MicroSoft} и производителями оперативной памяти,
а просто плохо сбалансированным динамическим кэшем.

\subsection{Спулинг}\label{Spooling}

\begin{epygraph}
Гигабайт тебе в спул.

\flushright Популярное ругательство
\end{epygraph}


Термин \termin{спулинг}{spooling} не имеет общепринятого русского аналога.
В соответствии с программистским фольклором, слово это происходит от
аббревиатуры \term{Simultaneous Peripherial Operation Off Line}.
Эту фразу трудно дословно перевести на русский язык; имеется в виду
метод работы с внешними устройствами вывода (реже -- ввода) в многозадачной 
ОС или многомашинной среде, при которой задачам создается иллюзия 
одновременного доступа к устройству. При этом, однако, задачи не получают к 
устройству прямого доступа, а работают в режиме \termin{off-line}{{\rm без 
прямого подключения}}. Выводимые данные накапливаются системой, а затем 
выводятся на устройство так, чтобы вывод различных задач не смешивался.

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

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

Классический спулинг реализован в ОС семейства \sysname{Unix}.
В этих ОС вывод задания на печать осуществляется командой \verb"lpr".
Эта команда копирует предназначенные для печати данные в каталог
\verb"/usr/spool/lp", возможно, пропуская их при этом через
программу-фильтр.
Каждая порция данных помещается в отдельный файл.
Имена файлов генерируются так, что имя каждого вновь
созданного файла было <<больше>> предыдущего при сравнении
\standname{ASCII}-кодов. За счет этого файлы образуют очередь.

Системный процесс-\termin{демон}{daemon} \verb"lpd" (или \verb"lpshed" в
\sysname{Unix SVR4}) периодически просматривает каталог. Если
там что-то появилось, а печатающее устройство свободно, демон
копирует появившийся файл на устройство. По окончании копирования
он удаляет файл, тем или иным способом уведомляет пользователя об
окончании операции (в системах семейства \sysname{Unix} чаще всего
используется электронная почта) и вновь просматривает каталог.
Если там по-прежнему что-то есть, демон выбирает первый
по порядку запрос и также копирует его на устройство.

Тот же механизм используется почтовой системой \sysname{Unix} --
программой \verb"sendmail", только вместо каталога
\verb"/usr/spool/lp" используется \verb"/usr/spool/mail".

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

В \sysname{OS/2} и \sysname{Windows~NT} спулинг организован отчасти
похожим образом с той разницей, что установка запроса в очередь может
происходить не только командой \verb"PRINT", но и простым копированием
данных на псевдоустройство \verb"LPT[1-9]". В отличие от систем семейства
\sysname{Unix} как программа \verb"PRINT",  так и
псевдоустройства портов активизируют процесс спулера
непосредственно при установке запроса.
Графические драйверы печатающих устройств в этих системах также
используют спул вместо прямого обращения к физическому порту.

\sysname{Novell Netware} предоставляет специальный механизм для
организации спулинга -- очереди запросов. Для хранения данных в этих
очередях также используется диск, но прикладные программы вместо
просмотра каталога могут пользоваться системными функциями
\verb"GetNextMessage" и \verb"PutMessage".
Вызов \verb"GetNextMessage" блокируется,  если очередь пуста;
таким образом,
нет необходимости ожидать пробуждения демона или специальным образом
активизировать его -- демон сам пробуждается при появлении запроса.
Любопытно, что почтовая система \progname{Mercury Mail} для
\sysname{Novell Netware} может использовать для промежуточного хранения
почты как очередь запросов, так и выделенный каталог в зависимости от
конфигурации.
