Задача систем планирования и распределения ресурсов многопроцессорных управляющих вычислительных системах в контуре обработке информации

АННОТАЦИЯ

При исследовании многопроцессорных управляющих вычислительных систем (ВС) представляет практический интерес рассмотрения следующих двух задач:

- влияние способа распределения заявок между процессорами на их производительность;

- определения организации обслуживания, обеспечивающей минимум времени пребывания в очереди заявок внешнего потока. В большинстве практически существующих систем либо абоненту, либо обслуживающему прибору, либо как тому, так и другому приходится ждать. Все виды ожидания связаны с расходами, ухудшением качества системы. В этом случае задача заключается в регулярном появлении заявок на обслуживание, если это возможно, либо в определении организации систем планирования и распределения ресурсов ВС в контуре обработки информации, таким образом, чтобы свести к минимуму оба вида ожиданий и связанные с ним расходы.

ABSTRACT

In study of multiprocessor controlling VS presents the practical interest consideration of two problems:

- an influence of the way of the sharing the demands between processor on their capacity;

-a determination to organizations of the service, providing minimum of time of stay in queue of the demands of the external flow. In most practically existing systems or subscriber, or servicing instrument, or as that, so and the other happens to wait. All types of the waiting are connected with expenses and system quality deterioration. In this case problem is concluded in regular appearance of the applications for service if this possible, or in determination of the organizations planning system and distribution resource VS in sidebar information handling, to reduce to minimum both types of the waiting and connected expenses with him.

Ключевые слова: многопроцессорные управляющие ВС, организация систем планирования и распределения ресурсов ВС, обмен информацией, функциональный синтез, многофазные системы, внутренний поток, фазовой вектор, трехконтурная управляющая ВС

Keywords: multiprocessor controlling VS, organizing planning system and distribution resource VS, exchanging an information, functional syntheses, polyphaser systems, internal flow, phase vector, three-circuit control VS.      

Введение. Статья посвящена развитию известных и разработке аналитических методов исследования средств обмена информацией и задач систем планирования и распределения ресурсов в многопроцессорных управляющих ВС. Сложность анализа таких систем обусловлена сложностью протекающих в них процессов. Анализ показал, что возникающие при обмене типы процессов и связанные с ними задачи можно охарактеризовать следующим образом:

1. Процессы накопления и хранения информации требуют определения - необходимой ёмкости запоминающих устройств, моментов выборки накопленной информации для обработки и – очередности сообщений.

2. При наличии ряда обслуживающих приборов и путей выполнения различных заявок возникают процессы распределения потока заявок. Задача в таком случае заключается в распределении работ между ресурсами ВС и определении последовательности их исполнения таким образом, чтобы добиться максимальной эффективности системы.

Постановка задачи. Для решения перечисленных задач и исследования комбинированных процессов используются модели обмена информацией. Они позволяют на этапе функционального синтеза провести анализ и оценить необходимую производность процессов, время реализации типовой программы (работы), анализировать потоки в системе, сравнить варианты построения функциональных узлов и способы обмена информацией между ВС и абонентами, а также выявить возможные ошибки. Учитывая динамику и статику процессов обмена информацией, а также статические характеристики потоков на выходе контуров обработки информации в ряде случаев многофазные системы массового обслуживания (СМО) сведены к двум и даже однофазным, что значительно упрощает анализ организации обменов многоконтурных управляющих вычислительных систем (ВС) [1].

Знание основных принципов построения систем обмена информации (СОИ) [5], характеристик реальных и перспективных функциональных узлов, и потоков информации в управляющих ВС позволяет построить ряд частных моделей для обмена с учетом интересующих нас факторов, влияющих на эффективность всей системы. Исследование проводится начиная с организации обмена в простейших одноконтурных вычислительных комплексах и заканчивая анализом отдельных режимов работы трехконтурных управляющих ВС[4].

Решение задачи. Формальной моделью описанной выше ВС служит двух узловая двухфазная СМО (рис 1) [2]. у которой узел (процессорные устройство) содержит один обслуживающий прибор А и является первой фазой для внешнего потока заявок и второй – для внутреннего потока, генерируемого внешним запоминающим устройством узлом С. (при S = 1). Полагаем, что ширина полосы пропускания памяти больше или равна ширине полосы процессоров, а поэтому на выходе С всегда содержатся заявки внутреннего потока, требующие второй фазы обслуживания. На вход системы поступает внешний пуассоновский поток интенсивности λ.

Рисунок 1. Формальная модель двух узловой двухфазной СМО

Прибор А должен обслуживать заявки внутреннего потока и внешнего, обладающего относительным приоритетом. Следовательно, заявки внешнего потока не прерывают уже начатого обслуживания заявки внутреннего потока, а поступают в очередь r буферного накопителя (БН) и ждут окончания обслуживания. Если же в очереди r нет заявок, а в узле С всегда имеются заявки внутреннего потока (предположение о неограниченности программ), то прибор А по окончании обслуживания одной заявки из узла С немедленно приступает к обслуживанию другой и т. д. до прихода заявок внешнего потока.

Эта модель позволяет проводить анализ обмена между процессорами и абонентами лишь в том случае, если процессоры закреплены постоянно за определенными механизмами, технологическим оборудованием или системами и известно распределение потоков. В этом случае можно считать, что на вход обслуживающего прибора L (L = 1,2,…,S) поступает не вес поток интенсивностью L, а часть его  где и тогда полученные выше результаты могут быть полностью использованы для определения показателей качества комплекса .

При равномерном распределении потоков между процессорами вероятность p того что процессор занят обслуживанием заявок внутреннего потока, равна

Эту вероятность можно интерпретировать как степень загрузки процессора, используемого для обслуживания заявок внутреннего потока. Тогда средняя суммарная интенсивность обработки информации на втором этапе  вычислительной системой, содержащей S процессоров, равна:

.

Среднее время ожидания обслуживания заявки внешнего потока при относительных приоритетах равна:  и абсолютных приоритетах

Сделав допущение о том, что время обслуживания имеет экспоненциальное распределение с параметром μ для внешнего потока и μ₁ для внутреннего, рассматриваемая СМО может быть описана однородной Марковской цепью, для которой определим фазовой вектор.

Двухфазные СМО с двумя потоками в литературе мало освещены и изучены. Решение общей задачи с S приборами не представляет теоретической трудности, но сопряжено с громоздкими вычислениями.

Проведем исследование системы для двух дисциплин обслуживания: в первом случае внешнему потоку представляется абсолютный приоритет, во втором – относительный.

Для определения критериев обслуживания внешнего потока в первом случае достаточно рассмотреть хорошо изученную S – линейную СМО с одним пуассоновским потоком на входе, обшей очередью  [2] и экспоненциально распределенным обслуживанием с параметром . Для определения стационарных вероятностей  необходимо решить систему однородных линейных уравнений:

 с условием нормировки  

Для  вероятности состояния, при котором приборы свободны от обслуживания, будет

средняя длина очереди равна

а среднее число приборов S, занятых обслуживанием заявок внутреннего потока,

Если ширина полосы пропускания памяти больше, чем у процессора, т.е. степень загрузки системы заявками внутреннего потока больше или равна единице, то относительное снижение производительности (вычислительных операций) будет равно

h = r, т.к. .

В случае неодинаковых приборов (с различной интенсивностью обслуживания) m₁, …, m_s, но  получены аналитические выражения лишь для S = 2.

Положив, что m₁>m₂ и с вероятностью j заявка выбирает прибор 1, а вероятностью 1-j прибор 2, построим систему однородных линейных уравнений:

Обозначив r=l / (m₁+m₂ ), a = m₂ / m₁ , 0£a£1 , получим

где

Среднее число требований в системе равно

Кривые j(a) при фиксированных  приведены на рис.2 и позволяют исследовать влияние величин a и j на величину , которую принимаем за критерий эффективности системы. Графики (a) при фиксированных j=0; 0,5; 1, приведены на рис. 3.

Рисунок 2. Кривые j(a) при фиксированных .

Рисунок 3. Зависимость  от a при j = сonst.

Из них следует, что если процессоры имеют разную производительность, то среднее число заявок в системе уменьшается, когда они выбирают более быстродействующий процессор. Кривые (a) наглядно показывают, что если параметры процессоров отличаются мало друг от друга (a®1), то можно с хорошим приближением для анализа воспользоваться моделью, в которой все приборы имеет одинаковую интенсивность (ошибка не больше 20-25%).

 Рисунок 4. Средняя длительность ожидания

Рисунок 5. Вероятность не нулевого ожидания

На графиках среднего времени ожидания начала обслуживания (рис.4),

и вероятность обслуживания с ожиданием (рис.5), взяты из [5]

показано, что величина v и P{v> 0}уменьшается с увеличением S. Поэтому, если в качестве критерия эффективности системы выбирают v и P{v>0}, то предпочтительное, не изменяя интенсивности обслуживания, увеличивать число приборов.

При относительном приоритете, представляемом внешнему потоку, для исследования многопроцессорной управляющей ВС можно воспользоваться S- линейной СМО с двумя потоками и раздельными очередями, если емкость буферного накопителя между фазами С и А равна бесконечности, а полоса пропускания памяти не больше, чем у процессора. Анализ соответствующих СМО проведен в работе [5], где получены рекуррентные соотношения, связывающие стационарные вероятности состояний при ограничениях на число мест для ожидания. В работе [6] получены решения в замкнутом виде для системы, где интенсивность обслуживания обоих потоков одинакова. В этом случае среднее время ожидания начала обслуживания заявок внешнего потока равна

где  - вероятность того, что в очереди нет внешних заявок;

 -вероятность потери приоритетных заявок;

 -вероятность того, что система свободна от требований, 

Эти формулы позволяют исследовать зависимость качества обслуживания внешних заявок от параметров внутреннего потока m₁ и m.

При длине внешнего накопителя, равной единице (r = 1), среднее время пребывания заявок внутреннего потока в системе, т.е. среднее время выполнения арифметических операций, равно

Из данного выражения можно определить уже среднюю скорость вычислений и относительное снижение производительности

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

Исследование двухфазной СМО с ограниченной емкостью буфера между фазами позволяет выяснить влияние комплексных процессоров на блокировку системы [1] и ее производительность.

Это вопрос более подробно рассмотрим ниже. Сейчас же, воспользовавшись ранее полученными формулами для среднего числа приборов S, занятых обслуживанием заявок внутреннего потока, и среднего времени ожидания начала обслуживания внешних заявок при различных способах их распределения между приборами и различных дисциплинах обслуживания, построим графики S и v. Из этих графиков, приведенных на рис.5, можно сделать следующие выводы.

Рисунок 6. График зависимости  и v от загрузки системы

Организация системы с постоянным закреплением абонентов за процессорами при равномерном распределении потоков заявок между ними и организация с «плавающим» коммутатором с точки зрения обеспечения эффективного быстродействия (средние скорости вычислительных операций одинаковы) равнозначны.

Однако организация обмена с «плавающим» коммутатором обеспечивает задержки начала обслуживания заявок внешнего потока значительно меньшие, чем при постоянном закреплении за отдельными механизмами.

Это объясняется тем, что при работе ВС с закреплением очередей за отдельными процессорами возникают моменты, когда очередь к одному и даже к нескольким из них пуста и их мощность не используется для обслуживания заявок внешнего потока, в то время как у других процессоров могут образоваться большие очереди.

Организация «плавающего» коммутатора позволяет разгрузить эти процессоры, возложив часть работы по обслуживанию внешних потоков на свободные (от внешних потоков) процессоры, что приводит к сокращению среднего времени ожидания начала обслуживания, а значит и общего времени пребывания требований в системе.

Затраты на организацию «плавающего» коммутатора будут оправданы в том случае, если дополнительные затраты на увеличение производительности процессоров для решения указанных задач будут выше.

Заключение. В работе при анализе приоритетных методов обслуживания не учитывались затраты на его прерывание, поэтому степень загрузки r меньше действительной r_q (r<r_q). С учетом потерь на прерывание и анализа состояния системы показатели качества обслуживающий системы ухудшается: уменьшается производительность, увеличивается время пребывания в очереди и на обслуживании заявок и т.д. Задержки диспетчирования приводят к увеличению времени обслуживания каждой заявки и появлению «мертвых зон», во время которых не воспринимаются заявки от внешних абонентов, хотя в регистр приоритетов они по-прежнему поступают. Их можно учитывать различными способами. Часто с этой целью величину Dt_I (i=1,2,…,N), зависящую от конкретного метода диспетчирования, типа (или приоритета) потока заявок и вида его обработки.

Однако можно рассматривать СМО, на вход которой поступает дополнительный поток – поток диспетчерских заявок, имеющий регулярный характер и постоянное время обслуживания. Полученными результатами анализа можно воспользоваться для выяснения зависимости рассмотренных показателей эффективности системы от различных методов диспетчирования, которые влияют на параметры потока диспетчерских заявок.

Cписок литературы:
1. Бекмуратов Т.Ф., Мусаев М.У. Моделирование и исследование блокирующих состояний. Узбекский журнал Проблемы информатики и энергетики. №3-4 2015 г с.3-8.
2. Артамонов Г.Т., Брехов О.М. Две модели структуры ЦВМ// Системы массового обслуживания и коммуникации. - М.: Наука, 1974, -с 34-42.
3. Мусаев М.У.. Организация обмена в двухконтурных вычислительных системах с «трехкольцевой» организацией информации. Узбекский журнал Проблемы информатики и энергетики. №4 стр 43-45 с 1999 г.
4. Мусаев М.У. Определения стационарных вероятностей основного процесса обмена информацией. Узбекский журнал Проблемы информатики и энергетики..№6 стр 3-8 с. 2015 г
5. Кофман А., Крюн Р. Массовое обслуживание. Теория и приложения /Пер. С англ.-М.: Мир.1965.- 442 с.