불확정 계산을 위한 EDF 기반의 실시간 스케줄링 알고리즘
An EDF Based Real-Time Scheduling Algorithm for Imprecise Computation
1
조회
0
다운로드
4
인용
0
참고문헌
키워드
초록
본 논문은 필수 실행 부분과 선택 실행 부분으로 구성된 불확정 태스크(imprecise task) 모델에서 효과적으로 스케줄링 하는 EDF(Earliest Deadline First)기반의 알고리즘을 제안한다. 이러한 태스크 모델은 태스크가 과부하 상태가 되었을 때 처리하는데 유용하게 사용된다. 과부하상황이 발생하면 선택 실행 부분 중 일부를 포기해야 하는데, 제안한 DOP 알고리즘은 이후에 발생할 태스크에 대해서 보다 유연하게 대처 할수 있게 하기 위해서 마감시간이 빠른 태스크의 선택 실행 부분을 제거하고, 마감시간이 늦은 태스크의 선택 실행 부분을 남기는 방법을 사용한다. 시뮬레이션을 통하여 성능을 평가한 결과 DOP는 기존에 연구된 스케줄링 알고리즘들에 비해서 좋은 성능을 보였다.
Abstract
This paper presents an EDF based scheduling algorithm for scheduling imprecise computation model where each task consists of mandatory part and optional part. Imprecise computation is useful to manage overload condition. In overload situation, some optional parts should be removed. The proposed DOP algorithm removes optional parts of earlier deadline tasks to enhance flexibly for newly arriving tasks. A simulation result shows that DOP has better performance than other algorithms.
참고문헌 (11)
- J. Liu, "Algorithms for scheduling imprecise computation", Computer, 24(5) (1991)
- Shih, W.-K., "Fast algorithms for scheduling imprecise computations", proceedings of the Real Time Systems Symposium (1989), IEEE Computer Society Press
- Shih, W.-K., "On-line scheduling of imprecise computations to minimize error", Real-Time Systems Symposium (1992)
- Jai-Hoon Kim, "Performance evaluation of on-line scheduling algorithms for imprecise computation", Real-Time Computing Systems and Applications (1998)
- 조성제, "Efficient real-time scheduling algorithms for multiprocessor systems", IEICE Transactions on Communications, E85-B(12), pp.2859~2867, Oxford University Press
- Giorgio C. Buttazzo, "Hard real-time computing systems, 2nd Ed" (2005), Springer
- C. L. Liu, "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment", Journal of the ACM, 20(1), pp.46~91 (1973)
- Liu, J. W., "Real-Time Systems", pp.70~ (2000), Prentice Hall
- Jia-Ming Chen, "Imprecise Computations with Deferred Optional Tasks", Journal of Information Science and Engineering, 25, pp.185~200 (2009)
- Radhakrishna Naik, "Modified IUF Scheduling Algorithm for the Real Time Systems", ICETET-10,IEEE third International Conference on Emerging Trends in Engineering & Technology, pp.712~716 (2010)
- Damir Poles, "Imprecise Computation Model, Synchronous Periodic Real-time Task Sets and Total Weighted Error", Journal of Computing and Information Technology, 18(4) (2010)