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

[0001] Компьютерно-реализуемый способ управления исполнением задач в компьютерной системе, включающий в себя этапы, на которых

[0002] Способ по п.1, в котором спецификация зависимости между задачами является спецификацией графического представления зависимости между задачами, при этом элементы "Задача" содержат вершины в графическом представлении, а элементы "Связь" содержат связи в графическом представлении.

[0003] Способ по п.1, в котором элемент "Ресурс" содержит временную шкалу с точками прикрепления, ассоциированными с точками на временной шкале.

[0004] Способ по п.1, в котором упомянутый ресурс включает в себя ресурс хранения.

[0005] Способ по п.1, в котором упомянутый ресурс включает в себя таблицу данных.

[0006] Компьютерная система, приспособленная для исполнения задач, включающая в себя

[0007] Система по п.6, в которой спецификация зависимости между задачами является спецификацией графического представления зависимости между задачами, при этом элементы "Задача" содержат вершины в графическом представлении, а элементы "Связь" содержат связи в графическом представлении.

[0008] Система по п.6, в которой элемент "Ресурс" содержит временную шкалу с точками прикрепления, ассоциированными с точками на временной шкале.

[0009] Система по п.6, в которой упомянутый ресурс включает в себя ресурс хранения.

[0010] Система по п.6, в которой упомянутый ресурс включает в себя таблицу данных.

Область техники, к которой относится изобретение

Настоящее изобретение касается управления исполнением задач.

Предшествующий уровень техники

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

Фиг. 1А иллюстрирует пример графа, представляющего зависимости между задачами, - "графа зависимостей". Вершины представляют задачи, а направленные связи - ограничения на зависимости. В этом примере зависимости между задачами появляются в результате доступа к общей структуре данных, в этом случае к таблице. Задача 102 инициализации таблицы 102 заключается в установлении размера таблицы и вводе в таблицу значений по умолчанию. Задача 104 загрузки таблицы состоит в записи набора записей данных в строки таблицы. Первая связь 106 определяет необходимость исполнения задачи 102 инициализации таблицы перед задачей 104 загрузки таблицы. Задача 108 разгрузки таблицы заключается в считывании записей данных, подлежащих использованию при последующих вычислениях, из строк таблицы. Вторая связь 110 определяет необходимость исполнения задачи 104 загрузки таблицы перед задачей 108 разгрузки таблицы. Направленность связи указывает на порядок исполнения. Подразумевается также зависимость, устанавливающая необходимость исполнения задачи 102 инициализации таблицы перед задачей 108 разгрузки таблицы.

В случае изменения задач, подлежащих исполнению в вычислительной системе (например, путем добавления или удаления задач), соответствующий граф зависимостей должен быть изменен. Как показано на фиг. 1В, граф 100 зависимостей трансформируется в граф 112, включающий в себя задачу 114 сортировки таблицы, размещенную между задачей 104 загрузки таблицы и задачей 108 разгрузки таблицы. Связь 110 между задачей 104 загрузки таблицы и задачей 108 разгрузки таблицы заменена на связь 116 между задачей 104 загрузки таблицы и задачей 114 сортировки таблицы и связь 118 между задачей 114 сортировки таблицы и задачей 108 разгрузки таблицы.

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

На фиг. 1С представлен граф 120 зависимостей, в котором исполнение первой группы 122 из трех задач, заключающихся в загрузке различных частей таблицы, должно полностью закончиться перед началом исполнения любой второй группы 124 из трех задач, заключающихся в выполнении операций (например, считывания, сортировки и т.д.) над частями таблицы. Этот пример иллюстрирует потенциальную сложность, которая может существовать в некоторых графах зависимостей. В графе с этим типом структуры количество связей между группами (9 в этом примере) увеличивается как произведение количества задач в первой группе (3 в этом примере) на количество задач во второй группе (3 в этом примере). Есть также связи к каждой из задач в первой группе 122 от задачи 126 инициализации таблицы и от каждой из задач во второй группе 124 к задаче 128 разгрузки таблицы.

Сущность изобретения

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

Этот аспект может включать в себя один или более следующих признаков:

в графическом представлении элементы "задача" включают в себя вершины, а элементы "связь" включают в себя связи;

элемент "ресурс" включает в себя временную шкалу с точками прикрепления, ассоциированными с точками на временной шкале;

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

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

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

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

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

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

Перечень фигур чертежей

Фиг. 1А - последовательный граф зависимостей.

Фиг. 1В - иллюстрация изменения графа зависимостей по фиг. 1А.

Фиг. 1С - непоследовательный граф зависимостей.

Фиг. 2А - граф зависимостей с элементом "ресурс".

Фиг. 2В - граф зависимостей с элементом "ресурс" типа временной шкалы.

Фиг. 3 - граф зависимостей с элементом "ресурс" типа временной шкалы и межзадачными связями зависимостей.

Фиг. 4 - граф зависимостей с элементом "ресурс" типа временной шкалы, имеющим направленные связи.

Описание

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

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

Например, граф 120 зависимостей, представленный на фиг. 1С, может быть изменен так, чтобы он включал в себя элемент "ресурс", представляющий таблицу, к которой задачи осуществляют доступ. Как показано на фиг. 2А, граф 200 зависимостей включает в себя элемент 202 "ресурс" типа таблицы, который представлен как другая вершина в этом графе наряду с вершинами "задача". Первая группа 122 из трех задач теперь связана с "входной" точкой 204 прикрепления элемента 202 "ресурс" типа таблицы, а вторая группа 124 из трех задач связана с "выходной" точкой 204 прикрепления элемента 202 "ресурс" типа таблицы. В графе с этим типом структуры количество связей между группами (6 в этом примере) увеличивается пропорционально количеству задач в каждой из этих двух групп (3 в этом примере). Это означает большое потенциальное уменьшение сложности с точки зрения количества связей.

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

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

Как показано на фиг. 2В, граф 220 зависимостей включает в себя элемент 222 "ресурс" типа временной шкалы. Задачи связаны с точками 223 ÷226 прикрепления на элементе 222 "ресурс" типа временной шкалы, и относительные позиции точек прикрепления на элементе 222 "ресурс" типа временной шкалы определяют ограничение на упорядочение для задач, связанных с элементом 222 "ресурс" типа временной шкалы. (Расстояние между любыми двумя точками 223 ÷226 прикрепления необязательно соответствует фактическому времени между исполнениями соответствующих задач.) Задачи, взаимодействующие с ресурсом, которые могут одновременно исполняться, связаны с одной и той же точкой прикрепления на временной шкале. Задачи исполняются во временной последовательности (слева направо в этом примере) согласно своим точкам прикрепления на временной шкале. В этом графе 220 относительная позиция точки 224 прикрепления для первой группы 122 задач и точки 225 прикрепления для второй группы задач определяют то же самое ограничение на упорядочение для групп задач, как и заданное в графах 120 и 200. Имеются также единичная связь с элементом 222 "ресурс" типа временной шкалы в точке 223 прикрепления от задачи 126 инициализации таблицы и единичная связь от элемента 222 "ресурс" типа временной шкалы в точке 226 прикрепления с задачей 128 разгрузки таблицы, которые определяют то же самое ограничение на упорядочение для этих задач, как и заданное в графах 120 и 200.

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

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

Как показано на фиг. 3, граф 300 зависимостей включает в себя элемент 302 "ресурс" типа временной шкалы с точками 304 ÷307 прикрепления. Связи к элементу "ресурс" типа временной шкалы определяют ограничение на упорядочение для взаимодействий с таблицей 301. Граф 300 также содержит "межзадачные" связи 322 и 324, определяющие дополнительные ограничения на упорядочение для взаимодействий между задачами, которые не подразумевают прямого взаимодействия с таблицей 301. Задача 308 составления части А заключается в генерации данных, подлежащих загрузке в таблицу 301. Следующая задача - задача 310 загрузки части А заключается в загрузке сгенерированных данных в таблицу 301. Так как задача 312 загрузки части В исполняется после задачи 310 загрузки части А (согласно правилу 2), а задача загрузки части А исполняется после задачи составления части А (согласно правилу 1), то также истинно, что задача 312 загрузки части В исполняется после задачи 308 составления части А.

Граф 300 зависимостей также определяет некоторые задачи, которые могут исполняться одновременно (или в неопределенном порядке). По окончании исполнения задачи 312 загрузки части В две задачи (например, выполняющиеся на отличном от задачи загрузки части В процессоре) могут осуществлять доступ к таблице 301 в любом порядке. Задача 314 копирования таблицы заключается в копировании всех данных в таблице 301 в точку, а задача 316 разгрузки части В - в выгрузке данных из таблицы 301 в промежуточную точку для осуществления доступа с помощью задачи 318 протокола передачи файлов (ftp). Задача 318 ftp имеет ограничение на упорядочение для исполнения (например, передачи данных из промежуточной точки) после задачи 316 разгрузки части В (вследствие правила 1), однако задача 318 ftp может выполняться до, после или одновременно с задачей 314 копирования таблицы. Кроме того, несмотря на то что правило 2 ограничивает задачу 320 удаления таблицы для исполнения по окончании исполнения задачи 314 копирования таблицы и задачи 316 разгрузки части В задача, задача 320 удаления таблицы может исполняться до, после или одновременно с задачей 318 ftp. Примеры упорядочения задач, определяемого графом 300, иллюстрируют возможность применения двух правил (правила 1 и правила 2) в комбинации для определения упорядочения среди задач в графе. Могут быть сформулированы и другие правила упорядочения для объединения элемента "ресурс" типа временной шкалы с другими графическими представлениями зависимости между задачами и выработки согласующихся ограничений на упорядочение.

Связи с элементом "ресурс" типа временной шкалы не должны быть направленными, однако направленность может быть использована для указания признаков или особенностей взаимодействий задачи и/или отношений, таких как отношения производства или потребления между задачей и ресурсом. Например, на фиг. 4 представлен граф 400 зависимостей, имеющий направленные связи, прикрепленные к элементу 402 "ресурс" типа временной шкалы (например, путем идентификации файла 401) в точках 403-406 прикрепления. Первая задача 408 связана с элементом 402 "ресурс" типа временной шкалы с помощью направленной связи, показывающей отношения производства (например, задача 408 заключается в записи данных в файл 401). Вторая задача 410 и третья задача 412 связаны с элементом 402 "ресурс" типа временной шкалы 402 с помощью направленных связей, показывающих отношения потребления (например, задачи 410 и 412 заключаются в считывании данных из файла 401). При этом четвертая задача 414 связана с отношениями производства.

В некоторых случаях направленность связей может обеспечить информацию, которая позволяет осуществлять переупорядочение задач без изменения зависимостей между задачами. В одном таком случае, если отношения производства являются отношениями, при которых задача может изменить состояние ресурса, а отношения потребления являются отношениями, при которых задача не изменяет состояние ресурса, то смежные задачи потребления могут быть подвергнуты переупорядочению. Например, в графе 400 зависимостей позиции второй задачи 410 и третьей задачи 412 (обе задачи потребления) могут быть подвергнуты перестановке без какого-либо влияния на результаты исполнения первой задачи 408 (или любых предыдущих задач) или четвертой задачи 414 (или любых последующих задач).

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

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

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