Рассмотрим систему, содержащую п идентичных процессоров, , на которой необходимо решить без прерываний набор из L независимых задач с временами решения t,, i = 1,…, L. Получение расписания с минимальным временем решения и в этом случае является NP-трудной задачей. Один из наиболее эффективных и нетрудоемких алгоритмов организации таких вычислений-алгоритм LPT (Longest-Processing Task first - самая длинная задача решается первой), являющийся частным случаем алгоритма критического пути для независимых задач. Суть этого алгоритма заключается в назначении задач в порядке убывания времени решения на освобождающиеся процессоры. Сотрудником фирмы BellLaboratories, США, Грэхемом в 1967 г. был получен следующий результат: при использовании алгоритма LPT для распределения любого пакета П = {Z,} независимых задач без прерываний в системе с п идентичными процессорами справедливо: где Т - время решения пакета П при распределении задач алгоритмом LPT;

Tq - длина оптимального расписания.

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

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

⇐Многопроцессорные системы при обработке пакетов зада с прерываниями | Информационные системы и технологии в зкономике | Производительность мультипроцессорных систем с общей и индивидуальной памятью⇒