Модель системы оперативной обработки

Очевидно, что по аналогии с введенной выше моделью системы реального времени может быть введена и модель системы оперативной обработки, отличающаяся тем, что этой моделью должен учитываться параметр - вероятность занятия ресурса m-ым абонентом (в общем случае < 1) при предоставлении ему права занять ресурс. Качество обслуживания заявок в этом случае можно описать следующими характеристиками: - средняя продолжительность арбитража требования m-го абонента, - средняя продолжительность обслуживания заявки системой.

При этом из (1.1) можем получить модель системы оперативной обработки, которая здесь принимает вид

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

Утверждение. Обслуживание заявки в режиме оперативной обработки корректно, если обслуживание номера поступающей в систему заявки можно охарактеризовать следующим величинами: , , где = при =1 m, и < если m для которых <1 (соответственно и Tam).

Доказательство. При описании системы данной моделью для системы характерно, что вся зависимость от ее загрузки 1 заявки, поступающие от абонентов обслуживаются за исключением времени (n* для n-ой

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

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

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

Будем говорить, что предоставленые абонентам дисциплиной обслуживания права используются ими в равной мере, если для них совпадают отношения / , соответственно, права предоставляемые m-му абоненту, дисциплиной обслуживания используются им в большей мере, чем m’ абонентом, где m, , m m’, если

Очевидно, что права, предоставляемые абонентам дисциплиной обслуживания используются ими в равной мере при условии: =P, .

В предположении, что в проблемно-ориентированной ЛВС требуется обеспечить среднее время реакции системы на входное воздействие , что для М абонентов, задается условием: , где , где - продолжительность решения задачи вычисления, Lm - число информационных взаимодействий с ресурсом средней продолжительностью , необходимое для выработки в системе сигнала реализации на входное воздействие, по аналогии с системой реального времени может быть введен коэффициент избыточности в эффективности обслуживания m-го абонента при реализации бесприоритетной передачи прав абонента в циклическом порядке: ,

где .

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

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

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

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

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

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

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

РАЗДЕЛ 2. МЕТОДЫ ДИСПЕТЧЕРИЗАЦИИ РЕАЛЬНОГО ВРЕМЕНИ

2.1. Требования к ДО заявок в распределенных ВС реального времени

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

К достоинствам первого подхода можно отнести защиту от перегрузок высокоприоритетных заявок [1], за счет «отключения» от ресурса низкоприоритетных заявок при высокой загрузке системы, к недостаткам - невозможность использования в реальном масштабе времени, т. к. для всех заявок, кроме наиболее приоритетной, в общем случае не выполняются условия (1.1). Другими словами, ДООП не может корректно быть использована в системах реального времени.

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

Обслуживанию по расписанию присущи следующие недостатки:

- невозможность защиты от перегрузок высокоприоритетных заявок реального времени. Эта проблема возникает при необходимости обслуживания в одной системе как важных заявок реального времени, так и некоторых заявок оперативной обработки, обслуживание которых несет в системе некоторый второстепенный характер. Внесение этих заявок в расписание также предполагает их обслуживание в реальном времени, соответственно при снижении тем самым эффективности обслуживания высокоприоритетных заявок реального времени;

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

- невозможность учета приоритета заявки и абонента системы, т.к. по расписанию права передаются между абонентами системы в предположении, что их приоритет однозначно соответствует приоритету заявки. Если в абонент поступает несколько типов заявок, образующих несколько очередей, актуальной становится задача учета приоритета уже очереди заявок абонента. Проиллюстрируем, в какой мере снижает эффективность обслуживания заявок опрос очередей по расписанию. В качестве исследуемого метода децентрализованного управления множественным доступом рассмотрим маркерный метод (метод эстафетной смены задатчика) и регламентируемое для него стандартами miniMAP и IEEE 802.4 [8,11] расписание обслуживания в циклическом порядке. Оценку эффективности метода проведем по параметру - информативность смеси в канале межмодульного обмена [9] (характеристика коэффициента пропускной способности канала связи)

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

.

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

Зависимости для случая представлены на рис. 2.1 и для случая - на рис. 2.2. В обоих случаях представлены характеристики для информационных кадров для ЛВС реального времени, регламентируемых стандартами IEEE 802.4 и miniMAP. Длина информационного кадра (в байтах) для IEEE 802.4 определяется следующим образом [7, 10] , где , если , , если (используются заполняющие байты в поле данных). Для miniMAP, ориентированного на применение в управляющих системах, структура кадра более экономична, в частности, отсутствуют заполняющие байты в поле данных, не требуется передачи 8 байт преамбулы для синхронизации приемников (задана только одна скорость передачи по каналу связи), сокращено адресное пространство кадра. На рис. 2.2 кроме того, приведена оценка информативности кадра, применяемого в рамках сетевой технологии асинхронной передачи данных с интеграцией служб ATM [3], где длины информационных кадров фиксированы и составляют (байтов) при (байта), т.е. кадр содержит всего 5 байтов управляющей информации ().

Рис. 2.1

Рис. 2.2

Из рис. 2.1 и 2.2 можно сделать следующие выводы.

1. Современными ЛВС реального времени, в основу построения которых положена реализация рекомендации HDLC на уровне звена передачи данных, крайне неэффективно используется связной ресурс при передаче коротких сообщений, что делает неэффективным их применение в УЛВС (кстати говоря, и стандарт miniMAP не отличается высокой эффективностью использования связного ресурса). Здесь отметим, что альтернативным к HDLC можно считать подход, как раз и разработанный для задач управления, регламентируемый стандартами MIL-STD-1553A/B, где передача данных ориентирована не на передачу байтов, а на передачу слов [7,9], где каждое слово содержит признак команда/данные, код команды, что позволяет идентифицировать принятое слово без учета порядка его поступления в пакете.

2. Для ИЛВС реального времени, где требуется в реальном масштабе времени обмениваться большими массивами информации, обеспечивая открытость системы, ЛВС IEEE 802.4 и miniMAP, как следует из рис. 2.2, могли бы быть эффективны. Однако реальный масштаб времени можно обеспечить в системе, если оградить связной ресурс от продолжительного занятия парой абонентов (в противном случае не обеспечить обслуживание в реальном времени заявок от других абонентов). Это приводит к необходимости уменьшения длины информационного пакета для таких приложений ЛВС. В частности, современная концепция ATM задает фиксированную длину пакета (ячейки) 53 байта, что уже требует реализации и альтернативных подходов к построению информационных кадров, в частности кадр ATM содержит лишь 5 управляющих байтов, включая адресное пространство. Рис. 2.2 иллюстрирует преимущество ATM по данному параметру над другими асинхронными сетевыми технологиями, в основе звена передачи данных которых находится HDLC, что обеспечивает эффективность данного стандарта для ЛВССРВ и ЛВСИС. Зависимости - информативности смеси, учитывающей потери пропускной способности канала, связанные с передачей маркера для опроса очередей по расписанию (в рассматриваемом случае - бесприоритетному) для ЛВС IEEE 802.4 и для сетевой технологии ATM представлены соответственно на рис. 2.3 и 2.4. Для ЛВС IEEE 802.4 учитываем стандартную длину маркера 17 байтов [8], для ATM исследуем некоторую гипотетическую модель - принимаем минимально возможную длину, определяемую длиной адреса абонента [ ], т.е. в предположении, что , составляющую 1 байт. Из приведенных рисунков видим, что даже при гипотетически идеальных параметрах системы передача маркера, необходимая для реализации передачи прав по расписанию, существенно сказывается на эффективности межмодульных взаимодействий, что подтверждает низкую эффективность ДОР для ЛВСРВ.

Рис. 2.3

Рис. 2.4

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

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

- эффективная реализация расписаний реального времени, которая позволит получать эффективные приоритетные расписания;

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

Основу реализации обслуживания по приоритетным расписаниям в ЛВС сегодня составляет построение SPT- расписаний (короткая работа здесь обслуживания заявки общим ресурсом вперед).

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

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

или при сопоставимости и

При условии

Заметим, что, если для данной задачи не будут введены приоритеты, получим

соответственно при сопоставимости и имеем

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

Однако, на практике данная возможность практически не используется, что вызвано следующим. При построении информационных систем (в том числе и на средствах передачи информации ЛВС) приоритетность обслуживания определяется не интенсивностью поступления заявок на обслуживание, а важностью обрабатываемой информации. Если же обратиться к стахостической мере количества информации I [... ], для которой характерно уменьшение обратно пропорционально вероятности ее появления Р (на практике используется логарифмическая мера) можем сделать вывод, что более высокий приоритет следует назначать абонентам, обрабатывающим более важную информацию, реже поступающую систему, что противоречит изложенному выше подходу к назначению приоритетов абонентам ЛВС. Это объясняет то, что данный подход (реализация SPT-расписаний в ЛВС), несмотря на внешнюю привлекательность, на практике не используется.

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

что обуславливает эффективность обслуживания в первую очередь (с приоритетом) наиболее важной заявки.

2.2. Концепция обслуживания в реальном времени с динамическими приоритетами

2.2.1. Основа построения приоритетных расписаний

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

Утверждение. В любой момент времени ОП не должен совпасть у заявок из нескольких очередей.

Доказательство. Если данное условие не будет выполнено, то в системе неминуем конфликт при занятии ресурса, т.к. несколько абонентов одновременно получат право занять ресурс после его освобождения. Для описания ДООП используем матрицу приоритетов (МП), представляющую собою квадратную матрицу размерности по числу M абонентов [1]. Элемент матрицы задает ОП абонента i по отношению к j: 0 - нет приоритета, 1 - есть. Для описания ДОР (в общем случае ДОСП) используем граф изменения матрицы ОП в моменты времени занятия ресурса в соответствии с расписанием. Пример графа бесприоритетной ДОР, реализуемой методом динамической смены ОП, для случая , цикл расписания которой имеет вид (1, 2, 3, 4), представлен на рис. 2.5. Бесприоритетность расписания обеспечивается тем, что каждый абонент входит в расписание равное число раз, в общем случае может быть более одного, например (1, 1, 2, 2, 3, 3, 4, 4).

Рис. 2.5

Требования к МП. Элементы МП должны удовлетворять следующим требованиям:

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

- если , то , т.е., если заявки класса i имеют приоритет по отношению к заявкам класса j, то последние не могут иметь приоритет по отношению к заявкам i;

- в МП не должны совпасть не любые две строки i, i', не любые два столбца j, j'; , , , .

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

Доказательство. В противном случае получим совпадение значений , т.е. при совпадении значений параметров получаем равный приоритет заявок - совпадают .

Изменение ОП заявок по расписанию в процессе функционирования системы должно быть реализовано по следующему правилу.

Правило изменения ОП. ОП в рамках ОР однозначно задаются расписанием, где в каждый момент времени приоритет заявок соответствует порядку передачи полномочий, исключая повторные передачи прав одной очереди в цикле ОР, например для расписания (1, 2, 1, 3) в момент - ОП [1, 2, 3], в - [2, 1, 3], в - [1, 3, 2], в - [3, 1, 2].

Для ДО с динамическими ОП, изменяемыми по расписанию, функция приоритетности заявки m, имеет вид

,

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

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

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

1. В любой момент времени функционирования системы матрице приоритетов ставится во взаимно однозначное соответствие матрица кодов ОП (МКП). Строки МКП соответствуют строкам МП, а столбцы задают код ОП очереди заявки. Пример МКП, в предположении, что «1» в разряде кодового слова приоритетнее «0» (по «1» права передаются, по «0» - нет), и что приоритет разряда кода убывает по мере возрастания его порядкового номера, приведен на рис. 2. 6.

Рис. 2.6

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

Рис. 2.7

3. При построении кодов ОП всех очередей заявок в процессе функционирования системы применяется приведенное ранее правило задания ОП заявок в графе смены МП.

4. При управлении доступом к ресурсу должно осуществляться поразрядное (начиная с более приоритетных разрядов) сравнение кодов ОП заявок, затребовавших к данному моменту времени ресурс, с «отключением» по каждому разряду менее приоритетных заявок - при однозначном кодировании заявок получаем бесконфликтное занятие ресурса. Утверждение. Метод кодового управления на всем интервале изменения загрузки системы имеет эффективность не ниже, чем методы опроса очередей.

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

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

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

Прежде всего, рассмотрим возможности построения ДО со смешанными приоритетами (ДОСП) или комбинированных ДО - ОР и с ОП. Реализация подобных возможностей позволит совместить в единой системе альтернативные подходы к обслуживанию, достигающие совершенно противоположные цели, соответственно - обслуживание по расписанию с целью реализации обслуживания заявок в реальном времени, обслуживание с ОП, позволяющее обеспечивать защиту от перегрузок высокоприоритетных заявок, что необходимо для эффективной реализации альтернативных приложений ЛВСКО. Данные возможности в одной системе позволяет получать изложенный принцип реализации ДОР, отличающийся тем, что в любой момент функционирования системы реализуется ДООП, с условием, что ОП заявок изменяются при каждом занятии ресурса системы. Однако, в процессе функционирования системы могут изменяться ОП не всех заявок, причем как низкоприоритетных, так и высокоприоритетных, либо группы очередей заявок могут организовывать свои очередности (расписания) смены ОП. Данные возможности, открываемые реализацией ДОР, посредством смены ОП в процессе функционирования системы, положены в основу идеи реализации ДОСП, соответственно получаемого в его рамках ряда ДО. Примеры графов ДОСП, иллюстрирующих альтернативные способы задания ОП, соответственно для защиты от перегрузок заявок реального времени (ОП неизменяем для низкоприоритетных заявок) и с целью выделения внеочередных заявок (ОП неизменяем для низкоприоритетных заявок), для случая представлены на рис. 2.8, на рис. 2.8.а - 1 и 2 очереди заявок имеют ОП над 3 и 4, а 3 над 4, 1 и 2 образуют бесприоритетное ОР (1, 2), на рис. 2.8.б - 1 очередь заявок имеет ОП над остальными, 2 и 3 над 4, а 2 и 3 бесприоритетное ОР между собой (2, 3). Обозначим, соответственно ДОСП [(1, 2), 3, 4] и [1, (2, 3), 4], где в круглых скобках отмечен цикл ОР, в квадратных (будем называть это циклом ДОСП) - ОП заявок, упорядоченный в порядке записи. В общем случае цикл ДОСП может содержать несколько циклов ДОР, например для [(1, 2, 1, 3), 4, 5, (6, 7, 8)]. При отсутствии в ДО цикла ОР, например [1, 2, 3, 4], имеем ДООП.

Рис. 2.8

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

С учетом сказанного, построение ДОСП (ОР и ОП) в общем случае реализуется следующим образом:

- заявки подразделяются на три большие группы: внеочередные, РМВ, бесприоритетные;

- внеочередным заявкам присваиваются максимальные ОП - при необходимости обслуживать их с равным приоритетом, либо в какой-нибудь очередности, для них реализуется расписание (ОР);

- для заявок реального времени строится ДОР (приоритетная, либо бесприоритетная), их ОП в любой момент времени ниже ОП внеочередных заявок;

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

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

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

- если в основе приоритетного обслуживания лежит учет, в первую очередь, приоритета заявки, младшие (более приоритетные) [ ] разрядов кодового слова, где Q - число уровней приоритета заявок, отводятся для кодирования приоритета заявок, старшие [ ] разрядов под кодирование приоритета абонента;

- если в основе приоритетного обслуживания лежит учет, в первую очередь, приоритета абонента, младшие [ ] разрядов кодового слова, отводятся для кодирования приоритета абонентов, старшие [ ] разрядов - под кодирование приоритета заявки.

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

Рис. 2.9

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

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

Рис. 2.10

Ранее отмечалось, что на практике в ЛВС не реализуются ДО с абсолютными приоритетами, что вызвано существенными временными потерями и увеличением сложности аппаратурной реализации прерывания взаимодействий по каналу связи в распределенной ВС. В сосредоточенных же системах, где эффективна реализация приоритетного обслуживания (например, в операционных многозадачных системах реального времени), как правило, возникает необходимость реализации в системе, наряду с рассмотренными возможностями, обслуживание с абсолютными приоритетами. Совместить такие альтернативные способы обслуживания опять же возможно с применением концепции многоуровневых приоритетов. Выделим старшие уровни (младшие разряды кода приоритета) для кодирования типа приоритета, например «1» - абсолютный приоритет, «0» - относительный. Если многоуровневый приоритет и так учитывает несколько видов относительного приоритета, можно ввести и несколько уровней типов приоритетов (абсолютный/относительный), например, в соответствии с МКП, приведенной на рис. 2.11, где приоритет заявки выше чем приоритет абонента ВС, и приоритет заявки и приоритет абонента могут быть как относительными, так и абсолютными, что задается в разрядах «тип приоритета» кода приоритета. Совмещение обслуживания с относительными и абсолютными приоритетами становится возможным благодаря тому, что при кодовом управлении при арбитраже по каждому разряду кода всеми абонентами фиксируется с каким кодом приоритета абонент (или заявка) занимает ресурс. В частности, при арбитраже по разрядам кода, задающим тип приоритета, абонентами фиксируется был ли в канале «0» или «1», что будет основанием (если канал занят заявкой, либо абонентом с «0» значением в соответствующем разряде кода) для прерывания взаимодействия при поступлении соответственно заявки с абсолютным приоритетом, либо заявки у абонента, имеющего абсолютный приоритет.

Рис. 2.11

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

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

- внешняя очередь имеет приоритет перед внутренней, т.е. пока есть заявки во внешней очереди, именно они, а не заявки из внутренней очереди, поступают на обслуживание;

- внутренняя очередь имеет преимущество перед внешней.

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

Обобщая алгоритм ПЗП, в предположении, что система может содержать некоторое число i, внутренних очередей, приходим к так называемому многоуровневому алгоритму - МА, действие которого основано на применении понятия уровней достигнутого обслуживания, где каждый уровень характеризуется некоторым промежутком времени полученного обслуживания. В этом случае чем больше квантов обслуживания получила та или иная заявка, тем на более высокий уровень она попадает, из которого выбирается на обслуживание реже/чаще.

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

Классификация методов обслуживания с многоуровневыми относительными приоритетами при кодовом управлении доступом к общим ресурсам представлена на рис.2.12.

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

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

3. Механизм кодового управления доступом к общим ресурсам можно рассматривать как единый высоко эффективный унифицированный механизм реализации ДО для альтернативных приложений ВС.

Рис. 2.12

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

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

Замечания.

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

2. Применительно к ЛВС отметим, что обслуживание с абсолютными приоритетами и с многоуровневым алгоритмом здесь предполагают обмен большими массивами данных абонентами ЛВС, что противоречит принципам функционирования ЛВСРВ. Вместе с тем, рассматриваемые возможности могут использоваться в ЛВСОО и ЛВСКО, где реализуются режимы оперативной обработки, допускающие передачу больших массивов данных по каналу связи ЛВС.

В завершении изложения методов обслуживания заявок в ВС с многоуровневыми приоритетами, в основе которых находится реализация исследуемых принципов обслуживания с динамическими приоритетами и кодовым управлением доступом к общим ресурсам, рассмотрим возможности адаптивного управления множественным доступом. В этих приложениях также может использоваться концепция обслуживания с многоуровневыми приоритетами. Идея адаптивного управления состоит в возможности изменения ДО (в частности изменение расписания передачи прав, изменение в назначении смешанных приоритетов, например вывод/ввод заявки в/из расписание) при превышении некоторого заданного функционированием системы, прежде всего в реальном времени, порогового значения времени ожидания обслуживания заявками. С целью адаптивного управления в многоуровневом ОП выделяются приоритетные разряды адаптивного управления. При функционировании системы с исходными приоритетами, в этих разрядах кодов ОП «0» значения. Если в системе появляются заявки (не зависимо у каких из абонентов ВС), для которых превышено установленное для них пороговое значение в продолжительности обслуживании, при очередном арбитраже требований ресурса в рассматриваемом(мых) разряде кода ОП появляется «1» значение, удерживаемое в течение всего времени функционирования системы с превышением заданных пороговых значений для продолжительности ожидания обслуживания заявок. При появлении «1» в разряде(ах) адаптивного уровня кода ОП, что является необходимым условием для всех абонентов использовать при арбитраже текущее значение кода ОП уже не для исходной, а для некоторой дополнительной(ых) ДО, которая реализуется (вырабатываются текущие значения кодов ОП при каждом занятии ресурса) в ВС одновременно с исходной, а используется по мере необходимости. Число разрядов в уровне адаптивного управления задается максимальным числом пороговых значений для продолжительности ожидания обслуживания заявок в системе , следующим образом [ ].

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

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

Рис. 2.13

2.2.5. Классификация ДО с динамическими приоритетами для ЛВС

Классификация возможных ДО для ЛВС, получаемых в рамках изложенной концепции кодового управления обслуживанием с динамическими приоритетами, изменяемыми по расписанию, представлена на рис. 2.14. Отметим, что здесь выделены классификационные признаки и соответственно приведена классификация ДО именно с позиции исследуемой концепции обслуживания. В рамках же каждой полученной дисциплины можно рассмотреть известные классификационные признаки - по виду стратегии обслуживания (вентильная, ординарная, исчерпывающая) и др. [1, 5, 6].

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

Рис. 2.14

2.3. Понятие и свойства канонического расписания реального времени

Пусть имеем R различных приоритетов абонентов в системе, обслуживаемых по расписанию, соответственно , и абонентов системы имеют равный r приоритет : , , . Таким образом система содержит M абонентов, которым соответствует R уровней приоритетов.

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

С учетом сформулированной задачи синтеза расписаний реального времени дадим определение канонического (в данном случае - оптимального) расписания. Под каноническим расписанием будем понимать расписание, обеспечивающее минимальные значения характеристик в рамках заданного разбиения M абонентов на R уровней приоритета, получаемое поочередной передачей прав абонентам в рамках радиального графа.

Под радиальным графом передачи прав понимается граф, содержащий вершин приоритета r, , причем в каждую вершину нижестоящего приоритета входит только одна дуга от одной вершины вышестоящего приоритета, из каждой вершины всех приоритетов, кроме R -го выходит [ ] дуг, где [ a ] - есть большее целое числа a, все вершины приоритета R соединяются дугой с вершиной приоритета 1 (из вершин R выходит только одна дуга) - в этом случае дуга направлена в сторону вершины 1, в то время как в остальных случаях дуга направлена в вершину, соответствующую пользователю с более низким приоритетом. Радиальный граф передачи прав представлен на рис. 2.15.

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

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

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

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

3. Если не осталось на рассмотрении вершин r -го приоритета через которые не прошел по крайней мере один путь (для невырожденного графа прежде всего это приоритет 2) из проведенных r путей (2 путей), дуга проходит как и первая, но уже через другие вершины приоритета и т.д., вплоть до соединения путями вершины первого приоритета со всеми вершинами приоритета R.

4. Все вершины R приоритета соединяются дугой с вершиной высшего приоритета.

5. Нумеруются пути в соответствии с очередностью их получения. Именно в соответствии с этой нумерацией (с этим порядком) в системе должны передаваться полномочия на доступ к ресурсу.

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

Иллюстрация получения поочередной передачи прав, с использованием приведенной процедуры представлена на рис. 2.16.

Рис. 2.16

Свойства канонических расписаний реального времени.

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

,

Поиск по сайту: