|
условным временным оператором (ty )* , определим для каждого очередной момент времени сцепления инициатора по своему треку, задаваемый этим временным оператором. Получим множество }. Назовем его активным временным множеством. Это множество содержит по одному значению от каждого процесса, остановленного на элементарном операторе, содержащем временное условие продвижения инициатора. Определим очередное значение времени по формуле: 10 = т Ш ‘М 9(У г) (2.14) Последовательное применение формулы (2.14) строит упорядоченное множество где а 1 -линейный порядок на Т \ Докажем ряд его свойств. Для процесса Z' имеем множество Т и линейный порядок а 1 (* = 1,«). Рассмотрим множество Т и порядок а т на Г, полученный транзитивным замыканием порядков а 1. Утверждение 2. Множества Т 1 и Т равны. В самом деле, любой элемент t e T был определен по формуле (2.14) из множества элементы которого принадлежат Г 1 (/ = 1,и). Поскольку Г = UT‘( V i) , то они же принадлежат и Г. Следовательно, каждый элемент множества Т ‘ принадлежит и множеству Т. Аналогично доказывается, что если элемент принадлежит Г, то он же принадлежит и 7*. Таким образом, утверждение 2 доказано. Утверждение J. На упорядоченном множестве } г ',а '( сохраняются все порядки а* (/ = 1,я ). Рассмотрим множество Т с порядком а'. Возьмем два любых его элемента Д и t\. Пусть в соответствие с а 1 /'ъТогда, в соответствие с 106 |
4. Для определения порядка расчета операторов, принадлежащих разным процессам, важно знание отношения сцепления для операторов разных процессов с одинаковым значением времени {,. Таким образом, можно сформулировать следующий алгоритм определения порядка вычисления элементарных операторов для совокупности параллельных процессов. Пусть заданы треки процессов 2 Т(/ = 1,я): для всех i. Пусть текущее значение времени равно t и все элементарные операторы ti , у которых t Получим множество { ^ +1 . Назовем его активным временным множеством. Это множество содержит по одному значению от каждого процесса, остановленного на элементарном операторе, содержащем временное условие продвижения инициатора. Определим очередное значение времени по формуле: tQ= m m t‘J+l,(V i) (2.14) Последовательное применение формулы (2.14) строит упорядоченное множество (Т:, а/), где а 1 -линейный порядок на Т \ Докажем ряд его свойств. Для процесса Z1 имеем множество Т и линейный порядок а 1 (/ = \,п). Рассмотрим множество Т = \jT'(¥i) и порядок а 1 на Т, полученный транзитивным замыканием порядков а ‘. Утверждение 2. Множества Т ‘и Т равны. 97 В самом деле, любой элемент te T был определен по формуле (2.14) из множества к * 1) ’ элементы которого принадлежат 7" 1 (1 = \,п). Поскольку T=[)T‘(Vi), то они же принадлежат и Т. Следовательно, каждый элемент множества Т ‘ принадлежит и множеству Т. Аналогично доказывается, что если элемент принадлежит Г, то он же принадлежит и 74 Таким образом, утверждение 2 доказано. Утверждение 3^ На упорядоченном множестве (г r,a f) сохраняются все порядки а' (/ = \,п ). Рассмотрим множество Т с порядком а 1. Возьмем два любых его элемента t\ и fY Пусть в соответствие с a 1 Тогда, в соответствии с (2.14) окажется минимальным элементом в {?*j+i} раньше, чем и следовательно, войдет во множество 7* раньше, чем t Поскольку упорядочение в 74 определяется порядком поступления элементов в 7*, то, следовательно, и в Т Лс<Л’ Аналогично можно провести доказательство и для остальных процессов. Таким образом, утверждение 3 доказано. На основании Утверждений 2 и 3 можно сделать заключение о том, что формула (2.14) позволяет построить новое множество Т, включающее все элементы множеств Т (Vi) , и провести упорядочение его элементов таким образом, что сохраняются все отношения порядка в каждом из них. Поскольку каждому te T (Vi) ставится в соответствие свой элементарный оператор в треке, то определение порядка на Т дает возможность однозначно определить порядок на всем множестве элементарных операторов заданных процессов. 2.3.2. Классы одновременных событий Рассмотрим последовательность выполнения элементарных операторов в системе. Пусть система содержит 9 объектов, в каждом из которых развивается процесс. На рис.2.22 приведен пример организации треков на 98 |