[kernel/locking] spinlock (2) - Test And Set, Ticket, ABQL, MCS

[kernel/locking] - spinlock(1)

 

앞선 글에서, 아키텍처에 종속적인 부분을 제외하고 spinlock을 어떻게 사용하는지 이야기해보았다. 실제 아키텍처별로 구현된 spinlock 구현체를 보려면 일단 spinlock에 대한 개념들이 더 필요하므로 개념을 짚고 넘어가겠다.

Test And Set (TAS)

spinlock의 기본적인 구현은 lock을 획득할 수 있을 때까지 loop를 도는 Test And Set lock이라고 할 수 있다

// Test and Set lock pseudocode
while (test_and_set(lock) == FAILED) {
	// spin
}

// 위의 while문이 끝나면 lock을 획득했다는 것이 보장된다.

여기서 test_and_set이란, 현재 lock이 획득 가능한 상태인지 확인하고, 가능한 경우 lock을 획득하는 함수이다. 이 함수가 성공할 때까지 무작정 루프를 도는 것이다. 이때 루프를 도는 것을 보통 spin한다고 한다. test_and_set은 물론 원자적 연산이다! 이 연산 도중에는 레이스 컨디션이 발생하지 않는다.

 

TAS는 원자적 연산을 통해서 lock을 획득하기 때문에 레이스 컨디션은 발생하지 않지만, 불공정하게 락을 획득하므로 starvation이 발생할 수 있다. 쉽게말해서 프로세스 A, B가 경쟁하고 있을 때, A가 2번 연속 락을 획득하는 것이 구현상 가능하다. 그리고 이 상황은 B에게 매우 불공정하다.

Ticket Lock

ticket lock은 말 그대로 번호표를 먼저 받고, 그 순서대로 락을 획득해서 공정성을 보장하는 매커니즘이다.

/* Yan Solihin's pseudocode for ticket lock */

/* 락을 처음 만들 때 초기화하는 함수 */
ticketLock_init(int *next_ticket, int *now_serving)
{
    *now_serving = *next_ticket = 0;
}

/* 내 번호표를 뽑고, 내 번호표의 차례가 될때까지 기다린다 */
ticketLock_acquire(int *next_ticket, int *now_serving)
{
    my_ticket = fetch_and_inc(next_ticket);
    while (*now_serving != my_ticket) {}
}

/* 번호표를 반납하는 함수 */
ticketLock_release(int *now_serving)
{
    ++*now_serving;
}

pseudocode를 보면 매우 단순하다. 티켓 번호를 받고, 티켓을 받은 순서대로 락을 획득함이 보장된다. 예를 들어서 프로세스 A, B가 순서대로 ticketLock_acquire를 호출하면, 다음과 같은 순서로 진행된다.

 

1. 프로세스 A가 my_ticket = 0인 ticket을 받는다.

2. 프로세스 B가 my_ticket = 1인 ticket을 받는다.

3. 현재 ticket lock의 now_serving = 0이므로 ticket 번호가 0인 A가 lock을 획득한다.

4. A가 락을 다시 반납하면 now_serving = 1이 된다.

5. 현재 ticket lock의 now_serving = 1이므로 ticket 번호가 1인 B가 lock을 획득한다.

...반복...

 

ticket lock은 공정성을 제공한다는 장점이 있지만, 프로세서가 많아지면 많아질수록 성능이 떨어지므로 scalable하지 못하다, 그그리고 cache invalidation으로 인한 엄청난 성능 저하가 발생한다. (이건 물론 TAS에도 해당되는 말이다.)

 

cache invalidation에 대해 간단히 설명하면, ticket lock에서 여러 개의 프로세서가 spin중이라면, 이 프로서세들은 모두 now_serving 변수에 접근중이다. 이 때, 하나의 프로세서가 락을 획득해서 now_serving++;을 실행하면 나머지 모든 프로세서가 각각의 캐시에 갖고 있는 now_serving 값이 유효하지 않게 되므로 (invalidation) 이 값을 갱신해줘야 한다. 따라서 성능 저하가 발생한다. 다시 말해서 ticket lock은 cache를 동기화하는 데 많은 오버헤드가 발생한다.

Array Based Queuing Locks (ABQL)

앞서 언급한 cache 동기화 문제의 근본적인 문제는 여러개의 프로세서가 동시에 하나의 변수에 spin한다는 것이다. 이 문제를 해결하는 방법은 각각의 프로세서가 local variable에 spin하도록 하고, lock을 반납하는 프로세서가 다음에 lock을 획득할 프로세서에게 차례를 넘기면, 하나의 프로세서에 대해서만 cache invalidation이 발생하게 된다. 따라서 ABQL은 공정하며, 앞서 말한 캐시 동기화 문제를 해결한다.

/* pseudocode for Array-Based Queueing Locks */

/* 락 초기화 */
ABQL_init(int *next_ticket, int *can_serve)
{
  *next_ticket = 0;
  for (int i = 1; i < MAXSIZE; i++)
    can_serve[i] = 0;
  can_serve[0] = 1; 
}

/*
	락을 획득하는 함수
    Ticket lock에서는 now_serving 변수 하나만 존재했지만,
	ABQL에선 ticket별로 각각의 변수가 존재한다. (can_serve 배열)
    
    can_serve[*my_ticket]이 1이 되면 락을 획득한게 된다.
*/
ABQL_acquire(int *next_ticket, int *can_serve)
{
  *my_ticket = fetch_and_inc(next_ticket);
  while (can_serve [*my_ticket] != 1) ; 
}

/*
	락을 반환하는 함수
    내 다음 차례의 프로세서가 spin하고 있는 변수를 1로 바꾼다 (락을 넘긴다)
    그리고 내 락을 반환한다.
*/
ABQL_release (int *can_serve)
{
  can_serve[*my_ticket + 1] = 1;
  can_serve[*my_ticket] = 0; // prepare for next time
}

 

MCS Lock

MCS는 사람 이름(Mellor-Crummey and Scott)이고, ABQL이 array 기반이라면 MCS는 list 기반이다. 원리는 크게 다르지 않다. 둘다 프로세서별로 자신이 가진 변수에 spin한다. MCS Lock에선 배열 대신 리스트를 사용한다는 점이 다르다.

  type qnode = record
      next : ^qnode
      locked : Boolean
  type lock = ^qnode      // initialized to nil
  
  // parameter I, below, points to a qnode record allocated
  // (in an enclosing scope) in shared memory locally-accessible
  // to the invoking processor
  
  procedure acquire_lock (L : ^lock, I : ^qnode)
      I->next := nil
      // predecessor : 나의 앞 노드
      predecessor : ^qnode := fetch_and_store (L, I) // 큐의 마지막에 새로운 노드 저장하고, 현재 tail을 불러온다.
      if predecessor != nil     // predecessor가 nil이 아니면, 내 앞에 누군가 큐에 대기중임  
          I->locked := true     // 그래서 나는 locked = true로 하고 기다린다.
          predecessor->next := I
          repeat while I->locked  // predecessor가 나한테 넘겨줄때까지 spin 
  
  procedure release_lock (L : ^lock, I: ^qnode)
      if I->next = nil        // successor가 없다면
          if compare_and_store (L, I, nil) // 큐를 비우고 끝낸다
              return
              // compare_and_store가 실패하면 누군가 큐에 들어오고 있는 것임
          repeat while I->next = nil // spin해서 기다린다.
      I->next->locked := false // successor의 lock을 해제한다.

이 외에도 좀더 최적화된 CLH, K42 등이 있다. 이번 글에서는 MCS까지만 소개하고 마치겠다.

 

참고 자료

Test-and-set - Wikipedia

Ticket lock - Wikipedia

Ticket spinlocks

Scalable Synchronization