\chapter[Параллельное исполнение]{Параллельное и псевдопараллельное исполнение}

\section[Выгоды многопpоцессности]{Выгоды многозадачности и многопроцессности}

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

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

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

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

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

Теоретически можно возложить задачу распараллеливания на
пользовательскую программу -- так поступают некоторые разработчики
программ реального времени для \sysname{MS~DOS} или в некоторых
кросс-системах.

Однако многопроцессность создает ряд специфических проблем,
и оказывается целесообразным реализовать решения этих проблем один
раз, собрать код, решающий их, в единый модуль и объявить этот модуль
ядром ОС. Именно таким образом построено ядро систем
\sysname{RT-11}, \sysname{OS-9} и ОС, базирующихся на технологии
\termin{микроядра}{microkernel} -- \sysname{QNX}, \sysname{UNIX System V R4},
\sysname{HURD}.

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

\section{Проблемы при параллельной работе}

Первой из проблем является проблема разделения ресурсов.
Действительно, представим себе две программы, пытающиеся печатать что-то
на одном принтере. Если они будут делать это произвольным образом,
их вывод на бумаге будет перемешан и скорее всего окажется совершенно
нечитаемым. Одним из разумных решений может быть монопольный захват
принтера одной из программ. При этом другая программа будет вынуждена ждать,
пока принтер не освободится. Значит, нужны средства для захвата ресурсов
и ожидания их освобождения\footnote{Hа пpактике для pазделения пpинтеpов
используют более сложные и удобные сpедства, обсуждаемые в pазделе
\ref{Spooling}.}.

Другая проблема -- это проблема
\termint{реентерабельности}{reenterability}{повтоpной входимости, от re-enter}
разделяемых программ.

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

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

При других техниках программирования могут
возникнуть серьезные проблемы, вплоть до развала системы.
Модули, которые можно вызывать многократно, называются \term{реентерабельными}.
Соответственно программы, которые так вызывать нельзя, называются
нереентерабельными. Типичный пример нереентерабельной программы --
ядро дисковой операционной системы \sysname{MS~DOS}.

\label{reentr}
Легко понять, что программы, управляющие внешними устройствами или
файловыми системами и вообще работающие с разделяемыми объектами,
{\it не могут} быть реентерабельными.

Во многих случаях оказывается выгодно рассматривать нереентерабельную
программу как разделяемый ресурс и распределять доступ к нему теми
же способами, что и к принтеру. Так поступает большинство известных авторам
средств организации параллельной работы под \sysname{MS~DOS}. Таким же
образом микроядро организует доступ пользовательских программ к модулям ОС.

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

Первая, самая простая из них, состоит в вопросе -- если одна задача
производит данные, а вторая их потребляет, то как задача-потребитель
узнает, что готова очередная порция данных? Или, что еще интереснее, как она
узнает, что очередная порция данных еще не готова?
Типичный случай такого взаимодействия -- асинхронное чтение с диска,
когда программа дает дисковому драйверу запрос: <<читай с такого-то сектора
в такой-то блок памяти>>, и продолжает заниматься своими делами.
Это режим работы, поддерживаемый всеми ОС линии
\sysname{RT-11} - \sysname{RSX-11} - \sysname{VAX/VMS} - \sysname{OpenVMS}
и многими системами реального времени.

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

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

\section{Методы синхронизации}

\subsection{Прерывания и сигналы}\label{signals}\label{interrupts}
\begin{epygraph}
\begin{verse}
Я слышу крик в темноте,\\
Возможно, это сигнал\\
\end{verse}

\flushright Nautilus Pompilius
\end{epygraph}

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

Слово \term{прерывание} представляет довольно неудачную, на взгляд
авторов, кальку с англоязычного термина \termin{interrupt}{{\rm
существительное от глагола} прервать}.

Прерывания, вызванные внутренними событиями,
часто называют \termin{исключениями}{exceptions}. Мы далее будем разделять
эти два понятия, то есть внешние прерывания будем называть просто
прерываниями, а внутренние -- исключениями.
Исключения возникают при делении на ноль, неопределенном
коде команды, ошибках обращения к памяти и т.д.

Реализации прерываний и исключений у разных процессоров немного отличаются.

{\small
Для примера рассмотрим организацию прерываний в машинах семейства
\machname{PDP-11}.
Машины данной архитектуры сейчас почти не используются, но
ряд архитектурных решений не потерял актуальности и поныне.
В частности, подход к реализации прерываний считается классическим.

Процессоры семейства \machname{PDP-11} различают 128 типов прерываний
и исключений. Каждому типу соответствует процедура - обработчик.
Адреса точек входа всех процедур собраны в таблицу, называемую
\term{таблицей векторов прерываний}. Эта таблица занимает 256 слов
физической памяти, начиная с нулевого адреса.
Каждый элемент таблицы (\term{вектор}) содержит адрес обработчика и
новое слово состояния
процессора. Ниже будет объяснено, для чего это сделано.

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

Каждый вход соответствует определенному уровню приоритета.
\machname{PDP-11} имеет восемь уровней приоритета прерывания.
Прерывание происходит только когда уровень приоритета процессора ниже
приоритета запрашиваемого прерывания. Если у процессора установлен приоритет
\verb"7", внешние прерывания запрещены. Приоритет процессора задается его
словом состояния.

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

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

\note{
При этом приоритет процессора автоматически устанавливается равным
тому значению, которое разработчик программы обработки считает правильным.
Обратите внимание: не равным приоритету обрабатываемого прерывания,
а тому, которое требует разработчик.
}

При завершении процедуры обработки вызывается команда \verb"RTI"
(ReTurn from Interrupt -- возврат из прерывания). Эта команда
выталкивает из стека адрес прерванной команды и старое слово
состояния, тем самым восстанавливая приоритет процессора.

Для сравнения: в процессорах семейства \machname{i80x86} вектор прерывания
содержит только адрес программы-обработчика, а приоритет процессора
задается не словом состояния процессора, а регистром внешнего устройства --
\term{контроллера прерываний}. Контроллер прерываний обычно устанавливает
приоритет равным приоритету прерывания, обрабатываемого в данный момент.
Чтобы повысить или понизить этот уровень, обработчик прерывания должен
программировать контроллер. Перед завершением обработчика необходимо
вернуть контроллер прерываний в исходное состояние, выполнив над ним
серию магических команд -- \term{эпилог прерывания}.

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

В моделях \machname{PDP-11}, имеющих диспетчер памяти, эта проблема
решается просто: для процессора в каждый момент времени заданы два
адресных пространства: пользовательское и системное.
Все прерывания обрабатываются в системном адресном пространстве.

В защищенном режиме процессоров \machname{i80x86} использован более
гибкий механизм установки адресного пространства для обработчика.
По существу, с каждым обработчиком может быть ассоциировано свое
виртуальное адресное пространство. О способе, которым это достигается,
лучше прочитать в литературе по соответствующим процессорам, например
\cite{Intel386}.
}

Аналогичное прерываниям средство реализовано в ряде ОС --
например, в \sysname{UNIX} -- для чисто программных событий.
Это средство называется \term{сигналами} и используется для обработки
исключительных ситуаций и, в некоторых случаях, для межпроцессной
коммуникации. Сигналы в \sysname{UNIX} часто используются
для принудительного завершения программы, и даже команда посылки
сигнала называется \verb"kill" -- \term{убить}.

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

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

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

Кроме того, программу, работающую совместно с процедурами обработки
прерываний, нельзя представить в виде детерминированного конечного автомата.
Это усложняет анализ алгоритмов и доставило в свое время много волнений
теоретикам программирования. Например, в \cite{Discipline} Дийкстра очень
эмоционально описывает свою реакцию при первом столкновении с системой,
использующей прерывания.

% Здесь надо рассказать легенду про Дийкстру.

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

{\bf Но как программа узнает, что события еще не происходило?}

Действительно, вернемся к примеру из предыдущего раздела:
программа {\bf A} производит данные, а программа {\bf B} их потребляет.
Наиболее простым решением было бы объединить эти программы в один процесс.
Тогда программа {\bf A}, произведя очередную порцию данных, вызывала бы программу
{\bf B}, и ждала бы, пока та пережует эту порцию.
Или наоборот, программа {\bf B}, обнаружив, что ей нужны очередные данные,
вызывала бы программу {\bf A}.
Понятно, что в этом случае мы отказываемся от всех преимуществ
многопроцессности.

Если мы хотим, чтобы программы {\bf A} и {\bf B} исполнялись параллельно,
программа {\bf B} должна быть способна узнать, что очередная порция данных
готова.
Например, мы можем создать флаг, который равен нулю, если данные не готовы,
и единице, если готовы.
Тогда модель взаимодействия выглядит так:
\begin{itemize}
\item Программа {\bf B}, когда ей нужны очередные данные, проверяет флаг.
Если флаг равен 1, данные готовы. Если не равен, то нужно заснуть
до получения сигнала.
\item Программа {\bf A}, подготовив очередную порцию данных, посылает сигнал
программе B.
\item Обработчик сигнала устанавливает флаг в 1 и возобновляет выполнение
программы {\bf B}.
\end{itemize}

Если мы запишем алгоритм программы {\bf B} на псевдокоде, он будет выглядеть
примерно так:

\begin{example}\label{signal1}\nopagebreak
\small\begin{verbatim}

extern boolean flag;

  set_signal_handler(DATA_READY, sighandler);
  while(1) {
    .... // Обработка очередной порции данных
    if (flag != TRUE) {
     /* Обратите внимание, что проверка флага *
      * и засыпание - это разные операторы!   */
      pause();
    }
    .... // Данные готовы!
  } // End while

void sighandler() {
  flag = TRUE;
}
\end{verbatim}
\end{example}

Для простоты мы опускаем обсуждение вопроса о том, кем и как флаг
устанавливается в 0. Нам и без этого хватит тем для обсуждения.
Внимательный читатель должен был задаться вопросом:
что будет, если обработчик сигнала активизируется в интервале между
операторами \verb"if" и \verb"pause()"? Хотя такое событие
маловероятно, оно приведет к засыпанию программы {\bf B} навсегда!

Напрашивающееся решение состоит в том, чтобы запретить сигнал
\verb"DATA_READY" на время проверки флага. Но мы все равно должны разрешить сигнал
перед засыпанием, поэтому это, на самом деле, вовсе не решение.

{\small
Одно из решений состоит в переделке программы таким образом:

{\samepage
\begin{example}\label{signal2}
\small\begin{verbatim}

extern boolean flag;

  set_signal_handler(DATA_READY, sighandler);
  while(1) {
    .... // Обработка очередной порции данных
    label:
    if (flag != TRUE) {
      pause();
    }
    .... // Данные готовы!
  } // End while

void sighandler() {
  flag = TRUE;
  goto label;
}
\end{verbatim}
\end{example}
}

Для простоты мы не обсуждаем вопрос о том, как можно делать передачу
управления между функциями. В языке \progname{C} это может быть сделано
библиотечными функциями \verb"setjmp/longjmp". В языках \progname{Ada} и
\progname{C++} для этого используется механизм обработки исключений.
На ассемблере мы должны не только передать управление, но и восстановить
стек в то состояние, которое он имел во время вызова целевой функции.
Желающие исследовать этот вопрос подробнее могут прочитать руководство
по соответствующим языкам программирования или исследовать исходные
тексты функций \verb"setjmp/longjmp", входящие в поставку
\progname{Borland~C/C++~3.x} или \progname{4.x}, ОС \sysname{BSD UNIX},
\sysname{Linux} и т.д.

Текст \ref{signal2}, на самом деле, содержит еще более серьезную ошибку:
что будет, если обработчик активизируется до окончания обработки данных?
Эта проблема также имеет решение, но мы не будем далее обсуждать эту
идею, а скажем лишь, что код, содержащий решения всех возникающих
проблем, занял бы около страницы.

Именно поэтому \progname{Справочное руководство программиста ОС UNIX}
не рекомендует пользоваться сигналами для синхронизации процессов.
}

\subsection{Семафоры}

Если мы хотим спроектировать простой и удобный механизм синхронизации,
лучше всего объединить проверку флага и засыпание процесса в единую операцию,
которая не может быть прервана исполнением другого процесса. Распространив
эту идею на случай взаимодействия более чем двух процессов, мы приходим к
механизму, известному под названием \term{семафоров Дийкстры}.

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

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

Наиболее простым случаем семафора является \term{двоичный} семафор.
Начальное значение флаговой переменной такого семафора равно 1, и вообще она
может принимать только значения 1 и 0. Двоичный семафор соответствует случаю,
когда с разделяемым ресурсом в каждый момент времени может работать только
одна программа.

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

При доступе к нескольким различным ресурсам с использованием семафоров
возникает специфическая проблема, называемая
\termin{мертвой блокировкой}{dead lock}.
На этой проблеме стоит остановиться подробнее, потому что
она возникает и при многих других методах синхронизации,
но в случае семафоров ее легче объяснить.

Рассмотрим две программы, использующие доступ к двум различным ресурсам.
Например, один процесс копирует данные со стримера на кассету
\machname{Exabyte}, а другой -- в обратном направлении.
Доступ к стримеру контролируется семафором \verb"sem1", а к кассете --
семафором \verb"sem2".

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

Эта проблема может быть решена несколькими способами. Первый способ --
разрешить программе в каждый момент времени держать закрытым только один
семафор -- прост и решает проблему в корне, но часто оказывается неприемлемым.
Более приемлемым оказывается соглашение, что семафоры всегда должны
закрываться в определенном порядке. Этот порядок может быть любым, важно только
чтобы он всегда соблюдался.
Третий, наиболее радикальный, вариант состоит в предоставлении возможности
объединить семафоры и/или операции над ними в неразделяемые группы.
При этом программа может выполнить операцию закрытия семафоров \verb"sem1"
и \verb"sem2" единой командой, во время исполнения которой никакая другая
программа не может получить доступ к этим семафорам.

Многие ОС предоставляют для синхронизации семафоры Дийкстры или похожие
на них механизмы.

{\small\label{AST}
Так, например, в системах \sysname{RSX-11} и \sysname{VMS} основным средством
синхронизации являются \termin{флаги событий}{event flags}.
Процессы и система могут \termin{очищать}{clear} или \termin{взводить}{set}
эти флаги.
Флаги делятся на локальные и глобальные. Локальные флаги используются
для взаимодействия между процессом и ядром системы, глобальные -- между
процессами.
Процесс может остановиться, ожидая установки определенного флага,
поэтому флаги во многих ситуациях можно использовать вместо двоичных семафоров.
Кроме того, процесс может связать с флагом события процедуру-обработчик
\termint{AST}{Asynchronous System Trap}{Асинхронно [вызываемый] системный
обработчик}. AST во многом напоминают сигналы или аппаратные прерывания.

В частности, флаги событий используются для синхронизации
пользовательской программы с асинхронным исполнением запросов на ввод/вывод.
Исполняя запрос, программа задает локальный флаг события. Затем она
может остановиться, ожидая этого флага, который будет взведен после
исполнения запроса. При этом мы получаем псевдосинхронный ввод/вывод,
напоминающий синхронные операции чтения/записи в \sysname{UNIX} и \sysname{MS~DOS}.
Но программа может и не останавливаться! При этом запрос будет исполняться
параллельно с исполнением самой программы, и она будет оповещена о
завершении операции соответствующей процедурой \verb"AST".

Любопытно, что в этом случае процедуре \verb"AST" не нужно устанавливать
никаких флаговых переменных, а программе не нужно проверять их -- она может
просто посмотреть значение флага события. Поэтому ничего похожего на
проблему в программе \ref{signal1} просто не возникает.

Асинхронный ввод/вывод часто жизненно необходим в программах реального
времени, но бывает полезен и в других случаях. Например, реализованная
С.Ковалевым программа просмотра файлов для \sysname{VAX/VMS} при запуске
считывает и форматирует столько данных, чтобы заполнить экран. Затем она
ожидает команд пользователя и одновременно считывает и форматирует данные
на несколько экранов вперед. Если пользователь дает команду <<следующий экран>>,
то показываются заранее отформатированные данные. За счет этого достигается
быстрый запуск и очень малое время реакции на команды, то есть очень высокая
субъективная <<скорость>>.
}

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

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

\subsection{Блокировка участков файлов}
\label{filelock}

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

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

Блокировка участков файла в качестве средства синхронизации была известна
еще с шестидесятых годов, но в том виде, который описан в стандартах
\standname{ANSI} и \standname{POSIX}, она была реализована в ОС
\sysname{UNIX} в начале 70-х. Этот стандарт поддерживается практически
всеми современными многопроцессными ОС и даже \sysname{MS/DR~DOS} при
работе в сети или в \sysname{MS~Windows}.

В \sysname{UNIX} возможны два режима блокировки:
\termin{допустимая}{advisory} и \termin{обязательная}{mandatory}.
Как та, так и другая блокировка
может быть блокировкой на чтение либо на запись. Допустимая блокировка
является <<блокировкой для честных>>: она не оказывает влияния на подсистему
ввода/вывода, поэтому программа, не проверяющая блокировок или игнорирующая
их, сможет писать или читать из заблокированного участка без проблем.
Обязательная блокировка требует б\'{о}льших накладных расходов, но запрещает
физический доступ к файлу: чтение или запись, в зависимости от типа блокировки.

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

\subsection{Гармонически взаимодействующие последовательные процессы}

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

Желание устранить эти проблемы привело в свое время Дийкстру к концепции,
известной как \term{гармонически взаимодействующие последовательные процессы}.
Эта концепция состоит в следующем:
\begin{itemize}
\item Каждый процесс представляет собой независимый программный модуль, для
которого создается иллюзия чисто последовательного исполнения.
\item Процессы не имеют разделяемых данных.
\item Все обмены данными, и вообще взаимодействие, происходят в выделенных
точках процессов. В этих точках процесс, передающий данные, останавливается
и ждет,  пока его партнер будет готов эти данные принять. В
некоторых реализациях
процесс-передатчик может не ожидать приема, а просто складывать данные в
системный буфер. Аналогично,
процесс, принимающий данные, ожидает, пока ему передадут данные.
Иными словами, все передачи данных неразрывно связаны с синхронизацией.
\item Синхронизация, не сопровождающаяся передачей данных, просто лишена
смысла -- процессы, не имеющие разделяемых структур данных, совершенно
независимы и не имеют ни критических точек, ни нереентерабельных модулей.
\end{itemize}

Концепция гармонически взаимодействующих процессов очень привлекательна с
теоретической точки зрения и позволяет легко писать правильные программы.
Однако часто по соображениям производительности оказывается невозможно
отказаться от разделяемой памяти. В этом смысле разделяемая память
напоминает предмет ненависти структурных программистов -- оператор \verb"goto".
И то, и другое является потенциальным источником ошибок и проблем, но часто
без них оказывается нельзя обойтись.

В современных системах реализован целый ряд средств, которые осуществляют
передачу данных одновременно с синхронизацией:
\termin{почтовые ящики}{mailboxes}
в системах линии \sysname{RSX-11} - \sysname{VMS}, \termin{трубы}{pipes}\footnote{В
русскоязычной литературе их часто называют программными каналами} в
\sysname{UNIX}, \termint{рандеву}{rendesvous}{свидание} в языке \progname{Ada},
транспьютерные линки и т.д. Они будут обсуждаться в разделе \ref{IPC}.

