Scientific journal

Modern high technologies

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

Для обеспечения обработки и хранения большого объема информации в современных сетевых инфраструктурах применяются системы хранения данных (СХД). Одним из способов повышения производительности СХД является использование кэширования. Производительность применяемой в таких системах кэш-памяти во многом определяется эффективностью реализуемых алгоритмов обработки кэшируемых данных. При разработке таких алгоритмов актуальной задачей является их формальное представление. Одним из способов формального описания алгоритмов является применение математического аппарата, связанного с их представлением на основе модели конечных автоматов с использованием рекуррентных бескванторных предикатных уравнений или систем канонических уравнений, предложенных Н.П. Вашкевичем для последовательных [1, 2] и параллельных [3, 4] алгоритмов.

Системы канонических уравнений для алгоритмов обработки кэшируемых данных

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

На рис. 1 и 2 представлены блок-схемы алгоритмов обработки кэшируемых данных, разработанных в рамках модификации метода обработки кэшируемых данных с использованием индексных таблиц [5]. Для них разработаны укрупненные граф-схемы алгоритмов (ГСА, рис. 3 и 4), на основе которых построены СКУ. Результаты укрупнения представлены в табл. 1 и 2. В данных ГСА следующие подряд условные вершины разделены операторными вершинами – разделительными событиями, которые подразумевают ожидание. Они введены для упрощения и корректной реализации СКУ. Операторы ГСА требуют различных времен выполнения, поэтому каждое уравнение СКУ построено не только при учете условий зарождения, но и при учете условия сохранения события.

Рис. 1. Блок-схема модифицированного алгоритма обработки команды чтения данных

Продолжение рис. 1

Таблица 1

Вершины модифицированного алгоритма вытеснения данных, составляющие операторы укрупненных ГСА

Примечание. События S3, S4 – разделительные.

Рис. 2. Блок-схема модифицированного алгоритма вытеснения чтения

СКУ1 для ГСА1:

S0(t + 1) = S0(t)&¬x0(t) ∨ xbegin(t);

S1(t + 1) = S0(t)& x0(t) ∨ S1(t)&¬z1(t);

S2(t + 1) = S1(t)&z1(t)&x1(t) ∨ S2(t)&z2(t)&x1(t) ∨ S2(t)&¬z2(t);

S3(t + 1) = S1(t)&z1(t)&¬x1(t) ∨ S2(t)&z2 (t)&¬x1(t) ∨ S3(t)&¬z3(t);

S4(t + 1) = S3(t)&z3(t)&x2(t) ∨ S4(t)&¬z4(t);

S5(t + 1) = S4(t)&z4(t)&x3(t) ∨ S5(t)&¬z5(t);

S6(t + 1) = S4(t)&z4(t)&¬x3(t) ∨ S6(t)&¬z6(t);

S7(t + 1) = S5(t)&z5(t) ∨ S6(t)&z6(t) ∨ S7(t)&¬z7(t);

S8(t + 1) = S3(t)&z3(t)¬x2(t) ∨ S8(t)&¬z8(t);

S9(t + 1) = S8(t)&z8(t)&x4(t) ∨ S9(t)&z9(t)&x4(t) ∨ S9(t)&¬z9(t);

S10(t + 1) = S8(t)&z8(t)&¬x4(t) ∨ S9(t)&z9(t)&¬x4(t) ∨ S10(t)&¬z10(t);

S11(t + 1) = S10(t)&z10(t) ∨ S7(t)&z7(t) ∨ S11(t)&¬z11(t);

Sk(t + 1) = S11(t)&z11(t) ∨ Sk(t)&¬zk(t),

где Si(t) – унарный предикат, определенный на множестве значений дискретного времени t. Истинность Si(t) означает, что автомат находится в состоянии Si в момент времени t, или в автомате реализуется частное событие Si в момент времени t. Входные сигналы xj(t) – частичные, т.е. на переход влияет сам сигнал, а не комбинация всех сигналов, как в случае полного автомата; xbegin(t) – сигнал установки автомата в начальное состояние. Входные сигналы xj(t) представлены унарными предикатами.

Исходя из того, что времена работы операторов различные, необходимо учесть условия окончания работы операторов, то есть каждый оператор по окончании своей работы должен выдать сигнал окончания. Тогда примем, что zi(t) – условие сохранения события Si при zi(t) = 0 («false»); при zi(t) = 1 («true») событие Si не сохраняется и происходит переход к следующему событию. Сигнал, или условие zi(t), формируется при выполнении события Si (условие zi(t) может быть истинным только после выполнения события Si). Использование условия сохранения позволяет событию Si выполняться за необходимое количество тактов.

Используемый в работе алгоритмов индекс включает в себя шесть базовых индексных таблиц [4]: ХТУДК – хеш-таблица управления; ТУСС – таблица управления свободными сегментами; УИОСДК – таблица, хранящая управляющую информацию о секторах дискового кэша; УИОСИС – таблица, содержащая управляющую информацию о совместно используемых сегментах; ТУСДК – таблица управления секторами дискового кэша.

Таблица 2

Вершины модифицированного алгоритма обработки команды чтения данных, составляющие операторы укрупненных ГСА

Примечание. События S4, S5, S8, S9 – разделительные.

Рис. 3. Граф-схема модифицированного алгоритма вытеснения данных (ГСА1)

СКУ2 для ГСА2:

S0(t + 1) = S0(t)&¬x0(t) ∨ xbegin(t);

S1(t + 1) = S0(t)&x0(t) ∨ S1(t)&¬z1(t);

S2(t + 1) = S1(t)&z1(t)&x1(t) ∨ S2(t)&z2(t)&x1(t) ∨ S2(t)&¬z2(t);

S3(t + 1) = S1(t)&z1(t)&¬x1(t) ∨ S2(t)&z2(t)&¬x1(t) ∨ S3(t)&¬z3(t);

S4(t + 1) = S3(t)&z3(t)&x2(t) ∨ S6(t)&z6(t)&x2(t) ∨ S4(t)&¬z4(t);

S5(t + 1) = S3(t)&z3(t)&¬x2(t) ∨ S6(t)&z6(t)&¬x2(t) ∨ S5(t)&¬z5(t);

S6(t + 1) = S5(t)&z5(t)&x5(t) ∨ S6(t)&¬z6(t);

S7(t + 1) = S5(t)&z5(t)&¬x5(t) ∨ S7(t)&¬z7(t);

S8(t + 1) = S7(t)&z7(t)&x6(t) ∨ S10(t)&z10(t)&x6(t) ∨ S8(t)&¬z8(t);

S9(t + 1) = S7(t)&z7(t)&¬x6(t) ∨ S10(t)&z10(t)&¬x6(t) ∨ S9(t)&¬z9(t);

S10(t + 1) = S9(t)&z9(t)&x7(t) ∨ S10(t)&¬z10(t);

S11(t + 1) = S9(t)&z9(t)&¬x7(t) ∨ S11(t)&¬z11(t);

S12(t + 1) = S11(t)&z11(t)&x8(t) ∨ S12(t)&z12(t)&x8(t) ∨ S12(t)&¬z12(t);

S13(t + 1) = S11(t)&z11(t)&¬x8(t) ∨ S12(t)&z12(t)&¬x8(t) ∨ S13(t)&¬z13(t);

S14(t + 1) = S4(t)&z4(t)&x3(t) ∨ S14(t)&¬z14(t);

S15(t + 1) = S4(t)&z4(t)&¬x3(t) ∨ S14(t)&z14(t) ∨ S15(t)&¬z15(t);

S16(t + 1) = S15(t)&z15(t) ∨ S16(t)&¬z16(t);

S17(t + 1) = S8(t)&z8(t)&x4(t) ∨ S17(t)&¬z17(t);

S18(t + 1) = S17(t)&z17(t) ∨ S8(t)&z8(t)&¬x4(t) ∨ S18(t)&¬z18(t);

S19(t + 1) = S16(t)&z16(t) ∨ S18(t)&z18(t) ∨ S19(t)&¬z19(t);

Sk(t + 1) = S13(t)&z13(t) ∨ S19(t)&z19(t) ∨ Sk(t)&¬zk(t).

Рис. 4. Граф-схема алгоритма обработки команды чтения данных (ГСА2)

Система канонических уравнений для параллельного алгоритма обращения к индексным таблицам

Аналогичным образом представлена граф-схема разработанного параллельного алгоритма обращения к индексным таблицам (рис. 5), применяемого в рамках выполнения алгоритмов обработки кэшируемых данных. Приведена ее формализация с помощью СКУ.

СКУ3 для ГСА3:

S0(t + 1) = S0(t)&¬x0(t) ∨ xbegin(t);

S1(t + 1) = S0(t)&x0(t) ∨ S1(t)&¬z1(t);

S2(t + 1) = S0(t)&x0(t) ∨ S2(t)&¬z2(t);

S’1(t + 1) = S1(t)&z1(t) ∨ S’1(t)&¬(S3(t) ∨ S17(t));

S’2(t + 1) = S2(t)&z2(t) ∨ S’2(t)&¬( S3(t) ∨ S17(t));

S3(t + 1) = S’1(t)&S’2(t)&x1(t) ∨ S3(t)&¬z3(t);

S 4(t + 1) = S3(t)&z3(t)&x2(t)∨ S4(t)&¬z4(t);

S5(t + 1) = S3(t)&z3(t)&¬x2(t) ∨ S5(t)&¬z5(t);

S6(t + 1) = S5(t)&z5(t)&¬x3(t) ∨ S6(t)&¬z6(t);

S 7(t + 1) = S6(t)&z6(t)∨ S7(t)&¬z7(t);

S8(t + 1) = S7(t)&z7(t)&¬x4(t) ∨ S8(t)&¬z8(t);

S9(t + 1) = S7(t)&z7(t)&¬x4(t) ∨ S9(t)&¬z9(t);

S10(t + 1) = S7(t)&z7(t)&x4(t) ∨ S10(t)&¬z10(t);

S11(t + 1) = S7(t)&z7(t)&x4(t) ∨ S11(t)&¬z11(t);

S’8(t + 1) = S8(t)&z8(t) ∨ S’8(t)&¬S12(t);

S’9(t + 1) = S9(t)&z9(t) ∨ S’9(t)&¬S12(t);

S’10(t + 1) = S10(t)&z10(t) ∨ S’10(t)&¬S12(t);

S’11(t + 1) = S11(t)&z11(t) ∨ S’11(t)&¬S12(t);

S12(t + 1) = S’8(t)&S’9(t)&S’10(t)&S’11(t) ∨ S12(t)&¬z12(t);

S13(t + 1) = S12(t)&z12(t)∨S5(t)&x3∨ S13(t)&¬z13(t);

S14(t + 1) = S12(t)&z12(t)∨S5(t)&x3∨ S14(t)&¬z14(t);

S15(t + 1) = S12(t)&z12(t)∨S5(t)&x3∨ S15(t)&¬z15(t);

S16(t + 1) = S12(t)&z12(t)∨S5(t)&x3∨ S16(t)&¬z16(t);

S’13(t + 1) = S13(t)&z13(t)∨ S’13(t)&¬Sk(t);

S’14(t + 1) = S14(t)&z14(t)∨ S’14(t)&¬Sk(t);

S’15(t + 1) = S15(t)&z15(t)∨ S’15(t)&¬Sk(t);

S’16(t + 1) = S16(t)&z16(t)∨ S’16(t)&¬Sk(t);

S17(t + 1) = S’1(t)&S’2(t)&¬x1(t) ∨ S17(t)&¬z17(t);

S18(t + 1) = S17(t)&z17(t)&¬x5(t) ∨ S18(t)&¬z18(t);

S19(t + 1) = S18(t)&z18(t)& ∨ S19(t)&¬z19(t);

S20(t + 1) = S18(t)&z18(t)& ∨ S20(t)&¬z20(t);

S21(t + 1) = S18(t)&z18(t)&∨ S21(t)&¬z21(t);

S’19(t + 1) = S19(t)&z19(t) ∨ S’19(t)&¬S22(t);

S’20(t + 1) = S20(t)&z20(t) ∨ S’20(t)&¬S22(t);

S’21(t + 1) = S21(t)&z21(t) ∨ S’21(t)&¬S22(t);

S22(t + 1) = S’19(t)&S’20(t)&S’21(t)∨ S17(t)&x5∨ S’22(t)¬z22(t);

S23(t + 1) = S22(t)&z22(t)∨ S23(t)&¬z23(t);

S24(t + 1) = S23(t)&z23(t)∨ S24(t)&¬z24(t);

S25(t + 1) = S23(t)&z23(t)∨ S25(t)&¬z25(t);

S26(t + 1) = S23(t)&z23(t)∨ S26(t)&¬z26(t);

S27(t + 1) = S23(t)&z23(t)∨ S27(t)&¬z27(t);

S’24(t + 1) = S24(t)&z24(t) ∨ S’24(t)&¬Sk(t);

S’25(t + 1) = S25(t)&z25(t) ∨ S’25(t)&¬Sk(t);

S’26(t + 1) = S26(t)&z26(t) ∨ S’26(t)&¬Sk(t);

S’27(t + 1) = S27(t)&z27(t) ∨ S’27(t)&¬Sk(t);

Sk(t + 1) = S4(t)&z4(t) ∨ S’13(t)&S’14(t)&S’15(t)&S’16(t)∨ S’24(t)&S’25(t)&S’26(t)&S’27(t)∨ Sk(t)&¬zk(t).

Рис. 5. Граф-схема параллельного алгоритма обращения к индексным таблицам (ГСА3)

Аналогично предыдущим случаям в СКУ3 учтены условия сохранения событий. Для параллельных событий (S8, S9; S10, S11; S13 – S16; S19 – S21; S24 – S27) принято, что факт завершения каждого Si-го события отмечается последующим появлением события Si’. Например, для подтверждения фактов завершения событий S1 и S2 определены события S1’ и S2’. С того момента t, как только высказывания S1’(t) и S2’(t) одновременно станут истинными («true»), в зависимости от значения входного символа x1 появится одно из событий S3 или S17, которое в следующем такте «прекратит» выполнение событий S1’ и S2’.

Выводы

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