|
Представляя выполнение в виде последовательности событий, мы тем самым естественно привносим в модель распределенной обработки данных понятие времени. Будем говорить, что событие e наступает раньше события e', если в последовательности событий e предшествует e'.
Пусть задано выполнение R = (e0, e1, … ex, ex+1, …). С этой последовательностью событий связана последовательность глобальных состояний (S0, S1, … Sx, Sx+1, …) такая, что Sx+1 = ex(Sx) для всех x ≥ 0. Важно отметить, что последовательность R не всегда однозначно определяет последовательность глобальных состояний: если в R не содержится ни одного события процесса Рi для некоторого i, 1 ≤ i ≤ N, то начальное состояние этого процесса остается неопределенным и может быть выбрано неоднозначным образом. Однако если в R содержится хотя бы одно событие процесса Рi, то первое событие еi = (Рi, s, s', m, С) указывает на то, что начальным состоянием процесса Рi является s. Таким образом, если в R содержится хотя бы одно событие каждого процесса, то начальное состояние S0 определяется однозначно и за счет этого однозначно определяется и вся последовательность (S0, S1, … Sx, Sx+1, …).
Для визуализации выполнения распределенной системы можно использовать пространственно-временные диаграммы. Пример одной из таких диаграмм приведен на рис. 2.6. Ход выполнения каждого процесса Pi
представляется в виде горизонтальной прямой линии. Каждое событие еi процесса Рi отмечается точкой на прямой, соответствующей этому процессу. Вообще говоря, в реальности выполнение того или иного события занимает некоторое ненулевое конечное время, однако, из-за предположения атомарности событий их можно изображать точками. На прямой процесса Pi событие ei изображается левее события ei' тогда и только тогда, когда ei →i ei', т.е. если событие ei наступает раньше события ei' в процессе Pi. Поэтому на диаграмме ось времени направлена слева направо. Например, на рис. 2.6 первым по порядку событием, произошедшим в процессе P2, является внутреннее событие, вторым событием является событие получения сообщения, а третьим – событие отправки сообщения. Стрелкой обозначается передача сообщения от одного процесса другому. Если отправка сообщения m происходит при наступлении события ei, а получение этого же сообщения m – при наступлении события ej', то события отправки ei и получения ej' называют взаимосвязанными. Вертикальная проекция событий на ось R описывает выполнение распределенной системы. Так как событие получения сообщения не может наступить раньше связанного с ним события отправки этого сообщения, стрелки, обозначающие передачу сообщения, всегда будут направлены слева направо.
Рис. 2.6. Пример пространственно-временной диаграммы распределенного
выполнения.
Последовательность глобальных состояний, связанная с данным выполнением R, может быть представлена на пространственно-временной диаграмме в виде последовательности вертикальных "срезов" состояний
процессов и каналов, проходящих между событиями, отмеченными точками (см. рис. 2.6). Ниже мы покажем, что порядок следования некоторых событий в выполнении R может быть изменен так, что это никак не отразится на последующем глобальном состоянии, достижимом в этом выполнении. Поэтому представление о времени как о линейном порядке на множестве E всех событий, происходящих при выполнении распределенной системы, не совсем подходит для распределенной обработки данных.
Происходящие события оказывают влияние только на часть глобального состояния системы. Поэтому два события, идущие друг за другом в выполнении и влияющие на раздельные части глобального состояния, оказываются независимыми и могут происходить в другом порядке. Действительно, пусть S – глобальное состояние распределенной системы, и пусть ei и ej – события, которые происходят в разных процессах Pi и Pj, т.е. i ≠ j, и при этом оба события допустимы в глобальном состоянии S. Тогда событие ei допустимо в глобальном состоянии ej(S), а событие ej – в глобальном состоянии ei(S) и при этом ei (ej(S)) = ej (ei(S)).
Для доказательства этого утверждения рассмотрим два события еi = (Рi, si, si', mi, Сi) и еj = (Рj, sj, sj', mj, Сj), где Сi и Сj – каналы, инцидентные процессам Pi и Pj. Важным обстоятельством оказывается тот факт, что ei и ej не являются взаимосвязанными событиями отправки и получения одного и того же сообщения, т.е. mi и mj – различные сообщения. В противном случае оба взаимосвязанных события отправки и получения не могли бы одновременно являться допустимыми в глобальном состоянии S, что противоречило бы условию. Обозначим через Si глобальное состояние, в которое перейдет система из состояния S после наступления события ei, т.е. Si = ei(S). Как указывалось в п. 2.1, глобальное состояние Si будет отличаться от S только состоянием процесса Рi и, возможно, состоянием канала Сi. А именно, процесс Рi будет находиться в состоянии si', а сообщение mi будет либо добавлено в канал Сi, если ei – событие отправки, либо удалено из канала Сi, если ei – событие получения сообщения. Так как mi и mj – различные сообщения, а состояние sj процесса Pj одинаково в глобальных состояниях S и Si, то событие еj является допустимым также и в состоянии Si. С помощью аналогичных рассуждений мы можем показать, что и событие еi является допустимым в состоянии Sj = ej(S).
Рассмотрим теперь глобальное состояние Sij = еj(Si). В нем процессы Pi и Pj находятся в состояниях si' и sj', а сообщение mi либо добавлено в канал Сi, либо удалено из него, в зависимости от типа события ei, равно как и сообщение mj либо добавлено в канал Сj, либо удалено из него, в зависимости от типа события ej. Эта же ситуация соответствует глобальному состоянию Sji = еi(Sj), т.е. Sij = Sji, что и требовалось доказать.
Таким образом, события не могут произойти в другом порядке, только в двух случаях:
Do'stlaringiz bilan baham: |
