Using Fixed Priority Pre-emptive Scheduling in Real-Time Systems

Authors

  • Doina Zmaranda University of Oradea Romania, 410087 Oradea, 1 Universitatii St.
  • Gianina Gabor University of Oradea Romania, 410087 Oradea, 1 Universitatii St.
  • Daniela Elena Popescu University of Oradea Romania, 410087 Oradea, 1 Universitatii St.
  • Codruta Vancea University of Oradea Romania, 410087 Oradea, 1 Universitatii St.
  • Florin Vancea University of Oradea Romania, 410087 Oradea, 1 Universitatii St.

Keywords:

real-time systems, fixed priority preemptive scheduling

Abstract

For real-time applications, task scheduling is a problem of paramount importance. Several scheduling algorithms were proposed in the literature, starting from static scheduling or cyclic executives which provide very deterministic yet inflexible behaviour, to the so called best-effort scheduling, which facilitates maximum run-time flexibility but allows only probabilistic predictions of run-time performance presenting a non-predictable and nondeterministic solution. Between these two extremes lies fixed priority scheduling algorithms, such as Rate Monotonic, that is not so efficient for real-time purposes but exhibits a predictable approach because scheduling is doing offline and guarantees regarding process deadlines could be obtained using appropriate analysis methods. This paper investigates the use of Rate Monotonic algorithm by making adjustments in order to make it more suitable for real-time applications. The factors that motivate the interest for fixed priority scheduling algorithms such Rate Monotonic when doing with real-time systems lies in its associated analysis that could be oriented in two directions: schedulability analysis and analysis of process interactions. The analyzing process is carried out using a previously implemented framework that allows modelling, simulation and schedulability analysis for a set of real-time system tasks, and some of the results obtained are presented.

References

A. Aravind and J. Chelladurai, Activation Adjusted Scheduling Algorithms for Real-Time Systems, Advances in Systems, Computing Sciences and Software Engineering, pp. 425-432, Springer 2006. http://dx.doi.org/10.1007/1-4020-5263-4_66

N. Audsley, On priority assignment in fixed priority scheduling, Fuzzy Control Rules in Convex Optimization, Inf. Process. Lett., 79(1), pp.39-44, 2001. http://dx.doi.org/10.1016/S0020-0190(00)00165-4

N. Audsey, A. Burns, R. Davis, K. Tindell, A. Wellings, Fixed Priority Preemptive Scheduling: An Historical Perspective, Real Time Systems, vol. 8, pp. 173-198, 1995. http://dx.doi.org/10.1007/BF01094342

R.J. Bril, P.J.L. Cuijpers, Analysis of hierarchical fixed-priority pre-emptive scheduling revisited, TU/e CS-Report 06-36, 2006.

G. C. Butazzo, Rate Monotonic vs. EDF: Judgement Day, Real-Time Systems, 2005. http://dx.doi.org/10.1023/B:TIME.0000048932.30002.d9

R.I. Davis, A. Burns, Hierarchical Fixed Priority Pre-Emptive Scheduling, Proceedings of the 26th IEEE Real Time System Symposium, IEEE Computer Society, pp. 389-398,2005. http://dx.doi.org/10.1109/rtss.2005.25

R. Dobrin and G. Fohler, Reducing the Number of Preemptions in Fixed Priority Scheduling, Proceedings of Euromicro Conference on Real Time Systems, pp. 144-152, 2004. http://dx.doi.org/10.1109/emrts.2004.1311016

J. Goossens, Scheduling of Offset Free Systems, Real-Time Systems, 24(2), pp. 239-258, 2003. http://dx.doi.org/10.1023/A:1021782503695

J. Goossens, R. Devillers, The no-optimality fo the monotonic priority assignments for hard real-time systems, Real-Time Systems, 13(2), pp. 107-126, 1997. http://dx.doi.org/10.1023/A:1007980022314

C. Kirch, Principles of Real-Time Programming, EMSOFT02, LNCS 2491, Springer-Verlag Berlin, 2002.

J. Kollar, J. Poruban, P. Vaclavik, Evolutionary Nature of Crosscutting Modularity, Proceedings of the 9th International Conference of Modern Electric Systems, EMES'07, pp. 43 - 48, 2007.

C. L. Liu and J. W. Layland, Scheduling Algorithms for Multiprogramming in a Hard real Time Environment, Journal of the ACM, vol. 20(1), pp. 46-61, 1973. http://dx.doi.org/10.1145/321738.321743

C. L. Liu, Real-Time Systems, Prentice Hall, 2000.

M. Naghibzadeh and K. H. Kim, A modified Version of Rate Monotonic Scheduling Algorithm and its Eficiency Assessment, Proceedings of the Seventh IEEE Internation Workshop on Object Oriented Real Time Dependent Systems, pp. 289-294, 2002. http://dx.doi.org/10.1109/WORDS.2002.1000064

I.Shin, I. Lee, Periodic resource model for compositional real-time guarantees, Proceedings of 24th IEEE Real Time System Symposium, (RTSS), pp.2-13, 2003.

S. Saewong, R. Rajkumar, J.P. Lohoczky, M.H. Klein, Analysis of Hierarchical Fixed- Priority Scheduling, Proceedings of 14th Euromicro Conference on Real Time Systems, (ECRTS), pp. 152-160, 2002.

K. Somasundaram; S. Radhakrishnan, Task Resource Allocation in Grid using Swift Scheduler, International Journal of Computer, Communication and Control, ISSN 1841-9836, EISSN 1841-9844, vol. IV, no.2, pp. 158-166, 2009.

D. Zmaranda, G. Gabor, Tool for Modeling and Simulation of Real-Time Systems Behavior, Proceedings of the 2nd IEEE International Workshop on Soft Computing Applications, SOFA 2007, Gyula, Hungary - Oradea, Romania, ISBN: 978-1-4244-1608-0, pp. 211-215, 2007. http://dx.doi.org/10.1109/SOFA.2007.4318331

D. Zmaranda, C. Rusu and M. Gligor, A Framework for Modeling and Evaluating Timing Behaviour for Real-Time Systems, Proceedings of the International Symposium on Systems Theory - Software Engineering, SINTES vol III, pp. 514-520, ISBN 973-742-148-5, 2005.

C. Gyorodi, R. Gyorodi, M. Dersidan, L. Bandici, Applying a pattern length constraint on the FP-Growth algorithm, Proceedings of the International Workshop on Soft Computing Applications SOFA 2009, IEEE - Computational Intelligent Society, 29 July - 1 August 2009, Szeged-Hungary, Arad - Romania, IEEE Catalog number CFP0928D-PRT, ISBN 987-1-4244- 5054-1, pp. 181-185, 2009 http://dx.doi.org/10.1109/SOFA.2009.5254855

Published

2011-03-01

Issue

Vol. 6 No. 1 (2011): International Journal of Computers Communications & Control (March)

Section

Articles

License

ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.

You are free to:

-Share: copy and redistribute the material in any medium or format;

-Adapt: remix, transform, and build upon the material.

The licensor cannot revoke these freedoms as long as you follow the license terms.

 

DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.