![]() |
5.2. Регулирующие предикатыСлово предикат означает то же, что условие. Термин этот принят в математической логике. Введенные нами логические операции (см. § 2.7) проверяют выполнение условий или, как говорят в логике, определяют логическое значение предиката. Описывая ниже алгоритмы, совместно преобразующие один общий операнд, сущность используемых при этом приемов будем пояснять с помощью семантических схем. Для операторных алгоритмов эти схемы будут отражать и их структуру. Для записи семантических схем используем язык схем, введенный в § 4.8. Характер этой книги вынуждает меня вместо строгих доказательств ограничиться содержательными рассуждениями и примерами. Как одно из средств координации алгоритмических процессов нам потребуется один тип операции, который мы сейчас объявим.
Пусть,
1) Если
Этот алгоритм осуществляет тождественное преобразование буфера
5) Ожидать
не влиял бы на алгоритмический процесс, если условие
Рассмотрим теперь случай, когда n алгоритмов А1, А2, ... , Аn обрабатывают операнд, в котором подконструкция
Такую совокупность условий будем называть системой регулирующих предикатов n-го порядка.
С помощью системы регулирующих предикатов n-го порядка можно обеспечить бесконфликтное обращение алгоритмов к буферу ![]()
В этих схемах алгоритмов Защитой от конфликтов являются операции "Ожидать". Только в приказах, которые следуют за приказами, содержащими эту операцию, могут стоять приказы, обращающиеся к буферу, и последним по порядку выполнения является приказ, изменяющий так состояние буфера, что право обращения к нему получает один из остальных алгоритмов. Регулирующие предикаты взаимно-однозначно соответствуют алгоритмам. В принципе, число алгоритмов может быть меньше порядка системы регулирующих предикатов. В этом случае взаимно-однозначное соответствие должно существовать между множеством алгоритмов и некоторым подмножеством регулирующих предикатов. Если внимательно проследить за процессом выполнения алгоритмов, то можно заметить, что каждый алгоритм может разрешать обращение к буферу другому, запрещая такое обращение себе. При этом нужно иметь в виду, что алгоритмы могут иметь условные приказы, которые приводят к разветвлению процесса выполнения данного алгоритма и могут иметь циклический характер, при котором происходит возврат к уже выполненным один или несколько раз приказам. В процессе выполнения каждого алгоритма до обращения к буферу должна быть обеспечена невозможность одновременного обращения к буферу другого алгоритма. Она обеспечивается тем, что обращению к буферу предшествует (хотя, может быть, не непосредственно) приказ ожидания.
На рис. 5.1 схематически показан совокупный процесс выполнения алгоритмов А1, А2, А3 в предположении, что начальное состояние буфера ![]() Рис. 5.1. Схема совместного выполнения трех алгоритмов, имеющих регулируемый буфер Если бы одна и та же группа совместно работающих алгоритмов пользовалась не одним, а двумя буферами (каждый со своей системой регулирующих предикатов), то существовала бы возможность того, что все алгоритмы впадут в ожидание и процесс остановится без того, чтобы хотя бы один алгоритм достиг отсылки типа "стоп". Это явление называют схватыванием, или клинчем. При разработке алгоритмов его предусмотреть или исключить трудно, и оно считается нежелательным. Но простейшие примеры схватывания привести легко.
Рассмотрим опять три алгоритма; пусть
1) Ожидать второй - с приказа
1) Ожидать а третий - с приказа
1) Ожидать
Пусть, кроме того, начальное состояние буферов таково, что для них выполняются условия
Заметим, что если бы начальное состояние буферов было таково, что выполняются условия
О любых нескольких алгоритмах, имеющих общий буфер, принято говорить, что они связаны этим буфером. О системе предикатов n-го порядка, регулирующих обращения к буферу
Мы рассматриваем достаточно общий случай, когда каждому алгоритму, соответствует только один из регулирующих предикатов, заданных на буфере Существуют два очень важных вида связи между алгоритмами и регулирующими предикатами:
Каждый из этих случаев допускает два варианта:
Соответствие "алгоритм - предикат" однозначное, а "предикат - алгоритм" не однозначное. Два (или более) алгоритма, соответствующие одному и тому же предикату, называются сопряженными относительно указанного предиката. Открытые буферы позволяют вводить в операнд, в то время когда ни один алгоритм к этим буферам не обращается, воздействия из внешней среды. Ясно, что в теории роботов открытые буферы играют существенную роль. Кроме того с их помощью можно обеспечить "одновременный" запуск нескольких алгоритмов. Например, представим себе, что в начале каждого из трех алгоритмов, приведенных на с. 83, стоял бы приказ следующего вида: 0) Ждать
![]()
где 100)
![]()
и, таким образом, остановка алгоритма будет реализована как ожидание предиката " |
![]()
|
|||
![]() |
|||||
© ROBOTICSLIB.RU, 2001-2019
При копировании материалов проекта обязательно ставить ссылку на страницу источник: http://roboticslib.ru/ 'Робототехника' |