|
Пк ресурсов со скоростью bk. С помощью оптимального приоритетного алгоритма планирования получено выражение минимума времени выполнения для такой структуры. В неприоритетных или простых планах ресурс, назначенный задаче, выделяется этой задаче, пока она не выполнится. Начальные результаты, обсужденные здесь, позволяют получать оптимальные неприоритетные двухресурсные планы для произвольного упорядочения задач, имеющих единичную продолжительность. Одним из подходов к решению данной проблемы, предлагаемым автором, является разбиение общего множества задач на пары совместимых и несовместимых задач. Говорят, что пара задач Т, и Tj является совместимой, если Т, 1-Tj и Tj Ф Tj. Пусть для множества из п задач т представляет максимальное число непересекающихся совместимых пар задач. Тогда п т нижняя граница по времени, необходимому для выполнения всех задач. Данный подход приводит к обнаружению максимального числа совместимых пар задач и затем к обнаружению оптимального упорядочения от задач этого множества к остальным задачам. Для данной постановки предлагается алгоритм генерации списка задач и показывается, что план, сгенерированный с использованием этого списка, не хуже любого плана, сформированного по любому другому списку. Алгоритм генерации 2-Б. Списочный план (или список, или список задач) L для графа G из п задач, обозначенный как L = (Ть Т2,..., Тп), представляет собой некоторую перестановку п задач. Считаем, что задача готова, если все из ее предшественников были выполнены. При использовании списка для создания плана бездействующий ресурс начинает обслуживать первую найденную в списке готовую задачу. Отсюда следует, что если список должен быть использован для создания оптимального плана, упорядочение задач в списке имеет первостепенное значение. Таким образом, 52 |
Ъ, если он в b раз быстрее стандартного процессора; Лью и Янг рассматривают мультипроцессорную систему, которая содержит п] процессоров со скоростью bi, П2 процессоров со скоростью ил* процессоров со скоростью &*. С помощью оптимального приоритетного алгоритма планирования получено выражение минимума времени выполнения для такой структуры. В неприоритетных или; простых планах процессор, назначенный задаче, выделяется этой задаче, пока она не выполнится. Начальные результаты, обсужденные здесь, позволяют получать оптимальные неприоритетные двухпроцессорные планы для произвольного-упорядочения задач, имеющих единичную продолжительность. Одним из подходов к решению данной проблемы, предлагаемым автором, является разбиение общего множества задач на пары совместимых и несовместимых задач. Говорят, что пара задач Т; и Tj является совместимой, если Ti * Tj и Tj Т,. Пусть для множества из л задач т представляет максимальное число непересекающихся совместимых пар задач.. Тогда л т нижняя граница по времени, необходимому для выполнения всех задач. Данный подход приводит к обнаружению максимального числа* совместимых пар задач и затем к обнаружению оптимального упорядочения от задач этого множества к остальным задачам; Для данной постановки предлагается алгоритм генерации списка задач и-показывается, что план, сгенерированный с использованием, этого списка, не хуже любого плана, сформированного по любому другому списку. Алгоритм генерации 2-Б. Списочный план (или список, или список задач) L для графа G из л задач, обозначенный как L = (Ть Т2,..., Тп), представляет собой некоторую перестановку л задач. Считаем, что задача готова, если все из ее предшественников были выполнены. При использованиисписка для создания плана бездействующий, процессор начинает обслуживать первую найденную в списке готовую задачу. Отсюда следует, что если список должен быть использован для создания 58 |