Open Access Open Access  Restricted Access Subscription or Fee Access

A Fuzzy Algorithm for Real-Time Scheduling of Soft Periodic Tasks

M. Sabeghi(1*), M. Naghibzadeh(2)

(1) Department of Computer Engineering, Ferdowsi University of Mashhad, Iran, Islamic Republic of
(2) Department of Computer Engineering, Ferdowsi University of Mashhad, Iran, Islamic Republic of
(*) Corresponding author


DOI: https://doi.org/10.15866/irease.v9i2.9719

Abstract


Many scheduling algorithms have been studied to guarantee the time constraints of real-time processes. Scheduling decision of these algorithms is usually based on parameters which are assumed to be crisp. However, in many circumstances the values of these parameters are vague. The vagueness of parameters suggests that we make use of fuzzy logic to decide in what order the requests should be executed to better utilize the system and as a result reduce the chance of a request being missed. We have proposed a new fuzzy algorithm called highest fuzzy priority first. The performance of this algorithm is compared with the well-known earliest deadline first (EDF) algorithm as well as least laxity first (LLF) algorithm through simulation. The simulations were divided into two parts. Firs, the tasks were considered to be preemptable, and second tasks were assumed to be non-preemptable. Simulation results show that this fuzzy approach outperforms the EDF and LLF. It is concluded that the proposed fuzzy approach is very promising and it has the potential to be considered for future research.
Copyright © 2016 Praise Worthy Prize - All rights reserved.

Keywords


Fuzzy Real Time Scheduling; EDF; LLF; MFDF; MFLF

Full Text:

PDF


References


K. Ramamritham, J. A. Stankovic, Scheduling algorithms and operating systems support for real-time systems, Proceedings of the IEEE, Vol. 82, No. 1, pp. 55--67, January 1994.
http://dx.doi.org/10.1109/5.259426

L. Sha, J. B. Goodenough, Real-Time Scheduling Theory and Ada, IEEE Computer, Vol. 23, No. 4, pp. 53-62 (April 1990).
http://dx.doi.org/10.1109/2.55469

A. S. Tanenbaum, Modern Operating Systems, Second Edition, Prentice-Hall, 2001.

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

M. Naghibzadeh, K. H. Kim, A Modified Version of Rate-Monotonic Scheduling Algorithm and its Efficiency Assessment, Seventh IEEE International Workshop on Object-Oriented Real-Time Dependable Systems (WORDS'02), 2002.
http://dx.doi.org/10.1109/words.2002.1000064

J. Hong, X. Tan, D. Towsley, A Performance Analysis of Minimum Laxity and Earliest Deadline Scheduling in a Real-Time System, IEEE Trans. on Comp., Vol. 38, No. 12, Dec. 1989
http://dx.doi.org/10.1109/12.40851

S.-H. Oh, S. M. Yang, A Modified Least-Laxity-First Scheduling Algorithm for Real-Time Tasks, Fifth International Conference on Real-Time Computing Systems and Applications (RTCSA'98), 1998.
http://dx.doi.org/10.1109/rtcsa.1998.726348

M. Sabeghi, M. Naghibzadeh, T. Taghavi, A Fuzzy Algorithm for Scheduling Soft Periodic Tasks in Preemptive Real-Time Systems, International Joint Conferences on Computer, Information, and Systems Sciences, and Engineering (CISSE), 2005.
http://dx.doi.org/10.1109/ictta.2006.1684635

M. Sabeghi, M. Naghibzadeh, T. Taghavi, A Fuzzy Algorithm for Real-Time Scheduling of Soft Periodic Tasks on Multiprocessor Systems, IADIS International Conference on Applied Computing, February 2006.
http://dx.doi.org/10.1109/ictta.2006.1684635

L. X. Wang, A course in fuzzy systems and control, Prentice Hall, Paperback, Published August 1996.

E. H. Mamdani, S. Assilian, An experiment in linguistic synthesis with a fuzzy logic controller, International Journal of Man-Machine Studies, Vol. 7, No. 1, pp. 1-13, 1975.
http://dx.doi.org/10.1016/s0020-7373(75)80002-2

M. Sugeno, Industrial applications of fuzzy control, Elsevier Science Inc., New York, NY, 1985.

J. S. R. Jang, ANFIS: Adaptive-Network-based Fuzzy Inference Systems, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 23, No. 3, pp. 665-685, May 1993.
http://dx.doi.org/10.1109/21.256541

D. Simon, Training fuzzy systems with the extended Kalman filter, Fuzzy Sets and Systems, Vol. 132, No. 2, 1, pp. 189-199, December 2002.
http://dx.doi.org/10.1016/s0165-0114(01)00241-x

K. Jeffay, D. F. Stanat, C. U. Martel, On non-preemptive scheduling of periodic and sporadic tasks, In Proceedings of the 12th IEEE Symposium on Real-Time Systems, pp129-139, 1991.
http://dx.doi.org/10.1109/real.1991.160366

B. Hamidzadeh, S. Shekhar, Specification and Analysis of Real-time Problem Solvers, IEEE Transactions on Software Engineering, Vol. 19, pages 788-803, 1993.
http://dx.doi.org/10.1109/32.238582

M. Sabeghi, M. Naghibzadeh, Deadline vs. Laxity as a Decision Parameter in Fuzzy Real-Time Scheduling, 2nd IEEE International Conference on Information & Communication Technologies: From Theory to Applications, April 2006.
http://dx.doi.org/10.1109/ictta.2006.1684635


Refbacks

  • There are currently no refbacks.



Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2019 Praise Worthy Prize