Математические модели асинхронных процессов информационного обмена в распределенных АСУ МП

Размещено на http://www.allbest.ru/

Математические модели асинхронных процессов информационного обмена в распределенных АСУ МП

Савенков А.Н.

The streamed mathematical models of information exchange based on description of cooperating processes, differing themes are considered in article. They allow to describe an asynchronous exchange of messages and problems connected with it. информация асинхронный потоковый

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

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

Обогащение потоковых моделей такими свойствами, как недетерминизм и распределенность процессов, а также обмен разнородными сообщениями ставит ряд серьезных проблем, связанных с исследованием разрешимости, как самих моделей, так и задач их анализа [1,2].

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

Для обнаружения возможности блокировки необходимо учитывать детальную структуру данных, которыми обмениваются процессы. Это возможно при использовании различных графовых моделей [3]. Это может быть ориентированный граф, каждая вершина которого соответствует некоторому ресурсному семафору S[i], а дуга (S[i], S[j]) с меткой Pk - возможности последовательного выполнения P-операции процессом Pk над семафорами S[i] и S[j]. Наличие в таком графе контура свидетельствовало бы о ситуации столкновения процессов.

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

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

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

Рисунок 1 - Тупик в сети с коммутацией каналов

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

Рисунок 2 - Примеры SDF-графов

Во избежание тупиковых ситуаций целесообразно специальным образом структурировать буферный пул.

Случаи блокировки информационного обмена не исчерпываются лишь ситуациями «столкновения» и «голодания». Чтобы это проиллюстрировать, прибегнем к модели, на основе SDF-графов [5]. На рис. 2а приведены примеры SDF-графов, вершины которых обозначают акторы, а маркировка дуг -- число производимых и потребляемых ими токенов (элементарных сообщений). Случай, представленный на рис. 2а, соответствует последовательности гнезд циклов.

Для однократного срабатывания актора а3 необходимо соответственно 10 и 100 срабатываний акторов a2 и а1. Граф на рис. 2б иллюстрирует случай «столкновения»: акторы а4, а5 взаимно блокируют друг друга. Пример на рис. 2в представляет так называемый несогласованный SDF-граф: актор а6 при каждом срабатывании производит два токена, передаваемых по дуге (а6, a8), в то время как по дуге (a7, a8) передается один. Нетривиального решения уравнения баланса, дающего целое число срабатываний актора a8, не существует. Ситуацию с актором a8 можно, с одной стороны, интерпретировать как ситуацию «голодания» по входящей дуге (а7, a8). С другой стороны, имеет место «переизбыток» данных, передаваемых по входу (а6, a8).

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

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

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

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

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

Применение потоковых моделей процессов информационного обмена для описания асинхронного обмена сообщениями позволит выявить вероятные блокировки и еще на этапе проектирования АСУ предотвратить возможность их появления.

ЛИТЕРАТУРА

1. Топорков В.В. Реализуемость потоковых моделей распределенных программ // Программирование. -- 2001. -- № 5. -- С. 18-25.

2. Apt K.R,, Plotkin G.D. Countable nondeterminism and random assignment // Journal of the ACM. -- 1986. -- V. 33, JV» 4. -- P. 724-767.

3. Najjar W.A., Lee E.A., Gao G.R. Advances in the dataflow computational model // Parallel Computing. -- 1999. - V. 25. -- P. 1907-1929.

4. Корнеев В.В. Параллельные вычислительные системы. -- М.: Нолидж, 1999. - 320 с.

5. Lee E.A., Messerschmitt D.G. Synchronous data flow // Proc. of the IEEE. - 1987. -- V. 75. - P. 1235-1245.

6. Коваленко В., Коваленко Е., Корягин Д. и др. Управление заданиями в распределенной вычислительной среде // Открытые системы. -- 2001. -- №5-6.-- С. 22-28.

Размещено на Allbest.ru