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

Doina Zmaranda, Gianina Gabor, Daniela Elena Popescu, Codruta Vancea, Florin Vancea

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.

Keywords


real-time systems, fixed priority preemptive scheduling

Full Text:

PDF

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




DOI: https://doi.org/10.15837/ijccc.2011.1.2213



Copyright (c) 2017 Doina Zmaranda, Gianina Gabor, Daniela Elena Popescu, Codruta Vancea, Florin Vancea

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

CC-BY-NC  License for Website User

Articles published in IJCCC user license are protected by copyright.

Users can access, download, copy, translate the IJCCC articles for non-commercial purposes provided that users, but cannot redistribute, display or adapt:

  • Cite the article using an appropriate bibliographic citation: author(s), article title, journal, volume, issue, page numbers, year of publication, DOI, and the link to the definitive published version on IJCCC website;
  • Maintain the integrity of the IJCCC article;
  • Retain the copyright notices and links to these terms and conditions so it is clear to other users what can and what cannot be done with the  article;
  • Ensure that, for any content in the IJCCC article that is identified as belonging to a third party, any re-use complies with the copyright policies of that third party;
  • Any translations must prominently display the statement: "This is an unofficial translation of an article that appeared in IJCCC. Agora University  has not endorsed this translation."

This is a non commercial license where the use of published articles for commercial purposes is forbiden. 

Commercial purposes include: 

  • Copying or downloading IJCCC articles, or linking to such postings, for further redistribution, sale or licensing, for a fee;
  • Copying, downloading or posting by a site or service that incorporates advertising with such content;
  • The inclusion or incorporation of article content in other works or services (other than normal quotations with an appropriate citation) that is then available for sale or licensing, for a fee;
  • Use of IJCCC articles or article content (other than normal quotations with appropriate citation) by for-profit organizations for promotional purposes, whether for a fee or otherwise;
  • Use for the purposes of monetary reward by means of sale, resale, license, loan, transfer or other form of commercial exploitation;

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

[End of CC-BY-NC  License for Website User]


INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL (IJCCC), With Emphasis on the Integration of Three Technologies (C & C & C),  ISSN 1841-9836.

IJCCC was founded in 2006,  at Agora University, by  Ioan DZITAC (Editor-in-Chief),  Florin Gheorghe FILIP (Editor-in-Chief), and  Misu-Jan MANOLESCU (Managing Editor).

Ethics: This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE).

Ioan  DZITAC (Editor-in-Chief) at COPE European Seminar, Bruxelles, 2015:

IJCCC is covered/indexed/abstracted in Science Citation Index Expanded (since vol.1(S),  2006); JCR2018: IF=1.585..

IJCCC is indexed in Scopus from 2008 (CiteScore2018 = 1.56):

Nomination by Elsevier for Journal Excellence Award Romania 2015 (SNIP2014 = 1.029): Elsevier/ Scopus

IJCCC was nominated by Elsevier for Journal Excellence Award - "Scopus Awards Romania 2015" (SNIP2014 = 1.029).

IJCCC is in Top 3 of 157 Romanian journals indexed by Scopus (in all fields) and No.1 in Computer Science field by Elsevier/ Scopus.

 

 Impact Factor in JCR2018 (Clarivate Analytics/SCI Expanded/ISI Web of Science): IF=1.585 (Q3). Scopus: CiteScore2018=1.56 (Q2);

SCImago Journal & Country Rank

Editors-in-Chief: Ioan DZITAC & Florin Gheorghe FILIP.