Основы проектирования систем

• Название: Основы проектирования систем
• Дата: 15.11.2021
• Размер: 1.88 Mb.
• Имя файла: 1792.pdf
• Тип: Учебное пособие; #272205
• страница: 9 из 15

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

64 обслуживание, уменьшение накладных расходов может оказаться значительным.
ДО группового режима широко применяются в беспроводных сетях связи под управлением протокола бесконфликтного доступа к среде и называются системами поллинга.
Система поллинга – объект, который содержит не менее двух накопителей и один или несколько серверов. В систему поллинга поступают заявки, которые необходимо обслужить (обработать). Заявки хранятся в накопителях и образуют очереди на обслуживание. Сервер по определённому правилу опрашивает накопители, подключается к одному из них и, в соответствии с выбранной дисциплиной обслуживания, последовательно обрабатывает заявки назначенной группы, называемой группой обработки.
В общем случае в системе могут использоваться ДО комбинированного режима, представляющего собой комбинацию одиночного и группового режимов.
В зависимости от отсутствия или наличия приоритетов между заявками разных классов дисциплины обслуживания делятся на два класса:

бесприоритетные ДО;

приоритетные ДО.
К бесприоритетным ДО относятся дисциплины обслуживания:

в порядке поступления (FIFO – First In First Out);

в обратном порядке (LIFO – Last In First Out);

в случайном порядке (Random);

в циклическом порядке (Cyclic), когда на обслуживание заявки выбираются в процессе циклического опроса накопителей в последовательности
H
...,
,
2
,
1
(

H
количество накопителей), после чего указанная последовательность повторяется.
Среди бесприоритетных ДО в технических системах наибольшее распространение получила дисциплина FIFO, которую в дальнейшем будем обозначать как ДО БП.
К приоритетным ДО относятся дисциплины обслуживания:

с относительными приоритетами (ОП) – приоритеты учитываются только при выборе новой заявки на обслуживание, причем при поступлении заявки с более высоким приоритетом обслуживание низкоприоритетной заявки не прерывается;

с абсолютными приоритетами (АП) – при поступлении заявки с высоким приоритетом прерывается обслуживание заявки с низким приоритетом и на обслуживание принимается поступившая высокоприоритетная заявка; при этом прерванная заявка может быть возвращена в накопитель или удалена из системы; если заявка возвращена в накопитель, то её дальнейшее обслуживание может быть продолжено с прерванного места или начато заново, то есть с начала;

со смешанными приоритетами (СП), представляющими собой любую комбинацию БП, ОП и АП;

65

с чередующимися приоритетами (ЧП) – приоритеты учитываются только в момент назначения на обслуживание новой группы (очереди) заявок после завершения обслуживания всех заявок предыдущей группы, при этом назначаемая на обслуживание группа может иметь произвольный размер (2 или более заявок) и в пределе включать в себя все заявки данной очереди;

обслуживание по расписанию (ОР), когда заявки разных классов
(находящиеся в разных накопителях) выбираются на обслуживание в соответствии с некоторым расписанием
(планом), задающим последовательность опроса очередей заявок, например, в случае трех классов заявок (накопителей) расписание может иметь вид: {1, 2, 1, 3, 1, 2}.
Дисциплины БП, ОП, АП и СП относятся к дисциплинам одиночного режима, означающего, что после обслуживания каждой заявки выполняется поиск заявки с наивысшим приоритетом, поступившей в систему раньше других, которая и выбирается на обслуживание.
Дисциплины Cyclic, ЧП и ОР могут быть реализованы как ДО группового режима, если размер назначаемой на обслуживание группы больше 1, и как ДО одиночного режима, если размер назначаемой на обслуживание группы равен 1, при этом, например, ДО ЧП вырождается в ДО ОП.
Среди дисциплин обслуживания одиночного режима наибольший интерес представляют дисциплины со смешанными приоритетами (СП), обладающие общностью по отношению к дисциплинам БП, ОП и АП.
Для математического описания ДО СП используется матрица
приоритетов
(МП), представляющая собой квадратную матрицу:
]
,
,
1
,
[
H
j
i
q
ij



Q
, где

H
число классов заявок, поступающих в систему.
Элемент
ij
q матрицы задает приоритет заявок класса i по отношению к заявкам класса j и может принимать следующие значения:

0 – нет приоритета;

1 – приоритет относительный (ОП);

2 – приоритет абсолютный (АП).
Элементы МП должны удовлетворять следующим требованиям:

0

ii
q
, так как между заявками одного и того же класса не могут быть установлены приоритеты;

если
1

ij
q
или 2, то
0

ji
q
, так как если заявки класса i имеют приоритет к заявкам класса j, то последние не могут иметь приоритет к заявкам класса i
)
,
1
,
(
H
j
i

Приоритеты заявок могут быть статическими и не изменяться в процессе функционирования системы или динамическими, т.е. изменяться в зависимости от разных факторов. Например, при достижении некоторого критического значения длины очереди заявок низкоприоритетного класса ему может быть предоставлен более высокий приоритет.

66
3.1.4. Режимы функционирования базовых моделей
Базовые модели могут отображать работу реальных систем в следующих режимах:

установившемся, когда вероятностные характеристики системы не изменяются со временем;

неустановившемся, когда характеристики системы изменяются со временем, что может быть обусловлено:
 началом работы системы (переходной режим);
 нестационарностью потоков заявок и длительностей обслуживания
(нестационарный режим);
 перегрузкой системы, когда интенсивность поступления заявок
λ
в систему с
N
устройствами превышает интенсивность их обслуживания
Nμ , где
b
μ
/
1

– интенсивность обслуживания заявок одним устройством;
Nμ
λ

означает, что система не справляется с нагрузкой
(режим перегрузки), при этом характеристики функционирования системы (в частности длина очереди перед устройством в системе с накопителем неограниченной емкости) растут неограниченно.
Обычно исследование систем проводится в предположении о существовании установившегося режима, непременным условием которого является требование отсутствия перегрузок. Это требование записывается в виде условия:
Nμ
λ

, т.е. загрузка системы должна быть строго меньше единицы:
1
)
1
;
/
min(


N
y

,
(5) где
μ
λ
y
/

– нагрузка системы.
Это условие для системы с одним устройством может быть записано в виде:
b
a

, где
λ
/
1

a
и
μ
/
1

b
– средние значения интервала между поступающими в систему заявками и длительности обслуживания заявок в устройстве соответственно.
Следует обратить внимание на то, что речь идёт о среднем значении интервала между заявками и среднем значении длительности обслуживания.
Если процессы поступления и обслуживания заявок детерминированные, то при отсутствии перегрузки очередь перед устройством не образуется. Такие системы, естественно, не представляют интереса и не рассматриваются в теории массового обслуживания. Очередь появится только в том случае, если процесс поступления заявок в систему и/или процесс обслуживания их в устройстве – случайные.
3.1.5. Характеристики систем с однородным потоком заявок
Рассмотрим характеристики функционирования систем с однородным потоком заявок, представляемых моделями с одним (рисунок 15) или с несколькими (рисунок 17) устройствами.
В систему с интенсивностью
λ
поступает случайный поток заявок, средняя длительность обслуживания которых в одном устройстве равна
b

67
Характеристики функционирования системы обычно рассчитываются для установившегося режима в предположении, что в системе отсутствуют перегрузки. Поскольку, в общем случае, процессы, протекающие в системе, носят случайный характер, то очевидно, что и характеристики функционирования системы представляют собой случайные величины, полное описание которых может быть представлено законами распределений в виде функции или плотности распределения. На практике обычно ограничиваются расчетом нескольких, чаще всего, двух первых моментов распределений случайных характеристик, что дает достаточно полное представление о свойствах исследуемой системы и позволяет эффективно решать задачи проектирования.
Ниже для простоты изложения материала в учебных целях и наглядности будем проводить все расчеты на уровне средних значений (математических ожиданий) характеристик функционирования, понимая, что при проектировании реальных систем на практике могут использоваться числовые моменты более высокого порядка, что приводит к применению сложных и громоздких математических зависимостей, но не меняет принципов проектирования такого рода систем.
В качестве основных характеристик базовых моделей с однородным потоком заявок используются следующие величины:

нагрузка системы:
b
y





/
;
(6) нагрузка представляет собой интегральную характеристику, объединяющую два нагрузочных параметра: интенсивность поступления заявок в систему
λ
(частоту использования ресурса устройства) и среднюю длительность обслуживания заявки в устройстве b (количество потребляемого ресурса устройства при одном обращении);

вероятность потери заявок:
)
(
)
(
lim п
п
T
N
T
N
T




,
(7) где T – время работы системы (наблюдения за системой);
)
(T
N
– число заявок, поступивших в систему за время T;
)
(
п
T
N
– число потерянных заявок
(например, из-за ограниченной ёмкости накопителя или превышения допустимого времени ожидания) за время T;

вероятность того, что заявка будет обслужена:
)
(
)
(
lim
)
1
(
0 0
T
N
T
N
T
п







,
(8) где
)
(
0
T
N
– число обслуженных (непотерянных) заявок за время T, причем
)
(
)
(
)
(
0
п
T
N
T
N
T
N


и
1
п
0




;

производительность системы, измеряемая как интенсивность потока обслуженных заявок:

68





)
1
(
п
0
'



;
(9) для систем с накопителем неограниченной ёмкости, при условии отсутствия перегрузок, вероятность потери заявок
0
п

π
и, следовательно, производительность системы совпадает с интенсивностью поступления заявок в систему:



'
;

интенсивность потока потерянных заявок из-за ограниченной
ёмкости накопителя:





)
1
(
0
п "



;
(10) очевидно, что





"
'
;

коэффициент
загрузки
или просто
загрузка
системы, представляющая собой долю времени, в течение которого система (в случае одноканальной СМО – устройство) работает, то есть выполняет обслуживание заявок:





 

1
;
)
1
(
min
N
y
π
ρ
п
,
(11) где N – число устройств в СМО,
п
π
– вероятность потери заявок, y – нагрузка системы; загрузка принимает значения в интервале [0; 1] (
1 0


ρ
) в отличие от нагрузки, которая может принимать любые положительные значения (
0

y
); в случае одноканальной СМО загрузка может трактоваться как вероятность того, что устройство работает (не простаивает);

коэффициент простоя системы:




1
; коэффициент простоя показывает долю времени, в течение которого система простаивает, и может трактоваться как вероятность простоя;

среднее время ожидания заявок в очереди:w ;
среднее время ожидания зависит от параметров системы и является одной из основных характеристик, на основе которой могут быть рассчитаны остальные характеристики с использованием фундаментальных зависимостей, поэтому часто задача исследования систем с очередями сводится, прежде всего, к определению значения времени ожидания;

среднее время пребывания заявок в системе, складывающееся из времени ожидания w и времени обслуживания b :
b
w
u


;

средняя длина очереди заявок:
w
l


;
(12)

среднее число заявок в системе (в очереди и на обслуживании в устройстве):
u
m


.
(13)
Такие характеристики, как время ожидания и пребывания заявок,длина
очереди и число заявок в системе, в общем случае, представляют собой случайные величины и полностью описываются соответствующими законами

69 распределений. На практике обычно ограничиваются расчетом указанных характеристик на уровне средних значений (математических ожиданий). Для более полного описания эффективности функционирования системы могут быть рассчитаны вторые моменты перечисленных характеристик (дисперсия или коэффициент вариации), показывающие их разброс относительно среднего значения.
Зависимости (12) и (13), связывающие средние значения временных (
w
,
)
u и безразмерных (
l
,
m
) характеристик, известны как формулы Литтла и представляют собой фундаментальные соотношения, справедливые для широкого класса моделей массового обслуживания.
Обычно исследование систем проводится в предположении о стационарности входящего потока заявок и длительности обслуживания. В этом случае условие существования установившегося режима совпадает с условием отсутствия перегрузок в системе и записывается в виде:
1


3.1.6. Характеристики систем с неоднородным потоком заявок
Для базовой модели с неоднородным потоком заявок (рисунок 17), в которую поступают H классов заявок с интенсивностями
H


,
,
1

,
а средние длительности обслуживания равны
H
b
b
,
,
1

, рассчитываются две группы характеристик обслуживания заявок:

характеристики по каждому классу (потоку) заявок;

характеристики объединенного (суммарного) потока заявок.
Характеристики по каждому классу заявок
H
i
,
,
1 

идентичны характеристикам базовой модели с однородным потоком (6) – (13) и в случае накопителей с неограниченной емкостью включают в себя:

нагрузку, создаваемую заявками класса i:
i
i
i
i
i
b
λ
μ
λ
y


/
;

загрузку системы заявками класса i:
)
1
;
/
(
min
N
y
ρ
i
i

, где N - число устройств в СМО;

среднее время ожидания заявок в очереди:
i
w
;

среднее время пребывания заявок в системе:
i
i
i
b
w
u


;

среднюю длину очереди заявок:
i
i
i
w
l


;

среднее число заявок в системе:
i
i
i
u
m


Характеристики объединенного (суммарного) потока заявок
позволяют определить усредненные по всем классам заявок показатели эффективности функционирования системы, а именно:

суммарную интенсивность поступления заявок в систему
(интенсивность суммарного потока):




H
i
i
1

;
(14)

суммарную нагрузку Y и суммарную загрузку R системы:

70



H
i
i
y
Y
1
;









1
;
min
1
H
i
i
R
