This content is not included in
your SAE MOBILUS subscription, or you are not logged in.
An Efficient Multi-Task Scheduling Methodology for Real-Time System Based on Normalized Slack Time
Technical Paper
2014-01-0232
ISSN: 0148-7191, e-ISSN: 2688-3627
Annotation ability available
Sector:
Language:
English
Abstract
This paper presents a multi-task scheduling algorithm with small circuit size implementation to achieve high-speed performance for real-time system.
Rate Monotonic Scheduling (RMS) is generally used because of its low cost and easy implementation although it is not highly efficient. On the other hand, Least Slack Time Scheduling (LSTS) has high scheduling efficiency, especially in a multi-core system, which is becoming widely used in recent years. However, it is difficult to process in real time by software implementation with LSTS, because the straightforward LSTS implementation has to calculate individual slack time from release time of each task, and compare them to determine the execution priority. Even though LSTS algorithm has already been implemented in hardware, its long circuit delay and the large circuit area still remain to be solved.
Our proposal focuses on the time management that is the dominant part in LSTS process. The proposed method normalizes slack time by using a common timer and determines the execution priority based on ascending order of the time point when slack time runs out. In such cases, time measurement for individual task is no longer needed and operations for task dispatching can be reduced. The proposed algorithm uses less amount of calculation to maintain the same execution priority of tasks as the conventional algorithm.
Consequently, proposed algorithm can reduce the circuit area by 77% and its delay by 88% compared to the conventional approach. Furthermore, the simulation result shows that scheduling efficiency with the proposed algorithm performs very close to the theoretical value.
Recommended Content
Journal Article | An Efficient Path Planning Methodology Based on the Starting Region Selection |
Technical Paper | Mathematical Modeling of Multiple Evaporator/Multiple Condenser LHPs Using EcosimPro |
Authors
Citation
Funazaki, T., Yamamoto, H., Taguchi, S., and Kondo, T., "An Efficient Multi-Task Scheduling Methodology for Real-Time System Based on Normalized Slack Time," SAE Technical Paper 2014-01-0232, 2014, https://doi.org/10.4271/2014-01-0232.Also In
References
- May , D. The XMOS Architecture and XS1 Chips Micro, IEEE 32 6 28 37 2012 10.1109/MM.2012.87
- Hwang , M. , Choi , D. , and Kim , P. Least Slack Time Rate first: an Efficient Scheduling Algorithm for Pervasive Computing Environment J. UCS 17 6 912 925 2011
- Hildebrandt , J. , Golatowski , F. , and Timmermann , D. Scheduling coprocessor for enhanced least-laxity-first scheduling in hard real-time systems Proceedings of the 11th Euromicro Conference on Real-Time Systems 208 215 1999 10.1109/EMRTS.1999.777467
- Min-Allah , N. , Hussain , H. , Khan , S.U. , and Zomaya , A.Y. Power efficient rate monotonic scheduling for multi-core systems J. of Parallel and Distributed Computing 72 1 48 57 2012 10.1016/j.jpdc.2011.07.005
- Goossens , J. , Baruah , S. , and Funk , S. Real-time scheduling on multiprocessor Proceedings of the 10th International Conference on Real-Time System 2002
- Zecena , I. ; Zong Ziliang ; Ge Rong ; Jin Tongdan ; Chen Zizhong ; Qiu Meikang Energy consumption analysis of parallel sorting algorithms running on multicore systems 2012 International Green Computing Conference 1 6 2012 10.1109/IGCC.2012.6322290
- Choi , H. S. , and Yun , H. C. Context Switching and IPC Performance Comparison between uClinux and Linux on the ARM9 based Processor Software Platform Lab, Digital Media R&D Center, Samsung Electronics 2005