|
2. В порядке уменьшения критерия загрузки. Критерий загрузки задачи 7„ обозначаемый Ц, определяется следующим образом: Ц = E/Tj. 3. Сохранение минимальной длины критического интервала. Критический интервал между двумя задачами определяется как минимальный интервал между временем завершения первой задачи и временем начала выполнения второй задачи в некоторой точке плана. Определение этого интервала не включает первую итерацию обоих задач, где по определению начало выполнения второй задачи немедленно следует за завершением первой задачи. При тестировании данных методов, задачи разделялись на два класса. В 1-м классе частоты задач кратны более чем двум базовым частотам, а во 2м не более чем двум базовым частотам. Ни один из алгоритмов не показал значительного превосходства над другими. Однако подход 2 исключительно хорошо показал себя на задачах первого класса. Подход 3 лучше решает некоторые задачи второго класса, а оба подхода 1 и 2 неплохо решают задачи, которые оказались трудными для подхода 3. В этом нет ничего необычного, так как число ресурсов, необходимых для задач второго класса, было значительно меньше, чем для задач первого класса. Также были обнаружены некоторые интересные аномалии. Во многих случаях обнаружилось, что уменьшение частот задач или времен их выполнения может привести к увеличению количества требуемых ресурсов. И наоборот, требуемое количество ресурсов может быть уменьшено увеличением частот задач или времен выполнения, т. е., увеличивая загруженность ресурса. 2.1.4.4. Учет пределов Ранее уже упоминался термин «планирование с учетом пределов» для среды, состоящей из одного ресурса и набора периодичных задач известной 69 |
принудительное время простоя получается, когда Jj объединяется с //.) В процессе объединения остальных задач плана нет необходимости в рассмотрении размещения задач в интервале принудительного простоя. Вместо этого для этой среды план с минимальным числом процессоров формируется в соответствии со следующим алгоритмом: 1) Пусть J/*, J2*,... подмножество задач, назначенных процессорам Pi, Сначала Ji*=J2*=...=0, а 11=12=...= . Всякий раз, когда задача Jj назначается пустой /}*, J = Tj Ej', 2) Чтобы определить Jh необходимо найти наименьшее / такое, что£г. < /,. и назначить Jt к Jj*. Оптимальный план для набора задач из табл. 4 показан на рис. 2.22. Этот результат обобщается для случая, когда / = k(f+!), к положительное целое число больше 1. 2.1.4.3. Периодичные задачи с независимым распределением частоты В этом параграфе рассматривается случай, когда устранена частотная связь между задачами, принятая ранее. Как можно было бы ожидать, в таком виде задача становится более сложной, а оптимальное решение не может быть найдено. Однако были разработаны эвристические подходы и проведено их относительное сравнение с применением моделирования. Эти подходы можно разделить на три группы. 1.В порядке уменьшения частоты. Задачи располагаются в порядке уменьшения частоты и их назначение также должно проходить в этом порядке. 2. В порядке уменьшения критерия загрузки. Критерий загрузки задачи Jh обозначаемый Д-, определяется следующим образом: Ц = Е/Г;. 3. Сохранение минимальной длины критического интервала. Критический интервал между двумя задачами определяется как минимальный интервал между временем завершения первой задачи и 74 временем начала выполнения второй задачи в некоторой точке плана. Определение этого интервала не включает первую итерацию обоих задач, где по определению начало выполнения второй задачи немедленно следует за завершением первой задачи. При тестировании данных методов, задачи разделялись на два класса. В 1-м классе частоты задач кратны более чем двум базовым частотам, а во 2м не более чем двум базовым частотам. Ни один из алгоритмов не показал: значительного превосходства над другими. Однако подход 2 исключительно хорошо показал себя на задачах первого класса. Подход 3 лучше решает некоторые задачи второго класса, а оба подхода 1 и 2 неплохо решают задачи, которые оказались трудными для подхода 3. В этом нет ничего необычного, так как число процессоров, необходимых для задач второго класса, было значительно меньше, чем для задач первого класса. Также были обнаружены некоторые интересные аномалии. Во многих случаях обнаружилось, что уменьшение частот задач или времен их выполнения может привести к увеличению количества требуемых процессоров. И наоборот, требуемое количество процессоров может быть уменьшено увеличением частот задач или времен выполнения, т.е., увеличивая загруженность процессора. 2.1.4.4. Учет пределов при формировании распределенных алгоритмов Ранее уже упоминался термин «планирование с учетом пределов» для среды, состоящей из одного процессора и набора периодичных задач известной частоты и периода. Теперь рассмотрим многопроцессорную систему, в которой задачи с неравными временами выполнения связаны некоторыми отношениями предшествования и выполняются без учета приоритетов. В частности, рассматривается случай, в котором задачи как терминальные, так и нетерминальные требуют различного времени 75 |