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

marek@cs.uh.edu

А. Цикоцки

andrzej@cs.uh.edu

Department of computer Science University of Houston Houston, TX 77204-3475
1. Что такое поток работ?
2. Работы, относящиеся к этой тематике
3. Спецификация потока работ

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

1. Что такое поток работ?

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

Выполнение множества задач с привлечением различных обрабатывающих объектов может контролироваться человеком или программной системой, называемой системой управления потоком работ. Рассмотрим, например, заказ на покупку в автоматизированном офисе [18]. Прежде чем заказ будет окончательно оформлен, он должен быть обработан и утвержден различными сотрудниками. Поэтому основные задачи в этом - проверка и заполнение различных частей заказа; эти задачи выполняются вручную или с помощью прикладных программ. Поскольку данные для обработки заказа могут храниться в различных базах данных, возможно понадобится выполнение дополнительных вспомогательных задач, производящих доступ к этим базам данных. Система управления потоком работ должна контролировать выполнение задач и осуществлять пересылку заказа между различными обрабатывающими объектами в соответствии со спецификацией потока работ.

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

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

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

2. Работы, относящиеся к этой тематике

В этом разделе мы кратко обсудим эволюцию моделей транзакции. Модели транзакции, рассматриваемые здесь, могут быть классифицированы на основании различных свойств, включающих структуру транзакции, параллельность внутри транзакции, зависимости выполнения, правила видимости, продолжительность, нарушение свойств атомарности и критерии корректности параллельного выполнения. В последующем обсуждении мы используем термин традиционные транзакции для обозначения вида транзакций, обладающих свойствами атомарности, согласованности, изолированности и долговременности (классические свойства atomicity, consistency, isolation, durability - ACID). Расширенные транзакции допускают группирование операций этих транзакций в иерархические структуры. Термин ослабленные транзакции означает, что данная модель транзакции ослабляет (некоторые) требования ACID. Вначале обсудим результаты имеющихся исследований в области расширенных и ослабленных моделей транзакций [14], а затем рассмотрим результаты, относящиеся к моделям потоков работ.

Расширенные и ослабленные модели транзакций

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

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

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

В большинстве моделей ослабленных транзакций используется некоторая форма компенсации. Подтранзакция может быть зафиксирована и может освободить ресурсы до того, как (глобальная) транзакция успешно завершится и будет зафиксирована. Если глобальная транзакция будет затем прервана, наличие у нее свойства атомарности при сбоях может потребовать устранения эффектов уже зафиксированных подтранзакций путем выполнения компенсирующих подтранзакций. Компенсирующая подтранзакция t- откатывает результаты зафиксированной подтранзакции t на семантическом уровне таким образом, что состояния базы данных до и после выполнения последовательности t t- совпадают. При этом, однако, может возникнуть несогласованность, если другая транзакция s использует результаты подтранзакции, которая будет компенсирована позже [19,34]. В открытых вложенных транзакциях для решения этой проблемы используется коммутативность. Поскольку доступ к результатам уже зафиксированных подтранзакций имеют только коммутирующие с ними подтранзакции, выполнение последовательности t s t- t- эквивалентно выполнению s t t-, что в соответствии с определением компенсации, эквивалентно выполнению s и, таким образом, не приводит к возникновению несогласованности. Другое решение, горизонт компенсации, в контексте многоуровневых действий, было предложено в [37]. В рамках этой модели операция-потомок может быть компенсирована только до фиксации операции-родителя. После того, как будет зафиксирована операция-родитель, единственный способ откатить результаты операции-потомка - компенсировать операцию-родитель целиком.

Концепция саги была введена в работе [19] для продолжительных транзакций. Сага состоит из набора ACID-подтранзакций T1,..., Tn с предопределенным порядком выполнения и из набора компенсирующих подтранзакций CT1,..., CTn-1 соответствующих T1,..., Tn-1. Сага завершается успешно, если фиксируются подтранзакции T1,..., Tn. Если одна из подтранзакций, скажем Tk, оказывается неуспешной, то зафиксированные подтранзакции T1,..., Tk-1 откатываются посредством выполнения компенсирующих подтранзакций CTk-1,..., CT1. Сага ослабляет требование полной изолированности и увеличивает степень параллельности внутри транзакции. Расширение этой модели, позволяющее строить вложенные саги, предложено в работе [20].

Гибкие транзакции [45, 16] были предложены в качестве модели транзакции, подходящей для среды мультибазы данных. Гибкая транзакция - это набор задач со множеством функционально эквивалентных подтранзакций для каждой из них и со множеством зависимостей выполнения этих подтранзакций, включающим зависимости по сбоям, зависимости успешных выполнений и внешние зависимости. Для ослабления требования изолированности в гибких транзакциях используется компенсация и ослабляется требование глобальной атомарности, что позволяет проектировщику транзакции указывать допустимые состояния завершения гибкой транзакции, в которых некоторые подтранзакции могут быть прерваны. IPL [8] - язык, предложенный для построения гибких транзакций с определяемыми пользователем атомарностью и изолированностью. Он содержит возможности традиционных языков программирования, такие как определение типов для поддержки специальных форматов данных, которые принимаются или производятся подтранзакциями, выполняющимися в различных программных системах, и описатели предпочтительности, которые основываются на использовании логических и алгебраических формул и служат для управления фиксацией транзакций.

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

Модели потока работ

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

Идею потока работ можно обнаружить в Языке Управления Заданиями (Job Control Language - JCL) пакетной операционной системы (такой, как OS фирмы IBM), который позволял пользователю определять задание как набор шагов. Каждый шаг содержал вызов программы, и шаги выполнялись последовательно. Некоторые шаги могли выполняться только при наличии определенных условий, например, если предыдущий шаг был удачным или наоборот. Эта простая идея постепенно была развита во многих продуктах и исследовательских прототипах, позволяющих структуризовать деятельность и предоставляющих управление параллельностью и фиксацией. Эти расширения позволяли проектировщику специфицировать потоки данных и управления между задачами и выборочно формировать характеристики транзакции для конкретной области деятельности, основываясь на ее семантике.

КонТракты (ConTracts) были предложены в работе [44] как механизм группирования транзакций в операции, состоящие из нескольких транзакций. КонТракт состоит из набора предопределенных действий (со свойствами ACID), называемых шагами и явно указанного плана выполнения, называемого сценарием. Выполнение КонТракта должно быть восстанавливаемым вперед (forward-recoverable), т.е. в случае сбоя состояние КонТракта должно быть сохранено, и его выполнение может быть продолжено. Кроме ослабленной изолированности, КонТракт обеспечивает ослабленную атомарность, так что выполнение КонТракта может быть прервано и возобновлено позднее.

Некоторые вопросы, связанные с потоками работ, были рассмотрены в работах по долговременным действиям (Long-Running Activities) [11,12]. Долговременное действие представляет собой набор выполняемых элементов, которые рекурсивно могут состоять из других действий или транзакций верхнего уровня (т.е. транзакций, которые могут порождать вложенные транзакции). Поток управления и поток данных действия могут быть определены статически в сценарии действия или динамически посредством правил событие-условие-действие (Event-Condition-Action - ECA). Эта модель содержит компенсацию, связь между выполняемыми элементами, опрос статуса действия и обработку исключений. Последнее предложение для среды программируемых транзакций также содержит несколько средств потоков работ, включая различные обрабатывающие объекты и различные требования координации и корректности [22].

Другими терминами, используемыми в литературе для обозначения потоков работ, являются поток задач (task flow), многосистемные приложения (multi-system applications) [1], множественные действия приложений (application multi-activities) [38], связанные приложения (networked applications) [13] и долговременные действия (long-running activities) [12]. Связанные с этим вопросы обсуждаются также в контексте кооперативных действий в работе [39] и в работе [7] в контексте кооперативного решения проблем.

3. Спецификация потока работ

При спецификации потока работ ключевыми являются вопросы:

  • Определение задачи: структура выполнения каждой задачи определяется указанием множества состояний, которые могут быть наблюдаемы извне, и множества переходов между этими состояниями. Кроме того, могут быть определены те характеристики обрабатывающих объектов, которые могут влиять на требования к выполнению задач.
  • Требования координации задач: требования координации задач обычно выражаются через межзадачные зависимости выполнения и зависимости потоков данных.
  • Требования к выполнению (требования корректности): требования к выполнению определяются для ограничения выполнения потока(ов) работ таким образом, чтобы удовлетворялись критерии корректности, зависящие от приложения. Они включают требования атомарности при сбоях (failure-atomicity), требования атомарности-выполнения (execution-atomicity) (включая правила видимости, указывающие, когда результаты зафиксированной задачи становятся видимыми для других параллельно выполняющихся потоков работ), а также требования к управлению синхронным выполнением потоков работ и требования восстановления.

Эти вопросы будут обсуждаться в следующих подразделах.

3.1. Определение задачи в потоке работ

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

Следовательно, структура задачи может быть определена заданием:

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

Picture 1

Рисунок 1.
Примеры диаграмм смены состояни задачи.

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

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

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

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

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

3.2. Требования координации задач

Как только будет определена принадлежность задачи потоку работ, внутренняя структура потока работ (поток управления) может быть определена путем спецификации требований координации задач. Обычно эти требования формулируются путем определения предусловий планирования для каждой из управляемых планировщиком смены состояний задачи. В общем случае эти зависимости могут быть определены статически перед началом выполнения потока работ, либо динамически, в процессе его выполнения. Примеры подходов, использующих статическое определение зависимостей, включают гибкие транзакции [16, 1], КонТракты [44], мультитранзакции [18], транзакции над мультибазами данных [46]. Динамически определяемые зависимости создаются в процессе выполнения потока работ, часто путем выполнения набора правил. События и условия, влияющие на обработку правил, могут меняться с изменением среды выполнения и/или ранее выполняющихся задач. Примеры такого подхода включают долговременные действия [12] и политранзакции [50].

Предусловия планирования для задачи могут быть определены через зависимости, включающие:

  • Состояния выполнения других задач. Например, "задача t1 не может стартовать, пока задача t2 не завершится", или "задача t1 должна быть прервана, если задача t1 будет зафиксирована".
  • Выходные значения других задач. Например, "задача t1 может стартовать, если задача t2 возвращает значение больше, чем 25".
  • Внешние переменные, которые изменяются внешними событиями, не являющимися частью потока работ (но могут быть связаны с событиями в других задачах потока работ или другими потоками работ). Примерами таких условий являются: "задача t1 не может стартовать ранее 9 часов" или "задача t1 должна стартовать через 24 часа после завершения задачи t2".

Термины зависимости выполнения, зависимости данных или значений, зависимости от времени используются в литературе для обозначения различных предусловий планирования. Эти зависимости могут быть скомбинированы при помощи обычных логических связок (ИЛИ, И, НЕ) для построения сложных условий планирования.

Picture 2

Рисунок 2.
Пример межзадачных зависимостей.

Обеспечение межзадачных зависимостей обсуждается в работе [3]. Задачи моделируются их состояниями вместе со значимыми событиями, соответствующими переходам между состояниями (старт, фиксация, откат и т.д.), которые могут быть форсированы, отвергнуты или задержаны. Межзадачные зависимости, такие как зависимости порядка e1 < e2 и зависимости существования e1 -> e2 между значимыми событиями задач, формально определяются с использованием Логики Деревьев Вычисления (Computation Tree Logic - CTL) и обладают соответствующими автоматами зависимостей, которые могут быть построены автоматически. Эти зависимости могут поддерживаться путем проверки нужных автоматов зависимостей. На рис. 2 приведен пример межзадачных зависимостей, где Задача2 должна стартовать после старта Задачи1, и Задача2 должна быть прервана, если Задача1 зафиксирована.

3.3. Требования атомарности по сбоям в потоке работ

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

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

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

3.4. Требования атомарности выполнения потока работ

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

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

3.5. Спецификация потоков работ

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

  • графические средства спецификации потоков работ и
  • языки спецификации потоков работ.

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

Практический метод спецификации потоков работ (графическое средство или язык) должен поддерживать:

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

Проектировщик потока работ может пожелать задать дополнительные свойства потока работ, например, критерии корректности выполнения задач.

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

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

Продолжение в следующем номере.

*) Эта работа частично поддерживалась грантом і3652008 Texas Advanced Research Program.

1) Мы говорим, что система является идемпотентной по отношению к задаче типа T, если эта задача может быть выполнена один или более раз без изменения результата. Примерами идемпотентных задач являются: "установить счетчик c в 0" или "выделить ресурс с номером x процессу с номером y" (но не "увеличить счетчик c" или "выделить экземпляр ресурса типа X процессу с номером y").