|
(задания и операции, в данном контексте, взаимозаменяемые термины), необходимо представить набор этих операций в виде их взаимосвязи друг с другом. Представление наборов заданий с использованием ориентированного графа или графа предшествования является наиболее популярным в литературе по планированию. Рисунок 2.1.1 изображает одно из возможных эквивалентных представлений для множества операций и заданий. Узлы в этом графе могут представлять независимые операции или части одной программы, которые связаны между собой во времени. По рисунку 2.1.1 можно сделать несколько важных выводов. Вопервых, множество вершин представляет набор операций Т = (ТЬ...,Т„). Направленные дуги между узлами означают, что существует частичное упорядочивание или отношение предшествования < между олперациями. Так если Tj < Tj, задача Т должна быть завершена до того, как Tj может начать выполнение. На рисунке 2.1.1, например, Ti < Т2, Ti < Т3, Т4 < Т7 и Т5 < Т7. Второе, что связанно с каждой вершиной это время, требуемое данному технологическому ресурсу на исполнение кода, представленного вершиной. Таким образом, мы говорим о функции М: Т —» (0, оо). Граф процесса может быть представлен тройкой (Т, М, <). Если ресурсы идентичны, то любая операция может выполняться на любом ресурсе, который удовлетворяет ее условиям предшествования. Рисунок 2.1.1 Представление набора операций процесса 36 |
необходимо представить набор этих задач в виде их взаимосвязи друг с другом. Представление наборов заданий с использованием ориентированного графа или графа предшествования является наиболее популярным в литературе по планированию (другие представления см. [2, 3], в разделе 2.2. используется матрица инциденций и матрица предшествования задач). Рис. 2.2.1 изображает одно из возможных эквивалентных представлений для множества задач и заданий. Узлы в этом графе могут представлять независимые операции или части одной программы (программного модуля), которые связаны между собой во времени. По рис. 2.2.1 можно сделать несколько важных выводов. Во-первых, множество вершин представляет набор задач Т = (ТЬ...,ТК). Направленные дуги между узлами означают, что существует частичное упорядочивание или отношение предшествования < между задачами. Так если Tj < Tj, задача Tj должна быть завершена до того, как Tj может начать выполнение. На рис. 2.2.1, например, Tj < Тг, Tj < Т3, Т4 < Т7 и Т5 < Т7. Второе, что связанно с каждой вершиной это время, требуемое гипотетическому процессору на исполнение кода, представленного вершиной. Таким образом, мы говорим о функции М: Т (0, ). Граф алгоритма может быть представлен тройкой (Т, М, <). Если процессоры идентичны, то любая задача может выполняться на любом процессоре, который удовлетворяет ее условиям предшествования. 42 |