The week's pick
Reseach Article
Article:Enhancement in LLF Real-Time dynamic Scheduling Algorithm using conventional RM algorithm
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 31 - Number 6 |
| Year of Publication: 2011 |
| Authors: Prem Sindhi, Ravindra K. Gupta |
10.5120/3826-5312
|
Prem Sindhi, Ravindra K. Gupta . Article:Enhancement in LLF Real-Time dynamic Scheduling Algorithm using conventional RM algorithm. International Journal of Computer Applications. 31, 6 ( October 2011), 6-10. DOI=10.5120/3826-5312
Abstract
To achieve timing requirements in real-time systems scheduling is very crucial. Essentiality of any Real-time system task is decided on the basis of deadline, slack time, or period of its occurrence. Earliest deadline first (EDF), least-laxity-first (LLF) also known as smallest slack time first, and rate-monotonic (RM) are well known algorithms based on deadline, slack time and period respectively. Among this EDF and LLF are dynamic scheduling algorithms as priorities of jobs of periodic task changes dynamically on the basis of deadline and slack time respectively while RM is a static scheduling algorithm as priority of jobs of periodic task is static on the bases of period. All these algorithms performance differs in overloaded and under loaded condition. Dynamic scheduling algorithms perform optimum in under loaded condition but as system become slightly overloaded their performance deteriorate very badly. Whereas static scheduling algorithms do not perform optimally in under loaded condition but performs fairly well in over loaded condition compared to dynamic scheduling algorithm. None of dynamic or static algorithm is best for both under-loaded as well as overloaded condition. Our aim is to combine the advantageous features of both dynamic and static real-time scheduling algorithms together. That is performance of dynamic algorithm in under-loaded condition and performance of static algorithm in over-loaded condition. In this paper we enhanced the LLF dynamic real-time scheduling algorithm with RM static real-time scheduling algorithm. In under-loaded condition scheduler schedules jobs according to LLF whereas in overloaded condition it schedules according to RM.
References
- Liu C. L., Layland L., Scheduling algorithms for multiprogramming in a hard-realtime environment, Journal of ACM, Vol 20(1), pp. 46-61, 1973.
- Ketan Kotecha, Apurva Shah, Adaptive Scheduling Algorithm for real-time operating system, In proceedings of IEEE Congress on Evolutionary Computation (CEC 2008), HongKong, pp. 2109-2112, June 2008.
- Ramamritham K., Stankovik J. A., Scheduling Algorithms and Operating Support for Real-Time Systems, Proc. of the IEEE, Vol 82(1), pp. 55-67, 1994.
- Apurva Shah, Ketan Kotecha, Dipti Shah, Dynamic Scheduling for Real-Time Distributed System using ACO, To Appear in International Journal of Intelligent Computing and Cybernetics, (IJICC).
- Locke C. D., Best Effort Decision Making for Real-Time Scheduling, Ph.D. Thesis, Computer Science Department, Carnegie-Mellon University, USA, 1986.
- Ramamritham K., Stankovik J. A., Shiah P. F., Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems, IEEE Transaction on Parallel and Distributed Systems, Vol 1(2), pp. 184-194, 1990.
- Carpenter J., Funk S. H., Holman P., Srinivasan A., Anderson J., Baruah S., A categorization of real-time multiprocessor scheduling problems and algorithms, In Joseph Y.T Leung, editor, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press LLC, 2003.
- Hermann Kopetz. Real-Time Systems Design Principles for Distributed Embedded Applications Second Edition
- ALBERT M. K., REAL-TIME SYSTEMS Scheduling, Analysis, and Verification, CHENG, University of Houston.
Index Terms
Keywords