Формулировка задачи
Группа операций модификации разделяемой структуры данных, которая происходит атомарно (неделимо), не прерываясь никакими другими операциями с той же структурой данных, называется транзакцией. В разд. "Мониторы и серверы транзакций" мы увидим более радикальное определение термина "транзакция" как группы операций, которые всегда либо происходят все вместе, либо не происходят вообще, даже если во время попытки их выполнения случится общесистемный сбой. Понятно, что для реализации так понимаемых транзакций одного только взаимоисключения недостаточно.
Программный модуль, внутри которого имеется хотя бы одна критическая секция, для которой не обеспечено взаимное исключение, называется нереентерабельным. Вызов процедур такого модуля из различных нитей приведет к ошибкам соревнования и допустим лишь при условии, что вызывающая программа реализует взаимное исключение самостоятельно. Соответственно, модуль, в котором таких секций нет, или который сам обеспечивает взаимное исключение для них, называется реентерабельным (от англ, re-enterable – способный к повторному вхождению) или реентрантным (reentrant). В современной англоязычной литературе часто также употребляются термины thread-unsafe (для обозначения нереентерабельных процедур) и thread-safe (соответственно, для реентерабельных).
Рассмотрим простейший случай разделяемого объекта: флаговую переменную, которая может принимать значения True и False. Такая переменная, в частности, может использоваться для реализации взаимного исключения в секции, работающей с более сложной структурой данных.
Если в критической секции не находится ни одной нити, переменная равна False, иначе – True. При входе в секцию нам необходимо проверить значение переменной и, если блокируемый участок свободен, присвоить ей True. Данный пример любопытен не только своей простотой, но и тем, что совмещает в себе оба типа критических секций: изменение разделяемых данных и анализ данных, которые могут параллельно модифицироваться кем-то еще.
Наивный способ работы с такой переменной приведен в примере 7.1 (пример реализован на паскалеподобном псевдокоде. Операторы parbegin/parend символизируют параллельное исполнение заключенных между ними операторов). Казалось бы, трудно представить себе более простую программу, однако именно благодаря простоте легко понять, что она никуда не годится: проверка флага и его установка реализуются двумя различными операторами, в промежутке между которыми другой процесс может получить управление и также установить флаговую переменную! Окно, в котором происходит соревнование, составляет всего две-три команды, но при попадании обоих процессов в это окно мы получаем как раз то, чего стремились избежать: оба процесса могут войти в критическую секцию одновременно.
Пример 7.1. Наивная реализация взаимного исключения на основе флаговой переменной.
program флаг; var flag: Boolean; procedure процесс один; begin while True do begin while flag do; flag: = True; критическая секция 1; flag: = False; … end end; procedure процесс два; begin while True do begin while flag do; flag: = True; критическая секция 2; flag: = False; end end; oegin flag: = False; parbegin процесс один; процесс два; parend еnd.