8. Одноканальная СМО с неограниченной очередью

(к оглавлению)

 

Цель работы:

-   Овладение аналитическими методами и методами имитационного моделирования исследования одноканальных систем массового обслуживания с неограниченной очередью заявок.

-   Исследование зависимости показателей системы от дисперсии времени обслуживания.

-   Исследование влияния приоритетности обслуживания на показатели системы.

 

Теоретические сведения

 

Рассмотрим одноканальную систему массового обслуживания с ожиданием.

Будем предполагать, что входящий поток заявок на обслуживание есть простейший поток с интенсивностью λ.

Интенсивность потока обслуживания равна μ и может иметь произвольное распределение.

Заявка, пришедшая на вход СМО и заставшая канал свободным, немедленно поступает на обслуживание.

Заявка, пришедшая на вход СМО и заставшая канал занятым, становится в очередь на обслуживание и ожидает неограниченно долго освобождения прибора.

По дисциплине обслуживания, под которым будем понимать правило (алгоритм) выборки заявок из очереди на обслуживание. Наиболее употребительными являются дисциплины:

-     С упорядоченным обслуживанием:

Заявки обслуживаются в порядке поступления: первый пришел - первым обслуживается (First In First Out, FIFO, или First Come First Served, FCFS),

-     С неупорядоченным обслуживанием:

Заявки обслуживаются в случайном порядке или

-     Со стековым обслуживанием:

Первой из очереди выбирается последняя заявка: последний пришел - первым обслуживается, Last In First Out, LIFO, или Last Come First Served, FCFS).

-     С приоритетным обслуживанием:

Заявки разных типов (приоритетов) образуют как бы несколько очередей, по одной очереди на каждое значение приоритета, и в каждый момент, когда сервер заканчивает обслуживание какой-то заявки, на обслуживание направляется заявка из первой в порядке убывания приоритета непустой очереди.

Приоритет заявки может быть:

·  статическим (не меняющимся с течением времени пребывания в системе);

·  динамическим (может, например, увеличиваться с длительностью ожидания заявки).

 

Для времени ожидания заявки в очереди справедлива формула Хинчина-Полачека:

 

 (0‑1)

где

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

  — среднее время ожидания заявки в очереди,

 σ_s — среднеквадратическое (стандартное) отклонение времени обслуживания в приборе,

 ρ — коэффициент использования прибора

  — средний интервал времени между поступлением заявок,

 c_s — коэффициент вариации времени обслуживания

 

Число заявок, ожидающих обслуживания (среднюю длина очереди), можно найти, умножив  на величину λ:

 

 (0‑2)

что, с учетом равенства

дает

 (0‑3)

 

Формула Хинчина-Полачека используется для оценивания длин очередей при проектировании информационных систем. Она применяется в случае экспоненциального распределения времени поступления при любом распределении времени обслуживания и любой дисциплине управления, лишь бы выбор очередного сообщения для обслуживания не зависел от времени обслуживания.

При проектировании систем встречаются такие ситуации возникновения очередей, когда дисциплина обслуживания выбирается в зависимости от времени обслуживания. Например, в некоторых случаях для первоочередного обслуживания могут выбираться более короткие сообщения с тем, чтобы получить меньшее среднее время обслуживания (среднее время пребывания в заявки системе). При управлении линией связи (каналом Интернет) можно присвоить входным сообщениям более высокий приоритет, чем выходным, поскольку первые короче. В таких случаях уже необходимо использовать не уравнение Хинчина — Поллачека или производные от него, а более сложные уравнения или использовать метод имитационного моделирования.

Особый интерес для практических применений представляют два случая.

1) Время обслуживания постоянно.

При регулярном характере потока рассеяние отсутствует, поэтому среднеквадратическое отклонение , и формулы (0‑1), (0‑2) преобразуются в выражения

 

 (0‑4)

и

 (0‑5)

 

2) Время обслуживания имеет экспоненциальное распределение.

 

В случае экспоненциального распределения, как известно, среднеквадратическое отклонение , поэтому (0‑1), (0‑2) приобретают вид:

 (0‑6)

и

 (0‑7)

 

Большинство значений времени обслуживания в информационных системах лежит где-то между этими двумя случаями. Времена обслуживания, равные постоянной величине, встречаются редко. Даже время доступа к твердому диску непостоянно из-за различного положения массивов с данными на поверхности. Одним из примеров, иллюстрирующих случай постоянного времени обслуживания может служить занятие линии связи для передачи сообщений фиксированной длины.

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

Экспоненциальное распределение времен обслуживания не наихудший случай, с которым приходится иметь дело в действительности. Однако, если времена обслуживания, полученные при расчете очередей, оказываются распределенными хуже, чем времена с экспоненциальным распределением, то это является предостерегающим сигналом для разработчика. Если стандартное отклонение больше среднего значения, то обычно возникает необходимость в коррекции расчетов.

 

Пример:

Пусть имеются шесть типов сообщений со временами обслуживания 15, 20, 25,30, 35, 40 и 300. Число сообщений каждого типа одинаково. Стандартное отклонение указанных времен несколько выше их среднего. Значение последнего времени обслуживания намного больше других. Это приведет к тому, что сообщения будут находиться в очереди значительно дольше, чем, если бы времена обслуживания были одного порядка. В таком случае при проектировании целесообразно принять меры для уменьшения длины очереди. Например, если указанные цифры связаны с длинами сообщений, то, возможно, очень длинные сообщения стоит разделить на части.

Получим количественную оценку системных показателей для первоначального варианта организации информационного обмена и для двух вариантов, в которых длины сообщений передаваемых сообщений выровнены.

Вычислим величины, входящие в формулу для средней длины очереди. Будем считать, средняя продолжительность для всей группы сообщений составляет 600 временных единиц. Тогда

Коэффициент загрузки

 

Математическое ожидание времени обслуживания

 

 

Среднеквадратическое отклонение времени обслуживания

 

 

Коэффициент вариации времени обслуживания

 

 

Подставляя в (0‑1) получим, что средний размер очереди в первоначальном варианте будет равен

 

 

Вычислим теперь этот показатель для случая, когда последнее сообщение разбивается на два сообщения одинаковой длины. Поступая аналогичным образом, будем иметь (очевидно, что значение  остается тем же):

 

 

Разбивая длинное сообщение на три части, получаем для средней длины очереди значение

 

 

Содержание работы.

Подготовка инструментария эксперимента.

Выполняется в соответствии с общими правилами.

Расчет на аналитической модели.

1. В приложении Microsoft Excel подготовьте таблицу следующего вида (показаны левая и правая части таблицы по горизонтали соответственно).

 

 

 

В столбцы левой части таблицы (Аналитическая модель) заносятся:

TΣ: средняя продолжительность цикла поступления пакета сообщений (задается в исходных данных задания)

N: число сообщений в пакете (в исходном варианте N=7)

Ta: средний интервал между приходами сообщениями в потоке сообщений TΣ/N

Vi: длины сообщений в пакете сообщений (для первого варианта расчета задается как исходные данные к заданию) – первая строка, квадраты длин сообщений в пакете сообщений – вторая строка (для расчета значения дисперсии)

M: математическое ожидание длин сообщений

D: дисперсия длин сообщений

r: коэффициент загрузки (M/Ta)

cs^2: квадрат коэффициента вариации  

nw_0: расчитаннная по формуле (0‑1) величина средней длины очереди для длин сообщений Vi

nw_e: расчитаннная по формуле (0‑1) величина средней длины очереди для экспоненциально распределенной длины сообщений со средней длиной (временем обслуживания) равной M

nw_d: расчитаннная по формуле (0‑1) величина средней длины очереди для сообщений одинаковой длины равной M

В столбцы правой части таблицы (Имитационная модель) заносятся результаты, полученные на программной модели.

 

2. В столбцы параметров таблицы (TΣ, N, V1,…V7) запишите исходные данные по своему варианту.

№ варианта соответствует порядковому номеру в списке группы).

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

3. Заполните соответствующие клетки таблицы для расчета показателей аналитической модели СМО. В столбцы с показателями аналитической модели впишите соответствующие формулы.

4. Повторите шаги 2-4 с числом сообщений N=8 и N=9, разбивая последнее сообщение соответственно на два и три сообщения равной длины.

 

Эксперимент на имитационной модели.

1. Проведите запуск программной модели для случая длин сообщений, заданных массивом исходных данных и бесприоритетной дисциплины обслуживания. Для этого установите в нужное значение параметр режима обслуживания и задайте для каждого запуска массивы, описывающие распределение интервалов (все элементы массива частот удобнее задавать равными единице, элементы массива значений задаются значениями V1,…V7). Результат запуска внесите в таблицу.

2. Повторите эксперимент для режима обслуживания с приоритетом коротких сообщений, переустановив в нужное значение параметр режима обслуживания. Результат внесите в таблицу.

3. Повторите эксперимент (шаги 1 и 2) для N=8 и N=9.

4. Проведите запуск программной модели для экспоненциально распределенной длины сообщений со средней длиной (временем обслуживания) равной M и бесприоритетной дисциплины обслуживания. Результат внесите в таблицу.

5. Повторите запуск для приоритетной дисциплины обслуживания. Результат внесите в таблицу.

6. Проведите запуск программной модели для экспоненциально распределенной длины сообщений со средней длиной (временем обслуживания) равной M и бесприоритетной дисциплины обслуживания. Результат внесите в таблицу.

7. Проведите запуск программной модели для случая сообщений одинаковой длины равной M и бесприоритетной дисциплины обслуживания. Результат внесите в таблицу.

8. Повторите запуск для приоритетной дисциплины обслуживания. Результат внесите в таблицу.

 

Анализ результатов.

Сравните и проанализируйте результаты, полученные теоретическим и экспериментальным способами.

 

Отчет по работе.

Отчет по работе должен включать:

-   исходные данные,

-   результаты расчетов,

-   результаты экспериментов с программной моделью сведенные в таблицу со структурой, описанной выше.

 

 

Контрольные вопросы:

1)Дайте краткое описание модели СМО с неограниченной очередью.

2)Какими показателями характеризуется функционирование СМО с неограниченной очередью?

3)Что такое дисциплина обслуживания? Назовите примеры наиболее известных дисциплин.

4)Что позволяет определить формула Хинчина-Полачека? Для каких случаев справедлива формула?

5)Каким образом можно определить показатели СМО для случаев, предусматривающих использование приоритетных дисциплин обслуживания?

6)Какие распределения времени обслуживания представляют наибольший интерес для практики? Опишите эти случаи.

7)От каких факторов зависят в основном значения показателей СМО с неограниченной очередью? Как можно влиять на эти факторы для улучшения показателей?

 

Задачи.

1)Сборочный участок производит в один час в среднем 90 блоков. На этом участке работает контролер, который проверяет все собранные блоки, средняя продолжительность контрольных операций составляет в среднем 1,25 минут. Определить среднее число изделий, ожидающих внимания контролера, и среднее время ожидания изделиями в очереди на проверку.

2)Железнодорожную станцию обслуживает касса с одним окном. В летние выходные дни интенсивность потока пассажиров к кассе составляет 0.45 человек в минуту. Кассир затрачивает на облуживания пассажира в среднем 2 мин. Определить среднее число пассажиров у кассы и среднее время, затрачиваемое пассажиром на приобретение билета.

3)Порт имеет один грузовой причал для разгрузки судов. Интенсивность потока судов составляет 0.5 судов в сутки. Разгрузка судна требует в среднем 1,5 суток. Предполагается, что суда могут ждать в очереди неограниченно долго. Найти показатели эффективности работы причала.

4)К базе данных сервера продажи билетов поступает 10 запросов в секунду. Среднее время обработки каждого запроса составляет 1 секунду. Запрос, поступивший в момент обработки одного из ранее поступивших запросов, становится в очередь. Определить среднюю длину очереди и среднее время, которое проведут запросы до обслуживания.

 

Варианты работ