Download 2008-Friebel-LHP-GI_OS.pdf

Contents : How to Deal with Lock Holder Preemption Extended Abstract Thomas Friebel and Sebastian Biemueller Advanced Micro Devices Operating System Research Center http://amd64.org/research 1 Introduction Spinlocks are a synchronization primitive widely used in current operating system kernels. With spinlocks a thread waiting to acquire a lock waits actively monitoring the lock. With sleeping locks in contrast a waiting thread blocks yielding the CPU to other threads. While sleeping locks seem to provide better functionality and overall system performance there are cases in which spinlocks are the better alternative. First under some circumstances like in interrupt handler top halves blocking is not feasible. Second saving and restoring a thread s state as sleeping locks do when yielding the CPU costs time. If the lock-protected critical section is very short waiting for the lock to be released o ers better performance. In both cases spinlocks provide advantages over sleeping locks. But spinlocks are used for very short critical sections only to avoid wasting CPU time waiting actively. Spinlocks are built on the assumption that a lock-holding thread is not preempted. In a virtualized environment this assumption is no longer true. Virtual machine monitors (VMMs) schedule virtual CPUs (VCPUs) on physical CPUs for time slices to achieve pseudo-parallel execution. At the end of a time slice the current VCPU is preempted the VCPU state is saved and the next VCPU starts executing. If a VCPU is preempted inside the guest kernel while holding a spinlock this lock remains acquired until the VCPU is executed again. This problem is called lock-holder preemption identi ed and analyzed by Uhlig et al. 3 for a paravirtualized version of Linux 2.4 running on top of an L4 microkernel. This work investigates the in uence of lock-holder preemption in the Xen hypervisor a commodity virtualization system. We show that lock-holder preemption can have a severe performance impact in today s systems. Furthermore we describe two approaches to counteract the performance degradation give some details on our implementation of one of the approaches and show that we are able to fully prevent any performance degradation caused by lock-holder preemption. 2 Spinlocks and Virtualization Lock-holder preemption describes the situation when a VCPU is preempted inside the guest kernel while holding a spinlock. As this lock remains acquired during the preemption any other VCPUs of the same guest trying to acquire this lock will have to wait until the VCPU is executed again and releases the lock. Lock-holder preemption is possible if two or more VCPUs run on a single CPU concurrently. Furthermore the more VCPUs of a guest run in parallel the more VCPUs have to wait if trying to acquire a preempted lock. And as spinlocks imply active waiting the CPU time of waiting VCPUs is simply wasted. Traditionally virtualization systems do not handle spinlocks in a special way. But as multi- and many-core machines are becoming more and more common the impact of lock-holder preemption grows. Table 1 shows execution times and spinlock wait times for kernbench a Linux kernel compilation benchmark running under Xen 3.1 on a 4-socket 16-core machine. In the single-guest setup a single 16-VCPU guest is running on the host system and executing kernbench. Here lock-holder preemption is very unlikely as each VCPU can run on a distinct CPU and thus no preemption is necessary. The two-guests setup introduces a second 16-VCPU guest running a CPU-bound job without any I/O. We simply used 16 processes executing an endless loop. This results in an overcommited system provoking lock-holder preemption. Table 1 shows an 8.8-second increase in time spent waiting for a spinlock. The kernbench execution time increases by 7.6 seconds or 7.0 %. Setup Single guest Two guests Guest time s 109.0 117.3 (+7.6) Time spent spinning s 0.2 (0.2 %) 9.0 (7.6 %) Table 1. Performance numbers for kernbench i) as a single VM and ii) in an overcommited system running the kernbench VM and a CPU-bound VM concurrently to cause lock-holder preemption. To analyze the behavior of Linux spinlocks in more detail we instrumented the spinlock code to collect histogram information of spinlock wait times. Figure 1 shows the distribution of number of waits over their time spent waiting. Most of the waits (97.8 %) do not take longer than 216 CPU cycles. A second small fraction of waits taking between 224 and 226 cyles occurs only in the two-guests setup. These newly introduced waits match Xen s time slice length of 30 ms and show lock-holder preemption: The VCPUs of the CPU-bound guest always run for complete time slices as they do not block for I/O. Therefore a lock-holder preempted by a CPU-bound VM will keep the lock for at least a complete time slice. Any other VCPUs trying to acquire that lock will busy wait for at least a part of their time slice

INFO HASH : 7771217fbcf2e4f525cf65bec498cc7353fa68cf

Download now

File Size: 69.8 kb