Моделирование ВС. Модели массового обслуживания. (Тема 3.2)

1.

СИСТЕМНЫЙ АНАЛИЗ И МАШИННОЕ МОДЕЛИРОВАНИЕ
МОДЕЛИРОВАНИЕ
ВЫЧИСЛИТЕЛЬНЫХ
СЕТЕЙ И СИСТЕМ

2. 3.2 МОДЕЛИ МАССОВОГО ОБСЛУЖИВАНИЯ

Теория массового
обслуживания
(ТМО)
ИЗУЧАЕТ
процессы обслуживания
случайное длительность
появление заявок
случайная
(требований) на
обслуживание
обслуживания
каждой
заявки

3. Теория массового обслуживания

ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ
Математический
аппарат:
вероятностные
математические
модели
Объекты
исследования:
• системы массового
обслуживания (СМО)
• сети массового
обслуживания (СеМО)

4. Системы массового обслуживания

СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ
Объекты
СМО
статические
динамические
моделируют средства
обслуживающие
моделируют
заявки
обработки информации
аппараты
(ОА)(запросы, требования,
решаемые
в ВС
(аппаратные и
задачи
транзакты)
программные)
ресурсы

5. Функционирование СМО

ФУНКЦИОНИРОВАНИЕ СМО
поступление
заявок
очередь
ОА
занят
свободен
правило поступления заявок
из очереди на обслуживание
дисциплина обслуживания

6. Приоритетное обслуживание в СМО

ПРИОРИТЕТНОЕ ОБСЛУЖИВАНИЕ В СМО
поступление
заявок
очередь
ОА
занят
преимущественное
право на обслуживание
приоритет
свободен

7. Типы СМО

ТИПЫ СМО
многоканальные
ОА1
ОА2
…
ОАn
многофазные
ОА1
ОА2
…
ОАn

8. Классификация СМО

КЛАССИФИКАЦИЯ СМО
Формат
классификационного
обозначения:
A/B/C/D/E
закон распределения интервалов
времени между поступлениями заявок
детерминированное
эрланговское
экспоненциальное
-- ЕG - М
-D
групповое
(пакетное)
гамма-распределение
- Г- Н
ТИПЫ: гиперэкспоненциальное
произвольное
поступление - Gr

9. Классификация СМО

КЛАССИФИКАЦИЯ СМО
Формат
классификационного
обозначения:
A/B/C/D/E
дисциплина обслуживания
закон распределения
FIFO
ТИПЫ:
времени•обслуживания
• LIFO
число обслуживающих
приборов
• RANDOM
SF
число мест в очереди

10. Типы СМО, используемые для моделирования вычислительных сетей и систем

ТИПЫ СМО, ИСПОЛЬЗУЕМЫЕ ДЛЯ
МОДЕЛИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ
СЕТЕЙ И СИСТЕМ
наименование обозначение
Одноканальные
СМО с
ожиданием
схема
G/G/1
Один обслуживающий прибор с
бесконечной очередью. С той или иной
долей приближения моделирует
практически любой узел ВС

11. Типы СМО, используемые для моделирования вычислительных сетей и систем

ТИПЫ СМО, ИСПОЛЬЗУЕМЫЕ ДЛЯ
МОДЕЛИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ
И СИСТЕМ
наименование обозначение
Одноканальные
СМО с потерями
G/G/1/r
схема
1…r
Один обслуживающий прибор с конечным
числом мест в очереди. Используется при
моделировании каналов передачи в ВС

12. Типы СМО, используемые для моделирования вычислительных сетей и систем

ТИПЫ СМО, ИСПОЛЬЗУЕМЫЕ ДЛЯ
МОДЕЛИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ
СЕТЕЙ И СИСТЕМ
наименование обозначение
Многоканальные
СМО с
ожиданием
схема
G/G/m
Несколько параллельно работающих
обслуживающих приборов с общей
бесконечной очередью. Моделируют
группы абонентских терминалов ВС,
работающих в диалоговом режиме
1
…
m

13. Типы СМО, используемые для моделирования вычислительных сетей и систем

ТИПЫ СМО, ИСПОЛЬЗУЕМЫЕ ДЛЯ
МОДЕЛИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ
СЕТЕЙ И СИСТЕМ
наименование обозначение
схема
Многоканальные
СМО с
потерями
1…r
G/G/m/r
Несколько параллельно работающих
обслуживающих приборов с общей
очередью, число мест в которой
ограничено. Используются для
моделирования каналов связи
1
…
m

14. Типы СМО, используемые для моделирования вычислительных сетей и систем

ТИПЫ СМО, ИСПОЛЬЗУЕМЫЕ ДЛЯ
МОДЕЛИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ
СЕТЕЙ И СИСТЕМ
наименование обозначение
схема
Одноканальные
lll
СМО с групповым
Gr/G/1
поступлением
заявок
Перед обслуживанием заявки
группируются в пакеты по определенному
правилу. Используются для
моделирования узлов коммутации.

15. Типы СМО, используемые для моделирования вычислительных сетей и систем

ТИПЫ СМО, ИСПОЛЬЗУЕМЫЕ ДЛЯ
МОДЕЛИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ
СЕТЕЙ И СИСТЕМ
наименование обозначение
Одноканальные
СМО с групповым
G/Gr/1
обслуживанием
заявок
схема
Заявки обслуживаются пакетами,
составляемыми по определенному
правилу. Используются для
моделирования узлов коммутации.
lll

16. Классификация задач теории массового обслуживания

КЛАССИФИКАЦИЯ ЗАДАЧ ТЕОРИИ МАССОВОГО
ОБСЛУЖИВАНИЯ
Задачи анализа поведения СМО
ЦЕЛЬ: выявление операционных
характеристик,
определяющих поведение
СМО в процессе
функционирования

17. Операционные характеристики СМО

ОПЕРАЦИОННЫЕ
ХАРАКТЕРИСТИКИ СМО
Q(t)
Qn
- длина очереди в момент времени
t, т.е. число заявок, ожидающих
обслуживания с учетом или без тех
заявок, обслуживание которых уже
началось.
- длина очереди на n –й стадии

18. Операционные характеристики СМО

ОПЕРАЦИОННЫЕ
ХАРАКТЕРИСТИКИ СМО
W(t) - виртуальная продолжительность
ожидания относительно момента
времени t.
Wn
- продолжительность периода, в
течение которого n -я заявка
ожидает обслуживания

19. Операционные характеристики СМО

ОПЕРАЦИОННЫЕ
ХАРАКТЕРИСТИКИ СМО
Ti
- продолжительность периода
занятости системы, начало которого
соответствует Q(t0)=i, т.е.
длительность периода занятости
системы, начинающегося при
наличии в системе i заявок
In
- продолжительность n -го периода
простоя системы

20. Классификация задач теории массового обслуживания

КЛАССИФИКАЦИЯ ЗАДАЧ ТЕОРИИ МАССОВОГО
ОБСЛУЖИВАНИЯ
Статистические задачи
ЦЕЛЬ: оценка соответствия
модели исходной системе
на основании
статистического анализа
экспериментальных данных
ее функционирования

21. Классификация задач теории массового обслуживания

КЛАССИФИКАЦИЯ ЗАДАЧ ТЕОРИИ МАССОВОГО
ОБСЛУЖИВАНИЯ
Операционные задачи
ЦЕЛЬ
описательные
принятие решений
относительно
режима
функционирования
нормативные
установление
нормативных
требования по
обеспечению
эффективной
работы

22. 3.3 АНАЛИТИЧЕСКОЕ МОДЕЛИРОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

Аналитическая модель СМО
в общем виде:
V (t ) F X (t ), Q (t )
где X (t) – вектор параметров входных
потоков заявок;
Q(t) – вектор параметров ОА и
ресурсов СМО

23. Ограничения аналитических моделей СМО

ОГРАНИЧЕНИЯ АНАЛИТИЧЕСКИХ
МОДЕЛЕЙ СМО
Входной поток заявок должен
обладать свойствами:
ординарности
стационарности
отсутствия
последействия
простейший
поток

24. Простейший поток

ПРОСТЕЙШИЙ ПОТОК
Вероятность поступления в
промежуток времени t ровно k
требований:
k
t
k
t
P (t )
k!
e
где >0 - постоянное число
(интенсивность)
,

25.

стационарность =
вероятность поступления
определенного числа заявок
в интервале времени t не
зависит от положения этого
интервала на оси времени.
t
tn
tm
t
Pk ( t m ) Pk (t n )

26.

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

27. Ограничения аналитических моделей СМО (продолжение)

ОГРАНИЧЕНИЯ АНАЛИТИЧЕСКИХ МОДЕЛЕЙ СМО
(ПРОДОЛЖЕНИЕ)
Интервалы времени между моментами
поступления заявок и времена
обслуживания заявок в устройствах ВС
распределены по экспоненциальному
закону
В общем случае приоритетность
обслуживания не рассматривается,
используются дисциплины обслуживания
типа FIFO

28.

Всем Счастья и Любви!