МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ДИСПЕТЧЕРОВ ЗАДАЧ СО СТРАТЕГИЕЙ РАЗДЕЛЕНИЯ ПРОСТРАНСТВА ДЛЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ НА ОСНОВЕ РАЗОМКНУТЫХ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ

Мартышкин  Алексей  Иванович

аспирант  каф.  «ВМиС»  ПензГТУ,  г.  Пенза

E-mail:  alexey314@yandex.ru

Бикташев  Равиль  Айнулович

канд.  техн.  наук,  профессор  каф.  «ВМиС»  ПензГТУ,  г.  Пенза

E-mail: 

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-07-31150)

АННОТАЦИЯ

Цель  работы  —  проведение  моделирования  для  анализа  производительности  диспетчера  задач  (ДЗ)  со  стратегией  разделения  пространства  в  составе  параллельной  вычислительной  системы  (ПВС).  Методы  исследования  основаны  на  положениях  теории  массового  обслуживания  (ТМО).  Рассматривается  система  с  индивидуальными  ДЗ  с  дисциплиной  обслуживания  FIFO.  Предлагаются  модели  на  основе  стохастических  сетей  для  получения  характеристик  ДЗ,  учитывающие  ограничение  числа  мест  в  очередях.  Результатами  работы  являются  выражения  для  расчета  времени  отклика  системы,  проверенные  на  адекватность  имитационным  моделированием.

ABSTRACT

The  purpose  is  to  conduct  simulations  to  analyze  the  performance  of  the  Task  Manager  (TM)  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].

Математическая  модель  ДЗ  со  стратегией  разделения  пространства  состоит  из  n-одноканальных  СМО  (S₁,…,S_m)  (см.  рис.  1).  Каждая  такая  СМО  моделирует  обслуживание  в  ДЗ  и  ЦП  (S₁,  S₂,…,  S_m).  Источник  S₀  моделирует  потоки  заявок    (пользовательских  процессов,  формируемых  предварительным  планировщиком  задач),  и  поглощает  обслуженные  заявки  (выдача  результата  пользователю).  В  работе  назначение  задач  по  очередям  выбрано  равновероятное,  чтобы  приближенно  оценить  картину  математического  моделирования  реального  процесса,  для  избегания  перегрузки  системы,  когда  все  задачи  будут  пытаться  получить  обслуживание  в  одном  или  нескольких  ЦП,  а  некоторые  ЦП  будут  вовсе  простаивать.  Перед  ДЗ  формируются  очереди  с  ограничением  числа  мест.  Если  имеется  свободное  место  в  одной  из  очередей,  то  задача  занимает  его.  Принятая  на  обслуживание  задача  находится  в  локальной  очереди  до  тех  пор,  пока  не  поступит  на  выполнение  в  ЦП.  При  завершении  выполнения  задачи  ДЗ  просматривает  локальную  очередь.  Если  в  ней  имеются  задачи  на  обслуживание,  то  назначается  на  выполнение  задача,  стоящая  в  голове  списка  (FIFO).  Если  очередь  пуста,  ЦП  переходит  в  режим  ожидания. 

ДЗ  задач  в  данном  случае  не  только  формирует  очереди  в  процессорных  узлах,  но  и  производит  балансировку  загрузки  по  некоторому  алгоритму.  Поэтому  задачи  могут  извлекаться  из  i-й  очереди  и  передаваться  с  некоторой  вероятностью  в  очередь  наименее  загруженного  j-го  процессорного  узла.

ДЗ  и  ЦП  представляются  в  виде  одноканальной  СМО.

Рисунок  1.  Схема  математической  модели  n-процессорной  системы  с  индивидуальными  диспетчерами  задач

На  вход  каждого  ДЗ  системы  поступает  поток  заявок  с  интенсивностью  .  Интенсивность  обслуживания  ДЗ  потока  заявок  равна  .

Определим  некоторые  характеристики  ДЗ:  вероятность  отказа  в  обслуживании  ,  среднюю  длину  очереди  ,  среднее  число  заявок    в  системе,  время  ожидания  в  очереди  перед  ДЗ  и  ЦП  .

Задача  получает  отказ  в  том  случае,  когда  занят  ДЗ  и  все  места  в  очереди:

,  где                               (1)

Найдем  относительную  пропускную  способность  ДЗ: 

                                                  (2)

Найдем  среднее  число  задач,  находящихся  в  очереди  перед  ДЗ.  Определим  эту  величину  как  математическое  ожидание  дискретной  случайной  величины  Z  —  число  заявок  на  обслуживание,  находящихся  в  очереди:  .  Согласно  формулам  и  выводам,  приведенным  в  [2],  получим  выражение  для  средней  длины  очереди:

  (3)

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

По  теореме  сложения  математических  ожиданий

,                              (4)

где:    —  среднее  число  заявок  в  очереди;

  —  среднее  число  заявок  на  обслуживании.

Величина    определена  выше,  найдем  величину  .

Так  как  ДЗ  в  рассматриваемой  части  СеМО  один,  случайная  величина    может  принимать  только  два  значения:  0  или  1.  Значение  0  она  принимает,  если  ДЗ  свободен  (обслуживание  предыдущей  задачи  окончено).  Вероятность  этого  равна:  .  Значение  1  она  принимает,  если  ДЗ  занят  ().

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

Таким  образом,  среднее  число  заявок,  стоящих  в  очереди  и  обслуживающихся  ДЗ,  будет  равно

,                                       (5)

Определим  теперь  среднее  время  ожидания  задачи  в  очереди  перед  ДЗ  .  Задача  поступает  в  систему  в  определенный  момент  времени.  С  вероятностью    ДЗ  свободен  и  время  ожидания  равно  нулю.  С  вероятностью    задача  придет  в  СМО,  перед  ней  не  будет  очереди,  и  она  будет  ждать  своего  обслуживания  в  течение  времени  (среднее  время  обслуживания  одной  задачи).  С  вероятностью    в  очереди  перед  рассматриваемой  задачей  будет  стоять  еще  одна  и  время  ожидания  в  среднем  будет  ,  и  т.  д.  При  ,  т.  е.  когда  вновь  приходящая  задача  застанет  ДЗ  занятым  и  ещё    задач  в  очереди,  то  время  ожидания  в  этом  случае  также  равно  нулю,  потому  что  задача  не  ставится  в  данную  локальную  очередь  (не  будет  обслуживаться  данным  ДЗ).  Опираясь  на  [2]  среднее  время  задержки  (латентность)  задачи  будет  равняться: 

                                           (6)

Теперь  определим  среднее  время  пребывания  задачи  в  системе  «очередь-ДЗ-ЦП».  Обозначим    случайную  величину  —  время  пребывания  задачи  в  СМО.  Эта  величина  складывается  из  случайных  величин  ,  где    —  время  ожидания  задачи  в  очереди  перед  ДЗ;    —  время  обслуживания  ДЗ,  если  задача  принята  на  обслуживание,  и  нулю,  если  она  не  обслуживается  (получает  отказ);    —  время  обслуживания  ЦП.

По  теореме  сложения  математических  ожиданий  .  Для  рассматриваемой  системы  ,  ,  а 

Отсюда  находим 

                                     (7)

Адекватность  аналитической  модели  диспетчеров  задач  со  стратегией  разделения  пространства  подтверждается  данными,  полученными  в  ходе  имитационного  моделирования.  Погрешность  не  превышает  15  %  ,  что  вполне  приемлемо  для  оценки  вариантов  реализации  ДЗ  на  эскизном  этапе  проектирования.

Список  литературы:

1.Бикташев  Р.А.,  Мартышкин  А.И.  Моделирование  диспетчеров  задач  многопроцессорных  систем  //  Успехи  современного  естествознания:  Научно-теоретический  журнал.  —  2012.  —  №  6.  —  С.  83—85.

2.Клейнрок  Л.  «Вычислительные  системы  с  очередями»,  М.:  «Мир»,  1979.  —  600  с.

3.Мартышкин  А.И.,  Бикташев  Р.А.,  Востоков  Н.Г.  Математическое  моделирование  диспетчеров  задач  для  систем  параллельной  обработки  на  основе  разомкнутых  систем  массового  обслуживания  //  В  мире  научных  открытий.  Красноярск:  Изд-во  «Научно-инновационный  центр»,  —  2013.  —  №  6.1  (42)  (Математика.  Механика.  Информатика).  —  С.  81—101.

4.Таненбаум  Э.  Современные  операционные  системы.  3-е  изд.  СПб.,  Питер:  2010.  —  1120  с.