6-3. Synchronization (3)

중앙대학교 3-2 리눅스 응용 설계 (손용석 교수님) 과목 정리입니다.

Spinlock in Linux Kernel

• spinlock 은 lock을 사용할 수 있는지 반복적으로 확인하는 동안 lock을 획득하려는 thread가 loop에서 대기하도록 하는 lock
• thread가 active한채로 남아있는데 useful task를 수행하지 않기 때문에 spinlock의 사용은 busy waiting의 일종이다.
  • thread는 lock을 사용할 수 있게 될 때까지 계속 spinning
  • 계속되는 반복은 multiprogramming environment 에서 문제가 생길 수 있다.
• Spinlock의 busy waiting은 CPU cycle을 낭비한다.
  • Spinlock은 context switching이 필요 없다. (Mutex 는 필요함)
  • 각 thread가 짧은 시간 동안 lock을 소유하는 경우 사용한다. (short critical section → spinlock 사용)

Ticket Spinlock in Linux Kernel

• lock 경쟁자들은 FIFO 방식으로 lock을 획득한다.
• 공정함

Ticket spinlock primitives

• spin_lock()
  • task는 ticket을 확인하고, 1씩 증가시킨다.
  • owner와 내 ticket을 비교한다.
    • 동일한 경우 lock 획득 → critical section 진입
    • 동일하지 않으면 다른 task가 lock을 갖고 있는 것
• spin_unlock()
  • task는 owner를 증가시킨다.

• spin_lock_init : 주어진 spinlock_t를 초기화
• spin_trylock : lock 획득 시도
  • 성공 → return 1
  • 실패 → return 0
• spin_is_locked
  • lock이 획득되었을 때 return 1
  • 그 외 return 0
• spin_lock
  1. disable preemption
  2. acquire lock
• spin_unlock
  1. lock 해제
  2. enable preemption
• spin_lock_irq
  1. disable local interrupt
  2. disable preemption
  3. acquire lock
• spin_unlock_irq
  1. release lock
  2. enable local interrupts
  3. enable preemption
• spin_lock_irqsave
  1. local interrupts의 현재 state를 flag로 저장
  2. disable local interrupt
  3. disable preemption
  4. acquire lock
• spin_unlock_irqrestore
  1. release lock
  2. flag로부터 이전 local interrupts state 복원하기
  3. enable preemption

Single spin_lock

→ boolean data type을 사용해도 된다.

⇒ but 여러 개의 spinlock에서 문제가 생길 수 있다.

• What if preempt_count is Boolean?
  • 많은 disable operation이 주어져도 하나의 enable operation이 task를 preempt 가능하게 만든다.

lock a가 release 될 때 preempt_count가 0이 되므로 lock b도 동시에 release 되게 된다.

⇒ 여러 개의 spinlock을 사용할 때는 쓸 수 없다.

• preempt_count 는 integer여야 한다.모든 spinlock이 release된 후에 preempt 가능해진다

Disadvantage of spin_lock

• task와 ISR 사이의 race condition을 방지할 수 없다.

• disable preemption은 normal task에서만 가능하다.

1. task 1이 critical section a를 사용 (spin_lock)
2. interrupt 발생 → interrupt에 의해 선점됨
3. ISR이 실행되지만 spin_lock에 의해 lock을 얻을 수 없기 때문에 계속 spinning
4. 마찬가지로 task1도 preemption된 ISR이 끝나지 않으므로 계속 waiting

⇒ deadlock 발생

Usage of spin_lock

• 모든 interrupt가 same critical section을 사용하지 않는다는 것을 알 때만 사용할 수 있다.

spin_lock_irq() in Linux Kernel

• a single spin_lock_irq()
  • spin_lock_irq → disable interrupt & preemption and lock 획득
  • spin_unlock_irq → release lock and enable interrupt & preemptiontask와 interrupt 사이의 race condition을 방지할 수 있다.

Disadvantage of spin_lock_irq()

• Nested spin_lock_irq()

spin_unlock_irq를 하는 순간 interrupt handler가 실행될 수 있다.

but spin_unlock_irq(locka)를 하지 않았기 때문에 실제로는 locka의 critical section 작업이 끝나지 않았음에도 ISR에 의해 선점 가능해진 것

Usage of spin_lock_irq()

• interrupt들이 같은 critical section에 사용되지 않을 때 사용

spin_lock_irqsave()

• spin_lock_irqsave
  1. local interrupt의 current state를 저장
  2. disable interrupt / preemption
  3. acquire lock
• spin_unlock_irqrestore
  1. release lock
  2. 이전 interrupt의 state 복원
  3. enable preemption

The main three ways to acquire spinlocks in Linux Kernel

• spin_lock()
  • performance highest
  • task interrupt 사이의 race condition 보장 X
• spin_lock_irq()
  • 모든 interrupt가 disable 되어 있기 때문에 interactivity, I/O processing , 기타 시스템 성능이 영향을 받음
  • interrupt handler와 task가 spinlock을 공유할 때 사용
  • lock을 해제하면 interrupt가 disable된 횟수에 관계없이 interrupt가 활성화된다.
• spin_lock_irqsave()
  • spin_lock_irq와 동일하지만 interrupt disable 되기 전에 interrupt state를 저장한다.
  • spinlock을 사용할 때, interrupt enable 여부가 확실하지 않을 때 사용
  • state가 저장되므로 spin_lock_irq 보다 느리다.

Ticket Spinlock Structure in Linux Kernel

arch_spinlock_t의 구현은 architecture에 따라 다를 수 있다.

Initializing spinlock in Linux Kernel

spin_lock_init → raw_spin_lock_init

Acquiring spinlocks in Linux Kernel

• spin_lock() - disabling preemption
• spin_lock_irq() - disabling interrupt & preemption
• spin_lock_irqsave()

Analyzing spin_lock()

• __raw_spin_lock
  • preempt_disable → 선점 불가 : preempt_count 증가

Analyzing spin_unlock()

preempt_enable() → 선점 가능하도록 설정

architecture에 따라서 arch_spin_unlock의 구현은 다를 수 있다.

Analyzing spin_lock_irq() and spin_unlock_irq()

• spin_lock_irq
  • local_irq_disable() : interrupt 비활성화. preempt_count 증가
• spin_unlock_irq
  • local_irq_enable() : interrupt 활성화. preempt_count 감소

Analyzing spin_lock_irqsave()

• interrupt state 저장
• interrupt 비활성화
• preempt_count 증가

spin_unlock_irqrestore()

• interrupt state 복원
• prempt_count 감소

ARM Architecture