ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМА УПРАВЛЕНИЯ ОБЪЕМОМ РАЗДЕЛОВ КЭША СИСТЕМЫ ХРАНЕНИЯ ДАННЫХ
СИСТЕМЫ ХРАНЕНИЯ ИНФОРМАЦИИ
УДК 004.021
В. С. ДУЖИН, Г. С. ЕВСЕЕВ, Е. М. ЛИНСКИЙ
ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМА УПРАВЛЕНИЯ ОБЪЕМОМ РАЗДЕЛОВ КЭША СИСТЕМЫ ХРАНЕНИЯ ДАННЫХ
Рассматривается модель кэша системы хранения данных, состоящего из двух разделов. Построен алгоритм управления объемом разделов. Исследовано влияние ошибок определения текущего и последующего состояния потока на качество работы алгоритма.
Ключевые слова: системы хранения данных, кэш, оценка эффективности.
Введение. Использование кэша в системе хранения данных позволяет существенно уменьшить время доступа к информации. К такой системе обращаются приложения, отправляя запросы на получение данных. Каждому приложению в кэше выделен отдельный раздел. Будем считать, что каждое приложение характеризуется требованием на время обработки запроса, выражающимся в среднем значении HR (Hit Rate, отношение числа запросов, найденных в кэше, к общему числу запросов за определенный временной интервал для его раздела).
В настоящей статье рассматривается алгоритм, динамически перераспределяющий границы раздела.
В отличие от работ [1, 2], в которых рассматриваются эвристические алгоритмы управления кэшем, в настоящей статье предложена модель кэша, состоящего из двух разделов, позволяющая проводить анализ алгоритмов управления.
Модель системы. Рассмотрим LRU-кэш, с которым работают два приложения, каждому из них ставится в соответствие свой раздел в кэше, свой поток входных запросов и требуемое значение HR.
Входные потоки характеризуются интенсивностью запросов и распределением стекового расстояния, под которым будем понимать количество различных адресов между двумя обращениями к одному и тому же адресу [3—4].
Пусть входные потоки к каждому разделу могут находиться в двух состояниях: S1 и S2 . Состояния различаются видом гистограммы стековых расстояний. Считается, что любой раздел, входной поток к которому находится в состоянии S1, удовлетворяет требованию по HR, если его размер (объем) равен V1. Раздел, входной поток к которому находится в состоянии S2 , удовлетворяет требованию, если его объем равен V2 . Будем считать, что V2 = 2V1, Vcache = 3V1 , где Vcache — суммарный объем кэша.
Рассмотрим дискретную временную модель: пусть N1 = N2 = N — интенсивность запросов к разделам в определенный интервал времени, а ξ1 , ξ2 — число запросов к адресам, находящимся в кэше (за то же время). Вероятности переходов между состояниями i-го потока описываются матрицей переходов марковской цепи:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
72 В. С. Дужин, Г. С. Евсеев, Е. М. Линский
⎡ Pi (S1 | S1)
⎢ ⎣
Pi
(S1
|
S2
)
Pi Pi
(S2 (S2
| |
S1) ⎤ S2 )⎦⎥
.
(1)
На рисунке приведены функции распределения вероятностей стековых расстояний для
потоков в состояниях S1 и S2 .
F(V′)
S1
h3 S2
h1 h2
V1 V2
V′
Заметим, что при заданном размере раздела V′ величина F(V′) может рассматриваться
как средний HR на данном разделе, т.к. F(V′) – вероятность того, что стековое расстояние не
превысит V′ (запрашиваемый адрес будет найден в кэше).
Будем считать, что требование к размеру раздела состоит в том, чтобы средний HR был
не меньше h1 . Как видно из рисунка, это условие не выполняется, когда входной поток нахо-
дится в состоянии S2 , а объем раздела равен V1.
Алгоритм управления кэшем. Рассмотрим алгоритм управления размерами разделов в
кэше, обеспечивающий улучшение качества работы системы за счет ее динамической адапта-
ции к изменениям входного потока. В течение каждого временного интервала собирается
статистика по входным потокам, на основании которой оценивается состояние потоков в дан-
ном интервале. Прогноз состояния входных потоков в последующем временном интервале
осуществляется на основе этих оценок и матриц (1). В конце каждого интервала происходит
перераспределение объемов разделов в соответствии с этим прогнозом. Например, если со-
стояние потока в предыдущем интервале оценено как Sˆ1, а P(S2 | S1) > 0,5 , то прогнозирует-
ся, что в следующем интервале поток перейдет в состояние S2 .
Ниже представлен способ получения оценки состояния входного потока. Пусть текущий
объем раздела равен V1, за последний интервал пришло N запросов, при этом ξ из них были
найдены в кэше. В этом случае вероятность того, что входной поток к данному разделу нахо-
дился в состоянии S1, определяется следующим образом:
P(S1
| V1, N, ξ)
=
P(S1, ξ | V1, N ) P(ξ | V1, N )
.
(2)
Выражение (2) получено из формулы для вероятностей зависимых событий [5] (в данном
случае случайными величинами являются S1 и ξ , а V1 и N — постоянными). Аналогичным
образом определяется вероятность нахождения входного потока к разделу в состоянии S2 .
Обозначим через R(V1, N ,ξ) отношение этих вероятностей и преобразуем его следующим об-
разом:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Оценка эффективности алгоритма управления объемом разделов кэша
73
R(V1,
N , ξ)
=
P(S1, ξ | V1, N ) P(S2, ξ | V1, N )
=
P(ξ | S1,V1, P(ξ | S2,V1,
N )P(S1 | V1, N ) N )P(S2 |V1, N )
.
(3)
Вероятности того, что из N пришедших заявок ξ будут найдены в кэше, описываются
биномиальным распределением:
⎪⎧P(ξ | S1,V1, N ) = CNξ h1ξ (1− h1)N −ξ,
⎨ ⎩⎪
P(ξ
|
S2
,V1,
N
)
=
CNξ
h2ξ
(1
−
h2
)
N
−ξ.
(4)
Вероятность того, что заявка найдена в кэше, равна h1 и h2 для состояний входного по-
тока S1 и S2 соответственно (см. рисунок). Заметим, что P(S1 | V1, N ) и P(S2 | V1, N ) не зави-
сят от случайной величины ξ и определяются исключительно из матрицы переходов марков-
ской цепи (1):
⎧⎨⎩PP((SS12
| V1, N ) | V1, N )
= =
P(S1), P(S2 ).
(5)
Подставив (4) и (5) в выражение (3), после необходимых преобразований получим:
R(V1, N , ξ)
=
⎛ ⎜ ⎝
h1(1− h2 ) h2 (1− h1)
⎞ξ ⎟ ⎠
⎛ ⎜ ⎝
1− 1−
h1 h2
⎞N ⎟ ⎠
P(S1) P(S2 )
,
(6)
таким же образом получим отношение для потока к разделу размера V2 :
R(V2, N, ξ)
=
⎛ ⎜ ⎝
h3 (1 − h1 (1 −
h1) h3 )
⎞ξ ⎟ ⎠
⎛ ⎜ ⎝
1− 1−
h3 h1
⎞N ⎟ ⎠
P(S1) P(S2 )
.
(7)
По формулам (6), (7) можно оценить состояние входного потока за временной интервал.
Будем считать, что при R > 1 входной поток в состоянии S1, а при R ≤ 1 — в S2 :
Sˆ
(V
,
N
,
ξ)
=
⎡⎢⎢SSˆˆ12,,еессллииVV ⎢⎢Sˆ1, если V
= V1, R(V1, N, ξ) > 1, = V1, R(V1, N, ξ) ≤ 1, = V2, R(V2, N, ξ) > 1,
⎣⎢Sˆ2, если V = V2, R(V2, N, ξ) ≤ 1.
(8)
Заметим, что достаточно определить оценку (8) лишь для одного потока: при оценке со-
стояния первого потока Sˆ1 ему назначается объем V1, а второму — V2 (это связано с тем, что
Vcache = 3V1, а распределять не весь объем кэша нецелесообразно). Если оценка состояния первого потока Sˆ2 , ему назначается объем V2 , а второму — V1.
Кэш выделяется, в первую очередь, тому потоку, оценка состояния которого более дос-
товерна. Достоверность определяется тем, насколько значение R отличается от единицы: при
R = 1 оценки становятся равновероятными, а значит их достоверность минимальна.
Таким образом, вначале вычисляются значения R для каждого раздела, затем устанав-
ливается размер того раздела, для которого R больше (если R < 1, то в сравнении будет уча-
ствовать величина
1 R
). Другому разделу назначается оставшийся объем кэша.
Оценка работы алгоритма. Рассмотрим методику оценки качества работы алгоритма
управления кэшем, которое определим как вероятность того, что на каком-либо временном
интервале требования на HR будут удовлетворены для обоих разделов. На качество работы
алгоритма влияют ошибка оценки текущих состояний потоков, вызванная низкой интенсив-
ностью входных потоков, а также ошибка определения последующего состояния, связанная со
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
74 В. С. Дужин, Г. С. Евсеев, Е. М. Линский
случайным характером переключения состояний входных потоков. Сначала рассмотрим иде-
альный случай, когда обе ошибки отсутствуют (построим верхнюю границу качества),
затем — когда присутствует лишь ошибка определения последующего состояния и, наконец,
когда присутствуют обе ошибки.
Вычислим верхнюю границу качества описанного алгоритма. Будем считать, что со-
стояния потоков на каждом временном интервале известны заранее. Соответственно выби-
раются оптимальные размеры разделов во всех случаях, когда это возможно. Требования по
HR не выполняются лишь тогда, когда оба входных потока находятся в состоянии S2 , по-
скольку в этом случае потребуется объем 2V2 > Vcache . Верхняя граница качества алгоритма
определяется следующим выражением:
Q1 = 1− P1(S2 )P2 (S2 ) ,
(9)
где P1(S2 ) и P2 (S2 ) — вероятность нахождения в состоянии S2 потоков запросов к 1-му и 2-му разделам, которая определяется из формулы полной вероятности [5]:
Pi (S2 ) = Pi (S1)Pi (S2 | S1) + Pi (S2 )Pi (S2 | S2 ) ,
(10)
где i = 1, 2 . Поскольку поток может быть в состоянии S1 либо в состоянии S2 ,
Pi (S1) = 1− Pi (S2 ) . Подставим (11) в (10) и после необходимых преобразований получим:
(11)
Pi (S2 )
=
Pi (S1
Pi (S2 | S1) | S2 ) + Pi (S2
|
S1)
.
(12)
Рассуждая аналогичным образом, можно вычислить вероятность нахождения потока в
состоянии S1:
Pi (S1)
=
Pi (S1
Pi (S1 | S2 ) | S2 ) + Pi (S2
|
S1)
.
Перепишем (9) с учетом (12):
(13)
Q1
=
1
−
(
P1(S1
|
S2
)
+
P1(S2 P1(S2 |
| S1)P2 (S2 | S1)
S1))( P2 (S1 | S2 )
+
P2
(S2
|
S1)
)
.
(14)
Вычислим оценку качества алгоритма при условии, что известны состояния входных
потоков за прошедший временной интервал (интенсивность потоков N → ∞ ), при этом прогноз следующего состояния осуществляется на основе матрицы переходов (1).
В таблице перечислены состояния системы, состоящей из двух разделов. Каждое со-
стояние характеризуется объемом разделов и состояниями их входных потоков. Заметим:
когда система находится в состояниях 1, 2, 5, 7, разделам хватает выделенных объемов для
выполнения требований. В состояниях 4, 8 требования не могут быть удовлетворены в прин-
ципе, поскольку входные потоки к обоим разделам находятся в состоянии S2 . В состояниях 3, 6 требования могут быть выполнены, если объем разделов выбран правильно. Таким обра-
зом, оценка качества работы данного алгоритма вычисляется с помощью следующего выра-
жения:
Q2 = Q1 − (P(3) + P(6)) ,
(15)
где P(3) , P(6) — вероятности перехода системы в соответствующие состояния. Выражение
(15) справедливо, поскольку P(3) и P(6) — вероятности несовместных событий.
Введем обозначение V (i) = {V (1) ,V (2)}. Пусть при V (1) первый раздел получает объем V1, второй V2 , а при V (2) — наоборот.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Оценка эффективности алгоритма управления объемом разделов кэша
75
Пусть Pош (S (1) , S (2) ,V (1) ) — вероятность того, что распределение разделов V (1) даст ошибку, если на предыдущем интервале состояние первого раздела было S (1) , а второго — S (2) . Аналогичным образом определяется Pош (S (1), S (2) ,V (2) ) . Тогда минимальная вероятность ошибки для ситуации S (1) = S1, S (2) = S1 определяется следующим образом:
{ }Pош (S1, S1) = min Pош (S1, S1,V (1) ), Pош (S1, S1,V (2) ) .
№ состояния
1 2
3
4 5
6
7 8
Объем 1-го раздела
V1 V1
V1
V1 V2
V2
V2 V2
Объем 2-го раздела
V2 V2
V2
V2 V1
V1
V1 V1
Состояние 1-го потока
S1 S1
S2
S2 S1
S1
S2 S2
Состояние 2-го потока
S1 S2
S1
S2 S1
S2
S1 S2
Требования по HR
Выполнены Выполнены Не выполнены из-за ошибки Невыполнимы Выполнены Не выполнены из-за ошибки Выполнены Невыполнимы
Вероятность ошибки определяется как сумма таких вероятностей для всех комбинаций
S (1) , S (2) :
22
∑ ∑ { }Pош = P(3) + P(6) =
min Pош (Si , S j ,V (1) ), Pош (Si , S j ,V (2) ) .
(16)
i=1 j=1
Перепишем (15) с учетом (16):
∑ ∑ { }2 2
Q2 = Q1 −
min Pош (Si , S j ,V (1) ), Pош (Si , S j ,V (2) ) .
i=1 j=1
Очевидно, что данный алгоритм работает лучше, когда состояния входных потоков из-
меняются редко: при стремлении элементов главной диагонали матрицы (1) к единице Q2
стремится к Q1 ( P(S1 | S2 ) и P(S2 | S1) стремятся к нулю, вероятности P(3) и P(6) стремятся
к нулю и выражение (15) вырождается в (14)).
Теперь рассмотрим ситуацию, когда оценка состояний входных потоков производится
при конечной выборке. В этом случае к ошибке оценки следующего состояния добавляется
ошибка оценки текущего состояния.
Определим зависимость качества алгоритма от интенсивности N . Для этого выпишем
матрицу переходов системы из двух разделов:
⎧⎪P(1)
=
8
∑
P(i)
P(1
|
i),
⎪ i=1
⎪8
⎪⎪P(2) = ∑ P(i)P(2 | i),
⎨ i=1
⎪ ⎪
#
⎪8
⎪P(8) = ∑ P(i)P(8 | i).
⎩⎪ i=1
(17)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
76 В. С. Дужин, Г. С. Евсеев, Е. М. Линский
Пусть V (i) — распределение объемов разделов в i-м состоянии системы, например,
V (6) = V (2) .
Поскольку изменение объема раздела и изменение состояний входных потоков являются независимыми событиями, вероятность перехода из j-го в i-е состояние системы может быть представлена в виде произведения вероятности изменения объема раздела c Vt−1 на Vt и
вероятностей переходов состояний потоков 1-го и 2-го раздела соответственно: P1(St | St−1) и
P2 (St | St−1) :
P(i | j) = P(Vt , St(1) , St(2) | Vt−1, St(−11) , St(−21) ) = P(Vt | Vt−1, St(−11) , St(−21) )P1(St | St−1)P2 (St | St−1) . Вычислим P(Vt | Vt−1, St(−11) , St(−21) ) для случая Vt = V (2) ,Vt−1 = V (1) . Пусть оценка состояния первого потока оказалась более достоверной. Для того чтобы объем 1-го раздела стал равен
V2 , необходимо, чтобы в предыдущем интервале была получена оценка состояния потока Sˆ(2) = S2 . При этом объем данного раздела в предыдущем интервале должен быть равен V1.
Из (8) следует, что для этого должно быть выполнено условие R(V1, N, ξ) ≤ 1. Соответственно
P(Vt | Vt−1, St(−11) , St(−21) ) = P(R(V1, N , ξ) ≤ 1) . После необходимых преобразований с учетом (6), (12), (13) получим:
P(Vt
| Vt−1, St(−11) , St(−21) ) =
P
⎛ ⎜ ⎜ ⎝
ξ
<
ln
⎛ ⎜ ⎝⎜
⎛ ⎜ ⎝
1− 1−
h2 h1
⎞N ⎟ ⎠
P1(S2 P1(S1
| S1) | S2)
⎞ ⎟ ⎠⎟
ln
⎛ ⎜ ⎝
h1(1− h2 ) h2 (1− h1)
⎞ ⎟ ⎠
⎞ ⎟ ⎟ ⎠
.
(18)
Обозначим правую часть неравенства (18) через Ξ и перепишем его с учетом того, что
ξ имеет биномиальное распределение:
∑P(Vt | Vt−1, St(−11) , St(−21) ) = m
УДК 004.021
В. С. ДУЖИН, Г. С. ЕВСЕЕВ, Е. М. ЛИНСКИЙ
ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМА УПРАВЛЕНИЯ ОБЪЕМОМ РАЗДЕЛОВ КЭША СИСТЕМЫ ХРАНЕНИЯ ДАННЫХ
Рассматривается модель кэша системы хранения данных, состоящего из двух разделов. Построен алгоритм управления объемом разделов. Исследовано влияние ошибок определения текущего и последующего состояния потока на качество работы алгоритма.
Ключевые слова: системы хранения данных, кэш, оценка эффективности.
Введение. Использование кэша в системе хранения данных позволяет существенно уменьшить время доступа к информации. К такой системе обращаются приложения, отправляя запросы на получение данных. Каждому приложению в кэше выделен отдельный раздел. Будем считать, что каждое приложение характеризуется требованием на время обработки запроса, выражающимся в среднем значении HR (Hit Rate, отношение числа запросов, найденных в кэше, к общему числу запросов за определенный временной интервал для его раздела).
В настоящей статье рассматривается алгоритм, динамически перераспределяющий границы раздела.
В отличие от работ [1, 2], в которых рассматриваются эвристические алгоритмы управления кэшем, в настоящей статье предложена модель кэша, состоящего из двух разделов, позволяющая проводить анализ алгоритмов управления.
Модель системы. Рассмотрим LRU-кэш, с которым работают два приложения, каждому из них ставится в соответствие свой раздел в кэше, свой поток входных запросов и требуемое значение HR.
Входные потоки характеризуются интенсивностью запросов и распределением стекового расстояния, под которым будем понимать количество различных адресов между двумя обращениями к одному и тому же адресу [3—4].
Пусть входные потоки к каждому разделу могут находиться в двух состояниях: S1 и S2 . Состояния различаются видом гистограммы стековых расстояний. Считается, что любой раздел, входной поток к которому находится в состоянии S1, удовлетворяет требованию по HR, если его размер (объем) равен V1. Раздел, входной поток к которому находится в состоянии S2 , удовлетворяет требованию, если его объем равен V2 . Будем считать, что V2 = 2V1, Vcache = 3V1 , где Vcache — суммарный объем кэша.
Рассмотрим дискретную временную модель: пусть N1 = N2 = N — интенсивность запросов к разделам в определенный интервал времени, а ξ1 , ξ2 — число запросов к адресам, находящимся в кэше (за то же время). Вероятности переходов между состояниями i-го потока описываются матрицей переходов марковской цепи:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
72 В. С. Дужин, Г. С. Евсеев, Е. М. Линский
⎡ Pi (S1 | S1)
⎢ ⎣
Pi
(S1
|
S2
)
Pi Pi
(S2 (S2
| |
S1) ⎤ S2 )⎦⎥
.
(1)
На рисунке приведены функции распределения вероятностей стековых расстояний для
потоков в состояниях S1 и S2 .
F(V′)
S1
h3 S2
h1 h2
V1 V2
V′
Заметим, что при заданном размере раздела V′ величина F(V′) может рассматриваться
как средний HR на данном разделе, т.к. F(V′) – вероятность того, что стековое расстояние не
превысит V′ (запрашиваемый адрес будет найден в кэше).
Будем считать, что требование к размеру раздела состоит в том, чтобы средний HR был
не меньше h1 . Как видно из рисунка, это условие не выполняется, когда входной поток нахо-
дится в состоянии S2 , а объем раздела равен V1.
Алгоритм управления кэшем. Рассмотрим алгоритм управления размерами разделов в
кэше, обеспечивающий улучшение качества работы системы за счет ее динамической адапта-
ции к изменениям входного потока. В течение каждого временного интервала собирается
статистика по входным потокам, на основании которой оценивается состояние потоков в дан-
ном интервале. Прогноз состояния входных потоков в последующем временном интервале
осуществляется на основе этих оценок и матриц (1). В конце каждого интервала происходит
перераспределение объемов разделов в соответствии с этим прогнозом. Например, если со-
стояние потока в предыдущем интервале оценено как Sˆ1, а P(S2 | S1) > 0,5 , то прогнозирует-
ся, что в следующем интервале поток перейдет в состояние S2 .
Ниже представлен способ получения оценки состояния входного потока. Пусть текущий
объем раздела равен V1, за последний интервал пришло N запросов, при этом ξ из них были
найдены в кэше. В этом случае вероятность того, что входной поток к данному разделу нахо-
дился в состоянии S1, определяется следующим образом:
P(S1
| V1, N, ξ)
=
P(S1, ξ | V1, N ) P(ξ | V1, N )
.
(2)
Выражение (2) получено из формулы для вероятностей зависимых событий [5] (в данном
случае случайными величинами являются S1 и ξ , а V1 и N — постоянными). Аналогичным
образом определяется вероятность нахождения входного потока к разделу в состоянии S2 .
Обозначим через R(V1, N ,ξ) отношение этих вероятностей и преобразуем его следующим об-
разом:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Оценка эффективности алгоритма управления объемом разделов кэша
73
R(V1,
N , ξ)
=
P(S1, ξ | V1, N ) P(S2, ξ | V1, N )
=
P(ξ | S1,V1, P(ξ | S2,V1,
N )P(S1 | V1, N ) N )P(S2 |V1, N )
.
(3)
Вероятности того, что из N пришедших заявок ξ будут найдены в кэше, описываются
биномиальным распределением:
⎪⎧P(ξ | S1,V1, N ) = CNξ h1ξ (1− h1)N −ξ,
⎨ ⎩⎪
P(ξ
|
S2
,V1,
N
)
=
CNξ
h2ξ
(1
−
h2
)
N
−ξ.
(4)
Вероятность того, что заявка найдена в кэше, равна h1 и h2 для состояний входного по-
тока S1 и S2 соответственно (см. рисунок). Заметим, что P(S1 | V1, N ) и P(S2 | V1, N ) не зави-
сят от случайной величины ξ и определяются исключительно из матрицы переходов марков-
ской цепи (1):
⎧⎨⎩PP((SS12
| V1, N ) | V1, N )
= =
P(S1), P(S2 ).
(5)
Подставив (4) и (5) в выражение (3), после необходимых преобразований получим:
R(V1, N , ξ)
=
⎛ ⎜ ⎝
h1(1− h2 ) h2 (1− h1)
⎞ξ ⎟ ⎠
⎛ ⎜ ⎝
1− 1−
h1 h2
⎞N ⎟ ⎠
P(S1) P(S2 )
,
(6)
таким же образом получим отношение для потока к разделу размера V2 :
R(V2, N, ξ)
=
⎛ ⎜ ⎝
h3 (1 − h1 (1 −
h1) h3 )
⎞ξ ⎟ ⎠
⎛ ⎜ ⎝
1− 1−
h3 h1
⎞N ⎟ ⎠
P(S1) P(S2 )
.
(7)
По формулам (6), (7) можно оценить состояние входного потока за временной интервал.
Будем считать, что при R > 1 входной поток в состоянии S1, а при R ≤ 1 — в S2 :
Sˆ
(V
,
N
,
ξ)
=
⎡⎢⎢SSˆˆ12,,еессллииVV ⎢⎢Sˆ1, если V
= V1, R(V1, N, ξ) > 1, = V1, R(V1, N, ξ) ≤ 1, = V2, R(V2, N, ξ) > 1,
⎣⎢Sˆ2, если V = V2, R(V2, N, ξ) ≤ 1.
(8)
Заметим, что достаточно определить оценку (8) лишь для одного потока: при оценке со-
стояния первого потока Sˆ1 ему назначается объем V1, а второму — V2 (это связано с тем, что
Vcache = 3V1, а распределять не весь объем кэша нецелесообразно). Если оценка состояния первого потока Sˆ2 , ему назначается объем V2 , а второму — V1.
Кэш выделяется, в первую очередь, тому потоку, оценка состояния которого более дос-
товерна. Достоверность определяется тем, насколько значение R отличается от единицы: при
R = 1 оценки становятся равновероятными, а значит их достоверность минимальна.
Таким образом, вначале вычисляются значения R для каждого раздела, затем устанав-
ливается размер того раздела, для которого R больше (если R < 1, то в сравнении будет уча-
ствовать величина
1 R
). Другому разделу назначается оставшийся объем кэша.
Оценка работы алгоритма. Рассмотрим методику оценки качества работы алгоритма
управления кэшем, которое определим как вероятность того, что на каком-либо временном
интервале требования на HR будут удовлетворены для обоих разделов. На качество работы
алгоритма влияют ошибка оценки текущих состояний потоков, вызванная низкой интенсив-
ностью входных потоков, а также ошибка определения последующего состояния, связанная со
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
74 В. С. Дужин, Г. С. Евсеев, Е. М. Линский
случайным характером переключения состояний входных потоков. Сначала рассмотрим иде-
альный случай, когда обе ошибки отсутствуют (построим верхнюю границу качества),
затем — когда присутствует лишь ошибка определения последующего состояния и, наконец,
когда присутствуют обе ошибки.
Вычислим верхнюю границу качества описанного алгоритма. Будем считать, что со-
стояния потоков на каждом временном интервале известны заранее. Соответственно выби-
раются оптимальные размеры разделов во всех случаях, когда это возможно. Требования по
HR не выполняются лишь тогда, когда оба входных потока находятся в состоянии S2 , по-
скольку в этом случае потребуется объем 2V2 > Vcache . Верхняя граница качества алгоритма
определяется следующим выражением:
Q1 = 1− P1(S2 )P2 (S2 ) ,
(9)
где P1(S2 ) и P2 (S2 ) — вероятность нахождения в состоянии S2 потоков запросов к 1-му и 2-му разделам, которая определяется из формулы полной вероятности [5]:
Pi (S2 ) = Pi (S1)Pi (S2 | S1) + Pi (S2 )Pi (S2 | S2 ) ,
(10)
где i = 1, 2 . Поскольку поток может быть в состоянии S1 либо в состоянии S2 ,
Pi (S1) = 1− Pi (S2 ) . Подставим (11) в (10) и после необходимых преобразований получим:
(11)
Pi (S2 )
=
Pi (S1
Pi (S2 | S1) | S2 ) + Pi (S2
|
S1)
.
(12)
Рассуждая аналогичным образом, можно вычислить вероятность нахождения потока в
состоянии S1:
Pi (S1)
=
Pi (S1
Pi (S1 | S2 ) | S2 ) + Pi (S2
|
S1)
.
Перепишем (9) с учетом (12):
(13)
Q1
=
1
−
(
P1(S1
|
S2
)
+
P1(S2 P1(S2 |
| S1)P2 (S2 | S1)
S1))( P2 (S1 | S2 )
+
P2
(S2
|
S1)
)
.
(14)
Вычислим оценку качества алгоритма при условии, что известны состояния входных
потоков за прошедший временной интервал (интенсивность потоков N → ∞ ), при этом прогноз следующего состояния осуществляется на основе матрицы переходов (1).
В таблице перечислены состояния системы, состоящей из двух разделов. Каждое со-
стояние характеризуется объемом разделов и состояниями их входных потоков. Заметим:
когда система находится в состояниях 1, 2, 5, 7, разделам хватает выделенных объемов для
выполнения требований. В состояниях 4, 8 требования не могут быть удовлетворены в прин-
ципе, поскольку входные потоки к обоим разделам находятся в состоянии S2 . В состояниях 3, 6 требования могут быть выполнены, если объем разделов выбран правильно. Таким обра-
зом, оценка качества работы данного алгоритма вычисляется с помощью следующего выра-
жения:
Q2 = Q1 − (P(3) + P(6)) ,
(15)
где P(3) , P(6) — вероятности перехода системы в соответствующие состояния. Выражение
(15) справедливо, поскольку P(3) и P(6) — вероятности несовместных событий.
Введем обозначение V (i) = {V (1) ,V (2)}. Пусть при V (1) первый раздел получает объем V1, второй V2 , а при V (2) — наоборот.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
Оценка эффективности алгоритма управления объемом разделов кэша
75
Пусть Pош (S (1) , S (2) ,V (1) ) — вероятность того, что распределение разделов V (1) даст ошибку, если на предыдущем интервале состояние первого раздела было S (1) , а второго — S (2) . Аналогичным образом определяется Pош (S (1), S (2) ,V (2) ) . Тогда минимальная вероятность ошибки для ситуации S (1) = S1, S (2) = S1 определяется следующим образом:
{ }Pош (S1, S1) = min Pош (S1, S1,V (1) ), Pош (S1, S1,V (2) ) .
№ состояния
1 2
3
4 5
6
7 8
Объем 1-го раздела
V1 V1
V1
V1 V2
V2
V2 V2
Объем 2-го раздела
V2 V2
V2
V2 V1
V1
V1 V1
Состояние 1-го потока
S1 S1
S2
S2 S1
S1
S2 S2
Состояние 2-го потока
S1 S2
S1
S2 S1
S2
S1 S2
Требования по HR
Выполнены Выполнены Не выполнены из-за ошибки Невыполнимы Выполнены Не выполнены из-за ошибки Выполнены Невыполнимы
Вероятность ошибки определяется как сумма таких вероятностей для всех комбинаций
S (1) , S (2) :
22
∑ ∑ { }Pош = P(3) + P(6) =
min Pош (Si , S j ,V (1) ), Pош (Si , S j ,V (2) ) .
(16)
i=1 j=1
Перепишем (15) с учетом (16):
∑ ∑ { }2 2
Q2 = Q1 −
min Pош (Si , S j ,V (1) ), Pош (Si , S j ,V (2) ) .
i=1 j=1
Очевидно, что данный алгоритм работает лучше, когда состояния входных потоков из-
меняются редко: при стремлении элементов главной диагонали матрицы (1) к единице Q2
стремится к Q1 ( P(S1 | S2 ) и P(S2 | S1) стремятся к нулю, вероятности P(3) и P(6) стремятся
к нулю и выражение (15) вырождается в (14)).
Теперь рассмотрим ситуацию, когда оценка состояний входных потоков производится
при конечной выборке. В этом случае к ошибке оценки следующего состояния добавляется
ошибка оценки текущего состояния.
Определим зависимость качества алгоритма от интенсивности N . Для этого выпишем
матрицу переходов системы из двух разделов:
⎧⎪P(1)
=
8
∑
P(i)
P(1
|
i),
⎪ i=1
⎪8
⎪⎪P(2) = ∑ P(i)P(2 | i),
⎨ i=1
⎪ ⎪
#
⎪8
⎪P(8) = ∑ P(i)P(8 | i).
⎩⎪ i=1
(17)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2013. Т. 56, № 8
76 В. С. Дужин, Г. С. Евсеев, Е. М. Линский
Пусть V (i) — распределение объемов разделов в i-м состоянии системы, например,
V (6) = V (2) .
Поскольку изменение объема раздела и изменение состояний входных потоков являются независимыми событиями, вероятность перехода из j-го в i-е состояние системы может быть представлена в виде произведения вероятности изменения объема раздела c Vt−1 на Vt и
вероятностей переходов состояний потоков 1-го и 2-го раздела соответственно: P1(St | St−1) и
P2 (St | St−1) :
P(i | j) = P(Vt , St(1) , St(2) | Vt−1, St(−11) , St(−21) ) = P(Vt | Vt−1, St(−11) , St(−21) )P1(St | St−1)P2 (St | St−1) . Вычислим P(Vt | Vt−1, St(−11) , St(−21) ) для случая Vt = V (2) ,Vt−1 = V (1) . Пусть оценка состояния первого потока оказалась более достоверной. Для того чтобы объем 1-го раздела стал равен
V2 , необходимо, чтобы в предыдущем интервале была получена оценка состояния потока Sˆ(2) = S2 . При этом объем данного раздела в предыдущем интервале должен быть равен V1.
Из (8) следует, что для этого должно быть выполнено условие R(V1, N, ξ) ≤ 1. Соответственно
P(Vt | Vt−1, St(−11) , St(−21) ) = P(R(V1, N , ξ) ≤ 1) . После необходимых преобразований с учетом (6), (12), (13) получим:
P(Vt
| Vt−1, St(−11) , St(−21) ) =
P
⎛ ⎜ ⎜ ⎝
ξ
<
ln
⎛ ⎜ ⎝⎜
⎛ ⎜ ⎝
1− 1−
h2 h1
⎞N ⎟ ⎠
P1(S2 P1(S1
| S1) | S2)
⎞ ⎟ ⎠⎟
ln
⎛ ⎜ ⎝
h1(1− h2 ) h2 (1− h1)
⎞ ⎟ ⎠
⎞ ⎟ ⎟ ⎠
.
(18)
Обозначим правую часть неравенства (18) через Ξ и перепишем его с учетом того, что
ξ имеет биномиальное распределение:
∑P(Vt | Vt−1, St(−11) , St(−21) ) = m