Формулировка задачи
Формулировка задачи
| Я что-то не вижу пивного ларька. Должно быть, его Успели снести за ночь. Б. Гребенщиков |
Чтобы понять, какие же методики применимы для взаимодействия параллельно исполняющихся нитей, давайте более четко сформулируем задачу. Для этого нам также надо ввести некоторое количество терминов. Кроме того, нам придется высказать ряд соображений, часть которых может показаться читателю банальностями.
Установим, что для каждой из нитей создается иллюзия строго последовательного исполнения (например, обработчик прерывания может создать для основного потока программы такую иллюзию, аккуратно сохраняя при вызове и восстанавливая при завершении все регистры процессора). Если для какой-то из нитей это условие не всегда соблюдается, мы будем считать ее двумя или большим числом различных нитей. Если это условие не соблюдается никогда, мы имеем дело с процессором нефон-неймановской архитектуры.
Общепринятое название для взаимодействия между различными нитями — асинхронное взаимодействие, в противоположность синхронному взаимодействию между различными модулями последовательно исполняемой программы.
Если нить работает только с объектами (под объектом мы, в данном случае, понимаем не только группу переменных в оперативной памяти или объект в смысле ООП, но и физические объекты, например управляемые компьютером внешние устройства), состояние которых не может быть изменено другими нитями, проблемы взаимодействия, да и самого взаимодействия, как такового, не существует.
Если нить работает с объектами, состояние которых вообще не подвергается модификации, например, с кодом или таблицами констант, проблемы также нет. Проблема возникает тогда и только тогда, когда модификации подвергается объект, разделяемый несколькими нитями. При этом для возникновения проблемы достаточно, чтобы только одна нить занималась модификацией, а остальные нити считывали состояние объекта.
Интервал, в течение которого модификация нарушает целостность разделяемой структуры данных, и, наоборот, интервал, в течение которого алгоритм нити полагается на целостность этой структуры, называется критической секцией. Задача написания корректной многопоточной программы, таким образом, может решаться двумя способами: либо искоренением критических секций из всех используемых алгоритмов, либо обеспечением гарантии того, что никакие две нити никогда одновременно не войдут в критическую секцию, связанную с одним и тем же разделяемым объектом. Наличие в программе критической секции с негарантированным исключением и есть ошибка соревнования, которая рано или поздно сработает.
Полное искоренение критических секций из кода требует глубокой переработки всех алгоритмов, которые используются для работы с разделяемыми данными. Результат такой переработки мы видели в примере 5.2: странная, на первый взгляд, двойная загрузка регистра в настроенной записи PLT в этом примере обусловлена именно желанием избежать проблем при параллельной настройке одной и той же записи двумя разными нитями (в качестве упражнения читателю предлагается разобраться, в каком порядке интерпретатор модифицирует запись, и как выглядит промежуточный код). У автора нет примеров, демонстрирующих невозможность такой переработки в обшем случае, но очевидно, что даже к крайне простым алгоритмам она совершенно не применима на практике.
Второй путь — предоставление гарантий взаимоисключения (mutual exclusion) — также непрост, но, в отличие от первого, практически реализуем и широко применяется.
Примечание
Примечание
Важно подчеркнуть, что сокращение времени, которое каждая из нитей проводит в критических секциях, хотя и полезно, со многих точек зрения, в частности с точки зрения улучшения масштабируемости алгоритма, само по себе оно проблемы решить не может. Без гарантии взаимоисключения, сокращение критического времени лишь понижает вероятность срабатывания ошибки соревнования (и, в частности, затрудняет поиск такой ошибки при тестировании), но не исправляет эту ошибку.
Группа операций модификации разделяемой структуры данных, которая происходит атомарно (неделимо), не прерываясь никакими другими операциями с той же структурой данных, называется транзакцией. В разд. Мониторы и серверы транзакций мы увидим более радикальное определение термина "транзакция" как группы операций, которые всегда либо происходят все вместе, либо не происходят вообще, даже если во время попытки их выполнения случится общесистемный сбой. Понятно, что для реализации так понимаемых транзакций одного только взаимоисключения недостаточно.
Программный модуль, внутри которого имеется хотя бы одна критическая секция, для которой не обеспечено взаимное исключение, называется нереентерабельным. Вызов процедур такого модуля из различных нитей приведет к ошибкам соревнования и допустим лишь при условии, что вызывающая программа реализует взаимное исключение самостоятельно. Соответственно, модуль, в котором таких секций нет, или который сам обеспечивает взаимное исключение для них, называется реентерабельным (от англ, re-enterable — способный к повторному вхождению) или реентрантным (reentrant). В современной англоязычной литературе часто также употребляются термины thread-unsafe (для обозначения нереентерабельных процедур) и thread-safe (соответственно, для реентерабельных).
Рассмотрим простейший случай разделяемого объекта: флаговую переменную, которая может принимать значения True и False. Такая переменная, в частности, может использоваться для реализации взаимного исключения в секции, работающей с более сложной структурой данных.
Если в критической секции не находится ни одной нити, переменная равна False, иначе — True. При входе в секцию нам необходимо проверить значение переменной и, если блокируемый участок свободен, присвоить ей True. Данный пример любопытен не только своей простотой, но и тем, что совмещает в себе оба типа критических секций: изменение разделяемых данных и анализ данных, которые могут параллельно модифицироваться кем-то еще.
Наивный способ работы с такой переменной приведен в примере 7.1 (пример реализован на паскалеподобном псевдокоде. Операторы parbegin/parend символизируют параллельное исполнение заключенных между ними операторов). Казалось бы, трудно представить себе более простую программу, однако именно благодаря простоте легко понять, что она никуда не годится: проверка флага и его установка реализуются двумя различными операторами, в промежутке между которыми другой процесс может получить управление и также установить флаговую переменную! Окно, в котором происходит соревнование, составляет всего две-три команды, но при попадании обоих процессов в это окно мы получаем как раз то, чего стремились избежать: оба процесса могут войти в критическую секцию одновременно.
