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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ДИСПЕТЧЕРОВ ЗАДАЧ СО СТРАТЕГИЕЙ РАЗДЕЛЕНИЯ ПРОСТРАНСТВА ДЛЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ НА ОСНОВЕ РАЗОМКНУТЫХ СЕТЕЙ
МАССОВОГО ОБСЛУЖИВАНИЯ
Мартышкин Алексей Иванович аспирант каф. «ВМиС"ПензГТУ, г. Пенза E-mail: alexey314@yandex. ru Бикташев Равиль Айнулович канд. техн. наук, профессор каф. «ВМиС"ПензГТУ, г. Пенза
E-mail: rabiktashev@mail. ru
MATHEMATICAL MODELING OF TASK MANAGER WITH THE
STRATEGY OF TIME-SHARING FOR PARALLEL COMPUTING SYSTEMS BASED OPEN QUEUING SYSTEMS
Alexey Martyshkin
a post-graduate student of the faculty «CMaS», Penza State Technological
University, Penza Ravil Biktashev
ph.D., Professor, Penza State Technological University, Penza
Работа выполнена при финансовой поддержке РФФИ (грант № 12−731 150)
АННОТАЦИЯ
Цель работы — проведение моделирования для анализа производительности диспетчера задач (ДЗ) со стратегией разделения пространства в составе параллельной вычислительной системы (ПВС). Методы исследования основаны на положениях теории массового обслуживания (ТМО). Рассматривается система с индивидуальными ДЗ с дисциплиной обслуживания FIFO. Предлагаются модели на основе стохастических сетей для получения характеристик ДЗ, учитывающие ограничение числа мест в очередях. Результатами работы являются выражения для расчета времени отклика системы, проверенные на адекватность имитационным моделированием.
ABSTRACT
The purpose is to conduct simulations to analyze the performance of the Task Manager™ with the strategy of the separation space of the parallel computing
system (PCS). Methods of investigation are based on the queuing theory. A system of individual TM with the discipline of service FIFO. Proposed a model based on stochastic networks to characterize the TM, taking into account the limitation of the number of places in the queues. The results of the work are the expressions for calculating the response time of the system, tested on the adequacy of the simulation.
Ключевые слова: математическое моделирование- диспетчер задач- стратегия разделения пространства- стохастическая сеть- дисциплина обслуживания.
Keywords: mathematical modeling- task manager- time-sharing strategy- stochastic network- service discipline.
Существуют различные способы построения ДЗ в системах параллельной обработки, из них можно выделить два основных: с разделением времени и разделением пространства [1, 4]. В рассмотренном в [3] ДЗ с разделением времени можно выявить недостаток его организации, из-за которого впоследствии снижается производительность всей системы в целом. Проблема в конфликтах, которые возникают при запросе ДЗ в том, что только определенное устройство имеет право взаимодействовать с очередью задач, на что тратится время. Может иметь место такая ситуация, при которой в системе при наличии свободных ЦП не происходит обработка ожидающих задач, поступающих с некоторой интенсивностью Л, из-за того, что ДЗ просто не успевает обслужить все задачи. Выходом из данной «конфликтной» ситуации может послужить иная организация самого ДЗ — с индивидуальными очередями процессов к ЦП, о чем и пойдет более подробно речь в данной статье.
Существует большое число дисциплин диспетчеризации, в соответствии с которыми и формируется очередь ожидающих обслуживания задач. В работе будет рассмотрена дисциплина FIFO, которая находит широкое применение на практике из-за своей простоты [4].
Математическая модель ДЗ со стратегией разделения пространства состоит из w-одноканальных СМО (Sj,…, Sm) (см. рис. 1). Каждая такая СМО моделирует обслуживание в ДЗ и ЦП (Sj, S2,…, Sm). Источник S0 моделирует потоки заявок Л0 (пользовательских процессов, формируемых предварительным планировщиком задач), и поглощает обслуженные заявки (выдача результата пользователю). В работе назначение задач по очередям выбрано равновероятное, чтобы приближенно оценить картину математического моделирования реального процесса, для избегания перегрузки системы, когда все задачи будут пытаться получить обслуживание в одном или нескольких ЦП, а некоторые ЦП будут вовсе простаивать. Перед Д З формируются очереди с ограничением числа мест. Если имеется свободное место в одной из очередей, то задача занимает его. Принятая на обслуживание задача находится в локальной очереди до тех пор, пока не поступит на выполнение в ЦП. При завершении выполнения задачи ДЗ просматривает локальную очередь. Если в ней имеются задачи на обслуживание, то назначается на выполнение задача, стоящая в голове списка (FIFO). Если очередь пуста, ЦП переходит в режим ожидания.
ДЗ задач в данном случае не только формирует очереди в процессорных узлах, но и производит балансировку загрузки по некоторому алгоритму. Поэтому задачи могут извлекаться из i-й очереди и передаваться с некоторой вероятностью в очередь наименее загруженного j-го процессорного узла.
ДЗ и ЦП представляются в виде одноканальной СМО.
Рисунок 1. Схема математической модели п-процессорной системы с индивидуальными диспетчерами задач
На вход каждого ДЗ системы поступает поток заявок с интенсивностью
=. Интенсивность обслуживания ДЗ потока заявок равна ¦
Определим некоторые характеристики ДЗ: вероятность отказа в обслуживании Ротк, среднюю длину очереди Ьочср, среднее число заявок 8 в системе, время ожидания в очереди перед ДЗ и ЦП WСМО.
Задача получает отказ в том случае, когда занят ДЗ и все места в очереди:
-ю) _Ло
Ротк — Рт+1 = т+2, Где V-- (1)
1 —? Ив
Найдем относительную пропускную способность ДЗ:
О — 1-Р -1 — Ут+1 (1 -ю) (2)
?--отн отк * т+2 ^ '-
1 — V
Найдем среднее число задач, находящихся в очереди перед ДЗ. Определим эту величину как математическое ожидание дискретной случайной величины Ъ — число заявок на обслуживание, находящихся в очереди: — М2.
Согласно формулам и выводам, приведенным в [2], получим выражение для средней длины очереди:
^^ _ V2 ¦ (1 — V)¦ [1 -?т '- (т +1 — т ¦ ?) _ V2 ¦ [1 — V™ ¦ (т +1 — т ¦у)] оЧср — (1 -vm+2) ¦ (1 -V)2 ~ (3)
Теперь получим формулу для среднего числа 8 задач, как стоящих в очереди, так и находящихся на обслуживании. Решим эту задачу следующим образом: рассмотрим общее число задач 8, связанных с системой, как сумму
двух случайных величин — числа задач, стоящих в очереди Ъ и числа задач О, находящихся на обслуживании 5 = Z + О.
По теореме сложения математических ожиданий
5 = М[5 ] = М[ Z ]+М[ О] = Ьочср + ш, (4)
где: Ьочср — среднее число заявок в очереди-
Ш — среднее число заявок на обслуживании. Величина Ьочср определена выше, найдем величину Ш.
Так как ДЗ в рассматриваемой части СеМО один, случайная величина О может принимать только два значения: 0 или 1. Значение 0 она принимает, если ДЗ свободен (обслуживание предыдущей задачи окончено). Вероятность этого
, т+2
равна: р -^. Значение 1 она принимает, если ДЗ занят (р = ^ ^^).
С учетом полученных выражений находим математическое ожидание числа заявок, находящихся на обслуживании ш = 0 • р +1-(1 — р) = ¦
т+2
со -а
1 т+2
1 — а
Таким образом, среднее число заявок, стоящих в очереди и обслуживающихся ДЗ, будет равно
т+2
со -а
Z = Ьоч ±-, (5)
ср Л т+2 '- V /
1 — а
Определим теперь среднее время ожидания задачи в очереди перед ДЗ Iож. Задача поступает в систему в определенный момент времени. С вероятностью Ро Д З свободен и время ожидания равно нулю. С вероятностью Р1 задача придет в СМО, перед ней не будет очереди, и она будет ждать своего обслуживания в течение времени 1/ (среднее время обслуживания одной
задачи). С вероятностью р2 в очереди перед рассматриваемой задачей будет стоять еще одна и время ожидания в среднем будет 2/ м, и т. д. При к = т +1, т. е. когда вновь приходящая задача застанет ДЗ занятым и ещё т задач в очереди, то время ожидания в этом случае также равно нулю, потому что задача не ставится в данную локальную очередь (не будет обслуживаться данным ДЗ). Опираясь на [2] среднее время задержки (латентность) задачи будет равняться:
— 1 Ьоч
г =-- Ьоч = -р (6)
ож ср л V /
А
'-00
Теперь определим среднее время пребывания задачи в системе «очередь-ДЗ-ЦП». Обозначим ШСМО случайную величину — время пребывания задачи в СМО. Эта величина складывается из случайных величин шсмМО = Тож + Тобслдп + Тобслцп, где Тож — время ожидания задачи в очереди перед ДЗ- ТобслДП — время обслуживания ДЗ, если задача принята на обслуживание, и
нулю, если она не обслуживается (получает отказ) — ТобслцП — время обслуживания ЦП.
По теореме сложения математических ожиданий
го = ЩЖсмо] = М[Тож] +М[Тобсдп] + МТобслцп]. Для рассматриваемой системы
М Тж ] = г ож, М [ Тбслдп ] = Qom» • г обслДП = 0отн, а М[ Т] = МцП
Мв
Отсюда находим
Ьоч О
Ш = Т + Т + Т =-- + отн +и (7)
Ш СМО 1 ож т 1 обслДП т 1 обслЦП — т т МЦП V '- /
Л)0 Мв
Адекватность аналитической модели диспетчеров задач со стратегией разделения пространства подтверждается данными, полученными в ходе имитационного моделирования. Погрешность не превышает 15%, что вполне
приемлемо для оценки вариантов реализации ДЗ на эскизном этапе
проектирования.
Список литературы:
1. Бикташев Р. А., Мартышкин А. И. Моделирование диспетчеров задач многопроцессорных систем // Успехи современного естествознания: Научно-теоретический журнал. — 2012. — № 6. — С. 83−85.
2. Клейнрок Л. «Вычислительные системы с очередями», М.: «Мир», 1979. — 600 с.
3. Мартышкин А. И., Бикташев Р. А., Востоков Н. Г. Математическое моделирование диспетчеров задач для систем параллельной обработки на основе разомкнутых систем массового обслуживания // В мире научных открытий. Красноярск: Изд-во «Научно-инновационный центр», — 2013. — № 6.1 (42) (Математика. Механика. Информатика). — С. 81−101.
4. Таненбаум Э. Современные операционные системы. 3-е изд. СПб., Питер: 2010. — 1120 с.

ПоказатьСвернуть
Заполнить форму текущей работой