Gleaner: Mitigating the Blocked-Waiter Wakeup Problem for Virtualized Multicore Applications

Xiaoning Ding, Phillip B. Gibbons, Michael A. Kozuch, Jianchen ShanUSENIX ATC 2014 · OpenReview

TL;DR

Virtualized multicore systems face a hidden performance bottleneck called the Blocked-Waiter Wakeup (BWW) problem, where synchronization-induced idling of virtual CPUs (vCPUs) incurs significant overhead due to hypervisor interventions. This paper introduces Gleaner, a novel approach that combines resource retention and consolidation scheduling to mitigate BWW, leading to substantial performance improvements for virtualized applications.

What Problem Does This Paper Address?

As multicore processors become increasingly prevalent, virtualized environments are expected to scale applications to leverage these abundant resources. While the "Lock-Holder Preemption" problem (where a thread holding a lock is preempted) has been well-studied and addressed, this paper highlights a related but distinct issue: the "Blocked-Waiter Wakeup" (BWW) problem. BWW arises when a thread in a virtualized environment blocks on a synchronization primitive (like a mutex). In a physical system, an idle CPU can enter a low-power state and be quickly woken up. However, in a virtualized setting, a blocked vCPU is not just idle; it's often descheduled by the hypervisor. Waking up this vCPU requires a VM trap, hypervisor intervention, and rescheduling onto a physical CPU (pCPU). This process is significantly more costly than on bare metal, leading to increased execution times, reduced throughput, and performance unpredictability, especially as the number of cores increases. The paper aims to quantify this problem and propose an effective solution.

Methods

The paper proposes Gleaner, a hybrid approach to mitigate the BWW problem. Gleaner combines two key techniques:

  • Resource Retention: This involves modifying how idle periods are handled. Instead of immediately yielding resources, Gleaner aims to keep vCPUs active for short periods. This can be achieved through techniques like yielding threads that call sched_yield() in a loop, or by leveraging hardware instructions like MWAIT to allow CPUs to enter low-power states that can be quickly exited. The goal is to avoid the costly vCPU descheduling and rescheduling by the hypervisor for brief idleness.
  • Consolidation Scheduling: This technique focuses on reducing the number of active vCPUs by consolidating workloads onto fewer cores. This is particularly useful when applications have long idle periods that resource retention alone cannot efficiently manage. By consolidating threads onto fewer vCPUs, Gleaner aims to make better use of the remaining active vCPUs and reduce the overall number of vCPUs that might enter costly idle states.

Gleaner implements these techniques at the user level within the guest OS to avoid intrusive kernel modifications, making it more widely adoptable. It dynamically adjusts the number of active vCPUs based on workload characteristics like computation length (Icomp), computation granularity (gcomp), and idle period length (lidle).

Datasets

The paper evaluates Gleaner using standard benchmarks from the PARSEC 3.0 suite and the SPLASH2X suite. They also use SysBench with an OLTP workload to simulate MySQL server performance. No new benchmarks were introduced; instead, the focus was on evaluating existing benchmarks under various virtualization scenarios.

Key Insights and Ideas

  • The Hidden Cost of Idling: The paper reveals that the cost of a vCPU entering and exiting an idle state in a virtualized environment is significantly higher than previously understood, especially when compared to physical systems. This "Blocked-Waiter Wakeup" problem is a major performance bottleneck for multicore virtualized applications.
  • BWW as the Dual of LHP: The authors frame BWW as the inverse of the Lock-Holder Preemption problem, highlighting that while LHP deals with preempted lock holders, BWW deals with the cost of waking up threads that were waiting for a lock.
  • User-Level Implementation is Key: By implementing Gleaner at the user level, the authors achieve a solution that can be adopted without modifying the guest OS kernel or the hypervisor, making it practical for real-world deployment.
  • Consolidation and Retention Synergy: The hybrid approach of combining resource retention for short idles and consolidation scheduling for longer ones proves more effective than either technique alone.
  • Performance vs. Throughput Trade-off: While Gleaner primarily aims to improve application performance, it can sometimes lead to a slight decrease in system throughput for certain types of synchronization (e.g., barrier synchronization), indicating a nuanced trade-off that Gleaner attempts to balance.

Key Results

  • Significant Performance Improvements: Gleaner can reduce virtualization-induced slowdowns by up to 16x for individual applications (e.g., dedup).
  • Average Speedup: On average, Gleaner provides a 203% speedup for PARSEC and SPLASH2X benchmarks on a 16-vCPU VM.
  • System Throughput Improvement: Gleaner can improve system throughput by up to 3x in scenarios with high vCPU switch overhead, such as with MySQL OLTP workloads.
  • Reduced Performance Variation: Gleaner helps to reduce performance variations between VMs sharing resources, especially for synchronization-intensive applications.
  • Energy Consumption: While Gleaner might slightly increase energy consumption due to yielding threads, the overall reduction in execution time often leads to a net decrease in energy consumption for many benchmarks. On average, it reduces energy consumption by 5% for PARSEC and 1% for SPLASH2X.

Limitations and Future Work

  • User-Level Limitations: The paper acknowledges that a user-level implementation might not always be able to detect concurrency level changes as quickly as a kernel-level solution, potentially leading to slightly increased execution times for some workloads.
  • I/O Latency: The authors suggest future work to extend Gleaner's approach to address vCPU state transitions caused by operations other than blocking synchronization, such as I/O waits, which can also double I/O latency.
  • Dynamic Workload Changes: Gleaner's dynamic adjustment of active vCPUs is designed to handle workload changes, but further research could explore more sophisticated prediction mechanisms for workload behavior.
  • Tuning Parameters: The effectiveness of Gleaner relies on tunable parameters (p and η). While the paper provides guidance, further exploration of optimal tuning strategies for diverse workloads could be beneficial.

Summary updated

BibTeX
@inproceedings{ding2014gleaner,
  author = {Xiaoning Ding and Phillip B. Gibbons and Michael A. Kozuch and Jianchen Shan},
  title = {{Gleaner: Mitigating the Blocked-Waiter Wakeup Problem for Virtualized Multicore Applications}},
  booktitle = {USENIX ATC},
  year = {2014},
  url = {https://openreview.net/forum?id=6TL9A9XL9D},
}
Figure