비정밀 실시간 스케쥴링에서 선택적 태스크들의 지연 방법에 관한 연구
A Study on The Deffering Method of The Optional Tasks in The Imprecise Real-Time Scheduling
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
비정밀 계산 기법은 모든 긴급한 태스크들이 그 태스크들의 계산시간 요구조건들과 그 결과들의 질을 서로 상호 보완함으로서 그들의 만기들 이전에 그들의 결과들을 산출하는 것을 보장한다. NORA 알고리즘은 비정밀 온라인 실시간 태스크 집합에서 최소의 총 오류를 산출하지만 만기가 빠른 태스크의 선택실행부분이 만기가 늦은 태스크의 필수실행부분보다 먼저 실행됨으로서 모든 태스크들의 필수실행부분들에 대한 스케쥴가능성이 낮아지는 문제가 발생한다. 이 문제를 개선하기 위하여 만기가 빠른 태스크들의 선택실행부분들을 지연시키는 DOP 알고리즘이 제안되었지만 이는 기존의 SMF 알고리즘과 차이가 없어 보인다. 그래서 본 논문은 만기가 빠른 태스크들의 선택실행부분들을 지연시키는 새로운 방법을 제안하고 기존의 NORA 및 EDF, DOP(SMF) 방법과 스케쥴가능성과 총 오류 면에서 비교 분석하여 본 알고리즘의 우수성을 나타내고자 한다.
Abstract
The imprecise computation technique ensures that all time-critical tasks produce their results before their deadlines by trading off the quality of the results for the computation time requirements of the tasks. The NORA algorithm produces minimum total error but has low schedulability problem by prior executing the optional parts of the earliest deadline tasks than the mandatory parts of the latest deadline tasks. To improve this problem, the DOP algorithm which delays the optional parts of the earliest deadline tasks but this algorithm seems to be almost similier with the previous famous SMF(Schedule Mandatory First) algorithm. Therefore, this paper proposes a new method which delays the optional parts of the earliest deadline tasks and demonstrates several superior advantages by comparing and analyzing in the aspects of the schedulability and total error with previous the NORA, DOP(SMF) algorithms.
참고문헌 (10)
- 최환필, "불확정 계산을 위한 EDF 기반의 실시간 스케줄링 알고리즘", 정보처리학회논문지. 컴퓨터 및 통신시스템, 18(4), pp.143~150 (2011), 한국정보처리학회
- W. K. Shih, "On-line scheduling of imprecise computations to minimize error", SIAM Journal on Computing, 25, pp.1105~1121 (1996)
- W. K. Shih, "A fast algorithm for scheduling imprecise computations with timing constraints to minimize weighted error", Proceedings of the 21st IEEE Real-Time Systems Symposium, pp.305~310 (2000)
- W. K. Shih, "Fast algorithms for scheduling imprecise computations", SIAM Journal on Computing, 20, pp.537~552 (1991)
- J. M. Chen, "Imprecise computations with deferred optional tasks", Journal of Information Science and Engineering, 25, pp.185~200 (2009)
- "Hard Real-Time Computing Systems"[URL]
- J. W. S. Liu, "Algorithms for scheduling imprecise computations", Comput. Magazine, 24, pp.58~68 (1991)
- J. H. Kim, "Performance evaluation of on-line scheduling algorithms for imprecise computation", Proceedings Fifth International Conference on Real-Time Computing Systems and Applications (1998)
- J. W. S. Liu, "Imprecise computations", Proceedings of The IEEE, 82(1), pp.83~94 (1994)