В сетях Керка описание прикладных функций, составляющих программную нагрузку СРВ, осуществляется в виде множества взаимосвязанных параллельно выполняемых процессов [14-17].
Программная система СРВ рассматривается как состоящая из взаимосвязанных подсистем. Каждая подсистема рассматривается в свою очередь как система. Процесс разбиения на подсистемы, подподсистемы и т.д. продолжается, пока не будет достигнута приемлемая детальность описания. Система на нижнем уровне описания называется процессом. Обычно процесс выполняет элементарную функционально законченную задачу и вычисляет значения переменных, которые характеризуют решение этой задачи. Значения переменных образуют состояние процесса.
Состояние системы в каждый момент определяется совокупностью состояний всех процессов. Заметим также, что в общем случае этап декомпозиции программной системы на процессы формализовать не удается.
Модель должна фиксировать взаимодействие процессов и тем самым вводить на множестве процессов частичную упорядоченность, определяющую последовательность выполнения процессов. Это означает, что отдельные процессы связываются с определенными ситуациями в окружающей системе или с определенными моментами времени. Моменты времени могут быть как относительными (по отношению к событию), так и абсолютными, фиксируемыми в астрономическом времени. Активизация части процессов может зависеть от результата работы программной системы.
Кроме фиксации последовательности выполнения процессов необходимо определять объем информации и моменты ее передачи между процессами. Модель ориентирована на метод обмена сообщениями, который имеет ряд преимуществ по сравнению с методом разделяемых переменных, например, методом семафоров.
Пусть 
– множество процессов программной нагрузки. Обозначим через 
состояние процесса 
в момент времени 
. Тогда состояние системы в момент времени 
определяется совокупностью 
. Здесь 
принимает только дискретные значения.
В СРВ процессы нередко имеют так называемую внутреннюю память. Например, состояние процесса 
в момент 
зависит от состояния процесса 
в моменты времени 
, 
. Поэтому состояние системы 
может включать состояния некоторого процесса, вычисленные в разные моменты времени.
В моделях Керка запуски процесса производятся в определенные моменты времени. С каждым процессом 
связывается множество пусковых моментов 
этого процесса. 
строго упорядоченное, для любого 
, то есть у всех процессов существует общий начальный пусковой момент. Мощность множества 
конечна, то есть в любом конечном промежутке времени процесс 
может быть активизирован конечное число раз.
Для любых 
и последовательных элементов 
, 
, где 
и 
– заданные из практических соображений функции, причем 
.
Чтобы гарантировать циклическое выполнение любого процесса 
, активизированного в момент 
нужно, чтобы время выполнения процесса 
было строго ограничено сверху, либо выполнялось условие
.
Процесс может принимать данные не только в начале выполнения, а в любой момент. Поэтому необходимо оценить задержку между запуском процесса потребителя и моментом требования входных данных. Эту задержку обозначим 
, где 
– средство, обеспечивающее связь между процессами 
(производители) и 
(потребители).
Величина 
в общем случае является случайной величиной на интервале 
, где 
– функции, заданные из практических соображений, при этом 
.
Предполагается также, что каждый процесс выполняется на собственном процессоре. При этом процесс не имеет информации о потребителях результатов своей работы, он знает только необходимые входные данные.
Каналы взаимодействия процессов
Данными в моделях Керка могут быть только состояния процессов. Поэтому необходимо иметь логические устройства ввода, которые снабжают процессы правильными данными в нужный момент времени. Логическое устройство ввода будем называть каналом.
Канал между процессом производителем 
и процессом потребителем 
обозначим 
, где 
упорядоченная пара, а 
– множество каналов, необходимых для осуществления взаимодействий в системе.
Для разных типов взаимодействий требуются разные типы каналов.
Нулевой канал 
не передает информацию, но гарантирует работу процессов 
и 
на одном множестве пусковых моментов, то есть 
.
Синхронный канал 
передает заранее определенное число последовательных во времени состояний процесса производителя и в то же время гарантирует работу процессов 
и 
на одном и том же множестве пусковых моментов.
Полусинхронный канал, или канал Петри 
передает информацию как и синхронный канал. Связываемые процессы выполняются с одинаковой частотой, то есть процесс-потребитель запускается после завершения работы процесса производителя. Тем самым процесс производитель генерирует множество пусковых моментов процесса потребителя.
Асинхронный канал 
передает информацию как и синхронный канал, но связывает процессы, выполняющиеся на разных множествах пусковых моментов.
В общем случае допускается ввод других типов каналов, поэтому для перечисленной совокупности типов каналов должно выполняться условие 
.
Канал 
, связывающий процессы 
и 
, можно определить как отображение
,
где 
– (value) область изменения значений состояний процесса 
;
– (domain) область определения входных данных процесса 
.
Это отображение создает постоянную связь между процессами, то есть состояния процесса 
, определенные в моменты времени 
, доступны процессу 
в моменты 
при условии, что 
.
Функция канала
Для обеспечения избирательности взаимодействия процессов во времени введена функция канала 
. Функция канала определяет подмножество множества 
, 
, 
, 
. Функция 
указывает на совокупность состояний производителя 
, полученных от запусков в моменты времени 
, 
, и доступных потребителю 
.
В ряде случаев для синхронного канала и канала Петри функцию канала можно задавать на строго упорядоченном множестве 
в виде интервала 
, то есть 
. Интервал пусковых моментов задается по отношению к текущему моменту. Принимается также, что 
соответствует текущему выполнению процесса 
, а 
соответствует непосредственно предыдущему выполнению и т.д. Величина 
обозначает число состояний производителя одновременно доступных потребителю. Например, функция 
определяет, что через этот канал потребителю одновременно доступны два состояния производителя, непосредственно предшествующие текущему выполнению.
Отметим также, что буфер для сбора состояний организован в канале, то есть процесс производитель не должен заботиться о буферизации своих состояний.
Для асинхронных каналов функция 
также может быть определена в виде интервала 
. Однако, поскольку взаимосвязанные процессы работают на разных множествах пусковых моментов, необходимо определить момент времени, начиная с которого состояния процесса производителя 
в принципе доступны потребителю. Все состояния производителя 
, вычисление которых началось до момента 
включительно, где 
удовлетворяет условию
доступны процессу потребителю 
в момент времени 
. Из доступных состояний производителя потребитель выбирает нужные ему состояния при помощи функции канала.
Пример анализа взаимодействия процессов на моделях Керка
Рассмотрим пример использования модели Керка для анализа работы программной нагрузки регулятора непосредственного цифрового управления [17] на разных конфигурациях вычислительной системы. Регулятор получает данные от системы управления, в составе которой он работает. На основе этих данных регулятор вычисляет управляющие воздействия по заданному алгоритму. На этапе анализа точный алгоритм не задается. Указываются лишь временные характеристики. Если окажется, что временные характеристики удовлетворяют заданным требованиям, то в регулятор можно встроить пропорционально-интегральный (ПИ), пропорционально-интегрально-дифференциальный (ПИД) или любой из алгоритмов многомерного регулирования.
Вычисленные значения управляющего воздействия регулятор выводит на исполнительное устройство. Для повышения надежности работы системы введена обратная связь от исполнительного устройства. В зависимости от условий применения нужно принять решение относительно конфигурации вычислительной системы, реализующей регулятор на вычислительной сети, на мультипроцессорной ЭВМ или же на одном процессоре.
Модель регулятора представлена на рис. 2.3 в виде графа, в котором узлами являются процессы, а дугами каналы.
Рис. 2.3. Граф модели регулятора в виде сети Керка
Программная нагрузка регулятора включает следующие процессы: АЛГ – алгоритмы управления; БУФ – имитирование буфера или линии передачи данных; ОУТ – подготовка сигналов для исполнительного устройства; ИСП – имитирование исполнительного устройства; СИН – синхронизация исполнительной части регулятора.
Напомним, что в модели Керка процессы выполняют элементарные функциональные задачи, а каналы обеспечивают взаимодействия процессов.
Анализ графа модели Керка
После фиксации совокупности и каналов у проектировщика имеется несколько возможностей для реализации проекта.
Рассмотрим влияние изменения типа и функции каналов на поведение проектируемой системы. На рис. 2.4 изображено поведение регулятора с тремя разными множествами каналов:
- множество каналов А; здесь К1, К2, К3, К4 – каналы Петри с функциями [0, 0], К5 – нулевой канал, К6 – асинхронный канал, К7 – синхронный канал с функцией [1, 1];
- множество каналов В; здесь К1, К2, К3, К4, К6, К7 – синхронные каналы с функцией [1, 1], К5 – нулевой канал;
- множество каналов С; здесь К1, К2, К3, К4, К6 – синхронные каналы с функцией [0, 0], К5 – нулевой канал, К7 – синхронный канал с функцией [1, 1].
Рис.2. 4. Варианты временных диаграмм работы регулятора:
а – для множества каналов А; в – для множества каналов В;
с – для множества каналов С
Соответствующие временные диаграммы представлены на рис. 2.4 а, 2.4 б, 2.4 в. При этом времена выполнения процессов приняты одинаковыми.
Из сравнения диаграмм очевидны следующие выводы.
Модель Керка с каналами Петри хорошо имитирует поведение сетевых моделей, в которых запуск процесса осуществляется при наличии данных. Соответствующий проект может быть реализован на любой ВС, так как нет особых требований к точности синхронизации. Процесс СИН здесь явно работает как сторожевой таймер.
Модель с множеством каналов В подходит для реализации на мультипроцессорной ВС. Вычислительная система на однопроцессорной ЭВМ будет работать неэффективно, а на сети сложно обеспечить точную синхронизацию отдельных ветвей. Заметим также, что системы с синхронным запуском процессов обеспечивают высокую точность во времени.
Модель с множеством каналов С описывает мультипрограммную работу однопроцессорной ЭВМ, так как процессы в такой схеме взаимодействия могут продвигаться только последовательно.
Анализ временных характеристик работы СРВ на моделях Керка
В качестве объекта исследований берется СРВ, в которой выявлены параллельные взаимодействия отдельных процессов. Все процессы данной СРВ распределены по процессорам. В общем случае число процессоров может быть меньше числа процессов. С каждым процессом связывается множество пусковых моментов и время его выполнения. Алгоритм анализа включает следующие операции.
- Формируется матрица пусковых моментов
, массив времен выполнения процессов, совокупность каналов взаимосвязи процессов и ряд других сведений.
- Выполняется расчет канальных пусковых моментов. В случае, если канал окажется каналом Петри или синхронным, то это будут моменты времени, когда данные процесса производителя могут быть использованы процессом потребителем. Если канал окажется асинхронным, то это значение укажет в какой момент времени данные процесса производителя в принципе доступны процессу потребителю.
- Значения канальных пусковых моментов процесса определяются путем прибавления к соответствующим элементам матрицы
времени выполнения процесса. Полученные значения оформляются в виде матрицы 
. Если при анализе учитывается время задержки данных в канале, то матрица 
формируется с учетом этих задержек. Заметим также, что такие задержки имеют место при передаче данных в каналах, связывающих процессы, выполняемые на разных процессорах.
- Построение и вывод временной диаграммы выполнения процессов. На горизонтальных линиях диаграммы наносятся времена выполнения соответствующих процессов. Для этого используются данные матриц начала и окончания выполнения процессов, матриц
и 
. Время работы процесса на диаграмме помечается жирными линиями. При несоответствии пусковых моментов и времени работы процессов конфликтующие участки помечаются жирными линиями удвоенной толщины. Затем, используя сведения о совокупности каналов, на диаграмме наносятся взаимосвязи процессов в виде стрелок, имеющих на конце указание номера процесса производителя.
- Анализ состава каналов для заданных пусковых моментов. Анализ выполняется на основе матриц
и 
. Результаты анализа формируются в матрицу состава каналов 
. Элементы матрицы могут принимать следующие значения:
1 – канал Петри;
2 – тупиковая ситуация 1-го типа, которая соответствует нереальному пусковому моменту. В этой ситуации два взаимосвязанных процесса выполняются на одном процессоре и, следовательно, предполагается строгая последовательность выполнения процессов. Тупик возникает в случае, когда процесс-потребитель запросил данные раньше, чем процесс производитель их выработал. В канале образуется нетранспортная задержка.
3 – асинхронный канал;
4 – тупиковая ситуация 2-го типа, когда несколько процессов одновременно обращаются к одному процессу;
5 – синхронный канал.
- Расчет нетранспортной задержки данных, то есть расчет времени, которое простаивает процесс потребитель в ожидании данных.
- Расчет пропускной способности каналов и формирование матрицы
. Пропускная способность канала 
рассчитывается по усредненным данным от 
пусковых моментов. Вначале определяется среднее время, которое канал может быть загружен передачей данных процесса производителя,
.
При этом суммируются положительные слагаемые, то есть
.
Далее определяется величина 
среднего времени, которое «отводит» процесс-потребитель каналу для получения данных,
.
Если 
, то элемент 
. Для такого канала указывается число обработанных состояний, равное 
и число состояний, стоящих в очереди, равное 
. Если 
, то элемент 
принимается равным 1, а для канала указывается резервное время (недогруженность) канала, равное разности 
.
Пример анализа временных характеристик
В качестве примера взят граф модели Керка, представленный на рис. 2.5.
Рис. 2.5. Граф модели Керка
Анализ выполняется с помощью программного средства «Сети Керка», разработанного на кафедре Информатики и проектирования систем ТПУ. Матрица пусковых моментов и времена выполнения процессов представлены на рис. 2.6.
Рис. 2.6. Окно с матрицей пусковых моментов
Результаты анализа по третьему пусковому моменту представлены на рис. 2.7.
Рис. 2.7. Окно с результатами анализа по 3-му пусковому моменту
Окно формируется для каждого пускового момента. Приводятся типы каналов, каналы, образующие тупик, и каналы, имеющие нереальный пусковой момент. В данном окне также можно посмотреть матрицу пропускных способностей (рис. 2.8) и характеристики каналов (рис. 2.9).
Рис. 2.8. Матрица пропускных способностей
Рис. 2.9. Характеристики каналов
Временная диаграмма выполнения процессов представлена на рис. 2.10.
Рис. 2.10. Временная диаграмма выполнения процессов
