A Study on New Defering Method for Optional Tasks to Improve Schedulability

Song Gi-Hyeon (송기현)

A Study on New Defering Method for Optional Tasks to Improve Schedulability

Journal of Knowledge Information Technology and Systems
Abbr : JKITS
2015, 10(3), pp.337-346
Publisher : Korea Knowledge Information Technology Society
Research Area : Interdisciplinary Studies > Interdisciplinary Research
Published : June 30, 2015

Song Gi-Hyeon ¹

¹대전보건대학교

Accredited

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.

KEYWORDS

Imprecise scheduling, Total error, Higher schedulability, Delay optional tasks, On-line scheduling, DOTMP algorithm

Citation status

* References for papers published after 2023 are currently being built.

[journal] 최환필 / 2011 / An EDF Based Real-Time Scheduling Algorithm for Imprecise Computation / 정보처리학회논문지. 컴퓨터 및 통신시스템 / 한국정보처리학회 18(4) : 143~150

[journal] W. K. Shih / 1996 / On-line scheduling of imprecise computations to minimize error / SIAM Journal on Computing 25(5) : 1105~1121

[confproc] W. K. Shih / 2000 / A fast algorithm for scheduling imprecise computations with timing constraints to minimize weighted error / in Proceedings of the 21st IEEE Real-Time Systems Symposium : 305~310

[journal] 송기현 / 2005 / An On-line Algorithm to Search Minimum Total Error for Imprecise Real-time Tasks with 0/1 Constraint / 멀티미디어학회논문지 / 한국멀티미디어학회 8(12) : 1589~1596

[journal] J. M. Chen / 2009 / Imprecise computations with deferred optional tasks / Journal of Information Science and Engineering 25 : 185~200

[journal] 송기현 / 2015 / A Study on New Defering Method for Optional Tasks to Improve Schedulability / 한국지식정보기술학회 논문지 / 한국지식정보기술학회 10(3) : 337~346

[confproc] J. H. Kim / 1998 / Performance evaluation of on-line scheduling algorithms for imprecise computation / Proceedings Fifth International Conference on Real-Time Computing Systems and Applications

[journal] Gi-Hyeon Song / 2006 / An efficient algorithm to minimize total error of the imprecise real time tasks / Journal of Korea Computer Industry Education Society 7(4) : 309~320

[journal] Gi-Hyeon Song / 2007 / Scheduling Algorithm to Minimize Total Error for Imprecise On-Line Tasks / 멀티미디어학회논문지 / 한국멀티미디어학회 10(12) : 1741~1751

[journal] 송기현 / 2007 / An Improved Online Algorithm to Minimize Total Error of the Imprecise Tasks with 0/1 Constraint / 정보과학회논문지 : 시스템 및 이론 / 한국정보과학회 34(10) : 493~501

KJCKorea
Journal Central

Journal of Knowledge Information Technology and Systems 2023 KCI Impact Factor : 0.89