- •Общие вопросы моделирования. Понятие модели. Классификация моделей. Модели физические, абстрактные, смешанные.
- •Виды моделей. Способ реализации моделирования и степень отражения в моделях времени и неопределенности.
- •Объект моделирования – вычислительная система. Основные задачи исследования объекта, их характеристика и методы решения.
- •Графовые модели алгоритмов и программ. Построение графовых моделей.
- •Эквивалентные преобразования графовых моделей алгоритмов и программ.
- •Марковские случайные процессы и их место при построении и исследовании вероятностных моделей объектов.
- •Дискретные марковские цепи. Основные задачи их исследования. Примеры объектов, для исследования которых могут быть использованы дмц.
- •Потоки событий. Основные понятия и определения. Простейший поток событий и потоки Эрланга.
- •Непрерывные марковские цепи. Основные задачи их исследования. Примеры объектов, для исследования которых могут быть использованы нмц.
- •Типовые графы состояний системы. Процесс “гибели и размножения”. Примеры объектных систем.
- •Типовые графы состояний системы. Циклический процесс. Примеры объектных систем.
- •Методы исследования немарковских случайных процессов, сводящихся к марковским.
- •Теория массового обслуживания и ее место при построении и исследовании вероятностных моделей объектов. Основные понятия и определения.
- •Системы массового обслуживания (смо). Обобщенная структура смо.
- •Основные параметры и характеристики смо.
- •Разомкнутые смо с очередью и нетерпеливыми заявками. Примеры объектных систем.
- •Разомкнутые смо с очередью и терпеливыми заявками. Примеры объектных систем.
- •Разомкнутые смо без потерь. Примеры объектных систем.
- •Замкнутые смо с простейшими потоками событий. Примеры объектных систем.
- •Смо с произвольными потоками событий. Случай бесприоритетной дисциплины обслуживания.
- •Смо с произвольными потоками событий. Случай дисциплины обслуживания с относительным приоритетом.
- •Смо с произвольными потоками событий. Случай дисциплины обслуживания с абсолютным приоритетом.
- •Сети массового обслуживания с простейшими потоками событий. Анализ разомкнутой сети. Примеры объектных систем.
- •Сети массового обслуживания с простейшими потоками событий. Анализ замкнутой сети. Примеры объектных систем.
- •Статистическое моделирование случайных процессов. Организация статистического моделирования. Моделирование базовых случайных величин (св).
- •Моделирование непрерывной случайной величины с произвольным распределением. Моделирование дискретной св. Моделирование случайных событий и потоков случайных событий.
-
Смо с произвольными потоками событий. Случай дисциплины обслуживания с абсолютным приоритетом.
Идея метода вложенных цепей Маркова – в случайном процессе рассматриваются моменты времени, в которые можно рассматривать процесс, как марковский. Можно принимать такие моменты времени за моменты времени поступления заявок.
Q(t) – объем незавершенной работы системы. Необходимо оценить время, которое требуется для завершения этого объема работы.
Имеем СМО с непрерывными состояниями, работающую в непрерывном времени, но имеющую разрывы (будут рассмотрены периоды t). Вся информация будет в точках (моменты прихода заявок), используя метод вложенных цепей маркова, будем рассматривать эти точки, а на остальные периоды – интерполяция.
Рассмотрим одноканальную разомкнутую СМО с неограниченной очередью. На вход системы поступают заявки H типов, считаем, что заявки каждого из H типов образуют простейший поток. Известны интенсивности: . Суммарный поток тоже будет простейшим: .
Принципиально: потоки обслуживания H типов имеют произвольное распределение.
Кодификатор: M|G|1|∞|∞
--------------------------------------------------------
Рассмотрим СМО с бесприоритетной дисциплиной ожидания и дисциплиной обслуживания с абсолютным приоритетом (с прерыванием обслуживания).
В канале k обрабатывается заявка Зj. В СМО поступает заявка Зi.
-
если поступившая заявка имеет менее высокий приоритет, то в канале продолжает обрабатываться Зj, а заявка Зi встает в соответствующую очередь Oi на последнее место.
-
если поступившая заявка имеет более высокий приоритет, то она поступает в канал на обработку, не дожидаясь завершения обработки Зj, а Зj поступает в соответствующую очередь Оj на ПЕРВОЕ место.
Если канал свободен, а очереди с приоритетом 1..k пусты, то заявка сразу же поступает на обслуживание, поэтому .
– среднее время ожидания начала обслуживания.
– среднее время ожидания в прерванном состоянии.
похоже на относительный приоритет, однако, суммирование в числителе идет не до H, а до k (потому что заявкам более низкого приоритета не дадут завершить обслуживание).
За время обслуживания заявки k-того приоритета в систему может прийти еще заявок приоритета .
Время обслуживания заявок более высокого приоритета, то есть время, на которое будет прервано обслуживание вновь поступившей заявки.
– время обслуживания заявок i-того приоритета, успевших прийти, пока ждет обслуживание наша заявка.
– Время обслуживания заявок всех приоритетов, более высоких, чем k, которые могут прервать обслуживание нашей заявки:
Но за время могут поступить еще несколько заявок более высокого приоритета, чем k. Их количество будет равно:
Среднее время обслуживания всех заявок будет таким:
Это может продолжаться до бесконечности, поэтому перейдем к пределу:
Введение дисциплины обслуживания с абсолютным приоритетом по отношению к дисциплине обслуживания с относительным приоритетом приводит к уменьшению среднего времени обслуживания высокоприоритетных заявок и к увеличению времени обслуживания низкоприоритетных заявок.