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

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

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

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

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

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

Пример 4.14. На рис. 4.43 приведена ГСА с разбиением на фазы.

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

Узлами в данном случае являются вершины 1, 5, 6, 11. В фазу I входят вершины {1, 2, 3, 4, 13, 14}, в фазу II – вершина {5}, в фазу III – вершины {6, 7, 8, 9, 10}, в фазу IV – вершины {11, 12}.

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

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

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

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

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

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

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

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

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

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

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

,

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

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

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

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