Программные продукты и системы, 2010, № 2

Программные продукты и системы
№ 2, 2010 г.

3

УДК 004.416.2

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ 

КОНТРОЛИРУЕМОГО ВЫПОЛНЕНИЯ

Н.В. Шмырев, к.ф.-м.н. (Научно-исследовательский институт системных исследований РАН

(НИИСИ РАН), г. Москва, shmyrev@niisi.msk.ru)

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

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

Ключевые слова: контролируемое выполнение, распределенные системы, системы реального времени.

Для описания сложной системы вычислений с 

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

статическую и динамическую верификацию 

корректности;

оптимизацию и проверку результатов оп
тимизации;

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

и с различной степенью детализации;

возможность описания ресурсов.

Предложенная автором модель построена на 

основе формального описания устойчивой системы реального времени, включающего восстановление системы после сбоев, временные свойства и 
планируемость [1]. В качестве модели приложения 
используется система переходов [2], в качестве 
общей спецификации – логика действий со временем (TLA – Temporal Logic of Actions) [3].

Сбои моделируются с помощью множества 

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

Программы и спецификации описываются в 

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

Приведем несколько определений.
Определение 1. Состояние – это отображение 

набора переменных Var на набор значений Val:

s : Var 
Val.

Определение 2. Действие – это некоторый

предикат над переменными, их значениями, а 
также их измененными значениями, которые обозначаются штрихом: x'+1≤y.

В качестве бесконечных последовательностей

действий 
=
1, 
2,… можно рассматривать вре
менные формулы, которые составлены из булевых 
операторов и операторов линейной временной логики.

Например: [
]( ) – предикат 
выполняется 

для любого суффикса , [
]( ) – предикат 
вы
полняется хотя бы однажды.

Определение 3. Программа – это набор, со
стоящий из следующих компонент:

конечное непустое множество
v
состоя
ний;

подмножество внутренних состояний
x

множества v ;

предикат первоначального состояния 
, 

включающий в себя только переменные из v ;

конечный набор A действий над перемен
ными из v .

Определение 
4. 
Вычисление 
программы 

P=( v , x , 
, A) – это последовательность состоя
ний , такая, что выполняются два условия:

1)
0 удовлетворяет ;

2)
i+1=
i или найдется такое 
A, что 
i+1, 
i

удовлетворяет .

Определение 5. Для программы P=( v , x , 
, 

A) рассмотрим NP=

A
V
.

Тогда точная спецификация определяется как 

(P)=
[NP] v и описывает набор всех разре
шенных состояний программы.

Определение 6. Внешняя спецификация про
граммы задается как
(P)= x
(P) и описывает 

все возможные последовательности внешних состояний системы.

И наконец, введем определение уточнения 

программ, позволяющее ввести понятие верификации. 

Определение 7. Отношение уточнения Pl Ph

означает, что программа Pl корректно реализует 
Ph, то есть отношение 
(Pl)
(Ph) выполнено 

для внешних спецификаций.

В работах [1] и [4] описываются дальнейшие 

расширения предложенных определений и воз

Программные продукты и системы
№ 2, 2010 г.

4

можности вывода теорем. Например, для описания
сбоев вводятся множество действий F и понятия
внешних и внутренних спецификаций, сбойного 

вычисления F(P,F)=( v , x ,
, A F), устойчивого 

к сбоям уточнения, и т.д. 

Рассмотрим варианты расширения описания 

для учета необходимых свойств.

Моделирование 

разных аспектов вычисления

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

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

Определим операцию комбинации программ.
Определение 8. Введем внутреннюю и внеш
нюю спецификации набора программ Pi:

(P1, …, Pn)=(
i) (
[NPi] v ),

(P1, …, Pn)= x
(P1, …, Pn).

Определение 9. Будем говорить, что про
грамма P является уточнением набора P1, …, Pn, 
если
(P)
(P1,…,Pn).

Таким образом, можно определить отношение 

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

Можно определить и другие операции над мо
делями программ.

Определение 10. Композиция программ P1 и 

P2 определяется набором состояний
1
v
2
v , на
чальным состоянием 
1
2 и набором действий 

A1 A2.

Другой операцией, позволяющей абстрагиро
ваться от внешней переменной, является операция 
сокрытия переменной.

Определение 11. Для программы P и пере
менной Var
x определим программу Hidex(P) с 

помощью набора состояний v и набора внутрен
них состояний x = x
Var.

Моделирование ресурсов

Потребляемые ресурсы, как и время, важны 

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

Например, время моделируется с помощью 

временных меток действий. Каждое действие 
связывается с нижней временной границей L( ) и 
верхней U( ). Чтобы считаться успешным, действие должно выполняться по крайней мере L( )
временных интервалов. Действие не должно выполняться реже, чем U( ). Модель может включать в себя более сложные механизмы планирования, например, планирование с временным освобождением ресурсов.

Определив набор ресурсов zi Z, для каждого 

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

now=0
,
(1)

[now' (now, ))]now,
(2)

t R+, (now>t).
(3)

Для механизма простейшего выделения памя
ти 
формулируются 
более 
простые 
условия:

mem( )>0, mem'>mem-Um( ), mem'<mem-Lm( ), 

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

При работе с ресурсом необходимо расширить 

определение внутренней и внешней спецификаций
соответственно:

RP=

A
V Ri( ), (P)=
[NP] v
[RP] v , 

где Ri – ограничения, накладываемые на использование ресурса.

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

Оптимизация

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

Программные продукты и системы
№ 2, 2010 г.

5

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

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

i и действия –C( ,
,
'). Соответственно изме
няется внутренняя спецификация:

CP=

A,
v, ' v
V
C( ,
,
'),

(P)=
[NP] v
[RP] v
[CP] v .

Полная модель приложения

Расширяя описание приложения, получим 

следующую формальную модель.

Определение. Программа описывается таки
ми сущностями:

программа без времени P( v , x , , A);
набор сбоев F и соответствующая програм
ма со сбоями с условием F(P,F) P;

счетчик часов now со свойствами време
ни (1);

внутренние состояния, описывающие нали
чие ресурсов, таких как доступная память;

функции расхода ресурсов Li( ) и Ui( ), за
дающие границы потребления ресурсов для каждого действия из P;

ценовые функции C( , , '), используемые 

для оптимизации;

внутренние и внешние спецификации 
(P)

и (P).

Для подобного описания можно сформулиро
вать свойства в терминах временных выражений 

и доказать их:
(P)
, в том числе и для набо
ра спецификаций P1, …, Pn, оценить корректность 
оптимизации с помощью эталонной модели Pe и 
вычислить результат оптимизации с помощью ценовой функции.

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

Литература

1. Liu Z., Joseph M. Real-Time and Fault-Tolerant Systems. 

Specification, verification, refinement and scheduling, UUNU/IIST, 
2005.

2. Pnueli A. The temporal logic of programs // 18th Annual 

Symposium on Foundations of Computer Science, 1977.

3. Lamport L. The temporal logic of actions // ACM 

Transactions on Programming Languages and Systems, 1994. Vol. 
16 (3).

4. Manna Z., Pnueli A. The Temporal Logic of Reactive and 

Concurrent Systems: Specification, Springer-Verlag, 1991.

5. Организация отладочного комплекса для целевых сис
тем со сложной архитектурой / Н.И. Вьюкова [и др.] // Информационная безопасность. Микропроцессоры. Отладка сложных 
систем; под ред. В.Б. Бетелина. М.: НИИСИ РАН, 2004.

УДК 004.416.2

ПРОГРАММИРОВАНИЕ, ОРИЕНТИРОВАННОЕ НА МОНИТОРИНГ, 

В КОНТЕКСТЕ КОНТРОЛИРУЕМОГО ВЫПОЛНЕНИЯ

В.А. Галатенко, д.ф.-м.н.; К.А. Костюхин, к.ф.-м.н.; Н.В. Шмырев, к.ф.-м.н. 

(НИИСИ РАН, г. Москва, galat@niisi.msk.ru, kost@niisi.msk.ru, shmyrev@niisi.msk.ru)

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

Ключевые слова: контролируемое выполнение, мониторинг, распределенные системы.

Под контролируемым выполнением [1] пони
мается такая организация функционирования аппаратно-программного комплекса, при которой 
осуществляются сбор и анализ информации о 
процессе 
функционирования 
и 
выполняются 

управляющие воздействия на этот комплекс.

Контролируемое выполнение направлено на 

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

Понятие контролируемого выполнения вклю
чает следующие основные положения:

интеграция средств информационной безо
пасности, отладки, управления;

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

охват всех этапов жизненного цикла аппа
ратно-программных комплексов, включая этап 
эксплуатации.

В [1] представлена среда контролируемого 

выполнения (система отладки/мониторинга
–

СОМ), которая поддерживает возможности инте

Программные продукты и системы
№ 2, 2010 г.

6

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

Эти возможности позволяют пользователям и 

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

В данной работе показано развитие концепции 

контролируемого выполнения, основанное на использовании парадигмы программирования, ориентированного на мониторинг (monitor-oriented 
programming, MOP [2]). 

Контролируемое выполнение, 
основанное на моделировании 

и верификации

Формальные методы верификации программ, 

основанные на статической проверке соответствия 
модели, доказательстве теорем, статическом анализе, в силу определенных ограничений [2] не позволяют в полной мере решить задачи, связанные 
с контролем количественных характеристик выполнения приложений. Авторы предлагают подход, включающий как статический анализ программного кода на соответствие модели, так и динамическую верификацию программы в ходе ее 
выполнения. В качестве средства описания модели выбран язык C ACSL (ANSI/ISO C SPECIFICATION LANGUAGE [3]), который позволяет описывать поведение программ на языке C в виде аннотаций. Инструмент Why [4] вместе со средствами 
для доказательства утверждений используется для 
проверки свойств в статическом режиме. Свойства, задающие количественные характеристики выполнения приложения, описываются с использованием средств профилирования инструментального комплекса СОМ и проверяются динамически 
в ходе выполнения программы.

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

Сбор и анализ информации 

средствами контролируемого выполнения

Контролируемое выполнение подразумевает 

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

Библиотека средств самоконтроля (БСС).

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

действия для исправления выявленных отклонений от эталонного правильного поведения.

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

В настоящее время реализован контроль сле
дующих аспектов поведения программ:

изменение хода выполнения программы в 

результате некорректных значений внутренних 
переменных программы и входных параметров 
вызываемых функций;

невозможность 
завершить 
выполнение 

фрагмента кода в установленное время (особенно 
актуально для контроля приложений в системах 
реального времени);

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

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

Рассмотрим основные группы вызовов БСС.
Актуаторы. Запуск актуаторов осуществляет
ся при помощи вызова UEL_ACTUATOR. Исполь

Программные продукты и системы
№ 2, 2010 г.

7

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

помещает в протокол сообщение вида

ASSERT (выражение):
[имя исходного файла:номер строки];

генерирует событие типа INVALID_STATE, 

которое может быть отображено средствами мониторинга инструментального комплекса;

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

Сенсоры. Данная группа делится на следую
щие типы.

Будильник. Сенсоры этого типа позволяют 

проверить, укладывается ли некоторая последовательность вычислений в заданный временной интервал. Сенсор UEL_SENSOR_GUARD (START) устанавливает интервал времени в секундах. Если за 
это время управление не достигает вызова 
UEL_SENSOR_GUARD (STOP), в протокол помещается соответствующее сообщение и генерируется 
событие, отображаемое средствами мониторинга.

Профилирование. Сенсоры этого типа от
мечают начало (UEL_SENSOR_PROFILER (START)) и 
конец (UEL_SENSOR_PROFILER (STOP)) профилируемого участка кода. Время выполнения участка 
(вместе с текстовым описателем) выводится в 
протокол.

Контроль использования динамически 

распределяемой памяти. Функции запроса и освобождения 
памяти 
UEL_calloc, 
UEL_malloc, 

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

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

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

Возвращаемые значения – UEL_ERR (ошибка 

при проверке), UEL_BAD (некорректный указатель), UEL_GOOD (корректный указатель).

При помощи вызовов данной группы можно 

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

Средства протоколирования. В любой точке 

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

Чтобы поместить интересующую пользовате
ля информацию в протокол, надо воспользоваться 
вызовом UEL_LOG_EXPRESSION.

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

Прочее. UEL_init, UEL_fini – инициализация и 

терминирование БСС.

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

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

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

сбор 
количественных 
характеристик, а 

именно:

процессорное время для выполнения опре
деленных фрагментов кода программы,

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

сетевые интерфейсы, используемые про
граммой;

Программные продукты и системы
№ 2, 2010 г.

8

использование аппаратных возможностей 

профилирования при условии наличия соответствующей поддержки;

использование стандартных средств и ме
ханизмов для возможности последующей интеграции с существующими решениями.

В силу специфики рассматриваемого класса 

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

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

С этой точки зрения важно, чтобы результат 

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

выполнение целевой системы, но и внешние инструменты обработки данных профилирования. 

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

Применение 
стандартизованных 
подходов, 

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

На основании изложенного можно сделать 

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

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

Необходимость введения этих средств про
диктована и сложностью рассматриваемых аппаратно-программных комплексов, и критичностью 
предъявляемых к ним требованиям по обеспечению должного качества обслуживания. 

Литература

1. Костюхин К.А. Организация контролируемого выпол
нения 
для 
разнородных 
распределенных 
программно
аппаратных комплексов. М.: НИИСИ РАН, 2006.

2. Chen F., Rosu G. MOP: Reliable software development 

using abstract aspects: Tech. rep.: Dept. of Computer Science, 
University of Illinois, 2006.

3. Baudin P., Filliatre J.-C., Marche C. Et al. ASCL: 

ANSI/ISO C Specification Language, 2008.

4. Filliatre J.-C., Marche C. The why/krakatoa/caduceus 

platform for deductive program verification, OOPSLA, 2004.

УДК 51.7, 519.1, 519.2, 519.6

АНАЛИЗ ОТКАЗОУСТОЙЧИВОСТИ 

ПАРАЛЛЕЛЬНЫХ КОЛЬЦЕВЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

(Работа выполнена при поддержке РФФИ, проект № 07-01-00101-a)

А.В. Коганов, к.ф.-м.н. (НИИСИ РАН, г. Москва, koganow@niisi.msk.ru); 

А.Н. Сазонов (ООО «Дойчебанк», г. Москва, sazonov@rg.ru)

Вводятся понятия модели кольцевой вычислительной системы (КлВС), представленной в виде ненаправленного 

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

Ключевые слова: вычислительные системы, наработка на отказ, дублирование.

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

имеющая свои преимущества и недостатки. На современном этапе чаще используются модели типа 

Программные продукты и системы
№ 2, 2010 г.

9

«звезда» или «дерево». В работах [1–3] исследуются планетарные вычислительные системы со 
структурой, близкой к древовидной и одновременно включающей подсистемы типа «звезда». 
Для таких систем в указанных работах рассматривается влияние процессов разрушения и починки. 
В работах [4–5] исследуются системы с полным 
графом, корпоративные вычислительные системы (КВС), которые идеально подходят для изучения эффектов, возникающих при росте системы, 
то есть не только процессов разрушения и восстановления существующих элементов, но и добавления новых. Еще одним подходом к изучению 
процессов роста может быть фиксация структуры 
графа системы (необязательно полносвязного) и 
рассмотрение набора одинаковых систем, граф которых имеет указанную структуру. Для данной 
работы в качестве графа выбрано кольцо, а системы, соответственно, названы кольцевыми вычислительными системами
(КлВС). На первый 

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

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

Моделирование 

функционирования КлВС

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

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

Поиск образа задачи на графе системы. Для 

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

Под разложимостью графа модели задачи на 

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

Генерация графа системы. Для КлВС был 

задан процесс генерации вероятностного типа с 
двумя основными характеристиками: количеством
вершин S и количеством цветов C.

При генерации КлВС каждая вершина получа
ет цвет как реализацию равновероятного испытания Бернулли на множестве цветов: 1, …, С. 

Разрушение и восстановление. Для модели
рования процессов разрушения и восстановления 
системы задаются два параметра: Pd – вероятность разрушения одного узла и Pf – вероятность 
починки одного узла.

Один цикл разрушения графа РКлВС прово
дится следующим образом: для каждого узла 
РКлВС проходит испытание Бернулли с вероятностью успеха Pd. В случае успеха узел и все инцен

Программные продукты и системы
№ 2, 2010 г.

10

дентные ему дуги исключаются из графа РКлВС. 
Восстановление осуществляется аналогично: для 
всех узлов исходной КлВС, не содержащихся в 
графе РКлВС, производится испытание Бернулли 
с вероятностью успеха Pf. В случае успеха узел и 
все инцендентные ему дуги, идущие к другим узлам РКлВС, добавляются в граф РКлВС. После 
одного цикла разрушения и восстановления при 
моделировании делается попытка разложения модели задачи на полученный граф РКлВС, поэтому 
порядок следования операций разрушения и восстановления важен [3]. В данной работе используется последовательность DR (destruct-repair), то 
есть каждый этап жизни системы состоит из разрушения, последующего восстановления и попытки разложения модели задачи на РКлВС.

Набор КлВС

Рост. Набор КлВС – это множество, состоящее 

из E одинаковых КлВС. 

Разрушенный набор – набор КлВС, в котором 

все или некоторые КлВС подвергались разрушению и восстановлению.

Отказ разрушенного набора – ситуация, при 

которой ни на одной (Р)КлВС из набора не может 
быть найден образ модели задачи.

Процесс роста разрушенного набора задается 

добавлением в набор одной или нескольких копий 
исходной, неразрушенной КлВС. В работе исследовались наборы систем с логарифмическим законом роста и количество систем (в том числе полностью разрушенных) в наборе на i-й итерации 
эксперимента E(i)=E0+ E1log2(i+2) , где скобки 
– операция округления вниз до ближайшего целого числа. В программных обозначениях E0=E0, 
E1=E1. Логарифмический рост выбран для экспериментальной проверки теоретического вывода о 
достаточности такой скорости роста для получения положительной вероятности не ограниченной 
по времени безотказной работы. Для этой цели естественно выбрать исходную систему с низкой отказоустойчивостью, например КлВС.

Алгоритм моделирования и сбора стати
стики. Помимо указанных параметров S, C, Pd, 
Pf, E0 и E1, для моделирования функционирования наборов КлВС задаются дополнительно Ni –
общее количество итераций разрушения–восстановления–роста–проверки в одном эксперименте, 
а также Ne – количество повторений эксперимента 
с целью сбора статистики.

Для проведения однократного эксперимента 

применялся следующий алгоритм.

1. Согласно параметрам S и C генерируется 

исходный граф КлВС.

2. Исходный граф копируется и сохраняется в 

качестве модели задачи.

3. Создается набор, состоящий из E(0)=E0+E1

копий исходного графа.

4. Запускается первая итерация эксперимента.

На каждой i-й итерации эксперимента
1) производится разрушение всех РКлВС из 

набора с использованием вероятности разрушения Pd;

2) производится починка всех РКлВС из набо
ра с использованием вероятности починки Pf;

3) происходит рост набора: к набору добавля
ются k копий исходной КлВС, причем k выбирается так, чтобы всего в наборе было E(i) систем, 
считая полностью разрушенные;

4) производится попытка разложения модели

задачи на все (Р)КлВС из набора. Если ни на 
одной системе из набора образ задачи не был найден, эксперимент завершается, наработка набора 
T в данном эксперименте устанавливается равной i-1.

Если достигнута итерация с номером Ni и от
каз на ней получен не был, T устанавливается 
равным Ni и эксперимент прекращается, считаясь
успешным. Если T<Ni, эксперимент считается неуспешным.

Для сбора статистики указанный эксперимент 

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

Результаты 

численного эксперимента

Варьирование количества типов элементов. 

В данной серии экспериментов варьировался 
параметр С – количество типов элементов. Результаты представлены в виде поверхностей, 
полученных по значениям функции F(C, Pf), где 
C – количество типов элементов; Pf – вероятность 
починки; F – количество успешных экспериментов. 

Эксперимент 1. Постоянные параметры

эксперимента: начальное количество копий КлВС 
E0=100; скорость роста набора E1=0 (рост отсутствует); вероятность разрушения Pd=0,1. Максимальное 
количество 
итераций 
эксперимента 

Ni=100; количество повторений каждого эксперимента Ne=1000; длина кольца S=10. Переменные 
параметры: число цветов C меняется от 2 до 100 с 
шагом 2; вероятность восстановления Pf меняется 
от 0,1 до 0,4 с шагом 0,01. 

Описание и анализ результата. При C=2 все 

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

При Pf 0,21 для всех C 10 частота выживания 

обнуляется, но с ростом вероятности починки 
примерно до 0,27 для всех значений С выходит на 
100 %. Это связано с большим начальным числом 
КлВС. В этом эксперименте (табл. 1) зависимость 
от числа цветов очень слабая для C 10. 

Программные продукты и системы
№ 2, 2010 г.

11

Таблица 1

Фрагмент таблицы значений F(C, Pf) 

по результатам эксперимента 1

С
Pf

0,20
0,21
0,22
0,23
0,24
0,25

2
100
100
100
100
100
100

4
13
12
10
18
36
75

6
5
3
3
2
24
57

8
1
1
0
5
21
66

10
0
0
1
4
32
71

Эксперимент 2. Число вершин S=100; пара
метр Pf варьируется от 0,7 до 0,83 с шагом 0,01;
остальные параметры такие же, как в эксперименте 1.

Описание и анализ результата. С увеличе
нием длины кольца при числе цветов C 3 вероятность выживания системы резко падает в сравнении с экспериментом 1. Это связано с ростом числа цветных подграфов исходной системы, которые 
надо воспроизвести на разрушенной системе. При 
С=2 сохраняется полная выживаемость при всех 
вероятностях ремонта. Для других значений С при 
Pf 0,76 частота выживания обнуляется. В интервале C 3 для 0,77 Pf 0,8 происходит быстрый 
рост частоты выживания почти до 100 % (табл. 2). 
Зависимость от числа цветов при C 3 слабая.

Таблица 2

Фрагмент таблицы значений F(C, Pf) 

по результатам эксперимента 2

C
Pf

0,750000 0,760000 0,770000 0,780000 0,790000

2
100
100
100
100
100

4
0
0
1
14
62

6
0
0
1
13
63

8
0
0
2
23
62

26
0
0
3
24
60

28
0
0
1
20
56

В обоих экспериментах пределы изменения Pf

подбирались вручную для включения в результаты эксперимента области перехода функции F(C, 
Pf) с нулевых значений к значениям Ni. 

Варьирование длины кольца. После анализа 

результатов экспериментов 1 и 2 был проведен 
эксперимент 3, в котором варьировались параметры S и C. Постоянные параметры: начальное 
количество копий КлВС E0=20; скорость роста 
набора E1=0 (не растет); вероятность разрушения 
Pd=0,3; вероятность починки Pf=0,6; максимальное количество итераций эксперимента Ni=100;
количество повторений каждого эксперимента 
Ne=1000. Переменные параметры: длина кольца S
изменяется от 2 до 30, шаг 1; количество типов 
элементов С изменяется от 2 до 50, шаг 1.

Описание и анализ результата. При S>10 и 

C>4 наработка на отказ F была близка к 0. Для 
С=2 наработка остается 100 при всех S. При малых 2<C 5 и S 5 наработка F близка к 100. При 
увеличении S до 10–15 наработка спадает до 0
(табл. 3). 

Таблица 3

Фрагмент таблицы значений F(S, C) 

по результатам эксперимента 3

S

C

2
3
4
5
9
10

2
100
100
100
100
100
100

3
100
100
100
100
100
100

4
100
100
100
100
100
99

5
100
100
97
93
100
94

6
100
93
85
86
87
79

7
100
61
39
41
19
30

8
100
58
22
10
2
3

9
100
53
18
6
0
1

10
100
35
14
5
0
0

11
100
38
6
3
0
0

12
100
33
4
1
1
0

13
100
37
3
2
0
0

28
100
4
0
0
0
0

29
100
8
0
0
0
0

30
100
3
0
0
0
0

В экспериментах 4–7 варьировались пара
метры S и Pf при различных С в разных экспериментах. Постоянные параметры: начальное количество копий КлВС E0=20; скорость роста набора E1=0 (не растет); вероятность разрушения 
Pd=0,3; максимальное количество итераций эксперимента Ni=100; количество повторений каждого эксперимента Ne=1000. Переменные параметры: длина кольца S варьируется от 2 до 30, шаг 1;
вероятность починки Pf варьируется от 0,05 до 
0,9, шаг 0,05; количество С типов элементов принимало значения 3, 5, 10, 20 соответственно в экспериментах 4, 5, 6, 7.

Описание и анализ результата. Эти экспе
рименты показали, что при всех значениях С наработка F с ростом S монотонно уменьшается. 
При S выше 16 наступает относительная стабилизация наработки на низком уровне. При этом для 
высоких значений Pf 0,65 начинается быстрый 
рост наработки до значений, близких к 100. С ростом C происходит некое уменьшение наработки, 
которое почти стабилизируется при C 5. На рисунках 1 и 2 показаны крайние по значениям C
поверхности зависимости F(S, Pf). Неровности 
поверхности связаны со статистическими флуктуациями средних значений. Графики для 5 C 10
близки к графику при C=20.

Программные продукты и системы
№ 2, 2010 г.

12

Эти результаты подтверждают уменьшение 

зависимости количества успешных экспериментов 
от S и от C по мере роста их значений.

Рост наборов систем. Основной и исходной 

целью разработки ПО для моделирования наборов 
РКлВС было изучение изменения значений F в зависимости от основного параметра роста – E1. 
Эксперименты 8 и 9 были посвящены этому вопросу.

Эксперимент 8. Постоянные параметры: ве
роятность разрушения Pd=0,3; максимальное количество итераций эксперимента Ni=100; количество повторений каждого эксперимента Ne=1000;
длина кольца S=100; вероятность починки Pf=0,5;
количество типов элементов C=3. Переменные параметры: начальное количество копий КлВС E0
варьируется от 0 до 100, шаг 1; скорость роста набора E1 варьируется от 0 до 30, шаг 1. 

Описание и анализ результата. Как и ожи
далось, по обеим переменным наработка F растет. 
В соответствии с теорией при достаточно большом параметре логарифмического роста E1 наработка выходит на высокие значения, близкие к 100 
при всех значениях начального количества копий 
E0. Крутизна роста F по Е1 близка при всех значениях Е0, но начинается он при различных значениях Е1. Для Е0=1 рост начинается с Е1=5. При 

Е0=90 рост начинается сразу при Е1=1. Линия начала роста в плоскости <E0, E1> в указанных пределах близка к прямой. При дальнейшем росте Е0
линия роста совпадает с осью Е0=0. Крутизна 
роста характеризуется изменением F от 0 до 100
при E1 12. График представлен на рисунке 3.

Эксперимент 9. Это дополнительный экспе
римент, в котором варьировались параметры C и 
E1. Его параметры в основном повторяют параметры эксперимента 8.

Постоянные параметры: вероятность разру
шения Pd=0,3; максимальное количество итераций эксперимента Ni=100; количество повторений 
каждого эксперимента Ne=1000; длина кольца 
S=100; вероятность починки Pf=0,5. =3; начальное 
количество копий КлВС E0=0. Переменные параметры: скорость роста набора E1 варьируется от 
0 до 30, шаг 1; количество типов элементов C
варьируется от 3 до 20, шаг 1.

Описание и анализ результата. Результаты 

эксперимента 9 показывают практически полную 
независимость значений F(C, E1) от C, в том числе и при значении C, равном 3, которое использовалось в эксперименте 8. При E1<12 наработка 
практически нулевая. Потом начинается плавный
рост наработки до значения около 100 при Е1=27. 
Линейный участок роста при 15 E1 21. При росте 
Е1 после значения 21 происходит плавный выход 
на константу 100 (рис. 4).

Общий анализ полученных данных. 

Классы систем

Результаты экспериментов 1–3 четко показы
вают резкое увеличение количества успешных 
экспериментов при снижении С до значения 2. 
При C=1 эксперимент выродился бы в поиск хотя 
бы одного исправного узла в любой из РКлВС. 
При C, равном 2, достаточно найти хотя бы два 
разнотипных связанных исправных элемента, так 
как любая двухцветная задача может быть разложена на граф РКлВС, состоящий из двух указанных элементов. 

Рис. 1. Зависимость F(S, Pf), C=3 (эксперимент 4)

Рис. 2. Зависимость F(S, Pf), C=20 (эксперимент 7)

1

4

7

10

13

16

19

22

25

28

0,05

0,3

0,55

0,8
0

20

40

60

80

100

S

Pf

80-100

60-80

40-60

20-40

0-20

2

5

8

11

14

17

20

23

26

29

0,05

0,35

0,65

0

10
20

30
40

50

60

70

80

90

100

S

Pf

90-100

80-90

70-80

60-70

50-60

40-50

30-40

20-30

10-20

0-10

Рис. 3. Зависимость F(E0, E1) (эксперимент 8)

0

7

14

21

28

35

42

49

56

63

70

77

84

91

98

0

12

24

0

10

20

30

40

50

60

70

80

90

100

E0

E1

90-100
80-90
70-80

60-70
50-60
40-50
30-40

20-30
10-20
0-10