Soft Real-Time Fuzzy Task Scheduling for Multiprocessor Systems

Authors: Mahdi Hamzeh, Sied Mehdi Fakhraie, Caro Lucas

Abstract:

All practical real-time scheduling algorithms in multiprocessor systems present a trade-off between their computational complexity and performance. In real-time systems, tasks have to be performed correctly and timely. Finding minimal schedule in multiprocessor systems with real-time constraints is shown to be NP-hard. Although some optimal algorithms have been employed in uni-processor systems, they fail when they are applied in multiprocessor systems. The practical scheduling algorithms in real-time systems have not deterministic response time. Deterministic timing behavior is an important parameter for system robustness analysis. The intrinsic uncertainty in dynamic real-time systems increases the difficulties of scheduling problem. To alleviate these difficulties, we have proposed a fuzzy scheduling approach to arrange real-time periodic and non-periodic tasks in multiprocessor systems. Static and dynamic optimal scheduling algorithms fail with non-critical overload. In contrast, our approach balances task loads of the processors successfully while consider starvation prevention and fairness which cause higher priority tasks have higher running probability. A simulation is conducted to evaluate the performance of the proposed approach. Experimental results have shown that the proposed fuzzy scheduler creates feasible schedules for homogeneous and heterogeneous tasks. It also and considers tasks priorities which cause higher system utilization and lowers deadline miss time. According to the results, it performs very close to optimal schedule of uni-processor systems.

Keywords: Computational complexity, Deadline, Feasible scheduling, Fuzzy scheduling, Priority, Real-time multiprocessor systems, Robustness, System utilization.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1328406

References:

[1] F. Gruian, "Energy-centric scheduling for real-time systems," in Department of Computer Science. Ph.D dissertation: Lund University, 2002, p. 164.
[2] Z. Deng, J. W. Liu, and S. Sun, "Dynamic scheduling of hard realtime applications in open system environment," Tech. Rep., University of Illinois at Urbana-Champaign 1996.
[3] G. Buttazzo and J. A. Stankovic, "RED: robust earliest deadline scheduling," in Proc. 3rd Intl. Workshop Responsive Computing Systems, Lincoln, NH, 1993, pp. 100-111.
[4] S. M. Petters, "Bounding the execution time of real-time tasks on modern processors," in Proc. 7th Intl. Conf. Real-Time Computing Systems and Applications, Cheju Island, 2000, pp. 498-502.
[5] J. Zhu, T. G. Lewis, W. Jackson, and R. L. Wilson, "Scheduling in hard real-time applications," IEEE Softw., vol. 12, pp. 54-63, 1995.
[6] K. Taewoong, S. Heonshik, and C. Naehyuck, "Scheduling algorithm for hard real-time communication in demand priority network," in Proc. 10th Euromicro Workshop Real-Time Systems, Berlin, Germany, 1998, pp. 45-52.
[7] C. L. Liu and J. W. Layland, "Scheduling algorithms for multiprogramming in a hard-real-time environment," J. ACM, vol. 20 pp. 46-61, 1973.
[8] D. Babbar and P. Krueger, "On-line hard real-time scheduling of parallel tasks on partitionable multiprocessors," in Proc. Intl. Conf. Parallel Processing, 1994, pp. 29-38.
[9] W. Lifeng and Y. Haibin, "Research on a soft real-time scheduling algorithm based on hybrid adaptive control architecture," in Proc. American Control Conf, Lisbon, Portugal, 2003, pp. 4022-4027 vol.5.
[10] T. F. Abdelzaher and K. G. Shin, "Comment on a pre-run-time scheduling algorithm for hard real-time systems," IEEE Trans Software Engineering, vol. 23, pp. 599-600, Sep 1997.
[11] K. Ramamritham and J. A. Stankovic, "Dynamic task scheduling in hard real-time distributed systems," IEEE Softw., vol. 1, pp. 65-75, July 1984.
[12] P. A. Laplante, "The certainty of uncertainty in real-time systems," IEEE Instrum. Meas. Mag., vol. 7, pp. 44-50, Dec 2004.
[13] K. Ramamritham and J. A. Stankovic, "Scheduling algorithms and operating systems support for real-time systems," Proc. IEEE, vol. 82, pp. 55-67, Jan 1994.
[14] J. Kreuzinger, A. Schulz, M. Pfeffer, T. Ungerer, U. Brinkschulte, and C. Krakowski, "Real-time scheduling on multithreaded processors," in Proc. 7th Intl. Conf. Real-Time Computing Systems and Applications, Cheju Island, South Korea, 2000, pp. 155-159.
[15] N. D. Thai, "Real-time scheduling in distributed systems," in Proc. Intl. Conf. Parallel Computing in Electrical Engineering, Warsaw, Poland, 2002, pp. 165- 170.
[16] C. Lin and S. A. Brandt, "Efficient soft real-time processing in an integrated system," in Proc. 25th IEEE Real-Time Systems Symp., 2004.
[17] I. E. W. Giering and T. P. Baker, "A tool for the deterministic scheduling of real-time programs implemented as periodic Ada tasks," Ada Lett., vol. XIV, pp. 54-73, 1994.
[18] L. HluchÛ, M. DobruckÛ, and J. Astalos, "Hybrid approach to task allocation in distributed systems," in Proc. 4th Intl. Conf. Parallel Computing Technologies, Yaroslavl, Russia, 1997 pp. 210-215.
[19] G. C. Buttazzo, G. Lipari, M. Caccamo, and L. Abeni, "Elastic scheduling for flexible workload management," IEEE Trans. Comput., vol. 51, pp. 289-302, Mar 2002.
[20] A. S. Tanenbaum, Distributed operating systems: Prentice Hall, 1994.
[21] J. Lee, A. Tiao, and J. Yen, "A fuzzy rule-based approach to real-time scheduling," in Proc. 3rd IEEE Conf. Fuzzy Systems, IEEE World Congress Computational Intelligence, FL, 1994, pp. 1394-1399 vol.2.
[22] M. Silly-Chetto, "Dynamic acceptance of aperiodic tasks with periodic tasks under resource sharing constraints," IEE Proc. Software, vol. 146, pp. 120-127, Apr 1999.
[23] M. Caccamo and G. Buttazzo, "Exploiting skips in periodic tasks for enhancing aperiodic responsiveness," in Proc. 18th IEEE Real-Time Systems Symp., San Francisco, CA, 1997, p. 330.
[24] J. Mario J. Gonzalez, "Deterministic processor scheduling," ACM Comput. Surv., vol. 9, pp. 173-204, 1977.
[25] R. Jiminez-Peris, M. Patino-Martinez, and S. Arevalo, "Deterministic scheduling for transactional multithreaded replicas," in Proc. 19th IEEE Symp. Reliable Distributed Systems, Nurnberg, Germany, 2000, pp. 164-173.
[26] S. Zhiao, E. Jeannot, and J. J. Dongarra, "Robust task scheduling in non-deterministic heterogeneous computing systems," in Proc. IEEE Intl. Conf. Cluster Computing, Barcelona, Spain, 2006, pp. 1-10.
[27] M. Sabeghi, M. Naghibzadeh, and T. Taghavi, "Scheduling nonpreemptive periodic tasks in soft real-time systems using fuzzy inference," in Proc. 9th IEEE Intl. Symp. Object and Component- Oriented Real-Time Distributed Computing, Gyeongju, KOREA, 2006, pp. 27-32.
[28] G. Chen, G. Chen, O. Ozturk, and M. Kandemir, "An adaptive locality-conscious process scheduler for embedded systems," in Proc. 11th IEEE Real-Time and Embedded Technology and Applications Symposium, San Francisco, CA, 2005 pp. 354-364.
[29] S. A. Brandt, S. Banachowski, L. Caixue, and T. Bisson, "Dynamic integrated scheduling of hard real-time, soft real-time, and non-realtime processes," in Proc. 24th IEEE Intl. Real-Time Systems Symposium, Cancun, Mexico, 2003, pp. 396-407.
[30] L. A. Zadeh, "Fuzzy sets versus probability," Proc. IEEE, vol. 68, pp. 421-421, March 1980.
[31] L. A. Zadeh, "Fuzzy logic, neural networks, and soft computing," Commun. ACM, vol. 37, pp. 77-84, March 1994.
[32] W. Pedrycz and F. Gomide, An introduction to fuzzy sets: analysis and design: The MIT Press, 1998.
[33] E. H. Mamdani, "Application of fuzzy algorithms for the control of a dynamic plant," Proc. IEE, vol. 121, pp. 1585-1588, Dec 1974.
[34] T. Takagi and M.Sugeno, "Fuzzy identification of systems and its applications to modeling and control," IEEE Trans. Syst., Man, Cybern., vol. 15, pp. 116-132, 1985.
[35] H. Surmann and A. P. Ungering, "Fuzzy rule-based systems on general-purpose processors," IEEE Micro, vol. 15, pp. 40-48, Aug 1995.
[36] G. Ascia and V. Catania, "A general purpose processor oriented to fuzzy reasoning," in Proc. 10th IEEE International Conf. Fuzzy Systems, Melbourne, Australia, 2001, pp. 352-355.
[37] K. Youngdal and L.-K. Hyung, "An architecture of fuzzy logic controller with parallel defuzzification," in Proc. Biennial Conf. of the North American Fuzzy Information Processing Society, Berkeley, CA, 1996, pp. 497-501.