НАУКА и ОБРАЗОВАНИЕ

А. Ю. Щеглов, д-р техн. наук, проф., СПб ГИТМО (ТУ)

Исследование эффективности обслуживания заявок в ЛВС реального времени по приоритетным расписаниям

Излагаются результаты проведенных исследований оценки эффективности приоритетного обслуживания заявок в реальном времени, в том числе в ЛВС, и эффективности применения предложенного принципа ко­дового управления множественным доступом для реализации приоритетных расписаний реального времени. Вводится критерий синтеза приоритетных расписаний реального времени.

Введение

На сегодняшний день существенно возрастает доля вычислительных систем, требующих обслуживания заявок в реальном масштабе времени. Помимо проблемно-ориентированных систем, прежде всего управляющих, к подобным системам сегодня относят и системы общего назначения, характеризуемые обработкой сигналов реального времени (речь, подвижное изображение и т. д.), среди которых возрастает роль систем с интеграцией обслуживания. В эти системы поступают заявки реального времени и оперативной обработки. В подобных системах возникает проблема, связанная, во-первых, с возможностью совмещения в единой системе на одних и тех же принципах альтернативных методов обслуживания заявок и, во-вторых, с эффективным обслуживанием заявок реального времени по расписаниям, прежде всего — приоритетным. С точки зрения эффективности реализации наибольшая сложность связана с реализацией расписаний в распределенных вычислительных системах или локальных вычислительных сетях (ЛВС). В [1] автором изложены принципы совмещения альтернативных способов обслуживания заявок в одной технической системе, в [2] — принципы реализации данного подхода в ЛВС, в [3] — подход к формализованному синтезу приоритетных расписаний. В данной статье автором исследуется эффективность реализации в ЛВС приоритетных расписаний, формализуются критерии синтеза расписаний.

Модель системы реального времени. Критерии обслуживания заявок в реальном времени

Так как основными требованиями к качеству построения и функционирования вычислительных систем (ВС) реального времени является выполнение временных ограничений в обслуживании заявок, то распределенную ВС реального времени ЛВС можно описать детерминированной моделью. К временным параметрам обслуживания заявок относятся величины:

·         — продолжительность занятия ресурса m-м, m = 1, ..., М, абонентом для информационного взаимодействия с ресурсом;

·         — продолжительность передачи прав (или полномочий на занятие ресурса) m-му абоненту после освобождения ресурса в системе;

·         — коэффициент частоты занятия ресурса i-м абонентом (i = 1, ..., М) относительно m-гo, i ≠ m. Качество обслуживания заявок можно описать характеристиками:

·         — продолжительность арбитража (или управления множественным доступом) требования m-го абонента с момента появления заявки до момента предоставления абоненту права занять ресурс или продолжительность ожидания заявкой обслуживания;

·         — продолжительность обслуживания заявки системой.

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

С учетом сказанного получаем модель системы реального времени:

                       (1)

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

В качестве параметра приоритетности обслуживания заявок в реальном времени может быть вве­дена количественная оценка — относительный уровень приоритетности реального времени (или относительный приоритет реального времени) двух абонентов m и m’;m, m'= 1, ..., М, под которым

понимается отношение . В системе реализуется бесприоритетная дисциплина обслуживания требований ресурса, если для любых двух абонентов системы m, m' выполняется условие:  если , приоритет m-го абонента  выше, в противном случае — ниже.

Системой (1) в общем случае определяются три способа задания приоритетного обслуживания заявок в реальном времени и соответственно их комбинации:

1) изменением параметров ;

2) изменением параметров ;

3) изменением параметров .

При этом очевидно, что выбор способов (и их комбинаций) задания приоритетов абонентов определяется соотношением параметров   и . При >> целесообразно использовать способы 1 и 3, при сопоставимости  и  — соответственно способы 1 и 2.

Условия эффективности приоритетного обслуживания в реальном времени

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

Пусть в систему реального времени поступает М типов заявок на обслуживание (каждый тип заявок в распределенной системе является принадлежностью соответствующего абонента), условием корректности функционирования системы будет выполнение М неравенств: , где  — гарантированная продолжительность реакции системы на воздействие, реализуемое в системе;  — задаваемое условиями функционирования ограничение на параметр . Требуемая реактивность системы по каждому m-му воздействию определяется следующими временными характеристиками обслуживания заявок системой:  — продолжительностью собственно решения задачи m-м вычислителем (абонентом) по заранее известной программе (здесь для простоты считаем, что каждым абонентом обрабатывается только один соответствующий тип воздействий); числом информационных взаимодействий с ресурсом , имеющих максимальную продолжительность , необходимым для выработки адекватного воздействия в соответствии с заранее известным алгоритмом (далее для простоты будем считать, что =1, m = 1,…, M). Тогда гарантарованная продолжительность реакции системы на m-е воздействие

Рассмотрим следующие возможные случаи.

1. Пусть требуется обеспечить равное время реакции системы на все воздействия  для всех m, причем m = 1,..., М воздействий совпадают. В этом случае идеальным является бесприоритетное обслуживание — в реальном времени это передача полномочий в циклической очередности.

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

Например, в ЛВС с интеграцией служб, в частности ATM, по одним и тем же каналам связи поступает речь, радиосигнал и подвижное изображение. Для речевого сигнала, полоса пропускания частот которого F = 0  4000 Гц по теореме Котельникова (T= 0,5/F) получаем  = 125 мкс, для передачи радиосигнала F = 0  5000 Гц имеем  = 34 мкс, для качественной же передачи подвижного изображения (телевидение) соответственно F = 0 5 МГц уже имеем  = 104 нс. В

управляющих ЛВС параметры  для различных заявок могут различаться еще существеннее.

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

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

                       (2)

Оценим, какой выигрыш для распределенных систем может дать реализация в системе приоритетного обслуживания, где приоритет вводится в целях эффективного использования производительности общего ресурса (при связном ресурсе — эффективного использования пропускной способности канала связи). С учетом  = 1 для всех М абонентов для системы с бесприоритетной дисциплиной обслуживания (характеристика обозначена БП) требований ресурса имеем

где  — продолжительность занятия ресурса абонентом с учетом потерь времени на передачу ему системой прав занять ресурс; считаем, что  совпадают для всех М абонентов (очередей заявок).

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

где ВП, НП — соответственно характеристики абонентов с высоким и низким приоритетом). Тогда выигрыш для более приоритетного абонента составит

(для всех m справедливо ).

Однако наряду с выигрышем для более приоритетного абонента имеем проигрыш для менее приоритетных абонентов

откуда результирующий выигрыш в производительности ресурса

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

;

соответственно для приоритетного обслуживания при двух уровнях приоритетности получаем

соответственно получаем результирующий выигрыш в производительности системы

                                                            (3)

Зависимости  для различных М при М = 16; 64 представлены на рис. 1, из которого делаем следующие выводы.

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

Рис. 1.

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

3. При k > 1 из (2) имеем  — отсутствует выигрыш как таковой, что может иметь место для некоторых приложений сосредоточенных систем, когда , где теряет актуальность задача приоритетного обслуживания заявок в целях эффективного использования ресурса абонентами системы. В данных приложениях систем реального времени применяются иные методы параллельной обработки, в частности крупноблочного распараллеливания, при бесприоритетном обслуживании заявок на доступ к ресурсу (в реальном времени — обслуживание в циклическом порядке), который здесь уже не является "узким местом" системы. Как следствие, здесь, как правило, реализуется принцип однородности структуры.

Замечание. Нетрудно показать, что предельным случаем системы, "узким местом" которой будет общий ресурс, можно считать многозадачную операционную систему реального времени (кстати говоря, сосредоточенную). Действительно, общим ресурсом здесь является квант процессорного времени, который и является "узким местом" многозадачной системы. Поэтому при использовании в системе распараллеливания по функциям (что, как правило, имеет место в специализированных операционных системах, реализуемых в задачах управления) возникает аналогичная задача приоритетного обслуживания в целях эффективного использования ресурса. Здесь также имеют место два способа задания приоритетов: изменением величины процессорного кванта для приоритетной задачи, изменением частоты опроса очередей заявок (не в циклическом порядке) от отдельных задач. Первый подход ограничен нарушением параллельности обработки, что недопустимо в системах реального времени (кстати говоря, именно эти же соображения приводят к уменьшению длины пакета данных в сетевой технологии ATM до 53 байт), второй имеет недостатком наличие больших временных затрат на опрос очередей по расписанию. Поэтому, как и в ЛВС, сегодня на практике реализуется бесприоритетный опрос очередей (например, используемая в ОС QNX дисциплина RR), т. е. в системах практически отсутствуют возможности эффективной диспетчеризации в реальном времени при распараллеливании задач по функциям. Другими словами, рассматриваемые в учебном пособии принципы диспетчеризации могут эффективно использоваться и в этих приложениях систем реального времени параллельной обработки —в различных приложениях как распределенных, так и сосредоточенных систем.

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

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

Выше речь шла о проблемно ориентированных ЛВС реального времени; относительно ЛВС реального времени общего назначения отметим, что здесь реализуется аналогичная идея приоритетного обслуживания, однако так как отсутствует алгоритм функционирования — невозможно задать параметр , то в качестве ограничений следует уже рассматривать не параметр , задаваемый в проблемно-ориентированных ЛВС для всех М абонентов, а параметр . При различии  для М абонентов могут вводиться приоритеты в целях эффективного использования "узкого места" — связного ресурса ЛВС.

Оценка эффективности применения метода кодового управления множественным доступом к ресурсам в ЛВС реального времени

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

Проиллюстрируем, в какой мере снижает эффективность обслуживания заявок опрос очередей по расписанию. В качестве исследуемого метода децентрализованного управления множественным доступом рассмотрим маркерный метод (метод эстафетной смены задатчика) и регламентируемое для него стандартами miniMAP и IEEE 802.4 расписание обслуживания в циклическом порядке. Оценку эффективности метода проведем по параметру I_s — информативности смеси в канале межмодульного обмена (характеристика коэффициента пропускной способности канала связи):

где  — частота посылок i-го типа в общем потоке сообщений; S — общее число типов посылок i= 1,..., S; n_i — число информационных бит в посылке i-го типа; N_i — общее число битов в посылке i-го типа. Влияние на эффективность межмашинного взаимодействия передачи полномочий между абонентами системы на занятие ими общего ресурса по расписанию проиллюстрируем на изменении параметра I_s, позволяющего оценить информативность смеси при одном — информационном кадре в системе I_s=1 - ( и соответственно при двух кадрах — информационный кадр и маркер I_{s = 2}. При этом будем говорить, что в системе одновременно может быть m из М абонентов (m = 1,..., М), активизированных на информационное взаимодействие. В этом случае маркер в среднем будет выдан в канал  = 2 раз для предоставления абоненту права занять ресурс, в то время как информационный кадр в этом случае будет передан единожды, где

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

Зависимости I_{s = 1} = f(n) для случая n = 1,..., 10 представлены на рис. 2 и для случая n = 10,..., 1000 — на рис. 3. В обоих случаях представлены характеристики для информационных кадров для ЛВС реального времени, регламентируемых стандартами IEEE 802.4 и miniMAP. Длина информационного кадра (в байтах) для IEEE 802.4 определяется следующим образом: N_i = n/(R + 31), где R = 43, если n ≤ 43 и R = n, если n > 43 (используются заполняющие байты в поле данных). Для miniMAP, ориентированного на применение в управляющих системах, структура кадра более экономична, в частности, отсутствуют заполняющие байты в поле данных, не требуется передачи 8 байт преамбулы для синхронизации приемников (задана только одна скорость передачи по каналу связи), сокращено адресное пространство кадра. На рис. 3 кроме того приведена оценка информативности кадра, применяемого в рамках сетевой технологии асинхронной передачи данных с интеграцией служб ATM, где длины информационных кадров фиксированы и составляют n₁ = 48 байт при N_i = 53 байт, т. е. кадр содержит всего 5 байт управляющей информации (I_s=1 = 48/53 = 0,91).

Рис. 2.

Рис. 3

Зависимости I_{s = 2} = f(m/M) — информативности смеси, учитывающей потери пропускной способности канала, связанные с передачей маркера для опроса очередей по расписанию (в рассматриваемом случае — бесприоритетному) для ЛВС IEEE 802.4 и для сетевой технологии ATM представлены соответственно на рис. 4 и 5. Для ЛВС IEEE 802.4 учитываем стандартную длину маркера 17 байт, для ATM исследуем некоторую гипотетическую модель — принимаем минимально возможную длину, определяемую длиной адреса абонента [log2.M], т. е. в предположении, что М = 256, составляющую 1 байт. Из приведенных рисунков видим, что даже при гипотетически идеальных параметрах системы передача маркера, необходимая для реализации передачи прав по расписанию, существенно сказывается на эффективности межмодульных взаимодействий, что подтверждает низкую эффективность обслуживания по расписанию для ЛВС.

Рис. 4.

Рис. 5.

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

Важной является оценка выигрыша заявок реального времени именно по параметру . В

предположении, что такие заявки имеют бесприоритетное обслуживание, причем ,соответственно совпадают для всех М (бесприоритетное расписание) абонентов, для системы, в которой из М абонентов S обслуживаются в реальном времени — в циклическом порядке, остальные — с более низким относительным приоритетом, реализуется дисциплина [(1, 2, 3, ..., S - 1, S), S + 1, S+ 2,..., М]. Имеем выигрыш, получае­мый для заявок реального времени или соответственно  в относительных единицах . Это говорит о том, что в предположении  за счет введения относительного приоритета для обслуживания заявок оперативной обработки (не реального времени) требования к качеству обслуживания заявок реального времени можно обеспечить с выигрышем в производительности ресурса системы (в рассматриваемом случае — "узкого места") в M/S раз, причем в отличие от метода построения приоритетного расписания здесь выигрыш может быть получен и для системы реального времени с бесприоритетным обслуживанием.

В предположении, что , и  имеем . Зависимости  представлены на рис. 6, который иллюстрирует целесообразность приоритетного (в смысле ДОСП) обслуживания заявок реального времени при условиях, во-первых, k ≤ 1, во-вторых, S << М.

Рис. 6.

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

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

* * *

В статье рассмотрены вопросы эффективности обслуживания заявок в реальном времени, введе­ны количественные показатели дисциплины приоритетного облслуживания заявок в реальном вре­мени, сформулирован критерий синтеза приоритетных расписаний реального времени. Проведено исследование эффективности реализации расписаний реального времени в распределенных вычислительных системах или ЛВС (прежде всего управляющих и с интеграцией служб), показано, что в данных приложениях вычислительных систем, во-первых, как правило, актуальна задача реализации приоритетных расписаний реального времени в целях эффективного использования общих сетевых ресурсов и, во-вторых, подобные дисциплины обслуживания в распределенных ВС или ЛВС могут быть эффективно реализованы предложенными методами кодового управления, обзор которых приведен в [2].

Список литературы

1. Щеглов А. Ю. Принципы обслуживания заявок в вычислительных системах с динамическими относительными приоритетами // Информационные технологии. 1997. № 8. С. 17—21.

2. Щеглов А. Ю. Принципы унификации методов кодового управления множественным доступом к ресурсам вычислительных систем и ЛВС // Информационные технологии. 1998. № 2. С. 20-25.

3. Щеглов А. Ю. Метод синтеза расписаний обслуживания заявок для распределенных вычислительных систем и ЛВС реального времени // Информационные технологии. 1997. № 10. С. 22-27.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, № 12, 1998

ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ И СЕТИ

Ключевые слова: Локальные вычислительные сети, системы реального времени, приоритетное обслуживание, критерии обслуживания, кодовое управление, распределение ресурсов.