8.4. P/V-системы

Р- и V-операции над семафорами впервые введены Дейкстрой [79] для решения проблем синхронизации в системах параллельных процессов. Как таковые они могут использоваться для моделирования синхронизации и связи таким же образом, как и сети Петри. Патил использовал этот подход, когда определяй задачу о курильщиках сигарет, чтобы показать ограниченность систем, которые могут использовать только Р- и V-операции между процессами. P/V-системы тем не менее популярны, и поэтому имеется много литературы по вычислительной технике, в которой обсуждаются или применяются эти операции, например, [44, 179].

В разд. 3.4.8 показано, что Р- и V-операции можно промоделировать с помощью сетей Петри. Доказательство Патила [2331 свидетельствует о том, что это включение собственное: существуют задачи (например, задача о курильщиках сигарет), которые можно решить в сетях Петри, но нельзя с использованием только Р- и V-операций. Однако P/V-системы являются достаточно мощным средством, чтобы включать модели графов вычислений [177] и модели конечных автоматов.

Чтобы преобразовать конечный автомат в P/V-систему, мы используем для моделирования каждого состояния автомата

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

Рис. 8.5. Конечный автомат.

Рис. 8.6 иллюстрирует преобразование конечного автомата, изображенного на рис. 8.5. Семафоры первоначально равны нулю, кроме семафора начального состояния, который инициализируется единицей.

Для преобразования графа вычислений в P/V-систему каждой дуге графа ставим в соответствие семафор Значением семафора будет число элементов данных, ожидающих в очереди для этой дуги. Таким образом, первоначально значением семафора будет Для каждого узла в графе вычислений создается процесс. Процесс узла сначала выполняет -операций над семафорами для всех дуг направленных в Этим обеспечивается то, что каждая очередь будет содержать не менее элементов данных. Затем, поскольку каждая -операция уменьшает семафор, а правильным результатом является только уменьшение на то мы выполняем -операций над чтобы восстановить правильное значение Мы завершаем процесс узла выполняя -операций над семафором для каждой дуги направленной из узла

Это преобразование проиллюстрировано на рис. 8.7 для узлов графа вычислений, приведенного на рис. 8.2.

Отметим, что граф вычислений может проверять и осуществлять ввод из нескольких источников за один шаг, тогда как P/V-системы

Рис. 8.6. P/V-система для конечного автомата на рис. 8.5.

могут проверять и осуществлять ввод из нескольких источников только с помощью последовательности проверок и вводов из отдельных источников. Неспособность к проверке и вводу из нескольких источников одновременно является ключевым моментом доказательства Патила ограниченности P/V-систем. Проблема состоит в том, что пока вы захватываете один ресурс, другой процесс может захватить второй ресурс, что приводит к тупику. Такой проблемы для графов вычислений не существует, так как источники не используются совместно процессами — не может быть двух узлов, разделяющих входные дуги. Это замечание существенно для построения P/V-системы, которая не попадала бы в тупик (завершалась) до тех пор, пока соответствующий граф вычислений не завершится.

Добавление P/V-систем к нашей иерархии моделей приводит ее к виду, изображенному на рис. 8.8.