concurrent.tex

\chapter{Параллельное программирование}
\label{ch:concurrent}

\lstset{language=,extendedchars=false,showspaces=true}





\section{Программирование с разделяемыми переменными}


\subsection{Неделимые действия и операторы ожидания}

Цель синхронизации --- предотвратить нежелаемые чередования неделимых действий,
выполняемых отдельными процессами. Это осуществляется путем объединения
мелкомодульных неделимых операций в крупномодульные (составные) действия или
задержки выполнения процесса до достижения программой состояния,
удовлетворяющего некоторому предикату. Первая форма синхронизации называется
\emph{взаимное исключение}; вторая --- \emph{условной синхронизацией}.


\subsubsection{Мелкомодульная неделимость}

\emph{Мелкомодульное} неделимое действие --- это действие, реализуемое
непосредственно аппаратным обеспечением, на котором выполняется программа.

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

\lstset{caption=}
\begin{lstlisting}
  int y = 0, z = 0;
  co
    x = y + z;
  //
    y = 1; z = 2;
  oc;
\end{lstlisting}

Если выражение \texttt{x = y + z} реализовано загрузкой значения $y$ в регистр и
последующим прибавлением значения $z$, то конечными значениями переменной $x$
могут быть 0, 1, 2 или 3.

Предполагается, что машины обладают следующими характеристиками.
\begin{itemize}
  \item Значения базовых типов (например \texttt{int}) хранятся в элементах
    памяти (например, словах), которые считываются и записываются неделимыми
    операциями.
  \item Значения обрабатываются так: их помещают в регистры, там к ним применяют
    операции и затем записывают результаты обратно в память.
  \item Каждый процесс имеет собственный набор регистров. Это реализуется или
    путем предоставления каждому процессу отдельного набора регистров, или путем
    сохранения и восстановления значений регистров при выполнении различных
    процессов. (\emph{Переключение контекста}).
  \item Любые промежуточные результаты, появляющиеся при вычислении сложных
    выражений, сохраняются в регистрах или областях памяти, принадлежащих
    исполняемому процессу, например, в стеке.
\end{itemize}

В этой модели машины, если выражение $e$ в одном процессе не обращается к
переменной, измененной другим процессом, вычисление выражения всегда будет
неделимой операцией, даже если для этого необходимо выполнить несколько
мелкомодульных действий. Это происходит потому, что при вычислении выражения $e$
ни одно значение, от которого зависит $e$, не изменяет своего значения, и ни
один процесс не может видеть временные значения, которые создаются при
вычислении выражения. Аналогично, если присваивание \texttt{x = e} в одном
процессе не ссылается на переменные, изменяемые другим процессом (например,
ссылается только на локальные переменные), то выполнение присваивания будет
неделимой операцией.

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

\textbf{Условие ``не больше одного''}. \emph{Критической ссылкой} в выражении
называется ссылка переменную, изменяемую другим процессом. Предположим, что
любая критическая ссылка --- это ссылка на простую переменную, которая хранится
в элементе памяти и может быть считана и записана атомарно. Оператор
присваивания \texttt{x = e} удовлетворяет условию ``не больше одного'', если
либо выражение $e$ содержит не более одной критической ссылки, а переменная $x$
не считывается другим процессом, либо выражение $e$ не содержит критических
ссылок, а другие процессы могут считывать переменную $x$.

Если оператор присваивания удовлетворяет требованию условия ``не больше
одного'', то выполнение оператора присваивания бутет \emph{казаться} неделимой
операцией, поскольку одна единственная разделяемая переменная в выражении будет
записываться или считываться только один раз. Например, если выражение $e$ не
содержит критических ссылок, а переменная $x$ --- простая переменная, читаемая
другими процессами, то они не смогут распознать, вычисляется ли выражение
неделимым образом. Аналогично, если $e$ содержит одну критическую ссылку, то
процесс, выполняющий присваивание, не сможет различить, каким образом изменяется
значение переменной; он увидит только некоторое конечное значение.

\begin{lstlisting}
  int x = 0, y = 0;
  co x = x + 1; // y = y + 1; oc;
\end{lstlisting}

\begin{lstlisting}
  int x = 0, y = 0;
  co x = y + 1; // y = y + 1; oc;
\end{lstlisting}


\subsubsection{Задание синхронизации: оператор ожидания}

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

Неделимые операции задаются с помощью скобок $\langle$ и $\rangle$. Например,
$\langle e\rangle$ указывает, что выражение $e$ должно быть вычислено неделимым
образом.

Синхронизация определяется с помощью оператора \texttt{await}:

\begin{lstlisting}[mathescape]
  $\langle$await (B) S;$\rangle$
\end{lstlisting}

Булево выражение задает \emph{условие задержки} (delay condition), а $S$ --- это
список последовательных операторов, завершение которых гарантировано.

Пример:
\begin{lstlisting}[mathescape]
  $\langle$await (s > 0) s = s - 1;$\rangle$
\end{lstlisting}

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

Как видно, общая форма оператора \texttt{await} определяет как взаимное
исключение, так и синхронизацию по условию. Для определения только взаимного
исключения можно использовать сокращенную форму оператора \texttt{await}:

\begin{lstlisting}[mathescape]
  $\langle$S;$\rangle$
\end{lstlisting}

Если последовтельность $S$ --- это одиночный оператор присваивания,
удовлетворяющее условию ``не больше одного'', или если последовательность $S$
реализована одной машинной инструкцией, то $S$ будет выполнена как неделимая;
таким образом $\langle S;\rangle$ имеет тот же эффект, что и $S$.

Для задания только условной синхронизации сократим оператор \texttt{await} так:

\begin{lstlisting}[mathescape]
  $\langle$await (B);$\rangle$
\end{lstlisting}

Если выражение $B$ удовлетворяет условию ``не больше одного'', как в данном
примере, то выражение $\langle$\texttt{await (B);}$\rangle$ может быть
реализовано как

\begin{lstlisting}
  while (not B);
\end{lstlisting}

Это пример так называемого \emph{цикла ожидания} (spin loop).

\emph{Безусловное} неделимое действие --- это действие, которе не содержит в
теле условия задержки $B$. Такое действие может быть выполнено немедленно,
кончено, в соответствии с требованием неделимости его выполнения. Аппаратно
реализуемые (мелкомодульные) действия, выражения в угловых скобках и операторы
\texttt{await}, в которых условие опущено или является константой ``истина'',
являются безусловными неделимым действиями.

\emph{Условное} неделимое действие --- это оператор \texttt{await} с условием
$B$. Такое условие не может быть выполнено, пока условие $B$ не станет
истинным. Если $B$ ложно, оно может стать истинным только в результате действий
других процессов. Таким образом, процесс, ожидающий выполнения условного
неделимого действия, может оказаться задержанным непредсказуемо долго.



\subsection{Стратегии планирования и живучести}

Большинство свойст живучести зависит от \emph{справедливости (fairness)},
связанной с гарантиями того, что каждый процесс получает шанс на продолжение
выполнения независимо от действий других процессов.

\textbf{Безусловная справедливость} (unconditional fairness). Стратегия
планирования \emph{безусловно справедлива}, если любое подходящее безусловное
неделимое действие в конце концов выполняется.

\textbf{Справедливость в слабом смысле} (weak fairness). Стратегия планирования
\emph{справедлива в слабом смысле}, если: 1) она безусловно справедлива, и
2) каждое подходящее условное неделимое действие в конце концов выполняется,
если его условие становится и затем остается истинным, пока его видит процесс,
выполняющий условное неделимое действие.

\textbf{Справедливость в сильном смысле} (strong fairness). Стратегия
планирования \emph{справедлива в сильном смысле}, если 1) она безусловно
справедлива, и 2) любое подходящее условное неделимое действие в конце концов
выполняется в предположении, что его условие бывает истинным бесконечно часто.





\section{Блокировки и барьеры}

\emph{Активное ожидание} --- реализация синхронизации, при которой процесс
циклически проверяет некоторое условие до тех пор, пока оно не станет
истинным. Достоинство синхронизации с активным ожиданием состоит в том, что для
ее реализации достаточно машинных инструкций современных процессоров. Активное
ожидание неэффективно при разделении процессора несколькими процессами (когда их
выполнение перемежается),но, когда каждый процесс выполняется на отдельном
процессоре, оно эффективно.


\subsection{Задача критической секции}

\emph{Задача критической секции} --- это одна из классических задач паралельного
программирования. В этой задаче $n$ процессов многократно выполняют сначала
критическую, а затем некритическую секцию кода. Критической секции предшествует
протокол входа, а следует за ней протокол выхода. Таким образом, предполагается,
что процесс имеет следующий вид:

\begin{lstlisting}
  process CS[i = 1 to n] {
    while (true) {
      протокол входа;
      критическая секция;
      протокол выхода;
      некритическая секция;
    }
  }
\end{lstlisting}

Каждая критическая секция является последовательностью операторов, имеющих
доступ к некоторому разделяемому объекту. Наша задача -- разработать протоколы
входа и выхода, удовлетворяющие следующим четырем свойствам:
\begin{enumerate}[(1)]
  \item \label{item:mutual-exclusion} \textbf{Взаимное исключение} (mutual
    exclusion). В любой момент времени только один процесс может выполнять свою
    критическую секцию.
  \item \label{item:livelocks-freedom} \textbf{Отсутствие взаимной блокировки
    (живая блокировка)} (freedom from livelocks). Если несколько процессов
    пытаются войти в свои критические секции, хотя бы один это осуществит.
  \item \label{item:delays-freedom} \textbf{Отсутствие излишних задержек}. Если
    один процесс пытается войти в свою критическую секцию, а другие выполняют
    свои некритические секции или завершены, первому процессу разрешается вход в
    критическую секцию.
  \item \label{item:starvation-freedom} \textbf{Возможность входа} (отсутствие
    голодания, freedom from starvation). Процесс, который пытается войти в
    критическую секцию, когда-нибудь это сделает.
\end{enumerate}

Первые три свойства являются свойствами безопасности, четвертое --- свойством
живучести.

Тривиальный способ решения задачи критической секции состоит в ограничении
каждой критической секции угловыми скобками, т.~е. в использовании безусловных
операторов \texttt{await}. Из семантики угловых скобок сразу следует условие
(\ref{item:mutual-exclusion}) -- взаимное исключение. Другие три свойства будут
удовлетворяться при безусловно справедливой стратегии планирования, поскольку
она гарантирует, что процесс, который пытается выполнить неделимое действие,
соответсвующее его критической секции, в конце концов это сделает, независимо от
других процессов. Однако при таком ``решении'' возникает вопрос о том, как
реализовать угловые скобки.

Реализация показана в листинге \ref{lst:critical-sec-largemodule}.

\lstset{label=lst:critical-sec-largemodule,
  caption=Задача критической секции: крупномодульное решение}
\begin{lstlisting}[mathescape]
  bool in1 = false, in2 = false;
  ## MUTEX: $\neg(in1 \land in2)$ -- глобальный инвариант

  process CS1 {
    while (true) {
      <await (!in2) in1 = true;>  /* вход */
      критическая секция;
      in1 = false;                /* выход */
      некритическая секция;
    }
  }

  process CS2 {
    while (true) {
      <await (!in1) in2 = true;>  /* вход */
      критическая секция;
      in2 = false;                /* выход */
      некритическая секция;
    }
  }
\end{lstlisting}



\subsection{Критические секции: активные блокировки}

В крупномодульном решении, приведенном в листинге
\ref{lst:critical-sec-largemodule}, используются две переменные. При обобщении
данного решения для $n$ процессов понадобятся $n$ переменных. Однако существует
только для интересующих нас состояния: или некоторый процесс находится в
критической секции, или ни одного там нет. Независимо от числа процессов, для
того, чтобы различить эти два состояния, достаточно одной переменной.

Пусть \texttt{lock} --- логическая переменная, которая показывает, находится ли
процесс в критической секции. Таким образом получим следующее условие:
\begin{equation*}
  lock == (in1 \lor in2)
\end{equation*}

Используя \texttt{lock} вместо \texttt{in1} и \texttt{in2}, можно реализовать
протоколы входа и выхода программы \ref{lst:critical-sec-largemodule} так, как
показано в листинге \ref{lst:critical-sec-lock}.

Преимущество протоколов входа и выхода, показанных в листинге
\ref{lst:critical-sec-lock}, по отношению к протоколам в листинге
\ref{lst:critical-sec-largemodule} совтоит в том, что их можно использовать для
решения задачи критической секции при любом числе процессов.

\lstset{label=lst:critical-sec-lock,
  caption=Критические секции на основе блокировок}
\begin{lstlisting}
  bool lock = false;

  process CS1 {
    while (true) {
      <await (!lock) lock = true;>  /* вход */
      критическая секция;
      lock = false;                 /* выход */
      некритическая секция;
    }
  }

  process CS2 {
    while (true) {
      <await (!lock) lock = true;>  /* вход */
      критическая секция;
      lock = false;                 /* выход */
      некритическая секция;
    }
  }
\end{lstlisting}



\subsubsection{``Проверить-установить''}

Использование переменной \texttt{lock} вместо \texttt{in1} и \texttt{in2},
показанное в листинге \ref{lst:critical-sec-lock}, очень важно, поскольку почти
у всех машин, особенно у мультипроцессоров, есть специальная инструкция для
реализации условных неделимых действий. Здесь применяется инструкция, называемая
``проверить-установить''.

Инструкция ``проверить-установить'' (\texttt{test-and-set}, \texttt{TS}) в
качестве аргумента получает разделяемую переменную \texttt{lock} и возвращает
логическое значение. В неделимом действии инструкция \texttt{TS} считывает и
сохраняет значение переменной \texttt{lock}, присваивает ей значение ``истина'',
а затем возрващает сохраненное предыдущее значение переменной
\texttt{lock}. Результат действия инструкции \texttt{TS} описывается следующей
функцией:

\lstset{caption=}
\begin{lstlisting}
  bool TS(bool lock) {
    < bool initial = lock;    /* сохранить начальное значение */
      lock = true;            /* установить lock */
      return initial; >       /* возвратить начальное значение */
  }
\end{lstlisting}

Используя инструкцию \texttt{TS}, можно реализовать крупномодульный вариант
программы \ref{lst:critical-sec-lock} по алгоритму, приведенному в листинге
\ref{lst:critical-sec-ts}. Использование блокирующей переменной, как в этом
алгоритме, обычно называется \emph{циклической блокировкой} (spin lock),
поскольку процесс постоянно повторяет цикл, ожидая снятия блокировки.

\lstset{label=lst:critical-sec-ts,
  caption=Критические секции на основе инструкции ``проверить и установить''}
\begin{lstlisting}
  bool lock = false;            /* разделяемая переменная */

  process CS[i = 1 to n] {
    while (true) {
      while (TS(lock)) skip;    /* протокол входа */
      критическая секция;
      lock = false;             /* протокол выхода */
      некритическая секция;
    }
  }
\end{lstlisting}

Программа в листинге \ref{lst:critical-sec-ts} имеет свойства
(\ref{item:mutual-exclusion}), (\ref{item:livelocks-freedom}) и
(\ref{item:delays-freedom}).

С другой стороны, выполнение свойства возможности входа
(\ref{item:starvation-freedom}) не гарантируется. Если используется справедливая
в сильном смысле стратегия планирования, то попытки процесса войти в критическую
секцию завершатся успехом, поскольку переменная \texttt{lock} бесконечно часто
будет принимать значение ``ложь''. При справедливой в слабом смысле стратегии
планирования, которая встречается чаще всего, процесс может навсегда зациклиться
в протоколе входа. Однако это может случиться, только если другие процессы все
время успешно входят в свои критические секции, чего на практике быть не
должно. Следовательно, решение в листинге \ref{lst:critical-sec-ts} должно
удовлетворять условию справедливой стратегии планирования.

Построенное решение с циклической блокировкой и аналогичные обладают свойством,
которое стоит запомнить:

\textbf{Протоколы выхода в решениях с циклической блокировкой}. В решении задачи
критической секции с циклической блокировкой протокол выхода должен просто
присваивать разделяемым переменным их начальные значения.



\subsubsection{``Проверить-проверить-установить''}

Хотя решение в листинге \ref{lst:critical-sec-ts} верно, эксперименты на
мультипроцессорных машинах показывают его низкую производительность, если
несколько процессов соревнуются за доступ к критической секции. Причина в том,
что каждый приостановленный процесс непрерывно обращается к разделяемой
переменной \texttt{lock}. Эта ``горячая точка'' вызывает \emph{конфликт при
обращении к памяти}, который снижает производительность модулей памяти и шин,
связывающих процессор и память.

К тому же инструкция \texttt{TS} при каждом вызове записывает значение в
\texttt{lock}, даже если оно не изменяется. Поскольку в мультипроцессорных
машинах с разделяемой памятью для уменьшения числа обращения к основной памяти
используются кэши, \texttt{TS} выполняется гораздо дольше, чем простое чтение
значения разделяемой переменной.

Затраты на обновление содержимого кэш-памяти и конфликты при обращении к памяти
можно сократить, заменив протокол входа на так называемый
``проверить-проверить-установить''. В нем процесс просто проверяет \texttt{lock}
до тех пор, пока не появится возможность выполнения \texttt{TS}.

\lstset{label=lst:critical-sec-check-check-set,
  caption=Критические секции на основе протокола
  ``проверить-проверить-установить''}
\begin{lstlisting}
  bool lock = false;            /* разделяемая блокировка */

  process CS[i = 1 to n] {
    while (true) {
      while (lock) skip;        /* протокол входа */
      while (TS(lock)) {
        while (lock) skip;
      }
      критическая секция;
      lock = false;             /* протокол выхода */
      некритическая секция;
    }
  }
\end{lstlisting}



\subsubsection{``Реализация операторов await''}

Любое решение задачи критической секции можно использовать для реализации
безусловного неделимого действия $\langle$\texttt{S};$\rangle$, скрывая
внутренние контрольные точки от других процессов. Пусть \texttt{CSenter} ---
входной протокол критической секции; а \texttt{CSexit} --- соответствующий
выходной. Тогда действие $\langle$\texttt{S};$\rangle$ можно реализовать так:
\lstset{caption=}
\begin{lstlisting}
  CSenter;
  S;
  CSexit;
\end{lstlisting}

Здесь предполагается, что все секции кода процессов, которые изменяют или
ссылаются на переменные, изменяемые в \texttt{S} (или изменяют переменные, на
которые ссылается \texttt{S}), защищены аналогичными входными и выходными
протоколами. В сущности, скобки $\langle$ и $\rangle$ заменены процедурами
\texttt{CSenter} и \texttt{CSexit}.

Приведенный вы ше образец кода можно использовать в качестве ``кирпичика'' для
реализации операторов $\langle$\texttt{await(B) S;}$\rangle$. Напомним, что
условное неделимое действие приостанавливает процесс, пока условие \texttt{B} не
станет истинным, после чего выполняется \texttt{S}. Когда начинается выполнение
\texttt{S}, условие \texttt{B} должно быть истинным. Чтобы обеспечить
неделимость всего действия, можно использовать протокол критической секции,
скрывая промежуточные состояния в \texttt{S}. Для циклической проверки условия
\texttt{B}, пока оно не станет истинным, можно использовать следующий цикл.

\lstset{caption=}
\begin{lstlisting}
  CSenter;
  while (!B) { CSexit; Delay; CSenter; }
  S;
  CSexit;
\end{lstlisting}

Здесь предполагается, что критические секции всех процессов, изменяющих
переменные, используемые в \texttt{B} или \texttt{S}, или использующих
переменные, изменяемые в \texttt{S}, защищены такими же протоколами входа и
выхода.

Если тело цикла выполняется, значит условие \texttt{B} было
ложным. Следовательно, единственный способ сделать условие \texttt{B} истинным
--- изменить в другом процессе значения переменных, входящих в это
условие. Предполагается, что все операторы, изменяющие эти переменные, находятся
в критических секциях, поэтому, ожидая, пока условие \texttt{B} выполнится,
нужно выйти из критической секции. Но для обеспечения неделимости вычисления
\texttt{B} и выполнения \texttt{S} перед повторным вычислением условия
\texttt{B} необходимо вновь войти в критическую секцию. Код \texttt{Delay} ---
некоторый код, замедляющий выполнение процесса. Он служит для сокращения
количества конфликтов обращения к памяти.



\subsection{Критические секции: решения со справедливой блокировкой}

Решения задачи критической секции с циклической блокировкой обеспечивают
взаимное исключение, отсутствие взаимных блокировок, активных тупиков и
нежелательных пауз. Однако для обеспечения свойства возможности входа
(\ref{item:starvation-freedom}) им необходима справедливая в сильном смысле
стратегия планирования. Как было сказано ранее, стратегии планирования,
применяемые на практике, являются справедливыми только в слабом
смысле. Маловероятно, что процесс, пытающийся войти в критическую секцию,
никогда этого не сделает, однако может случиться, что несколько процессов будут
без конца состязаться за вход. В частности, решения с циклической блокировкой не
управляют порядком, в котором несколько приостановленных процессов пытаются
войти в критические секции.

В данном разделе представлены три решения задачи критической секции со
справедливой стратегией планирования: алгоритм разрыва узла, поликлиники и
билета. Они зависят только от справедливой в слабом смысле стратегии
планирования, например от кругового (round-robin) планирования, при котором
каждый процесс периодически получает возможность выполнения, а условия задержки,
став истинными, остаются таковыми.


\subsubsection{Алгоритм разрыва узла}

Рассмотрим решение задачи критической секции для двух процессов (листинг
\ref{lst:critical-sec-largemodule}). Его недостаток в том, что оно не решает,
какой из процессов, пытающихся войти в критическую секцию, туда действительно
попадет. Например, один процесс может войти в критическую секцию, выполнить ее,
затем вернуться к протоколу входа и снова успешно войти в критическую
секцию. Чтобы решение было справедливым, должна соблюдаться очередность входа в
критическую секцию, если несколько процессов пытаются туда войти.

\emph{Алгоритм разрыва узла} (также называемый алгоритмом Питерсона) --- это
вариант протокола критической секции, который ``разрывает узел'', когда два
процесса пытаются войти в критическую секцию. Для этого используется
дополнительная переменная, которая фиксирует, какой из процессов вошел в
критическую секцию последним.

Чтобы пояснить алгоритм разрыва узла, вернемся к крупномодульной программе в
листинге \ref{lst:critical-sec-largemodule}. Сейчас цель --- реализовать
условные неделимые действия в протоколах входа с использованием только простых
переменных и последовательных операторов. Если мы по-прежнему ограничимся двумя
переменными, то, в зависимости от порядка установки значения переменной и
ожидания изменения, мы допускаем либо взаимную блокировку, либо не обеспечиваем
взаимное исключение.

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

Пусть \texttt{last} --- целочисленная переменная, которая показывает, какой из
процессов \texttt{CS1} и \texttt{CS2} начал выполнять протокол последним. Если
оба процесса пытаются войти в критические секции, т.~е. \texttt{it1} и
\texttt{it2} истинны, выполнение посленего из них приостанавливается. Это
приводит к крупномодульному решению, показанному в листинге
\ref{lst:breaking-knot-largemodule}.

\lstset{label=lst:breaking-knot-largemodule,
  caption=Алгоритм разрыва узла для двух процессов: крупномодульное решение}
\begin{lstlisting}
  bool in1 = false, in2 = false;
  int last = 1;

  process CS1 {
    while (true) {
      last = 1; in1 = true;     /* протокол входа */
      <await (!in2 or last == 2); >
      критическая секция;
      in1 = false;
      некритическая секция;
    }
  }

  process CS2 {
    while (true) {
      last = 2; in2 = true;     /* протокол входа */
      <await (!in1 or last == 1); >
      критическая секция;
      in2 = false;
      некритическая секция;
    }
  }
\end{lstlisting}

Алгоритм программы в листинге \ref{lst:breaking-knot-largemodule} очень близок к
мелкомодульному решению, для которого не нужны операторы \texttt{await}. В
частности, если все операторы \texttt{await} удовлетворяют условия ``не больше
одного'', то их можно реализовать в виде циклов активного ожидания. К сожалению,
операторы \texttt{await} в листинге \ref{lst:breaking-knot-largemodule}
обращаются к двум переменным, каждую из которых изменяет другой процесс. Однако
в данном случае нет необходимости в неделимом вычислении условий
задержки. Докажем это.

Предположим, процесс \texttt{CS1} вычисляет свое условие задержки и
обнаруживает, что оно истинно. Если \texttt{CS1} обнаружил, что \texttt{in2}
ложна, то теперь \texttt{in2} может быть истинной. Но в этому случае процесс
\texttt{CS2} только что присвоил переменной \texttt{last} значение 2;
следовательно, условие задержки остается истинным, если даже значение переменной
\texttt{in2} изменилось. Если обнаружено, что \texttt{last == 2} истинно, то
условие остается истинным, поскольку переменная \texttt{last} не изменится, пока
процесс \texttt{CS1} не выполнит свою критическую секцию. Итак, в обеих
ситуациях, если для процесса \texttt{CS1} условие окончания задержки истинно,
оно действительно истинно. (Аргументы для процесса \texttt{CS2} симметричны.)

Поскольку условие окончания задержки не обязательно вычислять неделимым образом,
каждый оператор \texttt{await} можно заменить циклом \texttt{while}, который
повторяется, пока условие окончания задержки ложно. Таким образом получаем
мелкомодульный алгоритм разрыва узла (листинг
\ref{lst:breaking-knot-smallmodule}).

\lstset{label=lst:breaking-knot-smallmodule,
  caption=Алгоритм разрыва узла для двух процессов: мелкомодульное решение}
\begin{lstlisting}
  bool in1 = false, in2 = false;
  int last = 1;

  process CS1 {
    while (true) {
      last = 1; in1 = true;     /* протокол входа */
      while (in2 and last == 1) skip;
      критическая секция;
      in1 = false;              /* протокол выхода */
      некритическая секция;
    }
  }

  process CS2 {
    while (true) {
      last = 2; in2 = true;     /* протокол входа */
      while (in1 and last == 2) skip;
      критическая секция;
      in2 = false;              /* протокол выхода */
      некритическая секция;
    }
  }
\end{lstlisting}

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

Пусть \texttt{in[1:n]} и \texttt{last[1:n]} --- целочисленные массивы. Значение
элемента \texttt{in[i]} показывает, какой этап выполняет процесс \texttt{CS[i]}.
Значение \texttt{last[j]} показывает, какой процесс последним начал выполнять
этап $j$. Эти переменные используются как показано в листинге
\ref{lst:breaking-knot-n}. Внешний цикл \texttt{for} выполняется \texttt{n-1}
раз. Внутренний цикл \texttt{for} процесса \texttt{CS[i]} проверяет все
остальные процессы. Процесс \texttt{CS[i]} ждет, если некоторый другой процесс
находится на этапе с равным или большим номером этапа, а процесс \texttt{CS[i]}
был последним процессом, достигшим этапа $j$. Как только этапа $j$ достигнет еще
один процесс, или все процессы ``перед'' процессом \texttt{CS[i]} выйдут из
своих критических секций, процесс \texttt{CS[i]} получит возможность выполняться
на следующем этапе. Таким образом, не более $n-1$ процессов могут пройти первый
этап, $n-2$ -- второй и так далее. Это гарантирует, что пройти все $n$ этапов и
выполнять свою критическую секцию процессы могут только по одному.

\lstset{label=lst:breaking-knot-n,
  caption=Алгоритм разрыва узла для $n$ процессов}
\begin{lstlisting}
  int in[1:n] = ([n] 0), last[1:n] = ([n] 0);

  process CS[i = 1 to n] {
    while (true) {
      for [j = 1 to n] {        /* протокол входа */
        /* запомним, что процесс i находится на этапе j и там является
           последним */
        last[j] = i; in[i] = j;
        for [k = 1 to n st i != k] {
          /* ждать, если процесс k находится на этапе с большим номером и
             процесс i был последним из прошедших на этап j */
          while (in[k] >= in[i] and last[j] == i) skip;
        }
      }
      критическая секция;
      in[i] = 0;                /* протокол выхода */
      некритическая секция;
    }
  }
\end{lstlisting}

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


\subsubsection{Алгоритм билета}

Следующее решение называется \emph{алгоритмом билета}, поскольку основано на
вытягивании билетов (номеров) и последующего ожидания очереди.

Пусть \texttt{number} и \texttt{next} --- целые переменные с начальными
значениями 1, а \texttt{turn[1:n]} --- массив целых с начальными значениями
0. Чтобы войти в критическую секцию, процесс \texttt{CS[i]} сначала присваивает
элементу \texttt{turn[i]} текущее значение \texttt{number} и увеличивает
значение \texttt{number} на 1. Чтобы процессы (посетители) получали уникальные
номера, эти действия должны выполняться неделимым образом. После этого процесс
\texttt{CS[i]} ожидает, пока значение \texttt{next} не станет равным полученному
им номеру. При завершении критической секции процесс \texttt{CS[i]} увеличивает
на 1 значение \texttt{next}, снова в неделимом действии.

Описанный протокол реализован в алгоритме, приведенном в листинге
\ref{lst:tickets-largemodule}. Поскольку значения \texttt{number} и
\texttt{next} считываются и увеличиваются в неделимых действиях, следующий
предикат будет глобальным инвариантом.

\lstset{caption=}
\begin{lstlisting}[mathescape]
  TICKET: $next > 0 \land$
    ($\forall i: 1 \le i \le n:$
      (CS[i] в своей критической секции) $\Rightarrow$
      (turn[i] == next) $\land$ (turn[i] > 0) $\Rightarrow$
      ($\forall j: 1 \le j \le n, j \ne i$: turn[i] $\ne$ turn[j]))
\end{lstlisting}

Последняя строка гласит, что ненулевые значения элементов массива \texttt{turn}
уникальны. Следовательно, только один \texttt{turn[i]} может быть равен
\texttt{next}, т.~е. только один процесс может находиться в критической
секции. Отсюда же следует отсутствие взаимоблокировок и ненужных задержек. Этот
алгоритм гарантирует возможность входа при стратегии планирования, справедливой
в слабом смысле, поскольку условие окончание задержки, ставшее истинным, таким и
остается.

\lstset{label=lst:tickets-largemodule,
  caption=Алгоритм билета: крупномодульное решение}
\begin{lstlisting}
  int number = 1, next = 1, turn[1:n] = ([n], 0);
  ## глобальный инвариант -- предикат TICKET (см. текст)

  process CS[i = 1 to n] {
    while (true) {
      <turn[i] = number; number = number + 1;>
      <await (turn[i] == next):>
      критическая секция;
      <next = next + 1;>
      некритическая секция;
    }
  }
\end{lstlisting}

Алгоритм в листинге \ref{lst:tickets-largemodule} содержит три крупномодульных
действия. Оператор \texttt{await} легко реализуется циклом с активным ожиданием,
поскольку в булевом выражении использована только одна разделяемая
переменная. Последнее неделимое действие, увеличение \texttt{next}, можно
реализовать с помощью обычных инструкций загрузки и сохранения, поскольку в
любой момент времени только один процесс выполняет протокол выхода. К сожалению,
первое неделимое действие (чтение значения \texttt{number} и его увеличение)
реализовать непросто.

У некоторых машин есть инструкции, которые возвращают старое значение переменной
и увеличивают или уменьшают ее в одном неделимом действии. Эти инструкции
выполняют именно то, что нужно для реализации алгоритма билета. В качестве
примера приведем инструкцию ``извлечь и сложить'' (\texttt{fetch-and-add},
\texttt{FA}), которая работает следующим образом:

\lstset{caption=}
\begin{lstlisting}
  FA(var, incr) {
    < int tmp = var;
      var = var + incr;
      return tmp; >
  }
\end{lstlisting}

\lstset{label=lst:tickets-smallmodule,
  caption=Алгорим билета: мелкомодульное решение}
\begin{lstlisting}
  int number = 1, next = 1, turn[1:n] = ([n], 0);

  process CS[i = 1 to n] {
    while (true) {
      turn[i] = FA(number, 1);  /* протокол входа */
      while (turn[i] != next) skip;
      критическая секция;
      next = next + 1;          /* протокол выхода */
      некритическая секция;
    }
  }
\end{lstlisting}

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

\lstset{caption=}
\begin{lstlisting}
  turn[i] = number; <number = number + 1;>
\end{lstlisting}

Переменная \texttt{number} гарантированно увеличивается правильно, но процессы
могут не получить уникальных номеров. Например, каждый из процессов может
выполнить первое присваивание примерно в одно и то же время и получить один и
тот же номер! Поэтому важно, чтобы оба присваивания выполнялись в одном
неделимом действии.

Нам уже известны два других способа решения задачи критической секции:
циклические блокировки и алгоритмы разрыва узла. Чтобы обеспечить неделимость
получения номеров, можно воспользоваться любым из них. Например, пусть
\texttt{CSenter} --- протокол входа критической секции, а \texttt{CSexit} ---
соответствующий протокол выхода. Тогда в программе \ref{lst:tickets-smallmodule}
инструкцию ``извлечь и сложить'' можно заменить следующей последовательностью.

\lstset{caption=}
\begin{lstlisting}
  CSenter;
  turn[i] = number;
  number = number + 1;
  CSexit;
\end{lstlisting}

Такой подход выглядит необычным, но на практике работает хорошо, особенно если
для реализации протоколов входа и выхода доступна инструкция типа
``проверить-установить''. При использовании инструкции ``проверить-установить''
процессы получают номера необязательно в соответствии с порядком, в котором они
пытаются это сделать, и теоретически процесс может зациклиться навсегда. Но с
очень высокой вероятностью каждый процесс получит номер, и большинство номеров
будут выбраны по порядку. Причина в том, что критическая секция в последнем
листинге очень коротка, и процесс не должен задерживаться в протоколе входа
\texttt{CSenter}. Основной источник задержек в алгоритме билета --- это
ожидание, пока значение в переменной \texttt{next} не станет равно значению
\texttt{turn[i]}.


\subsubsection{Алгоритм поликлиники}



\subsection{Барьерная синхронизация}

\subsubsection{Разделяемый счетчик}

\subsubsection{Флаги и управляющие процессы}

\subsubsection{Симметричные барьеры}



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

\subsection{Синтаксис и семантика}

\subsection{Основные задачи и методы}

\subsection{Задача об обедающих философах}

\subsection{Задача о читателях и писателях}

\subsection{Распределение ресурсов и планирование}




\lstset{language=C, extendedchars=true, showspaces=false}