|
Заметим, что слияние двух задач, приведенное на рисунке 2.1.10, Ь, создает новую периодичную задачу с периодом tj (равным 2Ti) и временем выполнения е/ (равным Т + Е\}. Кроме того, имеются два промежутка с простоями: Ij периодичный простой с длительностью tj ei, и Д'2 принудительное время простоя длинной // £2 (обозначениеД'указывает, что принудительное время простоя получается, когда 7,объединяется с 7,-.) В процессе объединения остальных задач плана нет необходимости в рассмотрении размещения задач в интервале принудительного простоя. Вместо этого для этой среды план с минимальным числом ресурсов формируется в соответствии со следующим алгоритмом: 1) Пусть 7/*, подмножество задач, назначенных ресурсам Pi, Р2,--.Сначала Jj*=J2*=...=0, а 11=12=...=‘х>. Всякий раз, когда задача 7,назначается пустой 7Д /,• = Tj £/, 2) Чтобы определить 7/, необходимо найти наименьшее 1 такое, что < 7,и назначить J, к Jj*. Оптимальный план для набора задач из таблицы 2.1.1 показан на рисунке 2.1.11. Этот результат обобщается для случая, когда f = k(fj+i), к положительное целое число больше 1. 2.1.4.З. Периодичные задачи с независимым распределением частоты Здесь рассматривается случай, когда устранена частотная связь между задачами, принятая ранее. Как можно было бы ожидать, в таком виде задача становится более сложной, а оптимальное решение не может быть найдено. Однако были разработаны эвристические подходы и проведено их относительное сравнение с применением моделирования. Эти подходы можно разделить на три группы. 1. В порядке уменьшения частоты. Задачи располагаются в порядке уменьшения частоты и их назначение также должно проходить в этом порядке. 68 |
принудительное время простоя получается, когда 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 |