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

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

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

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

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

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

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

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

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

    По  теме:

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

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

                                        Билай Н. А.

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

                                              Соловей Д. Е. 
                   
                   
                   

Воронеж 2011

Содержание:

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

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

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

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

  1. Заключение.
  2. Приложения

    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 заявок в очереди (вероятность  этого ), то в этом случае заявка не становится в очередь (и не обслуживается), поэтому время ожидания равно нулю. Среднее время ожидания будет равно:

stify">если  подставить сюда выражения для вероятностей (4), получим:

(10)

Здесь использованы соотношения (7), (8) (производная  геометрической прогрессии), а также из (4). Если сравнить это выражение с (8), можно заметить, что среднее время ожидания равно среднему числу заявок в очереди, поделенному на интенсивность потока заявок.

(11)

Среднее время пребывания заявки в системе. Обозначим — время пребывания заявки в СМО, которое складывается из среднего времени ожидания в очереди и среднего времени обслуживания . Если загрузка системы составляет 100 %, то очевидно, , в противном же случае

(12)

Отсюда

                                                    (13)

 

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

Формулировка  задачи:

Построить модель СМО с ожиданием «клиент  – очередь - сервер», исследовать  её характеристики и поведение.

Описание  системы:

Имеется одноканальная СМО с ожиданием, содержащая один однородный поток заявок. То есть поступившая на обслуживание заявка становится в очередь: если очередь свободна, то заявка отправляется на обработку, если очередь уже занята другими заявками, то она становится в очередь на соответствующее место в данном потоке обслуживания. 

Исходные данные:

1. Интенсивность  поступления заявок (λ = 110);

2. Интенсивность  обработки заявок (µ = 40);

3. Количество  мест в очереди (m = 80);

Требуется найти:

    1. Среднее количество заявок в очереди;

    2. Вероятность отказа;

    3. Среднее время ожидания обработки запроса;

    4. Относительную и абсолютную пропускную способность;

    5.  Среднее время ожидания и обработки  заявки. 
     
     

    Реализация  математического  аппарата.

    Исходя  из формулы (1):

     где  ;

    Т. е.

    Предельные  вероятности будут иметь следующий  вид:

    .

    .

    .

     

 справедливо только если p < 1, а если эти значения равны между собой, то мы получим неопределенность: 0/0 . Поэтому, вспомнив, что сумма геометрической прогрессии со знаменателем = 1 равна m + 2, будем иметь формулу:

;     т. е.   

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

,  имеем:

Исходя  из формулы (6), относительная пропускная способность:

Q = 1 - Pотк = 0.3636

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

A = λ*Q = 110 * 0.3636 = 39.996 = 40;

Далее сопоставляя уже имеющиеся данные и соответствующие формулы (11, 12, 13), определяем другие показатели. В итоге получаем:

Время ожидания заявки - 5,18897759396253E-36

Время обслуживания заявки - 0,00909090909090909

Время нахождения заявки в СМО - 0,00909090909090909 
 
 
 
 
 
 
 
 
 

Ниже приведена  блок-схема алгоритма работы СМО:

     

     

       

     

     

     

       Нет

     

     

     

     

       Да

     

     

Рис 2. Блок-схема  алгоритма программы 
 
 
 
 

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

Модель  СМО с ожиданием в данной курсовой работе описывается в программе, выполненной на  языке программирования C#.

Составлена  программа, в которой имеются  три основных блока: блок ввода исходных данных(textbox 1, 2, 3), блок вывода вычисленных данных(richTextbox 1, 2), блок вывода графика параметров (Console ZedGraph1).

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

Листинг и программы представлен в приложении.      

 

Алгоритм  работы программы:

      1.Ввод  данных: число поступивших заявок  в единицу времени, число обработанных заявок в единицу времени, длина очереди.

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

      4. Программа выводит результаты  на экран.

      5. Программа строит графики, по данным, полученным выше. 

Рис. 3. Графики программы. 
 

    Рис. 4. Работа программы СМО 
     
     

5. Заключение 

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

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

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

6. Приложения.

Приложение 1. Листинг  программы:

using System;//определение пространства имен

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

using ZedGraph;//подключение библиотеки zedgraph

namespace WindowsFormsApplication1

{

public partial class Form1 : Form

    {

        public Form1()

        {

            InitializeComponent();//инициализация компонентов формы

        }

public void button1_Click(object sender, EventArgs e)

        {

            double la = Convert.ToDouble(textBox1.Text);//ввод переменной лямбда (интенсивность поступления заявок)

            double mu = Convert.ToDouble(textBox2.Text);//ввод переменной мю (интенсивность обработки заявок)

            double m = Convert.ToDouble(textBox3.Text);//ввод переменной м (длинна очереди)

            double p = la / mu;//число заявок, обработанных в единицу времени

            double step = Math.Pow(p, m);

            double step1 = Math.Pow(p, m + 1);

            double step2 = Math.Pow(p, m + 2);

            double p0 = (1 - p) / (1 - step2);//предельная вероятность p0

            double Potk = (step1 * (1 - p)) / (1 - step2);//вероятность отказа

         double q = 1 - Potk;//относительная пропускная способность

            double A = q * la;//абсолютная пропускная способность

            double r1 = p * p * (1 - (m + 1 - m * p));