본 글의 내용은 Operating Systems: Three Easy Pieces의 Locks 챕터를 정리한 것입니다.

☑️ 개요

• 동시성이 등장하고 나서부터 생긴 근본적인 문제는 실행하고 싶은 일련의 명령어를 atomic하게 한 단위로 실행하고 싶지만, interrupt가 존재하기 때문에 불가능하다는 것이다.

• 이것을 해결 하기 위해 Lock이라는 개념이 도입되었으며, critical section을 마치 atomic하게 실행되도록 할 수 있다.

☑️ 기본 아이디어

• Lock을 사용하려면 잠금 변수(lock variable)을 선언해야 한다.

• 잠금 변수는 사용 가능(unlocked/free) 혹은 획득됨(locked/held) 상태로 존재한다.

• 어떤 스레드가 lock을 얻고 있는지, 어떤 스레드가 대기열에 존재하는 지에 대한 정보도 따로 저장된다.

• lock() 과 unlock() 은 단순하다. lock() 은 lock을 가지려는 시도이고, 보유하게 되면 critical section으로 진입할 수 있게 된다. (이때, 스레드는 lock의 owner라고 불린다.)

• lock을 특정 스레드가 보유하고 있다면, 다른 스레드가 lock() 을 호출해도 lock이 반환되지 않는다.

• unlock() 을 호출하면 다시 lock이 자유로워지며, 대기 중인 스레드가 알림을 받고 그 lock을 획득한다.

• 이렇게 lock은 개발자에게 스케줄링에 대한 최소한의 제어를 제공하며, 특정 코드 내에서 하나의 스레드만 활성화되도록 보장해준다.

☑️ Pthread Locks

• POSIX 라이브러리에서 lock에 사용하는 이름은 mutex로, mutual exclusion을 실현시키는데 사용된다.

• 여러 개의 잠금 변수를 선언할 수 있으므로, 좀 더 세분화 시켜서 접근할 수 있고, 동시성이 향상된다.

☑️ 효율적인 Lock을 구축하기

• 어떤 식으로 lock을 배치해야 효율적으로 활용한다고 할 수 있을까?

• 우선 lock이 어떤 목표로 사용된 것인지 이해하고, 효율적으로 배치됐는 지 평가하는 법을 알아야 한다.

  • 그것의 첫번째 기준은 lock이 mutual exclusion을 제공하는지에 대한 여부이다. 기본적으로 critical section에 여러 스레드가 진입하지 못하도록 막는지를 확인해야 한다.

  • 두 번째는 공정성(fairness)이다. lock을 얻기 위해 각 스레드가 공정하게 경쟁하는 지를 확인해야 한다. (대기 스레드에 starvation이 일어나서는 안 된다.)

  • 마지막 기준은 성능(performance)이다. lock을 사용하면 오버헤드가 생긴다. 이것에는 경합이 없는 경우의 오버헤드(단순히 lock을 걸고 해제하는 경우)와 여러 스레드 혹은 CPU가 경합할 때 생기는 오버헤드가 있다.

☑️ 초기 접근: Interrupt 비활성화

• mutual exclusion을 실현시키기 위해 초기에 사용됐던 방법으로는 interrupt 비활성화가 있었다.

• 이것은 굉장히 단순한 방법이지만, 스레드가 interrupt를 비활성화 하는 것은 privilleged operation을 사용하는 것이므로, 이것이 남용되지 않을 것이라는 보장이 필요했다.

• 이것은 앱에 지나친 신뢰를 요구하며, 악용될 여지가 훨씬 많다.

• 또한 멀티프로세서에서는 적용할 수 없었는데, 여러 스레드가 서로 다른 CPU에서 실행되면 interrupt 비활성화 여부는 중요하지 않았다.

• 그리고 interrupt를 장시간 비활성화하면 interrupt가 손실되고, 시스템에 문제가 생길 수 있다. CPU가 I/O 요청이 완료됐다는 사실을 놓치게 되면 프로세스는 어떻게 깨워져야 할까?

• 마지막으로 interrupt를 끄는 것이 굉장히 비효율적이라는 것이다. 일반적인 instruction 실행과 비교하면, interrupt 마스킹/마스킹해제는 최신 CPU에서 느리게 실행되는 경향이 있다.

• 위 이유 때문에 interrupt 비활성화는 제한된 상황에서만 mutual exclusion primitive로써 사용된다. 예시로 OS에서 자체 데이터 구조에 접근할 때, atomic함을 보장하거나 복잡한 interrupt 처리 상황을 배제하기 위해 interrupt 마스킹을 사용한다.
  

☑️ 실패한 Lock: Load/Store만 사용하기

• 위 예시에서는 Thread 1이 flag를 1로 설정하기 전에 interrupt가 발생하여 Thread 2가 critical section에 진입하고 있다. 즉 mutual exclusion이 실현되지 않는다.

• 또한 while 문, spin-wait 코드 때문에 단순히 기다리는 것에 CPU 자원을 소모하면서 성능을 하락시키게 된다.

☑️ Spin locks with Test-And-Set

(Test-And-Set 함수)

(Test-And-Set을 호출하는 spin lock 함수)

• interrupt 비활성화 대신 도입된 기법은 Test-And-Set이다.

• 위 예시에서는 lock에 새로운 값을 할당하고 이전 값을 return 한다. 즉, 값이 1일 때는 계속해서 spin-wait 하며 똑같은 1이라는 값을 할당하고, 값이 0일 때는 새 값인 1일 할당하고, 이전 값인 0을 return 하여 spin-wait을 벗어난다.

• 이것의 핵심은 위 연산이 atomic하게 수행된다는 것이다.

• 여기서는 spin-wait를 해야되기 때문에 무조건적으로 선점 스케줄러에서만 사용해야 한다.

☑️ Spin lock 평가하기

• Lock의 가장 중요한 측면은 정확성(correctness), mutual exclusion을 제공하느냐 이다.

• 그리고 공정성(fairness)도 중요한데, 안타깝게도 spin lock은 공정성을 보장하지 않는다. 이것은 starvation이 발생할 수 있음을 의미한다,

• 마지막으로 성능(performance)은 어떨까?

  • 단일 CPU인 경우 오버헤드가 상당히 클 수 있다. 만약 N개의 스레드가 존재한다면 N-1개의 스레드가 대기만 할 수도 있다.

  • 의외로 다중 CPU에서는 Spin lock이 상당히 잘 작동한다. (스레드와 CPU 개수가 거의 같을 때)

☑️ Compare-And-Swap (Compare-And-Exchange)

• Test-And-Set 과 유사하나, 다른 점은 예상 값과 동일할 때만 새로운 값을 할당한다.

• x86 에서 compare-and-exchange 라고도 불린다.

• 위 방식은 추후에 살펴볼 lock-free synchronization에서 더욱 강점을 가진다.

☑️ Load-linked & Store-conditional

(LL & SC Instruction 코드화)

• 몇몇 플랫폼은 critical section에 활용할 수 있는 명령어를 제공한다.

• 그 예로, MIPS 아키텍처의 load-linked와 store-conditional instruction이 있다.

• load-linked는 일반적으로 load instruction과 비슷하게 동작하며, 메모리에서 값을 가져와 레지스터에 저장한다.

• 그러나 store-conditional과 사용될 때 차이가 있는데, load-linked를 호출한 이후에 대상 값이 업데이트 되지 않았다면 새 값을 할당하는 것이 store-conditional 이다.

• 결과적으로 두 instruction으로 lock을 만들어낼 수 있다.

• load-linked를 spin lock에서 계속 호출하며, 잠금이 확보(플래그가 0) 되기를 기다리고, 확보되면 store-conditional로 lock을 갱신(플래그 1로 설정)하려 시도한다.

• 즉, 어떤 스레드가 load-linked를 호출하면, store-conditional을 호출할 때 또 다른 스레드가 store를 호출하지 않았어야 lock을 획득할 수 있다.

☑️ Fetch-And-Add

• fetch-and-add는 ticket lock을 구현할 수 있는 솔루션이다.

• lock에 ticket, turn 정보가 제공되는데, atomic하게 lock→ticket을 가져와서 값을 증가시키고, 자신은 증가시키기 이전의 값을 myturn으로 삼는다.

• 추후 unlock될 때 이 turn(lock→turn)값을 1 증가시키면서 다음 ticket들을 가지고 있는 스레드가 lock을 얻게 된다.

• 예시) 스레드 A가 먼저 시도하면 ticket을 1로 만들고 myturn이 0이 된다. 이후 스레드 B가 시도하면 ticket을 2로 만들고 myturn이 1이 되는데, 스레드 A가 unlock을 하면 lock→turn이 1이 되면서 스레드 B의 myturn과 같아져 B가 lock을 획득하게 된다.

☑️ Spin lock의 비효율성

• spin lock을 사용하면 스레드가 대기하는 것에 시간을 낭비하게 된다.

• 이것을 방지하려면 어떻게 해야 하는가? 결과적으로 OS 지원이 필요하다.

☑️ 대기열 사용: spinning 대신 sleeping

• starvation을 해결하기 위해, lock이 해제될 때 다음에 어떤 스레드에게 lock을 줄지 명시적으로 제어해야 된다.

• 이것을 실현하기 위해 대기중인 스레드를 추적할 수 있는 큐, 그리고 OS 지원이 필요하다.

• 예시로 Solaris의 park와 unpark가 있는데, park를 통해 스레드를 잠재우고, unpark를 통해 스레드를 깨운다.

• 즉, spin 대신 park를 통해 스레드가 잠드는 것이다. 그리고 lock이 해제될 때 이 스레드를 깨운다.

• unpark에는 스레드 ID를 전달하는데, 이때 대기열 큐에서 스레드 ID를 가져와 전달한다.

• 이 park/unpark는 일명 wakeup/waiting race를 발생시킬 수도 있는데, 이것은 어떤 스레드가 park를 하기 직전에 interrupt가 발생(switching)하여 다른 스레드가 lock을 해제해버리고, 다시 park를 하려던 스레드로 switching되어 아무도 깨우지 않는 상태가 될 수도 있다.

• Solaris는 그래서 setpark 를 제공하여 이것을 해결하는데, setpark 를 호출한 뒤 switching되어 다른 스레드가 unpark 를 호출하면, setpark 를 호출한 스레드로 돌아왔을 때 잠들지 않고 즉시 리턴된다.

☑️ OS마다 다른 유형의 지원: Linux

• Linux에서는 Solaris와 다르게 futex를 지원한다.

• futex의 futex_wait 는 특정 주소의 값이 예상하는 값일 때 스레드가 잠들도록 할 수 있고, 예상 값과 다르면 잠들지 않는다.

• futex_wake 는 큐에 대기하고 있던 잠들어있는 스레드를 깨운다.

☑️ Two-phase locks

• Linux는 먼 과거에 two-phase lock을 사용하였다.

• 이 lock은 첫번째 단계로, spin lock을 설정하여 lock을 획득할 때까지 잠시 spin하는데, 획득하지 못하면 두 번째 단계인 절전 모드로 진입한다. (잠금이 해제되면 깨어난다)

• 이것은 하이브리드 접근 방식의 예시라고 할 수 있고, 실제로도 두 아이디어를 결합하면 더 나은 결과를 얻기도 한다. 모든 사례에 적합한 범용적인 잠금은 존재하지 않는다.

✅ 요약

• interrupt와 멀티 스레드의 존재는 동시성 문제를 만들어냈다.

• 이것을 위해 lock을 활용하는데, 상호 배제 제공 여부, 공정성, 성능을 지표로 삼아 lock을 평가하게 된다.

• 초기에는 interrupt 비활성화도 활용하였으나, 악용될 여지가 많아 제한된 용도로만 사용된다.

• test-and-set, compare-and-swap, fetch-and-add 방식으로 spin lock을 만들 수 있으나, spin lock은 CPU를 쓸데없이 낭비한다는 단점이 있다.

• 그래서 스레드를 큐에 대기(잠들기)시키는 방식이 고안되었으며, OS마다 지원 방식이 다르다.

• 때로는 spinning과 잠들기를 함께 사용하기도 하며, 어떤 방식이 적합한가는 시스템마다 달라진다.