известия ран. теория и системы управления, 2014, № 6, с. 94-104
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^ МЕТОДЫ
удк 65.012.122
НЕСТАЦИОНАРНЫЕ ДИНАМИЧЕСКИЕ МОДЕЛИ В ЗАДАЧАХ ДИАГНОСТИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ*
© 2014 г. А. М. Грузликов, Н. В. Колесов, Ю. М. Скородумов, М. В. Толмачева
Санкт-Петербург, ОАО "Концерн "ЦНИИ "Электроприбор" Поступила в редакцию 04.12.13 г., после доработки 24.06.14 г.
Рассматриваются вопросы тестового диагностирования вычислительных систем реального времени. Показывается возможность применения при построении теста нестационарных динамических моделей. Предлагается алгоритм синтеза моделей с учетом свойств наблюдаемости и управляемости. Диагностирование нацелено на обнаружение нарушений в информационных обменах между программными модулями системы. При этом анализируются случаи как синхронных, так и асинхронных параллельных вычислений.
БО1: 10.7868/80002338814060079
Введение. Качество диагностического обеспечения вычислительных систем (ВС) существенно влияет на эффективность их использования. В связи с этим проблема совершенствования средств диагностирования остается актуальной. Эта проблема многогранна [1—4]. Ее решение предполагает использование набора средств, организация которых обычно подчиняется иерархическому принципу. При этом средства диагностирования, применяемые на каждом уровне иерархии, нацелены на обнаружение отказов в информационных связях между объектами предыдущего уровня. В данном случае объектом диагностирования является распределенная ВС, входящая в состав некоторой информационно-управляющей системы реального времени. Программное обеспечение системы представляет собой композицию программных модулей (ПМ), размещенных по ее процессорам. Цель диагностирования — выявление нарушений в информационных обменах между ПМ. Класс нарушений далее будет ограничен всевозможными изменениями множеств ПМ, участвующих в конкретных обменах. В этот класс входят, в частности, пропадание и появление новых обменов, что может приводить и к перестановке ПМ в некотором вычислительном пути. Причинами аномальных событий могут быть не обязательно отказы аппаратуры, но и допущенные при проектировании ошибки в организации вычислений и разработанных программах.
Рассмотрим два варианта организации вычислений в системе — синхронный и асинхронный. В первом случае будем предполагать, что обмены реализуются посредством моноканала с централизованным управлением, во втором случае, что данные обрабатываются программными модулями системы не в соответствии с заранее определенным планом, а по их готовности, т.е. асинхронно [5]. Причем в случае, когда исполняющий процессор занят, данные помещаются в соответствующую ему очередь. Предлагаемые ниже для рассматриваемых случаев решения хотя и различаются в деталях, но объединены общим подходом, основанным на использовании периодически нестационарных динамических моделей.
Общепризнанной формализацией распределенных вычислений является сеть Петри [6], которая была в свое время предложена для описания асинхронного взаимодействия вычислительных модулей. При решении задачи диагностирования распределенных ВС, различным вариантам которого посвящено большое число работ, часто используется именно эта модель [7—13]. При этом объект диагностирования описывается как дискретная событийная система, когда функционирование системы представляется как последовательность происходящих в ней событий.
В нашем случае также используется модель дискретной событийной системы, а анализируемыми событиями являются "прием" или "выдача" информации из программных модулей систе-
* Работа выполнена при финансовой поддержке РФФИ (грант № 13-08-00211а).
Рис. 1. Информационный граф системы
мы. Особенность предлагаемого подхода — решение задачи мониторинга в рамках концепции тестового диагностирования. При этом в анализируемую систему вводится избыточность, которая по существу представляет собой событийную модель системы.
Авторы используют описываемый подход для систем реального времени, однако он может быть применен и за пределами этого класса систем.
Работа имеет следующую структуру. В первом разделе приводится постановка задачи, во втором — процедура синтеза событийной модели синхронной системы, в третьем — аналогичная процедура для асинхронной системы, в четвертом — необходимые результаты из теории диагностирования периодически нестационарных дискретных систем.
1. Постановка задачи. Для пояснения сути предлагаемого подхода рассмотрим информационный граф некоторой гипотетической системы Б (рис. 1). В системе реализуются три функционально связанных ПМ: /1, /2 и /3, которые могут быть размещены как на разных процессорах системы, так и на одном. Каждый из ПМ на основе входных данных (щ — для /1, и2 и у3 — для /2, у1 и у2 — для /3) формирует выходные (у:,у2и у3 соответственно). Система диагностирования (СД) формирует для системы Б тестовые данные, дополняя ими входные данные для и /2, и анализирует выходную реакцию ПМ /3. В каждом из ПМ /1, /2 и /3 реальные информационные слова обрабатываются штатными алгоритмами. Параллельно с этим тестовые информационные слова обрабатываются специальными алгоритмами /т1, /т2 и /т3, реагирующими на события приема/выдачи информации, а результаты их обработки выдаются в составе выходных данных. Механизм обмена для реальных и тестовых данных является общим, поэтому возникает возможность по наблюдаемым в процессе работы тестовым результатам делать вывод о наличии или отсутствии в обменах рассматриваемых нарушений — изменений множеств участвующих в конкретных обменах ПМ. Таким образом, задача состоит в соответствующем подборе тестовых данных и алгоритмов их обработки в ПМ.
В определенном смысле алгоритм обработки тестовых данных является событийной моделью алгоритма обработки реальных данных, а значит, и моделью системы. Конечно, наблюдаемым результатом обработки тестовых данных выступают не сами события, а выходная символьная последовательность, по содержанию которой может быть восстановлена последовательность анализируемых событий. С учетом сказанного задача синтеза алгоритма обработки тестовых данных может быть сформулирована как задача синтеза модели системы.
2. Синтез событийной модели синхронной системы. Итак, один из центральных моментов обсуждаемой задачи — вопрос о надлежащем выборе алгоритма обработки тестовой информации в каждом ПМ. Данный вопрос не является тривиальным. Прежде всего, заметим, что объединенный алгоритм / обработки тестовой информации в системе Б — композиция алгоритмов, размещенных в ПМ. Он реализуется, как и основной алгоритм обработки, в виде параллельного вычислительного процесса. С нашей точки зрения, эта модель должна удовлетворять трем условиям. Во-первых, она должна быть адекватной, чтобы построенный по ней тест обнаруживал рассматриваемые аномальные события. Во-вторых, она должна быть достаточно простой, чтобы не требовать для своей реализации значительных ресурсов, и допускать автоматический синтез для любого графа межмодульных информационных связей. Наконец, в-третьих, анализ ее результатов должен реализоваться в виде последовательного алгоритма или набора таких алгоритмов. По существу, выдвижение всех этих условий связано со стремлением, по возможности, упростить реализацию диагностирования.
>У3
Рис. 2. Модель системы
Укажем универсальный подход к автоматическому синтезу fъ, справедливый для любого графа межмодульных информационных связей. Сведем специальными приемами рассмотрение информационных графов произвольного вида к анализу некоторых стандартных (примитивных) графов, а именно цепей. Итак, при построении модели системы воспользуемся следующим алгоритмом. По информационному графу найдем множество вычислительных путей, составляющих покрытие его ребер. Под вычислительным путем в данном случае понимается последовательность ребер и вершин, соединяющая некоторый вход информационного графа с его выходом. Для рассматриваемого примера (рис. 1) покрытие обеспечивается двумя путями с ребрами и1>у1,Уз и п'2,у2,у3,у2, у3. Здесь штрихи используются для обозначения передаваемой в массивах тестовой информации. Второй путь содержит цикл для покрытия информационной обратной связи с выхода системы на вход ПМ2. Сопоставим в модели системы с каждым путем цепь из такого числа динамических звеньев М, через сколько ПМ проходит данный путь. При этом если в путь входит ПМ; и он является 1-м по порядку в этой цепи, то с ним сопоставляется звено Мп. После описанных построений модель системы представляется совокупностью независимых цепей. Можно сказать, что результат вычисления модели формируется как массив значений аргументов, подвергнувшихся независимой обработке.
На рис. 2 представлена модель системы из рассматриваемого примера, где модель ПМ1 содержит одно звено Мп, модель ПМ2 — два звена М21 и М22, а модель ПМ3 — три звена М31, М32 и М33. Отметим особенность структуры массива у3, выдаваемого из третьей системы. В ней можно выделить две части, одна из которых формируется в звеньях М31 и М33 и предназначена для системы мониторинга, другая формируется в М 32 и предназначена для ПМ2.
Попробуем уточнить модели звена, ПМ и системы. Из теории технического диагностирования известно [1—3], что наибольшей эффективности диагностирования при наименьших затратах можно достичь в случае, когда объект диагностирования — линейный. Кроме того, ясно, что поскольку речь идет об анализе последовательности событий (последовательности выполнения ПМ), то этот алгоритм должен быть динамическим. В результате получаем, что моделью звена должна быть линейная динамическая система:
Хц а +1) = /пХп (0 + g¡,u¡, (0, Уа (0 = крп (0, I = 1, т, I = 1, Ш1,
(2.1)
где , и¡1 и уц — векторы состояния, входа и выхода, , giJ и — матрицы динамики, входа и выхода 1-го звена в модели /-го ПМ, т — число ПМ, т^ — число звеньев в ПМ;.
Каждое звено модели ПМ обрабатывает информацию лишь от одного массива и по одному и тому же алгоритму. В отличие от звена ПМ в общем случае обрабатывает несколько массивов, а следовательно, его модель содержит параллельную композицию н
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.