2 Требования к до заявок в распределенных вс реального времени

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

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

- невозможность учета приоритета заявки и абонента системы, т.к. по расписанию права передаются между абонентами системы в предположении, что их приоритет однозначно соответствует приоритету заявки. Если в абонент поступает несколько типов заявок, образующих несколько очередей, актуальной становится задача учета приоритета уже очереди заявок абонента. Проиллюстрируем, в какой мере снижает эффективность обслуживания заявок опрос очередей по расписанию. В качестве исследуемого метода децентрализованного управления множественным доступом рассмотрим маркерный метод (метод эстафетной смены задатчика) и регламентируемое для него стандартами 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