Объектно-транзакционные модели программ на алгоритмических языках

Пекунов Владимир Викторович доктор технических наук Инженер-программист, ОАО "Информатика" 153000, Россия, Ивановская область, г. Иваново, ул. Ташкентская, 90 Pekunov Vladimir Viktorovich Doctor of Technical Science Software Engineer, JSC "Informatika" 153000, Russia, Ivanovskaya oblast', g. Ivanovo, ul. Tashkentskaya, 90 pekunov@mail.ru Другие публикации этого автора

Транзакционная память ^{[1, 2]} – достаточно хорошо изученный формализм для построения параллельных программ, отличающийся простотой распараллеливания, связанной с отсутствием необходимости в явных синхронизациях ^[3]. Теоретически интересным является вопрос, можно ли с помощью некоторого формализма, базирующегося на той или иной предельной модификации транзакционной памяти, строить произвольные (последовательные или параллельные) программы, используя единственную алгоритмическую конструкцию — ветвление. При этом явные циклы можно заменить многократным условным пересогласованием транзакции. Достаточно очевидно, что такая замена требует работы с данными, сохраняющими свои значения при откате транзакции ^[4], а значит и перехода от полной изоляции транзакций к их частичной изоляции. Такой подход к реализации транзакционной памяти известен ^[5], в данной работе используется авторский вариант такой памяти ^[6] – предельная частично транзакционная память, включающая единственную специальную транзакционную ячейку.

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

Общая постановка проблемы

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

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

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

а) если пересогласование по транзакционной памяти не требуется, то сеть всегда завершает работу за конечное время;

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

Введем теперь понятие предельной частично транзакционной памяти. Пусть она представляет собой ассоциативный кортеж R_K = (V_K, T_K), ключами K которого являются некие идентификаторы, а значениями V_K могут быть произвольные структуры данных, причем каждая ячейка может иметь собственный тип T_K со значениями из множества {a, t}. Ячейки типа a являются элементарными ячейками с атомарным доступом, единственная ячейка типа t относятся к транзакционной памяти, локальные значения которой, фактически, хранятся в векторе V_K = (L₁, …, L_N). Каждый i-й элемент такого вектора является двойкой (S_i, C_i), где S_i – метка времени первой модификации ячейки в i-ом потоке, C_i – локальная копия ячейки для i-го потока (всего N параллельных потоков – параллельных путей исполнения).

Пусть C – множество классов. Класс S представляет собой тройку (N_с, F, M), где N_с — идентификатор (имя) класса, F — поля, M — методы. Определим отношение иерархии parent: , заданное функцией

где e — пустая цепочка. Пусть каждый метод множества M представляет собой ветвящийся алгоритм, не содержащий циклов, имеющий полный доступ ко всем полям узла-объекта и ко всем ячейкам некоторой общей предельной частично транзакционной памяти, если таковая присутствует.

Гипотеза. Модель, включающая сетевой граф (P, E), содержащий множество P, включающее объекты классов C текущей предметной области (соединенные дугами из множества E), вызываемые в определенном выше порядке [с учетом того, что методы объектов, между которыми не определено отношение следования (по структуре модели), всегда выполняются в параллель], функционирующие по ветвящимся алгоритмам в условиях предельной частично транзакционной памяти со специальным согласованием, способна выполнить произвольный разрешимый по Тьюрингу последовательный или параллельный алгоритм.

Назовем такие модели объектно-транзакционными (ОТМ).

Непараллельные ОТМ

Введем понятие предельной непараллельной объектно-транзакционной модели. Пусть такая модель является двойкой (R, N), где R – ассоциативный кортеж предельной частично транзакционной памяти, N – сеть из единственного узла-объекта A, относящегося к некоторому классу.

Введем специальный механизм согласования единственной транзакционной ячейки. Пусть она имеет идентификатор RESTART и хранит ссылку на текущий исполняемый метод объекта A (сразу заметим, что в случае ОТМ из нескольких узлов это будет список пар вида (A, M[A]), где A – ссылка на узел, M[A] -- ссылка на метод узла A), отличающаяся тем, что

а) в начале исполнения модели данная ячейка хранит ссылку на специальный метод, всегда вызываемый первым;

б) любое присваивание данной ячейке ссылки на произвольный метод неминуемо приводит к необходимости пост-пересогласования текущей транзакции (всей сети, по окончании ее текущей интерпретации) с вызовом указанного метода;

в) перед пост-пересогласованием текущей транзакции определяются подлежащие вызову методы объектов – это методы, ссылки на которые занесены в RESTART. Далее ячейка RESTART очищается и начинается пост-пересогласование транзакции (всей сети с самого начала).

Отметим, что все ячейки памяти типа a не влияют на процесс согласования.

Теорема 1. Предельная непараллельная ОТМ способна реализовать произвольный разрешимый по Тьюрингу алгоритм.

Доказательство. Рассмотрим произвольную программу на алгоритмическом языке высокого уровня C (с расширением, реализующим требуемый механизм согласования предельной частично транзакционной памяти). Если такая программа не содержит циклов, то она может быть реализована произвольным методом (реализующим произвольный ветвящийся алгоритм) единственного объекта предельной непараллельной ОТМ по определению.

Пусть программа содержит циклы. Эквивалентно трансформируем ее по следующим правилам:

а) свяжем с каждым оператором некую условную метку;

б) введем нетранзакционную переменную CURLABEL, хранящую имя метки текущего оператора;

в) в начале программы CURLABEL содержит метку начального оператора;

г) каждый оператор с меткой предваряем конструкцией вида

[else] if (CURLABEL == метка_текущего_оператора) {

д) в каждом операторе с меткой производим соответствующие присваивания переменной CURLABEL меток операторов, выполняемых следующими;

е) в конце каждого оператора ставим закрывающий блок знак «}», перед которым (за исключением операторов, исполняемых последними), ставим конструкцию рассогласования текущей транзакции (приводящую к ее последующему повтору по завершению текущего сеанса обработки сети) путем присваивания переменной RESTART ссылки на текущий метод;

ж) сначала преобразуем все циклы в цикл while;

з) каждый цикл while вида;

Метка1: while(условие) { Оператор_A; … Оператор_B; } Оператор_С;

заменим на условные операторы:

if (CURLABEL == Метка1 && условие) { CURLABEL = Метка_A; RESTART = …; }

else if (CURLABEL == Метка1 && !условие) { CURLABEL = Метка_C; RESTART = …; }

else if (CURLABEL == Метка_A) { Оператор_A; CURLABEL = …; RESTART = …; }

…

else if (CURLABEL == Метка_B) { Оператор_B; CURLABEL = Метка_1; RESTART = … }

else if (CURLABEL == Метка_C) { Оператор_C; … }

и) вся программа заключается в транзакционный блок;

к) все переменные программы оформляем как ячейки типа a предельной частично транзакционной памяти.

Получили эквивалентную программу, которая может быть исполнена произвольным методом ОТМ по определению. Итак, предельная непараллельная ОТМ способна реализовать произвольную программу (например, на алгоритмическом языке высокого уровня C), которой, как известно, может быть программа, реализующая алгоритм функционирования машины Тьюринга (способной реализовать произвольный разрешимый по Тьюрингу алгоритм), следовательно, такая ОТМ способна реализовать произвольный разрешимый по Тьюрингу алгоритм. Также отметим несомненную прямую структурную аналогию между полученной после преобразования программой на C и кодом для машины Тьюринга.

Доказано.

Следствие. Поскольку предельная непараллельная ОТМ способна реализовать произвольный, разрешимый по Тьюрингу алгоритм, следовательно, и непредельная непараллельная ОСМ способна реализовать такой алгоритм (например, используя один свой произвольный узел).

Параллельные ОТМ

Введем понятие предельной параллельной (K-поточной) объектно-транзакционной модели. Пусть такая модель является двойкой (R, N), где R – ассоциативный кортеж предельной частично транзакционной памяти, N – сеть, включающая узлы с пустыми методами (исток и сток), а также K рабочих узлов с непустыми методами, в каждый из которых входит дуга из истока и из каждого исходит дуга в сток. Пусть модель выполняет транзакционный блок по всем описанным выше правилам (возможно, с многократным пост-пересогласованием), учитывая, что процессы узлов, находящихся в ветвях, для которых не определено отношение следования, выполняются параллельно.

Теорема 2. Предельная параллельная (K-поточная) ОТМ способна реализовать произвольный разрешимый по Тьюрингу алгоритм с K параллельными ветвями.

Доказательство. Выше было показано, что одноузловая непараллельная ОТМ способна реализовать произвольный, разрешимый по Тьюрингу алгоритм. Здесь мы имеем систему из K узлов (которые могут работать параллельно), каждый из которых можно рассматривать как отдельную ОТМ, взаимодействующую с прочими ОТМ через общую память. Таким образом, всю систему можно рассматривать как K параллельно работающих машин Тьюринга, обменивающихся данными, например, через общую ленту. Соответственно, данная система способна выполнить произвольный разрешимый по Тьюрингу алгоритм с K параллельными ветвями.

Следствие. Поскольку предельная параллельная (K-поточная) ОТМ способна реализовать произвольный параллельный K-поточный алгоритм, разрешимый по Тьюрингу, следовательно и непредельная параллельная ОСМ с не менее чем K параллельными ветвями способна реализовать такой алгоритм.

Основные свойства ОТМ

В заключение сформулируем некоторые основные свойства объектно-транзакционных моделей, предложенных в данной работе. Данные свойства вытекают либо из основных структурно-функциональных особенностей моделей, либо из доказанных выше положений. Итак, основные свойства:

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

2. Алгоритмическая полнота по Тьюрингу (следует из теоремы 1).

3. Естественное описание параллелизма (параллельные и непараллельные процессы четко определяются структурой модели).

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

5. Принципиальная неоднородность используемых видов памяти при неизбыточной (исключающей простое дублирование тел циклов) реализации алгоритмов, содержащих циклы со счетчиком или межвитковыми зависимостями. Следует из того факта, что модель имеет сетевую структуру, ее методы также имеют ветвящуюся структуру, поэтому такие циклы неизбыточно могут быть реализованы только за счет пересогласования модели (требуется ячейка RESTART предельной частично транзакционной памяти) с сохранением изменяющегося контекста [счетчиков или иных общих для витков цикла переменных (требуются ячейки типа a частично транзакционной памяти)].

Выводы

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