|
2.1.3.
Разработка модели процесса строгого согласования реплик
При анализе строгой согласованности будем рассматривать синхронный
режим распространения изменений. На рисунке 2.4 представлена модель
согласования данных для этого случая [88, 91, 96, 98, 101]. Входящий поток
требований на чтение из одной реплики так же принимается пуассоновским с
параметром λ.
52
t
N
λ
N
λ
K
1
2
W
Обновление реплик
...
Ψ
1
(s)
Ψ
2
(s)
Ψ
W
(s)
Рисунок 2.4 – Модель строго согласования реплик (W+R>N).
На рисунке 2.4 обновляемые реплики обозначаются 1, 2, …, W, буквой K
обозначен координатор. Ψ
i
(s) – преобразование Лапласа-Стилтьеса функции
распределения вероятностей времени обновления i-ой. Требования на чтение
поступают с суммарной интенсивностью Nλ. Требования могут поступить как в
процессе обновления W реплик, так и до начала обновления. Задача состоит в
том, чтобы оценить характеристики случайного времени ожидания требованием
на чтение окончания обновления W реплик.
Для решения поставленной задачи сначала предлагается получить
производящую функцию W
q
(z) числа тех требований на чтение из N реплик,
которые поступят за время обновления W реплик. Из (2.4) следует, что требуемая
ПФ числа требований на чтение из N реплик, поступивших за время обновления i-
ой реплики, равна Ψ
i
(λN(1-z)). Т.к. требования на чтение из каждой реплики
поступают независимо друг от друга, ПФ числа требований на чтение из N
реплик, поступивших за время обновления W реплик, будет равна:
))
1
(
(
)
(
z
N
z
W
q
,
(2.12)
где
φ(s) =
W
i
i
s
1
)
(
(см. свойство (2.3)).
(2.13)
Тогда вероятность того, что за время обновления W реплик не поступит ни
одного требования на чтение, равна W
q
(0).
Далее, в [56, стр. 23, 24] доказывается, что, если за некоторый временной
интервал поступило n
≥
1 требований, моменты поступления этих требований
внутри данного интервала независимы и распределены по равномерному закону.
Это позволяет сделать вывод, что любое из пришедших требований имеет одну и
53
ту же функцию распределения вероятностей времени ожидания окончания
обновления W реплик.
Рассмотрим интервал между началом обновления и окончанием обновления
W реплик как интервал между событиями произвольного потока событий ς
1
,
ς
2
,
ς
3,
… с одинаковыми функциями распределений вероятностей интервалов между
этими событиями. Тогда, задача сводится к тому, чтобы оценить время t
0
между
произвольным моментом (в силу равномерности поступления требований внутри
интервала) и моментом наступления следующего события ς
i
(рисунок 2.5).
t
W
2
1
K
Время обновления W
реплик с ПЛС ϕ(s)
...
ς
i-2
ς
i-1
ς
i
ς
i+1
*
t
0
Рисунок 2.5 – Схема оценки времени ожидания t
0
.
ПЛС Φ(s) временного промежутка t
0
выводится в работе [56, стр. 36, 37] и
имеет следующий вид:
))
(
1
(
)
(
s
s
s
,
(2.14)
где α – среднее количество событий потока в единицу времени, φ(s) -
преобразование Лапласа-Стилтьеса функции распределения вероятностей
времени между событиями потока (см. (2.13)).
Т.к.
α
= -1/φ'(0), формулу (2.14) можно переписать следующим образом:
))
(
1
(
)
0
(
1
)
(
)
1
(
s
s
s
,
(2.15)
ПЛС Ω(s) функции распределения вероятностей времени ожидания
требованием на чтение окончания обновления W реплик имеет следующий вид:
s)
(
))
0
(
1
(
)
0
(
)
(
q
q
W
W
s
,
(2.16)
где W
q
(0) и Φ(s) определяются соответственно выражениями (2.12) и (2.15).
Выражение (2.16) читается следующим образом: с вероятностью W
q
(0), что
за время обновления W реплик не поступит ни одного требования на чтение из N
реплик, ПЛС равно единице (время ожидания равно нулю); с вероятностью (1-
54
W
q
(0)), что за время обновления W реплик поступит хотя бы одно требование на
чтение, ПЛС времени ожидания любым из них окончания обновления реплик
равно ПЛС, рассчитанному по формуле (2.15).
Т.к. время τ чтения R реплик складывается из времени ожидания и времени
непосредственного чтения, то ПЛС Ξ(s) временного промежутка τ можно оценить
следующим образом:
R
1
i
i
(s)
Ψ
Ω(s)
)
(
s
,
(2.17)
где Ω(s) и Ψ
i
(s) определяются соответственно выражениями (2.16) и (2.32).
Do'stlaringiz bilan baham: |
