Abstract
A drawback of current proportional fair schedulers is that they ignore task-to-processor mutual affinities, thereby causing frequent inter-processor task migrations and cache misses. This paper presents the Sticky-ERfair Scheduler, an Early-Release Fair (ERfair) scheduler that attempts to minimize task migrations and preemptions. Given any processor V i , Sticky-ERfair allocates to it the most recently executed ready task that previously executed on V i (thus restricting migrations and preemptions) in such a way that this allocation does not cause any ERfairness violations in the system at any time during the schedule length. Experimental results reveal that Sticky-ERfair can achieve upto over 40 times reduction both in the number of migrations and preemptions suffered with respect to Basic-ERfair (for a set of 25 to 100 tasks running on 2 to 10 processors) while simultaneously guaranteeing ERfairness at each time slot.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anderson J, Bud V, Devi UC (2005) An edf-based scheduling algorithm for multiprocessor soft real-time systems. In: Proceedings of the 17th euromicro conference on real-time systems (ECRTS’05), Washington, DC, USA, IEEE Comput. Soc., Los Alamitos, pp 199–208
Anderson J, Srinivasan A (2000) Early-release fair scheduling. In: Proceedings of the 12th euromicro conference on real-time systems, Jun 2000, pp 35–43
Anderson J, Srinivasan A (2004) Mixed pfair/ERfair scheduling of asynchronous periodic tasks. J Comput Syst Sci 68(1):157–204
Andersson B, Bletsas K (2008) Sporadic multiprocessor scheduling with few preemptions. In: ECRTS ’08: Proceedings of the 20th euromicro conference on real-time systems, Prague, Jul 2008, pp 243–252
Andersson B, 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, Jul 2003, pp 33–40
Andersson B, Tovar E (2006) Multiprocessor scheduling with few preemptions. In: Proceedings of the 12th IEEE international conference on embedded and real-time computing systems and applications, pp 322–334
Baruah S, Cohen N, Plaxton CG, Varvel D (1996) Proportionate progress: A notion of fairness in resource allocation. Algorithmica 15(6):600–625
Baruah S, Fisher N (2006) The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems. IEEE Trans Comput 55(7):918–923
Baruah S, Gehrke J, Plaxton CG (1995) Fast scheduling of periodic tasks on multiple resources. In: Proceedings of the 9th international parallel processing symposium, Apr 1995, pp 280–288
Berg E, Hagersten E (2004) Statcache: a probabilistic approach to efficient and accurate data locality analysis. In: ISPASS ’04: proceedings of the 2004 IEEE international symposium on performance analysis of systems and software, Washington, DC, USA. IEEE Comput Soc, Los Alamitos, pp 20–27
Block A, Anderson J (2006) Accuracy versus migration overhead in real-time multiprocessor reweighting algorithms. In: Proceedings of the 12th international conference on parallel and distributed systems, Washington, DC, USA. IEEE Comput. Soc., Los Alamitos, pp 355–364
Carpenter J, Funk S, Holman P, Srinivasan A, Anderson J, Baruah S (2004) A categorization of real-time multiprocessor scheduling problems and algorithms. Handbook of scheduling algorithms, methods and models
Cho H, Ravindran B, Jensen ED (2006) An optimal real-time scheduling algorithm for multiprocessors. In: RTSS ’06: proceedings of the 27th IEEE international real-time systems symposium, Washington, DC, USA. IEEE Comput. Soc., Los Alamitos, pp 101–110
Funaoka K, Kato S, Yamasaki N (2008) Work-conserving optimal real-time scheduling on multiprocessors. In: ECRTS ’08: proceedings of the 20th euromicro conference on real-time systems, Prague, Jul 2008, pp 13–22
Funk S, Goossens J, Baruah S (2001) On-line scheduling on uniform multiprocessors. In: Proceedings of the 22nd IEEE real-time systems symposium, Dec 2001
Gupta A, Tucker A, Urushibara S (1991) The impact of operating system scheduling policies and synchronization methods of the performance of parallel application. In: ACM SIGMETRICS conference on measurement and modeling of computer systems, pp 120–132
Harizopoulos S, Ailamaki A Affinity scheduling in staged server architectures, Mar 2002
Jeffay K, Goddard S (1999) A theory of rate-based execution. In: Proceedings of the 20th IEEE real-time systems symposium, pp 304–314
Jeffay K, Goddard S (2001) Rate-based resource allocation models for embedded systems. In: Lecture Notes in Computer Science, vol 2211. p 204
Kimbrel T, Schieber B, Sviridenko M (2006) Minimizing migrations in fair multiprocessor scheduling of persistent tasks. J Sched 9(4):365–379
Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20(1):46–61
Lopez JM, Garcia M, Diaz JL, Garcia DF (2000) Worst-case utilization bound for edf scheduling on real-time multiprocessor systems. In: Proceedings of the 12th euromicro conference on real-time systems, Jun 2000, pp 25–33
Malkevitch J (2004) Bin packing and machine scheduling. Feature column from the AMS: monthly essays on mathematical topics, Jun 2004
Negi HS, Mitra T, Roychoudhury A (2003) Accurate estimation of cache-related preemption delay. In: CODES+ISSS ’03: Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, pp 201–206
Phillips C, Stein C, Torng E, Wein J (1997) Optimal time-critical scheduling via resource augmentation. In: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp 140–149
Squillante MS, Lazowska ED (1993) Using processor-cache affinity information in shared-memory multiprocessor scheduling. IEEE Trans Parallel Distrib Syst 4(2):131–143
Squillante MS, Nelson RD (1991) Analysis of task migration in shared-memory multiprocessor scheduling. In: ACM SIGMETRICS conference on measurement and modeling of computer systems, pp 143–155
Srinivasan A, Holman P, Anderson J (2003) The case for fair multiprocessor scheduling. In: Proceedings of the 11th international workshop on parallel and distributed real-Time systems, Nice, France, Apr 2003
Torrellas J, Tucker A, Gupta A (1993) Benefits of cache-affinity scheduling in shared-memory multiprocessors: a summary. ACM SIGMETRICS Perform Eval Rev 21(1):272–274
Zhu D, Mosse D, Melhem R (2003) Multiple-resource periodic scheduling problem: how much fairness is necessary. In: Proceedings of the 24th IEEE real-time systems symposium, Dec 2003, p 142
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sarkar, A., Ghose, S. & Chakrabarti, P.P. Sticky-ERfair: a task-processor affinity aware proportional fair scheduler. Real-Time Syst 47, 356–377 (2011). https://doi.org/10.1007/s11241-011-9120-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11241-011-9120-2