[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Task mapper and application-aware virtual machine scheduler oriented for parallel computing

  • Published:
Journal of Zhejiang University SCIENCE C Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

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

  • Alessandro, R., 2004. Linux Device Drivers (3rd Ed.). Power Press, Beijing, p.100–152.

    Google Scholar 

  • 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. [doi:10.1145/258128.258201]

    Article  MathSciNet  MATH  Google Scholar 

  • 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. [doi:10.1109/TPDS.2003.120 6502]

    Article  Google Scholar 

  • 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. [doi:10.1016/j.jpdc.2005.01.006]

    Article  MATH  Google Scholar 

  • 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.

    Google Scholar 

  • 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. [doi:10.1016/j.jpdc.2005.04.017]

    Article  MATH  Google Scholar 

  • 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.

  • 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. [doi:10.1109/ICPADS.2008.102]

  • 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.

    Google Scholar 

  • Chandra, A., Shenoy, P., 2008. Hierarchical scheduling for symmetric multiprocessors. IEEE Trans. Parall. Distr. Syst., 19(3):418–431. [doi:10.1109/TPDS.2007.70755]

    Article  Google Scholar 

  • 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. [doi:10.1145/1248377.1248396]

  • 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. [doi:10.1007/s11761-011-0087-6]

    Article  MathSciNet  Google Scholar 

  • 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. [doi:10.1007/s11761-011-0092-9]

  • Cherkasova, L., Gupta, D., Vahdat, A., 2007. Comparison of the three CPU schedulers in Xen. ACM SIGMETRICS Perform. Eval. Rev., 35(2):42–51. [doi:10.1145/1330555. 1330556]

    Article  Google Scholar 

  • Chuzhoy, C., Naor, J., 2006. New hardness results for congestion minimization and machine scheduling. J. ACM, 53(5):707–721. [doi:10.1145/1183907.1183908]

    Article  MathSciNet  Google Scholar 

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

  • 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. [doi:10.1109/SC.2002.10009]

  • Danish, M., Li, Y., Richard, W., 2011. Virtual-CPU Schedul ing in the Quest Operating System. 17th IEEE Real-Time and Embedded Technology and Applications Symp., p.169–179. [doi:10.1109/RTAS.2011.24]

  • 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. [doi:10.1016/j.jpdc.2011.05.005]

    Article  Google Scholar 

  • 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.

  • El-Rewini, H., Lewis, T.G., 1990. Scheduling parallel program tasks onto arbitrary target machines. J. Parall. Distr. Comput., 9(2):138–153. [doi:10.1016/0743-7315(90)900 42-N]

    Article  Google Scholar 

  • 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. [doi:10.1016/j.jpdc.2006.05.006]

    Article  MATH  Google Scholar 

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

  • Ghazalie, T., Baker, T., 1995. Aperiodic servers in a deadline scheduling environment. Real-Time Syst., 9(1):31–67. [doi:10.1007/BF01094172]

    Article  Google Scholar 

  • 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. [doi:10.1145/354871.354 873]

    Article  Google Scholar 

  • 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. [doi:10.1145/1254810.1254828]

  • 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. [doi:10.1109/TC.2009.53]

    Article  MathSciNet  Google Scholar 

  • 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. [doi:10.1145/248157.248171]

    Article  Google Scholar 

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

    Google Scholar 

  • 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.

  • Hamidzadeh, B., Kit, L.Y., Lilja, D.J., 2000. Dynamic task scheduling using online optimization. IEEE Trans. Parall. Distr. Syst., 11(11):1151–1163. [doi:10.1109/71.888636]

    Article  Google Scholar 

  • 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.

  • 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). [doi:10.1360/jos182016]

    Article  Google Scholar 

  • 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. [doi:10. 1109/ISPDC.2005.39]

  • 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. [doi:10.1109/ICGRID.2006.311024]

  • 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. [doi:10.1109/12.817403]

    Article  Google Scholar 

  • James, E.S., Ravi, N., 2007. Virtual Machines: Versatile Platforms for Systems and Processes. Morgan Kaufmann, p.113–152.

  • 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. [doi:10.1109/AICCSA.2005.1387108]

  • 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. [doi:10.1145/269005.266689]

  • 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. [doi:10.1109/ESCIW. 2009.5408002]

  • 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. [doi:10.1109/ICPPW.2005.6]

  • 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. [doi:10.1145/1508293.1508308]

  • Kim, J., Rho, J., Lee, J.O., Ko, M.C., 2005. CPOC: effective static task scheduling for grid computing. LNCS, 3726: 477–486. [doi:10.1007/11557654_56]

    Google Scholar 

  • 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. [doi:10.1016/j.jnca.2010.06.001]

    Article  Google Scholar 

  • 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. [doi:10.1016/j.ijpe.2007.03.018]

    Article  Google Scholar 

  • 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.

  • Nesmachnow, S., Cancela, H., Alba, E., 2010. Heterogeneous computing scheduling with evolutionary algorithms. Soft Comput. Fus. Found. Methodol. Appl., 15(4):685–701. [doi:10.1007/s00500-010-0594-y]

    Google Scholar 

  • 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. [doi:10.1145/268998.266677]

  • Ogata, K., 2002. Modern Control Engineering. Prentice Hall, Upper Saddle River, p.52–67.

  • Pfoh, J., Schneider, C., Eckert, C., 2009. Formal Model for Virtual Machine Introspection. Proc. 1st ACM Workshop on Virtual Machine Security, p.1–10. [doi:10.1145/1655148.1655150]

  • 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. [doi:10.1007/11508380_24]

    Google Scholar 

  • 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. [doi:10.1016/j.ijpe.2005.05.021]

    Article  Google Scholar 

  • 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. [doi:10.1109/TPDS.2002.1011417]

    Article  Google Scholar 

  • 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. [doi:10.1109/MASCOT.1999.805062]

  • Rawat, S.S., Rajamani, L., 2009. Experiments with CPU Scheduling Algorithm on a Computational Grid. IEEE Int. Advance Computing Conf., p.71–75. [doi:10.1109/IADCC. 2009.4808983]

  • Rosenblum, M., Garfinkel, T., 2005. Virtual machine monitors: current technology and future trends. Computer, 38(5):39–47. [doi:10.1109/MC.2005.176]

    Article  Google Scholar 

  • 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. [doi:10. 1109/GCC.2007.64]

  • 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).

    Google Scholar 

  • 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. [doi:10.1109/71.207593]

    Article  Google Scholar 

  • 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. [doi:10.1109/71.993206]

    Article  Google Scholar 

  • 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.

  • 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.

  • 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). [doi:10.3724/SP.J.1001.2009.00577]

    Article  Google Scholar 

  • Wu, M., Dajski, D., 1990. Hypertool: a programming aid for message passing systems. IEEE Trans. Parall. Distr. Syst., 1(3):330–343. [doi:10.1109/71.80160]

    Article  Google Scholar 

  • 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. [doi:10.1109/IPDPS.2004.1303052]

  • 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). [doi:10.1360/jos182027]

    Article  MATH  Google Scholar 

  • 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. [doi:10.1109/71.954620]

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, Xi’an University of Technology, Xi’an, 710048, China

    Jing Zhang, Xiao-jun Chen, Jun-huai Li & Xiang Li

  2. State Key Laboratory for Manufacturing Systems Engineering, Xi’an Jiaotong University, Xi’an, 710048, China

    Jing Zhang

Authors
  1. Jing Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiao-jun Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jun-huai Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xiang Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xiao-jun Chen.

Additional information

Project (No. 2007AA010305) supported by the National High-Tech R&D Program (863) of China

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zhang, J., Chen, Xj., Li, Jh. et al. Task mapper and application-aware virtual machine scheduler oriented for parallel computing. J. Zhejiang Univ. - Sci. C 13, 155–177 (2012). https://doi.org/10.1631/jzus.C1100217

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1631/jzus.C1100217

Key words

CLC number

Search

Navigation