Методы эффективной реализации векторных часов

Размер векторных отметок времени определяется числом N процессов, участвующих в распределенном вычислении, и растет линейно с увеличением N. В случае, когда число процессов велико, использование механизма векторных часов будет приводить к необходимости пересылки значительного объема данных с каждым сообщением. Поэтому если в распределенной системе работают сотни процессов даже при небольшом числе событий, происходящих всего в нескольких процессах, доля накладных расходов в каждом пересылаемом сообщении может достигать недопустимых величин. Несмотря на то, что для выполнения условия строгой непротиворечивости длина векторных отметок времени не может быть меньше числа процессов в распределенной системе, существует ряд методов, позволяющих реализовать механизм векторных часов более эффективно.

Дифференциальная пересылка векторного времени

Метод дифференциальной пересылки векторного времени основан на том наблюдении, что между последовательными отправками сообщений одному и тому же получателю обычно изменяется лишь небольшое число компонентов векторного времени процесса-отправителя. Это становиться особенно заметным, когда распределенная система состоит из большого числа процессов, но информацией друг с другом активно обмениваются лишь немногие из них. Поэтому, когда процесс Р, отправляет сообщение процессу Pj, предлагается вместе с этим сообщением передавать только те компоненты векторного времени процесса которые изменились с момента последней отправки сообщения процессу Pj.

Таким образом, если с момента последней отправки сообщения процессу Pj в процессе Р, изменились только компоненты /у, i2, ... i„ его векторного времени V,- на значения соответственно Vy, v2, ... v„, то в новом сообщении процесс Р( пересылает лишь множество пар: {(/у, Vy), (i2, v2), ... (/„, vn)}. Когда процесс Pj получает такое сообщение, он обновляет свое векторное время согласно следующему правилу:

Данный метод позволяет уменьшить накладные расходы на передачу сообщений и, как следствие, снизить требования к емкости каналов связи и размеру буфера приема-передачи на отправляющей и принимающей стороне. Конечно, в наихудшем случае процессу придется передавать все компоненты своего векторного времени, однако, в среднем можно ожидать, что размер такой дифференциальной отметки времени, передаваемой с каждым сообщением, будет меньше, чем размер всего вектора V,. Стоит обратить внимание, что для правильной работы этого метода каналы должны обладать свойством FIFO.

Метод дифференциальной пересылки векторного времени требует, чтобы каждый процесс хранил значения всех своих отметок времени для последних событий отправки сообщений каждому другому процессу в распределенной системе. Прямая реализация данного требования приводит к накладным расходам на хранение отметок времени в каждом процессе с порядком роста 0{N~). Однако существует метод, позволяющий уменьшить накладные расходы, связанные с хранением дополнительной информации в каждом процессе, до 0(N). Суть его заключается в следующем.

Каждый процесс Р, дополнительно поддерживает работу с двумя массивами:

  • LSj[..N] (от англ. Last Sent). Элемент L5,-[/] содержит значение логического локального времени процесса Piy У,[/], на момент последней отправки процессом Р, сообщения процессу Рг
  • LUj[..N] (от англ. Last Update). Элемент LUj] содержит значение логического локального времени процесса Р„ У([/], на момент последнего изменения процессом Р, у-го компонента своего векторного времени У, [у].

Очевидно, L?/,[/] = У,[у] в каждый момент выполнения процесса Р„ а значение LUj] обновляется при получении процессом Р, сообщения, вызывающего изменение У, [у]. В свою очередь значение элемента 7Д[/] обновляется каждый раз при отправке процессом Р, сообщения процессу Ру.

Используя эти два массива, можно заключить, что с момента последней отправки процессом Р, сообщения процессу Р, в процессе Р, изменились только те к компонентов его векторного времени Vj[k], для которых LSjj] < LUj[k]. Поэтому, согласно методу дифференциальной пересылки векторного времени, только эти компоненты должны быть переданы в новом сообщении из Р, в Ру. Таким образом, когда процесс Р, отправляет сообщение процессу Рг вместе с этим сообщением в качестве отметки времени он пересылает лишь множество пар

вместо пересылки всего вектора У„ состоящего из N компонентов.

Пример работы метода дифференциальной пересылки векторных отметок времени приведен на рис. 3.7. На этом рисунке второе сообщение, переданное процессом Р3 в процесс Р2 с отметкой времени {(3,2)}, информирует процесс Р2 о том, что третий компонент векторного времени был изменен, и его новое значение равно двум. Передаваемая отметка времени выглядит именно так, потому что с момента последней отправки сообщения из Р3 в Р2 процесс Р3 изменил показания своих локальных часов с единицы до двух.

Пример работы метода дифференциальной пересылки векторного времени

Рис. 3.7. Пример работы метода дифференциальной пересылки векторного времени.

Таким образом можно сделать вывод, что применение представленного метода дифференциальной пересылки векторного времени может привести к уменьшению накладных расходов, связанных с передачей сообщений, особенно, в случае, когда взаимодействие процессов в распределенной системе носит локальный характер.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >