Effect of Thread Weight Readjustment Scheduler on Scheduling Criteria
Abstract
In this paper, we propose a new approach to significantly optimize some scheduling criteria, context switches and turnaround times in this context, when running multithreaded processes concurrently. Current proportional sharing schedulers allocate CPU time based on the weights of running threads in the system and don’t take into consideration the greedy behavior of multithreaded processes (processes with more threads receive more aggregate CPU time from the scheduler relative to processes with fewer threads). In order to minimize turnaround times and context switches of running multithreaded processes in simultaneous multithreaded (SMT) architectures, we investigate the effect of adjusting the weights of running sibling threads (threads forked from the same process) using novel proportional sharing scheduler, Thread Weight Readjustment Scheduler (TWRS), a proportional share CPU scheduler designed for multithreaded processes, which aims to reduce undesirable events (e.g. context switches) and turnaround times. TWRS provides a practical solution for multitasking operating systems because it operates in concert with existing kernels. We have implemented TWRS in Linux 2.6.24-1, which represents the most prevalent scheduler design (i.e. Completely Fair Scheduler (CFS)). Our evaluation shows that our scheduler minimizes context switches and turnaround time.
References
Satoshi Yamada, Shigeru Kusakabe, “Development of A Thread Scheduler for Global Aggregation of Sibling Threads, ” In Research Reports on Information Science and Electrical Engineering of Kyushu University, Vol.13, No.2, pp.69-74, 2008.
Abhishek Chandra , Micah Adler , Pawan Goyal and Prashant Shenoy, “Surplus Fair Scheduling: A Proportional-Share CPU Scheduling Algorithm for Symmetric Multiprocessors,” In: Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.4-4, October 22-25, San Diego, California, 2000.
Hiroaki Takasaki, Samih M. Mostafa, Shigeru Kusakabe, “Applying Eco-Threading Framework to Memory-Intensive Hadoop Applications,” 5th International Conference on Information Science and Applications (ICISA 2014), seoul, Korea, May, 2014.
Love R., “Linux Kernel Development,” 3nd edition, Noval Press, ISBN 0-672-32720-1, 2010.
Samih M. Mostafa, S.Z. Rida, S.H. Hamad, “Finding Time Quantum of Round Robin CPU Scheduling Algorithm in General Computing Systems Using Integer Programming,” International Journal of Research and Reviews in Applied Sciences (IJRRAS) 5 (1), pp. 64–71, 2010.
Hussain Hameed ,Malik Saif Ur Rehman,Hameed Abdul,Khan Samee Ullah,Bickler Gage,Min-Allah Nasro,Qureshi Muhammad Bilal,Zhang Limin,Yongji Wang,Ghani Nasir,Kolodziej Joanna,Zomaya Albert Y.,Xu Cheng-Zhong,Balaji Pavan,Vishnu Abhinav,Pinel Fredric,Pecero Johnatan,Kliazovich Dzmitry,Bouvry, Pascal,Li Hongxiang,Wang Lizhe,Chen Dan,Rayes Ammar, “A Survey on Resource Allocation in High Performance Distributed Computing Systems. Parallel Computing,” vol. 39, no. 11, pp. 709-736, 2014.
Silberschatz A, Galvin PB, Gagne G, “Operating Systems Concepts,” John Wiley and Sons. 9Ed. 2013.
Samih M. Mostafa and Shigeru Kusakabe, “Towards Minimizing Processes Response Time in Interactive Systems,” International Journal of Computer Science and Information Technology Research (IJCSITR). Vol. 1, Issue 1, pp. 65-73, 2013.
Samih M. Mostafa, Hamad SH and Rida SZ, “Improving Scheduling Criteria of Preemptive Tasks Scheduled under Round Robin Algorithm using Changeable Time Quantum,” J Comput Sci Syst Biol. 2011.
Wong C. S., Tan I., Kumari R. D., and Wey F., “Towards achieving fairness in the Linux scheduler,” In: SIGOPS Oper. Syst. Rev. 42, 5, pp. 34-43, July, 2008.
Yamada S. and Shigeru Kusakabe, “Effect of Context Aware Scheduler on TLB,” In: Workshop on Multi-Threaded Architectures and Applications, Published in CD, 2008.
Jeffrey D. Ullman, “Polynomial Complete Scheduling Problems,” In: Proc. of the fourth ACM symposium on Operating system principles, pp. 96 – 101, 1973.
Ramamritham, K., and Stankovic, J. A., “Scheduling Algorithms and Operating Systems Support for Realtime Systems,” In: Proceedings of the IEEE, vol. 82, no. 1, 1994.
Daniel P. Bovet and Marco Cesati, “Understanding the Linux Kernel,”. 3rd edition, O’Reilly Press, ISBN 0-596-00565-2, 2005.
Jacek Kobus and Rafal Szklarski, “Completely Fair Scheduler and its tuning,” http://www.fizyka.umk.pl/jkob/prace-mag/cfs-tuning.pdf, 2009.
Josh Aas., “Understanding the Linux 2.6.8.1 CPU scheduler,” Silicon Graphics, Inc., 2005.
Kevin Jeffay, F. Donelson Smith, Arun Moorthy and James Anderson, “Proportional Share Scheduling of Operating System Services for Real-Time Applications,” In: Proceedings of the 19th IEEE Real-Time Systems Symposium, Madrid, Spain, pp 480-491, Dec., 1998.
Eric Schulte Taylor Groves and Jeff Knockel, “BFS vs. CFS Scheduler Comparison,” http://cs.unm.edu/~eschulte/classes/cs587/data/bfs-v-cfs_groves-knockel-schulte.pdf, Dec., 2009.
Ting Yang, Tongping Liu, Emery D. Berger, Scott F. Kaplan, and J. Eliot B. Moss: Redline: First class support for interactivity in commodity operating systems. In: Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, pp. 73–86, 2008.
Prajakta Pawar, S.S.Dhotre and Suhas Patil, “CFS for Addressing CPU Resources in Multi-Core Processors with AA Tree,” International Journal of Computer Science and Information Technologies, Vol. 5 (1) , pp. 913-917, 2014.
Tobias Beisel, Tobias Wiersema, Christian Plessl, and André Brinkmann, “Programming and Scheduling Model for Supporting Heterogeneous Accelerators in Linux,” In: Proceedings of the 3rd Workshop on Computer Architecture and Operating System Co-design (CAOS), Paris, France 2012.
Ion Stoica, Hussein Abdel-Wahab, Kevin Jeffay, Sanjoy K. Baruah,Johannes E. Gehrke and C. Greg Plaxton, “A Proportional Share Resource Allocation Algorithm for Real-time and Time-shared Systems,” In: Proc. 17th IEEE Real-Time Systems Symp., Dec., 1996.
Wong C. S., Tan I.K.T., Kumari R.D. and Kalaiyappan K.P., “Iterative Performance Bounding for Greedy-Threaded Process,” In: TENCON IEEE Region 10 Conference, Singapore, 2009.
http://www.cs.fsu.edu/~baker/devices/lxr/http/source/linux/kernel/sched.c?v=2.6.25#L1183
Wong C.S., Tan I.K.T., Kumari R.D., Lam J.W. and Fun W., “Fairness and Interactive Performance of O(1) and CFS Linux Kernel Schedulers,” In: Information Technology, ITSim, 2008.
Tong Li, Dan Baumberger and Scott Hahn, “Efficient and Scalable Multiprocessor Fair Scheduling using Distributed Weighted Round-Robin,” In Proc. of the 14th ACM Symposium on Principles and Practice of Parallel Programming, Feb., 2009.
http://www.linuxcertif.com/man/1/sysbench/
John Regehr, “Some Guidelines for Proportional Share CPU Scheduling in General-Purpose Operating Systems,” Work in Progress Session of the Proc. IEEE Real-Time Systems Symp. (RTSS ',01), Dec., 2001.
