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

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

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

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

Предположим, у нас есть две последовательности действий, назовем их A и B. Разложим их на атомарные операции:

Как эти последовательности могут быть выполнены при наличии одного вычислителя?

Самый простой случай - выполняется полностью последовательность A, затем последовательность B. Такой вариант может возникнуть, например, при кооперативной многозадачности, когда A не желает возвращать управление до самого окончания работы:

Другой вариант, тоже несложный, - атомарные операции обеих последовательностей выполняются поочередно:

Число вариантов чередования операций A_i и B_j достаточно велико (любители математики могут оценить его самостоятельно). Как мы убедились в прошлой статье, некоторые из таких вариантов при определенных условиях могут приводить к некорректным результатам.

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

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

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

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

Некоторую помощь в первой задаче может оказать применение условий Бернстайна.

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

Введем некоторые обозначения. Назовем нашу последовательность действий P, набор ее входных переменных - R(P) (от слова read), а набор выходных переменных - W(P) (от слова write). В этом случае условия Бернстайна для двух последовательностей действий P и Q выглядят следующим образом:

Если:

то выполнение P и Q детерминировано.

А теперь - две новости. Как обычно, одна плохая, другая хорошая.

Начну с плохой. Рассмотрим условия Бернстайна внимательнее. Первое условие требует, чтобы последовательности не пытались записывать данные в одни и те же выходные переменные. Второе и третье требуют, чтобы одна последовательность не пыталась записывать данные в выходную переменную, которая одновременно является входной для другой последовательности. Если все эти условия выполняются, это равносильно тому, что P и Q не взаимодействуют. Мы и без этих условий догадывались, что изолированные процессы не должны мешать друг другу.

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

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

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

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

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

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

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

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

и

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

Примитивы для входа в критическую секцию могут быть реализованы либо чисто программно, либо с аппаратной поддержкой процессора. В случае, если за доступ к ресурсу конкурируют лишь два процесса, можно воспользоваться алгоритмом Деккера или более совершенным алгоритмом Петерсона. Более общим является Алгоритм булочной (Bakery algorithm), который может применяться к любому количеству процессов. Приводить здесь эти алгоритмы я не буду, желающие без труда найдут их в любом учебнике по операционным системам (например, здесь и здесь).

Некоторые достаточно развитые процессоры имеют специальные атомарные инструкции типа Test-and-Set (проверить значение переменной с одновременной установкой нового значения) или Swap (обменять значения двух переменных между собой). Они существенно упрощают реализацию примитивов входа в критическую секцию. В более простых микропроцессорах и микроконтроллерах, в которых программы обычно выполняются автономно (без поддержки операционной системы), такие инструкции, как правило, отсутствуют.

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

Примитивы выхода из критической секции тривиальны.