실시간 시스템 설계를 위한 주기 할당 알고리즘 (pp.223-226) = Period Assignment Algorithm for Real - Time System Design

국문 초록 (Abstract)

일반적으로 실시간 시스템의 시간적 특성은 시스템의 입력과 출력의 양단간에 부과되는 양극단 시간 제약으로 기술된다. 양극단 시간 제약은 각 태스크들이 취할 수 있는 주기값의 범위를 결정하는데, 이로부터 각 태스크들의 주기값을 유도할 수 있다. 이 때 주기값의 유도는 주기 조화성과 자원 이용을 고려한 목적 함수를 포함한 비선형 최적화 문제이다.
주기 유도 문제는 광범위한 해공간을 갖는 NP-hard 문제로서, 본 논문에서는 이 문제를 명확하게 정의하고 그 해법을 제시한다. 본 연구에서는 GCD 할당 정리와 출력 태스크에 적용하는 주기 조화성을 통해 선형 수행 시간을 가지는 근사(approximation) 알고리즘을 제안한다. 제시된 알고리즘은 최적해와 비교하여 자원 이용률의 측면에서 항상 1/2배 이상의 성능을 보장한다.

목차 (Table of Contents)

• 요약
• 1. 서론
• 2. 주기 할당 문제의 정의
• 3. 주기 할당 알고리즘
• 4. 알고리즘의 성능 분석
• 5. 결론
• 6. 관련 연구