Probabilistic and Fuzzy Process Classifiers for Operating Systems Scheduler

• Autorzy: Bagchi S.

Identyfikatory

DOI

10.3233/FI-2016-1369

• Języki publikacji: EN

Abstrakty

EN

The schedulers residing in kernel of Operating Systems employ patterns of resource affinities of concurrent processes in order to make scheduling decisions. The scheduling decisions affect overall resource utilization in a system. Moreover, the resource affinity patterns of a process may not be possible to profile statically in all cases. This paper proposes a novel probabilistic estimation model and a classifier algorithm to queuing processes based on respective resource affinities. The proposed model follows probabilistic estimation using execution traces, which can be either online or statically profiled. The algorithm tracks the resource affinities of processes based on periodic estimation and classifies the processes accordingly for scheduling. The effects of variations of estimation periods are investigated and fuzzy refinements are introduced. Experimental results indicate that the classifier algorithm successfully determines resource affinities of a set of processes online. However, the algorithm can determine inherent affinity pattern of a process in the presence of uniform distribution having enhanced IO frequency.

Słowa kluczowe

EN

CPU-bound; fuzzy logic; IO-bound; Kernel; probabilistic estimation; scheduler; scheduling quanta

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 4
• Strony: 405--427
• Opis fizyczny: Bibliogr. 21 poz., rys., tab., wykr.

Twórcy

autor

Bagchi S.

• Department of Aerospace and Software Engineering (Informatics), Gyeongsang National University, Jinju, 660-701 South Korea

Bibliografia

• [1] Wu J, Kuo TW. Real-Time Scheduling of CPU-Bound and I/O-Bound Processes, Sixth International Conference on Real-Time Computing Systems and Applications, IEEE, 1999, p.303–310. doi:10.1109/RTCSA.1999.811262.
• [2] Popiolek PF, Mendizabal OM. Monitoring and analysis of performance impact in virtualized environments. Journal of Applied Computing Research. 2012;2(2):75-82. doi:10.4013/jacr.2012.22.0.
• [3] Trapp P (et al.). Building CPU Stubs to Optimize CPU Bound Systems: An Application of Dynamic Performance Stubs. International Journal on Advances in Software. 2011;4(1/2):189-206. Available from: http://hdl.handle.net/2086/5481.
• [4] Chahar V, Raheja S. Fuzzy Based Multilevel Queue Scheduling Algorithm, 2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI), IEEE, 2013, p.115–120. doi:10.1109/ICACCI.2013.6637156.
• [5] Salah K, Manea A, Zeadally S, Calero JMA. On Linux starvation of CPU-bound processes in the presence of network I/O, Computers and Electrical Engineering Journal, Elsevier. 2011;37(6):1090–1105. doi:10.1016/j.compeleceng.2011.07.001.
• [6] Groot S (et al.). Modeling I/O Interference for Data Intensive Distributed, Applications, In Proceedings of the 28th Annual ACM Symposium on Applied Computing (SAC), ACM. 2013, p.343-350. doi:10.1145/2480362.2480434.
• [7] Xu Z, Yan B, Zou Y. Beyond Hadoop: Recent Directions in Data Computing for Internet Services, In Book titled - Cloud Computing Advancements in Design, Implementation, and Technologies (Ed. Aljawarneh S.), IGI Global, USA, 2012. doi:10.4018/978-1-4666-1879-4.ch004.
• [8] Mozafari B (et al.) Performance and Resource Modeling in Highly-Concurrent OLTP Workloads, In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD), ACM, 2013, p.301–312. doi:10.1145/2463676.2467800.
• [9] Hwang I, Pedram M, Kam T. A Study of the Effectiveness of CPU Consolidation in a Virtualized Multi-Core Server System. Proceedings of the 2012 ACM/IEEE international symposium on Low power electronics and design (ISLPED). ACM, 2012, p.339–344. doi:10.1145/2333660.2333736.
• [10] Pu X, Liu L, Mei Y, Sivathanu S, Koh Y, Pu C. Understanding Performance Interference of I/O Workload in Virtualized Cloud Environments, IEEE International conference on Cloud Computing, IEEE, Miami, 2010, p.51–58. doi:10.1109/CLOUD.2010.65.
• [11] Carey MJ, Lu H. Load balancing in a locally distributed database system, ACM SIGMOD International conference on Management of Data, ACM Press, Washington, 1986, p.108–119. doi:10.1145/16894.16865.
• [12] Rohm U. OLAP with a Database Cluster, in Book titled - Database Technologies: Concepts, Methodologies, Tools, and Applications: Concepts, Methodologies, Tools, and Applications (Ed. Erickson J.), IGI Global, USA, 2009.
• [13] Kuo WT, Mok AK. Incremental Reconfiguration and Load Adjustment in Adaptive Real-Time Systems, IEEE Transaction on Computers. 1997;46(12):1313-1324. doi:http://doi.ieeecomputersociety.org/10.1109/12.641932.
• [14] Kang DI, Gerber R, Saksena M. Performance-Based Design of Distributed Real-Time Systems, 3rd IEEE Real-Time Technology and Applications Symposium, IEEE. 1997, p.2–13. doi:10.1109/RTTAS. 1997.601321.
• [15] Alam B, Doja MN, Biswas R. Finding Time Quantum of Round Robin CPU Scheduling Algorithm Using Fuzzy Logic, International Conference on Computer and Electrical Engineering (ICCEE), IEEE, 2008, p.795–798. doi:10.1109/ICCEE.2008.89.
• [16] Rezaee A. (et al.). A Fuzzy Algorithm for Adaptive Multilevel Queue Management with QoS Feedback, International Conference on High Performance Computing and Simulation (HPCS), IEEE, 2011, p.121–127. doi:10.1109/HPCSim.2011.5999815.
• [17] Jose J, Sujisha O, Gilesh M, Bindima T. On the Fairness of Linux O(1) Scheduler, 5th International Conference on Intelligent Systems, Modelling and Simulation, IEEE, 2014, p.668–674. doi:10.1109/ISMS. 2014.120.
• [18] Mozafari B, Curino C, Madden S. DBSeer: Resource and Performance Prediction for Building a Next Generation Database Cloud, Sixth Biennial Conference on Innovative Data Systems Research (CIDR 2013), USA, 2013.
• [19] Kumar A, Vembu S, Menon AK, Elkan C. Learning and Inference in Probabilistic Classifier Chains with Beam Search, In the Proceedings of Machine Learning and Knowledge Discovery in Databases (ECML PKDD’12), Springer LNCS, Vol. 7523, 2012, p.665–680. doi:10.1007/978-3-642-33460-3 48.
• [20] Dembczynski K, ChengW, Hullermeier E. Bayes optimal multi-label classification via probabilistic classifier chains, In Proceedings of ICML, 2010, p.279–286. Available from: http://www.icml2010.org/papers/589.pdf.
• [21] Read J, Pfahringer B, Holmes G, Frank E. Classifier chains for multi-label classification, Machine Learning. 2011;85(3):333–359. doi:10.1007/s10994-011-5256-5.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).