Стационарные и нестационарные потоки заявок.

Различают стационарныеи нестационарные потоки заявок.

Стационарным потоком заявок – называется поток заявок, у которого вероятностные характеристики не зависят от времени.

Нестационарным потоком заявок – называется поток заявок, у которого вероятностные характеристики зависят от времени.

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

Так, например, поток заявок от абонентов, поступающий в АТС, не может считаться стационарным в течение суток, поскольку интенсивность разговоров ночью значительно ниже, чем днем (рис. 3.4)

Рисунок 3.4

. Из приведенного графика видно, что наибольшая интенсивность приходится на период от 9'до 18 ч, в пределах которого с некоторым приближением поток может рассматриваться как стационарный. Еще можно привести пример про факел ракеты.

Простейший поток заявок.

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

1. Стационарность – вероятностные характеристики потока не зависят от времени.

2. Отсутствие последействия - поступления заявки не зависит от времени прихода предыдущей заявки.

3. Ординарность – в каждый момент времени в систему поступает не более одной заявки.

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

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

Основные характеристики качества функционирования ЦУС.

Одной из важнейших характеристик качества функционирования ЦУС является загрузка системы:

Где интенсивность поступления заявок в систему; - интенсивность обслуживания заявок.

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

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

Поскольку загрузка определяет вероятность того, что система занята обслуживанием, т.е. работает, то вероятность простоя определяется значением называемым коэффициентом простоя.

При этом предполагается, что, , что справедливо для всех реальных систем.

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

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

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

Глава 3.

Дисциплины обслуживания заявок.

3.1 Бесприоритетная дисциплина обслуживания.

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

1) в порядке поступления (первой обслуживается заявка, поступившая раньше других);

2) в порядке, обратном порядку поступления заявок (первой обслуживается заявка, поступившая позже других);

3) наугад, т. е. путем случайного выбора из очереди.

Дисциплина обслуживания в порядке поступления называется FIFO1 (первый при), а дисциплина обслуживания в обратном порядке-LIFO2.

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

Бесприоритетчюе обслуживание заявок на основе дисциплины FIFO организуется в соответствии со следующим рисунком

Бесприоритетная дисциплина обслуживания

где Пр -процессор и О - очередь для заявок типа z1, ..., zn. Вновь поступившая заявка заносится в конец очереди. Заявки выбираются на обслуживание из начала очереди. Примером может служить очередь заданий печати для принтера.

Дисциплина обслуживания с относительными приоритетами заявок

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

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

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

Дисциплина обслуживания с относительными приоритетами

Заявкам типа z_l..., z_m присвоены относительные приоритеты i, ..., М соответственно. Заявка z_рпоступившая в систему, заносится в очередь О_р, в которой хранятся заявки приоритета р=1, ....М. В очереди O_р заявки упорядочены по времени поступления. Когда процессор Пp заканчивает ранее начатое обслуживание, то управление передается программе ДИСПЕТЧЕР. ДИСПЕТЧЕР выбирает на обслуживание заявку с наибольшим приоритетом — заявку z_i, если очереди О₁..., О_i-1 не содержат заявок. Выбранная заявка захватывает процессор Пр на все время обслуживания.

Дисциплина обслуживания с абсолютными приоритетами

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

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

Дисциплина обслуживания с абсолютными приоритетами

1 — заявка, ожидающая обслуживания; 2 — прерванная заявка.

Для каждого потока заявок z₁..., z_м организуется очередь O₁ ..., О_м, в которой заявки размещаются в порядке поступления. Заявкам z_1;..., z_m соответствуют абсолютные приоритеты 1, .... М. Если процессор Пр занят обслуживанием заявки z_i и на вход, поступает заявка типа z_j, то при i < =j заявка z_j заносится в конец очереди О_j, а при i > j обслуживание заявки z_i прерывается, заявка z_i заносится в начало очереди О_i и ДИСПЕТЧЕР переключает прибор на обслуживание заявки zj.

Обслуживание прерванных заявок может проводиться:

1) от начала;

2) от момента прерывания (дообслуживание).

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

ОП – кривая относительного приоритета; АП – кривая абсолютного приоритета. Присваивание заявкам абсолютных приоритетов приводит к уменьшению времени ожидания заявок с высокими приоритетами, но одновременно с этим увеличивается время ожидания низкоприоритетных заявок

Дисциплина обслуживания со смешанными приоритетами.

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

Пусть в систему поступает М типов заявок. Если заявки обслуживать без приоритетов (дисциплина FIFO), то для заявок типа 1, ..... М₁среднее время ожидания может оказаться недопустимо большим. Если перейти к дисциплине с относительными приоритетами (кривая ОП), то для заявок типа 1, ..., М₁положение исправляется, но времена, ожидания заявок с низкими приоритетами превышают предельно допустимые значения.

Если заявкам типа 1, ..., М₁ присвоить относительные приоритеты 1, ..... М₁, а заявки типа М₁+1,... М обслуживать без приоритетов, то среднее время ожидания соответствует кривой СП удовлетворяет заданным ограничениям.

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

⇐ Предыдущая 1 2 3 45