동기화와 lock

1. Critical section과 Race condition

• 공유 메모리를 사용하는 애플리케이션을 개발할 때는 서로 다른 두 객체가 공유 자원에 동시에 접근하는 race condition을 반드시 막아야 한다.
• Critical section에 동시에 접근하는 것을 막기 위해서는 커널에서 제공하는 다양한 수단(원자적 연산, 스핀락, 세마포어) 원자적인(atomically) 접근을 보장해 race condition을 해소하는 동기화(synchronization)가 필요하다.
• 동기화의 기본적인 동작과정은 다음과 같다.

1. 스레드 A와 B가 critical section에 접근하기 위해 락을 요청한다.
2. 스레드 A가 락을 휙득한다. 스레드 B는 무한루프(busy-waiting) 돌거나 sleep에 들어간다.
3. 스레드 A가 critical section을 처리한다.
4. 스레드 A가 락을 반환한다.
5. 스레드 B가 락을 휙득한다. 스레드 B가 critical section을 처리한다.

• 커널 동기화에는 두 가지를 반드시 염두해야 한다.
  • 커널 동시성 문제가 발생하는 것을 막는 것보다 막아야 한다는 사실을 깨닫는 것이 훨씬 더 어려우므로, 코드의 시작 단계부터 락을 설계해야 한다.
  • 락을 설정하는 대상은 ‘코드 블록’이 아니라 ‘데이터’다.

2. 데드락 (Deadlock)

• 데드락은 실행 중인 2개 이상의 스레드와 2개 이상의 자원에 대해 발생하는 심각한 동기화 오류로, 각 스레드가 서로가 갖고 있는 자원을 기다리고 있지만, 모든 자원이 이미 점유된 상태라 옴싹달싹 못하는 상태를 말한다.
• 데드락을 예방하기 위해서는 3가지 규칙을 준수하자.
  • 락이 중첩되는 경우 항상 같은 순서로 락을 얻고, 반대 순서로 락을 해제한다.
  • 같은 락을 두 번 얻지 않는다.
  • 락의 갯수나 복잡도 면에서 단순하게 설계한다.

3. 동기화 수단 1: 원자적 연산

• 리눅스 커널은 지원하는 모든 아키텍처에 대해 원자적 정수 연산과 비트 연산을 제공한다.
• 원자적 연산은 이름 그대로 연산을 하는 동안 다른 프로세서, 프로세스, 스레드가 접근하지 못함을 보장한다.
• 원자적 연산은 int 대신 특별한 자료구조인 atomic_t를 사용한다. (<linux/types.h>에 정의)

1. 다른 자료형에 원자적 연산을 잘못 사용하는 것을 막을 수 있기 때문이다.
2. 컴파일러가 개발자의 의도와 다르게 최적화하는 것을 막을 수 있기 때문이다.

• 대표적인 몇 가지 원자적 정수 연산 함수는 다음과 같다. (<asm/atomic.h>에 정의)
  • atomic_set(&var, num): atomic_t형 변수 var을 num으로 초기화한다.
  • atomic_add(num, &var): var을 num을 더한다.
  • atomic_inc(&var): var을 1 증가한다.
• 대표적인 몇 가지 원자적 비트 연산 함수는 다음과 같다. (<asm/bitops.h>에 정의)
  • test_and_set(int n, void *addr): 원자적으로 addr에서부터 n번째 bit를 set하고 이전 값을 반환한다.
  • test_and_clear(int n, void *addr): 원자적으로 addr에서부터 n번째 bit를 clear하고 이전 값을 반환한다.
• 가능하면 복잡한 락 대신 간단한 원자적 연산을 사용하는 것이 성능 면에서 훨씬 좋다.

4. 동기화 수단 2: 스핀락(Spin-lock)

• 간단한 원자적 연산만으로는 복잡한 상황에서는 충분한 보호를 제공할 수 없기 때문에 더 일반적인 동기화 방법인 ‘락’이 필요하다.

• ‘스핀락’이라는 이름대로 이미 사용 중인 락을 얻으려고 할 때 루프를 돌면서 (busy-wait) 기다린다.

• 스핀락은 프로세서 자원을 꽤 소모하므로 단기간만 사용해야 한다.

  DEFINE_SPINLOCK(lock);
  
  // 1. process context
  spin_lock(&lock);
  /***** critical section *****/
  spin_unlock(&lock);
  
  // 2. interrupt handler
  unsigned long flags;
  spin_lock_irqsave(&lock, flags);
  /***** critical section *****/
  spin_unlock_irqrestore(&lock, flags);

• 스핀락은 <linux/spinlock.h>과 <asm/spinlock.h>에 정의되어있다.

• 스핀락은 위와 같은 함수들을 사용해서 lock과 unlock을 하며 인터럽트 핸들러에서도 사용할 수 있다.

• 인터럽트 핸들러 버전은 데드락을 방지하기 위해 로컬 인터럽트를 비활성화하고 복원하는 과정을 포함한다.

5. 동기화 수단 3: 세마포어(Semaphore)

• 이미 사용 중인 락을 얻으려고 시도할 때 busy-wait 하는 게 스핀락이라면, 세마포어는 sleep으로 진입한다.

• 무의미한 루프로 낭비하는 시간이 사라지니 프로세서 활용도가 높아지지만, 스핀락보다 부가 작업이 많다.

  • Sleep 상태 전환, 대기큐 관리, wake-up 등 부가 작업을 처리하는 시간이 락 사용 시간보다 길 수 있기 때문에 오랫동안 락을 사용하는 경우에 적합하다.
  • Sleep 상태로 전환 되므로 인터럽트 컨텍스트에선 사용할 수 없다.
  • 세마포어를 사용할 때는 스핀락이 걸려있으면 안 된다.

• 세마포어는 동시에 여러 스레드가 같은 락을 얻을 수 있도록 사용 카운트를 설정할 수 있다.

• 0과 1로 이루어져 있다면 바이너리 세마포어 또는 뮤텍스(mutex), 그 외는 카운팅 세마포어라 부른다.

  struct semaphore sema;
  sema_init(&sema, count);    // 동적으로 세마포어 생성
  init_MUTEX(&sema);          // 동적으로 뮤텍스 생성
  
  // 세마포어(뮤텍스) 휙득 시도
  if (down_interruptible(&sema)) {
      ...
  }
  /***** Critical Section *****/
  up(&sema);    // 세마포어(뮤텍스) 반환

• 주로 사용하는 세마포어 관련 함수는 위와 같다.

• 특히 down() 함수 보다는 down_interruptible() 함수를 많이 사용하는 것에 주목하자.

• 세마포어(뮤텍스)를 얻을 수 없을 때 sleep에 진입할 때 프로세스 상태는 TASK_INTERRUPTIBLE 또는 TASK_UNINTERRUPTIBLE로 들어갈탠데, 당연히 나중에 세마포어를 휙득할 수 있을 때 깨어나야 하므로 후자를 더 많이 사용한다.

6. 동기화 수단 4: 뮤텍스(Mutex)

• 2.6 커널부터 ‘뮤텍스’ 방식의 락이 구현되었다.

  DEFINE_MUTEX(mu);
  mutex_init(&mu);
  mutex_lock(&mu);
  /* Critical section */
  mutex_unlock(&mu);

• 이 뮤텍스는 바이너리 세마포어와 유사하게 동작하지만, 인터페이스가 더 간단하고, 성능도 더 좋다.

• 뮤텍스를 사용할 수 없는 어쩔 수 없는 경우가 아니라면 세마포어보다는 새로운 뮤텍스를 사용하는 것이 좋다.

7. 동기화 수단 비교

요구사항	권장사항
락 사용시간이 짧은 경우	스핀락 추천
락 사용시간이 긴 경우	뮤텍스 추천
인터럽트 컨텍스트에서 락을 사용하는 경우	반드시 스핀락 사용
락을 얻은 상태에서 sleep 할 필요가 있는 경우	반드시 뮤텍스 사용

8. 선점 비활성화 & 배리어

• 리눅스 커널은 선점형 커널이므로 프로세스는 언제라도 선점될 수 있고 동시성 문제의 원인이 되기도 한다.
• 또한, SMP 환경에서는 프로세서별 변수가 아닌 이상 다른 프로세서가 동시적으로 접근할 수 있다.
• 따라서, 커널은 preempt_disable(), preempt_enable() 함수로 선점 카운터를 제어한다.
• 더 깔끔하고 자주 사용하는 방법으로 get_cpu() 함수를 사용하기도 한다. 프로세서 번호를 반환하면서 커널 선점을 비활성화 한다. 대응하는 함수는 put_cpu() 함수를 사용하면 커널 선점이 활성화된다.
• 동시성 문제는 굉장히 예민한 문제이므로 반드시 개발자의 의도대로 동작하게끔 컴파일러에게 알려야 한다. **성능을 위해 임의로 순서를 바꾸지 말고 코드 순서대로 메모리 I/O가 진행하게끔 컴파일러에게 알리는 명령을 ‘배리어(Barrier)’**라고 한다.
• 커널은 rmb()(메모리 읽기 배리어), wmb()(메모리 쓰기 배리어), barrier()(읽기 쓰기 배리어)를 제공한다.
• 배리어 명령, 특히 마지막 barrier() 명령은 다른 메모리 배리어에 비해 거의 코스트가 없고 상당히 가볍다.

---

참고

• https://product.kyobobook.co.kr/detail/S000000935348