[xv6] Spinlock

글의 참고

- https://github.com/mit-pdos/xv6-public/tree/master

---

글의 전제

- 밑줄로 작성된 글은 강조 표시를 의미한다.

- 그림 출처는 항시 그림 아래에 표시했다.

---

글의 내용

- 개요

: 레이스 컨디션을 막으려면, 즉, `상호 배제`가 되려면 2가지가 보장되어야 한다.

0" 인터럽트
1" 프로세스

: 먼저 완벽한 동기화를 위해서는 하드웨어의 지원이 반드시 필요하다. 인터럽트를 막기 위해서는 인터럽트를 비활성화 시키면 된다. 그리고, 멀티 프로세서 환경이라면, 현재 작업중인 프로세스는 다른 프로세스에게 선점되서는 안된다. 기본적으로 공유 메모리에 대한 `ATOMIC OPERATION` 기능을 통해서 크리티컬 섹션에 동기화가 이루어진다.

 

 

- 소스 분석

: `xv6`에서 `acquire` 함수는 스핀락을 구현한 함수다. 즉, 비지-웨이팅(Busy-waiting) 방식으로 주구장창 lock을 얻을 때 까지, 기다리는 거다. 짧게 기다린다면 좋을 수 있지만, 만약 기다리는 시간이 길어진다면 시스템 성능에 큰 영향을 끼치게 된다. 그래서 `xv6`에서는 `acquire` 말고도 `acquiresleep` 함수를 제공한다. 디스크와 같이 길게 기다려야 하는 작업에서 다른 프로세스 및 스레드에 프로세서를 양보하는 것이다. 

 

: `initlock` 함수는 사실 딱히 설명할 내용이 없다. `struct spinlock` 구조체에서도 볼 수 있지만, `lock` 필드를 제외한 나머지 필드는 디버깅용라고 되어있지만, `cpu` 필드는 사실 디버깅보다는 `locked` 필드와 함께 lock의 중첩이 발생했는지 여부를 판단하는데 아주 중요하다. 

// spinlock.h ... ... // Mutual exclusion lock. struct spinlock {   uint locked;       // Is the lock held?   // For debugging:   char *name;        // Name of lock.   struct cpu *cpu;   // The cpu holding the lock.   uint pcs[10];      // The call stack (an array of program counters)                      // that locked the lock. }; #################################################################################################### // spinlock.c ... ... void initlock(struct spinlock *lk, char *name) {   lk->name = name;   lk->locked = 0;   lk->cpu = 0; } // Acquire the lock. // Loops (spins) until the lock is acquired. // Holding a lock for a long time may cause // other CPUs to waste time spinning to acquire it. void acquire(struct spinlock *lk) {   pushcli(); // disable interrupts to avoid deadlock.   if(holding(lk))     panic("acquire");   // The xchg is atomic.   while(xchg(&lk->locked, 1) != 0)     ;   // Tell the C compiler and the processor to not move loads or stores   // past this point, to ensure that the critical section's memory   // references happen after the lock is acquired.   __sync_synchronize();   // Record info about lock acquisition for debugging.   lk->cpu = mycpu();   getcallerpcs(&lk, lk->pcs); } // Release the lock. void release(struct spinlock *lk) {   if(!holding(lk))     panic("release");   lk->pcs[0] = 0;   lk->cpu = 0;   // Tell the C compiler and the processor to not move loads or stores   // past this point, to ensure that all the stores in the critical   // section are visible to other cores before the lock is released.   // Both the C compiler and the hardware may re-order loads and   // stores; __sync_synchronize() tells them both not to.   __sync_synchronize();   // Release the lock, equivalent to lk->locked = 0.   // This code can't use a C assignment, since it might   // not be atomic. A real OS would use C atomics here.   asm volatile("movl $0, %0" : "+m" (lk->locked) : );   popcli(); } ... ... // Check whether this cpu is holding the lock. int holding(struct spinlock *lock) {   int r;   pushcli();   r = lock->locked && lock->cpu == mycpu();   popcli();   return r; } ... ...

: `acquire` 함수에는 상호 배제 원칙을 지키고 있다. 즉, 인터럽트를 비활성화(`pushcli`)하고, 하나의 프로세스만 크리티컬 섹션에 들어갈 수 있도록 하고 있다(`while(xchg(&lk->locked, 1) != 0)`). `acquire` 함수는 이 내용만 알면 된다. 

 

: 추가적으로 마지막에 `lk->cpu = mycpu(); getcallerpcs(&lk, lk->pcs);` 를 통해서 동기화 관련 문제가 발생했을 때, 어떤 프로세서 및 프로세스 때문에 에러가 발생했는지를 트래킹하기 위해 정보들을 저장하고 있다. 예를 들어, 뒤에서 `holding` 함수를 보겠지만, 가볍게 짚고 넘어가자면, `holding` 함수는 특정 프로세서가 2개의 동일한 락을 잡고 있는지를 검사한다. 이 말은, 해당 프로세서가 `LOCK`을 풀지 않고, 또 다시 `LOCK`을 얻으려고 하는 케이스다. 이러면, 당연히 문제가 된다. 이럴 때는 대비해서 `acquire` 함수는 프로세서에 대한 정보를 저장하고, 문제 발생 시 해당 프로세서에 대한 정보를 출력한다.

 

: `__sync_synchronize`에 대해 알아보자(`holding` 함수는 뒤에서 알아본다). 이 함수는 GCC 빌트-인 함수다. 즉, 특정 컴파일러에 종속적인 함수다. 이 함수는 `메모리 베리어`라는 어려운 개념을 사용한다. 

Built-in Function: `void __sync_synchronize` (...)
   - This built-in function issues a full memory barrier.
....

- 참고 : https://gcc.gnu.org/onlinedocs/gcc/_005f_005fsync-Builtins.html

 

: 이제 `release` 함수를 살펴보자. `release` 함수에서 가장 눈에 뛰는 코드는 `asm volatile("movl $0, %0" : "+m" (lk->locked) : );` 이다. 이 코드는 `acquire`에서 `while(xchg(&lk->locked, 1) != 0)` 의 반대 역할을 한다. 즉, `lk->locked` 변수에 0을 넣는다. 그런데, `xchg`를 사용하지 않아도 되는건가? `xv6`에서는 아래와 같이 설명한다.

....
The function release (1602) is the opposite of acquire: it clears the debugging fields and then releases the lock. The function uses an assembly instruction to clear locked, because clearing this field should be atomic so that the xchg instruction won’t see a subset of the 4 bytes that hold locked updated. The x86 guarantees that a 32-bit `movl` updates all 4 bytes atomically. Xv6 cannot use a regular C assignment, because the C language specification does not specify that a single assignment is atomic.
....

- 참고 : xv6 - DRAFT as of September 4, 2018

: C 언어 스펙에는 일반적인 할당 연산이 원자적임을 보장한다는 내용은 존재하지 않는다. 그러나, x86에서 32비트 `movl` 연산은 원자적 연산임을 보장한다. 이건 하드웨어적으로 x86 차원에서 지원하는 부분이다. 

 

: `xv6`에서 인터럽트를 활성 및 비활성화하는 부분을 살펴보자. 제일 처음 볼 수 있는 코드는 `pushcli`다. `pushcli/popcli`는 한 쌍으로 동작해야하며, 내부적으로 x86의 `cli/sti` 명령어를 어셈블리 레벨에서 호출하고 있다.

// spinlock.c ... ... // Pushcli/popcli are like cli/sti except that they are matched: // it takes two popcli to undo two pushcli.  Also, if interrupts // are off, then pushcli, popcli leaves them off. void pushcli(void) {   int eflags;   eflags = readeflags();   cli();   if(mycpu()->ncli == 0)     mycpu()->intena = eflags & FL_IF; // --- 1   mycpu()->ncli += 1; } void popcli(void) {   if(readeflags()&FL_IF)     panic("popcli - interruptible");   if(--mycpu()->ncli < 0)     panic("popcli");   if(mycpu()->ncli == 0 && mycpu()->intena)     sti(); }

: 그러나, 동기화에서 인터럽트 비활성화/활성화는 생각보다 단순하지 않다. 2가지 고려해야 할 부분이 있다.

 

1" 현재 프로세서의 인터럽트 상태
2" CLI/STI 명령어가 실행되는 횟수는 같지만, 순서가 매칭되지 경우. 예를 들어, `CLI CLI STI` 까지만 실행된 경우(최종 STI가 실행되기 전).

 

: 먼저, 위에서 `1`번으로 표시된 부분은 현재 프로세서의 인터럽트 상태를 저장하는 코드(`mycpu()->intena = eflags & FL_IF;`)다. 즉, `mycpu()->intena` 변수는 현재 프로세서의 인터럽트 상태를 저장한다. 그래서 그 앞쪽에 코드를 보면, `CLI` 명령어를 실행하기전에 EFLAGS에서 미리 인터럽트 정보를 추출하고 있다. 이게 중요한 이유는 이전 상태를 그대로 복구해야 하기 때문이다. 예를 들어, `pushcli`를 실행하기 전에, 현재 프로세서의 인터럽트 상태가 이미 비활성화라고 해보자. 그런데, `pushcli`는 무조건 cli 명령어를, `popcli`는 무조건 sti 명령어를 실행한다고 가정해보자. 그러면, 이미 인터럽트가 비활성화된 상태에서 pushcli/popcli를 순서대로 실행하면, 인터럽트가 활성화가 된다. 이 명령어들이 실행되기 전에 인터럽트가 비활성화였는데, 활성화가 된 것이다. 그래서 이전 상태를 저장해서 나중에 `popcli`에서 이전 상태에 따라서 `sti` 명령어를 실행할지 말지를 결정하기 때문에, `mycpu()->intena` 변수에 최초 인터럽트 상태를 저장한다.

 

: 그런데, 왜 `mycpu()->ncli == 0` 에서만 현재 프로세서의 인터럽트 상태 상태를 저장할까? `pushcli/popcli`가 여러 번 호출될 수 있는 상황에서 중요한 건 최초(pushcli)와 마지막(popcli) 인터럽트 상태다. `xv6`의 pushcli/popcli 의 구조는 여러 번 호출될 수 있다는 점을 고려해서 `mycpu()->ncli` 값을 증가/감소 시키면서 동작한다. 예를 들어, `acquire`만 보더라도, 호출되지마자 `pushcli`를 호출한다. 그 다음 바로 `holding` 함수가 호출되는데, 여기서 또 `pushcli`가 호출된다.

 

: popcli는 `mycpu()->ncli`가 0일 때, 인터럽트를 활성화시킬지 말지를 결정하며, pushcli는 `mycpu()->ncli`가 0일 때, 프로세서의 인터럽트 상태를 저장한다. 만약, `mycpu()->ncli`가 0이 아닐 경우, 인터럽트 상태를 변화시키지 않고 `mycpu()->ncli` 값만 증가/감소 시킨다. 이제 `holding` 함수를 알아보자.

// spinlock.c ... ... // Check whether this cpu is holding the lock. int holding(struct spinlock *lock) {   int r;   pushcli();   r = lock->locked && lock->cpu == mycpu();   popcli();   return r; } ... ...

: `holding` 함수 목적은 `acquire` 함수를 통해 lock을 얻었는데, release를 하지 않는 프로세스`를 검출하는 역할은 한다. `lock`을 얻었으면 반드시 release를 해야 한다. 이 조건이 발생하는 환경은 다음과 같다.

 

1" A 함수 - acquire(&idelock); acquire(&idelock);        // `idelock`을 두 번 가지려고 하므로, 에러 발생 -> 비정상 케이스
2" B 함수 - acquire(&idelock); acquire(&ptable.lock);  // 에러가 발생하지 않음 -> 정상 케이스 

 

: 동일한 프로세서에 동일한 락을 2번 얻으려고 하는것은, 앞에서 락을 해제(release)하지 않았다는 것을 의미한다.

// x86.h ... ... static inline uint xchg(volatile uint *addr, uint newval) {   uint result;   // The + in "+m" denotes a read-modify-write operand.   asm volatile("lock; xchgl %0, %1" :                "+m" (*addr), "=a" (result) :                "1" (newval) :                "cc");   return result; } ... ...

: 앞에서 전반적인 `스핀락`에 대한 메커니즘을 알아봤다. 그런데 핵심적인 부분을 아직 살펴보지 않았다. 바로, `xchg` 명령어다. 이 명령어를 통해서 프로세스들끼리의 동기화를 막을 수 있다. `XCHG` 명령어는 이 글을 참고하자. 간단하게만 설명하자면, `lock; xchgl %0, %1`을 통해서 `%1`의 값과 `%0` 값이 서로 교환되는 것이다. `lock` 명령어도 함께 사용했으니, 상호 배제가 전제된다. 

 

: 그런데, 인텔 공식문서에는 `XCHG` 명령어는 내부적으로 `LOCK#`을 걸기 때문에, 굳이 `LOCK 접두사`를 사용하지 않아도 된다고 했는데, `xv6`는 `LOCK 접두사` 사용하는 것 같다.