Методы управления ресурсами многопроцессорных систем при обработке пакетов независимых задач без прерываний

Алгоритм LPT

Рассмотрим систему, содержащую n идентичных процессоров, на которой необходимо решить без прерываний набор из L независимых задач с временами решения ti,i=1,…,L . Получение расписания с минимальным временем решения и в этом случае является NP-трудной задачей. Один из наиболее эффективных и нетрудоемких алгоритмов организации вычислений в этом случае – алгоритм LPT (longest-processing task first) - самая длинная задача решается первой), являющийся частным случаем алгоритма критического пути для независимых задач. Суть этого алгоритма заключается в назначении задач в порядке убывания времени решения на освобождающиеся процессоры. Сотрудником фирмы BellLaboratories США, Грэхемом в 1967г. был получен следующий результат:

Теорема.

При использовании алгоритма LPT для распределения любого

пакета П={Zi} независимых задач без прерываний в системе с n

i=1

идентичными процессорами справедливо: T £ (4/3-1/3n)*T0,

где Т- время решения пакета П при распределении задач алгоритмом LPT,

T0- длина соответствующего оптимального расписания .

Очевидно, что

T₀≥

Приведенная оценка является наилучшей.

Контрольные вопросы

1. Какую задачу позволяют решить рассмотренные алгоритмы?

1.1 Задачу управления ресурсами многопроцессорных систем при обработке пакетов задач как с прерываниями, так и без.

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

1.3 Задачу управления ресурсами многопроцессорных систем при обработке пакетов задач без прерываний.

2. Требуется ли предварительная обработка заданий перед передачей пакета на выполнение?

2.1 Требуется при реализации обоих алгоритмов.

2.2 Нужна только в алгоритме Макнотона.

2.3 Такой необходимости нет.

3. В чем заключается алгоритм Макнотона?

3.1 Упорядочение задач по убыванию времени решения и назначении задач последовательно на процессоры справа налево от уровня q.

3.2 Упорядочение задач по возрастанию времени решения и назначении задач последовательно на процессоры справа налево от уровня q.

3.3 Упорядочение задач по убыванию времени решения и назначении задач последовательно на процессоры слева направо от уровня q.

4. Как вычисляется оптимальное время q решения задач

4.1 q = max{max t_i , }

4.2 q = max t_i

4.3 q = min{max t_i , }

5. В чем главный недостаток прерывания решения задачи?

5.1 С каждым актом прерывания связаны потери машинного времени на загрузку/выгрузку задач из ОП.

5.2 Алгоритмы решения получаются полиномиальнотрудными.

5.3 При совершении прерывания могут произойти потери данных.

6. Как расшифровывается название алгоритма LPT?

6.1 Задачи выполняются в порядке убывания времени.

6.2 Самая первая задача выполняется дольше других.

6.3 Самая длинная задача ставится на 1 место в очереди на выполнение.

7. В чем суть алгоритма LPT?

7.1 Назначение задач в порядке убывания времени на освобождающиеся процессоры.

7.2 Назначение задач в порядке неубывания времени на освобождающиеся процессоры.

7.3 Назначение задач в том виде, в каком они поступили в систему на освобождающиеся процессоры.

8. Как рассчитывается длина оптимального расписания в алгоритме LPT?

8.1 T₀=

8.2 T₀£ max{max t_i , }

8.3 T₀= 1/n * min {t_i}

9. В чем основное достоинство обработки пакетов независимых задач без прерывания?

9.1 Не тратится время на загрузку/выгрузку прерванных задач из ОП.

9.2 Алгоритмы ,решающие данные задачи просты в реализации.

9.3 Простой процессоров при использовании данного метода минимален.

10. Чем алгоритм Макнотона отличается от алгоритма LPT по определению?

10.1 Обработка пакетов задач в одном случае производится с прерыванием, в другом случае без.

10.2 В одном из алгоритмов не требуется предварительной обработки задач перед загрузкой пакета на выполнение.

10.3 Алгоритмы отличаются способом расчета длины оптимального расписания.