Понятие о приоритетном обслуживании

Тема 8. Приоритетное обслуживание при передаче данных

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

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

а) какое сообщение брать на обслуживание следующим;

б) продолжать или прервать обслуживание сообщения, находящегося на обслуживании.

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

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

8.2. Виды приоритетного обслуживания

Решение о выборе следующего сообщения для обслуживания может быть принято внесистемно, т.е. без учета текущего состояния системы обслуживания – сети ПД – в зависимости только от номера категории срочности сообщения. С другой стороны, оно может быть принято внутрисистемно, т.е. решение может базироваться полностью или частично на анализе текущего состояния процесса передачи сообщения, например, типа обслуженного сообщения или времени ожидания сообщений в очереди в текущий момент.

Различают два вида приоритетного обслуживания: внесистемные приоритетные дисциплины и внутрисистемные приоритетные дисциплины.

Как при внесистемной, так и внутрисистемной приоритетной дисциплине решение о продолжении обслуживания сообщения, находящегося на обслуживании может зависеть, или не зависеть от состояния системы.

Внесистемные приоритетные дисциплины (приоритеты) обеспечивают обслуживание сообщений только на основе учета их категории срочности.

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

а) абсолютный приоритет: обслуживание сообщения категории срочности немедленно прерывается и начинается обслуживание сообщения категории срочности;

б) относительный приоритет: обслуживание категории срочности продолжается до полного завершения, после чего начинается обслуживание сообщения старшей категории срочности из ожидающих обслуживание;

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

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

а) абсолютный приоритет с дообслуживанием: обслуживание сообщения возобновляется с того момента, когда произошло прерывание;

б) абсолютный приоритет с повторением обслуживания: сообщение обслуживается заново с прежней реализацией времени обслуживания;

в) абсолютный приоритет с обслуживанием заново: сообщение обслуживается заново с новой реализацией времени обслуживания.

Дисциплина с абсолютным приоритетом может использоваться для создания преимуществ передачи сообщений привилегированных абонентов в рамках одной категории срочности. Дисциплина с относительным приоритетом предполагает, что сообщения одной категории срочности создаются однородными по важности абонентами. Сообщения старших категорий занимают место в очереди впереди всех сообщений младших категорий срочности. Это создает возможность для первоочередного обслуживания абонентов старших рангов, если их сообщениям приписывать старшие категории срочности. Дисциплина со смешанным приоритетом предполагает, что сообщение более низкой категории вытесняется с обслуживания при поступлении сообщения более высокой категории, если оно непрерывно обслуживалось в течение времени, меньшего и не вытесняется, если оно обслуживалось в течение времени большего или равного . Возможен и другой вариант дисциплины со смешенным приоритетом, когда сообщениям старшей категории приписывается абсолютный приоритет, а младшим категориям – относительный.

Совокупность отношений сообщений различных рангов преимущества называется системой приоритетов. Таким образом, в сетях ПД используется абсолютная, относительная или смешанная система внесистемных приоритетов. Задача назначения внесистемных приоритетов решается эвристически, т.е. на основе имеющегося опыта.

Во многих ситуациях внесистемные дисциплины обслуживания, при которых выбор сообщения на обслуживание зависит только от категории срочности, оказываются неспособными решать задачи распределения потоков сообщений в сети с заданными вероятностно-временными характеристиками. Например, если задаться целью, не задерживать сообщение любой категории в сети ПД свыше заданного предела, то правила выбора сообщения на обслуживание должны учитывать время пребывания сообщения в сети. Итак, необходимость обеспечения заданных вероятностно-временных характеристик доведения сообщений неминуемо приводит к использованию внутрисистемных приоритетов.

Внутрисистемные приоритеты определяют порядок обслуживания сообщений в рамках каждого внесистемного приоритета и не зависят от категорий, установленных системой управления. Различают фиксированные и динамические внутрисистемные приоритеты.

Фиксированные внутрисистемные приоритеты определяют фиксированное правило выбора сообщения из очереди на обслуживание в пределах одной категории срочности. Часто фиксированные приоритеты называют дисциплиной обслуживания. Динамические, или фактические, внутрисистемные приоритеты обеспечивают сообщению дополнительное преимущество на первоочередный выбор из очереди на обслуживание среди сообщений своей категории срочности в зависимости от времени пребывания сообщения в сети. Динамический приоритет изменяет индекс преимущества дискретно или непрерывно. Динамические приоритеты позволяют уравнять время пребывания сообщений в сети для каждой категории срочности.

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

,

где - доля времени занятия обслуживающего прибора обслуживанием сообщения категории,

- среднее время пребывания в очереди на обслуживание сообщений категории.

Закон сохранения имеет следующую формулировку: взвешенная сумма средних времен ожидания обслуживания сообщениями всех приоритетов есть величина постоянная.

Закон выполняется при следующих условиях:

1. Система приоритетов относительная или абсолютная с дообслуживанием.

2. Длина очередей в системах обслуживания неограниченна.

3. Обслуживающие устройства не простаивают, если хотя бы одно сообщение ожидает обслуживания.

4. Распределение промежутков времени между поступающими на обслуживание сообщениями и времена их обслуживания – произвольные.

Таким образом, введение системы приоритетов обеспечивает улучшение вероятностно-временных характеристик сообщений высших категорий срочности за счет ухудшения соответствующих характеристик для сообщений других категорий. При этом приоритеты не изменяют усредненных вероятностно-временных характеристик сети по доставке сообщений.

8.3. Характеристика дисциплин обслуживания

Дисциплины обслуживания можно классифицировать в зависимости от учета следующих факторов:

· относительного времени поступления сообщения в очередь;

· некоторой меры времени обслуживания(точного значения, оценки, распределения вероятностей и т.п.), необходимого для данного сообщения или израсходованного к рассматриваемому моменту времени.

Выбор сообщения для обслуживания в зависимости от времени его поступления является наиболее естественным. Наиболее распространены дисциплины обслуживания, зависящие от относительного времени поступления сообщения.

Обслуживание в порядке поступления – ОПП (первым пришел - первым обслужен)

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

Обслуживание в обратном порядке – ООП (последним пришел – первым обслужен)

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

Обслуживание в случайном порядке – ОСП

В этом случае очередность обслуживания сообщений (рис.8.3) не зависит от очередности их поступления. Сообщение из очереди на обслуживание выбирается случайным образом. Данная дисциплина достаточно точно отображает функционирование системы обслуживания, когда обслуживающий прибор последовательно опрашивает элементы памяти, каждый из которых независимо от других случайным образом содержит или не содержит сообщение. Все приведенные дисциплины обслуживания обеспечивают одинаковое значение среднего времени ожидания сообщений в очереди . Особенности этих дисциплин проявляются в различии дисперсий времени ожидания .

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

Важный класс дисциплин обслуживания направлен на первоочередное обслуживание сообщений с кратчайшим временем обслуживания, когда это время не известно. Такие дисциплины играют важную роль в работе вычислительных систем коллективного пользования с параллельным доступом. Описание этих дисциплин основано на понятии кванта, означающего промежуток времени, на который сообщению предоставляется обслуживающее устройство. Если в течение этого времени сообщение получает необходимое обслуживание, то оно покидает прибор обслуживания. В противном случае сообщение возвращается в очередь, где ожидает дообслуживание. Алгоритм обработки сообщений в подобных системах называют алгоритмом составления расписаний, или распределительным алгоритмом.

Наиболее известным и широко применяемым алгоритмом обработки является круговой опрос – КО. При алгоритме КО поступающие сообщения становятся в очередь после всех ожидающих сообщений (рис.8.4), т.е. обслуживание происходит в порядке поступления. Более сложный алгоритм обработки может быть назван «задние вперед» - ЗВ. Согласно этому алгоритму (рис.8.5) все поступающие сообщения сначала становятся во внешнюю очередь, из которой направляются в прибор обслуживания в порядке поступления. После получения первого кванта обслуживания, если он окажется недостаточным, эти сообщения направляются во внутреннюю очередь, из которой в порядке поступления поступают в прибор обслуживания для получения этого кванта обслуживания и т.д. Внешняя очередь имеет приоритет перед внутренним. Пока во внешней очереди есть сообщения, прибор обслуживания обращается только к ней. Возможно такое обобщение дисциплины ЗВ, при котором предполагается наличие нескольких внутренних очередей. В этом случае сообщение из i-той внутренней очереди после получения очередного кванта обслуживания переходит в (i+1)-ю очередь, а прибор обслуживания обращается сначала к внешней очереди и, если в ней нет сообщений последовательно разгружает внутренние очереди в порядке их номеров. Обобщение алгоритма ЗВ является многоуровневый алгоритм, действие которого основано на применении понятия уровней достигнутого обслуживания. Каждый уровень характеризуется некоторым промежутком времени, полученного обслуживания. Чем больше квантов обслуживания уже получило то или иное сообщение, тем оно длиннее и попадает на более высокий уровень, к которому обслуживающий прибор обращается реже. В свою очередь на каждом уровне обслуживания можно применять алгоритмы ОПП, КО, ЗВ или другие. С помощью модели с квантованием времени обслуживания могут быть описаны рассмотренные ранее алгоритмы ОПП и ООП.

Рис.8.1 Обслуживание в порядке поступления.

Рис.8.2 Обслуживание в обратном порядке.

Рис.8.3 Обслуживание в случайном порядке.

Рис.8.4 Круговой опрос.

Рис.8.5 Обслуживание по алгоритму «задние- вперед».

Контрольные вопросы

1. Чем определяется приоритетность сообщений?

2. На какие типы подразделена дисциплина с абсолютным приоритетом?

3. Когда необходимы динамические приоритеты? Как влияет закон сохранения на выбор длин сообщений для сети различных классов?

4. Что такое дисциплина обслуживания?

Задания для самопроверки

Разработать алгоритмы для реализации рассмотренных дисциплин обслуживания.

Дата добавления: 2014-01-07