М. Рузинкевич

marek@cs.uh.edu

А. Цикоцки**)

andrzej@cs.uh.edu

Department of computer Science University of Houston Houston, TX 77204-3475


4. Выполнение потоков работ
5. Существующие продукты и исследовательские прототипы
6 Заключение
Литература

4. Выполнение потоков работ

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

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

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

4.1. Планирование потока работ

Вначале мы обсудим цели планировщика, а затем рассмотрим некоторые подходы и прототипы.

4.1.1. Цели планировщика

Основными целями планировщика является обеспечение следующего:

  • Корректности планирования. Процесс планирования не может нарушить ни одну из зависимостей, представленную в спецификации потока работ. Кроме того, планировщик связан ограничениями, налагаемыми глобальным управлением параллельным выполнением, поскольку неконтролируемое взаимодействие задач, принадлежащих разным потокам работ, может привести к неверным результатам. Определение того, могут ли быть удовлетворены временные зависимости планирования, является особенно трудной задачей [23]. Планировщик должен учитывать, что при наличии временных зависимостей логические значения предикатов планирования могут изменяться динамически, без каких бы то ни было воздействий со стороны системы. В то же время, эти зависимости ограничивают возможные действия планировщика (например, указывая, что задача не может быть запущена ранее 10:00).
  • Безопасность. Планировщик должен гарантировать, что поток работ будет завершен в одном из специфицированных приемлемых заключительных состояний. Перед попыткой выполнения потока работ планировщик должен обратиться к спецификации, чтобы проверить, не завершается ли этот поток в неприемлемом состоянии. Если планировщик не может гарантировать, что поток работ будет завершен в приемлемом состоянии, он должен отвергнуть такую спецификацию, не пытаясь выполнить данный поток работ. Даже если спецификация потока работ является безопасной, т. е. приемлемое состояние завершения может быть всегда достигнуто, все равно остаются проблемы с выполнением потока работ, возникающие из-за возможности возникновения разного рода тупиков. Чтобы гарантировать отсутствие тупиков в потоке работ, можно использовать формальные методы спецификации и анализа (упомянутые в разделе 3.5). Задачей планировщика потока работ является построение стратегии выполнения, гарантирующей, что поток работ не будет завершен в неприемлемом состоянии.
  • Оптимальная политика планирования. Планировщику следует достигать приемлемых состояний завершения "оптимальным" образом. Тем не менее, понятие "оптимальный" может различаться для разных приложений. Одним из возможных определений может быть достижение цели за наиболее короткое время. Другим - связывание оценочной функции с выполнением каждой задачи. Тогда целью планировщика было бы выполнение всего потока работ с минимальной стоимостью. Если заранее известны вероятности успешного выполнения задач, планировщик может использовать их для нахождения стратегии выполнения, с максимальной вероятностью приводящей к глобальному успешному завершению.
  • Обработка отказов. Планировщик должен быть способен достигать приемлемого состояния завершения даже в случае возникновения отказа. Например, планировщик мог бы продолжить обработку после отказа и соответствующего восстановления как-будто "ничего не произошло", обеспечивая "возможность прямого восстановления" (forward recoverability). И, наоборот, планировщик мог бы прекратить выполнение всего потока работ (т. е. достигнуть одного из глобальных состояний аварийного завершения). Оба подхода требуют того, чтобы информация о состоянии сохранялась в случае отказа, поскольку даже во втором случае может потребоваться фиксация или возобновление выполнения некоторых подтранзакций (например, компенсирующих подтранзакций). Следовательно, планировщик должен журнализовать на надежном запоминающем устройстве всю информацию о своем состоянии, которая может потребоваться для восстановления и продолжения обработки.

4.1.2. Архитектура планировщика потока работ

В литературе описаны несколько планировщиков транзакций мультибаз данных. Однако большинство из предлагаемых решений затрагивают только часть проблем, обозначенных выше. Поэтому такие планировщики могут быть полезны только в специальных, ограниченных случаях. За исключением [3], все планировщики разработаны в основном для транзакций мультибаз данных, специального типа потоков работ. Планировщик, основанный на модели предикатных сетей Петри (Predicate Petri Nets model) [16] был разработан для управления гибкими транзакциями (Flexible Transactions). Другой исполнитель гибких транзакций был разработан с использованием логического параллельного языка L.0 [6, 2]. Пример подхода к планировщику как к интерпретатору языка спецификаций транзакций мультибаз данных для гибких транзакций описан в [33], где для спецификации транзакций мультибаз данных используется язык Vienna Parallel Logic (VPL). Планировщик может также быть разработан как интерпретатор правил Событие-Условие-Действие (Event-Condition-Action - ECA), как это описывается в [11, 12]. Аналогичный подход обсуждается в [22], где межзадачные зависимости в транзакциях мультибаз данных реализуются с использованием правил ECA. Подход, согласно которому процесс планирования моделируется игрой планировщика против своего окружения, представленного локальными системами баз данных, описан в [46]. Планировщик может также использовать модель конечных автоматов [31] для анализа зависимостей между подтранзакциями и для определения достижимости приемлемых состояний посредством инструментов анализа протоколов. Еще один прототип, представленный в литературе [3], использует темпоральную пропозициональную логику для планирования и соблюдения межзадачных зависимостей.

Прототип частично распределенного планировщика потоков работ недавно был разработан в Университете Хьюстона. На Рис. 3 представлена общая архитектура этого планировщика. Основными частями системы являются:

  • синтаксический анализатор, преобразующий спецификацию потока работ, написанную на языке METEOR ([35]) во внутреннее представление правил планирования;
  • планировщик потока работ, выполняющий эти правила;
  • глобальный менеджер параллельного выполнения, координирующий выполнение нескольких потоков работ;
  • монитор выполнения потоков работ, предназначенный для графического отображения развития выполнения потоков;
  • набор менеджеров задач, выполняющих роль интерфейса между планировщиком и системами обработки, реально выполняющими задачи;
  • набор обрабатывающих объектов;
  • коммуникационная подсистема;
  • словари.

Picture 3

Рисунок 3.
Архитектура Прототипа Планировщика Потока Работ.

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

4.2. Параллельное выполнение потоков работ

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

В предположении, что каждый поток работ выполняется корректно, параллельное выполнение нескольких потоков является корректным, если оно, в некотором смысле, эквивалентно последовательному, без взаимного влияния, выполнению этих потоков. При отсутствии какой-либо дополнительной информации о существующих ограничениях, налагаемых на состояния множества систем, участвующих в выполнении потока работ, и о свойствах потоков работ, для достижения упомянутой эквивалентности требуется поддержка глобальной сериализуемости и глобальной фиксируемости (commitment) потоков работ. Если доступна дополнительная информация (например, требования атомарности в связи со сбоями и атомарности для обеспечения изолированности для каждого потока работ), могут быть применимы более слабые критерии корректности параллельного выполнения потоков работ.

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

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

Неформально, глобальная история является М-сериализуемой, если каждая локальная история является сериализуемой, и никакие два потока работ Wi и Wj не включают задачи Tik, Til, относящиеся к одной атомарной единице выполнения Wi, и задачи Tjk и Tjl, относящиеся к одной атомарной единице выполнения Wj, такие, что Tikjk и Tiljl. Глобальная сериализуемость требует, чтобы порядок сериализации потока работ был бы совместимым для всех обрабатывающих объектов. Другими словами, если задача Ti потока Wi предшествует задаче Tj потока Wj в каком-либо обрабатывающем объекте, то ни в каком другом объекте задача потока Wj не может предшествовать задаче потока Wi. Для М-сериализуемости требуется только то, чтобы задачи, относящейся к одной атомарной единице выполнения потока работ, имели совместимый порядок сериализации во всех узлах, к которым они имеют доступ. М-сериализуемость допускает некоторые глобальные истории, которые были бы отвергнуты в случае глобальной сериализуемости. Это происходит вследствие того, что операции задачи Ti не связаны с операциями задач, которые относятся к атомарным единицам выполнения, отличающимся от той, к которой относится Ti. Следовательно, порядок сериализации задачи Ti влияет на порядок сериализации только тех задач, которые относятся к той же атомарной единице выполнения, что и Ti, а не всех задач потока Wi, как в случае глобальной сериализуемости.

В качестве примера рассмотрим историю, представленную на Рис. 4. Предположим, что каждый из двух идентичных потоков работ W1 и W2 состоит из двух атомарных единиц {T11,T12} и {T13} и {T21,T22} и {T23}, соответственно. Далее, пусть порядок сериализации между T11 и T21, установленный в узле Site1, не влияет на порядок сериализации в узле Site3. С другой стороны, поскольку задачи T12 и T22 конфликтуют, Т 22 должна быть выполнена раньше, чем T12. Формальное определение М-сериализуемости и механизм ее обеспечения представлены в [46].

Picture 4

Рисунок 4.

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

Схема, основанная на альтруистическом блокировании (Altruistic locking) [48], была предложена в [31]. В этой схеме предполагается, что в каждый момент времени только один поток работ может иметь доступ к узлу обработки, и, следовательно, существует полная изолированность между сосуществующими потоками работ. Для достижения сериализуемого выполнения потокам работ предоставляются блокировки установок в одном и том же порядке на каждой установке. Таким образом, если блокировка установки S1 была предоставлена задаче из потока Wi прежде, чем задаче из потока Wj, то этот порядок должен сохраняться на каждой установке. Для предотвращения косвенных конфликтов локальных транзакций в связи с потоками работ требуется, чтобы локальные системы поддерживали строгое планирование, применяя, например, механизм строгих двухфазных блокировок при управлении параллельным выполнением [4].

Алгоритм альтруистического блокирования предполагает возможность конфликта между любыми двумя выполняемыми в одно и то же время потоками работ. Такое пессимистическое предположение уменьшает возможную степень параллельности при выполнении потока работ, уменьшая тем самым производительность системы. Тем не менее, если семантика всех задач известна заранее, может быть разработан механизм управления параллельным выполнением, учитывающий только существенные конфликты. Это может повысить эффективность системы. Семантическое управление параллельным выполнением предназначено для специфического семейства приложений, в которых ограничения корректности определяются отдельно для каждого класса задач. Некоторые задачи должны сериализоваться, другие могут допускать некоторую несогласованность и, тем самым, могут быть выполнены несериализуемым образом. Менеджер параллельного выполнения, имея информацию об этих ограничениях, предоставляет блокировки задачам таким образом, чтобы выполнялись критерии корректности. Алгоритм, реализующий семантическое управление параллельным выполнением для группы телекоммуникационных приложений, описан в [36].

Следует заметить, что если все задачи выполняемых потоков работ коммутативны, никакое управление параллельным выполнением не требуется. Большинство коммерческих продуктов выполнения потоков работ разработаны для потоков, задачи которых разрабатываются вручную и предполагаются коммутативными. Поэтому обычно в этих продуктах не реализуется какой-либо механизм управления параллельным управлением.

4.3. Восстановление потока работ

Целью восстановления после отказа при выполнении потоков работ является обеспечение атомарности потоков работ в связи со сбоями. Процедуры восстановления должны гарантировать, что в случае возникновения отказа в любом из компонентов, принимающих участие в обработке потока работ (включая планировщик), поток все равно достигнет приемлемого состояния - возможно, с использованием компенсации. Мы можем предположить, что обрабатывающие объекты, принимающие участие в выполнении потока работ, обладают своими собственными локальными системами восстановления и сами обрабатывают возникающие в них локальные отказы. Поэтому мы будем обсуждать только отказы менеджеров выполнения потока работ (планировщика(ов) и менеджера параллельного выполнения).

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

Отказ менеджера параллельного выполнения может быть обнаружен посредством механизмов временного контроля, а информация о состоянии может быть реконструирована путем просмотра журналов. В предположении возможности прямого восстановления [44] и идемпотентности обрабатывающих объектов, выполнение потока работ может быть продолжено простым перезапуском незавершенных задач.

Нам также требуется обращать внимание на содержимое очередей запросов. Если используется механизм, обеспечивающий функции стабильных программных каналов (например, в системе VMS компании DEC очереди могут быть реализованы c использованием почтовых ящиков - стабильных очередей сообщений, доступных как виртуальные устройства ввода/вывода), сообщения хранятся на постоянном запоминающем устройстве и не теряются в случае отказа. Если очереди хранятся на ненадежном запоминающем устройстве (например, в среде ОС UNIX очереди могут быть реализованы с использованием сокетов), вместо восстановления содержимого очередей можно пойти на то, чтобы планировщики повторно посылали свои запросы.

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

5. Существующие продукты и исследовательские прототипы

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

Продукт Staffware, предлагаемый компанией Staffware, был первым программным продуктом, разработанным для автоматизации потоков работ. Staffware - это система, разработанная в технологии клиент/сервер и предназначенная для автоматизации хорошо определенных процедур, относящихся к интенсивному документообороту. Пакет поставляется для различных вариантов UNIX и Windows и может быть интегрирован с базами данных, системами электронной почты и системами обработки текста. Базовая часть Staffware содержит механизмы управления последовательным и параллельным управлением задач с зависимостями планирования, основанными на событиях, значениях данных и достигнутом времени выполнения. Набор графических интерфейсов позволяет пользователю определять и конфигурировать потоки работ и моделировать выполнение потока работ для обнаружения потенциальных узких мест.

Продукт InConcert, предлагаемый на рынке подразделением компании Xerox, является объектно-ориентированным средством создания и выполнения приложений, основанных на потоках работ. Возможности InConcert включают основанную на правилах спецификацию потока работ, триггеры событие-действие, временные и приоритетные зависимости и динамическую модификацию потока работ. InConcert является независимым от приложения и хранит всю информацию о потоке работ, как-то определение, атрибуты, информацию протоколирования и обеспечения безопасности, события и действия в SQL-ориентированной, совместимой со стандартом ANSI базе данных (например, Oracle или Sybase).

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

По сравнению с коммерческими продуктами, в исследовательских прототипах большее внимание уделяется транзакционным свойствам (изолированность или восстановимость) потоков работ. Как правило, возможности, предоставляемые этими проектами, могут использоваться как для реализации управления ослабленными транзакциями, так и для обработки потоков работ. Примеры таких сред обеспечивают проекты Narada [29], Contracts [44], Interbase [15], Carnot [52] и Distributed Object Management (DOM) [22].

Работа по выполнению мультисистемных приложений в неоднородной вычислительной среде ведется в рамках проекта Omnibase в Хьюстонском университете с 1985 года [28]. Основным вкладом этого проекта в управление потоками работ была разработка языка спецификаций задач DOL и распределенной среды выполнения Narada. Архитектура программного обеспечения, основанная на языке спецификаций задач, в дальнейшем была использована и развита в ряде проектов, включая Ernie в Bellcore, Interbase в Purdue [47], Narada в Хьюстоне [26] и Carnot в MCC [55].

Система, основанная на DOL, состоит из каталога ресурсов, ядра DOL и набора Менеджеров Локального Доступа (Local Access Managers - LAM). Каталог ресурсов содержит актуальную информацию о всех службах, известных ядру DOL. Эта информация включает в себя физические адреса, протоколы связи, регистрационную информацию и информацию о методах передачи данных. Ядро DOL обеспечивает выполнение DOL-программ путем взаимодействия с различными службами. Ядро выполняет активизацию задач, синхронизацию задач, условное выполнение и обмен данными между LAM, а также управление фиксацией локальных и глобальных задач. Оно также отвечает за открытие и закрытие соединений с участвующими в работе LAM, устанавливая между ними каналы связи, посылая им их локальные команды и осуществляя наблюдение за состоянием выполнения. LAM работает как представитель пользователя в обрабатывающем объекте, которым он управляет, и обеспечивает абстракцию выполняемой им службы. LAM поддерживает автономность обрабатывающих объектов. Ядро DOL взаимодействует с LAM, который несет ответственность за выполнение затребованных локальных команд.

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

Проект Carnot, выполняемый в MCC, двигается дальше в развитии поддержки распределенных служб и приложений, включая ослабленные транзакции и потоки работ [55, 52]. В основном компоненте системы, называемом Расширяемым Переключателем Служб (Extensible Services Switch - ESS), используется язык Rosette, основанный на акторной модели. Rosette поддерживает интерпретируемое управление распределенными приложениями, высокую степень параллельности и сверхоблегченные процессы. Поскольку управление программами и сценариями является интерпретируемым, одна установка может переслать сценарий другой, чтобы повлиять на локальное управление распределенным приложением. Далее, ESS поддерживает множество абстракций распределенной обработки, в частности потоки байтов (ByteStreams) и пространства деревьев (TreeSpaces), для упрощения разработки и эффективной реализации управления потоками работ и ослабленными транзакциями. Существует прототип ESS, взаимодействующий с различными коммуникационными ресурсами (например TCP/IP, SNA, X.25), информационными ресурсами (например коммерческими реляционными и объектно-ориентированными СУБД) и службами приложений (например X.500, X.400).

Система управления распределенными объектами (Distributed Object Management System - DOMS) [27] является объектно-ориентированной средой, в которой автономные и неоднородные системы могут быть интегрированы посредством представления своих данных и функций как объектов. Клиентские приложения (задачи) могут получить доступ к этим объектам, не имея информации об их расположении, языке доступа или деталях представления данных систем более низкого уровня. Для обеспечения согласованности объектов при возникновении отказов или при параллельном выполнении в DOMS используются транзакции при доступе к объектам в системах, которые могут предоставлять или не предоставлять транзакционные возможности, и к объектам, поддерживаемым самой системой DOMS. Если система не обеспечивает необходимые операции, в DOMS используется собственный интерфейс с операциями управления транзакциями, поддерживаемыми менеджером транзакций системы.

6 Заключение

Иерархические структуры расширенных моделей транзакций, таких как вложенные транзакции [42] и многоуровневые транзакции [53], часто являются слишком негибкими для приложений потоков работ. Основной проблемой, возникающей при разработке системы управления потоками работ в рамках данной модели транзакций, является то, что предопределенный набор свойств, обеспечиваемых моделью, может требоваться, а может и не требоваться семантикой потока работ. Например, межзадачные зависимости, требуемые семантикой потока работ, могут быть более сложными, чем те, которые поддерживаются данной моделью транзакций, или предоставляемые гарантии корректности (такие, как глобальная сериализуемость) могут быть более строгими, чем это требуется.

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

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

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

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

Литература

  1. M.Ansari, L. Ness, M. Rusinkiewicz, and A. Sheth. Using Flexible Transactions to Support Multisystem Telecommunication Applications. In Proceedings of the 18th International Conference on Very Large Data Bases, August 1992.
  2. M. Ansari, M. Rusinkiewicz, L. Ness, and A. Sheth. Executing Multidatabase Transactions. In Proceedings of the 25th International Conference on System Sciences, Hawaii, January 1992.
  3. P. Attie, M. Singh, A. Sheth, and M. Rusinkiewicz. Specifying and Enforcing Intertask Dependencies. In Proceedings of the 19th VLDB Conference, 1993.
  4. Y. Breitbart, D. Georgakopoulos, M. Rusinkiewicz, and A. Silberschatz. On rigorous transaction scheduling. IEEE Transactions on Software Engineering, 17, September 1991.
  5. Y. Breitbart and A. Silberschatz. Multidatabase Update Issues. In Proceedings of the ACM SIGMOD International Conference on Management of Data, June 1988.
  6. E. Cameron, L. Ness, and A. Sheth. An Executor for Multidatabase Transactions which Achieves Maximal Parallelism. In Proceedings of the First International Workshop on Interoperability in Multidatabase Systems, April, 1991.
  7. S. Chakravarthy, S. Navathe, K. Karlapalem, and A. Tanaka. Meetings the Cooperative Problem Solving Challenge: A Database-Centered Approach. In Cooperating Knowledge Based Systems 1990, Ed. S.M.Deen, Springer-Verlag, 1990.
  8. Jiansan Chen, Omran A. Bukhres, and Ahmed K. Elmagarmid. IPL: A Multidatabase Transaction Specification Language. In. Proc. of the 13th International Conference on Distributed Computing Systems, Pittsburg, PA, May 1993.
  9. P. Chrysanthis and K. Ramamritham. ACTA : A Framework for Specifying and Reasoningabout Transaction Structure and Behavior. In Proceedings of ACM SIGMOD Conference on Management of Data, 1990.
  10. P. Chrysanthis and K. Ramamritham. A Formalism for Extended Transaction Model. In Proceedings of the 17th International Conference on VLDB, 1991.
  11. U. Dayal, M. Hsu, and R. Ladin. Organazing Long-Running Activities with Triggers and Transactions. In Proceedings of ACM SIGMOD Conference onManagement of Data, 1990.
  12. U. Dayal, M. Hsu, and R. Ladin. A Transactional Model for Long-Running Activities. In Proceedings of the 17th VLDB Conference, September 1991.
  13. E. Dyson. Workflow. In Forbes, November 1992, p. 192.
  14. A. Elmagarmid, editor. Transaction Models for Advanced Database Applications. Morgan-Kaufmann, February 1992.
  15. A. Elmagarmid, J. Chen, and O.Bukhres. Remote System Interfaces: An Approach to Overcome Heterogeneous Barriers and Retain Local Autonomy in the Integration of Heterogeneous Systems. the International Journal on Intelligent and Cooperative Information Systems, 1993.
  16. A.K. Elmagarmid, Y. Leu, W. Litwin, and M. Rusinkiewicz. A Multidatabase Transaction Model for Interbase. In Proceedings of the 16th International Conference on VLDB, 1990.
  17. A. Farrag and M. Orzu. Using Semantic Knowledge of Transactions to Increase Concurrency. ACM Transactions on Database Systems, 14(4):503-525, December 1989.
  18. H. Garcia-Molina, D. Gawlick, J. Klein, K. Kleissner, and K. Salem. Coordinating Multi-transaction Activities. Technical Report CS-TR-247-90, Princenton University, February 1990.
  19. H. Garcia-Molina and K. Salem. SAGAS. In Proceedings of the ACM SIGMOD Conference on Management of Data, 1987.
  20. H. Garcia-Molina, K. Salem, D. Gawlick, J. Klein, and K. Kleissner. Modeling Long-Running Activities as Nested Sagas. Data Engineering Bulletin, 14(1), March 1991.
  21. D. Georgakopoulos. Multidatabase Recoverability and Recovery. In Proceedings of First International Workshop on Interoperability in Multidatabase Systems, April 1991.
  22. D. Georgakopoulos, M. Hornick, and P. Krychniak. An Environment for Specification and Management of Extended Transactions in DOMS. Technical Report September, GTE Laboratories Inc., 1992.
  23. D. Georgakopoulos, M. Rusinkiewicz, and W. Litwin. Chronological Scheduling of Transactions with Temporal Dependencies. Technical Report UH-CS-91-03, Dept. of Computer Science, University of Houston, February 1991.
  24. D. Georgakopoulos, M. Rusinkiewicz, and A. Sheth. Using Tasked-based Methods to Enforce the Serializability of Multidatabase Transactions. In IEEE Transactions on Knowledge and Data Engineering, 1993.
  25. J.N. Gray. The Transaction Concept: Virtues and Limitations. In Proceedings of the 7th International Conference on VLDB, September 1981.
  26. Y. Halabi, M. Ansari, R. Batra, W. Jin, G. Karabatis, P. Krychniak, M. Rusinkiewicz, and L. Suardi. Narada: An enviroment for specification and execution of multi-system applications. In Proceedings of the Second International Conference on System Integration, Morristown, New Jersey, June 1992.
  27. F. Manola, S. Heiler, D. Georgakopoulos, M. Hornick, and M. Brodie. Distributed object management. International Journal of Intelligent and Cooperative Information Systems, 1(1):5-42, March 1992.
  28. M. Rusinkiewicz et al. OMNIBASE: Design and Implementation of a Multidatabase System, IEEE CS Distributed Processing Newsletter, Volume 10, Number 2, 1988.
  29. Y. Halabi, M. Ansari, R. Batra, W. Jin, G. Karabatis, P. Krychniak, M. Rusinkiewicz, and L. Suardi. Narada: An Environment for Specification and Execution of Multi-System Applications. In Proceedings of the Second International Conference on Systems Integration, 1992.
  30. W. Win, L. Ness, M. Rusinkiewicz, A. Sheth. Concurrency Control and Recovery Multidatabase Work Flows in Telecommunication Applications. In Proceedings of the SIGMOD Conference, May 1993.
  31. W. Jin, N. Krishnakumar, L. Ness, M. Rusinkiewicz, and A. Sheth. Supporting Telecommunications Applications with Multidatabase Transactions. Bellcore Technical Memorandum, September 1993.
  32. J. Klein. Advanced Rule Driven Transaction Management. In IEEE COMPCON, 1991.
  33. E. Kuehn, F. Puntigam, and A. Elmagarmid. Transaction Specification in Multidatabase System Based on Parallel Logic Programming. In Proceeding of the First International Workshop on Interoperability in Multidatabase Systems, April, 1991.
  34. H. F. Korth, E. Levy, and A. Silberschatz. A Formal Approach to Recovery by Compensating Transactions. In Proceedings of the 16th International Conference on VLDB, 1990.
  35. N. Krishnakumar, A. Sheth. Specifying Multi-system Workflow Applications in METEOR. Bellcore, Technical Memorandum, 1994.
  36. Andrzej Kzrywda. Concurrent execution of transactional workflows. Master"s thesis, University of Houston, May 1994.
  37. P. Krychniak, M. Rusinkiewicz, A. Sheth, and G. Thomas. Bounding the Effects of Compensation under Relaxed Multi-level Serializability. Technical Report UH-CS-92-06, Dept. of Computer Science, University of Houston, March 1992.
  38. L. Kalinichenko. A Declarative Framework for Capturing Dynamic Behavior in Heterogeneous Interoperable Information Resorce Environment. In Proceedings of the 3rd RIDE Intl. Workshop on Interoperability in Multidatabase Systems (IMS"93), April 1993.
  39. K. Lee, W. Mansfield, and A. Sheth. A Framework for Controlling Cooperative Agents. In IEEE Computer, July 1993.
  40. N Lynch. Multi-level Atomicity - a New Correctness Criterion for Database Concurrency Control. ACM Transactions on Database Systems, 8(4), December 1983.
  41. S. Mehrotra, R. Rastogi, Y. Breitbart, N. Korth, and A. Silberschatz. Ensuring Transaction Atomicity in Multidatabase Systems. In Proceedings of the 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1992.
  42. J.E.B. Moss. Nested Transactions: An Approach to Reliable Distributed Computing. PhD thesis, MIT Press, Cambridge, MA, 1985.
  43. C. Pu. Superdatabases for Composition of Heterogeneous Databases. In IEEE Proceedings of the 4th International Conference on VLDB, 1988.
  44. A. Reuter. ConTracts: A Means for Extending Control Beyond Transaction Boundaries. In Proceeding of the 3rd Intl. Workshop on High Performance Transaction Systems, September 1989.
  45. M. Rusinkiewicz, A. Elmagarmid, Y. Leu, and W. Litwin. Extending the Transaction Model to Capture more Meaning. SIGMOD Record, 19, 1990.
  46. M. Ruusinkiewicz, A. Cichocki and P. Krychniak. Towards a Model for Multidatabase Transactions. International Journal of Intelligent and Cooperative Information Systems, Vol. 1, No. 3, 1992.
  47. M. Rusinkiewicz, S. Osterman, A. Elmagarmid, and K. Loa. The Distributed Operational Language for Specifying Multisystem Applications. In Proceedings of the First International Conference on Systems Integration, 1990.
  48. K. Salem, H. Garcia-Molina, and R. Alonso. Altruistic Locking: A strategy for Coping with Long-lived Transactions. Technical Report CS-TR-087-87, Dept. of Computer Science, Princenton University, April 1987.
  49. A. Sheth and L. Kalinichenko. Information Modeling in Multidatabase Systems: Beyond Data Modeling. In Proceedings of the 1st International Conference on Information and Knowledge Management, November 1992.
  50. A. Sheth, M. Rusinkiewicz, and G. Karabatis. Using Polytransactions to Manage Interdependent Data. In [14].
  51. R. Soley. A Common Architecture for Integrating Distributed Applications. In Proceeding of the Second International Conference on Parallel and Distributed Information Systems, January 1993.
  52. C. Tomlinson, P. Attie, P. Cannata, G. Meridith, A. Sheth, M. Singh, D. Woelk. Workflow Support in Carnot. In Data Engineering Bulletin, June 1993.
  53. G. Weikum. Principles and Realization Strategies of Multilevel Transaction Management. ACM TODS, 16(1), March 1991.
  54. G. Weikum and H.-J. Schek. Concepts and Applications of Multilevel Transactions and Open Nested Transactions. In [14].
  55. D. Woelk, P. Attie, P. Cannata, G. Meridith, A. Sheth, M. Singh, and C. Tomlinson. Task Scheduling using Intertask Dependencies in Carnot. In Proceedings of the SIGMOD Conference, May 1993.
  56. A. Wolski and J. Veijalainen. 2PC Agent method: Achieving serializability in presence of failures in a heterogeneous multidatabase. In Proceedings of PARBASE-90 Conference, February 1990.
  57. E.M. Clarke, E.A. Emerson, and A.P. Sista. Automatic Verification of Finite-State Concurrent Systems Using Temporal Logic Specifications. ACM Transactions On Programming Languages and Systems, Vol. 8, No. 2, April 1986.


*)Окончание. Начало см. СУБД, #2
**)Это работа частично поддерживалась Texas Advanced Research Program, грант # 3652008