Схема с откатом (Rollback Scheme)

Работа Rollback-схемы [51] основана на использовании аппаратной и программной избыточности. Процессорные модули A и B выполняют копии одной и той же задачи. При отсутствии ошибок на интервале состояние контрольной точки запоминается в памяти, после чего выполняется следующий интервал (ситуация «А» рис. 2.3 (а)).

Всякий раз, когда определяется несовпадение двух контрольных точек, производится повторное выполнение этого интервала (ситуация «В»). На рис. 2.3 (б) показаны действия в системе при возникновении ошибки в процессорном модуле B. То же самое происходит при возникновении ошибки в процессорном модуле A.

рис. 2.3. Варианты развития событий в Rollback-схеме:

а – нет ошибок;

б – откат в результате ошибки в модуле B или одновременном возникновении ошибок в обоих ВМ.

Можно использовать четыре способа формирования контрольных точек, (рис.(2.4)):

рис. 2.4 Варианты способа формирования контрольных точек в Rollback-схеме.

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

б) – использование промежуточных контрольных точек сохранения и сравнения состояний процессоров (SCCP): интервал решения задачи делится на подинтервалы (на рис.2.4 б) их 8), контрольные точки сохраняются в начале каждого подинтервала, в конце каждого подинтервала состояния модулей А и В сравниваются, если состояния не совпадают, то оба процессора выполняют откат назад к началу подинтервала, и он выполняется снова. Если состояния совпадают, то оба процессора выполняют следующий подинтервал решения задачи.

в) - использование промежуточных контрольных точек сохранения состояний процессоров (SCP): В каждой контрольной точке подинтервала сохраняются состояния модулей A и B, в конце интервала решения задачи (в конце последнего подинтервала) состояния модулей A и B сравниваются. Если состояния совпадают, то задача – завершена, и оба процессора выполняют следующий интервал решения задачи. Если состояния не совпадают, то находят подинтервал, где это происходит, и оба процессора выполняют откат назад к найденному подинтервалу. В примере откат назад выполнен к подинтервалу 2 (рис.2.4 в)).

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

АЛГОРИТМЫ РАБОТЫ

Схема – (а)

Шаг 1: Задать исходные состояния модулей А и В .

Шаг 2: Решить задачу на очередном интервале.

Шаг 3: В конце решения задачи состояния модулей А и В сравниваются.

Шаг 4: Если состояния не совпадают, то идти к шагу 2.

Шаг 5: Если состояния совпадают, то задача завершена. Заменить старые состояния модулей на новые.

Шаг 6: Идти к шагу 1.

Схема – (б)

Шаг 1: Интервал решения задачи делится на подинтервалы.

Шаг 2: Контрольные точки сохраняются в начале каждого интервала.

Шаг 3: Оба процессора выполняют данный подинтервал.

Шаг 4: В конце каждого подинтервала состояния модулей А и В сравниваются.

Шаг 5: Если состояния не совпадают, то идти к шагу 3.

Шаг 6: Если состояния совпадают, то контрольные точки сохраняются.

Шаг 7: Выполнение следующего интервала.

Шаг 8: Идти к шагу 3.

Схема – (в)

Шаг 1: Оба процессора выполняют данный подинтервал.

Шаг 2: В каждом подинтервале сохраняются состояния модулей А и В.

Шаг 3: В конце интервала решения задачи (в конце последнего подинтервала)

состояния модулей А и В сравниваются.

Шаг 4: Если они не совпадают, то находят подинтервал, где это происходит, и оба процессора выполняют откат назад к найденному подинтервалу, далее идти к шагу 3.

Шаг 5: Если состояния совпадают, то задача завершена.

Шаг 6: Выполнение следующего интервала.

Шаг 7: Идти к шагу 1.

Схема – (г)

Шаг 1: Контрольные точки сохраняются в начале интервала решения задачи.

Шаг 2: Оба процессора выполняют данный подинтервал.

Шаг 3: В конце каждого подинтервала сравниваются состояния модулей А и В.

Шаг 4: Если состояния не совпадают, то ошибка обнаружена, и оба процессора выполняют шаг 2.

Шаг 5: Если состояния совпадают, то задача завершена.

Шаг 6: Выполнение следующего интервала.

Шаг 7: Идти к шагу 2.

Схема восстановления вычислительного процесса с накатом (Roll-Forward Checkpointing Scheme - RFCS).

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

В зависимости от места возникновения ошибки, в RFCS-схеме возможны четыре сценария. Пусть интервал, предшествующий интервалу , завершился без ошибок. В этом случае, контрольные точки пары модулей A и B, выполняющих копии задачи, в конце интервала ( и ) совпадают. Интервалы, следующие за , обозначаются как и . Четыре возможные ситуации развития событий обозначаются через A – D.

(A) Нет ошибок: В процессорных модулях A и B на интервале нет ошибок. После этого выполняется следующий интервал (рис. 2.5 а)).

(B) Одна ошибка: Эта ситуация имеет место в случае, когда в единственном модуле возникает ошибка на интервале . Кроме того, нет ошибок в других модулях в интервалах и (рис. 2.5 а)).

Без потери общности предположим, что на интервале возникла ошибка в процессорном модуле B, и нет ошибок в процессорном модуле A и свободном модуле S в интервалах и (рис. 2.5 а)).

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

рис. 2.5 Возможные ситуации при восстановлении вычислительного процесса в RFCS-схеме

а – восстановление без отката назад;

б – откат после одного интервала повтора;

в – откат после двух интервалов повтора.

Шаг 1: Состояние S приводится в соответствие с состоянием модулей А и В в контрольной точке . Параллельно А и В выполняют следующий интервал .

Шаг 2: После завершения выполнения S интервала , контрольная точка сравнивается с и . Поскольку А и S выполнили без ошибок интервал , совпадает с ,. Поэтому модуль А рассматривается как безошибочный в интервале .

Во время выполнения S интервала , А и В завершают интервал и ожидают окончания сравнения с и . Поскольку сравнение определяет, что совпадает с , состояние модуля В приводится в соответствие с состоянием модуля А в контрольной точке .

Шаг 3: Для проверки правильности выполнения А на интервале процессорный модуль S выполняет интервал . Тем временем модули А и В выполняют интервал . Когда S завершает , контрольная точка сравнивается с . Если на интервале в А и S не было ошибок, и будут совпадать.

Шаг 4: На предыдущем шаге было определено, что А и В находятся в корректном состоянии в начале интервала . Поэтому восстановление можно считать завершенным. Любые ошибки в интервале могут рассматриваться подобно ошибкам в интервале .

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

(С) Возврат после одного интервала повтора: В этом случае, восстановление не является успешным, и система производит откат назад к началу интервала . Эта ситуация имеет место, когда два модуля завершили с ошибкой. Возможны три сценария развития событий, один из которых приведен на рис. 2.5 (б).

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

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

Для иллюстрации рассмотрим сценарий, приведенный на рис. 2.5.(в). Шаги 1 – 3 являются полностью идентичным соответствующим шагам в ситуации В. Однако, при сравнении с определяется их несовпадение. После этого система возвращается к последней корректной точке.

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

Поиск по сайту: