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

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

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

ВВЕДЕНИЕ

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

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

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

А. Ю. ЩЕГЛОВ

Ссылки постраничные или в конце работы (нумерация сквозная)

…К концу царствования Петра I русский флот состоял из 48 линейных кораблей, а галер и других мелких судов считалось в нем 787. Экипажи кораблей составляли без малого 28000 человек[25]. Достигнут такой результат был за 25 лет, считая за начало постройку азовского флота.

Роль флота в системе вооруженных сил государства была образно выражена в "Морском уставе": "Всякий потентат (правитель), который едино войско сухопутное имеет – одну руку имеет, а который и флот имеет – обе руки имеет"[26]. На медали в честь победы над Швецией было выбито: "Конец сей войне таким миром получен ничем иным, токмо флотом, ибо землею никоим образом достигнуть того было невозможно"[27].

Петр говорил: "Умножение флота имеет единственно целью обеспечение торговли и пристаней; пристани эти останутся за Россией, потому что они сначала ей принадлежали; во-вторых, потому, что пристани необходимы для государства, ибо чрез сих артерий может здравее и прибыльнее сердце государственное быть”[28].

[25] Князьков С. Из прошлого русской земли. Время Петра Великого / С.Князьков. М. Планета, 191. С.156.

[26] Зверев Б. Страницы военно-морской летописи России / Б..Зверев. М. Просвещение, 1981. С.72.

[27] Там же. С. 46.

[28] Князьков С. Указ соч. С. 156.

Санкт-Петербург 1997

УДК 681.324

Щеглов А. Ю. Методы диспетчеризации заявок на обслуживание в ЛВС реального времени. Учебное пособие. - СПб.: ИТМО, 1997. - 77 с.

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

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

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

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

Рецензенты: докт.техн.наук, профессор Т.И.Алиев

докт.техн.наук, профессор А.Ю.Тропченко

Одобрено на заседании кафедры вычислительной техники 11 [A1] марта 1997 г., протокол № 2.

[A2] © Санкт-Петербургский государственный институт точной механики и оптики (ТУ), 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 1.2

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

В задачи управления множественным доступом (при аппаратурном ее решении - в задачи распределенного арбитра, см. рис. 1.2) входит:

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

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

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

Рис. 1.3

Методы управления множественным доступом, реализующие соответствующие ДО, различаются видом сигнала передачи прав на занятие ресурса - либо асинхронным (по выделенной линии арбитража - эстафетный,

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

Рис. 1.4

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

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

Дата добавления: 2013-12-13