|
процессов. Так, для приведенного на рис. 2.15. примера в соответствие с условиями Утверждения 1, из операторов h\ и й4 первым должен вычисляться оператор h\, из h$ и h\%первым й^ и т.д. Получим возможный порядок вычислений: Ль йи, (hi, (йз, й^), ftp, й4 и т.д. В скобках указаны пары операторов из разных процессов, для которых можно поменять порядок вычислений. На основании проведенного анализа можно сделать следующие выводы: 1. Для каждого процесса в ходе вычисления операторов необходимо строго придерживаться порядка а на Т. 2. Выполнение п.1, обеспечивает реализацию сцепленности операторов если ti При выполнении п.1 указание сцепленности операторов с разным значением Действительно, если вычислены элементарные операторы йю и Л2з в момент времени то указание h-^—>h{\ не меняет порядок вычислений, поскольку к моменту времени Гц будет рассчитан оператор й^. При этом условие сцепленности выполняется автоматически. 4. Для определения порядка расчета операторов, принадлежащих разным процессам, важно знание отношения сцепления для операторов разных процессов с одинаковым значением времени tj. Таким образом, можно сформулировать следующий алгоритм определения порядка вычисления элементарных операторов для совокупности параллельных процессов. Пусть заданы треки процессов Z1 (г = 1,и): для всех /. Пусть текущее значение времени равно t и все элементарные операторы И , у которых t Для всех h) , имеющих t'=t и обладающих |
операторов процесса Zi, а затем всех операторов процесса Z2. Очевидно, что порядок а.\ и а 2 при этом сохраняется. Г. Моделирование сцепленных между собой процессов Ъ\ и Zi. Пример сцепления показан на рис.2 .2 1 . В этом случае должен быть обязательно выдержан порядок а] для Z) и (*2 для Zi, поскольку в общем случае внутри каждого процесса существует сцепленность элементарных операторов. Кроме того, необходимо выполнить условия Утверждения 1 для любой пары сцепленных операторов из разных процессов. Так, для приведенного на рис. 2.21. примера в соответствие с условиями Утверждения 1, из операторов h\ и /г14 первым должен вычисляться оператор hi, из h$ и h\%первым h\%и т.д. Получим возможный порядок вычислений; h i, h[4, (/?2 , A15), (A3 , h\^\ hn, Ыи т.д. В скобках указаны пары операторов из разных процессов, для которых можно поменять порядок вычислений. На основании проведенного анализа можно сделать следующие выводы; 1. Для каждого процесса в ходе вычисления операторов необходимо строго придерживаться порядка а на Т. 2. Выполнение п.1, обеспечивает реализацию сцепленности операторов hi-Ж), если ti При выполнении п.1 указание сцепленности операторов с разным значением Действительно, если вычислены элементарные операторы И\о и /?2з в момент времени то указание Иц—Жи не меняет порядок вычислений, поскольку к моменту времени /ц будет рассчитан оператор h-^. При этом условие сцепленности выполняется автоматически. 96 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 |