Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 1,021

ФОРМАЛЬНЫЕ АВТОМАТНЫЕ МОДЕЛИ АЛГОРИТМОВ ОБРАБОТКИ КЭШИРУЕМЫХ ДАННЫХ

Вашкевич Н.П. 1 Сибиряков М.А. 2
1 Пензенский государственный университет
2 Поволжский государственный технологический университет
Правильная организация алгоритмического управления в любой вычислительной системе значительно влияет на ее производительность, эффективность управления процессами и ресурсами. При разработке таких систем актуальна задача формализации алгоритмов обработки и управления. Особое внимание в данной статье уделяется математическому аппарату, связанному с формальным представлением алгоритмов в виде модели конечных автоматов. В качестве основной модели конечного автомата принята система рекуррентных канонических уравнений (СКУ), описывающих все реализуемые в системе частные события, принят язык граф-схем алгоритмов. Основной целью статьи является формализация рассматриваемых алгоритмов обработки кэшируемых данных в системах хранения данных с помощью СКУ. В статье представлены граф-схемы алгоритмов, на основе которых составлены системы канонических уравнений. Полученное математическое представление является, по существу, исполнимой формализованной спецификацией, которая позволяет осуществить непосредственный переход от СКУ к программной или аппаратной реализации данных алгоритмов.
системы хранения данных
обработка и хранение данных
кэширование
формализация алгоритмов
конечные автоматы
система канонических уравнений
1. Вашкевич Н.П. Выразительные возможности и эффективность формального языка, построенного на основе использования моделей недетерминированных автоматов // Известия высших учебных заведений. Поволжский регион. Технические науки. – 2006. – № 6. – С. 67–77.
2. Вашкевич Н.П., Зубков В.А. Алгоритм синтеза цифровых автоматов Мура с использованием языка исчисления предикатов // Вычислительная техника: Учебные записки. – Вып. 3. Пенза: Пенз. политехн. ин-т, 1969 – С. 25–36.
3. Вашкевич Н.П. Об одном способе синтеза цифровых автоматов по граф-схеме алгоритма с параллельными ветвями // Вычислительная техника: Межвуз. сб. науч. тр., Вып. 1, 2. – Пенза: Пенз. политехн. ин-т, 1973.
4. Вашкевич Н.П., Бикташев Р.А. Достоинство формального языка, основанного на концепции недетерминизма, при структурной реализации параллельных систем логического управления процессами и ресурсами // Известия высших учебных заведений. Поволжский регион. Технические науки. – 2011. – № 1 (7). – С. 3–11.
5. Sibiryakov M.A., Vasyaeva E.S., Koshpaev A.A. Analysis and comparison of cache memory control methods in storage systems // In the World Scientific. Ser.: Natural Technical Sciences. – Krasnoyarsk, 2014. – № 10 (58). – P. 276–280.

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

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

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

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

vah1a.tif

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

vah1b.tif

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

Таблица 1

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

Вершина укрупненной ГСА, Si

Номера составляющих вершин

S0

Начало

S1

51–55

X1

56

S2

57

X2

58, 59

X3

60

S6

61, 62

S5

63

S7

64–67

S8

68–70

X4

71

S9

72

S10

73–75

S11

76, 77

Sk

Конец

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

vah2.tif

Рис. 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

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

Вершина укрупненной ГСА, Si

Номера составляющих вершин

1

2

S0

Начало

S1

1, 2

X1

3

S2

4

S3

5–11

X2

12

X5

13

S6

15

S7

16–18

X6

20

X4

24

S17

LRU2

S18

39–44

1

2

S19

45, 46

X7

21

S10

22

S11

23, 25

X8

26

S12

27

S13

28

X3

14, 29

S14

LRU1

S15

30

S16

31–38

Sk

Конец

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

vah3.wmf

Рис. 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).

vah4.wmf

Рис. 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).

vah5.wmf

Рис. 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’.

Выводы

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


Библиографическая ссылка

Вашкевич Н.П., Сибиряков М.А. ФОРМАЛЬНЫЕ АВТОМАТНЫЕ МОДЕЛИ АЛГОРИТМОВ ОБРАБОТКИ КЭШИРУЕМЫХ ДАННЫХ // Современные наукоемкие технологии. – 2016. – № 8-2. – С. 205-213;
URL: http://www.top-technologies.ru/ru/article/view?id=36130 (дата обращения: 22.06.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074