A WEAKLY HARD SCHEDULING APPROACH OF PARTITIONED SCHEDULING ON MULTIPROCESSOR SYSTEMS

Habibah Ismail, Dayang N. A. Jawawi

Abstract


Real-time systems or tasks can be classified into three categories, based on the “seriousness” of deadline misses – hard, soft and weakly hard real-time tasks. The consequences of a deadline miss of a hard real-time task can be prohibitively expensive because all the tasks must meet their deadlines whereas soft real-time tasks tolerate “some” deadline misses. Meanwhile, in a weakly hard real-time task, the distribution of its met and missed deadlines is stated and specified precisely.  As real-time application systems increasingly come to be implemented upon multiprocessor environments, thus, this study applies multiprocessor scheduling approach for verification of weakly hard real-time tasks and to guaranteeing the timing requirements of the tasks. In fact, within the multiprocessor, the task allocation problem seem even harder than in uniprocessor case; thus, in order to cater that problem, the sufficient and efficient scheduling algorithm supported by accurate schedulability analysis technique is present to provide weakly hard real-time guarantees. In this paper, a weakly hard scheduling approach has been proposed and schedulability analysis of proposed approach consists of the partitioned multiprocessor scheduling techniques with solutions for the bin-packing problem, called R-BOUND-MP-NFRNS (R-BOUND-MP with next-fit-ring noscaling) combining with the exact analysis, named hyperperiod analysis and deadline models; weakly hard constraints and µ-pattern under static priority scheduling. Then, Matlab simulation tool is used in order to validate the result of analysis. From the evaluation results, it can be proven that the proposed approach outperforms the existing approaches in terms of satisfaction of the tasks deadlines. 


Keywords


Weakly hard real-time tasks, partitioned scheduling, multiprocessor systems, hyperperiod analysis, deadlines models

Full Text:

PDF

References


Klein. M. H. 1993. A Practitioner’s Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time System. Boston: Kluwer Academic Publisher.

Bernat, G. and Burns, A. 2001. Weakly Hard Real-Time Systems. IEEE Transactions on Computers. 50(4): 308-321.

Carpenter, J., Funk, S., Holman, P., Srinivasan, A., Anderson, J. and Baruah, S. 2004. A Categorization of Real-Time Multiprocessor Scheduling Problems and Algorithms. Handbook on Scheduling Algorithms, Methods and Models. Chapman Hall. CRC. 30.1-30.19.

Wu, T. and Jin, S. 2008. Weakly Hard Real-Time Scheduling Algorithm for Multimedia Embedded System on Multiprocessor Platform. 1st IEEE International Conference on Ubi-Media Computing. Lanzhou. 320-325. August.

Hamdaoui, M. and Ramanathan, P. 1995. A Dynamic Priority Assignment Technique for Streams with (m,k)-firm Deadlines. IEEE Transactions on Computers. 44(12): 1443-1451.

Kong, Y. and Cho, H. 2011. Guaranteed Scheduling for (m,k)-firm Deadlines-Constrained Real-Time Tasks on Multiprocessors. 12th International Conference on Parallel and Distributed Computing, Applications and Technologies. 18-23.

Kong, Y. and Cho, H. 2012. Energy-Constrained Scheduling for Weakly Hard Real-Time Tasks on Multiprocessors. Computer Science and Convergence. Lecture Notes in Electrical Engineering. 114: 335-347.

Oh, D. I. and Baker, T. P. 1998. Utilization Bounds for N-Processor Rate Monotonic Scheduling with Stable Processor Assignment. Real-Time Systems. 15: 183-193.

Andersson, B. and Jonsson, J. 2003. The Utilization Bounds of Partitioned and Pfair Static Priority Scheduling on Multiprocessors are 50%. In Proceedings of the 15th Euromicro Conference on Real-Time Systems. 33-40. July.

Lauzac, S., Melhem, R. and Mosse, D. 1998. An Efficient RMS Admission Control and its Application to Multiprocessor Scheduling. In Proc. of the IEEE Int’l Parallel Processing Symposium. Orlando: Florida. 511-518. March.

Anderson, B. 2003. Static-Priority Scheduling on Multiprocessors. PhD Thesis, Department of Computer Engineering. Chalmers University of Technology. Göteberg: Sweden.

AlEnawy, T. A. and Aydin, H. 2005. Energy-Aware Task Allocation for Rate Monotonic Scheduling. 11th IEEE Real-Time and Embedded Technology and Application Symposium. 213-223. March.

Fisher, N., Baruah, S. and Baker, T. P. 2006. The Partitioned Scheduling of Sporadic Tasks According to Static Priorities. 18th IEEE Euromicro Conference on Real-Time Systems. 127-137.

Niemeier, M., Wiese, A. and Baruah, A. 2011. Partitioned Real-Time Scheduling on Heterogeneous Shared-Memory Multiprocessors. 23rd Euromicro Conference on Real-Time Systems. 5-8 July. 115-124.

Chishiro, H. and Yamasaki, N. 2012. Experimental Evaluation of Global and Partitioned Semi-Fixed-Priority Scheduling Algorithms on Multicore Systems. 15th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing. 11-13 April.

Fan, M., Han, Q., Quan, G. and Ren, S. 2014. Multi-Core Partitioned Scheduling for Fixed-Priority Periodic Real-Time Tasks with Enhanced Rbound. 15th IEEE Int’l Symposium on Quality Electronic Design. 284-289.

Lopez, J. M., Garcia, M., Diaz, J. L. and Garcia, D. F. 2004. Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems. Real-Time Systems. 28(1). October.

Muller, D. and Werner, M. 2011. Towards Exact Thresholds for Scheduling n Tasks on m Processors Based on Partitioned EDF. 17th IEEE Real-Time and Embedded Technology and Applications Symposium.

Baruah, S. 2011. The Partitioned EDF Scheduling of Sporadic Task Systems. 32nd IEEE Real-Time Systems Symposium. 116-125. Vienna.

Coffman, E. G., Galambos, G., Martello, S. and Vigo, D. 1998. Bin-Packing Approximation Algorithms: Combinational Analysis. Kluwer Academic Publishers. Ed. D. Z. Du and P. M. Pardalos.

Liu, C. L. and Layland, J. W. 1993. Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment. Journal of the ACM. 20(1): 46-61.

Bernat, G. and Burns, A. 2001. Weakly Hard Real-Time Systems. IEEE Transactions on Computers. 50(4): 308-321. April.

Borger, M. W. 1987. VAXELN Experimentation: Programming a Real-Time Periodic Task Dispatcher Using VAXELN Ada 1.1. Technical Report. CMU/SEI-87-TR-032 ESD-TR-87-195. November.

Shin, D., Kim, J. and Lee, S. 2001. Intra-Task Voltage Scheduling for Low-Energy Hard Real-Time Applications. IEEE Design and Test of Computers. 18(2): 20-30.

Lee, L-T., Tseng, C-Y. and Hsu, S-J. 2007. An Adaptive Scheduler for Embedded Multiprocessor Real-Time Systems. IEEE Region 10 Conference (TENCON’07). 1-6, Taipei.

Immonen, A. and Niemelä, E. 2008. Survey of Reliability and Availability Prediction Methods from the Viewpoint of Software Architecture. Software and Systems Modeling. 7(1): 49-65.

Kheong, L. S. and Jayaratna, N. 2009. Framework for Structuring Learning in Problem-Based Learning. Retrieved Feb 11, 2011, from http://pbl.tp.edu.sg/Understanding%20PBL/Articles/lyejayarartna.pdf.




DOI: https://doi.org/10.11113/jt.v77.6204

Refbacks

  • There are currently no refbacks.


  

Copyright © 2012 Penerbit UTM Press, Universiti Teknologi Malaysia.
Disclaimer : This website has been updated to the best of our knowledge to be accurate. However, Universiti Teknologi Malaysia shall not be liable for any loss or damage caused by the usage of any information obtained from this web site.
Best viewed: Mozilla Firefox 4.0 & Google Chrome at 1024 × 768 resolution.