автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Моделирование процессов управления распределенными вычислительными комплексами дискретных производственных систем (на примере ГАУ механообработки)

ШДИВД. НАУК РЕСПУБЛИКИ УЗБЕКИСТАН УЗБЕКСКОЕ НАУЧНО-ПРОИЗВОДСТВЕННОЕ ОБЪЕДИНЕНИЕ "КИБЕРНЕТИКА"

На правах рукописи

БАХРАМОВ Рахим Муртазаевич

МОДЕЛИРОВАНИЕ ПРОЦЕССОВ УПРАВЛЕНИЯ РАСПРЕДЕЛЕННЫМИ ВЫЧИСЛИТЕЛЬНЫМИ КОМИКСАМИ ДИСКРЕТНЫХ ПРОИЗВОДСТВЕННЫХ СИСТВ11 ■ ( На примере ГАУ механообработки)

Специальность: 05.13.06 - Автоматизированные

системы [управления

Автореферат

диссертации на соискание ученой степени ■ кандидата технических наук

Ташкент - 1991

Работа выполнена в Узбекском научно-производственном с данении "Кибернетика" АН Республики Узбекистан.

Научный руководитель

Официальные оппоненты

- доктор технических наук, профессор Н.А.МУМИНОВ

- доктор технических наук, профессор С.С.КАСШОВ

кандидат технических наук З.З.ШЖЖВ

Ведущие предприятие

- ВЦ АН СССР.

Защита состоится " 15 " янооря 1992. г. в -10"" часов на заседании Специализированного совета Д 0.15.12.01 Узбекском научно-производственном объединении "Кибернетика" Академии наук Республики Узбекистан по адресу: 700125, г.Та кент, ул.Ф.Ходааева, 34, УзНПО "Кибернетика" Республики Узбекистан.

С диссертацией молено ознакомиться в библиотеке НПО "Ки бернетика" Академии наук Республики Узбекистан.

Автореферат разослан •• Гъ

." ^ерабря 199 ^ г.

Ученый секретарь Специализированного совета, доктор технических наук, »

профессор д £=>

Э.М.Алиев

ОЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Магистральным направлением повышения эффективности производства является комплексная автоматизация. Применение гибкого автоматизированного производства становится насущной необходимостью передовой промышленной технологии маши-но и приборостроения. Главная отличительная черта этих систем состоит в распределении функций управления между несколькими ЭШ, что потенциально повышает надежность, производительность и гибкость системы. Техническими средствами, на основе которых строятся также системы управления, являются распределенные вычислительные комплексы (РВК).

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

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

Дель работы - разработка моделей функционирования математического обеспечения распределенных вычислительных комплексов для организационно-технологического управления ГПС.

В соответствии с поставленной целью репены следующие основные задачи:

- формализация описания математического обеспечения РВК;

- математические модели распределенной операционной системы;

- имитационная модель движения информационных потоков меаду узлами РВК;

- математические модели выбора ресурсов;

- модели диспетчирования специального математического обеспечения ЕВК.

Методы исследования. Б методологическую основу работы положены теории систем массового обслуживания, имитационного моделирования и сетей Петри.

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

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

Диссертационная работа выполнена в соответствии с общесогз-ной НТП 0.16.10 "Создать и освоить гибкие автоматизированные производства на основе передовых технологических процессов, гибких переналаживаемых комплексов, промышленных роботов и микропроцессорной техники" и Х/Д 1/88 "Разработка и внедрение специального' математического и црограммноЛ) обеспечения распределенной микропроцессорной системы организационно-технологического управления ГПС".

Реализация результатов. Основные результаты работы в виде комплекса алгоритмов и программ приняты к внедрению на ПО ЭВМ "Алгоритм".

Апробация результатов. Основные положения диссертационной работы докладывались Я обсуждались: на научно-технической конференции "Моделирование и управление в технических системах" (Таш-цент, 20-23 мая, 1991 г.); на Республиканской конференции "Современные проблемы алгоритмизации" (Ташкент, 2-4 сентября, 1991г.),

Публикации. Основные положения диссертационной работы отражены в двух печатных работах.

Объем и структура работы. Диссертация изложена на 1А5 страницах машинописного текста, состоит из введения, четырех глав, заключения, списка использованной литературы ( 55 наименования), включает И таблиц и 25 рисунков.

В выполнение насюящей работы непосредственную помощь, наряду с научным руководителем, оказывал доктор технических наук Б.Ы.Исмаилов, который является научным консультантом.

s

СОДЕРЖАНИЕ РАБОТЫ

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

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

- доступ к ресурсам (вычислительна машинам, программам,данным и т.д.) с терминалов п ^пользовательских программ;

- интерактивное общение пользователей с запуленными по их требованиям программами;

- выполнение заданиЛ з реяпме дистанционной пакетной обработки;

- сбор статистика о уушасгонированин системы;

- обеспечение :-:адзлс-:ости п .'зизучестп cacTsrtH в целом.

Установлено, что з простейшем случае ?2К состоит из одной

:з*струмон?алъно.:1 SE.I (перз^ерпйкоа устройство), к которой.подключено несколько терминальных ЗШ (рлс.1). ста структура комплекса язлчзтел эффективной, потому что отпадает необходимость в использовании пер^олэнга для загрузки программ в станет с ЧПУ, так как загрузка упразлязгцг: программ-в терминальные ЗЗМ возкоз-ка с устройств внешней памяти инструментальной г,!аш1шы. Замена одной программы на другую возможна в этом случае без участля оператора.

Однако математическое обеспечение дэгзения информационных потоков медду узлами P'jX, а такие вопросы выбора ресурсов РВК являются малоисследовашими.

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

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

Дано формализованное представление : структуре программного обеспечения автоматизированной систем! оперативно диспетчерского управления (АСОДУ) РВК ГПС.

Рассматривая эту систему icait сложную систему, мы выделили две прикладные и системные задачи математического обеспечения

Рис.1. Структурная схема РЖ.

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

Обозначим эти два множества задач:

, ¿ч.*.

$к Ц-1 , .

где Ш - количество системных задач;

П - количество прикладных задач.

Взаимодействие мезду задачами осуществляется через "порты", .т.е. каядая системная или прикладная задача имеют входной "порт" и выходной "порт". Формально это выразится следующим образом:

Необходимо отметить, что множества могут пересекаться:

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

О—

Рис. 2. Двудольный граф структуры математического страты АСОДУ.

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

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

Состояние системы изменяется процессами, когда они запрашивают, приобретают или освобождают ресурсы. Если процесс не блокирован в данном состоянии системы, он может изменять это состояние системы на новое. Формально состояние системы можно описать графом обобщенных ресурсов:

где

1. я Ц/О , _ есть непустое множество вершин - процессов {.Рг,рг, />л) я У ~ есть непустое множество вершин -портов - ресурсов.

2. уз , ^ - есть „ множество повторно- используемых ресурсов.

Определение: Повторно используемый ресурс ( ) есть конечное множество идентичных единиц со следующими свойствами:

а) число единиц ресурса постоянно;

б) каддая единица ресурса или доступна или распределена одному и только одному процессу (разделение отсутствует);

в) процесс монет освободить единицу ресурса (сделать ее доступной) , только если он ^ ранее подучил эту единицу.

Определение: Потребляемый ресурс ( Сл ) есть конечное множество идентичных единиц, обладающий свойствами: \

а) число доступных единиц ресурса типа "изменяется-по ■ ■ мере того, как приобретаются (расходуются) и освобождаются (производятся) отдельные элементы процесса™, -и такое "число' -единиц ресурса является потенциально неограниченным;

б) процесс (производитель) увеличивает число, единиц ресурса, освобождая одну или более ед:шиц, которые он "создал";

в) процесс (потребитель) уменьшает число единиц ресурса, сначала запрашивая и затем приобретая одну или более единиц. Единицы ресурса, которые приобретены, в общем случае не возвращаются .ресурсу, а потребляются приобретающим процессом.

3. Каждое ребро направлено меаду вершиной -?1 и вершиной уэ . Если £ = , ); , то есть ребро запроса и'интегрируется как запрос процесса на единицу ресурса

Если , то: а) если ■ «Р,- , то / есть реб-

ро назначения и показываем распределение единицы ресурса ^ процессу или б) если ^ , то £ есть ребро про-

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

4. Для каждого существует связанное с ним поло-

где ] ( Д-, Р^ )| - количество единиц ресурса Ц- распре да-ленное процессу -Н' *

5. Для всех £ и процессов ^ должны выдерживать-

ся. следующие соотношения:

6» Ддя каждого Q €,/><. существует неотрицательное

целое , указывающее количество доступных единиц ресурса

. Это введенное определение характеризует ранг М2 ( I ) (топологию) модели функционирования математического обеспечения АССД7. Ранг Мг ( 2 ) определяется заданием логики работы процесса с ресурсом Q , а также синхронизацией этих процессов ( AI и А2 рис.3). Логику работы процесса с ресурсом Rj можно представить как взаимодействие автоматов, моделирующих соответственно и .

Ресурс моделируется!, работой автомата

4 - (s, к, т, а, п

где $ - состояние семафора ресурса, принимает значение I, если ресурс "занят" ("захвачен" процессом) и 0 в противном случае; X - количество единиц ресурса;

- матрица перехода; ¿1 - начальное состояние; Т - тип ресурса; принимает значение; 4 - ТИП IX///¿Г ; 4 - тип 7MIIF0 ■> <J = OUT .

Работа процесса J® моделиpjj&wя автоматом:

где i = [ ^ j - конечное множество состояний процесса <Р ;

- начальное состояниз процесса Р , причем yeS ; 'M~{ms\ - множество сообщений, которые могут быть приняты или досланы процессом J3 ; I - конечное множество событий на М , причем событие в / определяет либо посылку ( -п^. ), либо прием ( + rrif. ) сообщения /п^ ; Д - внутрешее собьйие, заключающее в отсутствие как

посылок, так и приема сообщений; F - функция переходов процесса fi / -$xF —S .

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

Рис. 3. Схема взаимодействия фунциональных модулей ПО.

щихся сообщениями через коммуникационные каналы (ресурс типа 4) (рис. 4). Предлагаемая модель базируется на протокол А .который определяется как

¿де 5 = [ - представляет два конечных множества 9е-

и

Я

соот-

ветственно

начальное состояние процессов £>■ и

_____________________________________„ » V /

\ ^ два конечных множества: сообщений,

Жу - множество сообщений, которые могут быть посланы процессом -Уу процессу ^ ; £ - {£/} ~ два конечных множества событий на М , причем событие £ € £{ определяет либо посыжу сообщения я? ¿Му процессов Р/ , либо прием сообщения ю е Ж,г- и обозначается соответственно -т и . Аналогично для

процесса ^ > € определяет посылку сообщения (обозначается -лг ) или прием сообщения т € Ж,-^ (обозначается + т. ). Событие, определяющее отсутствие как посылки,, так и приема сообщения, будет называться внутренним сообщением и обозначится Л . / = | /. /. } - две функции пе-^ и ^

реходоз процессов

соответственно:

л

А /

■ Рис. 4, Схема взаимодействия "г и .

4 . *■-'•/ •

/к ( $, £ ) определяет, в какое состояние перейдет процесс А* из состояния S е Sv в случае наступления события ^ е ^

Каналы ¿'¡у и » обеспечивающие обмен сообщениями

между процессами ^ и ^ , рассматриваются как очереди с дисциплиной обслуживания . Соответствующие очереди и

<у/ обозначаются последовательностями сообщений т в М Считается, что | С^ | =£ \^.\тах где 1 | и

I С/ I тлях соответственно длина очереди и максимально возможная длина очереди сообщений для канала ¿'¡у . Величина- \0(у\тах ограничивается пропускной способностью канала £гу . Однако, на практике для любой пропускной способности всегда можно рассчитать необходимый объем памяти, чтобы считать канал способным обслужить очереди любой длины. Кроме того, предпологаем, что канал в некотором смысле "идеальный", т.е. такие события, как потери, искане-ния и повторы сообщений, в нем невозможны.

Рассматривая всю систему "процесс - канал - процесс", определяем "обобщенные состояния" как ^ ^ ) г (С£ . 1 ) > где 6 , б 5,- - текущие состояния процессов % и

•Ру соответственно и ¿]у , - текущие состояния очередей соответственно в каналах А- и .

При этом обобщенная функция переходов

определяет переход из обобщенного соотояния < ( , )» ( , С/1 ) "> в новое обобщенное состояние < ( , ), С С А , ¿у/ )>в случае наступления события £

Изменение состояний процессов и каналов определяем, исходя из следующих правил. Правило I:

з;-/.-а,,-"). -

определяет посылку сообщения л? процессов ( ), на-

ходящихся в состоянии ( £ ), процессу ^ С ^ ), в результате чего процесс ( ) переходит из состояния . Я; (в/) в состояние ' с5*,' ( ф ) и сообщение л? ставится в конец очереди Сгу ( Су{- ).

Правило 2:

определяет получение сообщения п • процессов ^ ( ^ ), находящимся в состоянии ¿V ( «£• ) от процесса ^ ( ^ ) 1 в результате чего процесс ( ^ ) переходит из состояния Щ) в состояние SJ ) ъ сообщение т удаляется из на-

чала очереди С-- ( £. ).

Правило 3:

определяет выполнение процессом С ^ ), находящимся в состоянии ( в,- ) внутренних действий, в результате чего про-

1.3

цесс Ц ( ) переходит из состояния % ( ) в сос-

тояние ( ), а состояние очереди ( ) остается

без изменения.

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

Ч- = < 4 ■ й-. 4', >

где о£- и о,- - множества состояний;

и - начальные состояния;

К' _ входные алфавиты.

' /

Е*=\+т,, .... *тй/\ , меМуОЛС,*

Еу и /г- - выходные алфавиты.

...,-тТ1.) , те М;. и Мгк , {-щ, -Яг; } , дае М.. и М^ .

/. и - пункции переходов соответственно автоматов " '' РАг. и Ц- .

Здесь, исходя из описания протокольного уровня, предполагаем, что протокольные автоматы $>Аг- и РА^- не только взаимодействуют меаду собой через услуги нижнего уровня путем отмен протокольными элементагли и М^ , но и с другими процессами через сервисные элементы и ( и М^- ).

Иными словами, для каздого события посылки сообщения процессом ^ находящимся в состоянии 8К , существует событие прием этого же сообщения процессом , находящимся также в

состоянии Зх .

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

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

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

Путь QJ - матрица интенсивностей потока пакетов между узлами сети, где Qpm - интенсивность потока пакетов, возникающих в узле fl и адресованных в узелй'Сграфик р-лг ).

Интенсивность потока пакетов Аг- (пакетов (с), входящих в ¿■и канал связи, равна:

А.- " 2 Г tfpn , (fl,m) ; с'еЯрт , (I)

Р т .

г = /, т

где lefipm - обозначает, что сообщение, идущее по пути (А'®).-проходит через г'-й канал; М - число каналов в сети.

Среднее время задержки пакетов (с) в пути ) ив це-

лом по сети имеют, соответственно, вид:

tpm ~ 2 ¿с- ') (2)

Vt'eJpm

где / - интенсивность общего потока пакетов, пакетов/с,

поступающих в сеть:

Г - 2 2 (Црш ; (4)

" rrnl

¿1 - среднее время пребывания пакетов в ¿-м канале,с; I - число узлов в сети.

Среднее время задержки (с) в предположении о пуассоновском потоке поступления пакетов в каздый канал и экспоненциальном распределении длины сообщений со средним значением V ~Jk определяется по формуле:

м 3 ■ J # А • ' у _ i ? _(5)

где пропускная способность г-го канала, ¿=/,М : £ = _ (6)

•В формуле (5) предполагается, что среднее время обработки в узле Т = 0, т.к. этим временем обычно можно пренебречь. В общем случае, если учитывать г^емя обработки в узле Т , среднее время задержки определяется по Формуле:

В формуле (7) дополнительное слагаемое Т возникло'из-за того, что сообщения при их движении по сети проходят число узлов на один больше, чем число каналов.

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

Под стоимостью сети понимается стоимость каналов связи, а также средств передачи данных (мультиплексоров, адаптеров, модемов )•

Зависимость стоимости сети от пропускных способностей тана-лов выглядит следующим образом:

.(8)

г'ч

где - стоимостной коэффициент в г' -м канале;

<3{- - коэффициент нелинейности, имеющий значение в пределах а ¿<2; г'-- м.

Величины Ду и ¿7/ определяются путем регрессиотюго анализа зависимостей пропускных способностей канала от его стоимости.

Постановка задачи минимизации среднего времени задеркки пакетов при ограничении на стоимость сети- формулируется следующим образом:

м А • * /

при ограничениях:

(10)

Оптимальное решение, найденное методом неопределенных множителей Лаграпжа, находится из системы нелинейных уравнений с 1.1 + I неизвестным , . н , ¿3 :

ъ-хГ^ь/а*,^*, ■ Ш)

"ЧкХ/'в , (12)

г-г

где уЗ - вспомогательное неизвестное (неопределенны!! мно-лситель Лагранна).

Для частного случая Ог- =/ ( г'- /, М ), т.е. при линейной функции стоимости, точное решение имеет вид:

где „ д

■ $ ш)

Постановка задачи минимизации стоимости' сети при среднем времени задеряски пакетов, не превосходящем заданного, формируется следующим образом:

■ в/

г-/

при ограничениях:

м А ■ /

Оптимальное решение находится по формуле:

где"

х - f Л; <IS)

г-t

В четвертой главе рассмотрены'решения задач диспетчирова-ния распределенных.многопроцессорных систем.

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

• ' ' Г-(XJ)

№множество процессов и ресурсов Составляющими подмножества процессов являются (функции, приема информации).

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

Р3 - модуль,/в функции . которого входит выбор элемента из пула 5-3 словных буферов.и его заполнение, а также постановка этого элемента вместе.с 138 байтным;буфером в очередь к подуровни LLC канального уровня сетевого обеспечения РЗК.

^ - модуль приема кадров, обработки и их постановки с соответствующим заполнением элемента очереди в очередь на обработку сетевым уровнем сетевого.программного обеспечения РВК.

Ps - модуль, открытия (закрытия) логического канала сетевого уровня.. Использует ресурсы: пулы 5-словных и 8-словных, а также 512-байтных буферов. Взаимодействует с очередью интерфейса с канальным уровнем и очередью интерфейса с сетевым уровнем.

^ - модуль приема, (передачи) пакетов сетевым уровнем. Йсполь-зует, ресурсы: буфер из пула 512 байтных буферов, буфер из пула б словных буферов. Взаимодействует с ресурсами: очередью интерфейса с канальным уровнем и-списком каналов сетевого уровня.

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

регистр чода

список каначг лоп(пропеесой) и интерфеш.с

массив пользова тельских данних

пул сетеш.пс 13В-баПтиых буфероп

Рис. 5. Граф ресурсов РВК.

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

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

При этом решены следующие задачи:

1. Формализовано описание математического обеспечения РВК.

2. Разработаны математические модели распределенной операционной системы.

9. Разработаны разные структурные организации. передачи денных в узлах РВК.

4. Разработана имитационная модель движения информационных потоков между узлами РВК.

5. Разработаны математические модели выбора ресурсов.

6. Разработаны модели диспетчирования специального математического обеспечения РВК.

Основные результаты диссертационной работы опубликованы в следующих работах:

1. Моделирование программного обеспечения автоматизированных систем оперативно-диспетчерского управления. Республиканская научно-техническая конференция "Моделирование и управление в технических системах" (Ташкент, 20-23 мая 1991 г.)

2. Модели взаимодействия процессов и ресурсов взаимодействие открытых систем. Республиканская конференция "СсЕгв-'лниые проблемы алгоритмизации" (Ташкент, 2-4 сентября, 1991 г.).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

Подписано в печать 5.12.91 г. Заказ № 94, Тираж ГОР экз.

Отпечатано на ротапринте СПКБ АиВТ 700170, г.Ташкент, Володарского,26