Конфигурационное управление. Курс в РТУ МИРЭА

5.1. Планирование задач

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

К системе сборки [44] могут быть предъявлены следующие требования:

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

К основным элементам системы сборки относятся:

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

Система сборки принимает на вход таблицу и план выполнения задач и возвращает таблицу в актуальном состоянии – для стартовой задачи и всех ее зависимостей выполнены необходимые действия.

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

Таблица может быть представлена одним из следующих основных способов:

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

План выполнения задач описывается на языке системы сборки. Такие языки можно отнести к классу конфигурационных языков.

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

• алгоритм топологической сортировки графа зависимостей задач;
• алгоритм на основе рестартов задач;
• алгоритм на основе приостановки задач;

Алгоритм на основе рестартов задач устроен следующим образом. Рассмотрим ситуацию, когда выполняется задача \(A\) и было установлено, что она имеет зависимую задачу \(B\), которая должна быть выполнена в первую очередь. В этом случае выполнение задачи \(A\) отменяется, выполняется задача \(B\), затем выполнение задачи \(A\) стартует повторно.

Алгоритм на основе приостановки задач отличается тем, что не отменяет выполнение задачи \(A\) полностью, а лишь приостанавливает это выполнение. После завершения задачи \(B\) система сборки возвращается к приостановленной ранее задаче \(A\) и продолжает ее выполнение.

Также системы сборки различаются по типу зависимостей:

• статические зависимости;
• динамические зависимости.

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

В системе сборки может применяться техника раннего среза (early cutoff) – если задача выполнена, но ее результат не изменился с предыдущей сборки, то нет необходимости исполнять зависимые задачи, то есть процесс сборки можно завершить ранее. На практике такая ситуация определяется по хеш-значению файла, связанного с задачей. Например, если в файл main.c был добавлен новый комментарий, сборка может быть остановлена после определения отсутствия изменений в хеш-значении объектного файла – main.o.

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

На рис. 33 приведен пример сценария работы с облачной системой сборки. Пользователь совершает следующие действия:

1. Загружает исходные тексты, их хеш-значения 1, 2 и 3.
2. Затем пользователь запрашивает сборку main.exe. Система сборки определяет с помощью изучения истории предыдущих сборок, что кто-то уже скомпилировал ранее эти исходные тексты для main.exe. Результаты их сборки хранятся в облаке с хешами 4 (util.o) и 5 (main.o). Система сборки далее определяет, что для зависимостей с такими хешами есть готовый main.exe с хешем 6. По ключу 6 из облачного хранилища извлекается конечный результат;
3. Далее пользователь изменяет util.c, и его хеш становится равен 7. В облаке комбинации хешей (7, 2) не существует, то есть ранее никто еще не компилировал такой вариант исходного кода. Процесс продолжается до получения нового main.exe, после чего новые варианты файлов и их хеш-значения сохраняются в облаке.

5.1.1. Топологическая сортировка

Топологическая сортировка является популярным алгоритмом планировщика в системах сборки.

Рассмотрим пример, показанный на рис. 34. Здесь целевой задачей является «экипировка», для достижения которой необходимо выполнить подзадачи в корректном порядке. Таким порядком может быть следующий:

1 3 2 5 7 4 6 8

Легко заметить, что это не единственный корректный порядок. Следующий вариант тоже имеет право на существование:

1 3 4 2 6 5 7 8

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

Простой алгоритм топологической сортировки состоит из следующих шагов:

1. Найти узлы графа без входных зависимостей и добавить их к списку результатов.
2. Удалить ранее найденные узлы. Если узлов в графе не осталось, то возвратить результат. В противном случае перейти к п.1.

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

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