В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 51
Текст из файла (страница 51)
Мы кратко рассмотрилз вопрос конечности очереди далее в этой главе. + Дизззиялииа диспетчеризации(дарагс)>1пйсйзс>р11пе). Когда сервер завершает обработку очередноп> аапроса, а в очереди содержится больше одного запроса, должно быть принято решение о механизме выбора из очереди следующего запроса. Простейший метод диспетчеризации представляет собой метод Р11'О (Г>шг >и Бган Оцг — первым прибыл, первым обслужен). Как правило, этот метод применяется, когда используется термин очередь. Другой возможный вариант — метод Е1РО (Еззг 1п Бгзг Опг — последним прибыл, первым обслужен). Общий подход заклк>чается в использовании дисциплины диспетчериаации, основанной на относительных приоритетах. Например, маршрутизатор может учитывать информацию о качестве обслуживания. Ниже перечислены некоторые полезные параметры, включая показанные на рис.
8.2, а также некоторые другззе (интерес, в частности, часто представляет вариация различных параметров, которая выражается среднеквадратичным отклонением): + Л вЂ” скорость поступления, то есть среднее количество поступающих в секунду запросов; + Т, — среднее время обслуживания каждого запроса; в это время не входит время ожидания в очереди; + оп — среднеквадратичное отклонение времени обслуживания; + гз — коэз)крициент испол пользования; доля времени, которук> сервер (серверы) занят; + и — интенсивность графика; + г — среднееколичество во запросов в системе, ожидающих и обслуживаемых; + )1 — количество запросов в системе, ожидающих и обслуживаемых; + Т, — среднее врелзя, которое аапрос проводит в системе; + Тз — время, которое запрос проводит в системе; + а; — среднеквадратичное отклонение г, + о — среднеквадратичноеотклонение Т;, х + и> — среднее количество запросов, ожидающих обслуживания; + гз„.
— среднеквадратичное отклонение и;. + Т вЂ” среднее время ожидания (включая запросы с нулевым временем ожидания); + Тз — среднее время ожидания с ия (исключая запросы с нулевым временем ожидания); + А> — количество серверов; + т„~у> — у-ипр ц т „(у) -" о ен иль; это значение, ниже которого величина х встречается с частотой у. Очередь к нескольким серверам На ис. 8.4, а показано обобщение обсуждавшейся ранее простой модели для нескольких серверов с общей очередью.
Если при ывае ро а рис, а показано т зап с и свободен хотя бы один сервер, тогда этот запрос немедленна передается у р ру. этом се ве . Предполага, если свободными одновременно ется, что все серверы идентичны. Таким образом, если д оказываются несколько серверов, то выбор конкретно р р" н гасе ве аневлияетнавремя обслуживания. Если все серверы заняты, начинает р р ер ми оваться очередь.
Как только один иа серверов освобождается, из очереди с использованием дисциплины диспетчеризации выбирается запрос и передается серверу. Все параметры, кроме коэффициента использования, показа ' р азанные на нс. 8,2, с тем же успехом применимы к случаю нескольких серверов. Е у . Если нас есть А>идентичных серверов, тогда р представляет собои коэф ициент >цент использования кажнт использования системы лого сервера, а А>, можно рассматривать кзк коэффициент исп в целом. Зтаттермин часто называют интенсивностью тра и . ика 1пгепз11 гга(йс) и. Таким образом, теоретический максимум коэффициента исполь льзования составляет А> .
100 Кз а теоретический максимум для входной скорости равен А> Л Т, Как правило, ключевые характеристики, выбираемые для очереди к нссколь:им серверам, соответствуют характеристикам очереди к одному серверу. то 8.8. Модели очередей 231 230 Глава 8. Анализ очередей Очередь Дисциплин постуйпения Один сервер Несколько серверов »,Т, г = Лт, — Формула Литтла т= Лт, — Формула Литтлв т,=т.+т. Р=Лт« и=Лт,=рн г=кк+И„ к= и+р означает, что мы предполагаем бесконечную совокупность и бесконечный размер общей для всех серверов очереди. За исключением специально оговариваемых слу- чаев, дисциплина диспетчеризации представляет собой порядок Р1ЕО. Рис. 8.4.
Сравнение моделей одной очереди: а — к нескольким серверам, о — к каждому серверу На рис. 8А, 6, напротив, представлена структура из отдельной очереди к каждому из нескольких серверов. Как будет показано ниже, зто незначительное изменение структуры оказывает существенное влияние на производительность. Основные соотношения теории очередей Чтобы продвинуться дальше, мы должны принять несколысо упрошаюших попу шений. Принимая эти допущения, мы рискуем сделать модель менее соответству- фф юшей реальной ситуации.
К счастью, во многих случаях Результаты остаются до- статочно точными для задач планирования и проектирования. Однако существуют соотношения, справедливые для общего случая. Эти соотношения приведены в табл. 8А. Сами по себе они не очень полезны, однако могут использоваться для ответов на несколько основных вопросов, Вот пример, взятый из ~1541, Рассмотрим шпиона из закусочной «Королевские Гамбургерыь, пытаюшегося вычислить количество людей в закусочной Мел»опа1о'з, расположенной на противоположной стороне улицы.
Он не может весь день сидеть в Мс1»опа!ц'з, поэтому должен найти ответ, основываясь только на наблюдении входящих в Мс1»опаЫ'з и выходящих оттуда лккдей. Пронаблюдав аа дверью конкурирующей фирмы в течение дня, он определяет, что за час в среднем эту закусочную посешают 32 посетителя. Он также замечает, что средний посетитель остается внутри 12 минут. С помошью формулы Лнттла (1лЫе) шпион определяет, что в юждый момент времени в Мс1)опа!сЬ находится в среднем 6,4 посетителя (6,4 = 32 посетителя в час 0,2 часа/посетителя). Таблица 8.4. Некоторые основные соотношения теории очередей На данном этапе было бы полезно получить интуитивное представ.
ление об уравнениях из таблицы. Для формулы р = ».Тт сосчитаем средний интервал времени между поступлением заказов Т= 1/»,. Если значение Т больше, чел1 Тя тогда в течение интервала времени Т сервер оказывается занятым только на время Тл так что коэффициент использования равен Тт/Т = ХТе Аналогичные рассуждения применимы для случая очереди к нескольким серверам и формулы р = ХТк/Х. Чтобы понять формулы Литтла, рассмотрим следующий пример с одним запросом.
Когда запрос поступает в систему, он обнаруживает, что в среднем тв других запросов ждут в очереди впереди него. Когда запрос покидает очередь, отправляясь на обработку, за ним в очереди остается в среднем все те же тл ожидаюших запросов. Чтобы нагляднее представить это, обратите внимание на то, что пока запрос ждет своей очереди, очередь перед ним уменьшается, а позади него растет.
Котла запрос покидаеточередь,среднееколичествозапросовпозадинегоравно ил таккак тл, по определению, равно среднему количеству запросов, ожилаклцих обслуживания. Среднее время ожидания обслуживания равно Т„. Поскольку запросы прибывают со скоростью Х, мы можем считать, что за время Т„должно поступить»'Т запросов. Таким образом, тп = »„Т, Путем аналогичных рассуждений можно вывести формулу г= » Т,, Теперь рассмотрим последнюю формулу в первом столбце таблицы. Несложно видеттч что время, которое запрос проводит в системе, представляет собой сумму времени ожидания и времени обслуживания, Таким образом, в среднем, Т, = Т., + Т..
Последние формулы во втором и третьем столбцах можно легко проверить. В лю~ой момент времени число запросов в системе прелставляет собой сумму коли- 232 Глава 8. Анализ очередей 8.4. Очередь к одному серверу 233 честв ожидающих в очереди и обслуживаемых запросов. Для одного сервера сред- нее число обслуживаемых запросов равно р, поэтому г= ге+ р. Аналогично, для )у'серверов г = ю + 1Уе Допущения Входной информаццей для очереди является: + скорость поступления запросов; + время обслуживания; + количество серверов. Фундаментальная задача анализа очередей заключается в том, чтобы на основании такой входной информации получить следутощую информацию на выходе: + количество ожидающих аапросов; + время ожидания; + количество запросов в очереди; + время нахождения запроса в системе.
Что конкретно нам нужно знать об этих величинах? Во-первых, нам нужно знать их средние значения (кг, Т„„г; Т). Кроме того, было бы полезно кое-что узнать об их изменчивости. То есть нам нужно знать среднеквадратичное отклонение каждой из этих величин (о;, о, о;, о ). Также могут быть полезны и другие величины. Например, при проектировании буфера маршрутизатора или мультиплексора, возможно, будет полезно знать размер буфера, вероятность переполнения которого не превосходит 0,001. Другими словами, чему равно А1, такое, что Рг1число ожидав>ших запросов < гу1 = 0,999? Чтобы отвечать на подобные вопросы, в обшем случае требуется полное знание распределения вероятности временных интервалов между поступлениями запросов (интервалов времени между успешными поступлениями запросов) и времени обслуживания.
Более того, даже при наличии этой информации получаюшиеся в результате формулы оказываются исключительно сложными. Поэтому, чтобы двигаться дальше, мы должны принять некоторые упрощающие допушення. Наиболее важное из этих допущений касается скорости поступления запросов. Предполагается, что интервалы времени между поступлениями запросов распределены экспоненциально. Это равносильно заявленикг о подчинении числа поступаюших аа период времени Г аапросов распределению Пуассона. Другими словами, это означает, что запросы поступают случайным образом и не зависят друг от друга. Это допушенне принимается почти всегда.
Без него анализ очередей оказывается невозможным или, в крайнем случае, довольно сложным. При таком допуШении оказывается, что, зная только среднее значение и среднеквадратичное отклонение скорости поступления запросов, можно получить много полезных результатов. Ситуацию можно упростить еше больше, если предположить, что время обслуживания подчиняется экспоненциальному распределению или постоянно. При этом могут быть получены еше более точные результаты. Для обозначения основных допущений, принимаемых при моделировании очередей, была разработана так называемая нотпация Кендалла (Кепг1аП'з погас1оп), Эта нотация имеет вид Х/У/Х, где Х обозначает распределение интервалов времени между поступлениями запросов, У вЂ” распределение времени обслуживания, ь1 — количество серверов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
