부정확 온라인 스케쥴링에서 선택적 태스크들의 지연정도에 따른 효과 (The Effect on Defering Degree of The Optional Tasks in The Imprecise On-Line Scheduling)

서지정보

· 발행기관 : 한국지식정보기술학회
· 수록지 정보 : 한국지식정보기술학회 논문지 / 12권 / 2호 / 267 ~ 275페이지
· 저자명 : 송기현

초록

부정확 계산들을 지원하는 시스템에 있어서, 모든 시간에 극한적인 태스크는 필수적 서브태스크와 선택적 서브태스크로 논리적으로 분할될 수 있다. 이러한 부정확 계산들에 있어서, 필수적 서브태스크들의 스케쥴가능성을 향상시키며 선택적 서브태스크들의 총오류를 감소시키는 온라인 스케쥴링 문제들이 최근에 제안되어 왔다. 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) 알고리즘들이 선택적 서브태스크들을 지연시켜 비선점형 부정확 온라인 태스크들의 스케쥴가능성을 향상시키기 위하여 제안되었다. 그러나 지금까지, 이러한 선택적 서브태스크들의 지연 정도가 스케쥴가능성과 총오류에 미치는 영향이 구체적으로 알려지지 않았다. 그래서, 본 논문에서는 선점형 뿐만 아니라 비선점형 선택적 서브태스크들에서의 지연 정도가 스케쥴가능성과 총오류에 미치는 영향들을 실험을 통하여 각 각 분석하고 비교하였다.

영어초록

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.

참고자료

· 없음