Лабораторная работа 4 - СМО. Лабораторная работа 4 сравнение одноканальных смо с различными входными потоками и потоками обслуживания
 Скачать 141.13 Kb.
|
|
Лабораторная работа №4 СРАВНЕНИЕ ОДНОКАНАЛЬНЫХ СМО С РАЗЛИЧНЫМИ ВХОДНЫМИ ПОТОКАМИ И ПОТОКАМИ ОБСЛУЖИВАНИЯ Цель работы – изучение влияния типов входных потоков и по- токов обслуживания на характеристики одноканальных СМО 1. Теоретическая часть 1.1. Одноканальные СМО Во многих случаях входящие потоки заявок и потоки обслужи- вания реальных систем хорошо описываются простейшими потока- ми. Однако для многих систем потоки могут отличаться от простей- ших. Системы с потоками, отличными от простейших, могут быть исследованы специальными математическими методами или мето- дом имитационного моделирования. В работе рассматривается одноканальная система с очередью неограниченной длины, имеющая различные типы входного потока заявок и потока обслуживания. Несмотря на простоту данной моде- ли, ей хорошо описываются многие реальные технические и органи- зационные системы, в том числе и в вычислительной технике. При- мерами таких систем являются компьютерная сеть с топологией “об- щая шина” и прямое соединение двух компьютеров каналом связи. В зависимости от стохастических характеристик потока он мо- жет обладать той или иной степенью последействия, т.е. степенью влияния состояний системы в прошлом на состояния системы в бу- дущем. В некотором смысле двумя крайними случаями здесь яв- ляются регулярный и простейший потоки. Регулярный поток харак- теризуется максимальным последействием, т.к. момент возникнове- ния очередного события в потоке полностью определяется моментом возникновения предыдущего события. Простейший поток характери- зуется отсутствием последействия, и момент возникновения очеред- ного события в потоке не зависит от моментов возникновения пре- дыдущих событий. Можно показать, что для некоторых характери- стик одноканальных СМО (например, средней длины очереди и среднего времени ожидания) характеристики системы с регулярным потоком обслуживания имеют значения вдвое меньше, чем для си- стемы с простейшим потоком обслуживания. Значения характери- стик систем с другими потоками обслуживания будут лежать между соответствующими значениями характеристик СМО с регулярным и простейшим потоками обслуживания. 1 1.2. Расчет характеристик системы “M\M\1\” Если поток обслуживаний и входящий поток в одноканальной СМО являются простейшими, то такая система обозначается “M\M\1\” (рис. 1). Рис. 1. Система “M\M\1\” Характеристики данной системы легко находятся аналитиче- ски. Она описывается Марковским процессом с бесконечным числом дискретных состояний и непрерывным временем, граф состояний ко- торого приведен на рис. 2. λ λ λ λ λ µ µ µ µ µ Рис. 2. Граф состояний для системы “M\M\1\” Здесь λ – интенсивность входного потока заявок, µ – интен- сивность потока обслуживаний. Состояния системы пронумерованы по числу заявок, находящихся в системе: 0 S – канал обслуживания свободен, очередь пуста, 1 S – канал обслуживания занят, очередь пуста, 2 S – канал обслуживания занят, в очереди одна заявка, … k S – канал обслуживания занят, в очереди 1 − k заявка, … По графу состояний можно составить следующую систему уравнений Колмогорова для установившегося режима: 2 K=1 λ µ S S 1 S 2 S к … … ( ) ( ) ( ) , : , : , : , : 1 1 3 1 2 2 2 0 1 1 1 0 0 + − + = + + = + + = + = k k k k P P P S P P P S P P P S P P S µ λ µ λ µ λ µ λ µ λ µ λ µ λ Здесь i P – вероятности пребывания системы в состоянии i S Обозначим µ λ ρ = . Тогда все i P можно выразить через 0 P : , , 1 , 0 0 2 0 0 0 2 0 1 2 0 0 1 P P P P P P P P P P P P K K ρ ρ ρ ρ ρ µ λ µ λ ρ µ λ = = − + = − + = = = Учитывая, что 1 0 = ∑ ∞ = i i P , можно найти 0 P : ( ) ∑ ∞ = − = + + + + = + + + − = − = 1 3 2 3 2 0 0 1 1 1 1 1 i i P P P ρ ρ ρ ρ ρ ρ ρ Ряд в последней формуле сходится при 1 < ρ . Зная вероятности состояний, можно найти такие характеристики СМО, как средняя длина очереди ν , среднее время ожидания ож t , среднее время пре- бывания заявки в системе пр t и среднее число заявок в системе m : ( ) ( ) ( ) ( ) ρ ρ ρ ρ ρ ρ ρ ρ ρ − = − − = + + + − = + + + = = ∑ ∞ = 1 1 1 3 2 1 3 2 2 3 2 3 2 1 1 P P P k P m k k ( ) ( ) ( ) ( ) ρ ρ ρ ρ ρ ρ ρ ρ ρ ν − = − − = + + − = + + = − = ∑ ∞ = 1 1 1 2 1 2 ) 1 ( 2 2 2 2 3 2 2 P P k P k k (1) Два оставшихся параметра можно найти по формулам Литтла: ( ) ( ) ρ λ ρ λ ρ λ ρ λ ν − = = − = = 1 , 1 2 m t t пр ож (2) 3 1.3. Имитационное моделирование СМО Язык GPSS содержит широкие средства для моделирования стандартных СМО. Блоки для генерации потоков заявок, моделиро- вания очередей и устройств уже были рассмотрены ранее. В GPSS World включен набор подпрограмм для генерации случайных чисел, распределенных в соответствии с типовыми распределениями (табл. 1). В каждой из этих подпрограмм первым параметром является но- мер потока случайных чисел RNj, представляющий собой целое по- ложительное число. Это номер потока равномерно распределенных от 0 до 1 случайных чисел, на основе которых генерируются случай- ные числа с другими распределениями. Рекомендуется для каждого потока событий (входящего потока заявок или потока обслуживаний) использовать свой собственный поток случайных чисел. Например, для генерации простейшего потока с интенсивно- стью lambda с использованием первого потока случайных чисел нуж- но использовать следующий блок: GENERATE (Exponential(1, 0, 1/lambda)) 2. Порядок выполнения работы 1. Изучите теоретический материал. 2. Выполните расчет одноканальной СМО с очередью при простейшем входном потоке и простейшем потоке обслу- живания. Интенсивность потока обслуживания выберите согласно таблице: Номер варианта Интенсивность обслуживания, µ 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 3,5 10 5,5 4 Табл. 1. Функции GPSS для генерации случайных чисел с типовыми распределениями № п/п Тип распределения Плотность вероятности, математическое ожи- дание, дисперсия Функция GPSS 1 Равномерное ( ) ∉ ∈ − = ] , [ 0 ] , [ 1 b a x b a x a b x f , 2 b a M + = , ( ) 12 2 a b D − = UNIFORM(RNj, a,b) где a – левая граница интервала, b – правая граница интервала 3 Показательное (Экспо- ненциальное) ( ) ( ) s m x e s x f − − = 1 , m x ≥ , s m M + = , 2 s D = EXPONENTIAL(RNj, m, s) где m – смещение распределе- ния, s – масштабшый параметр. 4 Нормальное (Гауссово) ( ) ( ) 2 2 2 2 1 s m x e s x f − − = π , m M = , 2 s D = NORMAL(RNj, m, s) где m и s – параметры распреде- ления 5 Дискретное равномерное ( ) { } max min min x min max x p , , 1 , , 1 1 + ∈ + − = , 2 max min M + = , ( ) 12 1 2 − − = min max D DUNIFORM(RNj, min, max) где min и max – соответственно минимальное и максимальное значение 5 Постройте графики зависимости времени ожидания в очере- ди, среднего времени пребывания заявки в системе, средней длины очереди и среднего числа заявок в системе от интенсивности входно- го потока λ . Диапазон изменения λ примите от 0 до µ 3. Разработайте программы на языке GPSS для следующих ва- риантов СМО (5 программ): Номер вари- анта СМО Распределение интерва- ла времени между двумя поступившими на вход заявками Распределение времени обслуживания заявки 1 Экспоненциальное Постоянная задержка 2 Экспоненциальное Экспоненциальное 3 Экспоненциальное Равномерное 4 Экспоненциальное Эрланга 2 порядка 5 Экспоненциальное Эрланга 3 порядка При разработке программ выберите постоянную задержку для времени обслуживания равной µ 1 , а интенсивность экспоненци- ального распределения для времени обслуживания равной µ соглас- но п. 3. Равномерное распределение времени обслуживания выбери- те равным % 25 1 ± µ . Случайная величина с распределением Эрланга порядка k получается сложением k экспоненциально распределен- ных величин с интенсивностью µ k Параметры распределения интервала между заявками во вход- ном потоке выбираются аналогично с учетом того, что средняя ве- личина задержки будет варьироваться от 0 до µ / 1 4. Постройте графики зависимости средней длины очереди от среднего значения величины коэффициента загрузки ρ в одних и тех же координатах для всех пяти графиков. При построении каждого графика определите значения средней длины очереди для ρ , равного 0,1; 0,3; 0,5; 0,7; 0,9. Для каждой точки выполните три прогона моделирования, а в качестве конечного результата возьмите среднее значение по трем прогонам. Сравните полученные графики. 5. Сформулируйте выводы по работе и ответьте на контроль- ные вопросы. 3. Содержание отчета 1. Название работы. 2. Цель работы. 6 3. Основные теоретические сведения. 4. Расчет СМО для случая простейших потоков. 5. Текст типовой модели СМО на языке GPSS. 6. Графики времени ожидания в очереди и длины очереди от средней интенсивности входящего потока для различных СМО. 7. Выводы по работе. 4. Контрольные вопросы 1. Как можно оценить значения характеристик СМО с произ- вольным потоком обслуживания? 2. Система “M\M\1”. Расчет характеристик. 3. Основные блоки GPSS, предназначенные для моделирова- ния СМО. 4. Функции GPSS для моделирования случайных чисел, рас- пределенных в соответствии с типовыми распределениями. 5. Как тип входного потока влияет на характеристики СМО? 6. Как тип потока обслуживаний влияет на характеристики СМО? Библиографический список 1. Томашевский В., Жданова Е. Имитационное моделирование в среде GPSS. – М.: Бестселлер, 2003. – 416 с. 7 |