Similar articles

Abstract: We design a task mapper TPCM for assigning tasks to virtual machines, and an application-aware virtual machine scheduler TPCS oriented for parallel computing to achieve a high performance in virtual computing systems. To solve the problem of mapping tasks to virtual machines, a virtual machine mapping algorithm (VMMA) in TPCM is presented to achieve load balance in a cluster. Based on such mapping results, TPCS is constructed including three components: a middleware supporting an application-driven scheduling, a device driver in the guest OS kernel, and a virtual machine scheduling algorithm. These components are implemented in the user space, guest OS, and the CPU virtualization subsystem of the Xen hypervisor, respectively. In TPCS, the progress statuses of tasks are transmitted to the underlying kernel from the user space, thus enabling virtual machine scheduling policy to schedule based on the progress of tasks. This policy aims to exchange completion time of tasks for resource utilization. Experimental results show that TPCM can mine the parallelism among tasks to implement the mapping from tasks to virtual machines based on the relations among subtasks. The TPCS scheduler can complete the tasks in a shorter time than can Credit and other schedulers, because it uses task progress to ensure that the tasks in virtual machines complete simultaneously, thereby reducing the time spent in pending, synchronization, communication, and switching. Therefore, parallel tasks can collaborate with each other to achieve higher resource utilization and lower overheads. We conclude that the TPCS scheduler can overcome the shortcomings of present algorithms in perceiving the progress of tasks, making it better than schedulers currently used in parallel computing.

[1]Abeni, L., Buttazzo, G., 1998. Integrating Multimedia Applications in Hard Real-Time Systems. Proc. 19th IEEE Real-Time Systems Symp., p.4-13.

[2]Alessandro, R., 2004. Linux Device Drivers (3rd Ed.). Power Press, Beijing, p.100-152.

[3]Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O., 1997. On-line routing of virtual circuits with applications to load balance and machine scheduling. J. ACM, 44(3):486-504.

[4]Bansal, S., Kumar, P., Singh, K., 2003. An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems. IEEE Trans. Parall. Distr. Syst., 14(6):533-544.

[5]Baskiyar, S., Dickinson, C., 2005. Scheduling directed a-cyclic task graphs on a bounded set of heterogeneous processors using task duplication. J. Parall. Distr. Comput., 65(8):911-921.

[6]Bavier, A., Peterson, L.L., Moseberger, D., 1999. BERT: a Scheduler for Best Effort and Realtime Tasks. Technical Report, Department of Computer Science, Princeton University, USA, p.12.

[7]Boyer, W.F., Hura, G.S., 2005. Non-evolutionary algorithm for scheduling dependent tasks in distributed heterogeneous computing environments. J. Parall Distr. Comput., 65(9):1035-1046.

[8]Caprita, B., Chan, W., Nieh, J., Clifford, S., Zheng, H.Q., 2005. Group Ratio Round-Robin: O(1) Proportional Share Scheduling for Uniprocessor and Multiprocessor Systems. Proc. Usenix Annual Technical Conf., p.8-16.

[9]Cerin, C., Fkaier, H., Jemni, M., 2008. Experimental Study of Thread Scheduling Libraries on Degraded CPU. 14th IEEE Int. Conf. on Parallel and Distributed Systems, p.697-704.

[10]Chan, W.C., Nieh, J., 2003. Group Ratio Round-Robin: an O(I) Proportional Share Scheduler. Technical Report, Department of Computer Science, Columbia University, USA, p.1-5.

[11]Chandra, A., Shenoy, P., 2008. Hierarchical scheduling for symmetric multiprocessors. IEEE Trans. Parall. Distr. Syst., 19(3):418-431.

[12]Chen, S., Gibbons, P.B., Kozuch, M., Liaskovitis, V., Ailamaki, A., Blelloch, G.E., Falsafi, B., Fix, L., Hardavellas, N., Mowry, T.C., et al., 2007. Scheduling Threads for Constructive Cache Sharing on CMPS. Proc. 19th Annual ACM Symp. on Parallel Algorithms and Architectures, p.105-115.

[13]Chen, X.J., Zhang, J., Li, J.H., Li, X., 2011a. Resource management framework for collaborative computing systems over multiple virtual machines. Serv. Orient. Comput. Appl., 5(4):225-243.

[14]Chen, X.J., Zhang, J., Li, J.H., Li, X., 2011b. Resource virtualization methodology for on-demand allocation in cloud computing systems. Serv. Orient. Comput. Appl., in press.

[15]Cherkasova, L., Gupta, D., Vahdat, A., 2007. Comparison of the three CPU schedulers in Xen. ACM SIGMETRICS Perform. Eval. Rev., 35(2):42-51.

[16]Chuzhoy, C., Naor, J., 2006. New hardness results for congestion minimization and machine scheduling. J. ACM, 53(5):707-721.

[17]Cota-Robles, E.C., Flautner, K., 2008. Real-Time Scheduling of Virtual Machines. U.S. Patent 7356817.

[18]Dail, H., Casanova, H., Berman, F., 2002. A Decoupled Scheduling Approach for the GrADS Program Development Environment. Proc. ACM/IEEE Conf. on Supercomputing, p.55-62.

[19]Danish, M., Li, Y., Richard, W., 2011. Virtual-CPU Scheduling in the Quest Operating System. 17th IEEE Real-Time and Embedded Technology and Applications Symp., p.169-179.

[20]Daoud, M.I., Kharma, N., 2011. A hybrid heuristic-genetic algorithm for task scheduling in heterogeneous processor networks. J. Parall. Distr. Comput., 71(11):1518-1531.

[21]Duda, K.J., Cheriton, D.R., 1999. Borrowed-Virtual-Time (BVT) Scheduling: Supporting Latency-Sensitive Threads in a General-Purpose Scheduler. Proc. 17th ACM SOSP, p.1-16.

[22]El-Rewini, H., Lewis, T.G., 1990. Scheduling parallel program tasks onto arbitrary target machines. J. Parall. Distr. Comput., 9(2):138-153.

[23]Fu, S., Xu, C.Z., 2006. Stochastic modeling and analysis of hybrid mobility in reconfigurable distributed virtual machines. J. Parall. Distr. Comput., 66(11):1442-1454.

[24]Fumio, M., 2009. Optimum Virtual Machine Placement and Rejuvenation Scheduling for High-Availability Consolidated Server Systems. CISUC, NEC, Japan, p.6-12.

[25]Ghazalie, T., Baker, T., 1995. Aperiodic servers in a deadline scheduling environment. Real-Time Syst., 9(1):31-67.

[26]Govil, K., Teodosiu, D., Huang, Y., Rosenblum, M., 2000. Cellular disco: resource management using virtual clusters on shared-memory multiprocessors. ACM Trans. Comput. Syst., 18(3):229-262.

[27]Govindan, S., Nath, A.R., Das, A., Urgaonkar, B., Sivasubramaniam, A., 2007. Xen and Co.: Communication-Aware CPU Scheduling for Consolidated Xen-Based Hosting Platforms. Proc. 3rd Int. Conf. on Virtual Execution Environments, p.126-136.

[28]Govindan, S., Choi, J., Nath, A.R., Das, A., Urgaonkar, B., Sivasubramaniam, A., 2009. Xen and Co.: communication-aware CPU management in consolidated Xen-based hosting platforms. IEEE Trans. Comput., 58(8):1111-1125.

[29]Goyal, P., Vin, H.M., Cheng, H., 1996. Start-time fair queuing: a scheduling algorithm for integrated services packet switching networks. ACM SIGCOMM Comput. Commun. Rev., 26(4):157-168.

[30]Grefenstette, J., Back, T., Fogel, D.B., Michalewicz, Z., 1997. Handbook of Evolutionary Computation (1st Ed.). Oxford University Press, Oxford, UK, p.241-246.

[31]Gupta, D., Cherkasova, L., Gardner, R., Vahdat, A., 2006. Enforcing Performance Isolation across Virtual Machines in Xen. Proc. 7th Int. Middleware Conf., p.342-362.

[32]Hamidzadeh, B., Kit, L.Y., Lilja, D.J., 2000. Dynamic task scheduling using online optimization. IEEE Trans. Parall. Distr. Syst., 11(11):1151-1163.

[33]Hiroshi, Y., Kenji, K., 2007. Foxy Technique: Tricking Operating System Policies with a Virtual Machine Monitor. Proc. 3rd Int. Conf. on Virtual Execution Environments, p.55-64.

[34]Huai, J.P., Li, Q., Hu, C.M., 2007. Research and design on hypervisor based virtual computing environment. J. Software, 18(8):2016-2026 (in Chinese).

[35]Ilavarasan, E., Thambidurai, P., Mahilmannan, R., 2005. Performance Effective Task Scheduling Algorithm for Heterogeneous Computing System. Proc. 4th Int. Symp. on Parallel and Distributed Computing, p.28-38.

[36]Iosup, A., Dumitrescu, C., Epema, D., Li, H., Wolters, L., 2006. How Are Real Grids Used the Analysis of Four Grid Traces and Its Implications. Proc. 7th IEEE/ACM Int. Conf. on Grid Computing, p.262-269.

[37]Iverson, M.A., Ozguner, F., Potter, L., 1999. Statistical prediction of task execution times through analytic benchmarking for scheduling in a heterogeneous environment. IEEE Trans. Comput., 48(12):1374-1379.

[38]James, E.S., Ravi, N., 2007. Virtual Machines: Versatile Platforms for Systems and Processes. Morgan Kaufmann, p.113-152.

[39]Jin, H., Hu, Q.H., Liao, X.F., Chen, H., Deng, D.F., 2005. IMAC: an Importance-Level Based Adaptive CPU Scheduling Scheme for Multimedia and Non-Real Time Applications. 3rd ACS/IEEE Int. Conf. on Computer Systems and Applications, p.119-125.

[40]Jones, M.B., Rosu, D., Rosu, M.C., 1997. CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities. Proc. 16th Symp. on Operating System Principles, p.198-211.

[41]Juve, G., Deelman, E., Vahi, K., Mehta, G., Berriman, B., Berman, B.P., Maechling, P., 2009. Scientific Workflow Applications on Amazon EC2. Proc. 5th IEEE Int. Conf. on E-Science Workshops, p.59-66.

[42]Katz, D.S., Jacob, J.C., Deelman, E., Kesselman, C., Singh, G., Su, M.H., Berriman, G.B., Good, J., Laity, A.C., Prince, T.A., 2005. A Comparison of Two Methods for Building Astronomical Image Mosaics on a Grid. Proc. Int. Conf. Workshops on Parallel Processing, p.85-94.

[43]Kim, H., Lim, H., 2009. Task-Aware Virtual Machine Scheduling for I/O Performance. Proc. ACM SIGPLAN/ SIGOPS Int. Conf. on Virtual Execution Environments, p.101-110.

[44]Kim, J., Rho, J., Lee, J.O., Ko, M.C., 2005. CPOC: effective static task scheduling for grid computing. LNCS, 3726:477-486.

[45]Kong, X.Z., Lin, C., Jiang, Y.X., Yan, W., Chu, X.W., 2011. Efficient dynamic task scheduling in virtualized data centers with fuzzy prediction. J. Network Comput. Appl., 34(4):1068-1077.

[46]Laslo, Z., Golenko-Ginzburg, D., Keren, B., 2008. Optimal booking of machines in a virtual job-shop with stochastic processing times to minimize total machine rental and job tardiness costs. Int. J. Prod. Econ., 111(2):812-821.

[47]Lehoczky, J., Sha, L., Ding, Y., 1989. The Rate Monotonic Scheduling Algorithm: Exact Characteristics and Average Case Behavior. Proc. IEEE Real-Time Systems Symp., p.166-171.

[48]Nesmachnow, S., Cancela, H., Alba, E., 2010. Heterogeneous computing scheduling with evolutionary algorithms. Soft Comput. Fus. Found. Methodol. Appl., 15(4):685-701.

[49]Nieh, J., Lam, M.S., 1997. The Design, Implementation, and Evaluation of SMART: a Scheduler for Multimedia Applications. Proc. 16th ACM Symp. on Operating System Principles, p.184-197.

[50]Ogata, K., 2002. Modern Control Engineering. Prentice Hall, Upper Saddle River, p.52-67.

[51]Pfoh, J., Schneider, C., Eckert, C., 2009. Formal Model for Virtual Machine Introspection. Proc. 1st ACM Workshop on Virtual Machine Security, p.1-10.

[52]Phinjaroenphan, P., Bevinakoppa, S., Zeephongsekul, P., 2005. A method for estimating the execution time of a parallel task on a grid node. LNCS, 3470:226-236.

[53]Qi, X.T., Jonathan, F.B., Yu, G., 2006. Disruption management for machine scheduling: the case of SPT schedules. Int. J. Prod. Econ., 103(1):166-184.

[54]Radulescu, A., van Gemund, A.J.C., 2002. Low-cost task scheduling for distributed memory machines. IEEE Trans. Parall. Distr. Syst., 13(6):648-658.

[55]Rau, M.A., Smirni, E., 1999. Adaptive CPU Scheduling Policies for Mixed Multimedia and Best-Effort Workloads. Proc. 7th Int. Symp. on Modeling, Analysis, and Simulation of Computer Systems, p.45-52.

[56]Rawat, S.S., Rajamani, L., 2009. Experiments with CPU Scheduling Algorithm on a Computational Grid. IEEE Int. Advance Computing Conf., p.71-75.

[57]Rosenblum, M., Garfinkel, T., 2005. Virtual machine monitors: current technology and future trends. Computer, 38(5):39-47.

[58]Shi, L., Sun, Y.Y., Wei, L., 2007. Effect of Scheduling Discipline on CPU-MEM Load Sharing System. 6th Int. Conf. on Grid and Cooperative Computing, p.242-249.

[59]Shi, L., Zhou, D.Q., Jin, H., 2009. Xen Virtualization Techonolgy. Huazhong University of Science and Technology Press, Wuhan, China, p.222-224 (in Chinese).

[60]Sih, G.C., Lee, E.A., 1993. A compile-time scheduling heuristic for interconnection constrained heterogeneous processor architectures. IEEE Trans. Parall. Distr. Syst., 4(2):175-187.

[61]Topcuoglu, H., Hariri, S., Wu, M.Y., 2002. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parall. Distr. Syst., 13(3):260-274.

[62]Volkmar, U., Joshua, L.V., Espen, S., Uwe, D., 2004. Towards Scalable Multiprocessor Virtual Machines. Proc. 3rd Conf. on Virtual Machine Research and Technology Symp., p.4.

[63]Waldspurger, C.A., Weihl, W.E., 1994. Lottery Scheduling: Flexible Proportional-Share Resource Management. Proc. 1st Usenix Symp. on Operating System Design and Implementation, p.359-368.

[64]Wang, J., Sun, J.L., Wang, X.Y., Yang, X.H., Wang, S.K., Chen, J.B., 2009. Efficient scheduling algorithm for hard real-time tasks in primary-backup based multiprocessor systems. J. Software, 20(10):2628-2636 (in Chinese).

[65]Wu, M., Dajski, D., 1990. Hypertool: a programming aid for message passing systems. IEEE Trans. Parall. Distr. Syst., 1(3):330-343.

[66]Zhang, W., Fang, B., He, H., Zhang, H., Hu, M., 2004. Multisite Resource Selection and Scheduling Algorithm on Computational Grid. Proc. 18th Int. Parallel and Distributed Processing Symp., p.105.

[67]Zhang, W.Z., Tian, Z.H., Zhang, H.L., He, H., Liu, W.M., 2007. Multi-cluster co-allocation scheduling algorithms in virtual computing environment. J. Software, 18(8):2027-2037 (in Chinese).

[68]Zomaya, A.Y., Teh, Y.H., 2001. Observations on using genetic algorithms for dynamic load balance. IEEE Trans. Parall. Distr. Syst., 12(9):899-911.