A Study on New Defering Method for Optional Tasks to Improve Schedulability
1
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
The imprecise computation technique prevents timing faults and achieves graceful degradation by making sure that an approximate result of an acceptable quality is available to the user whenever the exact result of the desired quality cannot be obtained in time. In the imprecise scheduling, NORA 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. But the NORA algorithm has low schedulability problem. Then, DOP algorithm delays the optional parts of the earliest deadline tasks as many as possible but the algorithm is almost similar to SMF(Schedule Mandatory First) algorithm. Next, DMO algorithm showing similar total error and schedulability to DOP algorithm preserving deadline order of tasks is proposed. To improve schedulability of DMO algorithm, this paper proposes a new algorithm which delays the optional parts of the earliest deadline tasks as many as possible. The proposed algorithm showes higher schedulability and similar total error than DMO algorithm.
Abstract
The imprecise computation technique prevents timing faults and achieves graceful degradation by making sure that an approximate result of an acceptable quality is available to the user whenever the exact result of the desired quality cannot be obtained in time. In the imprecise scheduling, NORA 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. But the NORA algorithm has low schedulability problem. Then, DOP algorithm delays the optional parts of the earliest deadline tasks as many as possible but the algorithm is almost similar to SMF(Schedule Mandatory First) algorithm. Next, DMO algorithm showing similar total error and schedulability to DOP algorithm preserving deadline order of tasks is proposed. To improve schedulability of DMO algorithm, this paper proposes a new algorithm which delays the optional parts of the earliest deadline tasks as many as possible. The proposed algorithm showes higher schedulability and similar total error than DMO algorithm.
참고문헌 (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(5), pp.1105~1121 (1996)
- W. K. Shih, "A fast algorithm for scheduling imprecise computations with timing constraints to minimize weighted error", in Proceedings of the 21st IEEE Real-Time Systems Symposium, pp.305~310 (2000)
- 송기현, "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]
- J. M. Chen, "Imprecise computations with deferred optional tasks", Journal of Information Science and Engineering, 25, pp.185~200 (2009)
- 송기현, "A Study on New Defering Method for Optional Tasks to Improve Schedulability", 한국지식정보기술학회 논문지, 10(3), pp.337~346 (2015), 한국지식정보기술학회
- 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)
- Gi-Hyeon Song, "An efficient algorithm to minimize total error of the imprecise real time tasks", Journal of Korea Computer Industry Education Society, 7(4), pp.309~320 (2006)
- 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]