|
частоты и периода. Теперь рассмотрим многоресурсную систему, в которой задачи с неравными временами выполнения связаны некоторыми отношениями предшествования и выполняются без учета приоритетов. В частности, рассматривается случай, в котором задачи как терминальные, так и нетерминальные требуют различного времени завершения. Пример графа, удовлетворяющего этим требованиям, показан на рисунке 2.1.12. На этом рисунке пара чисел вида A/В рядом с узлом обозначает задачу, чье время начала выполнения равно А и которая должна быть выполнена за В единиц времени после начала выполнения. Рисунок 2.1.12 Граф с многочисленными временными ограничениями Эвристическое решение этой задачи является разновидностью планов с наидлиннейшим путем, рассмотренных ранее. Однако в этом случае большое число наидлиннейших путей может быть определено для задач с пределами. Фактически процедура является вариацией разбиения по последнему предшествованию для случая с неравными временами задач и множественными пределами. Итак, в данном параграфе рассмотрены некоторые из наиболее важных моделей и алгоритмов формирования детерминированных наборов задач распределенных производственных процессов. Предполагалось, что графы задач являются ацикличными, без ответвлений и что времена выполнения задач точно известны. Тем не менее, следует упомянуть, что во многих случаях эти предположения могут нарушаться, однако, ранее систематически 70 |
временем начала выполнения второй задачи в некоторой точке плана. Определение этого интервала не включает первую итерацию обоих задач, где по определению начало выполнения второй задачи немедленно следует за завершением первой задачи. При тестировании данных методов, задачи разделялись на два класса. В 1-м классе частоты задач кратны более чем двум базовым частотам, а во 2м не более чем двум базовым частотам. Ни один из алгоритмов не показал: значительного превосходства над другими. Однако подход 2 исключительно хорошо показал себя на задачах первого класса. Подход 3 лучше решает некоторые задачи второго класса, а оба подхода 1 и 2 неплохо решают задачи, которые оказались трудными для подхода 3. В этом нет ничего необычного, так как число процессоров, необходимых для задач второго класса, было значительно меньше, чем для задач первого класса. Также были обнаружены некоторые интересные аномалии. Во многих случаях обнаружилось, что уменьшение частот задач или времен их выполнения может привести к увеличению количества требуемых процессоров. И наоборот, требуемое количество процессоров может быть уменьшено увеличением частот задач или времен выполнения, т.е., увеличивая загруженность процессора. 2.1.4.4. Учет пределов при формировании распределенных алгоритмов Ранее уже упоминался термин «планирование с учетом пределов» для среды, состоящей из одного процессора и набора периодичных задач известной частоты и периода. Теперь рассмотрим многопроцессорную систему, в которой задачи с неравными временами выполнения связаны некоторыми отношениями предшествования и выполняются без учета приоритетов. В частности, рассматривается случай, в котором задачи как терминальные, так и нетерминальные требуют различного времени 75 завершения. Пример графа, удовлетворяющего этим требованиям, показан на рис. 2.23. На этом рисунке пара чисел вида A/В рядом с узлом обозначает задачу, чье время начала выполнения равно А и которая должна быть выполнена за В единиц времени после начала выполнения. Рис. 2.23. Граф с многочисленными временными ограничениями Эвристическое решение этой задачи является разновидностью планов с наидлиннейшим путем, рассмотренных ранее. Однако в этом случае большое число наидлиннейших путей может быть определено для задач с пределами. Фактически процедура является вариацией разбиения по последнему предшествованию для случая с неравными временами задач и множественными пределами. Итак, в данном параграфе рассмотрены некоторые из наиболее важных моделей и алгоритмов формирования детерминированных наборов задач распределенных алгоритмов в информационно-управляющих системах (ИУС включают как подклассы, например, АСУ, КСУП и т.д.). Предполагалось, что графы задач являются ацикличными, без ответвлений и что времена выполнения задач точно известны. Тем не менее, следует упомянуть, что во многих компьютерных системах эти предположения могут нарушаться, однако, ранее систематически не рассматривались реализации циклов и ветвей в графах в рамках общей модели. Приведенные результаты показали, что эффективные оптимальные алгоритмы могут существовать только в некоторых частных случаях, и предполагают возможность активного исследования эвристических методов. 76 |