2.1 체크포인터 운영 및 고장 탐지 방법

5개의 동일한 프로세서로 구성된 QMR 시스템에서 고장 탐지는 다수결 회로(majority voter)를 통해 이루어진다. 각 프로세서 상태 값을 다수결 회로에 전송하여 3개 이상의 프로세서에서 일치하는 값을 다수결 상태 값으로 결정한다. 다수결 값과 다른 상태 값을 가지는 프로세서는 고장이 발생한 것으로 간주한다.

여기서 중요한 관건은 어느 시점에서 고장 탐지를 실행하는가이다. 고장 탐지를 자주 하면 고장 극복 능력은 상승하지만, 반면 다수결 회로에 상태 값을 전송하고 그 결과를 이용하여 고장이 발생한 프로세서를 특정하는 데 시간이 더 소요된다. 즉 너무 빈번한 고장 탐지는 오버헤드를 증가시키고, 고장 탐지 구간이 길어지면 고장이 발생할 확률도 증가한다. QMR 시스템은 상태 값을 다수결 표결하기 때문에 5개 프로세서 중에서 최대 2개 프로세서에서 고장이 발생하더라도 나머지 3개 프로세서는 정상 값을 출력하므로 고장을 극복할 수 있다. 고장 프로세서의 상태 값을 다수결 값으로 교체하면 해당 프로세서의 고장이 간단하게 복구된다. 하지만 3개 이상의 프로세서에서 동시에 고장이 발생하면 QMR 시스템은 실패한다.

본 연구에서 상태 값은 태스크의 실행에 필요한 모든 변수 값을 의미한다. 과도 고장은 외부의 환경적 또는 전기적 요인에 의해 일시적으로 발생하는 시스템의 오동작을 말하며, 이러한 오동작이 상태 값을 변경시키면 태스크의 실행에 오류를 일으킨다. 따라서 고장이 발생한 프로세서의 상태 값을 정상값으로 교체하면 과도 고장이 복구되는 것으로 간주한다. 반면에 고장 원인이 지속적으로 존재하는 간헐적(intermittent) 고장 또는 영구 고장은 상태 값의 교체만으로는 복구할 수 없다. 이들은 5중 구조를 이용한 다수결 표결을 통하여 극복된다.

본 연구에서는 QMR 시스템에 체크포인터를 도입하여 3개 이상의 프로세서 고장도 복구할 수 있는 기법을 제안한다. 다수의 체크포인터를 태스크의 실행 시간 중에 삽입한 후 고장이 발생하면 고장 발생 직전의 체크포인터로 회귀(rollback)하여 태스크를 다시 실행함으로써 고장을 복구할 수 있다. 본 연구에서는 다루는 고장의 종류를 과도 고장으로 한정한다. 영구 고장은 발생 후 시스템에 그 영향이 계속 남아 태스크 재실행 후에도 잘못된 출력을 내보내기 때문에 시간적 여유 구조의 방법으로는 복구되지 못한다.

이번 연구에서는 시스템에서 발생하는 고장에 대하여 다음과 같은 가정이 성립한다고 설정한다.

가정 1 : (a) 고장 탐지 시에는 모든 프로세서에서 발생한 고장이 탐지된다.

(b) 체크포인터에는 고장이 발생하지 않는다.

제안된 방법에서는 태스크의 상태 변수를 다수결 회로를 이용하여 표결하기 때문에 각 프로세서에서 발생하는 거의 모든 고장을 탐지할 수 있다. 따라서 가정 1.(a)는 합리적이라고 말할 수 있다. 또한 체크포인터에 상태 변수를 저장할 때 오류가 없는 다수결 값을 사용하고, 외부의 영향에 무관한 고신뢰성을 가진 메모리를 상태 변수 저장소로 사용한다면 가정 1.(b)도 보장된다.

본 논문에서 대상으로 하는 태스크는 결정적 스케줄링(deterministic scheduling)에 의해 미리 정해진 강성 실시간 태스크(hard real-time task)로 한정한다. 따라서 체크포인터는 각 프로세서에서 실행되는 태스크의 동기화 시점으로 간주할 수 있다. 강성 실시간 태스크의 경우 데드라인 이내에 반드시 태스크의 수행이 끝나야 하므로 고장 복구에 소요되는 시간이 짧을수록 유리하다. 이중 구조 또는 삼중 구조는 1개 프로세서에서 고장은 복구할 수 있으나 그 이상에서 발생하는 고장은 복구할 수 없다.

태스크가 정해져 있는 경우에도 체크포인터에서의 상태 값은 사전에 알 수 없는 경우가 많다. 왜냐하면 제어 태스크와 같이 태스크의 실행 중에 외부 센서로부터(또는 통신 채널을 통하여) 데이터를 읽어와 그 값을 기반으로 연산을 하고 결과가 상태 값에 반영되는 경우 체크포인터에 어떤 값이 저장될지 미리 알 수 없기 때문이다.

그림 1은 이번 연구에서 제안하는 QMR 시스템에서의 고장 탐지 및 체크포인터 삽입 방법을 나타낸다. 본 방법의 핵심은 체크포인터 구간 사이에 여러 번의 고장 탐지를 실행하여 고장 탐지 확률을 높이는 것이다. 그림 1에서 볼 수 있듯이 QMR 시스템은 P1에서 P5까지 5개의 프로세서를 가지며, 각 프로세서의 태스크는 T1, T2,...,Tnm의 nm개 조각으로 나뉜다. 태스크 조각은 순서대로 실행되며 각 태스크 조각을 실행한 후 고장 탐지를 하고 고장이 발견되지 않으면 다음 태스크 조각을 실행한다. 이때 만약 1~2개 프로세서에서 고장이 발견된다면 동기화 과정을 실행하여 다수결 값을 고장이 발생한 프로세서 상태 값에 덮어씀으로써 고장을 복구한다. 본 논문에서 Ti는(1≤i≤nm) i번째 태스크 조각을 가리킴과 동시에 Ti를 수행하는 데 걸리는 시간도 나타낸다고 설정한다.

그림 2는 QMR 구조를 이용한 고장 탐지 및 동기화 방법을 상세하게 나타낸다. 각 프로세서는 매 고장 탐지 시점에서 태스크 조각을 실행한 후 얻어진 상태 변수(state value)를 다수결 회로(그림 2의 ‘Voter’)로 전송하며, 다수결 회로는 5개의 프로세서가 전달하는 상태 변수에 대한 표결을 실시한다. 다수결의 결과에 따라 QMR 시스템이 실행하는 다음 동작은 아래와 같이 나뉜다.

(i) 다수결 값이 존재하는 경우 : 다수결 값이 존재한다는 뜻은 5개의 상태 변수 중 동일한 값을 가지는 변수가 세 개 이상 있다는 의미이다. 다시 말하면 고장이 발생한 프로세서의 개수가 0~2개이며, 다수결을 차지한 변수는 고장이 일어나지 않은 정상적인 상태 변수이다. 제안된 방법에서는 이러한 정상적인 상태 변수를 고장이 발생한 프로세서의 상태 변수에 덮어쓰는 동기화를 실행함으로써(그림 2의 ‘Synchronize State’ 동작) 고장 복구를 구현한다. 상태 변수 동기화를 완료하면 다음 태스크 조각을 실행한다. 만약 다수결 개수가 5라면 어떠한 프로세서에서도 고장이 발생하지 않았다는 뜻이기 때문에(그림 2의 ‘No fault’ 조건) 동기화 과정 없이 다음 태스크 조각을 곧바로 실행한다.

(ii) 다수결 값이 존재하지 않는 경우 : 다수결 값이 존재하지 않는다는 것은 3개 이상의 프로세서에서 고장이 발생했다는 뜻이다. 이 경우는 고장의 영향을 받지 않은 정상적인 상태 변수 값을 특정하지 못한다. 따라서 QMR 시스템은 직전의 체크포인터로 회귀하여 체크포인터에 저장된 정상적인 상태 변수로 태스크를 재실행한다.

그림 3은 앞에서 설명한 QMR 구조에서 제안된 체크포인터를 운영하는 방식을 나타낸 순서도이다. 본 순서도에서 j는 태스크 조각 Tj에 해당하는 인덱스이며, v는 상태 변수가 저장되는 체크포인터의 위치를 나타낸다. v=0일 때는 상태 변수의 초기 값을 사용한다. 그림에서 나타내었듯이 Tj를 실행한 후 QMR 다수결 회로를 이용한 표결을 실시한다(‘QMR Voting’). 3개 이상 프로세서 고장이 발생하면 앞에서 설명했듯이 v번째 체크포인터로 회귀한 후 저장된 상태 변수로 시스템을 복구한다(‘Restore v-th State’). 제안된 방식에서는 m개의 고장 탐지 모듈마다 체크포인터를 한 개씩 삽입하기 때문에 가장 최근의 체크포인터 v에는 태스크 Tvm+1 조각을 실행하기 위한 상태 변수가 저장되어 있다. 따라서 그림 3에서 볼 수 있듯이 v번째 체크포인터로 회귀한 다음에는 j=vm로 설정한 후 j를 1 증가시키고(‘j=j+1’) 태스크 조각 Tj+1를 재실행한다(‘Task Execution: Tj’).

한편 Tj를 실행한 후 1~2개 프로세서에서 고장이 발생하였다면 동기화 과정을 수행하며(‘Synchronize States’), 고장이 하나도 발생하지 않았다면 동기화를 실시하지 않는다. 마지막으로 m번의 고장 탐지를 수행한 후에는 체크포인터에 상태 변수를 저장하고 체크포인터 수를 하나 증가시킨다(‘Store State Values (v=v+1)’). 현재까지 실시한 고장 탐지 횟수가 m보다 적다면 j를 1 증가시켜 다음 태스크 조각 Tj+1을 실행한다. 위의 과정을 모든 태스크 조각의 수행이 끝날 때까지 반복한다.

2.2 전체 태스크 실행 시간

제안된 QMR 시스템에서 각 프로세서의 태스크에 n개의 체크포인터가 삽입되고 체크포인터 사이에는 m번의 고장 탐지 과정이 실행된다고 하였다. 따라서 그림 1에서 나타낸 바와 같이 한 개의 태스크는 nm개의 구간으로 나눌 수 있으며, T1부터 Tnm까지 순차적으로 실행하면 태스크의 수행이 완료된다. 고장이 발생하지 않은 한 개의 태스크를 수행하는 데 소요되는 시간을 T라고 하면 T는 다음과 같이 유도된다.

위 식에서 구한 T는 고장 탐지 과정이나 체크포인터를 고려하지 않은 순수한 태스크 수행 시간이다.

본 연구에서는 제안된 QMR 시스템에 삽입되는 체크포인터가 모두 등(等) 간격으로 배치된다고 설정한다. 고장 탐지가 실행되는 시각 사이의 간격을 Δ라 하고 다수결 회로를 이용하여 고장을 탐지하는 데 소요되는 시간을 Td라 하자. 한 태스크에서 총 nm번의 고장 탐지가 실행되기 때문에 Δ는 다음과 같이 구할 수 있다.

2.1장에서 QMR 시스템은 1~2개 프로세서에서 고장이 발생하면 동기화 과정을 수행하고 3개 이상의 프로세서에서 고장이 발생하면 고장 탐지 구간을 재수행한다고 하였다. 이러한 고장 탐지 및 극복 과정을 일반화하여 QMR 시스템이 태스크 실행을 완료할 때까지 총 i번의 동기화 과정을 수행하고 r번의 고장 탐지 구간 재수행을 실행했다고 가정하자. 또한 고장 탐지와 체크포인터 삽입, 그리고 동기화 과정과 재수행 때문에 늘어난 태스크의 전체 실행 시간을 T(i,r)이라 하자. T(i,r)은 순수 태스크 실행 시간 T에 nm번의 고장 탐지와 n번의 체크포인팅(체크포인터에 상태 값 저장), 그리고 i번의 동기화와 r번의 고장 탐지 구간 재수행 시간을 모두 더한 값이다. 따라서 T(i,r)은 아래 식과 같이 유도된다.

위 식에서 Tc는 체크포인터에 상태 값을 저장하는 데 걸리는 시간이며, Ts는 동기화 과정에 소요되는 시간이다.

태스크의 데드라인을 D라고 하면 태스크의 실행 시간은 D를 넘지 말아야 한다. 즉 임의의 i와 r에 대해서

이 성립되어야 한다. 또한 체크포인터 수 n과 고장 탐지 횟수nm도 식 (4)를 만족시키도록 설정하여야 한다. 즉 i와 r이 최소값(i=0,r=0)일 때의 태스크 전체 실행 시간이 T(0,0)≤D가 되도록 n과 m을 결정한다.

태스크 실행이 식 (4)의 조건을 만족시키면서 최대 몇 번의 동기화 과정을 거칠 수 있는지 알아보기 위해 가능한 최대 동기화 횟수를 w라고 정의하자. 고장 탐지 모듈과 체크포인터만 삽입한 후 동기화와 고장 탐지 구간 재수행을 한 번도 실행하지 않았을 때의 태스크 수행 시간은 식 (3)으로부터 T(0,0)으로 표현된다. T(0,0) 역시 식 (4)를 만족시켜야 하기 때문에 D―T(0.0)의 여유 시간이 얻어진다. 그런데 동기화 시간이 Ts이므로 동기화 과정이 실행될 수 있는 최대 횟수는 D―T(0.0)에서 Ts를 나누어 얻는 몫과 같다. 이것을 식으로 표현하면 다음과 같다.

여기서 $LFLOOR{x RFLOOR}$는 x를 넘지 않는 최대 정수이다. 식 (5)는 고장 구간 재수행이 한 번도 실행되지 않는다는 가정에서 얻어진 결과이다.

위 유도 과정을 응용하여 가능한 최대 구간 재수행 횟수도 구해보자. 그런데 위 유도 과정과 달리 이번에는 태스크 실행 중 i번의 동기화 과정도 함께 수행된다고 가정한다. 이를 표현하기 위해 i번의 동기화 과정이 수행될 때 데드라인 조건 식 (4)를 만족시키는 최대의 재수행 가능 횟수를 r(i)라고 표기한다. 식 (5)를 응용하면 r(i)는

로 유도된다.

3.1 마코프 체인 모델

제안된 QMR 시스템에 대한 마코프 체인 모델을 유도하기 위해 먼저 각 프로세서에서 발생하는 고장이 발생률 λ를 가진 포와송(Poisson) 분포를 따른다고 설정하자. 또 고장 탐지 간격 Δ 내에서 고장이 하나도 없을 확률을 p라 하고, 1개 이상의 고장이 발생할 확률을 q라 하자. p와 q는 다음과 같이 표현된다^[10].

p과 q를 이용하여 Δ 내에서 고장이 발생하는 프로세서의 개수에 따른 아래와 같은 세부 확률을 구해 보자.

∙ α : Δ 내에서 5개 프로세서 모두에 고장이 없을 확률

∙ β : Δ 내에서 1개 또는 2개 프로세서에서 고장이 발생할 확률

∙ μ : Δ 내에서 3개 이상의 프로세서에서 고장이 발생할 확률

식 (7)로부터 각각의 확률은 다음과 같이 유도된다.

QMR 시스템 마코프 체인 모델의 상태 변수는 xi,j로 표현한다. 여기서 i는 QMR 시스템이 지금까지 i번의 동기화 과정을 실행했다는 의미이며, j는 상태 xi,j에서 다음에 실행되어야 하는 태스크 조각은 Tj+1이라는 뜻이다(j=nm일 때는 시스템이 현재 상태에 계속 머무른다). i와 j는 각각 0≤i≤w와 0≤j≤nm의 범위를 가지므로 마코프 체인의 총 상태 개수는 (w+1)(nm+1)개이다.

그림 4는 본 연구에서 제안하는 QMR 시스템의 확률적인 상태 변화를 마코프 체인으로 모델링한 것이다. 그림 4에서 볼 수 있듯이 마코프 체인의 상태는 (w+1)개의 행으로 배열되어 있으며 각 행은 동기화 횟수가 동일한 nm+1개의 상태로 구성된다. 예를 들어 첫 번째 행은 x0,0,...,x0,nm로 이루어져 있다. 그림 4에서 진한 색의 상태는 체크포인터가 배치된 곳을 나타낸다. 예를 들어 첫 번째 행의 상태 x0,m은 태스크 조각 Tm의 수행이 끝났으므로 고장 탐지 후 체크포인터를 삽입하고 Tm+1을 수행하기 직전의 상태이다. 이를 일반화하면 v번째 체크포인터는 상태 x0,vm에 삽입된다고 말할 수 있다(1≤v≤n).

본 마코프 체인은 다음과 같이 α, β, μ에 의한 세 가지 종류의 확률적 상태 천이를 가진다.

(i) 확률 α에 의한 상태 천이 :

그림 4의 마코프 체인은 x0,0에서 시작하여 첫 번째 태스크 조각 T1을 실행하는데 이 과정에서 어떠한 프로세서에서도 고장이 발생하지 않으면(확률 α) 다음 상태 x0,1로 천이하여 두 번째 태스크 조각 T2를 실행한다. 마찬가지로 x0,1에서는 α의 확률로 j 값이 1 증가한 x0,2로 천이한다. 그림 4의 마코프 체인 모델의 상태 천이 경로 중 확률 α로 이루어진 것들이 모두 이러한 과정을 나타낸다. 이를 일반화하여 마코프 체인 모델이 현재 상태 xi,j에 있다고 하자. QMR 시스템은 태스크 조각 Tj+1를 실행하는데 이 과정에서 어떠한 프로세서에서도 고장이 발생하지 않았다면(확률 α) 마코프 체인은 다음 상태 xi,j+1로 천이한다. 즉 0≤i≤w, 0≤j<nm에서

이다.

(ii) 확률 β에 의한 상태 천이 :

(i)과 다르게 x0,0에서 T1를 실행할 때 1개 또는 2개의 프로세서에서 확률 β로 고장이 탐지되었다고 가정하자. 이 경우 제안된 방법에 의해 고장이 발생한 프로세서의 복구를 위한 동기화 과정이 수행되며, 고장이 복구된 후에는 다음 태스크 조각 T2가 실행될 수 있다. 따라서 동기화 과정의 횟수를 나타내는 인덱스 i 값이 1 증가하고 T1의 수행이 끝났기 때문에 마코프 체인은 x0,0에서 x1,1로 천이한다. 이를 일반화하여 마코 프 체인이 상태 xi,j에 있을 때 Tj+1의 실행 과정 중 β의 확률로 1~2개의 프로세서에서 고장이 발생하였다고 하자. 앞의 경우와 마찬가지로 QMR은 동기화 과정을 한 번 수행하여 고장을 복구한 후 다음 태스크 조각 Tj+2를 실행할 수 있는 상태를 가지므로 xi+1,j+1로 천이한다. 즉 0≤i<w, 0≤j<nm에서

이다.

(iii) 확률 μ에 의한 상태 천이 :

이번에는 x0,0에서 T1를 실행할 때 3개 이상의 프로세서에서 μ의 확률로 고장이 탐지된 경우를 생각하자. 이 경우에는 다수결 값이 존재하지 않으므로 동기화로 고장을 복구할 수 없다. 따라서 가장 가까운 직전 체크포인터로 회귀하고 저장된 상태 값을 이용하여 태스크 조각을 재수행한다. x0,0에서 가장 가까운 직전 체크포인터는 x0,0 자신에 배치된 것이므로 그림 4에 나타낸 바와 같이 x0,0은 확률 μ의 셀프 루프(self-loop) 천이를 가진다. 현재 상태가 x0,0이 아니라 x0,1이라고 하자. 또 태스크 조각 T2가 실행될 때 고장 탐지 모듈에서 얻어지는 다수결 값이 존재하지 않는다고 하자. 앞의 경우와 마찬가지로 이것은 3개 이상의 프로세서에서 고장이 발생했다는 뜻이므로 QMR 시스템은 직전 체크포인터로 회귀해야 한다. 그런데 그림 4의 첫 번째 상태 행에서 볼 수 있듯이 x0,1에서 가장 가까운 직전 체크포인터 역시 x0,0에 배치된 것이다. 따라서 마코프 체인은 x0,1에서 x0,0으로의 확률적 상태 천이 μ를 가진다.

위의 설명을 일반화하기 위해 마코프 체인이 상태 xi,j에 있을 때 태스크 조각 Tj+1의 실행 중 3개 이상의 프로세서에서 고장을 탐지했다고 가정하자. QMR 시스템이 회귀해야 할 체크포인터의 위치를 특정하기 위해서 j를 아래와 같이 표현하자.

태스크에는 매 m개의 고장 탐지 모듈마다 체크포인터 한 개가 삽입되기 때문에 xi,j에서 가장 가까운 직전 체크포인터는 v번째 체크포인터이며 이것은 상태 xi,vm에 배치되어 있다. 따라서 QMR 시스템은 상태 xj,vm로 회귀하여 태스크 조각 Tvm+1부터 재실행한다. 즉 0≤i≤w, 0≤j<nm에서

이다. 그림 4의 확률 μ를 가지는 모든 천이가 이 과정을 나타낸다.

xi,nm는 i번의 동기화 과정을 거쳐서 마지막 태스크 조각 Tnm을 실행함으로써 전체 태스크의 실행을 성공적으로 완료한 상태이다(0≤i≤w). xi,nm에 도달한 이후 QMR 시스템은 이 상태에 계속 머문다. xi,nm이 가진 확률 1의 셀프 루프 천이가 이를 표현한다.

3.2 태스크의 실행 성공 확률

본 절에서는 앞에서 도입한 마코프 체인 모델에 기반하여 태스크의 실행 성공 확률을 구한다. 현재까지 수행한 고장 탐지 횟수 k를 마코프 체인 상태 xi,j가 가지는 인수라고 설정하면 xi,j를 k에 대한 함수라고 해석할 수 있다. xi,j의 표현을 확장하여 k번의 고장 탐지를 수행한 후 QMR 시스템이 가지는 상태를 xi,j(k)라고 하자. 또한 πi,j(k)를 QMR 시스템이 xi,j(k)에 도달할 확률이라고 하자. 태스크 실행 성공 확률은 πi,j(k+1)를 이용하여 표현할 수 있기 때문에 각 상태에 대한 확률 πi,j(k+1)를 아래와 같이 먼저 구한다.

(i) 확률 πi,0(k+1) :

πi,0(k+1)는 QMR 시스템이 xi,0(k+1)를 가지는 확률이다. 다시 말하면 QMR 시스템이 i번의 동기화 과정을 거치고 k+1번의 고장 탐지를 수행한 후 상태 xi,0에 도달하는 확률이다(0≤i≤w). 그림 4에서 확인할 수 있듯이 xi,0은 마코프 체인의 첫 번째 열에 위치하며 xi,0에서 첫 번째 태스크 조각 T1이 수행된다. 따라서 QMR 시스템이 xi,0(k+1)를 가지기 위해서는 i번의 동기화와 k번의 고장 탐지가 이미 수행된 이후 T1,...,Tm 중 하나의 태스크 조각을 실행하다가 3개 이상의 프로세서에서 고장이 발생해야 한다. 제안된 고장 극복 알고리듬에 의해 QMR 시스템은 직전 체크포인터로 회귀해야 하는데 T1,...,Tm에 대한 직전 체크포인터는 xi,0에 배치되어 있기 때문이다. 또한 xi,0에서는 T1이 수행되기 때문에 동기화 과정으로는 xi,0에 다시 도달할 수 없다.

i번의 동기화 과정과 k번의 고장 탐지 후 태스크 조각 Th+1를 실행해야 하는 상태는 xi,h(k)이며(0≤h≤m-1), QMR 시스템이 xi,h(k)를 가지는 확률은 앞에서 정의했듯이 πi,h(k)이다. 또한 3개 이상의 프로세서에서 고장이 발생하는 확률은 μ이기 때문에 QMR 시스템은 xi,h(k)에 도달하여 xi,0(k)로 다시 천이할 확률은 μπi,h(k)이다. h=1,...,m-1에 대한 이 확률을 모두 더하면 QMR 시스템이 xi,0(k+1)를 가지는 확률을 구할 수 있다. 따라서 πi,0(k+1)는 다음과 같이 표현된다.

(ii) 확률 πi,vm(k+1) (1≤v≤n-1) :

이번에는 QMR 시스템이 1≤v≤n-1인 xi,vm(k+1)에 도달하는 확률 πi,vm(k+1)를 구해 보자. 상태 xi,vm의 두 번째 인덱스가 m의 배수이기 때문에 v번째 체크포인터가 xi,vm에 삽입되며 태스크 조각 Tvm+1이 수행된다. QMR 시스템이 xi,vm(k+1)에 도달하는 경우는 세 가지이다.

∙ 먼저 xi,vm-1(k)에서 태스크 조각 Tvm을 실행하면서 고장 탐지 과정을 거쳤지만 5개 프로세서에서 고장이 하나도 발생하지 않는 경우이다(확률 α). 고장 탐지 횟수만 1 증가하고 xi,vm-1에서 xi,vm로 천이하기 때문에 QMR 시스템은 xi,vm(k+1)에 도달한다. 이때의 확률은 απi,vm-1(k)로 표현된다.

∙ 다음으로 xi-1,vm-1(k)에서 Tvm을 실행하면서 (k+1)번째 고장 탐지를 한 결과 1~2개의 프로세서에서 고장이 발생하는 경우이다(확률 β). 상태 xi-1,vm-1에 있던 QMR 시스템은 동기화 과정만 한 번 수행한 후 다음 상태 xi,vm로 천이한다(식 (10) 참조). 고장 탐지 횟수가 k+1이 되었기 때문에 QMR 시스템은 xi,vm(k+1)에 도달한다. 이때의 확률은 βπi-1,vm-1(k)로 표현된다.

∙ 마지막으로 i번의 동기화 과정을 거친 후 Tvm+1,...,Tvm+m 중 하나의 태스크 조각 Tvm+h을 수행하면서 (k+1)번째 고장 탐지 과정에서 3개 이상의 프로세서에서 고장이 발생한 것을 인식하는 경우이다(확률 μ). 제안된 알고리듬에 따라 QMR 시스템은 직전 체크포인터가 배치된 상태 xvm으로 회귀하여 Tvm+1부터 재수행하는데 이것은 QMR 시스템이 xi,vm(k+1)에 도달하는 것으로 표현될 수 있다. 해당 확률은 μπi,vm+h(k)이다(0≤h≤m-1).

위의 세 가지 경우의 확률을 모두 더하면 πi,vm(k+1)이 아래와 같이 유도된다(i<0인 경우는 πi,j(k)=0으로 설정한다).

(iii) 확률 πi,nm(k+1) :

마코프 체인 모델의 마지막 열인 j=nm열에 해당하는 상태에 대한 확률 πi,nm(k+1)을 구해 보자. xi,nm(k+1)은 i번의 동기화 과정과 (k+1)번의 고장 탐지 과정 후 QMR 시스템이 상태 xi,nm을 가지는 경우를 나타낸다. QMR 시스템이 xi,nm(k+1)에 도달하는 경우는 앞의 (ii)와 유사하게 다음 세 가지 경우로 나뉜다.

∙ 만약 i번의 동기화 과정과 k번째 고장 탐지 후 모든 태스크 조각의 수행이 끝났다면 (k+1)번째 고장 탐지에서 관측하는 고장 발생 유무와 상관없이 QMR 시스템은 계속 상태 xi,nm에 머무른다. 이 확률은 πi,nm(k)로 표현된다.

∙ 다음으로 그림 4와 식 (9)에서 볼 수 있듯이 상태 xi,nm-1에서 α의 확률로 xi,nm으로 바로 천이하는 경우이다. 다시 말하면 QMR 시스템은 xi,nm-1에서 (k+1)번째 고장 탐지를 수행한 결과(xi,nm-1(k+1)로 표현) 하나도 고장이 발견되지 않았기 때문에 xi,nm으로 천이하며, 이것은 xi,nm(k+1)로 표현된다. 이에 해당하는 확률은 απi,nm-1(k)이다.

∙ 마지막으로 xi-1,nm-1(k)에서 (k+1)번째 고장 탐지 과정에서 1~2개 프로세서에서 고장이 발생했음을 인지하는 경우이다. QMR 시스템은 동기화 과정을 수행하고 상태 xi,nm으로 천이한다. 이 결과 역시 xi,nm(k+1)로 표현되며 이에 해당하는 확률은 βπi-1,nm-1(k)이다

위에서 기술한 세 가지 경우를 합하여 πi,nm(k+1)을 구하면 아래 식과 같다.

(iv) 확률 πi,vm+h(k+1) (1≤v≤n-1, 1≤h≤m-1) :

마지막으로 (i)~(iii)에 해당하지 않는 열 j = vm+h에 대한 확률 πi,vm+h(k+1)을 구해 보자(1≤h≤m-1). 먼저 xi,vm+h-1(k)에 도달한 후 (k+1)번째 고장 탐지 과정에서 고장을 탐지하지 않으면 QMR 시스템은 xi,vm+h(k+1)로 천이한다. 이에 해당하는 확률은 απi,vm+h-1(k)이다. 또한 xi-1,vm+h-1(k)에 도달한 후 (k+1)번째 고장 탐지 과정에서 1~2개 프로세서에서 고장이 발생한 것을 발견하였다면 QMR 시스템은 동기화 과정을 거친 후 xi,vm+h(k+1)에 도달한다. 이 확률은 βπi-1,vm+h-1(k)이다. 앞의 두 경우의 확률을 더하면 πi,vm+h(k+1)은 아래 식과 같다.

식 (13)~(16)을 적용하면 그림 4의 마코프 체인이 임의의 상태에 있을 확률을 구할 수 있다. 이때 고려되어야 할 중요한 조건은 태스크의 수행 시간, 고장 탐지 시간, 동기화 시간을 합한 전체 실행 시간이 데드라인 D를 넘지 않도록 고장 탐지 횟수 k가 제한되어야 한다는 점이다. 태스크의 수행을 D 내에 끝내기 위해서는 기본적으로 nm번의 고장 탐지가 수행되어야 한다. 또 데드라인 이내에 구간 재수행이 가능한 횟수 r(i)는 식 (6)과 같이 동기화 과정 횟수 i에 의존한다.

동기화 과정 횟수가 i일 때 가능한 최대의 고장 탐지 횟수를 ki라고 하자. nm번의 기본 고장 탐지가 수행되어야 하고 구간 재수행을 한 번 실행하면 고장 탐지도 한 번 더 할 수 있기 때문에 아래 식의 관계가 유도된다.

n개의 체크포인터가 동일 간격으로 배치되고 체크포인터 사이에 m번의 고장 탐지가 실행되는 QMR 구조를 가진 실시간 시스템이 데드라인 D 이내에 태스크 실행을 성공시킬 확률을 PD(n,m)이라고 하자. πi,j(k)와 식 (17)에서 구한 ki를 이용하여 PD(n,m)을 유도해보자. 총 i번의 동기화 과정을 거친 후 태스크 수행이 완료되기 위해서는 ki번째 고장 탐지까지 nm개의 태스크 조각이 모두 실행 완료되어야 한다. 이에 해당하는 확률은 정의에 따라서 πi,nm(ki)로 표현된다. 그런데 동기화 횟수 i는 0에서 w까지 변할 수 있기 때문에 PD(n,m)은 (w+1)개의 개별 확률 π0,nm(ki),...,πw,nm(ki)를 모두 더한 값이 된다. 따라서 데드라인 이내에서 태스크의 실행을 성공할 확률 PD(n,m)은 다음과 같이 얻어진다.

QMR 시스템은 초기에 상태 x0,0에 머무르기 때문에 각 상태에서의 초기 확률값은 π0,0(0)=1, πi,j(0)=0이다 (i≠0, j≠0).

4.1 최적 고장 탐지 횟수와 체크포인터 개수 탐색

앞 장에서 구한 마코프 체인 모델과 관련 식을 이용하여 태스크의 성공 확률 PD(n,m)를 모의실험으로 구한다. 이번 연구에서는 특히 고장 탐지 횟수 m과 체크포인터 수 n을 변화시키면서 PD(n,m)의 값을 최대로 하는 최적의 고장 탐지 횟수 m*과 체크포인터 수 n*을 구하는 것을 목표로 한다. 모의실험 과정에서 매개 변수 값은 D=10, Td=0.05, Tc=0.5로 설정하였으며 T, Ts, λ는 각각 T=0.4, 0.6, Ts=0.05, 0.2, λ=0.5, 0.8 중 하나의 값을 가진다고 설정하였다.

그림 5는 T=4로 설정했을 때의 모의실험 결과를 보여준다. 그림 5(a)와 (b)에서 알 수 있듯이 λ=0.5일 때 m*=4이며(그림 5(a)), λ=0.8일 때 m*=5이다(그림 5(b)). 즉 고장 발생률 λ가 증가하면 최적의 고장 탐지 횟수 m* 역시 증가한다. 이것은 고장이 자주 발생할수록 고장 탐지 횟수를 늘려야 한다는 논리적 귀결과 일치하는 결과이다. 한편 그림 5(a)와 (c), 또는 그림 5(b)와 (d)를 서로 비교하면 알 수 있듯이 다른 조건이 동일하다면 상태 동기화 시간 Ts가 증가할수록 최적의 고장 탐지 횟수는 줄어듦을 알 수 있다. 예를 들어 그림 5(a)에서 Ts=0.05일 때 m*=4이지만 그림 5(c)에서 Ts=0.2일 때 m*=3이다. 이것은 고장 발생 후 상태 동기화에 많은 시간이 소요되면 반대급부로 데드라인을 맞추기 위해 고장 탐지 횟수는 줄어든다는 사실을 알려준다.

그림 6은 T=6으로 설정된 모의실험 결과이다. 그림 5와 비교 하여 전체 태스크 시간이 늘어났기 때문에 재수행을 위해 사용할 수 있는 여유 시간은 감소할 수밖에 없으며 모의실험 결과도 이와 부합한다. 특히 그림 6의 (a), (b) 또는 (c)와 (d)를 서로 비교하면 그림 5의 결과와는 다르게 고장 발생률 λ가 증가할수록 최적의 고장 탐지 횟수가 감소함을 알 수 있다. 또한 그림 6의 (a)와 (c), 또는 (b)와 (d)를 서로 비교하면 상태 동기화 시간 Ts가 증가하면 최적의 체크포인터 수 n*와 고장 탐지 횟수 m*가 동시에 줄어듦을 볼 수 있다.

그림 5와 그림 6의 모의실험 결과에서 알 수 있듯이 최적 체크포인터 수와 고장 탐지 횟수는 한두 개의 매개 변수에 따라서 결정되는 것이 아니라 고장 발생률 λ, 동기화 시간 Ts, 태스크 실행 시간 T, 데드라인 D, 그리고 체크포인터에 상태 값을 저장하는 시간 Tc 등과 복합적으로 연관되어 있다. 따라서 이 매개 변수 값들이 주어지면 시뮬레이션을 통해 최적 체크포인터 수와 고장 탐지 횟수를 수치 해석적으로 구해야 한다.

4.2 기존 QMR 시스템과의 비교 모의실험

제안된 QMR 시스템의 고장 탐지 능력의 우수성을 입증하기 위해 기존 QMR 시스템과의 비교 모의실험을 실시한다. 표 1은 체크포인터 기법을 탑재한 기존의 QMR 시스템^[12]과 제안된 QMR 시스템에 대해 동일한 매개 변수 조건 하에서 탐색한 최적 체크포인터 개수 n*와 태스크 실행 성공 확률 ${P}_{{D}}^{*}$을 나타낸다. 기존 QMR 시스템은 체크포인터에 상태를 삽입하기 전 한 번만 고장 탐지를 실행하지만^[12], 제안된 QMR 시스템은 두 개의 체크포인터 사이에 여러 번의 고장 탐지 과정을 실행하는 차이점을 가진다. 표 1에서 설정한 매개 변수 조건은 그림 5와 그림 6의 모의실험 과정에서 설정한 것과 동일하다. 표 1에서 쉽게 알 수 있듯이 동일한 매개 변수 조건 하에서 제안된 QMR 시스템의 태스크 실행 성공 확률 ${P}_{{D}}^{*}$이 기존 QMR 시스템의 확률보다 항상 더 크게 나오며, 태스크 수행 시간 T가 증가할수록 두 시스템의 확률 차이는 더 벌어진다. 예를 들어 T=4, Ts=0.05, λ=0.5일 때는 제안된 QMR 시스템의 태스크 수행 성공 확률은 0.9969, 기존 QMR 시스템의 성공 확률은 0.9539로 제안된 QMR 시스템의 확률이 0.9969/0.9539 = 1.05배 더 크다. 반면 T=6, Ts=0.05, λ=0.5일 때 두 시스템의 태스크 수행 성공 확률은 각각 0.0584와 0.0013로 제안된 QMR 시스템의 확률이 무려 0.0584/0.0013 = 44.92배 더 크게 나왔다. 이러한 비교 실험 결과는 제안된 QMR 시스템이 기존의 시스템보다 고장 탐지 및 극복 면에서 더 좋은 성능을 가짐을 입증한다.