книги / Надежность и диагностика компонентов инфокоммуникационных и информационно-управляющих систем.-1

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

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

По фронту РМЕ1 выполняется вывод из стека.

Селектор РМЕ блокирует прохождение РМЕ на Рк, стек и Тош при исключении второго обращения к памяти команд.

Методы блокового контроля правильности хода программ

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

341

Однако такое равномерное разбиение требует значительных преобразований ГСА, так как не учитывает ее структуру. Избежать этих преобразований можно за счет разбиения команд ГСА на блоки неравной длины.

Блоковый контроль программ по методу разбиения программы на фазы (блоки)

Как видно из предыдущих разделов, контроль программ

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

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

ВГСА выделяются узлы – вершины, к которым подходит более одной дуги. Отъединением от каждого узла всех подходящих к нему дуг граф разбивают на множество несвязанных подграфов. Последовательность команд, соответствующая каждому подграфу, представляет собой фазу. У каждой фазы только один вход и один или несколько выходов.

Пример 4.14. На рис. 4.43 приведена ГСА с разбиением на фазы. Узлами в данном случае являются вершины 1, 5, 6, 11. В фазу I входят вершины {1, 2, 3, 4, 13, 14}, в фазу II – вершина {5}, в фазу III –

вершины {6, 7, 8, 9, 10}, в фазу IV – вершины {11, 12}.

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

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

342

Рис. 4.43. ГСА, разбитая на фазы

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

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

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

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

g(x) = x6 + x4 + x3 + x +1.

343

Рис. 4.44. Схема встроенного контроля по методу сигнатур блоков команд

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

Вслучае короткого перехода требуется после проверки скорректировать содержимое эмулятора программного счетчика.

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

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

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

команды не вводятся. tизб – (временная избыточность) зависит от состава команд программы:

344

tизб = NNк.п ,

где Nк.п – количество команд короткого перехода; N – общее количество команд в программе.

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

Nбл Nп / N 2 ,

где Nбл – число блоков, на которое разбивается программа; Nп – число команд перехода; N – общее количество команд в программе.

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

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

Основное достоинство метода – незначительная временная и информационная избыточность.

Блоковый контроль правильности хода программ

спомощью сигнатур

Вданном разделе более детально рассматривается реализация метода блокового контроля с помощью сигнатур. Рассматриваемый метод блокового контроля правильности хода выполнения программы (функциональной модели МП системы) основан на сравнении

345

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

LCALL AC,

т.е. вызов подпрограммы по адресу, указанному во втором и третьем байтах команды, где АC – выделенные для СВК адреса из адресного пространства ПЗУ. СВК выделяет момент появления АC на адресной шине и стробирует сигнатуратор. По адресу АC в ПЗУ хранится команда RET (возврат из подпрограммы).

			Рассмотрим пример. На рис. 4.45
			приведена граф-схема фрагмента про-
			граммы, где вершины соответствуют ли-
			нейным участкам программы (в частном
			случае – одной команде), а на рис. 4.46
			показана граф-схема этой программы
			с дополнительными командами, обеспе-
			чивающими равенство сигнатуры нулю
			в точках сравнения или требуемые зна-
			чения в точках схождения и замыкания
			контуров (S4,5,6; S14,15; S3).
			Выравнивание сигнатур выполня-
			ется при помощи команды
	Рис. 4.45. Граф-схема фраг-
	мента программы		MOV direct,#data

Поле direct фиксировано и определяет адрес ячейки внутреннего ОЗУ, не используемой в рабочей программе. Меняя поле #data, можно добиться требуемого значения сигнатуры. Если значение поля direct принять равным коду команды, то сумма по модулю два кода команды и поля direct равна нулю. В этом случае, чтобы после вы-

346

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

Рис. 4.46. Граф-схема программы с дополнительными командами

Рассмотрим выделенный окружностью участок программы на рис. 4.46 (см. ниже). Пусть S4, S5, S6 – сигнатуры, вычисленные к моменту выполнения команд выравнивания по соответствующим путям. Пусть к моменту выполнения фазы 7 сигнатура S4,5,6 должна равняться нулю, независимо от того, по какому пути выполнился переход к 7.

347

Определим data 1, data 2, data 3:

S4 + data 3 = 0, отсюда data 3 = S4;

S6 + data 2 + data 3 = 0, отсюда data 2 = S6 + S4;

S5 + data 1 + data 2 + data 3 = 0, отсюда data 1 = S5 + S6.

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

Оценим объем дополнительной памяти (М) для команд, обеспечивающих реализацию рассматриваемого метода контроля. Пусть D – число команд, на которые выполняется переход больше чем из одного места программы (узловые команды), Si – число переходов к i-й узловой команде, С – число циклов в программе. Все команды, используемые для модификации программы, трехбайтные.

Каждое сравнение сигнатуры с 0 требует выполнения трех ко-

манд:

MOV direct, #data – обеспечивает нулевую сигнатуру; LCALL AC – инициирует момент сравнения;

LJMP – обеспечивает продолжение рабочей программы. Таким образом,

D

M = 3x ∑Si

i=1

+ 3xC .

На рис. 4.47 приведена функциональная схема СВК, реализующая рассматриваемый блоковый метод контроля правильности хода выполнения программы для микроконтроллера как объекта контроля. Сигналы с шины данных ЦП поступают на первый вход, а сигналы из регистра сигнатуры (РгС) – на второй вход сумматора по mod2 (СМ). Результат сложения фиксируется по фронту сигнала РМЕ ЦП в РС. Содержимое РС может быть записано в ЦП через буфер Б или загружено из ЦП при выполнении команды MOV X.

348

Для этого РС присваивается адрес Арс из адресного пространства внешнего ОЗУ. При загрузке РС переводится в третье состояние, это обеспечивает на втором входе сумматора все единицы и РгС < < – D + 1...1.

Рис. 4.47. Функциональная СВК, реализующая блоковый метод контроля

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

349

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

Метод контроля программ на основе полиноминальной интерпретации схем алгоритмов (программ)

В данном разделе представлен метод контроля программ по ГСА, где двоичное представление команд интерпретируется как двоичное представление коэффициентов полинома соответствующей степени [6].

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

Пример 4.15. На рис. 4.48 представлена ГСА; 7 линейных фрагментов, на которые она разбивается, приведены на рис. 4.49.

Каждому линейному фрагменту ставится в соответствие полином Мh(х):

	h		k
М		(x) =	∑
			x f (k−l )
			l=1

f −1		k
∑
	l		xr	,
r=0

где h – порядковый номер фрагмента; k – количество операторных вершин в линейном фрагменте; f – количество разрядов в двоичной комбинации каждой операторной вершины.

350