Online Adaptive Fault Tolerant based Feedback Control Scheduling Algorithm for Multiprocessor Embedded Systems

기술 요약: 멀티프로세서 임베디드 시스템을 위한 온라인 적응형 결함 허용 기반 피드백 제어 스케줄링 알고리즘

문제 정의
본 논문은 개방적이고 예측 불가능한 환경에서 작동하는 멀티프로세서 임베디드 시스템의 제어-스케줄링 공동 설계(control-scheduling co-design)에 내재된 과제를 다룹니다. Rate Monotonic (RM) 및 Early Deadline First (EDF)와 같은 전통적인 스케줄링 알고리즘은 작업 매핑과 최악 실행 시간(WCET)이 사전에 정의된 개루프(open-loop) 가정을 기반으로 합니다. 그러나 실제 시나리오에서는 환경적 불확실성으로 인해 안전 필수(Safety Critical, SC) 작업 및 비-SC 작업 모두의 실행 시간이 변동하며, 이는 잠재적인 데드라인 미달 및 자원 과소 또는 과다 활용을 초e로 초래합니다. 기존의 피드백 제어 스케줄링 알고리즘(FCSA)은 동적인 부하 변동 하에서 최적의 솔루션을 제공하지 못하는 경우가 많으며, 현재의 결함 허용(Fault Tolerance, FT) 설계는 시스템 결함을 고려하지 않은 고정된 매핑을 가정하여 관심 영역을 분리해 놓는 경우가 많습니다. 저자들은 멀티프로세서 시스템에서 서비스 품질(QoS)과 데드라인 준수를 보장하기 위해 온라인 적응, 결함 허용, 그리고 피드백 제어를 통합하는 통합된 접근 방식에 대한 문헌상의 공백을 확인했습니다.

방법론
제안된 방법론은 분산 공유 하드웨어 플랫폼을 위해 설계된 온라인 적응형 결함 허용 피드백 제어 스케줄링 알고리즘을 도입합니다. 시스템 아키텍처는 멀티프로세서 노드로 구성되며, 각 노드는 SC 작업 전용 코어 하나와 비-SC 작업 전용 코어 하나, 총 두 개의 코어를 포함합니다. 스케줄링 알고리즘은 고정 우선순위 선점(fixed-priority pre-emption) 방식을 사용하는 실시간 운영체제(RTOS) 상에서 동작합니다.

방법론의 핵심은 다음과 같은 구성 요소를 갖춘 폐루프 제어 시스템입니다:

1. 시스템 모델: 멀티프로서 시스템을 비선형 다중 입력 다중 출력(MIMO) 시스템으로 모델링합니다. 제어 입력은 작업 주기(샘플링 속도)이며, 출력 변수는 측정된 CPU 활용률입니다.
2. 제어기 설계: 저자들은 다음의 두 가지 주요 요소로 구성된 온라인 적응형 제어기를 채택합니다:
   • 재귀 최소 제곱법(Recursive Least Squares, RLS) 모델 추정기: 이 구성 요소는 지수 망각 계수(exponential forgetting factor)를 사용하여 시스템 모델의 시변 파라미터를 온라인으로 식별합니다. 이는 변화하는 런타임 조건과 실행 시간 편차에 적응하기 위해 모델 계수를 업데이트합니다.
   • 선형 이차(Linear Quadratic, LQ) 최적 제어기: 이 제어기는 참조 명령(목표 CPU 활용률)을 추적하는 동시에 제어 입력의 큰 변화에 페널티를 부여하여 이차 비용 함수를 최소화합니다. 비용 함수는 추적 정확도와 제어 조정의 크기 사이의 균형을 맞춥니다.
3. 결함 허용 통합: 본 설계는 (배경에서 언급된 능동 복제, 재실행 또는 체크포인팅 개념과 같은) 결함 허용 메커니즘을 통합하여, 결함이 존재하는 상황에서도 SC 작업이 데드라인을 충족하도록 보장합니다. 제어기는 결함에도 불구하고 CPU 활용률을 스케줄링 가능한 범위 내로 유지하는 것을 목표로 합니다.

주요 기여

• 새로운 통합: 본 논문은 온라인 적응, 결함 허용, 그리고 피드백 제어 스케줄링을 멀티프로세서 임베디드 시스템에 특화하여 통합하는 방법론을 제시하며, 이 맥락에서 이 세 가지 요소를 함께 다룬 첫 번째 연구라고 주장합니다.
• 적응형 메커니즘: 정적 또는 비적응형 FCSA 설계와 달리, 제안된 알고리즘은 RLS 기반 추정기를 사용하여 시스템 모델을 동적으로 업데이트함으로써, 실제 작업 실행 시간에 대한 사전 지식 없이도 동적인 부하 변동과 실행 시간 변화를 처리할 수 있습니다.
• 강건한 제어 전략: LQ 제어기의 사용은 시스템을 원하는 활용률 설정값(set point)에 유지함으로써 CPU 성능과 자원 활용을 최적화하고, 과부하를 방지하며 데드라인 미달 비율을 최소화합니다.

실험 결과
저자들은 CPU 활용률 제어에 초점을 맞춘 세 가지 실험을 통해 방법론을 검증했습니다:

1. 과소 활용 시나리오: 실제 실행 시간이 추정치의 30%인 상태(과소 활용)에서, 제어기는 작업 속도를 높여 두 프로세서의 CPU 활용률을 목표치인 0.8123으로 수렴시켰습니다.
2. 과다 활용 시나리오: 실제 실행 시간이 추정치의 7배인 경우(심각한 과다 활용)에도, 제어기는 작업 속도를 낮추었습니다. 모델 추정 부정확성으로 인한 초기 진동에도 불구하고, 시스템은 빠르게 0.8123 설정값으로 수렴했습니다.
3. 동적 부하에 대한 강건성: 시스템에 특정 간격(300, 400, 800 샘플 단계)으로 동적 워크로드 변화를 가했습니다. 온라인 적응형 제어기는 최소한의 진동과 함께 활용률을 설정값으로 유지하며, 갑작스러운 부하 변동에 대한 강건성을 입증했습니다.

결과는 실제 실행 시간이 추정치보다 현저히 높더라도(최대 7배까지) 작업이 데드라인을 준수하는 한 시스템이 안정적으로 유지됨을 보여줍니다. 그러나 저자들은 실행 시간이 이 임계값을 초과할 경우 시스템이 불안정해져 진동과 데드라인 미달이 발생한다고 언급했습니다.

의의 및 주장
본 논문은 제안된 방법론이 CPU 성능 및 자원 활용 측면에서 QoS를 제공함으로써, 멀티프로세서 임베디드 시스템을 위한 제어-스케줄링 공동 설계에 있어 우수한 접근 방식을 제공한다고 주장합니다. 그 의의는 결함 및 동적 부하 변화가 존재하는 상황에서도 시스템 안정성을 유지하고 SC 작업을 위한 데드라인을 충족할 수 있는 능력에 있습니다. 이는 전통적인 개루프 또는 비적응형 피드백 방식이 달성하기 어려운 부분입니다.

저자들은 제안된 시스템이 개선된 안정성과 자원 사용량을 보여주지만, 이러한 피드백 스케줄링 기반 제어 시스템의 실제 구현은 여전히 "거의 완전히 열려 있는 문제"라고 결론지었습니다. 이들은 향후 연구가 더욱 발전된 CPU 활용 모델과 하이브리드 온라인 제어기를 개발하여 전체적인 시스템 성능을 더욱 향상시키는 데 집중될 수 있다고 제안합니다. 본 논문은 모든 실시간 스케줄링 문제를 해결한다고 주장하는 것이 아니라, 현대적 임베디드 환경의 불확실성을 처리하기 위한 중요한 진전으로서 이 적응형 결함 허용 접근 방식을 위치시키고 있습니다.