Jiannan Ouyang
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 significant impact when an OS is executing inside a critical region that is protected by a spinlock. The interaction between OS level spinlocks and VMM scheduling is known as the Lock Holder Preemption problem and has a significant impact on overall VM performance. However, with the use of ticket locks instead of generic spinlocks, virtual environments must also contend with waiters being 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 Preemptable 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 interface, when executing a set of microbenchmarks as well as a realistic e-commerce benchmark.
- Hackbench, 2008. http://people.redhat.com/mingo/cfs-scheduler/tools/hackbench.c/.Google Scholar
- Ebizzy 0.30, 2009. http://sourceforge.net/projects/ebizzy/.Google Scholar
- Kernbench 0.50, 2009. http://freecode.com/projects/kernbench.Google Scholar
- Dell dvd store database test suite 2.1, December 2010. http://linux.dell.com/dvdstore/.Google Scholar
- Chen, P. M., and Noble, B. D. When virtual is better than real. In The 8th Workshop on Hot Topics in Operating Systems (HotOS-VIII) (2001). Google ScholarDigital Library
- Friebel, T. How to deal with lock-holder preemption. Presented at the Xen Summit North America, July 2008.Google Scholar
- He, B., Scherer, W., and Scott, M. Preemption adaptivity in time-published queue-based spin locks. In High Performance Computing HiPC 2005, D. Bader, M. Parashar, V. Sridhar, and V. Prasanna, Eds., vol. 3769 of Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 2005, pp. 7--18. Google ScholarDigital Library
- McKenney, P., and Slingwine, J. Read-copy update: Using execution history to solve concurrency problems. In Parallel and Distributed Computing and Systems (1998), pp. 509--518.Google Scholar
- Mellor-Crummey, J., and Scott, M. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems (TOCS) 9, 1 (1991), 21--65. Google ScholarDigital Library
- Mellor-Crummey, J., and Scott, M. Synchronization without contention. ACM SIGPLAN Notices 26, 4 (1991), 269--278. Google ScholarDigital Library
- Ousterhout, J. Scheduling techniques for concurrent systems. In Proceedings of the 3rd International Conference on Distributed Computing Systems (1982), pp. 22--30.Google Scholar
- Raghavendra, K., and Fitzhardinge, J. Paravirtualized ticket spinlocks, May 2012.Google Scholar
- Riel, R. v. Directed yield for pause loop exiting, 2011.Google Scholar
- Sukwong, O., and Kim, H. S. Is co-scheduling too expensive for smp vms? In Proceedings of the sixth conference on Computer systems (New York, NY, USA, 2011), EuroSys '11, ACM, pp. 257--272. Google ScholarDigital Library
- Uhlig, V., LeVasseur, J., Skoglund, E., and Dannowski, U. Towards scalable multiprocessor virtual machines. In Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium - Volume 3 (Berkeley, CA, USA, 2004), VM'04, USENIX Association, pp. 4--4. Google ScholarDigital Library
- VMware, I. Vmware(r) vsphere(tm): The cpu scheduler in vmware esx(r) 4.1, 2010.Google Scholar
- Wells, P. M., Chakraborty, K., and Sohi, G. S. Hardware support for spin management in overcommitted virtual machines. In Proceedings of the 15th international conference on Parallel architectures and compilation techniques (New York, NY, USA, 2006), PACT '06, ACM, pp. 124--133. Google ScholarDigital Library
- Weng, C., Liu, Q., Yu, L., and Li, M. Dynamic adaptive scheduling for virtual machines. In Proceedings of the 20th international symposium on High performance distributed computing (New York, NY, USA, 2011), HPDC '11, ACM, pp. 239--250. Google ScholarDigital Library
- Zhang, L., Chen, Y., Dong, Y., and Liu, C. Lock-visor: An efficient transitory co-scheduling for mp guest. In Proceedings of the 41st International Conference on Parallel Processing (Pittsburgh, PA, USA, 2012), pp. 88--97. Google ScholarDigital Library
Index Terms
- Preemptable ticket spinlocks: improving consolidated performance in the cloud
Recommendations
Preemptable ticket spinlocks: improving consolidated performance in the cloud
VEE '13When 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 ...
A lock-aware virtual machine scheduling scheme for synchronization performance
In virtualized environments, multiprocessor virtual machines encounter synchronization problems such as lock holder preemption (LHP) and lock waiter preemption (LWP). When the issue happens, a virtual CPU (VCPU) waiting for such locks spins for an ...
Optimizing virtual machines using hybrid virtualization
Minimizing virtualization overhead and improving the reliability of virtual machines are challenging when establishing virtual machine cluster. Paravirtualization and hardware-assisted virtualization are two mainstream solutions for modern system ...
Comments