Механизмы, основанные на синхронизации
Наиболее известный и элементарный механизм, основанный на синхронизации, - это семафор, средство блокировки для управления распределенными ресурсами. Семафор - это объект с двумя операциями: reserve (занять) и free (освободить), традиционно обозначаемыми P и V, но мы предпочитаем использовать содержательные имена. В каждый момент времени семафор либо занят некоторым клиентом, либо свободен. Если он свободен и клиент выполняет reserve, то семафор занимается этим клиентом. Если клиент, занявший семафор, выполняет free, то семафор становится свободным. Если семафор занят некоторым клиентом, а новый клиент выполняет reserve, то он будет ждать, пока семафор освободится. Эта спецификация отражена в следующей таблице:
| reserve | Занимается мной | Я жду | |
| free | Становится свободным |
|
Предполагается, что события, соответствующие пустым клеткам таблицы, не происходят, они могут рассматриваться как ошибки или как не вызывающие изменений. |
Правила захвата семафора после его освобождения, когда этого события ожидают несколько клиентов, могут быть частью спецификации семафора или вовсе не задаваться. (Обычно для клиентов выполняется свойство равнодоступности (fairness), гарантирующее, что никто не будет ожидать бесконечно, если получающий доступ к семафору обязательно его освобождает).
Это описание относится к бинарным семафорам. Целочисленный вариант допускает наличие одновременного обслуживания до n клиентов для некоторого целого n>0.
Хотя семафоры используются во многих практических приложениях, они сейчас считаются средствами низкого уровня для построения больших надежных систем. Но они дают хорошую отправную точку для обсуждения усовершенствованных методов.
Критические интервалы (critical regions) представляют более абстрактный подход. Критический интервал - это последовательность инструкций, которая может выполняться в каждый момент не более чем одним клиентом. Для обеспечения исключительного доступа к объекту a можно написать нечто вроде:
hold a then ... Операции с полями a ...end. Здесь критический интервал выделен ключевыми словами then... end. Только один клиент может выполнять критический интервал в каждый момент, другие клиенты, выполняющие hold, будут ждать.
Большей части приложений требуется общий вариант - условный критический интервал (conditional critical region), в котором выполнение критического интервала подчинено некоторому логическому условию. Рассмотрим некоторый буфер, разделяемый производителем, который может только писать в буфер, если тот не полон, и потребителем, который может только читать из буфера, если тот не пуст. Они могут использовать две соответствующие схемы:
hold buffer when not buffer.full then "Записать в буфер, сделав его непустым" end hold buffer when not buffer.empty then "Прочесть из буфера, сделав его неполным" endТакое взаимодействие между входным и выходным условиями требует введения утверждений и придания им важной роли в синхронизации. Эта идея будет развита далее в этой лекции.
Другим хорошо известным механизмом синхронизации, объединяющим понятие критического интервала с модульной структурой некоторых современных языков программирования, являются мониторы (monitor). Монитор - это программный модуль, похожий на модули Modula или Ada. Основной механизм синхронизации прост: взаимное исключение достигается на уровне процедур. В каждый момент времени только один клиент может выполнять процедуру монитора.
Интересно также понятие "путевого выражения" (path expression). Путевое выражение задает возможный порядок выполнения процессов. Например, выражение:
init ; (reader* | writer)+ ; finishописывает следующее поведение: вначале активизируется процесс init, затем активным может стать один процесс writer или произвольное число процессов reader; это состояние может повторяться конечное число раз, затем приходит черед заключительного процесса finish. В записи выражения звездочка (*) означает произвольное число параллельных экземпляров, точка с запятой (;) - последовательное применение, символ черты (|) - "или-или", (+) - любое число последовательных повторений.
Часто цитируемый аргумент в пользу путевого выражения заключается в том, что они задают процессы и синхронизацию раздельно, устраняя помехи, возникающие между описанием отдельных алгоритмических задач и составлением расписания их выполнения.
| Еще одна категория методов для описания синхронизации основана на анализе множества состояний, через которое может проходить система или ее компонент, и переходов между этими состояниями. В частности, сети Петри основаны на графическом описании таких переходов. Хотя такие методы достаточно понятны для простых устройств, они быстро приводят к комбинаторному взрыву числа состояний и переходов, и трудны для иерархического проектирования (независимой спецификации подсистем, а затем рекурсивного вложения их спецификаций в большие системы). Поэтому они вряд ли применимы к большим эволюционирующим программным системам. |