Рассмотрим систему с п идентичными процессорами, с помощью которой необходимо решить Ь независимых задач; каждая задача решается одним процессором в течение времени ?,, і = 1 ,…, Ь. Требуется найти алгоритм, который для каждого данного пакета (набора) задач строил бы расписание решения задач на процессорах системы, обеспечивающее минимально возможное время решения. При этом достигается максимально возможная производительность системы. Например, в двухпроцессорной системе и при наборе задач с временем их решения 3; 3; 2; 2; 2 возможны различные варианты назначения задач на решение. Приведем некоторые из них (рис. 4.19).

Рис. 4.19. Варианты расписаний для двухпроцессорной системы: а - работает один процессор: о работают два процессора; в - используется алгоритм Макнотона Очевидно, что наилучший в смысле минимизации общего времени решения задач вариант в, для которого время Т решения пакета задач совпадает с соответствующим оптимальным значением '/’= То = 0 и в данном случае равно величине 0 = max {max //,

(і/«) вд Величина 0 является нижней границей для оптимального значения 7о. Действительно, длина Тлюбого расписания не может быть меньше ни max t\ - максимального из времен решения задач пакета, ни величины (1/и Ltj), определяющей длину расписания в том случае, когда до момента завершения решения последней из задач пакета ни один процессор не простаивает, т.е. все процессоры имеют 100 %-ную загруженность.

В общем случае даже при и = 2 задача поиска оптимального значения Т при условии решения задач является NP-трудной, т.е. все известные алгоритмы ее решения имеют трудоемкость, экспо -ненциально зависящую от L. Однако если допустить возможность прерывания решения задач пакета до завершения их обслуживания, то могут быть предложены полиномиально-трудоемкие алгоритмы, приводящие к расписанию оптимальной длины 7о- При этом считается, что после прерывания решение задачи может быть возобновлено с точки прерывания на любом процессоре, не обязательно на том, на котором задача решалась.первоначально. Число прерываний должно быть по возможности меньшим, так как с каждым актом прерывания связаны потери машинного времени на загрузку-выгрузку задач из оперативной памяти.

Рассмотрим предложенный Макнотоном в 1959 г. алгоритм построения оптимального по длине расписания с не более чем п-\ прерываниями.

Алгоритм Макнотона заключается в предварительном упорядочении задач по убыванию времени решения и назначении задач последовательно по порядку номеров одну за другой на процессоры системы справа налево от уровня 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. Оптимальное расписание Для доказательства этого построим такой пример пакета задач, для которого алгоритм Макнотона дает расписание с числом прерываний п~ 1.

Пусть: Ь = п + 1и^= п, I - \, п + 1.

Тогда: 8 = тах {п ,\/п (п + \)п} = п + 1, а расписание, получаемое в соответствии с алгоритмом Макнотона, имеет вид, показанный на рис. 4.21.

Рис. 4.21. Расписание для «-процессорной системы по Макнотону

Число прерываний в этом случае, как видно, равно л-1,что и требовалось показать. Покажем теперь, что любое оптимальное расписание для этого пакета задач также имеет не менее п-\ прерываний. Очевидно, что в любом оптимальном расписании ни один процессор не простаивает на интервале [0, п + 1 ]. Предположим, что существует некоторое оптимальное расписание с числом прерываний, меньшим и-1. Тогда по крайней мере два процессора (для определенности возьмем Рк и Рі) обслуживают заявки без прерываний. Очевидно, эти процессоры обслуживают нейоторые задачи 2ц< и в интервале [0, п] без прерываний (если решение этих задач начинается позже момента времени ґ = 0, значит, до этого момента на этих процессорах решались некоторые другие задачи, решение которых прерывается в мо менты начала решения задач Z* и 2ц). Найдутся моменты времени t, /', такие, что n<t<t< п + 1, ив интервале [t, t'\ хотя бы один процессор простаивает, а потому рассматриваемое решение не может быть оптимальным.

Так как мы пришли к противоречию, делаем вывод о том, что предположение о числе прерываний, меньшем п-\, в оптимальном расписании ложно.

⇐Однопроцессорные системы оперативной обработки | Информационные системы и технологии в зкономике | Многопроцессорные системы при обработке пакетов независимых зада без прерываний⇒