!!! Прочти содержание лабораторной работы ЛАБОРАТОРНАЯ РАБОТА №2 ИССЛЕДОВАНИЕ СИСТЕМ…
- User
!!! Прочти содержание лабораторной работы ЛАБОРАТОРНАЯ РАБОТА №2 ИССЛЕДОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С ОТКАЗАМИ Составители: д.т.н., проф. И.С. Грузман; магистрант Е.В. Андрес Цель работы. Изучить одноканальные и многоканальные системы массового обслуживания (СМО) с отказами. Выполнить анализ основных характеристик СМО. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ2 С возникновением телекоммуникационных систем (ТКС) появилась необходимость в специальных математических методах анализа и прогнозирования качества их функционирования. Основу всех процессов в ТКС составляет обработка или передача (обслуживание) какого-то потока сообщений (заявок), поступающих в какие-то случайные моменты времени. Обработка или передача каждого сообщения (обслуживание заявки) продолжается какое-то случайное время. Часть ТКС, участвующая в процессе обслуживания заявки так, что одновременно с ним никакое другое сообщение не может обрабатываться этой частью, называется обслуживающим каналом. Случайный характер потока заявок и времен обслуживания приводит к тому, что в какие-то периоды времени на входе ТКС скапливается излишне большое число заявок, в другие же периоды ТКС будет работать с недогрузкой или вообще простаивать. Поэтом при решении задач анализа и прогнозирования качества работы ТКС необходимо считаться с тем, что случайность является определяющим фактором для процессов, протекающих в ТКС. Математические модели ТКС строятся на основе теории систем массового обслуживания (СМО). Предмет теории СМО – построение математических моделей, связывающих заданные условия работы СМО (число каналов, их производительность, правила работы, характер потока заявок) с интересующими нас характеристиками – показателями эффективности СМО, описывающими ее способность справляться с потоком заявок. Если СМО содержит ровно один канал, то в каждый момент времени она способна обслуживать не более чем одну заявку. Если на такую систему, занятую обслуживанием, в течение интервала времени обслуживания поступит еще одна заявка, то она не сможет быть обслужена. Это
2 При написании данного раздела были использованы источники [2.1–2.4] простейший случай ресурсного конфликта – заявки, поступающие друг за другом, не могут быть обслужены немедленно при поступлении (в реальном масштабе времени) из-за того, что канал не успевает обслужить заявки за время между их поступлениями. Частота возникновения ресурсных конфликтов меньше, если СМО будет содержать не один, а несколько каналов, включенных так, чтобы поступающие заявки распределялись бы для обслуживания на любой свободный из них в данный момент. Однако, очевидно, что если время обработки не бесконечно мало по сравнению с интервалом между поступлением заявок, то и в СМО с несколькими каналами также может возникнуть ресурсный конфликт – вновь поступившая заявка не сможет получить немедленного обслуживания, так как все каналы окажутся занятыми в данный момент. В этом случае система может просто проигнорировать поступившую заявку. Она будет отброшена, а СМО будет считаться заблокированной. Вероятность такого события является важной характеристикой системы. Чтобы ни одна заявка не была потеряна в результате ресурсного конфликта, в СМО может быть предусмотрен специальный буфер памяти, в который будут помещаться заявки, которые не могут быть обслужены немедленно при поступлении из-за занятости всех каналов. В этом случае говорят, что СМО является системой с очередями. В очереди может оказаться не одна, а несколько заявок, если число поступающих заявок за некоторый интервал времени превысит число освободившихся за это время каналов. Если очередь не будет бесконечно нарастать, все заявки рано или поздно будут обслужены, однако время их пребывания в очереди будет разным и может рассматриваться как случайная величина. Распределение этой случайной величины также является важнейшей характеристикой системы обслуживания. Часто для оценки качества используется только ее среднее значение – среднее время ожидания обслуживания. Таким образом, недостаточность ресурсов в телекоммуникационной системе может приводить либо к потерям поступающих на обработку или передачу заявок, либо к задержке их обслуживания. Простейшая модель потока заявок Поступающие на вход СМО заявки образуют поток дискретных событий, полностью определяемый множеством моментов времени их поступления
1 2 n t {t ,t ,...,t ,...} (см.рис. 2.1). Для детерминированного потока моменты времени задаются таблицей или формулой. Детерминированный поток событий называется регулярным, если события следуют одно за другим через строго определенные промежутки времени. Такой поток сравнительно редко встречается в реальных системах. На практике поток событий случайный и значения моментов поступления заявок есть значения случайной величины.
Рис. 2.1. В общем случае случайные потоки можно классифицировать по наличию или отсутствию трех основных свойств: стационарности, последействия и ординарности.
- Поток событий называется стационарным, если вероятность попадания того или иного числа событий на участок времени длиной (см. рис.2.1) зависит только от длины участка и не зависит от того, где именно расположен этот участок. Условию стационарности удовлетворяет поток заявок, вероятностные характеристики которого не зависят от времени. В частности, для стационарного потока характерна постоянная плотность (среднее число заявок в единицу времени). На практике часто встречаются потоки заявок, которые (по крайней мере, на ограниченном отрезке времени) могут рассматриваться как стационарные. Например, поток вызовов на городской телефонной станции на участке времени от 9 до 10 часов может считаться стационарным. Тот же поток в течение целых суток уже не может считаться стационарным (ночью плотность вызовов значительно меньше, чем днем).
- Поток событий называется потоком без последействия, если для любых неперекрывающихся участков времени число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие. Условие отсутствия последействия означает, что заявки поступают в систему независимо друг от друга. Например, поток пассажиров, входящих на станцию метро, можно считать потоком без последействия потому, что причины, обусловившие приход отдельного пассажира именно в тот, а не другой момент, как правило, не связаны с аналогичными причинами для других пассажиров. Однако условие отсутствия последействия может быть легко нарушено за счет появления такой зависимости. Например, поток пассажиров, покидающих станцию метро, уже не может считаться потоком без последействия, так как моменты выхода пассажиров, прибывших одним и тем же поездом, зависимы между собой.
- Поток событий называется ординарным, если вероятность попадания на элементарный участок двух или более событий пренебрежимо мала по сравнению с вероятностью попадания одного события. Условие ординарности означает, что заявки приходят поодиночке, а не парами, тройками и т. д. Если поток событий обладает всеми тремя свойствами (т.е. стационарен, ординарен и не имеет последействия), то он называется простейшим (или стационарным пуассоновским) потоком. Для пуассоновского потока интервал времени между соседними событиями i i 1 t t t имеет показательное распределение с плотностью 1 w( t ) exp( t ) , t 0, (2.1) где – интенсивность потока (среднее количество поступивших заявок в единицу времени). Для случайной величины t , имеющей показательное распределение (2.1), математическое ожидание mt и среднее квадратическое отклонение t равны: 1 m t t . Далее будем полагать, что время обслуживания заявки также подчиняется экспоненциальному распределению 1 w( ) exp( ) , t 0, где – интенсивность обслуживания, т.е. среднее число обслуженных заявок в единицу времени. Одноканальные и многоканальные СМО с отказом Исходные данные. Многоканальная СМО состоит из n каналов. На нее поступает пуассоновский поток заявок с интенсивностью . Поток обслуживаний в каждом канале имеет интенсивность µ. Такая система может находиться в одном из n 1 состояний: 0 S – все каналы свободны; 1 S – занят ровно один канал, остальные свободны; 2 S – заняты ровно два канала, остальные свободны; … n S – заняты все n каналов. Многоканальная СМО с отказом наилучшим образом имитирует работу коммутатора в сетях передачи данных. Коммутатор имеет несколько параллельно работающих серверов, обрабатывающих и направляющих пакеты по разным адресам. Если все серверы заняты обработкой пакетов, то очередной пакет получает отказ в обслуживании и пересылается на другой коммутатор или пропадает. Частным случаем многоканальной СМО с отказом является одноканальная СМО с отказом ( n 1 ). В такой СМО может содержаться только одна заявка в канале, которая обслуживается, либо ни одной заявки. Простейший пример такой модели – одноканальная телефонная линия, когда множество пользователей пытаются дозвониться до одного и того же абонента. При занятости абонента получается отказ. Основные характеристики СМО с отказом
- Среднее время обслуживания одной заявки в канале 1 обс t . (2.2)
- Приведенная интенсивность потока заявок (2.3) показывает среднее число заявок, приходящееся на среднее время обслуживания одной заявки.
- Вероятность того, что все каналы свободны, т.е. вероятность того, что в системе нет ни одной заявки: 1 0 0 n j j p j ! . (2.4) По сути, вероятность 0 p равна доле времени простоя каналов.
- Вероятность того, что ровно k каналов заняты обслуживанием заявок 0 k k p p k ! . (2.5)
- Вероятность того, что пришедшая заявка получит отказ (не будет обслужена). Для этого нужно, чтобы все n каналов были заняты, значит 0 n P p p отк n n! . (2.6)
- Относительная пропускная способность СМО – вероятность того, что заявка будет обслужена (отношение среднего числа заявок, обслуживаемых системой в единицу времени, к среднему числу поступающих за это время заявок) 0 1 1 n Q P P p обс отк n ! . (2.7)
- Абсолютная пропускная способность СМО – среднее число заявок, которое может обслужить система за единицу времени (интенсивность выходящего потока обслуженных заявок) 0 1 n A Q p n! . (2.8)
- Среднее число занятых каналов. Поскольку абсолютная пропускная способность – это интенсивность потока обслуженных заявок, а каждый занятый канал в единицу времени обслуживает в среднем заявок, то среднее число занятых каналов равно A k . (2.9) Из формул (2.7) и (2.8) следует, что относительная пропускная способность Q и абсолютная пропускная способность A зависят не только от числа каналов n и среднего времени обслуживания одной заявки в канале 1 obs t , но и от интенсивности потока заявок . Если поток заявок является регулярным, то система лучше справляется с их обслуживанием. Если же поток заявок нерегулярный и образует местные сгущения или разрежения, то работа системы затрудняется: на одних участках времени возникают простои, а на других наблюдается перегрузка системы, когда некоторые заявки получают отказ. Поэтому различают номинальную и фактическую пропускную способность системы. Номинальная пропускная способность зависит только от числа каналов и работоспособности каждого из них. Если каждая заявка обслуживается ровно obs t , и заявки следовали бы одна за другой без перерыва, то номинальная пропускная способность системы ном обс n A n t . Фактическая пропускная способность равна абсолютной пропускной способности A . Фактическая пропускная способность системы всегда ниже номинальной. Например, для одноканальной системы с отказами отношение номинальной пропускной способности к фактической равно: 1 A ном A . ДОМАШНЕЕ ЗАДАНИЕ
- В соответствии с вариантом, заданным преподавателем (табл.2.1.), рассчитайте следующие характеристики одноканальной и многоканальной СМО:
- абсолютная пропускная способность;
- относительная пропускная способность;
- вероятность отказа;
- долю времени простоя каналов;
- среднее число занятых каналов.
- Рассчитайте необходимое время наблюдения набл N T , где объем выборки N вычисляется по формуле 1 отк отк P P N , 0 03 . – относительная точность оценки вероятности отказа P отк многоканальной СМО. ЛАБОРАТОРНОЕ ЗАДАНИЕ
- Запустите GUI приложение для исследования СМО. Для этого:
- запустите Matlab;
- в окне Current Folder задайте путь к папке, в которой лежит GUI приложение;
- в окне Command Window наберите команду – laboratornaya_CMO и нажмите ―Enter‖.
- Введите заданные в домашнем задании параметры. Наблюдайте графики поступивших заявок (точки розового цвета), заявок, получивших отказ (точки красного цвета) и графики занятости каналов.
- Измерьте число поступивших заявок Nпост , число обслуженных заявок Nобс , времена одновременной работы каналов Tri .
- По результатам измерений найдите оценки следующих характеристик СМО:
- вероятность отказа пост обс отк обс N N P N ; (2.10)
- относительную пропускную способность обс пост N Q N ; (2.11)
- абсолютную пропускную способность обс набл N A T ; (2.12)
- долю времени простоя СМО 1 0 1 n i i набл Tr p T ; (2.13)
- среднее число занятых каналов 1 n i i набл Tr k i T . (2.14)
- Сравните полученные оценки характеристик с рассчитанными в домашнем задании.
- Постройте и сравните следующие зависимости:
- относительной пропускной способности;
- средней длительности интервала простоя каналов;
- вероятности того, что все каналы заняты; от интенсивности нагрузки ρ для одноканальной и многоканальной СМО, варьируя количество обслуженных заявок в диапазоне 0 2. ,..., .
!!! Ответь на контрольные вопросы:
- Каковы основные характеристики потока заявок?
- Что характеризует параметр в экспоненциальном законе распределения?
- Что характеризует параметр в экспоненциальном законе распределения?
- Что такое простейший поток?
- Приведите основные характеристики пуассоновского потока.
- Каким образом расставляются заявки в каналах?
- Какому закону подчиняется время обслуживания заявки в канале?
- Какими бывают виды СМО по способу обслуживания заявок?
- Назовите основные характеристики структуры СМО.
- Какие основные характеристики СМО с отказом?
- Чем отличается номинальная пропускная способность от фактической?
- Докажите корректность оценок характеристик СМО (2.10)…(2.14), вычисленных по экспериментальным данным.
- Assistant
1. Каковы основные характеристики потока заявок?
Основные характеристики потока заявок:
- Интенсивность потока (λ): среднее число заявок, поступающих в систему за единицу времени.
- Распределение интервалов между поступлениями заявок: статистическое распределение времен между последовательными прибывающими заявками (например, экспоненциальное распределение для пуассоновского потока).
- Стационарность: статистические характеристики потока не зависят от времени.
- Отсутствие последействия (марковское свойство): поступление каждой заявки независимо от предыдущих.
- Ординарность: в бесконечно малом интервале времени вероятность поступления более одной заявки пренебрежимо мала по сравнению с вероятностью поступления одной заявки.
2. Что характеризует параметр λ в экспоненциальном законе распределения?
Параметр λ в экспоненциальном законе распределения характеризует интенсивность потока заявок, то есть среднее количество заявок, поступающих в систему за единицу времени. В экспоненциальном распределении времени между поступлениями заявок параметр λ является обратной величиной к среднему интервалу между заявками.
3. Что характеризует параметр μ в экспоненциальном законе распределения?
Параметр μ в экспоненциальном законе распределения характеризует интенсивность обслуживания, то есть среднее количество заявок, которое может обслужить один канал за единицу времени. В распределении времени обслуживания заявок параметр μ является обратной величиной к среднему времени обслуживания одной заявки.
4. Что такое простейший поток?
Простейший поток — это поток событий, обладающий следующими свойствами:
- Стационарность: вероятностные характеристики потока не меняются со временем.
- Отсутствие последействия (независимость событий): поступление каждой заявки не зависит от предыдущих поступлений.
- Ординарность: за бесконечно малый интервал времени вероятность поступления более одной заявки пренебрежимо мала.
Простейший поток соответствует пуассоновскому процессу и часто используется для моделирования случайных потоков заявок в системах массового обслуживания.
5. Приведите основные характеристики пуассоновского потока.
Основные характеристики пуассоновского потока:
- Распределение числа заявок: число заявок, поступающих за фиксированный интервал времени, подчиняется пуассоновскому распределению.
- Распределение интервалов между заявками: времена между поступлениями заявок распределены по экспоненциальному закону с параметром λ.
- Свойство отсутствия последействия: поступления заявок происходят независимо друг от друга.
- Стационарность: интенсивность λ потока не зависит от времени.
- Ординарность: вероятность поступления более одной заявки в бесконечно малом интервале времени пренебрежимо мала.
6. Каким образом расставляются заявки в каналах?
В многоканальной системе массового обслуживания поступающие заявки распределяются по свободным каналам. Если при поступлении заявки есть свободные каналы, заявка сразу поступает на обслуживание в один из них. Если свободных каналов несколько, выбор канала может осуществляться по определенному правилу (например, случайный выбор, по порядку). Если же все каналы заняты, в системе с отказами заявка отвергается, а в системе с ожиданием она становится в очередь.
7. Какому закону подчиняется время обслуживания заявки в канале?
Время обслуживания заявки в канале подчиняется экспоненциальному закону распределения с параметром μ. Это означает, что вероятность того, что время обслуживания будет больше некоторого значения t, экспоненциально уменьшается с увеличением t.
8. Какими бывают виды СМО по способу обслуживания заявок?
Системы массового обслуживания (СМО) по способу обслуживания заявок делятся на:
- Системы с отказами: если все каналы заняты, поступившая заявка отклоняется (не обслуживается).
- Системы с ожиданием (с очередью): поступившие заявки, которые не могут быть обслужены немедленно из-за занятости всех каналов, ставятся в очередь ожидания.
- Системы с ограниченной очередью: очередь имеет фиксированный размер; если очередь заполнена, новые заявки отвергаются.
- Системы с бесконечной очередью: очередь не ограничена по длине.
- По дисциплине обслуживания: системы могут различаться по правилам выбора заявок из очереди (например, FIFO — первым пришёл, первым обслужен; LIFO — последним пришёл, первым обслужен; приоритетное обслуживание и т.д.).
9. Назовите основные характеристики структуры СМО.
Основные характеристики структуры системы массового обслуживания:
- Количество каналов обслуживания (n): число параллельно работающих серверов (каналов).
- Интенсивность поступления заявок (λ): среднее число заявок, поступающих в систему за единицу времени.
- Интенсивность обслуживания (μ): среднее число заявок, которое может обслужить один канал за единицу времени.
- Распределение времени обслуживания: статистическое распределение времени, затрачиваемого на обслуживание одной заявки.
- Наличие и ёмкость очереди: определяет, может ли заявка ожидать обслуживания и сколько заявок может находиться в очереди одновременно.
- Дисциплина обслуживания: правило, по которому заявки выбираются из очереди для обслуживания.
- Структура поступления заявок: характеристики потока заявок (например, пуассоновский поток).
10. Какие основные характеристики СМО с отказом?
Основные характеристики системы массового обслуживания с отказами:
- Вероятность отказа (Pₒтₖ): вероятность того, что поступившая заявка будет отклонена из-за занятости всех каналов.
- Относительная пропускная способность (Q): вероятность того, что заявка будет обслужена (Q = 1 - Pₒтₖ).
- Абсолютная пропускная способность (A): среднее число заявок, обслуживаемых системой за единицу времени (A = λ * Q).
- Коэффициент нагрузки (ρ): отношение интенсивности поступления заявок к интенсивности обслуживания (ρ = λ / μ), характеризующий среднее число заявок, требующих обслуживания в единицу времени относительно возможностей одного канала.
- Среднее число занятых каналов: показывает, сколько каналов в среднем занято обслуживанием заявок.
11. Чем отличается номинальная пропускная способность от фактической?
Номинальная пропускная способность системы — это максимальное число заявок, которое система может обслужить за единицу времени при условии непрерывной занятости всех каналов. Она определяется как произведение числа каналов на их индивидуальную пропускную способность: Aₙₒ₍ₘ₎ = n * μ.
Фактическая пропускная способность — это реальное среднее число заявок, обслуживаемых системой за единицу времени, учитывающее статистическую природу поступления заявок и возможные простои каналов. Она обычно меньше номинальной из-за вариабельности в поступлении заявок и времени обслуживания.
12. Докажите корректность оценок характеристик СМО (2.10)…(2.14), вычисленных по экспериментальным данным.
Корректность оценок характеристик СМО, вычисленных по экспериментальным данным (формулы (2.10) – (2.14)), обосновывается следующими статистическими принципами:
- Формула (2.10) для вероятности отказа Pₒтₖ:
[ P_{\text{отк}} = \frac{N_{\text{пост}} - N_{\text{обс}}}{N_{\text{пост}}} ]
Эта оценка представляет собой относительную частоту отказов, которая при большом числе наблюдений стремится к истинной вероятности отказа согласно закону больших чисел.
- Формула (2.11) для относительной пропускной способности Q:
[ Q = \frac{N_{\text{обс}}}{N_{\text{пост}}} ]
Это непосредственная оценка вероятности обслуживания заявки, дополняющая вероятность отказа (Q = 1 - Pₒтₖ).
- Формула (2.12) для абсолютной пропускной способности A:
[ A = \frac{N_{\text{обс}}}{T_{\text{набл}}} ]
Эта оценка определяет среднее число обслуженных заявок за единицу времени по экспериментальным данным, что соответствует определению абсолютной пропускной способности.
- Формула (2.13) для доли времени простоя системы p₀:
[ p_0 = 1 - \frac{\sum_{i=1}^{n} Tr_i}{T_{\text{набл}}} ]
Здесь сумма времени занятости каналов Trᵢ делится на общее время наблюдения, что дает долю времени, когда каналы заняты; вычитание из 1 дает долю времени, когда все каналы свободны (простой системы).
- Формула (2.14) для среднего числа занятых каналов k:
[ k = \frac{\sum_{i=1}^{n} i \times Tr_i}{T_{\text{набл}}} ]
Это оценка среднего числа занятых каналов, где Trᵢ — суммарное время, когда заняты i каналов, умноженное на число каналов i и нормированное на общее время наблюдения.
Все эти оценки являются состоятельными и несмещенными статистическими оценками соответствующих теоретических характеристик системы массового обслуживания. При достаточном объеме данных они приближаются к истинным значениям характеристик, что подтверждает их корректность.