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

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


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

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

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

ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ ДИСПЕТЧЕРОВ ЗАДАЧ СО СТРАТЕГИЕЙ РАЗДЕЛЕНИЯ В ПРОСТРАНСТВЕ ДЛЯ МНОГОПРОЦЕССОРНЫХ СИСТЕМ НА ОСНОВЕ СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ
Мартышкин Алексей Иванович канд. техн. наук, доцент кафедры Вычислительных машин и систем Пензенского государственного технологического университета, РФ, г. Пенза
E-mail: A lexey314@yandex. ru
NUMERICAL SIMULATION OF TASK MANAGER WITH THE STRATEGY OF SEPARATED IN SPACE FOR MULTIPROCESSOR SYSTEMS BASED
ON QUEUEING NETWORKS
Alexey Martyshkin
candidate of Science, assistant professor Department of Computational Systems and Machines of Penza State Technological University, Russia, Penza
Работа выполнена при финансовой поддержке стипендии Президента Р Ф молодым ученым т аспирантам на 2012−2014 гг. (СП-1172. 2012. 5).
АННОТАЦИЯ
Целью статьи является проведение моделирования для анализа производительности диспетчера задач со стратегией разделения в пространстве в многопроцессорной системе. Методы исследования основаны на положениях теории систем и сетей массового обслуживания и теории вероятностей. В статье приводится численное моделирование диспетчеров задач для многопроцессорных систем на основе разомкнутых сетей массового обслуживания. Результатами работы являются выражения для расчета характеристик представленной системы: для каждого класса задач в отдельности и для суммарного потока задач. Сделаны выводы.
ABSTRACT
The purpose of the article is to conduct modeling for analyze the performance of Task Manager with the strategy of separation in space in a multiprocessor system. Research methods based on the provisions theory of systems and networks, queuing theory and probability theory. The article provides a numerical simulation of Task Managers for multiprocessor systems based on open queuing networks. Result is the
Created by DocuFreezer | www. DocuFreezer. com |
expression for calculating the characteristics of the present system: for each class of tasks separately and for a total stream problems. The conclusions made.
Ключевые слова: математическая модель- диспетчер задач- разделение в пространстве- случайный процесс- система массового обслуживания- приоритет- вероятность.
Keywords: mathematical model- task manager- space division- the stochastic process- queuing system- priority- probability.
Изучая сложные системы со случайным характером функционирования, полезной математической моделью является стохастический процесс, который развивается в зависимости от ряда случайных факторов.
Примером случайных процессов могут служить процессы, связанные с диспетчеризацией задач в многопроцессорных системах. Большая часть моделей систем со стохастическим характером функционирования строится на основе моделей массового обслуживания, процессы в которых являются случайными и, зачастую, марковскими, либо каким-то образом связанные с марковскими процессами, применение которых оказывается особенно эффективным и результативным при исследовании систем и сетей массового обслуживания с накопителями ограниченной емкости.
Математическая модель диспетчера задач (ДЗ) со стратегией разделения в пространстве [2, 4] состоит из w-одноканальных СМО (Sj,…, Sm) (см. рис. 1). Каждая такая СМО моделирует обслуживание в ДЗ и центральном процессоре
л
(ЦП) (Si, S2,…, Sm). Источник S0 моделирует потоки заявок 0 и поглощает обслуженные заявки. Перед Д З формируются очереди с ограничением числа мест. В систему поступает неоднородный поток задач. Ожидающие обслуживания задачи разнесены по очередям ограниченной емкости. Между задачами разных классов установлены относительные приоритеты (ОП), означающие, что всякий раз из очередей на обслуживание выбирается задача с самым высоким приоритетом. При этом при поступлении в систему
высокоприоритетной задачи обслуживание низкоприоритетной не прерывается. При заполненных очередях поступившая задача теряется. ДЗ и ЦП представляются в виде одноканальной СМО.
Рисунок 1. Схема математической модели п-процессорной системы с
индивидуальными диспетчерами
Рассматриваемая система является одноканальной. Входящий поток задач — неоднородный: в систему поступает два потока пользовательских задач разного приоритета. Очереди для задач каждого класса являются ограниченными по длине. Для примера, в данной работе длина очередей
принята одинаковой и равной г = Г2 = 1
Дисциплина буферизации — без вытеснения задач: если при поступлении в систему задачи любого класса соответствующая очередь заполнена до конца, то задача теряется. Дисциплина обслуживания — с относительными приоритетами: задачи первого класса имеют высший приоритет по отношению к задачам второго класса [1, 5].
Поступающие в систему задачи двух классов образуют простейшие потоки
1 л
с интенсивностями 1 и 2 соответственно.
Длительности обслуживания задач каждого класса распределены по
= /Ъ ^2= /ь ъ экспоненциальному закону с интенсивностями / 1 и / 2, где 1 и
Ъ2 соответственно средние длительности обслуживания задач класса 1 и 2.
Для описания состояний марковского процесса будем использовать распределение задач между ДЗ и очередями. Закодируем состояния следующим образом: Х{. (Д/О1, О2), где Д= {0, 1, 2} - состояние ДЗ, задаваемое классом задачи, находящейся на обслуживании («0» — ДЗ- «1» или «2» — на обслуживании находится задача класса 1 или 2) — О1, О2= {0,1} - состояние очередей 1 и 2 («0» — отсутствие задачи в очереди, «1» — наличие одной задачи в очереди соответствующего класса). При таком предложенном способе кодирования система может находиться в следующих состояниях (рис. 2):
Х0: (0/0,0) — в системе нет ни одной задачи-
Х2: (1/0,0) — на обслуживании находится задача класса 1-
Х2: (2/0,0) — на обслуживании находится задача класса 2-
Х3: (1/1,0) — на обслуживании находится задача класса 1 и одна задача класса 1 ожидает обслуживания в очереди О11-
Х4: (1/0,1) — на обслуживании находится задача класса 1 и одна задача класса 2 ожидает обслуживания в очереди О12-
Х5: (2/1,0) — на обслуживании находится задача класса 2 и одна задача класса 1 ожидает обслуживания в очереди О11-
Х6: (2/0,1) — на обслуживании находится задача класса 2 и одна задача класса 2 ожидает обслуживания в очереди О12-
Х7: (1/1,1) — на обслуживании находится задача класса 1 и по одной задачи класса 1 и 2 ожидают обслуживания в очередях О11 и О12-
Х8: (2/1,1) — на обслуживании находится задача класса 2 и по одной задачи класса 1 и 2 ожидают обслуживания в очередях О11 и О12-
Рисунок 2. Размеченный граф переходов
В каждый момент времени происходит только одно событие: либо поступление задачи какого-либо класса, либо завершение обслуживания задачи в ДЗ, поскольку вероятность появления двух и более событий в один и тот же момент времени равна нулю [1, 3].
При наличии в очередях задач первого и второго приоритетов (состояния Х7 и Х8) после завершения обслуживания некоторой задачи в ДЗ случайный процесс переходит в состояние Х4, означающее, что на обслуживание всегда выбирается высокоприоритетная задача класса 1.
По графу переходов составим систему уравнений для определения стационарных вероятностей:
Л1+Л2) • Ро Рх + М2 • Р2 (Л1+Л2 +Мх) • Рх = л • Ро + Мх • Рз + М2 • Р5 (Лх+Л2 + М2) • Р2 = Л2 • Ро + Мх • Ра +М2 • Рб (Л2 +Мх) • Рз = v Рх (Лх+Мх) • Ра = Л2 • Рх + Мх • Р7 + м2 • Р% (Л2 +м2) • Р5 = v Р2
(л+м2) • Рб = Л2 • Р2 Мх • Р7 = Л2 • Р% + Л • Ра М2 • Р% = Л2 • Р5 + Л • Рб Р + Рх + Р2 + Рз + Ра + Р5 + Рб + Р7 + Р% = х
(1)
& lt-
Расчет характеристик представленной системы будем производить двумя способами: 1) для каждого класса задач- 2) для суммарного потока задач.
Расчет характеристик обслуживания задач каждого класса (приоритета) выполняется по следующим выражениям:
а. нагрузка на ДЗ
Ух =Лх = Лх^ Ьх- У2 = Л = Л2 • Ь2
Мх М2 (2)
б. загрузка, создаваемая потоком задач, которая может характеризоваться вероятностью того, что на обслуживании в ДЗ находится задача класса 1 или 2 соответственно
Рх = Рх + Рз + Ра + Р7- Р2 = Р2 + Р5 + Рб + Р8 (3)
в. среднее число задач в очередях перед ДЗ
1х = Рз + Р 5 + Р7 + Р8- 12 = Ра + Рб + Р7 + Р8
(4)
г. среднее число задач в очередях и на обслуживании
т = ^ + р- т2 = К + Р
д. вероятность потери задач из-за переполнения очередей
= Рз + Р5 + Рт + Р8- = Р 4 + Рб + Рт + Р8
е. производительность по каждому классу (приоритету) задач
Л = Л * (1 -?1) —2 =2 * (1 -?2)
ж. среднее время ожидания задач в очередях
I, 12
= -г- оо2=-4-
Л Л2
з. среднее время пребывания задач в системе
т / т /
и1 = у^ + уцп =®1 + Ь1 + уцп — и2 = у^+ уцп = ®2 + Ь2 + уцп
(6)
(7)
(8)
(9)
Расчет характеристик обслуживания задач суммарного потока выполняется по следующим выражениям:
1) суммарная нагрузка на ДЗ
У = У1 + у 2
(10)
2) суммарная загрузка системы
Р = Р + Р2
3) коэффициент простоя системы
4) суммарное число задач в очередях
Ь = ^ +12
5) суммарное число задач в системе
м = т + т = ь + р
6) вероятность потери задач
2 =? + С2
7) производительность системы
л'- = Л + Л
8) среднее время ожидания в очередях задач суммарного потока
Ж = (+Л2®2)/ = Ь/
/Л /Л
9) среднее время пребывания задач суммарного потока
(11)
? = 1-р (12)
(13)
(14)
(15)
(16)
и =(л'-^ + = ^ = ф + (?1 + ?2) + Уцп
(18)
Ниже приведены полученные графики численного моделирования ДЗ со стратегией разделения в пространстве (рис. 3, рис. 4).
Рисунок 3. Зависимость латентности диспетчера задач от интенсивности неоднородного входного потока задач
Рисунок 4. Зависимость времени ответа системы от интенсивности неоднородного входного потока задач
Были получены выражения для численного расчета основных вероятностно-временных характеристик ДЗ со стратегией разделения в
пространстве. Расчет характеристик представленной системы производился
двумя способами: а) для каждого класса задач- б) для суммарного потока задач.
Список литературы:
1. Алиев Т. И. Основы моделирования дискретных систем. СПб.: СПбГУ ИТМО, 2009. — 363 с.
2. Бикташев Р. А., Мартышкин А. И. Моделирование диспетчеров задач многопроцессорных систем // Успехи современного естествознания: Научно-теоретический журнал. — 2012. — № 6. — С. 83−85.
3. Вентцель Е. С. Введение в исследование операций. М.: & quot-ЁЁ Медиа& quot-, 2012. — 390 с.
4. Мартышкин А. И. Исследование диспетчеров задач многопроцессорных систем на моделях массового обслуживания // XXI век: итоги прошлого и проблемы настоящего плюс: Научно-методический журнал. Пенза: Пенз. гос. технол. академия. — 2012. — № 5. — С. 139−146.
5. Таненбаум Э. Современные операционные системы. 3-е изд. СПб.: Питер, 2010. — 1120 с.

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