В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 52
Текст из файла (страница 52)
Наиболее часто встречающиеся распределения обозначаются следующим образом: + Π— произвольное распределение интервалов времени обслуживания запросов или интервалов времени между поступлениями запросов; + О1 — произвольное распределение интервалов времени между поступлениями запросов с ограничением, заключаюшимся в независимости этих интервалов; + М вЂ” отрицательноезкспоненциальное распределение; + П вЂ” детерминированное поступление запросов, или обслуживание фиксированной длины. Таким образом, запись М/М/1 означает модель с одним сервером, в которой количество поступающих запросов распределено по Пуассону (интервалы времени между поступлениями распределены экспоненцнально), и с экспоненциальным распределением интервалов времени 'обслуживания.
8.4. Очередь к одному серверу Ниже приведены некоторые формулы для очереди к одному серверу при следуюших допущениях: + частота поступления запросов подчиняется распределению Пуассона; + дисциплина диспетчеризации не дает предпочтения запросам, основываясь на времени обслуживания; + в формулах для среднеквадратичного отклонения предполагается диспетчеризация г1г О; + запросы не выбрасываются из очереди. Для первого случая частота поступления запросов распределена по Пуагпону, а интервалы времени обслуживания подчиняются пронавольному распределению. Использование коэффициента масштабирования А позволяет упростить формулы для некоторых ключевых выходных переменных. Обратите внимание на то, что масштабируюший коэффициент зависит ог отношения среднеквадратичного отклонения времени обслуживания к среднему значению.
Никакой другой инфор мании о времени обслуживания не требуется. Итак, формулы для произвольного распределения времени обслуживания (М/О/1): А = — 1+ —" г 1 г'=р+— 1 — р 234 Глава 8. Анализ очередей 0,4 очередь к одному серверу 236 2 ш= — ' 1 — р РТ 2(1- Р) Т,=Т„+ — * РТ,А 1 — р ЗР' 5Р' Р" о,= — Р + 1-р 2 6 12 РТ„А 1-р Т„Р Р 1 — р11 3 12 Т„= — '; Т„= — ' РТ Р 1 Р о„= —; о, ,$ Т, 1 — Р ' 1-Р' Рг()т=Ж1 =(1 — Р)Р ' "-'С.згке Ф"'Ь Р ГЛ<)у!=Х(1-Р)Р'' Рг~Т» <Т1=1-е " ' т (У) =Т 1и 100 100-у ' мз,,и'.~в з ~'»оьх р ьи о,вт, " ,, ст;0 о,г о,з 0,4 О,Б 2(1 — Р) Т,(2 — р) 2(1 — Р) Интерес представляют два особых случая.
Когда среднеквадратичное отклонение равно среднему аначению, распределение времени обслуживания является экспоненциальным (М/М/1). Это простейший случай, в котором легче всего по лучить результаты. Далее показаны упрощенные варианты формул для среднеквадратичного отклонения »и Т„а также некоторые другие интересные соотношения; Р, Р 1-р'" 1-р' Другой инте есный с чай ру " р ' случай, когда среднеквадратичное отклонение времени обслуживания равно нулю, что означает постоянное время обслуживания (М/П/1): Я г= +Р; 2(1 — р) На рис. 8.5 и 8.6 показаны графики зависимостей средних значений размера очереди и времени присутствия запроса в системе для трех значений отношения о, /Т,. Последняя величина называется коэффициентом иэмекчиеости (сое(бс1епг о(таг1ак|оп) и представляет собой нормализованную меру изменчивости. Обратите внимание на то, что лучшая производительность достигается при постоянном времени обслуживания, а худшая — при экспоненциально распределенном.
Во многих случаях можно считать экспоненциально распределенное время обслуживания худшим случаем, поэтому консервативные результаты можно получить путем анализа, основанного на этом допущении. Это очень удобно, так как для случая М/М/1 сушествуют таблицы, в которых можно быстро найти нужные значения. коэффициент ислоль»о»алий (Р) рис. В.В. Среднее число эап россе в системе длл очеРеди к одному сервеРУ Какое отношение о„, / Т„может встретиться на практикеу Мы можем рассмат1ивать четыре области значении: 236 Глава 8. Анализочередей ю од О,4 0,6 0,8 1,0 Коэффициент иолользования (р) 1 — К С= — С-функция Эрланга; 1-РК г=С вЂ” +тттр; те=С вЂ”; Р Р 1-Р 1 — Р С Т, С Т Т = — — '+Т;Т )У1-р " Н~ р Т„ аг = —" Ж(1 — Р) 1 — ттР<! Р) — СР: 1 — р Рис.
8.6. Среднее резидентное время для очереди к одному серверу + Нулевое значение. Это редкий случай постоянного времени обслуживания. Например, к этой категории может относиться случай, при котором размеры всех передаваемых пакетов одинаковы. + Отношениемеяьше 1. Поскольку этот случай лучше, чем зкспоненцнальное распределение, с помощью формул для схемы М/М/1 можно получить значения размеров очереди и интервалов времени несколько большие, чем они должны быть, Таким образом, схема М/М/1 позволяет рассчитать границы безопасной зоны параметров. К этой категории относятся приложения с ааполнением форм. + Олитошение близко к 1.
Это довольно распространенный случай, соответствующий экспоненциальному распределению, когда врелтя обслуживания в значительной степени является случайным. Рассмотрим случай вывода сообщений на алфавитно-цифровой экран компьютера. Полный экран может вместить до 1920 символов, а в сообщении могут находиться от 0 до 1920 символов. К этой категории относятся такие приложения, как заказ авиабилетов, поиск файлов, коллективно используемые локальные сети, а также сети с коммутацией пакетов. + Отношение больше 1.
Для этого случая уже неприменима схема М/М/1, и нужно использовать схему М/О/1, Наиболее распространенным вариантом данного случая является бимодальное распределение с далеко отстоящими друг от друга пиками. Пример такого случая — система с большим количеством коротких сообщений, большим количеством длинных сообщений и практически без сообшений промежуточного Размера.
8.8. Очередь к нескольким серверам 237 Те же соображения применимы к скорости поступления запросов. Если частота поступления запросов распределена по Пуассону, то интервалы времени подчиняются экспоненциальному распределению, а отношение среднеквадратичного отклонения к среднему значению равно 1. Если данное отношение существенно меньше 1, тогда поступления стремятся к равноотстоящему варианту (с невысоким уровнем изменчивости), и приближение Пуассона позволяет получить оценку верхних границ размеров очереди и времени ожидания. С другой стороны, если это отношение больше 1, тогда запросы поступают очень неравномерно и проблема перегрузки становится очень актуальной.
8.5. Очередь к нескольким серверам Ниже перечислены формулы для некоторых ключевых параметров случая нескольких серверов. Ряд ограничений накладывается в допущениях: + частота поступления запросов подчиняется распределению Пуассона: + значения времени обслуживания распределены экспоненциально; + все серверы загружены в равной мере; + среднее время обслуживания всех серверов одинаково; + используется диспетчеризация Р)РО; + запросы не выбрасываются из очереди. Для этой модели полезная статистик» была получена только для схемы М/М/ Ттт, в которой экспоненциальное распределение времени обслуживания идентично для всех серверов: ~ (НР)' К = „" ', — функция отношения Пуассона; ч"; (НР)' тм Л 238 Глава 8. Анализ очередей 8.6. Примеры 239 Р !Т„>Г)=С."о "", И(1 — р) ! 100 — г ! Т, т = А'(!-р) Обратите внимание на присутствие С-функции Эрланга практически во всех уравнениях.
Она означает вероятность того, что в данный момент времени заняты все серверы. Другими словами, это вероятность того, что количество запросов в системе (ожидающих и обслуживаемых) больше или равно количеству серверов. Соответствующее уравнение имеет вид С(Ж )— 1 — Ж,И Здесь К вЂ” функция отношения Пуассона. Поскольку величина С представляет собой вероятносзь, зта величина всегда находится в диапазоне от 0 до 1.
Как можно видеть, она является функцией от числа серверов и коэффициента использования. Это выражение часто встречается при расчетах очередей. Можно воспользоваться готовыми табличными значениями или компьютерной программой. Обратите внимание нато, что для системы с одним сервером эта формула упропРется до С(1 Р) = Р. 8.6.
Примеры Рассмотрим несколько примеров, чтобы понять, как работают эти уравнения. Серверы баз данных Рассмотрим локальную сеть, в которой имеется 100 персональных компьютеров, и сервер, хранящий обшую базу данных для приложений, посылаюгпих ему запросы. Среднее время, требующееся серверу для ответа на запрос, составляет 0,6 с, а среднеквадратичное отклонение ожидается равным среднему значению. В моменты пиковой нагрузки частота запросов в локальной сети достигает 20 запросов в минуту. Мы хотели бы получить ответы на следующие вопросы: + Чему равно среднее время отклика, если пренебречь накладными расхода- ми линии? + Если максимальное приемлемое время отклика считается равным 1,5 с, н» сколько процентов может вырасти нагрузка, прежде чем будет достигнут максимум? + Если ожидается увеличение коэффициента использования на 20 %, увели- чится ли время отклика больше или меньше, чем на 20 %? Предположим, что система соответствует схеме М/М/1, Проигнорируем влияние локальной сети, предполагая, что ее вклад в задержку является пренебрежимо малым.
Коэффициент использования вычисляется так: р = Лт, = (20 запросов э минуту)(0,6 с на передачу)/(60 с/мин) = 0,2. Первое значение, среднее время отклика, легко вычислить: Т, = Т/(1 — р) = 0,6/(1 — 0,2) = 0,75 с Второе значение получить труднее. В самом деле, как было сказано, ответа нет, тзк как существует ненулевая вероятность, что в некоторых случаях время отклика превысит 1,5 с для любого значения коэффициента использования, Вместо этого скажем, что нам хотелось бы, чтобы 90 % всех значений времени отклика были меньше 1,5 с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
