CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Schedulability Test for Soft Real-Time Systems under Multi-processor Environment by using an Earliest Dead-line First Scheduling Algorithm

by Jagbeer Singh, Ranjit Patnaik, Satyendra P. Singh, Manamohan Sahoo
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 46 - Number 7
Year of Publication: 2012
Authors: Jagbeer Singh, Ranjit Patnaik, Satyendra P. Singh, Manamohan Sahoo
10.5120/6922-9325

Jagbeer Singh, Ranjit Patnaik, Satyendra P. Singh, Manamohan Sahoo . Schedulability Test for Soft Real-Time Systems under Multi-processor Environment by using an Earliest Dead-line First Scheduling Algorithm. International Journal of Computer Applications. 46, 7 ( May 2012), 29-38. DOI=10.5120/6922-9325

@article{ 10.5120/6922-9325,
author = { Jagbeer Singh, Ranjit Patnaik, Satyendra P. Singh, Manamohan Sahoo },
title = { Schedulability Test for Soft Real-Time Systems under Multi-processor Environment by using an Earliest Dead-line First Scheduling Algorithm },
journal = { International Journal of Computer Applications },
issue_date = { May 2012 },
volume = { 46 },
number = { 7 },
month = { May },
year = { 2012 },
issn = { 0975-8887 },
pages = { 29-38 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume46/number7/6922-9325/ },
doi = { 10.5120/6922-9325 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:39:09.928006+05:30
%A Jagbeer Singh
%A Ranjit Patnaik
%A Satyendra P. Singh
%A Manamohan Sahoo
%T Schedulability Test for Soft Real-Time Systems under Multi-processor Environment by using an Earliest Dead-line First Scheduling Algorithm
%J International Journal of Computer Applications
%@ 0975-8887
%V 46
%N 7
%P 29-38
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This paper deals with the study of Earliest Deadline First (EDF) which is an optimal scheduling algorithm for uniprocessor real time systems use for scheduling the periodic task in soft real-time multiprocessor systems. In hard real-time systems, a significant disparity exists. EDF-based schemes and RMA scheduling (which is the only known way of optimally scheduling recurrent real-time tasks on multiprocessors): on M processors, all known EDF variants have utilization-based schedulability bounds of approximately M/2, while RMA algorithms can fully utilize all processors. This is unfortunate because EDF-based algorithms entail lower scheduling and task-migration overheads. In work on hard real-time systems, it has been shown that this disparity in Schedulability can be lessened by placing caps on per-task utilizations. Our main contribution is a new EDF-based scheme that ensures bounded deadline tardiness. In this scheme, per-task utilizations must be focused, but overall utilization need not be restricted. Our scheme should enable a wide range of soft real-time applications to be scheduled with no constraints on total utilization. Also propose techniques and heuristics that can be used to reduce tardiness as well as increase the efficiency of task.

References
  1. T. P. Baker. Multiprocessor EDF and deadline monotonic schedulability analysis. In Proc. of the 24th IEEE Real time Systems Symposium, pages 120{129, Dec. 2003.
  2. S. Baruah and J. Carpenter. Multiprocessor fixed-priority scheduling with restricted inter processor migrations. In Proceedings of the 15th Euromicro Conference on Real-time Systems, pages 195{202. IEEE Computer Society Press, July 2003.
  3. S. Baruah, N. Cohen, C. G. Plaxton, and D. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15:600{625, 1996.
  4. J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Anderson, and S. Baruah. A categorization of real-time multiprocessor scheduling problems and algorithms. In Joseph Y. Leung, editor, Handbook on Scheduling Algorithms, Methods, and Models. Chapman Hall/CRC, 2004 (to appear).
  5. E. D. Jensen, C. D. Locke, and H. Tokuda. A time driven scheduling model for real-time operating systems. In Proc. Of the 6th IEEE Real-time Systems Symposium, pages 112{122, 1985.
  6. C. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 30:46{61, January 1973.
  7. J. Lopez, M. Garcia, J. Diaz, and D. Garcia. Worst-case utilization bound for edf scheduling on real-time multiprocessor systems. In Proceedings of the 12th Euromicro Conference on Real-time Systems, pages 25{33, June 2000.
  8. A. Mok. Fundamental Design Problems of Distributed Systems for Hard Real-time Environments. PhD thesis, Massachusetts Institute of Technology, Cambridge, Mass. , 1983.
  9. L. Sha and J. Goodenough. Real-time scheduling theory and Ada. IEEE Computer, 23(4):53{62, 1990.
  10. F. Zhang and A. Burns, Schedulability Analysis for Real-Time Systems with EDF Scheduling, in Technical Report YCS-426-2008, Dept. of Computer Science, University of York, UK. 2008.
  11. Audsley N. C. , Burns A. , Davis R. I. , Tindell K. W. Fixed Priority pre-emptive scheduling: A historic perspective Real-Time Systems journal, Vol. 8(2/3), March/May, Kluwer A. P. , 1995.
  12. Xu J. and Parnas D. Scheduling process with release times, deadlines, precedence and exclusion, relations. IEEE Trans. on Software Eng. 16(3):360-369, 1990.
  13. S. K. Baruah, A. K. Mok, and L. E. Rosier. Preemptively Scheduling Hard-Real-Time Sporadic Tasks on One Processor. In Proceedings 11th IEEE Real-Time System Symposium, pp. 182-190, 1990.
  14. S. K. Baruah, L. E. Rosier, and R. R. Howell. Algorithms and Complexity Concerning the Preemptive Scheduling of Periodic Real-Time Tasks on One Processor. Journal of Real-Time Systems, 4 (2):301-324, 1990.
  15. S. K. Baruah, R. R. Howell, and L. E. Rosier. Feasibility Problems for Recurring Tasks on One Processor. Theoretical Computer Science, 118 (1):3-20, 1993.
  16. E. Bini and G. C. Buttazzo. Measuring the Performance of Schedulability Tests. Journal of Real-Time Systems, 30 (1-2):129-154, 2005.
  17. G. C. Buttazzo, Real-Time Scheduling and Resource Management, in Handbook of Real-Time and Embedded Systems. 2008, Chapman & Hall/CRC.
  18. M. L. Dertouzos. Control robotics: The Procedural Control of Physical Processes. In 39 Proceedings of the IFIP Congress, pp. 807-813, 1974.
  19. L. George, N. Rivierre, and M. Spuri, Preemptive and non-preemptive Real-Time uniprocessor scheduling, in Technical Report 2966, INRIA, France. 1996.
  20. H. Hoang, G. Buttazzo, M. Jonsson, and S. Karlsson. Computing the Minimum EDF Feasible Deadline in Periodic Systems. In Proceedings 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pp. 125-134, 2006.
  21. J. Y. -T. Leung and M. L. Merrill. A Note on Preemptive Scheduling of Periodic, Real-Time Tasks. Information Processing Letters, pp. 115-118, 1980.
  22. C. L. Liu and J. W. Layland. Scheduling Algorithm for Multiprogramming in a Hard Real-Time Environment. Journal of the ACM, 20 (1):40-61, 1973.
  23. I. Ripoll, A. Crespo, and A. K. Mok. Improvement in Feasibility Testing for Real-Time Tasks. Journal of Real-Time Systems, 11 (1):19-39, 1996.
  24. M. Spuri, Analysis of Deadline Schedule Real-time Systems, in Technical Report 2772, INRIA, France. 1996.
  25. F. Zhang and A. Burns, Schedulability Analysis for Real-Time Systems with EDF Scheduling, in Technical Report YCS-426-2008, Dept. of Computer Science, University of York, UK. 2008.
Index Terms

Computer Science
Information Sciences

Keywords

Multiprocessor Systems Soft Real-time Task Migration Exact Schedulability Test Earliest-deadline-first Scheduling Feasible Earliest-deadline-first

Powered by PhDFocusTM