Preemptable Ticket Spinlocks: Improving
Consolidated Performance in the Cloud
Jiannan Ouyang
Department of Computer Science
University of Pittsburgh
Pittsburgh, PA 15260
ouyang@cs.pitt.edu
John R. Lange
Department of Computer Science
University of Pittsburgh
Pittsburgh, PA 15260
jacklange@cs.pitt.edu
Abstract
When executing inside a virtual machine environment, OS level
synchronization primitives are faced with significant challenges
due to the scheduling behavior of the underlying virtual machine
monitor. Operations that are ensured to last only a short amount of
time on real hardware, are capable of taking considerably longer
when running virtualized. This change in assumptions has signif-
icant impact when an OS is executing inside a critical region that
is protected by a spinlock. The interaction between OS level spin-
locks and VMM scheduling is known as the Lock Holder Preemp-
tion problem and has a significant impact on overall VM perfor-
mance. However, with the use of ticket locks instead of generic
spinlocks, virtual environments must also contend with waiters be-
ing preempted before they are able to acquire the lock. This has
the effect of blocking access to a lock, even if the lock itself is
available. We identify this scenario as the Lock Waiter Preemption
problem. In order to solve both problems we introduce Preemptable
Ticket spinlocks, a new locking primitive that is designed to enable
a VM to always make forward progress by relaxing the ordering
guarantees offered by ticket locks. We show that the use of Pre-
emptable Ticket spinlocks improves VM performance by 5.32X on
average, when running on a non paravirtual VMM, and by 7.91X
when running on a VMM that supports a paravirtual locking inter-
face, when executing a set of microbenchmarks as well as a realistic
e-commerce benchmark.
Categories and Subject Descriptors D.4.1 [Process Manage-
ment]: Mutual exclusion
Keywords Virtual Machines; Lock Holder Preemption; Paravirtu-
alization
1. Introduction
Synchronization has long been recognized as a source of bottle-
necks in SMP and multicore operating systems. With the increased
use of virtualization, multi-core CPUs, and consolidated Infrastruc-
ture as a Service (IaaS) clouds this issue has become more sig-
nificant due to the Lock Holder Preemption problem [15]. Lock
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. To copy otherwise, to republish, to post on servers or to redistribute
to lists, requires prior specific permission and/or a fee.
VEE’13, March 16–17, 2013, Houston, Texas, USA.
Copyright
c
2013 ACM 978-1-4503-1266-0/13/03. . . $15.00
holder preemption occurs whenever a virtual machine’s (VM’s) vir-
tual CPU (vCPU) is scheduled off of a physical CPU while a lock
is held inside the VM’s context. The result is that when the VM’s
other vCPUs are attempting to acquire the lock they must wait until
the vCPU holding the lock is scheduled back in by the VMM so it
can release the lock. As kernel level synchronization is most often
accomplished using spinlocks, the time spent waiting on a lock is
wasted in a busy loop. While numerous attempts have been made to
address this problem, the solutions have targeted only generic spin-
lock behaviors and not more advanced locking primitives such as
ticket spinlocks (spinlocks that ensure consistent ordering of acqui-
sitions). As a result of the introduction of ticket spinlocks virtual
machine synchronization now must contend not only with Lock
Holder Preemption but also Lock Waiter Preemption.
Ticket spinlocks [9] are a form of spinlock that enforces or-
dering among lock acquisitions. Whenever a thread of execution
attempts to acquire a ticket spinlock it either (1) acquires the lock
immediately, or (2) is granted a ticket which determines the order
among all outstanding lock requests. The introduction of ticket
spinlocks was meant to ensure fairness and prevent starvation
among competing threads by preventing any single thread from
obtaining a lock before another thread that requested it first. In this
manner each thread must wait to acquire a lock until after it has
been held by every other thread that previously tried to acquire
it. This ensures that a given thread is never preempted by another
thread while trying to acquire the same lock, and thus guarantees
that well behaved threads will all acquire the lock in a timely man-
ner.
While ticket spinlocks have been shown to provide advantages
to performance and consistency for native OS environments, they
pose a new challenge for virtualized environments. This is due
to the fact that when running inside a VM, the use of a ticket
spinlock can result in multiple threads waiting to acquire a spinlock
that is currently available. This problem exists whenever a VMM
preempts a waiter that has not yet acquired the lock. In this case
even if the lock is released, no other thread is allowed to acquire it
until the next waiter is allowed to run, resulting in a scenario where
there is contention over an idle resource. We denote this situation
as the Lock Waiter Preemption problem.
Lock holder preemption has traditionally been addressed using
a combination of configuration, software and hardware techniques.
Initial workarounds to the lock holder preemption problem required
that every vCPU belonging to a given VM be gang scheduled in or-
der to avoid this problem altogether [16]. While this eliminates the
lock holder preemption problem, it does so in a way that dramat-
ically reduces the amount of possible consolidation and increases
the amount of cross VM interference. As a result of these draw-
backs, several attempts have been made to address the lock holder