research-article

Demand-based coordinated scheduling for SMP VMs

Authors:

Seungryoul MaengAuthors Info & Claims

ASPLOS '13: Proceedings of the eighteenth international conference on Architectural support for programming languages and operating systems

Pages 369 - 380

https://doi.org/10.1145/2451116.2451156

Published: 16 March 2013 Publication History

Abstract

As processor architectures have been enhancing their computing capacity by increasing core counts, independent workloads can be consolidated on a single node for the sake of high resource efficiency in data centers. With the prevalence of virtualization technology, each individual workload can be hosted on a virtual machine for strong isolation between co-located workloads. Along with this trend, hosted applications have increasingly been multithreaded to take advantage of improved hardware parallelism. Although the performance of many multithreaded applications highly depends on communication (or synchronization) latency, existing schemes of virtual machine scheduling do not explicitly coordinate virtual CPUs based on their communication behaviors.

This paper presents a demand-based coordinated scheduling scheme for consolidated virtual machines that host multithreaded workloads. To this end, we propose communication-driven scheduling that controls time-sharing in response to inter-processor interrupts (IPIs) between virtual CPUs. On the basis of in-depth analysis on the relationship between IPI communications and coordination demands, we devise IPI-driven coscheduling and delayed preemption schemes, which effectively reduce synchronization latency and unnecessary CPU consumption. In addition, we introduce a load-conscious CPU allocation policy in order to address load imbalance in heterogeneously consolidated environments. The proposed schemes are evaluated with respect to various scenarios of mixed workloads using the PARSEC multithreaded applications. In the evaluation, our scheme improves the overall performance of consolidated workloads, especially communication-intensive applications, by reducing inefficient synchronization latency.

References

[1]

AMD. Amd64 architecture programmer's manual volume 2: System programming, 2010.

[2]

R. H. Arpaci, A. C. Dusseau, A. M. Vahdat, L. T. Liu, T. E. Anderson, and D. A. Patterson. The interaction of parallel and sequential workloads on a network of workstations. In Proc. SIGMETRICS, 1995.

Digital Library

[3]

A. C. Arpaci-Dusseau. Implicit coscheduling: coordinated scheduling with implicit information in distributed systems. ACM TOCS, 19 (3): 283--331, 2001.

Digital Library

[4]

A. C. Arpaci-Dusseau, D. E. Culler, and A. M. Mainwaring. Scheduling with implicit information in distributed systems. In Proc. SIGMETRICS, 1998.

Digital Library

[5]

P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield. Xen and the art of virtualization. In Proc. SOSP, 2003.

Digital Library

[6]

C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: characterization and architectural implications. In Proc. PACT, 2008.

Digital Library

[7]

H. Chen, H. Jin, K. Hu, and J. Huang. Scheduling overcommitted VM: Behavior monitoring and dynamic switching-frequency scaling. FGCS, 2011.

Digital Library

[8]

K. J. Duda and D. R. Cheriton. Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler. In Proc. SOSP, 1999.

Digital Library

[9]

A. C. Dusseau, R. H. Arpaci, and D. E. Culler. Effective distributed scheduling of parallel workloads. In Proc. SIGMETRICS, 1996.

Digital Library

[10]

D. Feitelson. Gang scheduling performance benefits for fine-grain synchronization. JPDC, 16 (4): 306--318, 1992.

[11]

T. Friebel and S. Biemueller. How to deal with lock holder preemption. In Xen Summit, 2008.

[12]

Intel. Intel 64 and ia-32 architectures software developer's manual. volume 3b: System programming guide, part 2, 2010.

[13]

W. Jiang, Y. Zhou, Y. Cui, W. Feng, Y. Chen, Y. Shi, and Q. Wu. CFS optimizations to KVM threads on multi-core environment. In Proc. ICPADS, 2009.

Digital Library

[14]

H. Kim, H. Lim, J. Jeong, H. Jo, and J. Lee. Task-aware virtual machine scheduling for I/O performance. In Proc. VEE, 2009.

Digital Library

[15]

A. Kivity, U. Lublin, and A. Liguori. KVM: the Linux virtual machine monitor. In Proc. OLS, 2007.

[16]

W. Lee, M. Frank, V. Lee, K. Mackenzie, and L. Rudolph. Implications of I/O for gang scheduled workloads. In Proc. IPPS, 1997.

Digital Library

[17]

Y. Lee, W. Son, S. Park, G. Lee, D. Howard, and D. Slezak. Design and implementation of a locking-aware scheduler for multiprocessor environments. Convergence and Hybrid Information Technology, 6935: 384--390, 2011.

Digital Library

[18]

W. Mauerer. Professional Linux Kernel Architecture. Wrox Press Ltd., 2008.

Digital Library

[19]

P. B. Menage. Adding generic process containers to the Linux kernel. In Proc. OLS, 2007.

[20]

J. Ousterhout. Scheduling Techniques for Concurrent Systems. In Proc. ICDCS, 1982.

[21]

M. Russinovich and D. A. Solomon. Windows Internals: Including Windows Server 2008 and Windows Vista, Fifth Edition. Microsoft Press, 5th edition, 2009.

Digital Library

[22]

P. Sobalvarro, S. Pakin, W. Weihl, and A. Chien. Dynamic coscheduling on workstation clusters. In Proc. IPPS, 1998.

Digital Library

[23]

P. G. Sobalvarro and W. E. Weihl. Demand-based coscheduling of parallel jobs on multiprogrammed multiprocessors. In Proc. IPPS, 1995.

Digital Library

[24]

O. Sukwong and H. S. Kim. Is co-scheduling too expensive for SMP VMs? In Proc. EuroSys, 2011.

Digital Library

[25]

V. Uhlig, J. LeVasseur, E. Skoglund, and U. Dannowski. Towards scalable multiprocessor virtual machines. In Proc. VM, 2004.

Digital Library

[26]

VMWare. VMware, Inc. VMware vSphere 4: The CPU scheduler in VMware ESX 4.1. Technical report, 2010.

[27]

C. Weng, Z. Wang, M. Li, and X. Lu. The hybrid scheduling framework for virtual machine systems. In Proc. VEE, 2009.

Digital Library

[28]

C. Weng, Q. Liu, L. Yu, and M. Li. Dynamic adaptive scheduling for virtual machines. In Proc. HPDC, 2011.

Digital Library

[29]

Y. Wiseman and D. G. Feitelson. Paired gang scheduling. IEEE TPDS, 14 (6): 581--592, 2003.

Digital Library

[30]

Y. Yu, Y. Wang, H. Guo, and X. He. Hybrid co-scheduling optimizations for concurrent applications in virtualized environments. In Proc. ICNAS, 2011.

Digital Library

Cited By

Jia WZhang JShan JDing XFedorova ANarayanan DDi Luna GQuerzoni L(2023)Making Dynamic Page Coalescing Effective on Virtualized CloudsProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3567487(298-313)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3552326.3567487
Ishiguro KYasuno NAublin PKono K(2023)Revisiting VM-Agnostic KVM vCPU Scheduler for Mitigating Excessive vCPU SpinningIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.329768834:10(2615-2628)Online publication date: Oct-2023
https://doi.org/10.1109/TPDS.2023.3297688
Vepuri NJiang X(2023)Performance Analysis of Virtual Machine Monitoring System2023 IEEE Green Energy and Smart Systems Conference (IGESSC)10.1109/IGESSC59090.2023.10321757(1-6)Online publication date: 13-Nov-2023
https://doi.org/10.1109/IGESSC59090.2023.10321757
Show More Cited By

Index Terms

Demand-based coordinated scheduling for SMP VMs
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Scheduling

Recommendations

Is co-scheduling too expensive for SMP VMs?
EuroSys '11: Proceedings of the sixth conference on Computer systems

Symmetric multiprocessing (SMP) virtual machines (VMs) allow users to take advantage of a multiprocessor infrastructure. Despite the advantage, SMP VMs can cause synchronization latency to increase significantly, depending on task scheduling. In this ...
Demand-based coordinated scheduling for SMP VMs
ASPLOS '13

As processor architectures have been enhancing their computing capacity by increasing core counts, independent workloads can be consolidated on a single node for the sake of high resource efficiency in data centers. With the prevalence of virtualization ...
Demand-based coordinated scheduling for SMP VMs
ASPLOS '13

As processor architectures have been enhancing their computing capacity by increasing core counts, independent workloads can be consolidated on a single node for the sake of high resource efficiency in data centers. With the prevalence of virtualization ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS '13: Proceedings of the eighteenth international conference on Architectural support for programming languages and operating systems

March 2013

574 pages

ISBN:9781450318709

DOI:10.1145/2451116

General Chair:
Vivek Sarkar
Rice University, USA
,
Program Chair:
Rastislav Bodik
University of California, Berkeley, USA

ACM SIGPLAN Notices Volume 48, Issue 4
ASPLOS '13
April 2013
540 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2499368
Issue’s Table of Contents
ACM SIGARCH Computer Architecture News Volume 41, Issue 1
ASPLOS '13
March 2013
540 pages
ISSN:0163-5964
DOI:10.1145/2490301
Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 March 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASPLOS '13

Sponsor:

ASPLOS '13: Architectural Support for Programming Languages and Operating Systems

March 16 - 20, 2013

Texas, Houston, USA

Acceptance Rates

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

52
Total Citations
View Citations
828
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)2

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jia WZhang JShan JDing XFedorova ANarayanan DDi Luna GQuerzoni L(2023)Making Dynamic Page Coalescing Effective on Virtualized CloudsProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3567487(298-313)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3552326.3567487
Ishiguro KYasuno NAublin PKono K(2023)Revisiting VM-Agnostic KVM vCPU Scheduler for Mitigating Excessive vCPU SpinningIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.329768834:10(2615-2628)Online publication date: Oct-2023
https://doi.org/10.1109/TPDS.2023.3297688
Vepuri NJiang X(2023)Performance Analysis of Virtual Machine Monitoring System2023 IEEE Green Energy and Smart Systems Conference (IGESSC)10.1109/IGESSC59090.2023.10321757(1-6)Online publication date: 13-Nov-2023
https://doi.org/10.1109/IGESSC59090.2023.10321757
Jia WZhang JShan JLi JDing XGavrilovska AAltınbüken DBinnig C(2022)Achieving low latency in public edges by hiding workloads mutual interferenceProceedings of the 13th Symposium on Cloud Computing10.1145/3542929.3563459(477-492)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3542929.3563459
Ishiguro KYasuno NAublin PKono KTitzer BXu HZhang I(2021)Mitigating excessive vCPU spinning in VM-agnostic KVMProceedings of the 17th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments10.1145/3453933.3454020(139-152)Online publication date: 7-Apr-2021
https://dl.acm.org/doi/10.1145/3453933.3454020
Schildermans SShan JAerts KJackrel JDing X(2021)Virtualization Overhead of Multithreading in X86 State-of-the-Art & Remaining ChallengesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.306470932:10(2557-2570)Online publication date: 1-Oct-2021
https://doi.org/10.1109/TPDS.2021.3064709
Fan HWu SZhao XXie ZDi SXiao JYu CJin H(2021)Accelerating Parallel Applications in Cloud Platforms via Adaptive Time-Slice ControlIEEE Transactions on Computers10.1109/TC.2020.299961970:7(992-1005)Online publication date: 1-Jul-2021
https://doi.org/10.1109/TC.2020.2999619
Jia WShan JLi TShang XCui HDing XGavrilovska AZadok E(2020)vSMT-IOProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489176(449-463)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489176
Kim TPark CHuh JAhn J(2020)Reconciling Time Slice Conflicts of Virtual Machines With Dual Time Slice for CloudsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2020.299325231:10(2453-2465)Online publication date: 1-Oct-2020
https://doi.org/10.1109/TPDS.2020.2993252
Zhao YSuo KWu XRao JWu SJin HWeissman JButt ASmirni E(2019)Preemptive Multi-Queue Fair QueuingProceedings of the 28th International Symposium on High-Performance Parallel and Distributed Computing10.1145/3307681.3326605(147-158)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3307681.3326605
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents