부정확 온라인 스케쥴링에서 선택적 태스크들의 지연정도에 따른 효과
The Effect on Defering Degree of The Optional Tasks in The Imprecise On-Line Scheduling
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
부정확 계산들을 지원하는 시스템에 있어서, 모든 시간에 극한적인 태스크는 필수적 서브태스크와 선택적 서브태스크로 논리적으로 분할될 수 있다. 이러한 부정확 계산들에 있어서, 필수적 서브태스크들의 스케쥴가능성을 향상시키며 선택적 서브태스크들의 총오류를 감소시키는 온라인 스케쥴링 문제들이 최근에 제안되어 왔다. NORA(No Off-line tasks and on-line tasks Ready upon Arrival) 알고리즘은 도착과 동시에 실행준비가 되는 온라인 태스크들로만 구성되는 태스크 시스템에서 최소의 총오류를 산출하는 스케쥴을 발견할 수 있다. DOT(Deferred Optional Tasks)와 DOP(Deferable Optional Part) 알고리즘은 총오류를 최소로 유지하면서 만기가 빠른 선택적 태스크들을 지연시킨다. 그러나, 이 알고리즘들은 단지 선점형 온라인 부정확 태스크들을 스케쥴링하기 위하여 설계 되었으며 비선점형 태스크의 스케쥴링들에는 적용될 수 없었다. 그래서, DOTMD(Delay Optional Tasks Meeting its Deadine)와 DOTMP(Delay Optional Tasks as Many as Possible) 알고리즘들이 선택적 서브태스크들을 지연시켜 비선점형 부정확 온라인 태스크들의 스케쥴가능성을 향상시키기 위하여 제안되었다. 그러나 지금까지, 이러한 선택적 서브태스크들의 지연 정도가 스케쥴가능성과 총오류에 미치는 영향이 구체적으로 알려지지 않았다. 그래서, 본 논문에서는 선점형 뿐만 아니라 비선점형 선택적 서브태스크들에서의 지연 정도가 스케쥴가능성과 총오류에 미치는 영향들을 실험을 통하여 각 각 분석하고 비교하였다.
Abstract
In a system that supports imprecise computations, every time-critical task is structured in such a way that it can be logically decomposed into two subtasks: a mandatory subtask and an optional subtask. In the imprecise computations, the on-line scheduling problems not only to improve schedulability for the mandatory subtasks but to minimize total error for the optional subtasks have been proposed recently. The NORA(No Off-line tasks and on-line tasks Ready upon Arrival) algorithm can find a schedule with the minimum total error for a task system consisting solely of on-line tasks that are ready upon arrival. To improve the schedulability of the NORA algorithm, The DOT(Deferred Optional Tasks) and the DOP(Deferable Optional Part) algorithms delay the optional subtasks of the earliest deadline tasks keeping the total error minimized. However, the algorithms were designed only for preemtable on-line imprecise tasks and couldn’t be applied for nonpreemtable tasks. So, the DOTMD(Delay Optional Tasks Meeting its Deadine) and the DOTMP(Delay Optional Tasks as Many as Possible) algorithms are proposed for scheduling the nonpreemtable imprecise on-line tasks to improve the schedulability by defering the optional subtasks also. But, the effects of the defering degree for the optional subtasks on the schedulability and the total error haven’t been known yet specifically until now. Therefore, in this paper, the effects of the defering degree not only for the preemtable but for the nonpreemtable optional subtasks on the schedulability and the total error are analyzed and compared respectively by simulation study.
참고문헌 (15)
- S. K. Baruah, "Competitive on-line scheduling of imprecise computations", IEEE Transactions on Computers, 47, pp.1027~1032 (1998)
- J. Y. Chung, "Scheduling imprecise computations to minimize total error", Microprocessing and Microprogramming, 27, pp.767~774 (1989)
- J. W. S. Liu, "Imprecise computations", IEEE Special Issue on Real-Time Systems, pp.83~94 (1994)
- W. K. Shih, "A fast algorithm for scheduling imprecise computations with timing constraints to minimize weighted error", Proceedings of the 21 st IEEE Real-Time Systems Symposium, pp.305~310 (2000)
- W. K. Shih, "Algorithms for scheduling imprecise computations with timing constraints to minimize maximum error", IEEE Transactions on Computers, 44, pp.466~471 (1995)
- W. K. Shih, "Fast algorithms for scheduling imprecise computaions", SIAM Journal on Computing, 20, pp.537~552 (1991)
- W. K. Shih, "On-line algorithms for scheduling imprecise computations", SIAM Journal on Computing, 25(5), pp.1105~1121 (1996)
- J. M. Chen, "Imprecise computations with deferred optional tasks", Journal of Information Science and Engineering, 25, pp.185~200 (2009)
- 최환필, "불확정 계산을 위한 EDF 기반의 실시간 스케줄링 알고리즘", 정보처리학회논문지. 컴퓨터 및 통신시스템, 18(4), pp.143~150 (2011), 한국정보처리학회
- 송기현, "비정밀 실시간 스케쥴링에서 선택적 태스크들의 지연 방법에 관한 연구", 한국지식정보기술학회 논문지, 9(1), pp.95~104 (2014), 한국지식정보기술학회
- 송기현, "A Study on New Defering Method for Optional Tasks to Improve Schedulability", 한국지식정보기술학회 논문지, 10(3), pp.337~346 (2015), 한국지식정보기술학회
- 송기현, "An On-line Algorithm to Search Minimum Total Error for Imprecise Real-time Tasks with 0", 1 Constraint, 2005, pp.8(12), 1589~1596[DOI]
- G. H. Song, "An efficient algorithm to minimize total error of the imprecise real time tasks with 0", 1 constraint, 2006, pp.7(4), 309~320
- Gi-Hyeon Song, "Scheduling Algorithm to Minimize Total Error for Imprecise On-Line Tasks", 멀티미디어학회논문지, 10(12), pp.1741~1751 (2007), 한국멀티미디어학회
- 송기현, "0", 1 제약조건을 갖는 부정확한 태스크들의 총오류를 최소화시키기 위한 개선된 온라인 알고리즘, 2007, pp.34(10), 493~501[DOI]