СМО с ожиданием

Министерство  образования и науки Российской Федерации

Государственное образовательное учреждение

высшего профессионального образования

Воронежская государственная лесотехническая  академия

Кафедра вычислительной техники 

Курсовая  работа

по  дисциплине

«Методы решения прикладных задач в информационных системах»

По  теме:

«СМО  с ожиданием» 
 
 
 

                                                          Выполнила: студ. 1241 гр.

                      Билай Н. А.

            Проверил: доцент 

                            Соловей Д. Е. 
 
 
 

Воронеж 2011

Содержание:

   Введение: СМО и их актуальность.

1. Обзор типов СМО.
2. СМО с ожиданием: математическая модель и алгоритм работы.

3. Постановка задачи, математическая модель задания, алгоритм выполнения задания.

4. Программная  реализация.

5. Заключение.
6. Приложения

6. 1. Листинг  программы

    7. Список  используемых источников.

Введение: СМО и их актуальность

В последнее  время в нашей жизни очень широко используются системы массового обслуживания (СМО).   Это объясняется тем, что СМО прочно входят в огромный спектр отраслей производства и человеческой деятельности.

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

Математический  аппарат, структура СМО, принципы её действия – рассматриваются в  этой курсовой работе в общих положениях, а так же приводится пример реализации конкретной СМО.

 

1.Обзор типов СМО.

Система массового обслуживания (СМО) - система, которая производит обслуживание поступающих в неё требований. Прибор – устройство, обслуживающее требования. Классическая СМО содержит от одного до бесконечного числа приборов. В зависимости от наличия возможности ожидания поступающими требованиями начала обслуживания СМО подразделяются на:

1. системы с потерями, в которых требования, не нашедшие в момент поступления ни одного свободного прибора, теряются;

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

3. системы с накопителем конечной ёмкости (ожиданием и ограничениями), в которых длина очереди не может превышать ёмкости накопителя. В этом случае, требование, поступающее в переполненную СМО (отсутствуют свободные места для ожидания), теряется.

Выбор требования из очереди на обслуживание производится с помощью так называемой дисциплины обслуживания. Их примерами являются FCFS/FIFO (пришедший первым обслуживается первым), LCFS/LIFO (пришедший последним обслуживается первым), RANDOM (случайный выбор). В системах с ожиданием накопитель может иметь сложную структуру.

Основные  понятия СМО

Требование (заявка) — запрос на обслуживание.

Входящий  поток требований — совокупность требований, поступающих в СМО.

Время обслуживания — период времени, в течение которого обслуживается требование.

Математическая  модель СМО — это совокупность математических выражений, описывающих входящий поток требований, процесс -обслуживания и их взаимосвязь

СМО с ожиданием классифицируются следующим образом:

· Одноканальная СМО с ожиданием

· Многоканальная СМО с ожиданием:

· СМО с ограниченной длинной очереди – число мест в очереди строго определенное, имеется несколько обслуживающих приборов.

· Системы с неограниченной длиной очереди – очередь может быть сколь угодно длинной, вплоть до бесконечности, содержит несколько обслуживающих приборов.

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

В данной курсовой работе внимание уделяется первому из выше перечисленных типов СМО. В теоретической части этот тип раскрыт более полно. 
 
 
 
 

2. Одноканальная СМО с ожиданием

Ниже  рассмотрена простая СМО с  ожиданием — одноканальная система (n - 1), в которую поступает поток заявок с интенсивностью . Интенсивность обслуживания равна (т. е. в среднем непрерывно занятый канал будет выдавать обслуженных заявок в единицу времени). Заявка, поступившая в момент полной занятости канала, становится в очередь и ожидает обслуживания.

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

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

—канал свободен;

—канал занят, очереди нет;

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

—канал занят, k - 1 заявок стоят в очереди;

— канал занят, т заявок стоят в очереди.

Граф  случайных потоков (ГСП) показан на рис. 1. Все интенсивности потоков событий, переводящих в систему по стрелкам слева направо, равны - , а справа налево — . Действительно, по стрелкам слева направо систему переводит поток заявок (как только придет заявка, система переходит в следующее состояние), справа же налево — поток «освобождений» занятого канала, имеющий интенсивность (как только будет обслужена очередная заявка, канал либо освободится, либо уменьшится число заявок в очереди).

Рис. 1. Одноканальная СМО с ожиданием

Для подобных СМО используются следующие выражения (см. формулу 1):

(1)

или с  заменой: :

(2)

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

(3)

в связи  с этим предельные вероятности принимают вид:

(4)

Выражение (3) справедливо только при < 1 (при = 1 - она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m + 2, и в этом случае:

Определим характеристики СМО: вероятность отказа , относительную

пропускную  способность q, абсолютную пропускную способность А, среднюю длину  очереди , среднее число заявок, связанных с системой , среднее время ожидания в очереди , среднее время пребывания заявки в СМО

Вероятность отказа. Очевидно, что заявка получает отказ только в случае, когда канал занят и все m мест в очереди тоже:

(5)

Относительная пропускная способность:

(6)

Абсолютная  пропускная способность:

Средняя длина очереди.

Найдем  среднее число заявок, находящихся в очереди. Это значение есть - математическое ожидание дискретной случайной величины R — числа заявок, находящихся в очереди:

С вероятностью - в очереди стоит одна заявка, с вероятностью — две заявки, с вероятностью - в очереди стоят k - 1 заявок, и т. д. Отсюда имеем:

(7)

Поскольку , сумму в (7) можно трактовать как производную по от суммы геометрической прогрессии:

Подставляя  данное выражение в (7) и используя из (4), окончательно получаем:

(8)

Среднее число заявок, находящихся  в системе. Получим далее формулу для среднего числа заявок, связанных с системой (как стоящих в очереди, так и находящихся на обслуживании). Поскольку , где_ — среднее число заявок, находящихся под обслуживанием, а k известно, то остается определить . Поскольку канал один, число обслуживаемых заявок может равняться 0 (с вероятностью ) или 1 (с вероятностью 1 - ), откуда:

и среднее число заявок, связанных с СМО:

(9)

Среднее время ожидания заявки в очереди.

Если заявка приходит в систему в какой-то момент времени, то с вероятностью канал обслуживания не будет занят, и ей не придется стоять в очереди (время ожидания равно нулю). С вероятностью заявка придет в систему во время обслуживания какой-то другой заявки. Перед ней не будет очереди, и она станет дожидаться начала своего обслуживания в течение времени (среднее время обслуживания одной заявки). С вероятностью - в очереди перед рассматриваемой заявкой будет стоять еще одна. В среднем, её время ожидания - , и т. д.

Если  же k = m + 1, т. е. когда вновь приходящая заявка застает канал обслуживания занятым и m заявок в очереди (вероятность  этого ), то в этом случае заявка не становится в очередь (и не обслуживается), поэтому время ожидания равно нулю. Среднее время ожидания будет равно: