How to Deal with Lock Holder Preemption

How to Deal with Lock Holder Preemption

notion에서 보기 

---

1. Introduction

spinlocks

• 운영체제 커널에서 많이 사용되는 synchronization 기법
• 스레드가 계속해서 lock을 모니터링하며 lock을 얻기 위해 대기한다.

spinlock for better alternatives

• interrupt handler에서 blocking이 안되는 경우
• context switching 이 시간을 많이 소요하는 경우**해당 프로세스가 CS를 아주 잠깐 사용하여 context switching이 실제 CS 사용 시간보다 길면 비효율적이기 때문에 그 잠깐 동안 spin을 하면서 대기 한다.
• → 기다리는 프로세스를 sleep 시키지 않고 spinning하면서 대기시킨다.

spinlock in virtualized environment

• 락을 소유한 스레드는 preemption되지 않는다.
• → 가상화 환경에서는 적용되지 않는다.
• vCPU가 pesudo-parallel execution을 할때 pCPU에서 하나의 프로세스로 타임퀀텀을 갖는다. 타임퀀텀이 끝나면 vCPU가 선점당하고 진행중이던 상태 saving하고 다음 vCPU가 실행된다.

lock holder preemption problem

• 게스트 커널 내부에서 vCPU가 spinlock을 가진 상태로 선점 당한다. 그러면 해당 vCPU가 다시 스케줄링되어 실행되기 전까지 spinlock을 계속 가지고 있게되어 그 동안 다른 vCPU가 락을 가질 수 없게 된다.
• 다른 vCPU는 타임퀀텀을 다 소모해서 선점당했지만 여전히 spinlock을 가지고 있는 vCPU가 다시 실행되어 lock을 반납할때까지 기다려야 한다.
• spinlock = active waiting
• → vCPU를 기다리는 시간 낭비됨
• CPU bound vCPU에 의해 선점되는 lock은 최소한 주어진 타임퀀텀까지는 유지된다.⇒ 대부분의 대기 시간은 lock holder preemption에 의해 발생되는 대기들에 의해 생긴다. (spinlock을 기다리는데 소모되는 시간)
• → lock을 기다리는 다른 vCPU는 spnning (busy waiting)하면서 최소한 그 시간동안은 기다린다.

2. Spinlocks and Virtualization

• lock holder preemption 문제는 두 개 이상의 vCPU가 하나의 pCPU에서 동시 실행될 경우에 발생한다.
• multi-core machine의 발전으로 lock holder preemption이 성능에 미치는 영향이 커졌다.
• single VM vs overcommitted VM→ single VM의 경우 각 vCPU가 개별 pCPU에서 실향될 수 있기 때문에 preemption이 거의 발생하지 않는다.
• → overcommitted 환경에서의 preemption을 측정하기 위해 입출력 없는 CPU bound 프로세스를 실행시킨 16-vCPU guest를 사용했다. 그 결과 spinlock을 기다리는데 소모한 시간이 8.8초나 증가했다.
•  
• histogram of waiting time for a spin lock→ 대부분의 대기 시간은 2^16 CPU cycle을 넘지 않고, 일부 two-guest 상태에서 발생하는 대기 시간만 오래걸린다.→ 그러니까 선점당한 락 소유 CPU는 최소한 주어진 타임퀀텀만큼 lock을 가지고 있게 되고, 락을 얻으려 하는 다른 vCPU들은 최소한 타임퀀텀만큼 spin을 하며 대기해야 한다.
• → CPU-bound guest의 vCPU는 항상 타임퀀텀을 다 채워서 실행하게 한다.
•  
• histogram of spinlock wait time→ 대부분의 대기 시간은 lock holder preemption에 의해 발생하는 것이다.
•  

3. Tolerating Lock Holder Preemption

To aviod lock holder preemption overhead

instrumenting the guest OS

• spinlock은 오직 커널 내부에서만 사용된다.
• 커널 내부는 거의 항상 하나 이상의 spinlock을 가지고 있다.
• spinlock은 커널을 떠나기 전에 해제한다.

⇒ user space로 반환되기 전까지 kernel space에서 실행되는 vCPU의 preemption을 지연시킬 수 있다.

tolerating lock holder preemption

• 불필요한 spinning을 방지한다.
• 긴 대기(unusually long wait)를 탐지하여 lock holder preemption에 걸리지 않을 것 같은 vCPU로 바꿔야 한다.→ hypercall은 동일한 게스트에서 다른 vCPU를 스케줄링하게 한다. 특히 커널 모드에서 선점되 vCPU는 preempted lock holder가 될 가능성이 높기 때문에 선호한다.
• → VM에게 unusually long wait를 알리기 위해 spinlock backoff 코드를 확장하여 특정 threshold보다 오래 대기할때 hypercall을 발생시키도록 한다.
• preempted lock holder가 critical section을 빨리 끝내 lock을 풀 수 있도록 돕는다.

4. FIFO Ticket spinlocks

• fairness 개선된 버전
• lock에 도착한 순서대로 스레드에 lock을 할당한다.
• lock 경쟁이 있을 때 FIFO 대로 다음 스레드에게 lock을 넘긴다.
• 실행 시간을 개선시킨다.
•