Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Кафедра ВТ ИТМО (ТУ), 197101, Санкт-Петербург, Саблинская ул., 14
Министерство общего и профессионального образования РФ
Санкт - Петербургский государственный институт точной механики и оптики
(технический университет)
А. Ю. ЩЕГЛОВ
МЕТОДЫ ДИСПЕТЧЕРИЗАЦИИ ЗАЯВОК НА ОБСЛУЖИВАНИЕ
В ЛВС РЕАЛЬНОГО ВРЕМЕНИ
Учебное пособие
Санкт-Петербург 1997
УДК 681.324
Щеглов А. Ю. Методы диспетчеризации заявок на обслуживание в ЛВС реального времени. Учебное пособие. - СПб. : ИТМО, 1997. - 77 с.
Рассматриваются проблемы диспетчеризации заявок на обслуживание в управляющих и информационных локальных вычислительных сетях (ЛВС) реального времени, в основе параллельной обработки которых находится принцип распараллеливания по функциям; ЛВС оперативной обработки и комбинированного обслуживания, в части синтеза дисциплин обслуживания и методов децентрализованного управления множественным доступом к общим ресурсам при многоточечном подключении абонентов к каналу связи. Иллюстрируется общность требований к обслуживанию заявок в реальном времени для современных управляющих и информационных ЛВС, для ЛВС комбинированного обслуживания и с интеграцией служб связи, рассматриваемых в рамках сетевой технологии ATM.
Излагается современная концепция обслуживания с динамическими относительными приоритетами, изменяемыми по расписанию при каждом занятии общего связного ресурса, при кодовом управлении множественным доступом к ресурсам. Рассматриваются и исследуются принципы обслуживания по расписаниям - в реальном времени, с относительными, со смешанными и с многоуровневыми приоритетами, учитывающими в одной системе приоритеты заявок и абонентов системы в реальном времени и в режиме оперативной обработки данных. Излагаются принципы комбинирования и унификации альтернативных дисциплин обслуживания в рамках рассматриваемого подхода.
Рассматриваются вопросы повышения эффективности кодового управления множественным доступом, за счет оптимального кодирования относительных приоритетов. Вводится понятие и рассматриваются методы динамического кодирования относительных приоритетов, изменяемых по расписанию.
Рассматриваются альтернативные подходы к реализации передачи в системе прав на занятие ресурса при кодовом управлении доступом, излагаются принципы комбинирования и унификации альтернативных методов.
Рецензенты: докт.техн.наук, профессор Т.И.Алиев
докт.техн.наук, профессор А.Ю.Тропченко
Одобрено на заседании кафедры вычислительной техники 11 марта 1997 г. , протокол № 2.
© Санкт-Петербургский государственный институт точной механики и оптики (ТУ), 1997
До недавнего времени опережающее развитие в вопросах создания и использования распределенных вычислительных систем (ВС) имели сосредоточенные (или мультипроцессорные) ВС, отличающиеся высокой эффективностью межмодульных взаимодействий по параллельной системной шине, либо высокоскоростным коммутируемым каналам (транспьютерные системы). Эффективность функционирования сосредоточенных систем, в основе построения которых, как правило, находится принцип однородности структуры, определяется эффективностью языков параллельного программирования. Принципиально иные особенности имеют распределенные ВС, отличающиеся использованием последовательных каналов связи, подверженных воздействию помех и, как следствие, низкой эффективностью межмодульных взаимодействий. Такие системы называются вычислительными сетями, особое место среди которых занимают локальные вычислительные сети (ЛВС), отличающиеся небольшой территорией охвата и, как следствие, применением ориентированных на такую территорию средств и методов передачи данных. Низкая эффективность межмодульных взаимодействий в ЛВС накладывает ограничения на способы построения распределенных коллективов вычислителей. Здесь эффективен уже способ распараллеливания задач по функциям, где каждый вычислитель системы самостоятельно решает свою часть (функцию) общей задачи ВС, чем минимизируется число межмодульных взаимодействий при решении задачи системой. В качестве условия синтеза алгоритма параллельной обработки здесь рассматривается минимизация числа межмодульных взаимодействий абонентов системы.
Особое место среди ЛВС занимают проблемно-ориентированные ЛВС (ЛВСПО), в частности ЛВС, используемые в задачах управления (УВС) - в системах автоматического управления (САУ) и на нижних уровнях автоматизированных систем управления (АСУ). В соответствии с требованиями к работе ЛВС в реальном масштабе времени протекания управляемого процесса, функционирование ВС здесь характеризуется жесткими ограничениями, накладываемыми на время реакции системы на входные воздействия, значения которых могут быть достаточно малы (могут составлять миллисекунды и их доли). При возможности существенного увеличения мощности отдельных вычислителей ЛВС, реализующих отдельные функции общей задачи, решаемой ЛВС, например путем объединения их в сосредоточенные ВС (магистрально-модульные УВС [7]), остается ограниченной эффективность межмодульных взаимодействий ЛВС, что вызвано требованиями к высокой помехозащищенности передачи данных между вычислителями (в современных стандартах на интерфейсы распределенных УВС физическая скорость передачи данных ограничивается
единицами Мбит/с [7]). Отмеченные особенности ЛВС, с учетом того, что система может содержать десятки и сотни вычислителей, требующих высокой эффективности межмодульных взаимодействий, обусловливает, что связной ресурс является «узким местом» ЛВС, определяющим их производительность в целом, что требует эффективного решения задачи распределения прав на занятие ресурса между абонентами ЛВС, соответственно при аппаратурной реализации.
Практически аналогичные требования сегодня выдвигаются и к функционированию современных ЛВС общего назначения (ЛВСОН). Современные сетевые технологии, прежде всего ATM (ATM - Asynchronous Transfer Mode) [3] предполагают реализацию сетей связи, в том числе и ЛВС, с интеграцией служб связи (ЛВСИС). При этом в одной сети передаются сигналы реального времени (например, при передаче речи и подвижных изображений) и оперативной обработки (передача данных и текста) , причем сигналы реального времени для различных служб, прежде всего - передача речи и подвижных изображений, имеют существенно различающиеся требования ко времени обработки. Существенным отличием реализации ЛВС в этой концепции будет: требование к функционированию в реальном масштабе времени, обмен фиксированными короткими (53 байтными) пакетами данных (называемыми ячейками), эффективное аппаратурное решение задачи управления доступом абонентов к ресурсам ЛВС [3].
Качество использования общего ресурса в значительной степени определяется методом диспетчеризации [1] - в системах с распараллеливанием по функциям - дисциплиной обслуживания или выбора заявки на использование ресурса от одного из абонентов системы (дисциплина занесения заявки в очередь в ЛВС определяется месторасположением вычислителя с учетом функционального распараллеливания обработки в ЛВСПО, соответственно источника нагрузки в ЛВСОН).
С учетом требований к высокой надежности и модульности построения к реализации ЛВС сегодня, как правило, выдвигается требование распределенного или децентрализованного управления занятием ресурса, причем в большинстве приложений как ЛВСПО, так и ЛВСОН предполагается, что абоненты системы, равно как и общие ресурсы, подключаются к единому для системы каналу связи магистральной топологии. Тогда задача управления доступом абонентов к ресурсу должна быть в равной мере (симметрично) распределена между всеми абонентами ЛВС, т. е. должна решаться устройством децентрализованного управления, задача проектирования которого по существу в ЛВС сводится к проектированию дисциплины обслуживания и способа эффективной ее распределенной аппаратурной реализации.
В учебном пособии рассматриваются особенности и методы построения распределенных ВС, прежде всего в части диспетчеризации заявок на обслуживание методами децентрализованного управления
доступом абонентов к общим ресурсам системы, излагается наиболее перспективная на сегодняшний день концепция построения ЛВС реального времени, позволяющая отказаться от опроса очередей при обслуживании заявок по расписаниям, что существенно улучшает характеристики межмодульных взаимодействий в ЛВС, обсуждаются важнейшие вопросы проектирования и унификации алгоритмических и технических средств распределенных ВС реального времени.
При изучении материала необходимо знание теоретических основ и математических методов теории вычислительных систем и сетей в объеме монографии [1], желательно знакомство с принципами управления множественным доступом к каналу связи ЛВС, изложенными, например в [8, 10, 11], и с методами оптимального кодирования [4]. В своих материалах автор полностью следовал терминологии, введенной и использованной в [1, 2].
Учебное пособие содержит четыре раздела. В первом разделе рассматриваются классификация, принципы построения и модель ЛВС реального времени, формулируются задачи эффективного управления множественным доступом к ресурсам системы в реальном масштабе времени. Рассматриваются цели и критерии оптимальности приоритетного обслуживания заявок в ЛВС. Второй раздел посвящен методам диспетчеризации, применяемым в ЛВС, в частности эффективно распределяющим права на занятие ресурса по расписаниям. Исследуются цели и возможности обслуживания заявок на основе смешанных приоритетов. Раздел содержит описание концепции кодового управления доступом к ресурсам как эффективного унифицированного для ЛВС подхода к обслуживанию заявок в реальном времени и со смешанными приоритетами. Исследуется модель системы кодового управления. Вводится понятие и рассматриваются свойства канонического расписания. Третий раздел посвящен методам кодирования приоритетов абонентов ЛВС. Рассматриваются задачи и возможности повышения эффективности кодового управления доступом к каналу за счет оптимального кодирования приоритетов абонентов. Излагаются принципы динамического кодирования приоритетов абонентов, реализуемого в системе для передачи прав на занятие ресурса по расписанию. В четвертом разделе рассматриваются альтернативные механизмы кодового управления множественным доступом и исследуются возможности их унификации в рамках единой концепции кодового управления, обсуждаются пути повышения эффективности кодового управления, за счет эффективной передачи прав между абонентами на доступ к ресурсу.
Ограниченный объем пособия не позволяет изложить многие вопросы достаточно полно. Более подробно с ними можно ознакомиться с помощью дополнительной литературы [12 - 24].
В соответствии с общей классификацией ВС [2], рассматривая ЛВС как вычислительную сеть, представляющую собою совокупность ВС, объединенных при помощи средств связи, включающих каналы связи и устройства сопряжения ВС с каналами связи, расположенную на небольшой территории, и использующую ориентированные на эту территорию средства и методы передачи данных; получаем классификацию ЛВС, представленную на рис. 1.1. Все многообразие ЛВС можно разделить на две большие группы - проблемно ориентированные (ЛВСПО) и оперативной обработки (ЛВСОН), в основу такого деления положено наличие (отсутствие) распараллеливания решаемой ЛВС задачи. Под ЛВСПО будем понимать ЛВС, ориентированные на решение ими в процессе всего времени работы ограниченного числа задач, связанных между собою по данным или требующих взаимодействий при их параллельной обработке, что позволяет синтезировать алгоритм функционирования ВС при проектировании ЛВС. Под ЛВСОН будем понимать ЛВС, круг решаемых задач которых не может быть ограничен, либо решаемые ЛВС задачи независимы, т. е. не связаны между собою по данным, что не позволяет синтезировать алгоритм функционирования ВС при проектировании ЛВС.
По виду заявки на обслуживание, под которой здесь будем понимать причину инициирования передачи данных по каналу связи ЛВС, будем делить ЛВС на ЛВС реального времени (ЛВСРВ) и ЛВС оперативной обработки (ЛВСОО). Под ЛВСРВ будем понимать ЛВС, функционирующие в реальном масштабе времени, характеризуемом нарушением законов функционирования системы или потерей заявок на обслуживание при превышении предельных ограничений на время реакции системы на входное воздействие. Под временем реакции системы понимается задержка во времени между моментом поступления в систему данных и моментом окончания их обработки системой. Под ЛВСОО будем понимать ЛВС, функционирование которых характеризуется снижением качества обслуживания без нарушения законов функционирования системы или отсутствием потерь заявок на обслуживание при превышении предельных ограничений на время реакции системы на входное воздействие. ЛВС, сочетающие в себе принципы обслуживания в реальном времени и оперативной обработки будем называть ЛВС комбинированного обслуживания (ЛВСКО).
Рис. 1.1
По виду решаемых ЛВСПО задач (назначение), будем их делить на управляющие и информационные ЛВС. Под управляющими ЛВС (УЛВС) будем понимать ЛВС, работающие совместно с объектом управления, непрерывно функционирующим во времени. Соответственно, по наличию (отсутствию) оператора, принимающего решение в контуре управления, УЛВС могут функционировать в составе АСУ или САУ. Под информационной ЛВС (ИЛВС) будем понимать ЛВС, предназначенную для сбора, обработки, передачи, хранения и отображения информации, представленной базами и банками данных.
ЛВСОН будем подразделять по виду реализуемых ими служб связи. Под службой связи понимается предоставляемые ЛВС услуги, связанные с обработкой и передачей конкретных видов информации, представляемой в
канале связи соответствующими физическими сигналами. Примерами служб связи реального масштаба времени, под которыми понимаются службы, характеризуемые реальным масштабом времени поступления и передачи по сети связи сигналов, при невозможности их промежуточной буферизации без искажения (потери) информации, является телефонная связь (служба передачи речи), передача подвижных изображений, радиосигналов и т.д. Примерами служб связи оперативной обработки, отличающихся возможностью промежуточного хранения передаваемой информации с целью эффективного использования каналов связи ЛВС, являются службы передачи данных, текстов, неподвижных изображений и т. д. С учетом сказанного, ЛВСОН будем делить на ЛВС, реализующие службы связи реального масштаба времени (ЛВССРВ) и службы связи оперативной обработки (ЛВССОО). ЛВСКО в данных приложения называются ЛВС с интеграцией служб (ЛВСИС), сочетающие службы связи реального масштаба времени и оперативной обработки.
Т.к. под ЛВС понимается распределенная ВС, «узким местом» которой, ограничивающим производительность ВС в целом, является общий ресурс, в первую очередь, связной, задача синтеза ЛВС, по существу, сводится к задаче эффективной реализации доступа абонентов системы к общим ресурсам. При этом важнейшей проблемой проектирования ЛВС является синтез дисциплины обслуживания (в данных приложениях ВС - ЛВС, диспетчеризация заявок на обслуживание сводится к выбору заявок из очередей) - правила (алгоритма), на основе которого заявки выбираются из очередей при их множественном доступе к коллективно используемым ресурсам, прежде всего к общему связному ресурсу - каналу связи ЛВС. Множественный доступ - процедура получения доступа к коллективно используемому ресурсу. Под управлением множественным доступом (арбитражом заявок на обслуживание) понимается бесконфликтный, реализуемый либо с предотвращением возможного конфликта, либо с его разрешением, доступ абонентов к коллективно используемому ресурсу в соответствии с реализуемой в ЛВС дисциплиной обслуживания требований ресурса. Конфликт (столкновение) ситуация, при которой через один канал связи передают данные одновременно несколько абонентов, приводящая к искажению информации в канале связи. Децентрализованное управление множественным доступом характеризуется тем, что задача арбитража (решаемая в рассматриваемых приложениях аппаратурно) в равной мере (симметрично) распределена между абонентами системы. Децентрализованное управление множественным доступом реализуется за счет передачи между абонентами полномочий (прав) - разрешающих сигналов, позволяющих абонентам доступ к коллективно используемым ресурсам.
Основное внимание в монографии уделяется исследованию принципов диспетчеризации заявок на обслуживание в ЛВС реального
времени, т.е., следуя введенной классификации ЛВС, применяемых для различных приложений ЛВСРВ и ЛВСКО.
В основе реализации современных распределенных ВС находятся следующие общие принципы построения:
- параллельность обработки, позволяющая создавать мощные коллективы вычислителей при различных принципах распараллеливания задач;
- модульность, обусловливающая высокую надежность и живучесть ВС, простоту резервирования блоков и наращивания вычислительной мощности;
- распределенность (или децентрализованность) управления общими ресурсами, обеспечивающая высокую надежность систем параллельной обработки данных;
- решение задачи управления распределением прав между абонентами на доступ к «узкому месту» ВС - общему ресурсу, аппаратурными средствами, что обеспечивает высокую эффективность его использования в системе.
Структура распределенной системы с общими ресурсами, в основе построения которой лежат перечисленные принципы, представлена на рис. 1.2 - в качестве связного ресурса рассмотрим применение последовательного канала связи магистральной топологии – «общая шина».
Под шинной (магистральной) ЛВС понимается ЛВС, в которой всегда имеется лишь один маршрут между любыми двумя абонентами, и данные, выдаваемые в канал любым абонентом ЛВС, доступны всем абонентам, включая и источник информации.
Подобная структура отличается следующим:
- в системе отсутствуют какие-либо узлы коммутации, что обеспечивает «многоточечное» подключение абонентов к каналу связи [7] и, как следствие, максимальную надежность и модульность построения, а за счет одновременной обработки абонентами информации, поступающей из канала, и максимальную эффективность межмодульных взаимодействий;
- по этой же причине в системе наиболее сложно решается задача управления доступом абонентов к общим ресурсам - задача управления доступом к ресурсам здесь формулируется и решается в общем виде.
С учетом сказанного, на сегодняшний день это наиболее перспективная структура распределенных ВС, используемая, как правило, в системах реального времени, а нас интересующая наиболее общей постановкой исследуемой задачи управления множественным доступом к общим ресурсам. Поэтому приведенная структура ВС и будет нами
рассматриваться далее (отметим, что позволяя решить исследуемую задачу в общем случае - при магистральном канале связи, излагаемые методы при незначительных модификациях могут применяться и для частных, с точки зрения управления доступом к ресурсам, приложений, например при кольцевой топологии ЛВС).
Замечание. На рис. 1.2 кроме связного приведены другие ресурсы ВС, которые присоединяются к каналу связи также по правилу многоточечного подключения. Поэтому взаимодействие абонента с любым ресурсом осуществляется по единому каналу связи, следовательно задача управления доступом к ресурсам системы здесь опять же сводится к задаче управления доступом к связному ресурсу.
Задача диспетчеризации здесь решается арбитром, под которым понимается устройство, реализующее в ЛВС децентрализованное управление множественным доступом абонентов к общим ресурсам в соответствии с требуемой дисциплиной обслуживания.
Рис. 1.2
В задачи управления множественным доступом ( при аппаратурном ее решении - в задачи распределенного арбитра, см. рис. 1.2) входит:
- диспетчеризация заявок на обслуживание - в распределенных ВС при функциональном распараллеливании, при котором каждый абонент территориально приближен к источнику нагрузки и решает задачи исключительно по обработке поступающих от него заявок, сводится к задаче выбора заявок из очередей или к реализации дисциплины обслуживания (ДО);
- передача прав между абонентами системы на доступ к ресурсу в соответствии с задаваемой дисциплиной обслуживания очередностью.
Классификация наиболее широко используемых сегодня в ЛВС методов диспетчеризации [1] представлена на рис. 1.3, реализующих их методов управления множественным доступом на рис. 1.4 [8, 10]. Среди ДО можно выделить бесприоритетные, реализующие случайный выбор одной из поступивших заявок, и обслуживание в циклическом порядке (ОЦП), когда все очереди заявок опрашиваются последовательно одна за другой в циклическом порядке; приоритетные ДО с относительными приоритетами (ОП), при которых после освобождения ресурса его занимает активная заявка с наиболее высоким ОП. На практике реализуются два подхода к заданию ОП заданием фиксированным значением кода адреса в системе, либо местом подключения абонента к связному ресурсу.
Рис. 1.3
Методы управления множественным доступом, реализующие соответствующие ДО, различаются видом сигнала передачи прав на занятие ресурса - либо асинхронным ( по выделенной линии арбитража - эстафетный,
специальным кодовым словом по каналу связи - маркерный), либо временным интервалом (синхронный). Методы, реализующие ДООП, различаются способом задания относительного приоритета, либо кодом адреса в системе, либо местом подключения к каналу. Занятие канала здесь осуществляется за счет последовательного «отключения» менее приоритетных абонентов в результате сравнения разрядов кода ОП, либо при распространении отключающего сигнала по однонаправленной линии приоритета.
Рис. 1.4
Следуя классификации интерфейсов ЛВС реального времени [7] можно выделить: магистрально-модульные ВС, где последовательный канал связи имеет длину, как правило, до 10 метров: стандарт Bitbus, SSB (в интерфейсах Multibus), NUBUS, Fastbus, I2C, D2B и др.; рассредоточенные ВС - здесь в качестве передающей среды уже используется последовательный канал связи, имеющий длину от сотен метров до километров при возможности ее наращивания активными ретрансляторами. К таким интерфейсам относятся: интерфейс распределенной магистрали (ИРМ), интерфейс линейной связи с последовательной передачей информации (ИЛПС), MAP, PROWAY, ( MAP, PROWAY - регламентируют правила построения ЛВС реального времени), MIL-STD-1553B и др.
Методы же управления множественным доступом, реализуемые для рассматриваемых интерфейсов с учетом представленной на рис. 1.4 классификации, следующие: маркерный (в частности сюда относится и предельный случай эстафетной смены задатчика - метод Polling - при смене задатчика или центрального узла каждым сигналом передачи прав) - наиболее широко применяемый метод, например в Bitbus, ИРМ, ИЛПС, PROWAY, MAP, MIL; и метод ДКУ, используемый в I2C и D2B [7]. Метод ДПВУ нашел применение лишь в сосредоточенных ВС с параллельной системной магистралью ( И-41, VME-bus и др.), где приоритет абонентов убывает по мере удаления модулей «по гирлянде». Здесь применяется и метод ДКУ (в данных приложениях можно рассматривать как комбинированные ДКУ и ДПВУ), причем разряды кода, либо признаки занятия ресурса абонентами группы, подаются по специальным выделенным для этой цели управляющим линиям шины ( И-41, Multibus I, II и др.) [7].
Т.о. современными стандартами, регламентирующими правила построения ЛВС реального времени, по существу, рекомендуется к использованию только маркерный метод управления множественным доступом, реализующий ОЦП посредством опроса очередей в соответствии с бесприоритетным расписанием. В монографии будет показано насколько неэффективен данный подход при реализации рассматриваемых ЛВС различных приложений.
В ЛВС, используемых в современных информационных системах, широкое использование находит случайный метод управления множественным доступом, в частности CSMA-CD (с обнаружением наложения) [8, 10, 11], реализующий бесприоритетную ДО с передачей прав случайным образом. Однако, данный подход уже не удовлетворяет современным сетевым технологиям, реализующим интеграцию служб связи, в том числе и реального времени, как при асинхронной передаче данных - ATM - в ЛВС технологии ATM используется маркерный метод управления доступом к магистральному каналу [3], так и при синхронной передаче - ISDN. Для этих приложений необходимы эффективные методы управления множественным доступом реального времени, реализующие приоритетные расписания. Такие методы могут быть получены лишь в том случае, если удастся отказаться от механизма опроса очередей при реализации расписаний, в том числе и приоритетных.
В монографии подробно рассматривается современная концепция обслуживания заявок в реальном времени, в основе которой находится оригинальный принцип обслуживания с динамическими ОП, изменяемыми по расписаниям, объединяющая в себе новые возможности обслуживания в реальном масштабе времени, со смешанными и с многоуровневыми (учитывающими приоритеты заявок) приоритетами, при высокой эффективности управления множественным доступом к ресурсам и открывающихся возможностях по унификации механизмов передачи прав на занятие ресурса между абонентами системы.
Так как основными требованиями к качеству построения и функционирования ВС реального времени является выполнение временных ограничений в обслуживании заявок, то распределенную ВС реального времени можно описать детеминированной моделью. К временным параметрам обслуживания заявок относятся величины: - продолжительность занятия ресурса , абонентом для информационного с ним взаимодействия, - продолжительность передачи прав m-му абоненту после освобождения ресурса в системе, - коэффициент частоты занятия ресурса i-м абонентом относительно m-го . Качество обслуживания заявок можно описать характеристиками: - продолжительность арбитража требования m-го абонента (с момента появления заявки до момента предоставления абоненту права занять ресурс) или соответственно, продолжительность ожидания заявкой обслуживания, - продолжительность обслуживания заявки системой. Для систем реального времени интерес представляют граничные (худшие для любой заявки) значения рассмотренных характеристик, которые соответственно обозначим: , , , , , , , откуда получаем параметры обслуживания заявок в системе реального времени: , .
С учетом сказанного, получаем модель системы реального времени
(1.1)
Утверждение. Обслуживание заявки в реальном масштабе времени корректно, если для любого абонента системы m, выполняются условия (1.1).
Доказательство. Если условие (1.1) хотя бы для одного абонента системы не выполняется нельзя считать, что его заявки обслуживаются в реальном масштабе времени, т.к. его параметры обслуживания и в этом случае не могут быть ограничены сверху и, следовательно, всегда найдутся условия функционирования системы, при которых и
или заявка будет обслужена не в реальном времени, т.е. для системы потеряна.
Т.к. особенностью обслуживания заявок в реальном времени будет то, что каждая заявка гарантированно должна быть обслужена за время , то в данном случае приоритет заявки нельзя трактовать как преимущественное право одной заявки перед другой быть обслуженной (как, например в случаях относительных и абсолютных приоритетов)[1], здесь приоритеты заявок представляют собой (численно определяются) отношение гарантированных продолжительностей их обслуживания: .
Будем говорить, что в системе реализована бесприоритетная дисциплина обслуживания требований общего ресурса реального времени, если для всех абонентов совпадают значения параметра , соответственно приоритетная дисциплина обслуживания требований общего ресурса реального времени, если хотя бы для двух любых абонентов не совпадают значения параметра .
В качестве параметра приоритетности обслуживания заявок в реальном времени может быть введена количественная оценка - относительный уровень приоритетности реального времени (или относительный приоритет реального времени) двух абонентов m и m'; , под которым понимается отношение . Соответственно в системе реализована бесприоритетная дисциплина обслуживания требований ресурса, если для любых двух абонентов системы m, m' выполняется: , если приоритет m абонента в выше, в противном случае - в ниже.
Системой (1.1) в общем случае определяются три способа задания приоритетного обслуживания заявок в РМВ и соответственно их комбинации.
1. Изменением параметров .
2. Изменением параметров .
3. Изменением параметров .
При этом очевидно, что выбор способов (и их комбинаций) задания приоритетов абонентов определяется соотношением параметров и . При целесообразно использовать способы 1 и 3, при сопоставимости и , соответственно способы 1 и 2.
Рассмотрим, с какой целью и при каких условиях следует назначать приоритеты абонентам распределенной ВС реального времени.
Пусть в систему реального времени поступает M типов заявок на обслуживание (каждый тип заявок в распределенной системе является принадлежностью соответствующего абонента), условием корректности функционирования системы будет выполнение M неравенств: , где - гарантированная продолжительность реакции системы на воздействие, реализуемое в системе, - задаваемое условиями функционирования ограничение на параметр . Требуемая реактивность системы по каждому m-му воздействию определяется следующими временными характеристиками обслуживания заявок системой: - продолжительность собственно решения задачи m-м вычислителем (абонентом) по заранее известной программе (здесь для простоты считаем, что каждым абонентом обрабатывается только один соответствующий тип воздействий); числом информационных взаимодействий с ресурсом , имеющих максимальную продолжительность , необходимым для выработки адекватного воздействия в соответствии с заранее известным алгоритмом (далее для простоты будем считать, что , ). Тогда гарантированная продолжительность реакции системы на m-е воздействие
Рассмотрим следующие возможные случаи.
1. Пусть требуется обеспечить равное время реакции системы на все воздействия - для всех m, воздействий совпадают. В этом случае идеальным является бесприоритетное обслуживание - в реальном времени это передача полномочий в циклической очередности.
2. Пусть заданы различными (различен функциональный смысл воздействий, что имеет место при функциональном распараллеливании). Тогда при бесприоритетной дисциплине обслуживания требований система может функционировать корректно лишь при выполнении для всех M абонентов самого жесткого для системы ограничения:
Например, ЛВСИС, в частности ATM, по одним и тем же каналам связи поступает речь, радиосигнал и подвижное изображение. Для речевого сигнала, полоса пропускания частот которого F = 0 - 4000 Гц по теореме Котельникова (T = 0, 5/F) [4] получаем = 125 мкс, для передачи радио сигнала F = 0 - 15000 Гц имеем = 34 мкс, для качественной же передачи подвижного изображения (телевидение) соответственно F = 0 - 5 МГц уже имеем = 104 нс. В УЛВС параметры для различных заявок могут различаться еще существеннее.
Предположим, что рассматриваемое жесткое ограничение в системе при выбранной производительности технических средств не выполняется для некоторых абонентов. При этом в общем случае некоторые ограничения в системе могут выполняться с большим запасом по производительности ресурса. Тогда можно сформулировать задачу об эффективном перераспределении производительности вычислительных средств системы с учетом выполнения требований к корректности функционирования системы в целом. Критерием оптимальности задания очередности передачи прав (соответственно дисциплины обслуживания) будет относительный коэффициент избыточности в эффективности обслуживания
При этом очевидно, что наиболее эффективно система с общими ресурсами будет реализована в том случае, если выполняются условия , , что можно считать условием оптимальности дисциплины обслуживания реального времени, а параметр - критерием оптимальности. В общем случае для критерия оптимальности (характеристики и для различных воздействий не совпадают) имеем
(1.2)
Оценим, какой выигрыш для распределенных систем может дать реализация в системе приоритетного обслуживания, где приоритет вводится с целью эффективного использования производительности общего ресурса (при связном ресурсе - эффективного использования пропускной способности канала связи). С учетом для всех M абонентов, для системы с бесприоритетной дисциплиной обслуживания (характеристика обозначена БП) требований ресурса имеем
,
где - продолжительность занятия ресурса абонентом с учетом потерь времени на передачу ему прав системой занять ресурс, считаем что совпадают для всех M абонентов (очередей заявок).
Пусть требования к времени реакции системы на 1-е входное воздействие существенно выше, чем требования к любому иному входному воздействию : . Реализуем для рассматриваемой системы приоритетную дисциплину обслуживания требований, в которой очередность предоставления прав абонентам системы на занятие ресурса выглядит следующим образом (1, 2, 1, 3, 1, 4, 1, . . , 1, M-1, 1, M, 1, 2, . . ). Для данной ДО имеем следующие характеристики обслуживания заявок
,
(где ВП, НП - соответвенно характеристики абонентов с высоким и низким приоритетом), откуда выигрыш для более приоритетного абонента составит
(для всех m )
Однако, наряду с выигрышем для более приритетного абонента имеем и проигрыш для менее приоритетных абонентов
,
откуда результирующий выигрыш в производительности ресурса
Оценим количественную оценку получаемого выигрыша. Пусть , где . В предположении, что , для бесприоритетного обслуживания имеем
,
соответственно, для приоритетного обслуживания при двух уровнях приоритетности получаем
соответственно получаем результирующий выигрыш в производительности системы
. (1.3)
Зависимости для различных M, при M=16;64 представлены на рис. 1.5, из которого делаем следующие выводы. 1. При существенном различии ограничений для M абонентов при условии появляется возможность существенного повышения производительности системы реального времени, за счет реализации эффективного управления использованием общего ресурса абонентами, являющегося «узким местом» системы, в результате введения приоритетного обслуживания. Получаемый выигрыш в производительности системы в целом здесь может составить десятки раз, возрастая при увеличении числа абонентов в системе M.
Рис. 1.5
2. Получаемый от реализации приоритетного расписания выигрыш снижается при увеличении коэффициента k, или при опережающем росте над , что определяет переход к классу сосредоточенных систем.
3. При из (1.2) имеем - отсутствует выигрыш как таковой, что может иметь место для некоторых приложений
сосредоточенных систем, когда , где теряет актуальность задача приоритетного обслуживания заявок с целью эффективного использования ресурса абонентами системы. В данных приложениях систем реального времени применяются иные методы параллельной обработки, в частности крупноблочного распараллеливания, при бесприоритетном обслуживании заявок на доступ к ресурсу (в реальном времени - обслуживание в циклическом порядке), который здесь уже не является «узким местом» системы. Как следствие, здесь, как правило, реализуется принцип однородности структуры.
Замечание. Нетрудно показать, что предельным случаем системы, «узким местом» которой будет общий ресурс, можно считать многозадачную операционную систему реального времени (кстати говоря, сосредоточенную). Действительно, общим ресурсом здесь является квант процессорного времени, который и является «узким местом» многозадачной системы. Поэтому при использовании в системе распараллеливания по функциям (что, как правило, имеет место в специализированных операционных системах, реализуемых в задачах управления) возникает аналогичная задача приоритетного обслуживания с целью эффективного использования ресурса. Здесь также имеют место два способа задания приоритетов - изменением величины процессорного кванта для приоритетной задачи, изменением частоты (не ОЦП) опроса очередей заявок от отдельных задач. Первый подход ограничен нарушением параллельности обработки, что недопустимо в системах реального времени (кстати говоря, именно эти же соображения приводят к уменьшению длины пакета данных в сетевой технологии ATM до 53 байтов), второй имеет недостатком наличие больших временных затрат на опрос очередей по расписанию. Поэтому как и в ЛВС сегодня на практике здесь используется бесприоритеный опрос очередей (например, используемая в ОС QNX дисциплина RR), т.е. в системах практически отсутствуют возможности эффективной диспетчеризации в реальном времени при распараллеливании задач по функциям. Другими словами, рассматриваемые в монографии принципы диспетчеризации могут эффективно использоваться и в этих приложениях систем реального времени параллельной обработки - в различных приложениях как распределенных, так и сосредоточенных ВС.
С учетом сказанного, цель реализации приоритетного обслуживания в ЛВС реального времени, в которых ресурс является «узким местом», состоит в перераспределении прав между абонентами на доступ к ресурсу в соответствии с заданными ограничениями на время реакции системы на входное воздействие. Выполнение данных ограничений при минимальной производительности ресурса достигается при выполнении условия: , , которое можно считать условием оптимальности приоритетных ДО реального времени. Соответственно, количественное задание приоритетов абонентов может быть получено с использованием выражения (1.2).
Замечание. Приведенное исследование иллюстрирует и общий подход к синтезу алгоритма функционирования распределенной ВС (), состоящий в минимизации числа межмодульных взаимодействий при обслуживании заявок, что формально записывается следующим образом: , .
Выше речь шла о ЛВСПО реального времени, относительно ЛВСОН реального времени отметим, что здесь реализуется аналогичная идея приоритетного обслуживания, однако, т.к. отсутствует алгоритм функционирования - невозможно задать параметр , то в качестве ограничений следует уже рассматривать не параметр , задаваемый в ЛВС для всех M абонентов, а параметр . При различии для M абонентов могут вводиться приоритеты с целью эффективного использования «узкого места» - связного ресурса ЛВС.
1.6. Модель системы оперативной обработки
Очевидно, что по аналогии с введенной выше моделью системы реального времени может быть введена и модель системы оперативной обработки, отличающаяся тем, что этой моделью должен учитываться параметр - вероятность занятия ресурса m-ым абонентом (в общем случае < 1) при предоставлении ему права занять ресурс. Качество обслуживания заявок в этом случае можно описать следующими характеристиками: - средняя продолжительность арбитража требования m-го абонента, - средняя продолжительность обслуживания заявки системой.
При этом из (1.1) можем получить модель системы оперативной обработки, которая здесь принимает вид
Замечание. При , имеем детерминированную модель реального времени (1.1), где =, =. Т.о. приведенная здесь модель представляет собой более общий случай обслуживания, для которой справедливо следующее утверждение.
Утверждение. Обслуживание заявки в режиме оперативной обработки корректно, если обслуживание номера поступающей в систему заявки можно охарактеризовать следующим величинами: ,, где = при =1m, и < если m для которых <1 (соответственно и Tam).
Доказательство. При описании системы данной моделью для системы характерно, что вся зависимость от ее загрузки 1 заявки, поступающие от абонентов обслуживаются за исключением времени (n* для n-ой
заявки в очереди m-го абонента) т.е. любой абонент является элементом системы, т.к. при любых условиях функционирования с системой не производится отключения от ресурса. Т.о. здесь как и в системе реального времени особенностью обслуживания заявок будет то, что каждая заявка гарантированно должна быть обслужена за время при среднем времени обслуживания, на которое и расчитывается система оперативной обработки,
. Или в данном случае приоритет заявки, как и в системах реального времени нельзя трактовать, как преимущественное право одной заявки перед другой быть обслуженной, а приоритет заявок представляют собой (численно определяются) отношением средних и гарантированных продолжительностей их обслуживания: , .
Однако в данном случае уже имеет смысл говорить не только о дисциплине обслуживания заявок, которая как и для системы реального времени характеризуется параметрами = f ((m),, ) т.е. дисциплина обслуживания как и для системы реального времени описывается детерминированной моделью, но и о использования прав абонентами, предоставленных дисциплиной обслуживания, что определяется параметром = f ().
Будем говорить, что предоставленые абонентам дисциплиной обслуживания права используются ими в равной мере, если для них совпадают отношения / , соответственно, права предоставляемые m-му абоненту, дисциплиной обслуживания используются им в большей мере, чем m’ абонентом, где m,, mm’, если
Очевидно, что права, предоставляемые абонентам дисциплиной обслуживания используются ими в равной мере при условии: =P, .
В предположении, что в проблемно-ориентированной ЛВС требуется обеспечить среднее время реакции системы на входное воздействие , что для М абонентов, задается условием: , где , где - продолжительность решения задачи вычисления, Lm - число информационных взаимодействий с ресурсом средней продолжительностью , необходимое для выработки в системе сигнала реализации на входное воздействие, по аналогии с системой реального времени может быть введен коэффициент избыточности в эффективности обслуживания m-го абонента при реализации бесприоритетной передачи прав абонента в циклическом порядке: ,
где .
Тогда формализованным условием введения приоритетного обслуживания будет: ,что можно считать условием оптимальности дисциплины обслуживания, а параметр соответственно критерием оптимальности
(в общем случае для имеем характеристики и для различных воздействий не совпадают).
Т.о. как и в системе реального времени здесь можно количественно описать приоритеты и сформулировать аналогичную задачу синтеза дисциплины обслуживания, критерием оптимальности которой является параметр , а условием оптимальности: .
Рассмотрим, чем же отличается рассмотренная модель оперативной обработки от модели реального времени. По существу только тем, что здесь учитывается два параметра и , причем основным является . При этом ограничения типа выполняться не должны, выдвигаются требования к выполнению условий , другими словами, здесь реализуется обслуживание в реальном времени. Но производительность технических средств выбирается не исходя из выполнения условий: , а исходя из выполнения условий: .
Поэтому далее говоря о построении систем реального времени, понимаем, что аналогично могут строиться и системы оперативной обработки на основе рассмотренной модели с обслуживанием (в том числе и приоритетном) по расписаниям с тем лишь отличием, что синтез расписаний осуществляется с учетом параметров .
Отметим, что обслуживанию по расписанию в режиме оперативной обработки присущи как существенные достоинства, так и существенные недостатки. К основному достоинству можно отнести возможность эффективного использования ресурса при за счет синтеза расписания, максимально учитывающего ограничения , , для ЛВС ОН. Однако для ЛВС ПО, соответственно данное достоинство можно реализовать лишь при эффективной передаче прав по расписанию, что не обеспечивается современными методами управления множественным доступам в ЛВС. Поэтому данное достоинство будет обеспечено лишь в том случае, когда будут предложены методы эффективной передачи прав по расписанию, эффективность которых не будет зависеть от величины загрузки системы (о таких методах речь пойдет ниже).
К недостаткам данного подхода можно отнести то, что он не обеспечивает возможность защиты от перегрузки высокоприоритетных абонентов (либо заявок), за счет «отключения» от ресурса низкоприоритетных, что реализуется обслуживанием с относительными приоритетами. Поэтому на практике целесообразно говорить об использовании обоих рассмотренных методов обслуживания в ЛВС ОО, а также ставить задачу их эффективной совместной реализации в единой технической системе.
Альтернативные способы обслуживания заявок в распределенных ВС составляют ДО с относительными приоритетами (ДООП) и обслуживание заявок по расписаниям (ДОР), частным случаем последнего является опрос очередей заявок в циклическом порядке - бесприоритетное расписание.
К достоинствам первого подхода можно отнести защиту от перегрузок высокоприоритетных заявок [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-расписаний в ЛВС), несмотря на внешнюю привлекательность, на практике не используется.
Очевидно, что условием эффективного приоритетного обслуживания заявок по расписанию в ЛВС будет независимость затрат от интенсивности поступления заявок в систему, что формализовано можно представить следующим образом: .При этом (в случае ) все работы имеют равную длину
что обуславливает эффективность обслуживания в первую очередь (с приоритетом) наиболее важной заявки.
Идея излагаемой концепции состоит в реализации дисциплин обслуживания реального времени с передачей прав по расписанию (ДОР), за счет смены относительных приоритетов (ОП) в рамках реализуемой в системе дисциплины обслуживания с относительными приоритетами (ДООП) по расписанию при каждом занятии ресурса абонентами системы.
Утверждение. В любой момент времени ОП не должен совпасть у заявок из нескольких очередей.
Доказательство. Если данное условие не будет выполнено, то в системе неминуем конфликт при занятии ресурса, т.к. несколько абонентов одновременно получат право занять ресурс после его освобождения.
Для описания ДООП используем матрицу приоритетов (МП), представляющую собою квадратную матрицу размерности по числу 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: ; - приращение (может иметь отрицательные значения) приоритета заявки, получаемое при смене состояний цикла расписания . Для заявок, обслуживаемых с ОП, для , и для , .
В основе излагаемого подхода находятся следующие принципы кодового управления реального времени.
1. В любой момент времени функционирования системы матрице приоритетов ставится во взаимно однозначное соответствие матрица кодов ОП (МКП). Строки МКП соответствуют строкам МП, а столбцы задают код ОП очереди заявки. Пример МКП, в предположении, что «1» в разряде кодового слова приоритетнее «0» (по «1» права передаются, по «0» - нет), и что приоритет разряда кода убывает по мере возрастания его порядкового номера, приведен на рис. 2. 6.
Рис. 2.6
2. В процессе функционирования системы при каждом занятии ресурса МКП изменяется в соответствии со сменой исходной МП (заменой МП на МКП во все моменты времени ), в результате чего получается граф смены МКП, полностью соответствующий графу смены МП (чем реализуется передача прав по расписанию). Пример взаимно однозначного отображения графов МП в МКП для случая, представленного на рис. 2. 5 (бесприоритетное обслуживание), приведен на рис. 2. 7.
Рис. 2.7
3. При построении кодов ОП всех очередей заявок в процессе функционирования системы применяется приведенное ранее правило задания ОП заявок в графе смены МП.
4. При управлении доступом к ресурсу должно осуществляться поразрядное (начиная с более приоритетных разрядов) сравнение кодов ОП заявок , затребовавших к данному моменту времени ресурс, с «отключением» по каждому разряду менее приоритетных заявок - при однозначном кодировании заявок получаем бесконфликтное занятие ресурса. Утверждение. Метод кодового управления на всем интервале изменения загрузки системы имеет эффективность не ниже, чем методы опроса очередей.
Доказательство. Утверждение доказывается тем, что при ином подходе (опрос очередей) права передаются поочередно от одной очереди заявок к другой, опрашивая их, и при стационарности системы для занятия ресурса может потребоваться несколько передач кодового слова - маркера, имеющего длину не менее [] разрядов. При кодовом управлении при любой
загрузке системы потребуется лишь единожды выдать в канал разряды кода приоритета той же длины, что позволяет говорить о том, что эффективность кодового управления совпадает с идеальной характеристикой опроса очередей, в случае активности на занятие ресурса заявок из всех очередей.
Зависимость изменения информативности смеси для ЛВС, реализуемой в рамках технологии ATM, при использовании кодового управления в реальном времени множественным доступом к каналу связи при приведена на рис. 2.4, который иллюстрирует высокую эффективность кодового управления по сравнению с методом передачи маркера, реализуемого при опросе очередей.
Прежде всего, рассмотрим возможности построения ДО со смешанными приоритетами (ДОСП) или комбинированных ДО - ОР и с ОП. Реализация подобных возможностей позволит совместить в единой системе альтернативные подходы к обслуживанию, достигающие совершенно противоположные цели, соответственно - обслуживание по расписанию с целью реализации обслуживания заявок в реальном времени, обслуживание с ОП, позволяющее обеспечивать защиту от перегрузок высокоприоритетных заявок, что необходимо для эффективной реализации альтернативных приложений ЛВСКО. Данные возможности в одной системе позволяет получать изложенный принцип реализации ДОР, отличающийся тем, что в любой момент функционирования системы реализуется ДООП, с условием, что ОП заявок изменяются при каждом занятии ресурса системы. Однако, в процессе функционирования системы могут изменяться ОП не всех заявок, причем как низкоприоритетных, так и высокоприоритетных, либо группы очередей заявок могут организовывать свои очередности (расписания) смены ОП. Данные возможности, открываемые реализацией ДОР, посредством смены ОП в процессе функционирования системы, положены в основу идеи реализации ДОСП, соответственно получаемого в его рамках ряда ДО. Примеры графов ДОСП, иллюстрирующих альтернативные способы задания ОП, соответственно для защиты от перегрузок заявок реального времени (ОП неизменяем для низкоприоритетных заявок) и с целью выделения внеочередных заявок (ОП неизменяем для низкоприоритетных заявок), для случая представлены на рис. 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
Замечание. Предоставление высокого ОП внеочередным заявкам можно рассматривать как подход, альтернативный обслуживанию системных заявок с абсолютным приоритетом, применительно для ЛВС реального времени. Это обусловливается тем, что при небольших размерах информационного кадра и децентрализации управления множественным доступом к ресурсам, пропадает смысл прерываний взаимодействий с ресурсом низкоприоритетных абонентов при поступлении системной заявки (это приводит к большим временным потерям, чем при обслуживании с ОП, при существенном усложнении процедуры управления множественным доступом к ресурсам).
С учетом сказанного, построение ДОСП (ОР и ОП) в общем случае реализуется следующим образом:
- заявки подразделяются на три большие группы: внеочередные, РМВ, бесприоритетные;
- внеочередным заявкам присваиваются максимальные ОП - при необходимости обслуживать их с равным приоритетом, либо в какой-нибудь очередности, для них реализуется расписание (ОР);
- для заявок реального времени строится ДОР (приоритетная, либо бесприоритетная), их ОП в любой момент времени ниже ОП внеочередных заявок;
- низкоприоритетным заявкам оперативной обработки (нереального времени) присваиваются ОП более низкие, чем заявкам реального времени (чем последние при ООП защищаются от перегрузок), которые, в свою очередь, могут обслуживаться как в режиме ОП, так и между собою по расписанию.
Замечание. В общем случае в системе могут присутствовать не все три возможных группы заявок, но для исследуемого класса систем всегда присутствуют заявки реального времени.
Другой широкий класс возможностей в обслуживании заявок в реальном времени, открывающийся в рамках рассматриваемой концепции приоритетного обслуживания в распределенных системах, состоит в возможности учета не только приоритета абонента, но и собственно приоритета поступающей заявки на обслуживание, в предположении, что требования к временным параметрам обслуживания заявки определяются не только приоритетом абонента. Реализация данной возможности обслуживания является непременным условием построения ЛВСИС, в частности в рамках технологии 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.14. Отметим, что здесь выделены классификационные признаки и соответственно приведена классификация ДО именно с позиции исследуемой концепции обслуживания. В рамках же каждой полученной дисциплины можно рассмотреть известные классификационные признаки - по виду
стратегии обслуживания (вентильная, ординарная, исчерпывающая) и др. [1, 5, 6].
Кроме того, для ЛВСОО и ЛВСКО может быть реализована ДО с многоуровневым приоритетом, учитывающим абсолютные приоритеты и многоуровневый алгоритм обслуживания для заявок оперативной обработки, и практически для любых приложений ЛВС – обслуживание с адаптивным управлением множественным доступом.
Рис. 2.14
Пусть имеем R различных приоритетов абонентов в системе, обслуживаемых по расписанию, соответственно , и абонентов системы имеют равный r приоритет : , , . Таким образом система содержит M абонентов, которым соответствует R уровней приоритетов.
Детерминированная задача синтеза расписаний реального времени может быть сформулирована следующим образом : , , , , где - характеристика обслуживания m-го абонента r-го приоритета, - ограничение, накладываемое на время обслуживания заявки абонента системой, функционирующей в реальном масштабе времени.
С учетом сформулированной задачи синтеза расписаний реального времени дадим определение канонического (в данном случае - оптимального) расписания. Под каноническим расписанием будем понимать расписание, обеспечивающее минимальные значения характеристик в рамках заданного разбиения M абонентов на R уровней приоритета, получаемое поочередной передачей прав абонентам в рамках радиального графа.
Под радиальным графом передачи прав понимается граф, содержащий вершин приоритета r, , причем в каждую вершину нижестоящего приоритета входит только одна дуга от одной вершины вышестоящего приоритета, из каждой вершины всех приоритетов, кроме R-го выходит [] дуг, где [a] - есть большее целое числа a, все вершины приоритета R соединяются дугой с вершиной приоритета 1 (из вершин R выходит только одна дуга) - в этом случае дуга направлена в сторону вершины 1, в то время как в остальных случаях дуга направлена в вершину, соответствующую пользователю с более низким приоритетом. Радиальный граф передачи прав представлен на рис. 2.15.
Рис. 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). Тогда параметры обслуживания заявок абонента определяются гарантированной продолжительностью обслуживания
,
и средней продолжительностью гарантированного обслуживания требований с учетом различных очередностей S
.
Таким образом в общем случае - при нескольких очередностях в системе дисциплина обслуживания реального времени задается параметрами и . Для канонического расписания значения и соответственно совпадают для абонентов всех R приоритетов.
2. В системе реализуются минимально возможные значения для всех абонентов всех R приоритетов.
3. Относительный уровень (коэффициент) приоритетности абонентов , : вырожденного графа - при минимальных составляет
,
соответственно, ограничением на общность построения радиального графа будет
;
Из анализа свойств канонических расписаний, можем сделать следующие выводы.
1. В основе синтеза расписаний реального времени должно находиться построение канонического расписания, с последующей его модификацией, учитывающей особенности конкретной задачи синтеза.
2. При минимизации значений параметра для всех абонентов всех уровней приоритета системы R (эффективное использование ресурса) строго задается соотношение уровней коэффициента приоритетности абонентов системы.
3. Исходное соотношение коэффициентов приоритетности может быть изменено либо подбором соответствующих значений двух других параметров и в рамках канонического расписания, либо изменением значений (либо , в общем случае они могут не совпадать), путем их увеличения (уменьшить их уже невозможно, что следует из второго свойства канонических расписаний) для абонентов отдельных уровней приоритета.
Аналогично может быть построено расписание и для ЛВС ОО. Следует отметить, что в этом случае расписание также может синтезироваться по параметрам . При этом значения должны выбираться таким образом, чтобы для синтезированного по этим параметрам расписания выполнялось: .
Методика синтеза расписания в данном случае состоит в следующем.
1.Назначаются , где .
2.Для заданных параметров с использованием описанной выше методики синтезируется расписание
3.Строится модель (аналитическая или имитационная) системы массового обслуживания с полученным расписанием с целью определения значений .
4.Проводится сравнение значений . В результате которого значения уменьшаются для тех параметров m для которых соответственно увеличиваются в случае, если .
5.С новыми заданными значениями переход к п.п.2.
Синтез расписания продолжается до выполнения условия: ,
где значения задаются перед началом решения задачи, исходя из условий задачи.
Замечание. Задача синтеза расписания для ЛВС ОО может решаться и за один этап, однако это требует решения задачи определения значения
для заданного т.е. должны быть определены и формализованы зависимости .
Данная задача на сегодняшний день не решена и в книге лишь обозначается в постановочной части.
При моделировании систем с передачей прав по расписанию, реализуемой опросом очередей, в частности при маркерном методе управления множественным доступом, возникает серьезная проблема, вызванная тем, что получение аналитических зависимостей, связывающих время ожидания заявок с числом обращений к очередям по расписаниям,
каждое из которых требует учета затрат времени на передачу прав - сложная задача, которая не может быть решена классическими методами теории массового обслуживания [1]. Поэтому при проектировании таких систем используют некоторые приближения - аппроксимирующие функции, достаточно полный обзор которых приведен в [5, 6]. При кодовом же управлении множественным доступом в основе находится ДООП, что позволяет применить при моделировании систем известные формулы теории массового обслуживания.
В общем случае можем выделить две большие группы заявок на обслуживание - реального и нереального масштабов времени. Заявки первой группы обслуживаются по расписанию и параметром обслуживания здесь будет - гарантированная продолжительность обслуживания
,
где - гарантированные затраты времени на передачу прав абоненту для занятия системы ( для кодового управления при равномерном кодировании они фиксированы и составляют []), - гарантированные затраты времени при занятии ресурса, которые также, как правило, фиксированы (например, связанные с передачей 53 байтов информации в рамках сетевой технологии ATM ), - коэффициент, задающий гарантированное предоставление ресурса (более высокий приоритет) другим абонентам системы между очередными предоставлениями прав занять ресурс m-му абоненту (приоритет абонента тем выше, чем меньше ).
Заявки оперативной обработки обслуживаются либо бесприоритетно, либо в режиме ОП. В последнем случае для расчета характеристик обслуживания можно воспользоваться моделью однолинейной СМО с H классами (приоритетами) очередей неограниченной длины с ординарной стратегией обслуживания заявок, образующих простейшие потоки с интенсивностями , и случайными длительностями обслуживания с известными первыми и вторыми начальными моментами , , , - соответственно загрузки, создаваемые различными потоками; в которой для среднего времени ожидания обслуживания заявки класса k имеем [1]
,
где
, а ,
причем т.к. или , .
Исследуем эффективность ДОСП РМВ в альтернативных приложениях использования ОП. Эффективность использования ОП с целью защиты от перегрузок заявок реального времени, с учетом известного закона сохранения времени ожидания для ДО [1], где - уровни ОП, - загрузки уровней l, - среднее время ожидания заявок класса l, дает соответственно выигрыш для заявок РМВ - ОП 1 (для них имеем ОЦП) и проигрыш для заявок ОП 2 (пусть между собою для них также ОЦП) или ДО [(1,2,…,S ), (S +1,...,M )]
, ,
при обработке заявок с ОП по схеме, приведенной на рис. 2.17, где в систему поступает M простейших потоков с интенсивностями и средними длительностями обслуживания со вторыми начальными моментами ; , - соответственно загрузки, создаваемые потоками различных ОП ( обслуживание заявок каждого класса реализуется на основе дисциплины FIFO ). Исследуемая характеристика для случая , , , приведена на рис. 2.18, где видно, что времена ожидания заявок монотонно убывают с ростом ОП.
Рис. 2.17
Рис. 2.18
Важной является оценка выигрыша заявок реального времени именно по параметру . В предположении, что такие заявки имеют бесприоритетное обслуживание, причем , соответственно совпадают для всех M (бесприоритетное расписание) абонентов, для схемы, приведенной на рис. 2.17, имеем выигрыш, получаемый для заявок реального времени
или, соответственно в относительных единицах . Это говорит о том, что в предположении >, за счет введения ОП для обслуживания заявок оперативной обработки, требования к качеству обслуживания заявок реального времени можно обеспечить с экономией производительности ресурса системы (в рассматриваемом случае – «узкого места») в раз, причем в отличие от метода построения приоритетного расписания здесь выигрыш может быть получен и для системы реального времени с бесприоритетным обслуживанием.
В предположении, что и имеем . Зависимости представлены на рис. 2.19, который иллюстрирует целесообразность приоритетного (в смысле ДОСП) обслуживания заявок реального времени при условиях, во-первых, , во-вторых, .
Рис. 2.19
Эффективность введения в систему внеочередных заявок ОП (как отмечалось, можно рассматривать как подход, альтернативный способу обслуживания с абсолютными приоритетами для распределенных ВС, для которых прерывание взаимодействия абонента с ресурсом связано с большими временными потерями и дополнительной сложностью децентрализованного управления доступом к ресурсу) имеет смысл оценивать мерой внеочередности их обслуживания или предоставляемым для них значением параметра , составляющим для одной заявки ОП (при двух и более заявок ОП уже необходимо учитывать реализуемую для них ДО).
Для оценки характеристик обслуживания заявок при бесприоритетном кодовом управлении множественным доступом в рассмотренных ранее предположениях можно использовать известное выражение [1]
,
Это обусловлено тем, что в отличие от методов опроса очередей здесь отсутствует передача прав в явном виде, а складывается из двух составляющих и ( где в рассматриваемом случае ), при этом на параметр W не сказывается несимметричность загрузки системы.
Очевидно, что при реализации кодового управления множественным доступом к ресурсу, возможности повышения эффективности доступа заложены в решении задачи оптимального кодирования приоритетов абонентов системы и в выборе эффективных способов передачи прав на занятие ресурса между абонентами системы. Данным аспектам
диспетчеризации заявок при кодом управлении множественным доступом будут посвящены следующие разделы.
Данный раздел посвящен исследованию проблемы повышения эффективности кодового управления множественным доступом к связному ресурсу, что актуально для альтернативных приложений ЛВСРВ и ЛВСКО. Это обусловливается небольшими размерами передаваемых пакетов данных абонентами при занятии канала связи (а в ряде приложений, например в технологии ATM, и отказом от контроля передаваемых данных - контролируется только управляющая часть ячейки), что делает затраты времени на арбитраж даже при кодовом управлении множественным доступом к связному ресурсу сопоставимыми с продолжительностью взаимодействия абонентов при получении доступа к каналу связи.
Замечание. Здесь и далее говорим о кодировании ОП абонентов ЛВС, однако аналогично задача формулируется и решается при кодировании ОП заявок на обслуживание.
Ранее показано, что при кодовом управлении множественным доступом осуществляется арбитраж заявок по каждому разряду кода ОП , (число которых при равномерном коде [] , где D - основание кода), на каждый из которых приходятся удельные затраты , откуда получаем
(3.1)
Выражение (3.1) определяет альтернативные пути уменьшения затрат времени на управление множественным доступом при кодовом управлении , задаваемые изменением параметров и . Первый из них может быть сформулирован в постановке задачи оптимального кодирования: для заданного вероятностного ансамбля {} [4], где - распределение вероятностей заявок на множестве M , найти множество кодов ОП длиной, , обращающих в минимум среднюю скорость кодирования
Для решения рассмотренной классической задачи теории информации может быть использован метод Хаффмена [4]. Альтернативный подход - снижение потерь за счет уменьшения связан с выбором механизма передачи прав на доступ к ресурсу между абонентами системы. Этот вопрос будет рассмотрен в следующем разделе.
Особенностью иной постановки задачи оптимального кодирования ОП будет необходимость учета более высокого приоритета уровня «1» над уровнем «0» (пусть исходно задали таким образом) в каждом разряде кода ОП, т.к. значением «1» в разряде кода приоритета абоненту предоставляется право занять ресурс, по значению «0» не предоставляется. Множество абонентов с заданной на нем вероятностью p требований общего ресурса, одинаковой для всех абонентов системы, называется математической моделью равномерного поэтапного кодирования/декодирования (или просто поэтапного кодирования) пользователей общих ресурсов: {M, N, , , }. Величина p здесь является характеристикой интенсивности поступления в систему требований ресурса.
Под величиной будем понимать вероятность однозначного декодирования m-го абонента по n из N разрядам кода приоритета при вероятности p обращения абонентом к общему ресурсу системы. Рассмотрим изменение величины при , соответственно при изменении p. Зависимости для случая представлены на рис. 3.1 (формула для расчетов приведена ниже), из которого следует, что при невысоких загрузках системы вероятность однозначного декодирования абонента не сильно изменяется с увеличением длины кодового слова, откуда может быть сделан вывод, что способ кодирования по всем N (имеется в виду равномерный код) разрядам кода приоритета в общем случае избыточен, особенно при малых загрузках системы.
Рис. 3.1
Другими словами, выше рассмотрен принцип поэтапного кодирования, состоящий в управлении множественным доступом поэтапно - по частям кода приоритета, с увеличением длины кода на каждом этапе, и, как следствие, при возможности неоднозначного декодирования абонента по используемой части кода приоритета - на всех этапах, кроме последнего. Нетрудно показать, что скорость поэтапного кодирования максимальна при использовании всех N разрядов в коде приоритета.
Замечание. Особенностью реализации принципа поэтапного кодирования является возможность предоставления права занять ресурс одновременно нескольким абонентам, что требует обнаружения конфликта информации в канале, что, в свою очередь, будет являться условием необходимости увеличения длины кода приоритета. Принцип поэтапного кодирования предполагает конфликтную передачу прав между абонентами системы на занятие ресурса.
Влияние условия - ОП «1» над «0» при занятии ресурса, которое необходимо учитывать при кодировании приоритетов абонентов, рассмотрим на простом примере. Определим вероятность однозначного декодирования абонента по одному разряду кода приоритета (имеется в виду - только по первому разряду , естественно в предположении, что здесь возможен конфликт), например для случая , т.е. рассмотрим следующие кодовые комбинации «0011», «0001», «0111». Имеем: - для комбинации «0011» , - для комбинации «0001» , - для комбинации «0111» .
Зависимости для рассматриваемых случаев представлены на рис. 3.2, из которого могут быть сделаны следующие выводы.
1. Эффективность способа кодирования зависит от изменения p.
2. Могут иметь место интервалы изменения величины p, когда неравномерное кодирование абонентов (неравное число единиц и нулей в кодовой комбинации) эффективнее равномерного кодирования (соответственно, число нулей и единиц в кодовой комбинации совпадает).
Из рис. 3.2 в частности видим, что на интервале изменения параметра эффективнее код «0111», на интервале изменения - код «0011», на интервале изменения - код «0001».
Рис. 3.2
Предельными случаями неравномерных кодов являются соответственно предельно неравномерные по «0» и по «1» коды, примеры которых для случая представлены соответственно на рис. 3.3.а и 3.3.б, первый из которых эффективен при , второй при , причем предельно неравномерный по «0» код обеспечивает поэтапный бесконфликтный арбитраж (бесконфликтное кодирование). Особенностью этих кодов будет максимальная эффективность соответственно при низкой и высокой загрузках системы. Другими словами, предельно неравномерные коды, по существу представляют собою предельные случаи кодирования, ориентированные, соответственно на низкую и высокую загрузки системы, и потому содержащие соответственно максимальное (по «1») и минимальное (по «0») число единиц в каждом кодовом слове кода, а любой применяемый
на практике неравномерный код будет занимать промежуточное положение между равномерным кодом ОП и соответствующим предельно неравномерным по «0» или по «1» кодом. Равномерный код отличается совпадением числа 1 и 0 в каждом кодовом слове.
Рис. 3.3
Эффективность неравномерного поэтапного кодирования можно оценить по критерию «скорость однозначного поэтапного неравномерного кодирования по разрядам»
где - вероятность однозначного декодирования абонентов по разрядам кода ОП.
Под полной математической моделью поэтапного кодирования приоритетов абонентов понимается математическая модель равномерного поэтапного кодирования, учитывающая параметр или, соответственно, кодовая вероятностная модель, учитывающая параметр p. Или особенностью полной математической модели будет наличие уже двух параметров p и различно влияющих на выбор оптимального способа кодирования: p - задает возможность эффективного поэтапного кодирования, в результате в качестве оптимального может быть получен неравномерный код; - задает возможность эффективного полного кодирования, при этом в результате также в качестве оптимального может быть получен неравномерный код, причем в общем случае эти оптимальные неравномерные коды могут не совпадать.
В качестве критерия оптимальности также как и для модели поэтапного кодирования должен использоваться параметр , учитывающий параметр : - математическое ожидание скорости однозначного декодирования пользователя. Условием
оптимальности выбора способа кодирования будет или с учетом дискретности исходного набора альтернативных вариантов кодирования имеем
,
где - параметр для k-го способа кодирования из сравниваемого множества вариантов K, где
Заметим, что в отличие от соответствующих формул, приведенных ранее, здесь уже учитывается не только число единиц в кодовых комбинациях разряда кодов ОП абонентов, но и то, каким абонентам (соответственно, с какими значениями параметра ) принадлежат значения единиц.
Утверждение. Всегда можно построить оптимальный код, который будет эффективнее случайного назначения кодов ОП.
Доказательство. Нетрудно показать, что метод случайного задания кодов ОП в среднем имеет характеристики обслуживания ниже, чем метод равномерного поэтапного кодирования, который неэффективен при низких и высоких загрузках системы. В области эффективного использования равномерного кода случайное задание кодов ОП неэффективно, т.к. не гарантирует однозначного декодирования абонента по разрядам кода.
Данное утверждение приведено с той целью, чтобы показать, что в рамках концепции кодового управления, в частности при оптимальном кодировании ОП абонентов, всегда можно получить конфликтный способ управления множественным доступом в реальном времени, который будет эффективнее для конкретных приложений, чем широко используемые в ЛВСОО случайные методы [8, 11], основным достоинством которых можно считать простоту реализации. Действительно, здесь не требуется поддерживать и, как следствие, восстанавливать в случае искажения какой-либо очереди передачи прав. Это делает данный метод, регламентируемый, например стандартами IEEE 802.3, TOP [8, 11] сегодня наиболее широко применяемым в ЛВСОО и ЛВССОО где отсутствуют жесткие ограничения на продолжительности обработки заявок.
Определяющим при реализации оптимального способа кодирования является эффективное использование общего ресурса абонентами ВС. Однако, как отмечалось ранее - это следует из системы (1.1), изменением значения можно задавать (изменять) приоритет абонента, влияя при
этом на величину гарантированного времени обслуживания заявки . Это актуально при небольшой величине информационного кадра. Однако, как отмечалось выше, сегодня выполнение данного условия характерно как для управляющих, так и для информационных ВС. Например, при , в рамках концепции АТМ получаем, что затраты составляют 15% затрат времени на передачу информационного кадра (8/53). Очевидно, что в рамках кодирования ОП абонентов может быть реализован принцип приоритетного кодирования, который состоит в кодировании ОП более важного абонента более коротким кодовым словом, с целью минимизации продолжительности доступа к ресурсу именно более приоритетного пользователя. Такой подход, справедлив из соображений учета важности абонентов, но в общем случае не дает оптимального кода в смысле эффективного использования ресурса, т.к. при кодировании приоритетов здесь уже учитываются не параметры потока требований ресурса, а исключительно важность абонентов друг относительно друга. Таким образом под приоритетным будем понимать такое кодирование приоритетов абонентов в системе с множественным их доступом к общим ресурсам, при котором целью кодирования является учет относительной важности абонентов.
Замечание. По существу, это также метод оптимального кодирования, но эффективность использования ресурса здесь уже определяется не характеристиками входного потока его требований, а возможностью назначения приоритетов реального времени (назначением приоритетов в соответствии с детерминированной моделью обслуживания в реальном времени).
Постановка задачи приоритетного кодирования выглядит следующим образом. Пусть задано множество абонентов системы {M, } характеризуемых различной важностью, которую требуется учитывать реализацией заданных соотношений длин кодов ОП , . Требуется осуществить кодирование ОП - сопоставить множеству абонентов M множество кодов приоритетов {, }, каждое из которых имеет исходно заданную длину , обеспечивающее взаимно однозначное отображение множества абонентов во множество кодовых слов и наоборот.
Рассмотрим метод приоритетного кодирования или метод построения в ВС приоритетных кодов ОП абонентов. Очевидно, что прежде всего при решении рассматриваемой задачи кодирования необходимо определить допустимые соотношения длин кодов приоритетов в системе, что позволит проверить возможность построения кода приоритета с заданным соотношением длин кодов, а при невозможности, скорректировать задаваемое соотношение. Другими словами, имея исходно заданные соотношения длин кодов, необходимо определить возможность построения приоритетного кода в принципе.
Например, возможно ли осуществить приоритетное кодирование с основанием 2 ОП семи абонентов системы кодами приоритетов с длинами (числом разрядов): 2,2,3,3,3,3,4 ? Имея положительный ответ на данный вопрос, уже можно приступать к решению собственно задачи кодирования.
Возможность построения приоритетного кода с заданными длинами кодов ОП абонентов (в общем случае неравномерного) в полной мере определяется свойствами однозначного кодирования. Поэтому здесь можно использовать неравенство Крафта для префиксных кодов [4], которое гласит, что для существования префиксного кода в алфавите объема D с длинами кодов , необходимо и достаточно, чтобы выполнялось условие:
(3.2)
С использованием этого неравенства может быть сформулировано условие допустимости соотношений длин кодов приоритетов абонентов при их приоритетном кодировании кодом с основанием D - может быть выбрано соотношение длин кодовых слов , , при котором выполняется неравенство (3.2).
Вернемся к нашему примеру и проверим выполняемость неравенства Крафта. Имеем , т.е. префиксный код не может быть построен. Изменим условие, рассмотрим соотношение длин кодовых слов: 2,2,3,3,3,4,4, имеем , неравенство Крафта выполняется, или может быть построен префиксный код (равенство 1 означает, что данный код не может быть улучшен).
Метод приоритетного кодирования, учитывающий задаваемое соотношение длин кодовых слов, отражающее приоритетность абонентов системы основывается на следующих положениях:
- кодирование приоритетов абонентов начинается с младшего разряда с переходом к более старшему разряду кодового слова;
- анализируемому разряду кода приоритета с меньшей заданной длиной кодового слова присваивается значение «1» (более приоритетное значение для арбитража требований ресурса), с большей длиной кодового слова - значение «0»;
- при кодировании учитывается, что Q абонентов с равной заданной длиной кода приоритетов при кодировании должны различаться в [] старших разрядах кодового слова, где [a] - большее целое числа a.
Применение метода для получения кода ОП абонентов для рассмотренного выше примера проиллюстрировано на рис. 3.4.
Рис. 3.4
Будем говорить, что кодирование приоритетов абонентов, предполагающее неизменное соответствие кодов приоритетов абонентам в течение всего времени функционирования системы, называется статическим кодированием ОП абонентов ВС. Однако изложенная концепция обслуживания по расписаниям предполагает смену ОП в процессе функционирования системы, а следовательно и смену по расписанию кодов ОП абонентов при реализации децентрализованного кодового управления множественным доступом к ресурсу. Будем говорить, что кодирование ОП абонентов, предполагающее изменение ОП в соответствии с какой-либо заданной очередностью в процессе функционирования системы, называется динамическим кодированием ОП абонентов ВС. Другими словами, статический код с заданными очередностью и моментами времени изменения его при функционировании системы называется динамическим кодом.
Выше речь шла об оптимальном (либо в смысле эффективности использования ресурса, либо в смысле приоритетности доступа к ресурсу отдельными абонентами) статическом кодировании, где в качестве критерия оптимального выбора статического кода использовалась скорость (средняя скорость) кодирования. При изменении же кодов ОП в процессе функционирования ВС возникает проблема оптимального изменения исходных кодов ОП, реализующих достоинства исходных оптимальных кодов в процессе функционирования системы, или принципов оптимального динамического кодирования ОП абонентов ВС.
Очевидно, что динамический код можно рассматривать как конечное множество статических кодов, где каждый из статических кодов ( пусть в динамическом коде их M, ) характеризуется определенной средней скоростью кодирования . С учетом этого, можем ввести понятие средней скорости динамического кода , которая может рассматриваться как математическое ожидание скоростей кодирования применяемых статических кодов с учетом вероятности их появления в динамическом коде, замкнутый граф которого содержит M вершин - моменты времени , , каждая
из M вершин в замкнутом графе динамического кода встречается ровно раз
,
где
, ,
причем с целью эффективного использования ресурса оптимальный динамический код следует выбирать из условия: .
С учетом сказанного, может быть сформулирован следующий принцип оптимальности динамического кода - динамический код будет реализован в системе оптимальным образом в том случае, если в каждый момент времени приоритеты абонентов системы закодированы оптимальными статическими кодами. С учетом сформулированного критерия оптимальности и предложенных ранее методов статического кодирования рассмотрим методы оптимального динамического кодирования.
В общем случае можно выделить следующие альтернативные способы изменения статического кода: сквозное и групповое динамическое изменение кодов. Под сквозным изменением кодов приоритетов абонентов понимается циклическое изменение (уменьшение , либо увеличение) на единицу значений кодов приоритетов при каждом изменении момента времени . Пример графа динамического кода со сквозным кодированием для случая представлен на рис. 3.5. Средняя скорость динамического кода в рассматриваемом случае совпадает со скоростью равномерного статического кода R.
Под групповым изменением кодов приоритетов абонентов понимается такое изменение кодов, при котором сохраняются исходные группы (по каждому отдельно взятому разряду) абонентов, имеющие одинаковые значения этого разряда кода приоритета, причем, если значение разряда изменяется на противоположное, оно изменяется у всех абонентов группы.
Рассмотрим алгоритм группового изменения статических кодов, регламентирующий очередность смены кодовых слов.
1. Инвертируется первый (младший) разряд кода приоритета.
2. Инвертируется второй разряд кода приоритета.
3. Инвертируется первый разряд кода приоритета.
4. Если код приоритета содержит два разряда, инвертируется второй разряд, переход к п.п. 1.
5. Инвертируется третий разряд кода приоритета.
6. Выполняются п.п. 1 - п.п. 3 алгоритма.
7. Если код приоритета содержит три разряда, инвертируется третий разряд, переход к п.п. 1.
8. Инвертируется четвертый разряд кода приоритета.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
k-1. Если k разрядов в коде приоритета, инвертируется k разряд, переход к п.п. 1.
k. Инвертируется k-й разряд.
k+1. Выполняются п.п. 1 - п.п k алгоритма.
k+2. Если разрядов в коде приоритета, инвертируется -й разряд, переход к п.п. 1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Пример графа динамического кода при групповом кодировании для случая представлен на рис. 3.6.
Рассмотрим условия применения альтернативных способов динамического кодирования, с учетом того, что в зависимости от исходного задания входного потока требований ресурса в качестве оптимальных могут быть получены следующие статические коды: равномерный и неравномерный, полный и неполный (поэтапное кодирова ние/декодирование).
Рис. 3.5
Рис. 3.6
Утверждение. Способ сквозного изменения кода при динамическом кодировании позволяет получить оптимальный динамический код при использовании в качестве статического равномерного полного или неполного кодов.
Доказательство. При циклическом изменении кода из одного полного равномерного кода всегда получается другой полный равномерный код. В случае неполного равномерного кода при циклическом изменении кода из равномерного кода получается равномерный код, причем в результате такого изменения сохраняется число единиц и нулей в каждой кодовой комбинации любого отдельно взятого разряда кодов приоритетов абонентов (сохраняется
число и изменяется их принадлежность, но для неполного кодирования важным является именно сохранение числа единиц и нулей).
Утверждение. Способ группового изменения кода при динамическом кодировании позволяет получить оптимальный динамический код при использовании в качестве статического неравномерного полного кода.
Доказательство. Особенностью группового изменения кода является то, что сохраняются исходные группы абонентов, одинаково закодированных по отдельно взятому разряду. Это означает, что сохраняется соотношение длин приоритетов между абонентами в различные моменты времени . В рассматриваемом случае (входной поток требований определен параметром ) важно сохранение соотношения длин между группами абонентов , что здесь и обеспечивается.
Пример графа динамического кода для случая , при использовании в качестве оптимального статического неравномерного полного кода, представлен на рис. 3.7.
Замечание. В данном способе динамического кодирования внутри отдельных групп может использоваться как сквозное, так и групповое кодирование.
Способ группового динамического кодирования, позволяющий сохранять исходные длины кодов приоритетов групп абонентов в процессе функционирования ВС будем называть кодированием с сохранением длины кодов групп.
Утверждение. Способ группового изменения кода при динамическом кодировании позволяет получить оптимальный динамический код при приоритетном статическом кодировании ОП абонентов.
Доказательство. Как отмечалось, особенностью группового изменения кода является то, что здесь сохраняются исходные соотношения длин между группами абонентов. Именно это свойство кода должно быть реализовано при приоритетном кодировании, т.к. исходной длиной кода здесь реализуется приоритет абонента.
Рассмотрим случай, когда в качестве оптимального выбирается неполный (поэтапное кодирование) код. Для реализации динамического кода в этом случае не может эффективно использоваться ни способ сквозного изменения кодов, ни рассмотренный способ группового изменения кодов приоритетов, т.к. особенностью рассматриваемого статического кода будет следующее - в предположении, что различные абоненты имеют равные вероятности занятия ресурса и поток заявок определяется лишь его интенсивностью, важным становится уже не длина кодов приоритета групп абонентов , а то, сколько абонентов имеют значение «1» в каждом отдельно взятом разряде кода приоритета (или число единиц в каждом кодовом слове). Здесь также должен быть реализован принцип группового кодирования, однако особенность получения динамического кода здесь состоит в том, что групповое кодирование осуществляется и внутри каждой
исходной группы абонентов (в групповом коде, приведенном выше, допускалось сквозное кодирование внутри групп).
Пример группового динамического кода, сохраняющего число единиц в отдельно взятом разряде для случая приведен на рис. 3.8.
Рис. 3.7
Рис. 3.8
Способ группового динамического кодирования, позволяющий сохранять исходное число единиц в отдельно взятом разряде будем называть кодированием с сохранением числа единиц в отдельно взятом разряде. Утверждение. Способ группового изменения кода при динамическом кодировании с сохранением числа единиц в отдельно взятом разряде позволяет получить оптимальный динамический код при использовании в качестве статического неравномерного неполного кода при задании потока требований параметром p.
Доказательство. Рассмотренный способ кодирования позволяет сохранять число единиц в каждом отдельно взятом разряде кода приоритета (или в каждом кодовом слове), соответственно, исходную неравномерность кода, определяемую соотношением числа единиц и нулей в каждом отдельно взятом разряде. Следовательно, в любой момент времени статический код здесь будет оптимальным.
Кроме рассмотренных методов динамического кодирования, учитывающих либо свойства входного потока требований ресурса, либо приоритетные свойства абонентов, на практике может быть применен метод кодирования, обеспечивающий минимальную гарантированную скорость динамического кодирования. Под гарантированной скоростью динамического кодирования приоритетов абонентов будем понимать суммарную скорость статического кодирования приоритетов, определяемую в моменты времени
.
Физический смысл гарантированной скорости динамического кода следующий - задает максимальное число разрядов, по которым должен быть произведен арбитраж при предоставлении прав занять ресурс m-му абоненту, при наличии требований ресурса у всех M абонентов системы. С учетом коэффициентов повторяемости моментов времени в цикле расписания : , , гарантированная скорость динамического кодирования приоритета m-го абонента
.
Метод динамического кодирования с минимальной гарантированной скоростью основывается на следующих утверждениях.
Утверждение. Выполнение условия достигается в том случае, когда , соответственно
.
Доказательство. Для того, чтобы один код мог быть отделен от другого минимум должен быть произведен арбитраж требований по одному разряду кода приоритета. Подставив имеем
,
.
Утверждение. Условие выполняется в том случае, когда динамический код реализуется по следующему правилу: в любой
момент времени в старшем разряде кода приоритета (именно с него начинается арбитраж требований) только наиболее приоритетного в этот момент времени абонента находится «1», у остальных абонентов системы в этом разряде «0».
Доказательство. Утверждение доказывается тем, что при рассмотренных условиях арбитраж требований ресурса может быть осуществлен только по одному (старшему) разряду кода приоритета, т.е. выполняется условие: .
Пример построенного с учетом приведенных правил динамического кода для случая представлен на рис. 3.9. Получили неравномерный код со значением параметра (бита) или в 2 раза меньше, чем для равномерного кода.
Рис. 3.9
Очевидно, что средняя скорость кодирования при реализации данного способа увеличивается не более чем на 1 (вводится еще один разряд).
Достоинством рассмотренного метода динамического кодирования будет то, что при весьма незначительном ухудшении статических скоростей кодирования в моменты времени (в общем случае здесь имеем уже неоптимальные коды) не более чем на 1, может быть достигнуто весьма существенное улучшение параметра , крайне важного для систем реального масштаба времени, определяющего возможность построения системы.
Оценим получаемый выигрыш от использования метода. Если длина наиболее приоритетного кода в моменты времени , составляет (в общем случае неравномерный код) имеем
или
.
Замечание. При реализации приоритетной дисциплины обслуживания требований ресурса рассмотренный метод динамического кодирования
реализуется также. Отличие здесь состоит лишь в другой очередности и частоте смены моментов времени , .
В завершение исследования вопросов кодирования приоритетов абонентов ВС сформулируем и докажем весьма важное утверждение.
Утверждение. При реализации в системе ДОСП динамическая смена ОП абонентов ВС по расписанию должна происходить как при занятии ресурса заявкой реального времени, так и при занятии ресурса заявкой оперативного обслуживания (т.е. при занятии ресурса любой заявкой).
Доказательство. Утверждение доказывается тем, что в противном случае - при изменении ОП только занятием ресурса заявкой реального времени, параметр приоритетной заявки реального времени увеличится на () - считаем их соответственно совпадающими для всех абонентов ВС.
Реализация передачи прав на занятие ресурса в ЛВС в соответствии с оптимальными кодами ОП рассматривается в следующем разделе.
Как ранее отмечалось, в общем случае принцип кодового управления предполагает поразрядное сравнение кодов ОП при управлении доступом к ресурсу при котором в бит-синхронном, либо ином режиме канал, который по приему должен быть доступен всем абонентам системы, занимается передачей зонда абонентами. Поступление из канала значения зонда «1» абоненту, имеющему в анализируемом разряде менее приоритетное значение «0», исключает данного абонента из дальнейшей «борьбы за ресурс» проводимой процедуры кодовой передачи прав с целью бесконфликтного занятия ресурса.
Альтернативные способы кодирования ОП - полное и поэтапное, обусловливают целесообразность использования двух видов зонда, в качестве которого может использоваться либо разряд кода ОП (уровни логических «0» или «1») при полном кодировании, либо собственно информационный кадр при поэтапном кодировании - здесь при «борьбе за ресурс» абонентами, имеющими «1» в анализируемом разряде кода ОП, выдается в канал уже информационный кадр (абоненты, имеющие «0» в разряде кода канал не занимают). В обоих случаях возможен конфликт данных в канале - в первом
случае - разрядов зонда, во втором - информационных сообщений. Так как поэтапное кодирование не гарантирует однозначного декодирования абонента по части кода при информационном (в общем случае конфликтном) методе реализуется процедура обнаружения конфликта, например по искажению несущей частоты - аналогично тому, как это делается для случайных методов управления множественным доступом CSMA-CD в ЛВСОО. По способу зондирования канала рассмотренные методы можно разделить на зондовый конфликтный метод и информационный конфликтный метод.
Под зондовым конфликтным методом кодового управления множественным доступом понимается метод, реализующий механизм зондирования канала специальными сигналами, соответствующими логическим значениям разрядов кода приоритета абонентов при полном (равномерном, либо неравномерном) кодировании, с возможностью обнаружения наложений (конфликтов) разрядов зонда в канале.
Замечание. При кодировании приоритетов абонентов кодами, имеющим основание 2 (частный, но наиболее просто реализуемый случай), разряд зонда при «борьбе за ресурс» в канал могут выдавать лишь абоненты, имеющие значение этого разряда «1». Имеющие в разряде «0» канал не занимают, а при получении из канала «1» прекращают «борьбу за ресурс».
Под информационным конфликтным методом кодового управления множественным доступом понимается метод, реализующий механизм зондирования канала непосредственно информационными сообщениями абонентами, имеющими в разряде кода приоритета, по которому осуществляется «борьба за ресурс», «1», при поэтапном (равномерном, либо неравномерном) кодировании, с возможностью обнаружения наложений (конфликтов) информационных кадров в канале по искажению несущей частоты.
В общем случае возможны два способа передачи полномочий по каналу связи - асинхронный и синхронный. Под асинхронным способом передачи полномочий понимается передача права занять ресурс между абонентами сигналом (сигналами, в частности коротким пакетом - маркером), поступающим по каналу связи, либо по специально отведенным под эти цели управляющим линиям (линиям арбитража), под синхронным способом передачи полномочий понимается передача прав временными интервалами, синхронизирующими начало передачи информации каждым абонентом системы.
В частности, после обнаружения конфликта в канале и соответствующем переходе к арбитражу по следующему разряду кода приоритета, при асинхронной передаче прав перед началом зондирования в канале должен появиться сигнал, означающий переход к зондированию по следующему разряду, при синхронной передаче прав переход к зондированию по следующему разряду осуществляется через фиксированный
интервал времени после завершения зондирования по предыдущему разряду кода приоритета абонентов.
Утверждение. Для зондовых конфликтных способов целесообразно применять только синхронную передачу прав.
Доказательство. Утверждение доказывается тем, что в данном случае абоненты зондируют канал в синхронном режиме, при котором интервалы отсчитываются от момента начала зондирования по соответствующему разряду, последовательно по всем разрядам кода (полный код). При этом не имеет никакого смысла вводить кроме синхронной (которая и так имеет место) еще и асинхронную передачу прав.
Утверждение. Конфликт зондов в канале - это единственный способ передачи полномочий в соответствии с полным (не предельно неравномерным по «0») кодом.
Замечание. Строго говоря, и при информационном конфликтном способе может быть реализована передача полномочий в соответствии с полным кодом. При этом в случае отсутствия конфликта при передаче информационного сообщения, выдачу сообщения в канал надлежит прекратить, с целью последующей передачи полномочий , что естественно противоречит здравому смыслу.
Доказательство. С учетом изложенного выше, можем говорить, что имеют место лишь два способа передачи полномочий: асинхронный и синхронный. В данном случае одним из них полномочия передаются сразу нескольким абонентам Возникает проблема проведения арбитража между ними. При реализации синхронного арбитража имеем предельно неравномерный код. При любом способе передачи полномочий асинхронно без конфликта также имеем предельно неравномерный код, т.е. конфликт здесь обязателен, причем этот конфликт должен решать задачу арбитража среди конфликтующих по данному разряду кодового слова абонентов. Если имеем конфликт информационных сообщений, то получаем поэтапное кодирование. Из сказанного имеем, что для управления множественным доступом в рассматриваемом случае (полное кодирование) должен быть реализован конфликт в канале, но не информационных сообщений или конфликт каких-либо сигналов (зондов) по которому могут быть различимы (проведен арбитраж) конфликтующие абоненты системы.
В отличие от информационного конфликтного способа, где возможны два состояния канала при «борьбе за ресурс» - отсутствие передачи и передача информационного кадра, для зондового конфликтного способа уместно говорить о трех состояниях канала - отсутствие передачи, передача «0», передача «1». Поэтому здесь эффективно может использоваться кодирования приоритетов абонентов кодом по основанию 3, что естественно снижает потери времени на арбитраж при занятии ресурса. Пример кодов приоритетов абонентов в алфавите A = {*, 0, 1} для случая представлен на рис. 4.1.
Рис. 4.1
Зондирование канала абонентами реализуется следующим образом: по знаку «*» зонд не выдается, по знаку «0» выдается сигнал «0», по знаку «1» выдается сигнал «1». Пусть приоритетность знаков следующая: самый приоритетный «1», затем «0», затем «*». Наложение сигналов реализуется следующим образом: если зонд не выдается, абоненту со знаком «*» в разряде кода достаточно обнаружить любой сигнал в канале для снятия своего требования ресурса; абонент со знаком «1» не анализирует состояние канала после выдачи сигнала; абонент со знаком «0» выдает сигнал «0» в канал и проверяет его искажение ( при этом сигналы «0» не должны искажать друг друга), при искажении сигнала «0», которое здесь может быть осуществлено сигналом «1», абонент снимает свое требование ресурса. Замечание. В первом разряде отсутствует знак «*», этим разрядом должно производиться уведомление о занятии канала, или какой-то сигнал должен выдаваться в канал.
Для использования способа в реальном времени должны быть реализованы следующие правила динамического кодирования.
Правило 1. Код приоритета абонентов изменяется в результате циклического прибавления к нему знака *.
Правило 2. Сложение знаков * и * дает: * + * = 0.
Правило 3. Сложение знаков 0 и * дает: 0 + * = 1.
Правило 4. Сложение знаков 1 и * дает: 1 + * = ** (перенос знака * со сложением в следующий разряд).
Правило 5. При циклическом прибавлении знака * к коду 11...11 имеем: 11...11 + * = **...**.
Замечание. В рассмотренной классификации конфликтных методов кодового управления можно отвести место и известному случайному методу занятия канала с обнаружением наложения CSMA-CD - это информационный конфликтный метод (реализуется поэтапное кодирование) с синхронной передачей прав на занятие ресурса при случайном задании кодов приоритетов абонентов (в третьем разделе доказано, что этот метод всегда будет иметь более низкую эффективность, чем соответствующий конфликтный метод реального времени, для которого решена задача оптимального кодирования приоритетов абонентов).
Альтернативные варианты реализации информационных и зондовых конфликтных методов достаточно полно описаны в [12 - 18].
В предыдущем разделе было введено понятие предельно неравного по «0» кода приоритета абонентов, который может эффективно использоваться при высокой загрузке системы (). Отличительной особенностью данного кода, пример которого приведен на рис. 3.3.б, является наличие только одной единицы в каждом кодовом слове, что подразумевает бесконфликтную передачу прав - при зондировании канала по каждому разряду кода приоритета лишь один абонент системы может занять канал. С учетом двух способов передачи прав можно выделить два бесконфликтных метода кодового управления - асинхронный (названный нами в [12-18] счетным) и синхронный, общими условиями реализации которых будет:
- использование предельно неравномерного по «0» кода приоритета абонентов системы;
- каждый сигнал полномочий должен поступать всем абонентам системы;
- сигнал полномочий, поступающий абоненту, передает права в соответствии со значениями кодов приоритетов абонентов.
Идея асинхронного метода состоит в том, что полномочия передаются как и при маркерном методе по каналу, но не коротким пакетом - маркером, содержащим адрес абонента, которому предоставляются права занять ресурс, а отдельным сигналом, поступающим всем абонентам. Каждый полученный из канала сигнал означает для абонента переход к следующему разряду кода приоритета. Абонент, имеющий в разряде «1» может бесконфликтно занять канал информационным сообщением. Если сообщения для выдачи в канал абонент не имеет, он выдает асинхронный сигнал передачи полномочий, осуществляя этим переход к следующему разряду кода.
В общем случае возможны два вида сигнала асинхронной передачи полномочий – специальный сигнал и собственно канальный кадр, передача которого по каналу изменяет текущие значения ОП, а окончание взаимодействия разрешает занять канал абоненту с максимальным текущим ОП.
Аналогично реализуется и бесконфликтный доступ с синхронной передачей прав. Основной проблемой здесь является обеспечение абсолютной синхронизации абонентов, причем с децентрализованным управлением. С учетом того, что без дополнительной синхронизации система может функционировать достаточно непродолжительное время, надежно функционирующую синхронную систему можно получить, если реализовать следующий подход.
Пусть абонент при реализации синхронной передачи полномочий будет действовать следующим образом - занимать канал передачей какого-то сигнала в случае, если у него отсутствует сообщение для передачи, в
противном случае - в течение какого-то интервала времени оставлять канал незанятым. По истечение же данного временного интервала может занять канал под информационное взаимодействие. В данном случае по умолчанию все абоненты системы будут знать о прекращении передачи полномочий в системе (такой подход нами назван методом с естественной синхронизацией) [12-18].
Другим очевидным недостатком бесконфликтной передачи прав является их передача и при отсутствии в системе требований ресурса, что не только бессмысленно, но и снижает надежность системы в целом. Так как потребность в передаче полномочий возникает только когда в системе появляется по крайней мере требование ресурса от одного абонента, целесообразно и начинать их передачу именно в этом случае. При этом для запуска процедуры передачи полномочий (если она еще не запущена в системе), абонентом, требующим ресурс, должен выдаваться в канал специальный сигнал уведомления (заметим, что арбитраж требований этим сигналом не проводится, поэтому в младшем разряде кода приоритета всех абонентов в этом случае находится значение «1», что увеличивает на 1 разряд длину кода приоритета всех абонентов системы). Получив из канала этот сигнал, все абоненты запускают децентрализованную процедуру передачи полномочий (при этом может быть использован любой из способов передачи полномочий, как синхронный, так и асинхронный). Данная группа бесконфликтных методов названа нами методами с предварительном уведомлением о занятии ресурса [12], а реализуемый при этом подход к управлению множественным доступом - принципом управления с предварительным уведомлением о занятии ресурса.
В общем случае, в зависимости от загрузки системы, могут быть использованы три стратегии передачи полномочий после уведомления о появлении в системе требования ресурса, представленные на рис. 4.2.
Рис. 4.2
Первая стратегия предполагает необходимость уведомления перед каждым занятием ресурса (соответственно, альтернативный ей гипотетический вариант - это работа системы без предварительного уведомления), две остальные предполагают возможность занятия ресурса без уведомления при большом числе требований - функционально это означает, что при большом числе требований передача полномочий осуществляется без
предварительного уведомления, при малом числе требований процедура передачи прав запускается только в том случае, когда в системе появляются требования ресурса (или реализуется принцип адаптивной к загрузке системы передачи полномочий на занятие ресурса).
На сегодняшний день с целью повышения эффективности управления множественным доступом в широком диапазоне изменения нагрузки системы реализуются комбинированные методы, при этом, как правило, в рамках единой системы пытаются объединить методы, имеющие различные области эффективного использования, соответственно конфликтные, ориентированные на функционирование при низких загрузках системы, и бесконфликтные, эффективные при высоких загрузках. На практике это приводит к попыткам совмещения методов управления множественным доступом, имеющих совершенно различные механизмы передачи прав, как правило, это случайный CSMA-CD и маркерный методы.
Принцип кодового управления позволяет комбинировать подходы в рамках единого механизма управления множественным доступом - информационного конфликтного метода с синхронной, либо асинхронной передачей прав, или зондового конфликтного метода с синхронной передачей прав. Комбинирование здесь реализуется исключительно за счет смены исходных статических кодов, адаптивно к изменению загрузки системы в процессе ее функционирования с сохранением исходного механизма передачи прав. При этом могут быть достигнуты очень высокие результаты, что обусловливается возможностью достаточно плавного (без резких скачков) учета загрузки, за счет того, что между предельными вариантами кодов - предельно неравномерного по «1» для минимальной загрузки и по «0» для максимальной загрузки (бесконфликтная передача) находится множество кодов, которые могут быть использованы с соответствующими пороговыми значениями загрузки.
Таким образом, можно говорить о существовании единой концепции получения комбинированных методов, состоящей исключительно в изменении исходных статических кодов ОП абонентов адаптивно к изменению загрузки системы. В целом рассмотренный подход намечает возможность получения единой концепции реализации управления множественным доступом, сводящей все многообразие способов управления множественным доступом к нескольким обобщающим методам, в результате чего может быть поставлен вопрос об их унификации.
Обобщая сказанное ранее, делаем вывод о существовании следующих принципиально отличных подходов, конфликтных, различающихся способом зондирования канала и способом передачи прав к ресурсу, и бесконфликтных, отличающихся способом передачи прав. Кроме того, выше выделен класс комбинированных методов, получаемых в рамках конфликтных методов сменой статических кодов приоритетов абонентов. При этом единая концепция комбинирования методов обусловливает, что и бесконфликтные методы могут быть получены в рамках конфликтных, при использовании в них предельно неравномерных по «0» кодов приоритета абонентов системы. С учетом сказанного, делаем вывод, что все многообразие механизмов управления множественным доступом в рамках принципа кодового управления можно свести всего лишь к трем методам - информационному конфликтному с синхронной и асинхронной передачей прав на занятие ресурса, зондовому конфликтному с синхронной передачей прав. Все же многообразие методов, включая бесконфликтные и комбинированные, может быть получено в рамках трех перечисленных основных подходов, реализацией соответствующих кодов приоритетов абонентов.
Унифицированный ряд методов кодового управления множественным доступом представлен на рис. 4.3.
С целью исследования эффективности методов кодового управления множественным доступом реального времени могут быть применены вероятностные модели системы управления множественным доступом , позволяющие оценить средние затраты времени на передачу полномочий одному из активных абонентов системы после освобождения ресурса (или потери времени на арбитраж). Например, для ОЦП (в общем случае не представляет сложности получение вероятностных моделей и для приоритетных расписаний, однако при этом следует учитывать, что для каждого расписания необходимо получать свою модель) для зондового конфликтного метода управления множественным доступом вероятностная модель имеет вид
,
для информационного конфликтного метода
,
соответственно, для способа поочередной передачи полномочий - опрос очередей (в том числе, маркерного)
,
где - продолжительность передачи прав по одному разряду кода ОП, - затраты времени на обнаружение конфликта, - затраты времени на поочередную передачу прав между очередными абонентами в расписании.
Рис. 4.3
Зависимости , в предположении, что загрузка системы симметричная ( совпадают для всех M абонентов системы), для альтернативных подходов представлены на рис. 4.4 ( - период следования импульсов в канале связи - величина, обратная физической скорости передачи данных).
Рис. 4.4
Рис. 4.4 иллюстрирует высокую эффективность методов кодового управления при различии областей эффективного использования альтернативных подходов, что позволяет утверждать о перспективности применения изложенной концепции кодового управления множественным доступом в альтернативных приложениях ЛВСРВ и ЛВСКО. В свою очередь, предоставляемая возможность совмещения в рамках единого механизма управления доступом ДО с относительными и абсолютными приоритетами, при возможности совмещения такого обслуживания с обслуживанием по расписанию при высокой эффективности доступа к общим ресурсам при кодовом управлении позволяет утверждать и о высокой эффективности применения изложенной концепции в сосредоточенных ВС, в частности в многозадачных операционных системах реального времени, в первую очередь - специализированных.
Замечания.
1. В ЛВСРВ и ЛВСКО, как, впрочем, и в многозадачных операционных системах реального времени, при проектировании системы возникает проблема задания фиксированной продолжительности занятия ресурса абонентом , получившим право доступа, для информационного взаимодействия с ресурсом (для ЛВС определяется числом передаваемых байтов информации в пакете, для операционной системы - величиной кванта процессорного времени). При этом, с одной стороны, как отмечалось, в системах реального времени параметр следует уменьшать (именно при этом достигается эффект параллельности обработки, т.к. тогда в течение
меньшего интервала времени общий ресурс, являющийся «узким местом», монопольно используется одним абонентом), кстати говоря, именно сказанное ограничивает реализацию приоритетного обслуживания заявок изменением значений , с другой стороны, уменьшение ограничено потерями производительности ресурса (пропускной способности связного ресурса), связанными с затратами времени на передачу прав . Если параметры и сопоставимы (что имеет место в распределенных системах) уменьшение приводит к обратному эффекту - в системе так велики потери производительности, связанные с управлением множественным доступом к ресурсу (в ОС - переключение задач), что в ней теряет всяческий смысл параллельная обработка. Сказанное объясняет необходимость задания сегодня достаточно большим, что связано с низкой эффективностью управления множественным доступом, в частности при реализации расписаний опросом очередей (так в ATM каждой ячейкой переносится 48 информационных байтов, что в какой-то мере приводит к нарушению реального масштаба времени передачи соответствующих сигналов, т.к. имеем уже некоторое накопление информации - идеальной была бы передача 1 байта данных при 256 уровнях квантования сигнала [4]; продолжительность временного кванта в ОС QNX может достигать 100 мкс, что также может приводить к нарушению условий функционирования в реальном времени). Поэтому из сказанного делаем вывод, что эффективное решение задачи управления множественным доступом, позволяющее уменьшать потери без снижения эффективности обслуживания заявок, даст еще один эффект - позволит уменьшить , что, с одной стороны, позволит повысить эффект параллельности обработки для решаемых сегодня распределенными системами задач (т.е. качество обслуживания в реальном масштабе времени), с другой стороны, обеспечит эффективное решение новых задач в существующих системах, в частности реализовать в ЛВС новые виды служб связи.
2. К сосредоточенным ВС относятся системы, в которых абоненты находятся на небольших расстояниях друг от друга. В этом случае в шину могут дополнительно вводиться управляющие линии арбитража - здесь кодового управления - куда абоненты выдают разряды кодов ОП абонентов. При этом также могут быть реализованы все изложенные выше принципы кодового управления, однако здесь уже целесообразно использование в системе только зондового конфликтного метода управления с синхронной передачей прав, причем задача арбитража в данных приложениях может решаться одновременно с передачей данных, так используются различные линии шины для передачи кода приоритета и данных.
Таким образом, можем сделать вывод, что в рамках изложенной в монографии концепции диспетчеризации с децентрализованным кодовым управлением множественным доступом, можно реализовать эффективное управление распределением ресурсов для различных приложений ВС и ЛВС реального времени и комбинированного обслуживания, что достигается как за счет предоставляемых широких возможностей учета приоритетов заявок и абонентов системы, так и за счет возможности реализации альтернативных способов передачи прав на занятие ресурса. При этом рассмотренная концепция позволяет унифицировать как альтернативные подходы к обслуживанию заявок в рамках метода обслуживания с динамическими ОП, так и собственно механизмы передачи прав в рамках метода децентрализованного кодового управления множественным доступом.
4.5. Унификация методов для альтернативных топологий сетей связи.
4.5.1.Принципы реализации и классификация методов для альтернативных топологий ЛВС.
Ранее отмечалось, что особенностью шинной топологии ЛВС является отсутствие узлов коммутации в сети связи. Это обуславливает то, что информация, вызываемая любым абонентом, практически одновременно ЛВС набирает всем остальным абонентам сети (нами данный случай выделен как наиболее общий). Другая топология (например, кольцо и звезда) предполагает последовательный анализ поступающей через узлы коммутации информации, тем не менее, и в данных случаях возможно (и целесообразно) использование предложенных нами методов диспетчеризации. Однако отличие состоит в том, что здесь (ввиду последовательности обработки информации) уже возможны два подхода и решения задачи управления множественным доступом, которые рассмотрим на примере ЛВС кольцевой топологии, структура которой представлена на рис.4.5. Отличие подходов состоит в том - устанавливается ли
Абонент_1 Абонент_m Абонент_M
приоритетность занятия связного ресурса перед передачей информационного кадра (как это делается при шинной топологии зондовыми методами), либо сразу предается соотношения. При незанятости канала без предварительного арбитража. Однако, в данном случае, ввиду последовательности арбитража узлами коммутации (), появляется возможность избежать конфликтов при реализации информационных методов доступа, за счет передачи приоритета абонента, вызвавшего кадр, т.е. структура кадра в этом случае примет вид, где после открывающего флага следует код приоритета (КП) затем уже служебная информация . КП добавляется в заголовок, соответствующий MAC подуровни в соответствии с моделью ISO[ . . . ]. В этом случае абонент имеющий пакет для передачи канал связи с сформированным для него КП начинает выдачу пакета при отсутствии поступления другого пакета из канала на другой вход его УК. В противном случае УК сравнивает КП обоих пакетов, буферируя менее приоритетный и выдавая в канал более приоритетный пакет. При этом КП, передаваемые в пакетах, формируются по описанным выше правилам (в частности, здесь может быть реализован метод регистровых задержек).
С учетом сказанного, классификация методов кодового управления множественным доступом для топологии ЛВС, содержащих УК, принимает вид, приведенный на рис 4.6.
метод кадрового
управления
по способу занятия канала
зондовый информационный
по способу передачи КП
в служебном в поле заголовка
кадре-зонде МАС подуровня
информационного
кадра
рис 4.6
Замечание. При зондовом способа при незанятом канала в сигнальном кадре-зонде активный источник выдает зонд, который (как и при шинной реализации) поразрядно анализируется УК других абонентов, вступивших в конфликт, которые соответствующим образом в случае необходимости изменяет значения разрядов зонда на противоположные. По содержимому КП зонда, возвратившемуся из кольца на вход УК активного абонента, он принимает решения, выдавать ли пакет в канал или пропустить зонд более приоритетному активному абоненту, чтобы тот занял канал. Структура кадра-зонда кроме КП содержит служебное поле-признак зонда, данный способ напоминает собой шарнирное кольцо, однако в отличие от последнего позволяет реализовать рассмотренные выше преимущества принципа кодового управления.
Таким образом, предложенные в книге подходы могут быть реализованы и для других, промежуточных топологий ЛВС, причем в данном случае их реализация упрощается, за счет реализации последовательного анализа информации используемыми узлами коммутации.
Раздел 5. Обобщение методов
4.5.2.Принципы реализации и классификация методов для глобальных сетей связи.
Отличие кольцевой топологии ЛВС (а тем более топологии «звезда») от топологии глобальной сети не так велико, как шинной. Здесь также имеют место узлы коммутации, отличие состоит лишь в том, что много (а не одна как в ЛВС звезда) и каждый в общем случае характеризуется более чем двумя входами и более чем двумя выходами, рис.4.7.
УК
УК
УК
Рис. 4.7
Многочисленные каналы связи здесь уже образуют пучки линий. Однако здесь могут быть реализованы принципы кодового управления множественным доступом, аналогичные описанным выше. При этом в глобальной сети возможны два решения обслуживания: с установлением соединения и без установления соединения. В режиме установления соединения абонентом в сеть посылается специальный пакет-зонд, содержащий КП. Каждый УК анализирует КП зонда, поступающего с каждой линии(пучка), настраиваясь в соответствии с заданной для него ДО на обслуживание пакета, который затем будет передан абонентом, пославшим зонд другими словами, аналогично протоколу Х.25 здесь реализуется согласование качества обслуживания абонентом и сетью (УК) пакета перед его передачей абонентом в сеть, за счет выдачи абонентом значения КП в служебном пакете-зонде и настройки УК сети на обслуживание поступающего с данной линии пакета в соответствии с заданной ДО. Альтернативный подход, как и для кольцевых ЛВС, состоит в выдаче абонентом в сеть КП в заголовке информационного пакета, рис. 4.5. Поступившие же в УК пакеты уже должны обслуживаться в соответствии с реализованной в нем ДО.
Замечание. КП должны передаваться в заголовках сетевого уровня протоколов доступа и подсетям. В простейшем случае КП могут передаваться и в заголовках внутрисетевых протоколов, однако в данном случае ДО, реализуемая в УК может учитывать приоритеты входящих линий и пучков линий связи.
Таким образом, как и для кольцевых ЛВС, ДО здесь реализуется УК и возможна аналогичная классификация методов, приведенная на рис.4.8.
метод кодового управления
по режиму взаимодействия сети
с установлением без установления
соединения соединения
по способу передачи КП
в служебном кадре в поле заголовка
запроса на установление сетевого уровня
соединения информационного
кадра
рис 4.8
Таким образом, может быть сделан вывод о том, что рассмотренные принципы обслуживания в полном объеме могут быть реализованы как для различных топологий ЛВС, так и при построении глобальных сетей связи при альтернативных подходах и их реализации.
1. Алиев Т.И. Исследование методов диспетчеризации в цифровых управляющих системах. - Л.:ЛИТМО, 1984. - 82с.
2. Основы теории вычислительных систем/ Под ред. С. А. Майорова. М.:Высшая школа, 1978. - 410с.
3. Владимиров Н.А. Технология ATM: основные положения// Сети. 1996. - № 2. - С. 62-73.
4. Колесник В.Д., Полтырев Г.Ш. Курс теории информации. - М.:Наука, 1982. - 416с.
5. Колесниченко В.Е. Основные результаты для вероятностно временных характеристик систем циклического обслуживания// Автоматика и вычислительная техника. - 1991. - № 3. - С. 59-64.
6. Колесниченко В.Е. Простые аппроксимации распределения времени ожидания для локальных вычислительных сетей с маркерным доступом// Автоматика и вычислительная техника. - 1990. - № 1. - С. 49-54.
7. Мячев А.А., Степанов В.Н., Щербо В.К. Интерфейсы систем обработки данных. - М.:Радио и связь, 1989. - 416с.
8. Овчинников В.В., Рыбкин И.И. Техническая база интерфейсов локальных вычислительных сетей. - М.:Радио и связь, 1989. - 272с.
9. Организация последовательных мультиплексных каналов систем автоматического управления/ С.Т. Хвощ, В.В. Дорошенко, В.В. Горовой; Под общ. ред. С.Т. Хвоща. - Л.:Машиностроение, 1989. - 271с.
10. Прангишвили И.В., Подлазов В.С., Стецюра Г.Г. Локальные микропроцессорные вычислительные сети. - М.:Наука, 1984. - 176с.
11. Стандарты по локальным вычислительным сетям: Справочник/ В.К. Щербо, В.М. Киреичев, С.И. Самойленко. - М.:Радио и связь, 1990. 304с.
12. Щеглов А.Ю. Принципы арбитража с предварительным уведомлением о занятии канала данных// Электронное моделирование. - 1995. - 17, № 3. С. 35 - 41.
13. Щеглов А.Ю. Способы реализации работоспособного синхронного множественного доступа// Электронное моделирование. - 1994. - 16, № 3. С. 32 - 38.
14. Щеглов А.Ю. Ускоренное зондирование канала данный - новый принцип случайного доступа в локальных вычислительных сетях// Изв. РАН. Техническая кибернетика. - 1994. - № 2. - С. 129-136.
15. Щеглов А.Ю. Высокопроизводительный метод децентрализован ного кодового управления для неоднородной микропроцессорной системы// Кибернетика и системный анализ. - 1994. - № 2. - С. 176-180.
16. Щеглов А.Ю. Счетно-интервальный способ множественного доступа для ЛВС реального времени// Автоматика и вычислительная техника. 1991. - № 5. - С. 74-77.
17. Щеглов А.Ю. Алгоритм динамического изменения приоритетов для высокопроизводительного метода ДКУ реального времени// Кибернетика и системный анализ. - 1994. - № 5. - С. 179-181.
18. Щеглов А.Ю. Счетные методы множественного доступа - альтернативный способ асинхронной передачи полномочий на доступ к шинному каналу данных в локальных вычислительных сетях// Электронное моделиро вание. - 1995. -17, № 4. - С. 41-46.
19. Щеглов А.Ю. Высокопроизводительные счетные методы доступа для локальной вычислительной сети реального времени// Электронное моделирование. - 1992. - 14, № 2.- C.104-107.
20. Щеглов А.Ю. Элементы теории управления множественным доступом пользователей к общим ресурсам вычислительной системы// Вторая Международная конференция "Развитие и применение открытых систем". Тезисы докладов. - М.: Совет РАН по автоматизации научных исследований, 1995. - С.74-76.
21. Щеглов А.Ю. Ускоренный метод децентрализованного кодового управления доступом к моноканалу в реальном времени// Электронное моделирование. - 1993. - 15, № 3. - С.88-92.
22. Куконин А.Ю., Щеглов А.Ю. Методы децентрализованного управления доступом к каналу малых локальных вычислительных сетей// Управляющие системы и машины. - 1992. - № 7/8. - С.124-127.
23. Щеглов А.Ю. Приоритетные счетные методы доступа для локальных вычислительных сетей// Системы и средства телекоммуникаций. - 1992. - № 5/6. - С.40-42.
24. Щеглов А.Ю., Куконин А.Ю. Метод децентрализованного кодового управления доступом к каналу с передачей полномочий// Электронное моделирование. - 1991. - 13, № 6. - С.32-34.
СОДЕРЖАНИЕ
|
[0.0.0.1] Учебное пособие
[1]
[2] [2.1] 1.1. Классификация ЛВС. Основные понятия [2.2] 1.2. Общие принципы построения. Структура системы [2.3] 1.3. Задачи и методы управления множественным доступом к общим ресурсам [2.4] 1.4. Модель системы реального времени [2.5] 1.5. Условия эффективности приоритетного обслуживания в реальном времени [3] РАЗДЕЛ 2. МЕТОДЫ ДИСПЕТЧЕРИЗАЦИИ РЕАЛЬНОГО ВРЕМЕНИ [3.1] 2.1. Требования к ДО заявок в распределенных ВС реального времени [3.2] 2.2. Концепция обслуживания в реальном времени с динамическими приоритетами [3.2.1] 2.2.1. Основа построения приоритетных расписаний [3.2.2] 2.2.2. Принципы эффективной реализации приоритетного обслуживания в распределенной системе [3.2.3] 2.2.3. Дополнительные возможности обслуживания по расписаниям в рамках концепции кодового управления [3.2.4] 2.2.4. Дополнительные возможности обслуживания с многоуровневыми приоритетами [3.2.5] 2.2.5. Классификация ДО с динамическими приоритетами для ЛВС [3.3] 2.3. Понятие и свойства канонического расписания реального времени [3.4] 2.4. Модель системы обслуживания с кодовым управлением множественным доступом [4] РАЗДЕЛ 3. МЕТОДЫ КОДИРОВАНИЯ ПРИОРИТЕТОВ ЗАЯВОК НА ОБСЛУЖИВАНИЕ [4.1] 3.1. Принципы оптимального кодирования ОП абонентов [4.2] 3.2. Принципы приоритетного кодирования ОП абонентов [4.3] 3.3. Задачи и методы динамического кодирования ОП абонентов [5] РАЗДЕЛ 4. МЕТОДЫ КОДОВОГО УПРАВЛЕНИЯ МНОЖЕСТВЕННЫМ ДОСТУПОМ. ПРИНЦИПЫ УНИФИКАЦИИ [5.1] 4.1. Конфликтные методы кодового управления [5.2] 4.2. Бесконфликтные методы кодового управления [5.3] 4.3. Единая концепция комбинирования методов [5.4] 4.4. Унифицированный ряд методов кодового управления [6] ЛИТЕРАТУРА |