1.Определяется интенсивность потока заявок  I в смо Si из системы алгебраических уравнений

, ( 1)

где P_ij — вероятность передачи заявки из j - ой СМО в i-ую,

 _i — интенсивность входного потока заявок в СМО S_j,

n — число узлов в сети.

Для нахождения интенсивностей  _i составляется матрица вероятностей передач заявок между системами S₁,S₂,...,S_n сети.

где S₀ — источник входного потока заявок неограниченной емкости.

Из системы (I) получаем  ₁=(1/ ) ,  ₁=( _j/ ) , (j=1,2,...n).

2.Вычисляются коэффициенты передач для каждой смо

 _i =  _j/ ,(i=1,2,...n), ( 2)

где  — интенсивность входного потока заявок (в модели — СМО S0)

3.Определяется среднее время обслуживания Ui заявки в смо Si :

 _i =  _i/B_i, (i=1,2,...n), ( 3)

где  _i — трудоемкость процессорных операций в СМО S_i,  _i быстродействие устройств в СМО S_i.

4.Вычисляются коэффициенты загрузки отдельных СМО сети :

 _i =  _{i i}/m_i, ( 4)

где m_i — число обслуживаемых устройств в каждом из СМО S_i.

5.Для отдельных СМО сети определяются следующие характеристики:

а) среднее число заявок, находящихся на обслуживании

k = m_i _i, ( 5)

б) средняя длина очереди заявок

l_i = (m_i^m_{i   i}^m+1)   _0i/(m_i!(1- _i)²), ( 6)

где  _0i — вероятность простоя всех m_i каналов, равная

, ( 7)

в) среднее число заявок, находящихся на обслуживании и в очереди к устройству:

r_i = l_i+k_i,

г) среднее время ожидания заявок в очереди

, ( 8)

д) среднее время пребывания заявок в СМО

, ( 9)

е) суммарные средние времена ожидания и пребывания, учитывающие число прохождений заявки через данную СМО

W_i =  _iw_i, ( 10)

U_i =  _iu_i, ( 11)

6.Для моделирующей сети в целом характеристики п.5 определяются как

, ( 12)

, ( 13)

, ( 14)

, ( 15)

2.Расчет характеристик мультипроцессорной системы

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

1) Имеет доступ к общей памяти;

2) имеет общий доступ к устройствам ввода-вывода;

3) управляется общей операционной системой, которая обеспечивает требуемое взаимодействие между процессорами и выполняемыми им программами как на аппаратном, так и на программном уровне.

С точки зрения структурной организации МПС наиболее существенным является способ связи между процессорами и памятью системы. Различают системы с общей и индивидуальной памятью. Структура системы с общей памятью представлена на рисунке 9.1, где Пр - процессор, МП - модуль памяти, К - коммутатор модуля памяти, КВВ - канал ввода-вывода, ВУ - внешнее устройство.

 

Рисунок 2 - Структура системы с общей памятью

 

Основная особенность МПС с общей памятью состоит в том, что каждый из процессоров Пр₁, Пр₂, ..., Пр_N имеет доступ к любому модулю МП₁, МП₂, …, МП_L которые могут функционировать независимо друг от друга и в каждый момент времени может выполняться до N одновременных обращений к модулям памяти с целью записи или чтения слова информации.

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

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

МПС с общей памятью функционирует в режиме разделения нагрузки, при котором любая программа может выполняться на любом процессоре. Процесс обслуживания заявок в режиме разделения нагрузки для системы с одноуровневой памятью можно рассматривать как процесс функционирования одной N-канальной системы массового обслуживания (рисунок 3) с интенсивностью  входящего потока, общей очередью заявок O, заявки из которой выбирается в порядке поступления их в систему, и средней длительностью обслуживания заявки каждым из процессоров Пр₁, …, Пр_N, равной  . Заявка, поступающая в систему, содержащую N процессоров, при наличии хотя бы одного свободного процессора, немедленно принимается процессором на обслуживание. Если все N процессоров заняты обслуживанием ранее поступивших заявок, поступающая заявка размещается в очереди.

Определим характеристики МПС на основе модели (рисунок 3). Модель соответствует МПС (рисунок 2) только для случая, когда вся информа-ция, обрабатывемая процессорами, размещается в оперативной памяти.

 

Рисунок 3 - Модель МВС с общей памятью

 

Пусть в МПС поступает М потоков заявок с интенсивностями  ₁, …,  _M. Обслуживание заявок сводится к выполнению соответствующих программ, средние трудоемкости которых равны  ₁, …,  _M операций в расчете на один прогон программы. Принимаем, что обслуживание заявок выполняется на основе дисциплины FIFO. В таком случае можно считать, что система обслуживает однородный поток заявок, поступающих с интенсивностью

Для обслуживания любой заявки из суммарного потока требуется в среднем

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

,

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

.

Параметры  , N и  должны отвечать условию существования стационарного режима, при котором в очереди пребывает конечное число заявок и, следовательно, конечны времена ожидания и пребывания заявок. На каждый из процессоров поступает N-ая доля заявок и, следовательно, отдельный процессор обслуживает поток с интенсивностью

.

Загрузка процессора

,

где

- суммарная интенсивность обслуживания заявок N - процессорной системой. Стационарный режим существует, если

Следовательно, параметры МПС должны отвечать соотношению

т.е.

,

при этом суммарная загрузка

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

1.Средняя длина очереди заявок, ожидающих обслуживания в системе

( 2.1)

где

вероятность того , что в системе нет ни одной заявки, т.е. все N процессоров простаивают,

загрузка процессора N - процессорной системы.

2.Среднее время ожидания заявок в очереди

( 2.2)

3.Среднее время пребывания заявок в системе

( 2.3)

4 Вероятность того, что в момент поступления очередной заявки все N процессоров заняты обслуживанием

, ( 2.4)

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

Функционирование МПС в режиме разделения нагрузки с двухуровневой памятью можно представить разомкнутой сетевой моделью (рисунок 4).

Рисунок 4- Сетевая модель МВС с общей памятью двух уровней

Обслуживание заявки, поступившей на вход системы, состоит из этапов счета, выполняемых процессорами, которые моделируются системой S₁, и этапов обращения к памяти, моделируемой системой S₂. Этап обращения к памяти следует за этапом счета с вероятностью p и с вероятностью (1-p) заявка покидает систему. Внешняя память представлена С-канальной системой массового обслуживания S₂, т.е. предполагается, что любое обращение к внешней памяти может быть обслужено любым из каналов ввода-вывода. На основе использования аппарата линейных стохастических сетей могут быть найдены следующие характеристики МВС с общей памятью двух уровней: