МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ ПРИ ОБРАБОТКЕ ПАКЕТОВ ЗАДАЧ С ПРЕРЫВАНИЯМИ
Рассмотрим систему с п идентичными процессорами, с помощью которой необходимо решить L независимых задач; каждая задача решается одним процессором в течение времени ?,, і = 1 ,..., L.
Требуется найти алгоритм, который для каждого данного пакета (набора) задач строил бы расписание решения задач на процессорах системы, обеспечивающее минимально возможное время решения. При этом достигается максимально возможная производительность системы. Например, в двухпроцессорной системе и при наборе задач с временем их решения 3; 3; 2; 2; 2 возможны различные варианты назначения задач на решение. Приведем некоторые из них (рис. 4.19).Рис. 4.19. Варианты расписаний для двухпроцессорной системы: и — работает один процессор: о работают два процессора; в — используется алгоритм Макнотона
Очевидно, что наилучший в смысле минимизации общего времени решения задач вариант в, для которого время Т решения пакета задач совпадает с соответствующим оптимальным значением '/’= То = 0 и в данном случае равно величине 0 = max {max //,
(i/я) вд
Величина 0 является нижней границей для оптимального значения 7о. Действительно, длина Тлюбого расписания не может быть меньше ни max t\ — максимального из времен решения задач пакета, ни величины (1/л Ltj), определяющей длину расписания в том случае, когда до момента завершения решения последней из задач пакета ни один процессор не простаивает, т.е. все процессоры имеют 100 %-ную загруженность.
В общем случае даже при и = 2 задача поиска оптимального значения Т при условии решения задач является NP-трудной, т.е.
все известные алгоритмы ее решения имеют трудоемкость, экспоненциально зависящую от L. Однако если допустить возможность прерывания решения задач пакета до завершения их обслуживания, то могут быть предложены полиномиально-трудоемкие алгоритмы, приводящие к расписанию оптимальной длины 7о- При этом считается, что после прерывания решение задачи может быть возобновлено с точки прерывания на любом процессоре, не обязательно на том, на котором задача решалась.первоначально. Число прерываний должно быть по возможности меньшим, так как с каждым актом прерывания связаны потери машинного времени на загрузку-выгрузку задач из оперативной памяти.Рассмотрим предложенный Макнотоном в 1959 г. алгоритм построения оптимального по длине расписания с не более чем п—1 прерываниями.
Алгоритм Макнотона заключается в предварительном упорядочении задач по убыванию времени решения и назначении задач последовательно по порядку номеров одну за другой на процессоры системы справа налево от уровня 0.
Примем: и = 2, L - 4, время решения задач: 5; 4; 3; 2. Тогда 0 = max {5, 1/2 • (5 + 4 + 3 + 2)} = 7; а расписание, полученное в соответствии с алгоритмом Макнотона, имеет вид, показанный на рис. 4.20.
В данном случае число прерываний равно единице.
Покажем, что и-1 (максимальное число прерываний для расписания, полученного в соответствии с алгоритмом Макнотона) является достижимой границей числа прерываний.
5 10 Г
Рис. 4.20. Оптимальное расписание
15
Для доказательства этого построим такой пример пакета задач, для которого алгоритм Макнотона дает расписание с числом прерываний л-1.
Пусть: L = п + 1иї,'= п, і - \, п + 1.
Тогда: 8 = max {п ,\/п (п + 1)л} = п + 1, а расписание, получаемое в соответствии с алгоритмом Макнотона, имеет вид, показанный на рис.
4.21.Рис. 4.21. Расписание для «-процессорной системы по Макнотону
Число прерываний в этом случае, как видно, равно л-1,что и требовалось показать. Покажем теперь, что любое оптимальное расписание для этого пакета задач также имеет не менее п-\ прерываний. Очевидно, что в любом оптимальном расписании ни один процессор не простаивает на интервале [0, п + 1 ]. Предположим, что существует некоторое оптимальное расписание с числом прерываний, меньшим л-1. Тогда по крайней мере два процессора (для определенности возьмем Рк и Pj) обслуживают заявки без прерываний. Очевидно, эти процессоры обслуживают нейоторые задачи Z/amp; и Zu в интервале [0, п] без прерываний (если решение этих задач начинается позже момента времени t = 0, значит, до этого момента на этих процессорах решались некоторые другие задачи, решение которых прерывается в моменты начала решения задач Z* и 2ц). Найдутся моменты времени t, /’, такие, что nlt;tlt;t'lt; п + 1, ив интервале [t, t'\ хотя бы один процессор простаивает, а потому рассматриваемое решение не может быть оптимальным.
Так как мы пришли к противоречию, делаем вывод о том, что предположение о числе прерываний, меньшем п-\ в оптимальном расписании ложно.
- МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ ПРИ ОБРАБОТКЕ ПАКЕТОВ НЕЗАВИСИМЫХ ЗАДАЧ БЕЗ ПРЕРЫВАНИЙ
Рассмотрим систему, содержащую п идентичных процессоров, , на которой необходимо решить без прерываний набор из L независимых задач с временами решения t,, i = 1,..., L. Получение расписания с минимальным временем решения и в этом случае является NP-трудной задачей. Один из наиболее эффективных и нетрудоемких алгоритмов организации таких вычислений—алгоритм LPT (Longest-Processing Task first — самая длинная задача решается первой), являющийся частным случаем алгоритма критического пути для независимых задач. Суть этого алгоритма заключается в назначении задач в порядке убывания времени решения на освобождающиеся процессоры. Сотрудником фирмы BellLaboratories, США, Грэхемом в 1967 г. был получен следующий результат: при использовании алгоритма LPT для распределения любого пакета П = {Z,} независимых задач без прерываний в системе с п идентичными процессорами справедливо:
где Т — время решения пакета П при распределении задач алгоритмом LPT;
Tq — длина оптимального расписания.
Приведенная оценка является наилучшей.
Очевидно, что