|
Конус прошлого и конус будущего для события
В распределенном вычислении на событие ej' потенциально влияют только такие события ei, для которых ei → ej', и событие ej' "знает" о наступлении только этих событий ei. Поэтому множество таких событий ei формирует "прошлое" события ej', которое обозначается через Past(ej'):
Past(ej') = {ei: ei , ei → ej'}.
Множество Past(ej') называют (световым) конусом прошлого для события ej', как проиллюстрировано на рис. 2.8. Подмножество множества Past(ej') событий, происходящих в процессе Pi, обозначим через Pasti(ej'). Множество Pasti(ej') линейно упорядочено отношением →i. Пусть max(Pasti(ej')) – наибольший элемент этого множества. Очевидно, что событие max(Pasti(ej')) является последним событием процесса Pi, потенциально влияющим на событие ej' (см. рис. 2.8). Важно отметить, что событием max(Pasti(ej')) при i ≠ j всегда будет являться событие отправки сообщения.
Совокупность P(ej') = max(Pasti(ej')) всех последних событий процессов, которые могут оказывать влияние на событие ej', называют поверхностью конуса прошлого для события ej'. Здесь обратим внимание, что если событие ei произошло раньше, чем ej', то все события, в свою очередь наступившие в Pi раньше ei, также произошли раньше ej'. Поэтому поверхность конуса прошлого определяет все множество Past(ej') событий, произошедших раньше ej'.
Рис. 2.8. Конус прошлого и конус будущего для события.
Аналогично конусу прошлого для события определяется его конус будущего. А именно, (световому) конусу будущего Future(ej') события ej'
принадлежат все события ei, на которые ej' может оказывать влияние (см. рис. 2.8):
Future(ej') = {ei: ei , ej' → ei}.
Если через Futurei(ej') обозначить все события множества Future(ej'), происходящие в процессе Pi, то наименьшим элементом min(Futurei(ej')) этого множества будет являться первое событие процесса Pi, на которое влияет ej'. Следует обратить внимание, что событием min(Futurei(ej')) при i ≠ j всегда будет являться событие получения сообщения.
Совокупность F(ej') = min(Futurei(ej')) всех первых событий процессов, на которые ej' может оказывать влияние, называют поверхностью конуса будущего для события ej'. Аналогично P(ej') поверхность конуса будущего F(ej') определяет все множество событий Future(ej'), которые потенциально зависят от ej'.
Очевидно, что все события процесса Pi, которые наступают после события max(Pasti(ej')), но перед событием min(Futurei(ej')), являются параллельными с событием ej'. Поэтому параллельными с ej' событиями являются те и только те события, которые принадлежат множеству E \ Past(ej') \ Future(ej').
Логический и физический параллелизм. Для распределенного вычисления два события считаются логически параллельными, когда они не связаны отношением причинно-следственной зависимости друг с другом. В свою очередь, физический параллелизм событий подразумевает наступление событий практически в одно и то же время. Важно отметить, что события могут быть логически параллельными даже в случае, когда они происходят в разные моменты времени. Например, на рис. 2.7 события e24 и e31 происходят в различные моменты времени, однако, являются логически параллельными. Тем не менее, если бы скорости выполнения процессов и задержки доставки сообщений были бы другими, указанные события вполне могли бы произойти практически в одно и то же время. При этом результат вычисления не будет зависеть от того, совпадает ли выполнение логически параллельных событий во времени или нет. Поэтому, несмотря на то, что два логически параллельных события могут происходить в различные моменты времени, для всех практических и теоритических задач можно считать, что такие события происходят одновременно. Однако здесь важно еще раз оговориться, что в отличие от физического параллелизма, отношение логического параллелизма не является транзитивным, т.е. (ei || ej') ˄ (ej' || ek'') / ei || ek''. Поэтому,
например, для стороннего наблюдателя события e 4 и e 1 на рис. 2.7 могли
2 3
2
1
бы происходить практически одновременно. Также событие e 4 могло бы произойти практически в одно и то же время с событием e 5. Однако
e31 |/| e15, и потому эти события всякий раз будут происходить друг за
другом, и между ними в выполнении всегда будут находиться другие события.
Do'stlaringiz bilan baham: |
