В ЛВС РЕАЛЬНОГО ВРЕМЕНИ

А. Ю. ЩЕГЛОВ

МЕТОДЫ ДИСПЕТЧЕРИЗАЦИИ ЗАЯВОК НА ОБСЛУЖИВАНИЕ

В ЛВС РЕАЛЬНОГО ВРЕМЕНИ

Учебное пособие

ВВЕДЕНИЕ

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

Особое место среди ЛВС занимают проблемно-ориентированные ЛВС (ЛВСПО), в частности ЛВС, используемые в задачах управления (УВС) - в системах автоматического управления (САУ) и на нижних уровнях автоматизированных систем управления (АСУ). В соответствии с требованиями к работе ЛВС в реальном масштабе времени протекания управляемого процесса, функционирование ВС здесь характеризуется жесткими ограничениями, накладываемыми на время реакции системы на входные воздействия, значения которых могут быть достаточно малы (могут составлять миллисекунды и их доли). При возможности существенного увеличения мощности отдельных вычислителей ЛВС, реализующих отдельные функции общей задачи, решаемой ЛВС, например путем объединения их в сосредоточенные ВС (магистрально-модульные УВС [7]), остается ограниченной эффективность межмодульных взаимодействий ЛВС, что вызвано требованиями к высокой помехозащищенности передачи данных между вычислителями (в современных стандартах на интерфейсы распределенных УВС физическая скорость передачи данных ограничивается единицами Мбит/с [7]). Отмеченные особенности ЛВС, с учетом того, что система может содержать десятки и сотни вычислителей, требующих высокой эффективности межмодульных взаимодействий, обусловливает, что связной ресурс является «узким местом» ЛВС, определяющим их производительность в целом, что требует эффективного решения задачи распределения прав на занятие ресурса между абонентами ЛВС, соответственно при аппаратурной реализации.

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

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

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

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

При изучении материала необходимо знание теоретических основ и математических методов теории вычислительных систем и сетей в объеме монографии [1], желательно знакомство с принципами управления множественным доступом к каналу связи ЛВС, изложенными, например в [8, 10, 11], и с методами оптимального кодирования [4]. В своих материалах автор полностью следовал терминологии, введенной и использованной в [1, 2].

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

Ограниченный объем пособия не позволяет изложить многие вопросы достаточно полно. Более подробно с ними можно ознакомиться с помощью дополнительной литературы [12 - 24].

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

1.1. Классификация ЛВС. Основные понятия

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

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

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

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

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

1.2. Общие принципы построения. Структура системы

В основе реализации современных распределенных ВС находятся следующие общие принципы построения:

- параллельность обработки, позволяющая создавать мощные коллективы вычислителей при различных принципах распараллеливания задач;

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

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

- решение задачи управления распределением прав между абонентами на доступ к «узкому месту» ВС - общему ресурсу, аппаратурными средствами, что обеспечивает высокую эффективность его использования в системе.

Структура распределенной системы с общими ресурсами, в основе построения которой лежат перечисленные принципы, представлена на рис. 1.2 - в качестве связного ресурса рассмотрим применение последовательного канала связи магистральной топологии – «общая шина».

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

Подобная структура отличается следующим:

- в системе отсутствуют какие-либо узлы коммутации, что обеспечивает «многоточечное» подключение абонентов к каналу связи [7] и, как следствие, максимальную надежность и модульность построения, а за счет одновременной обработки абонентами информации, поступающей из канала, и максимальную эффективность межмодульных взаимодействий;

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

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

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

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

Рис. 1.2

1.3. Задачи и методы управления множественным доступом к общим ресурсам

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

Классификация наиболее широко используемых сегодня в ЛВС методов диспетчеризации [1] представлена на рис. 1.3, реализующих их методов управления множественным доступом на рис. 1.4 [8, 10]. Среди ДО можно выделить бесприоритетные, реализующие случайный выбор одной из поступивших заявок, и обслуживание в циклическом порядке (ОЦП), когда все очереди заявок опрашиваются последовательно одна за другой в циклическом порядке; приоритетные ДО с относительными приоритетами (ОП), при которых после освобождения ресурса его занимает активная заявка с наиболее высоким ОП. На практике реализуются два подхода к заданию ОП заданием фиксированным значением кода адреса в системе, либо местом подключения абонента к связному ресурсу.

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

Следуя классификации интерфейсов ЛВС реального времени [7] можно выделить: магистрально-модульные ВС, где последовательный канал связи имеет длину, как правило, до 10 метров: стандарт Bitbus, SSB (в интерфейсах Multibus), NUBUS, Fastbus, I²C, D²B и др.; рассредоточенные ВС - здесь в качестве передающей среды уже используется последовательный канал связи, имеющий длину от сотен метров до километров при возможности ее наращивания активными ретрансляторами. К таким интерфейсам относятся: интерфейс распределенной магистрали (ИРМ), интерфейс линейной связи с последовательной передачей информации (ИЛПС), MAP, PROWAY, (MAP, PROWAY - регламентируют правила построения ЛВС реального времени), MIL-STD-1553B и др.

Методы же управления множественным доступом, реализуемые для рассматриваемых интерфейсов с учетом представленной на рис. 1.4 классификации, следующие: маркерный (в частности сюда относится и предельный случай эстафетной смены задатчика - метод Polling - при смене задатчика или центрального узла каждым сигналом передачи прав) - наиболее широко применяемый метод, например в Bitbus, ИРМ, ИЛПС, PROWAY, MAP, MIL; и метод ДКУ, используемый в I²C и D²B [7]. Метод ДПВУ нашел применение лишь в сосредоточенных ВС с параллельной системной магистралью (И-41, VME-bus и др.), где приоритет абонентов убывает по мере удаления модулей «по гирлянде». Здесь применяется и метод ДКУ (в данных приложениях можно рассматривать как комбинированные ДКУ и ДПВУ), причем разряды кода, либо признаки занятия ресурса абонентами группы, подаются по специальным выделенным для этой цели управляющим линиям шины (И-41, Multibus I, II и др.) [7].

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

В ЛВС, используемых в современных информационных системах, широкое использование находит случайный метод управления множественным доступом, в частности CSMA-CD (с обнаружением наложения) [8, 10, 11], реализующий бесприоритетную ДО с передачей прав случайным образом. Однако, данный подход уже не удовлетворяет современным сетевым технологиям, реализующим интеграцию служб связи, в том числе и реального времени, как при асинхронной передаче данных - ATM - в ЛВС технологии ATM используется маркерный метод управления доступом к магистральному каналу [3], так и при синхронной передаче - ISDN. Для этих приложений необходимы эффективные методы управления множественным доступом реального времени, реализующие приоритетные расписания. Такие методы могут быть получены лишь в том случае, если удастся отказаться от механизма опроса очередей при реализации расписаний, в том числе и приоритетных.

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

Так как основными требованиями к качеству построения и функционирования ВС реального времени является выполнение временных ограничений в обслуживании заявок, то распределенную ВС реального времени можно описать детеминированной моделью. К временным параметрам обслуживания заявок относятся величины: - продолжительность занятия ресурса , абонентом для информационного с ним взаимодействия, - продолжительность передачи прав 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.

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

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

Пусть в систему реального времени поступает 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 абонентов могут вводиться приоритеты с целью эффективного использования «узкого места» - связного ресурса ЛВС.

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