29. 락

운영체제: 가장 쉬운 세가지 이야기 - Operating Systems: Three Easy Pieces를 바탕으로 작성하였습니다.

---

 

락이란 무엇인가?

- 락은 변수이다.

- 소스코드 임계영역을 락으로 둘러 원자 단위로 실행되게 끔 한다.

- lock() 함수를 통해 락 획득을 시도하고, 가용 상태가 아니라면 return하지 않고 spin하며 대기한다.

- unlock() 함수를 통해 보유중인 락을 해제하고, spin하며 대기중인 쓰레드가 있다면 그 쓰레드는 락을 획득한다.

- 락을 통해 운영체제의 영역인 스케쥴링 제어권을 프로그래머가 일부 이양받게 된다.

 

Pthread 락

- POSIX 라이브러리를 통해 사용하여, 하나의 락을 사용하여 전체 쓰레드를 관리하는 coarse-grained 방식과 여러개의 쓰레드를 사용하는 fine-grained 방식으로 나뉜다.

 

락 평가

- 락은 아래의 요소들로 평가한다.

1. 상호 배제(Mutual Exclusion)

2. 공정성

3. 성능

     1. 경쟁이 없는 경우

     2. 단일 CPU 환경에서 여러 쓰레드간 경쟁이 있는 경우

     3. 멀티 CPU 환경에서 여러 쓰레드간 경쟁이 있는 경우

 

락의 구현

- 락은 하드웨어, 운영체제 또는 둘의 결합으로 구현된다.

 

이제부터 하드웨어의 지원을 통해 락을 구현하는 방식이다.

 

1. 인터럽트 제어 방식

- 인터럽트를 enable, disable해 구현한다.

- 장점은 구현이 단순하다는 것이고

- 단점은 

   1. 인터럽트를 사용하는 쓰레드를 신뢰해야한다는 점

   2. 멀티 CPU에서 작동하지 않는 점

   3. I/O 인터럽트와 같은 중요한 인터럽트 시점을 놓칠 수 있다는 것

   4. 최신 CPU에서 느린 경향이 있는 점

- 그러나 OS 내부 자료 구조에 원자적 연산이 필요한 경우 제한적으로 사용된다.(실행 주체가 OS이기 때문에 신뢰 문제가 없기 때문)

 

2. 실패한 시도: 오직 load/store 명령어 사용

- 단일 변수와 load/store 명령어만으로 구현이 된다.

- 문제는

   1. 인터럽트가 적시에 발생하면 두 쓰레드가 동시에 임계영역에 진입이 가능하다는 점

   2. spin-wait으로 인해 CPU가 낭비된다는 점

 

3. Test-And-Set으로 작동하는 스핀 락

- 락 지원을 위한 하드웨어 설계를 바탕으로 한다.

- test & set이 원자적 명령어로 이루어져 있기 때문에 Correctness를 만족한다.

- 대기중인 쓰레드가 CPU 독점 방지위해 선점형 스케쥴러를 사용하여 일정 시간마다 인터럽트를 발생시켜 다른 쓰레드가 CPU를 할당받도록 한다.

- 평가

1. 상호 배제: O

2. 공정성: X

3. 성능

  1. 단일 CPU 환경에서 쓰레드간 경쟁이 있는 상태: X(CPU 낭비)

  2. 멀티 CPU 환경에서 쓰레드간 경쟁이 있는 상태: O(CPU 낭비 덜 함)

 

5. Load-Linked & State-Conditional

- Load-Linked: 단순하다. 메모리 값을 레지스터에 저장한다.

- State-Conditional: 코드 부분에서 if(no update to ptr since Load-Linked to this ptr address){//락 획득} 이 부분이 핵심이다.

 

6. Fetch-And-Add

- 티켓 락이라 불린다.

- 단일 변수 대신 여러 개의 변수(Ticket, Turn)를 사용한다.

동작 방식은

1. 첫 쓰레드가 실행되면 티켓 값 0, 턴 값 0으로 시작한다. 두 값이 동일하기 때문에 락을 획득한다. 직후에 티켓 값을 1 증가시킨다.

2. 두번째 쓰레드가 실행되면 티켓 값이 1, 턴 값은 0이다. 두 값이 다르기 때문에 대기한다.

3. 첫 쓰레드가 unlock()을 통해 락을 해제하면 직후 턴 값을 1 증가시킨다.

4. 두번째 쓰레드가 티켓 값과 턴 값의 동일성 여부를 검사하며 대기중이기 때문에, 즉시 락을 획득하고 직후에 티켓 값을 1 증가시킨다.

 

여기까지가 하드웨어의 지원을 통한 락 구현이다.

이 방식의 문제는 과도한 스핀으로 인한 CPU 낭비를 초래한다는 것이다.

 

어떻게 대기하면서 CPU 낭비없는 락을 만들 수 있을까?

 

이제부터 운영체제의 지원을 통해 락을 구현하는 방식이다.

 

1. 간단한 접근법: 무조건 양보

- 스핀하며 대기해야 하는 경우... deschedule시킨다. (deschedule: 쓰레드의 상태 running -> ready)

- 단일 CPU 환경에서 쓰레드가 2개라면 정상적으로 동작한다. 락을 보유하고 있는 쓰레드에게 CPU 양보해 코드 실행을 마치고 unlock()하도록 하면 락을 획득할 수 있으니까.

- 하지만 쓰레드가 예를 들어 100개 이상리마녀 라운드 로빈 방식으로 양보를 진행할텐데, 이러면 상당한 문맥 교환 비용이 발생한다. 즉 CPU 낭비 대신 다른 비용을 발생시킨다. 더욱이, 굶주림(Starvation)문제를 전혀 해결하지 못한다.

 

2. 큐의 사용: 스핀 대신 잠자기

 

* 스핀 락을 배제해야하는 이유

- 명칭으로부터 바로 알 수 있듯이, CPU 낭비가 낭비된다.

- 우선순위 역전 문제