Hitham Seddig Alhassan ALHUSSIAN, Mohamed Nordin Bin ZAKARIA, Fawnizu Azmadi Bin HUSSIN

Minimizing scheduling overhead in LRE-TL real-time multiprocessor scheduling algorithm

In this paper, we present a modification of the local remaining execution-time and local time domain (LRE-TL) real-time multiprocessor scheduling algorithm, aimed at reducing the scheduling overhead in terms of task migrations. LRE-TL achieves optimality by employing the fairness rule at the end of each time slice in a fluid schedule model. LRETL makes scheduling decisions using two scheduling events. The bottom (B) event, which occurs when a task consumes its local utilization, has to be preempted in order to resume the execution of another task, if any, or to idle the processor if none exist. The critical (C) event occurs when a task consumes its local laxity, which means that the task cannot wait anymore and has to be scheduled for execution immediately or otherwise it will miss its deadline. Event C always results in a task migration. We have modified the initialization procedure of LRE-TL to make sure that tasks that have higher probability of firing a C event will always be considered for execution first. This will ensure that the number of C events will always be at a minimum, thereby reducing the number of task migrations.

PDF

___

[1] Kopetz H. Real-Time Systems. 2nd ed. New York, NY, USA: Springer, 2013.
[2] Burns A, Wellings AJ. Real-Time Systems and Programming Languages. 4th ed. Toronto, Canada: Pearson Education, 2009.
[3] Buttazzo GC. Hard Real-Time Computing Systems. 3rd ed. New York, NY, USA: Springer, 2013.
[4] Laplante PA, Ovaska SJ. Real-Time Systems Design and Analysis. 4th ed. New York, NY, USA: Wiley, 2011.
[5] Liu JWS. Real-Time Systems. 1st ed. Upper Saddle River, NJ, USA: Prentice Hall, 2000.
[6] Nelissen G, Berten V, N´elis V, Goossens J, Milojevic D. U-EDF: An unfair but optimal multiprocessor scheduling algorithm for sporadic tasks. In: 24th Euromicro Conference on Real-Time Systems; 1113 July 2012; Pisa, Italy. New York, NY, USA: IEEE. pp. 13-23.
[7] Funk S, Levin G, Sadowski C, Pye I, Brandt S. DP-Fair: A unifying theory for optimal hard real-time multiprocessor scheduling. Real-Time Syst 2011; 47: 389-429.
[8] Audsley N, Burns A, Davis R, Tindell K, Wellings A. Real-time system scheduling. In: Randell B, Laprie J-C, Kopetz H, Littlewood B, editors. Predictably Dependable Computing Systems. Berlin, Germany: Springer, 1995, pp. 41-52.
[9] Nelissen G, Berten V, Goossens J, Milojevic D. Reducing preemptions and migrations in real-time multiprocessor scheduling algorithms by releasing the fairness. In: IEEE 17th International Conference on Embedded and RealTime Computing Systems and Applications; 2931 August 2011; Toyama, Japan. New York, NY, USA: IEEE. pp. 15-24.
[10] Davis RI, Burns A. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput Surv 2011; 43: 1-44.
[11] Bastoni A, Brandenburg BB, Anderson JH. An empirical comparison of global, partitioned, and clustered multiprocessor EDF schedulers. In: 31st IEEE Real-Time Systems Symposium; 30 November3 Dec 2010; San Diego, CA, USA. New York, NY, USA: IEEE. pp. 14-24.
[12] Bastoni A, Brandenburg BB, Anderson JH. Is semi-partitioned scheduling practical? In: 23rd Euromicro Conference on Real-Time Systems; 68 July 2011; Porto, Portugal. New York, NY, USA: IEEE. pp. 125-135.
[13] Liu CL, Layland JW. Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 1973; 20: 46-61.
[14] Funk S. LRE-TL: An optimal multiprocessor algorithm for sporadic task sets with unconstrained deadlines. RealTime Syst 2010; 46: 332-359.
[15] Baruah SK, Cohen NK, Plaxton CG, Varvel DA. Proportionate progress: a notion of fairness in resource allocation. Algorithmica 1996; 15: 600-625.
[16] Cho H, Ravindran B, Jensen ED. An optimal real-time scheduling algorithm for multiprocessors. In: 27th IEEE Real-Time Systems Symposium; 58 December 2006; Rio de Janeiro, Brazil. New York, NY, USA: IEEE. pp. 101-110.
[17] Goodrich M, Tamassia R, Goldwasser M. Data Structures and Algorithms in Java. 6th ed. New York, NY, USA: Wiley, 2014.
[18] Ma W. Data Structures and Algorithms Analysis in Java. 3rd ed. London, UK: Pearson, 2011.