운영체제 21. 락

21. 락

• 프로그래머들은 소스코드의 임계영역을 락으로 둘러서 그 임계영역이 마치 하나의 원자단위 명령어인것 처럼 실행되도록 한다.

21.1 락 : 기본개념

• 락은 둘 중 하나의 상태를 갖는다.
  • 첫 번째는 사용가능(available) 상태 (unblocked 또는 free) 이다. 즉, 어떤 쓰레드도 락을 소유하고 있지 않다.
  • 두 번째는 사용 중(acquired) 상태이다. 즉, 임계영역에서 정확히 하나의 쓰레드가 락을 획득한 상태이다.
• lock과 unlock 루틴의 의미는 간단하다. lock() 루틴 호출을 통해 락 획득을 시도한다. 만약 어떤 쓰레드도 락을 갖고 있지 않으면 그 쓰레드는 락을 획득하여 임계영역 내로 진입한다. 이렇게 락을 획득한 쓰레드를 락 소유자(owner)라고 부른다. 만약 다른 쓰레드가 lock()을 호출한 경우, 락이 사용중인 동안에는 lock() 함수는 리턴하지 않는다. 락을 소유한 쓰레드가 임계영역에 존재하는 상태에서는 다른 쓰레드들이 임계영역으로 진입할 수가 없다.
• 락의 소유자가 unlock()을 호출한다면 락은 이제 다시 사용 가능한 상태가 된다. 어떤 쓰레드도 이 락을 대기하고 있지 않았다면 락의 상태는 사용 가능으로 유지된다. 만약에 대기중이던 쓰레드가 있었다면, 락의 상태가 변경되었다는 것을 인지하고 락을 획득하여 임계영역 내로 진입하게 된다.
• 락은 프로그래머에게 스케줄링에 대한 최소한의 제어권을 제공한다. 일반적으로 쓰레드는 프로그래머가 생성하고, 운영체제가 제어한다. 락은 쓰레드에 대한 제어권을 일부 이양 받을 수 있도록 해준다. 락으로 코드를 감싸서 프로그래머는 그 코드내에서는 하나의 쓰레드만 동작하도록 보장할 수 있다.

21.2 락의 평가

• 락 설계시, 락의 정상동작 여부 판단을 위한 평가 기준을 정해야 한다.
  • 첫째, 상호배제를 제대로 지원하는가
  • 둘째, 공정성(fairness), 쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가, 락을 전혀 얻지 못하는 기아(starve)상태가 발생하는가
  • 마지막, 성능(performance), 락 사용 시간적 오버헤드. 하나는 경쟁이 전혀 없는 경우의 성능, 다음은 여러 쓰레드가 단일 CPU상에서 락을 획득하려고 경쟁할 때 성능, 마지막은 멀티 CPU 상황에서 락 경쟁시의 성능.

21.3 인터럽트 제어

• 초창기 단일 프로세스 시스템에서는 상호배제 지원을 위해 임계영역내에서 인터럽트를 비활성화 하는 방법을 사용했다.
• 단일 프로세서 시스템에서 임계영역 진입 전에 특별한 하드웨어 명령어를 사용해서 인터럽트를 비활성화 시킨다면 임계영역 내의 코드에서는 인터럽트가 발생할 수 없다. 임계영역 내의 일련의 명령어들을 한 묶음으로, 원자적으로 실행할 수 있게 된다. 모든 동작이 끝난 후에 다시 하드웨어 명령어를 통해 인터럽트를 활성화하여 프로그램이 이전처럼 실행된다. 인터럽트가 발생하지 않으면, 코드가 실행중에 다른 쓰레드가 중간에 끼어들지 않는다는 것을 보장할 수 있다.
• 이 방법은 단점이 많다. 먼저 이 요청을 하는 쓰레드가 인터럽트를 활성/비활성화 하는 특권(privileged) 연산을 실행할 수 있도록 허가해야 한다. 또 이를 다른 목적으로 사용하지 않음을 신뢰할 수 있어야 한다.
• 두 번째 단점은 멀티 프로세서에서는 적용을 할 수가 없다는 것이다. 특정 프로세서에서의 인터럽트 비활성화는 다른 프로세서에서 실행중인 프로그램에는 전혀 영향을 주지 않는다.
• 세 번째 단점은 장시간 동안 인터럽트를 중지시키는 것은 중요한 인터럽트의 시점을 놓칠 수 있다는 것이다.
• 마지막으로 비효율적이다. 일반적인 명령어의 실행에 비해 인터럽트를 비활성화 시키는 코드들은 최신의 CPU들에서는 느리게 실행되는 경우가 있다.
• 위의 이유로 상호배제를 위해 인터럽트를 비활성화 하는 것은 제한된 범위에서만 사용되어야 한다. 예를 들어 운영체제가 내부 자료 구조에 대한 원자적 연산을 위해 인터럽트를 비활성화 할 수 있다.

21.4 Test-And-Set을 사용하여 작동하는 스핀 락 구현하기

• 하드웨어 기법 중 가장 기본은 test-and-set 명령어 또는 원자적 교체(atomic exchange)로 알려진 명령어다.
• test-and-set 명령어가 하는 동작은 다음과 같다. ptr이 가리키고 있던 예전의 값을 반환하고 동시에 new에 새로운 값을 저장한다. 여기서 핵심은 이 동작들이 원자적으로 수행된다는 것이다. test-and-set 이라고 부르는 이유가 이전 값을 검사(test)하는 동시에 메모리에 새로운 값을 설정(set) 하기 때문이다.
• 락의 값을 검사(test)하고 새로운 값으로 설정(set)하는 동작을 원자적 연산으로 만듦으로써 오직 하나의 쓰레드만 락을 획득할 수 있도록 만들었다.
• 스핀락은 가장 기본적인 형태의 락으로서 락을 획득할 때까지, CPU 사이클을 소모하면서 회전한다. 단일 프로세서에서 이 방식을 제대로 사용하려면 선점형 스케줄러(Preemptive scheduler)를 사용한다. 선점형 스케줄러는 필요에 따라 다른 쓰레드가 실행 될 수 있도록 타이머를 통해 쓰레드에 인터럽트를 발생시킬 수 있다. 선점형이 아니면 단일 CPU에서 스핀락의 사용은 불가능하다. while문을 회전하며 대기하는 쓰레드가 CPU를 영원히 독점하기 때문이다.

21.5 스핀락 평가

• 상호배제
  • 스핀락은 임의의 시간에 단 하나의 쓰레드만이 임계영역에 진입할 수 있도록 한다.
• 공정성
  • 스핀락은 어떠한 공정성도 보장해 줄 수없다. while문을 회전중인 쓰레드는 경쟁에 밀려서 계속 그 상태에 남아 있을 수 있다.
• 성능
  • 단일 CPU의 경우 스핀락이 갖는 오버헤드는 상당히 클 수가 있다. 쓰레드는 할당 받은 기간동안 CPU사이클을 낭비하면서 락을 획득 하기위해 대기한다.
  • 반면에 CPU가 여러개인 경우 꽤 합리적으로 동작한다. 다른 프로세서에서 락을 획득하기 위해 while문을 회전하면서 대기하는 것은 그렇게 많은 사이클을 낭비하지 않기 때문에 효율적일 수 있다.

21.6 Compare-And-Swap

• SPARC의 Compare-And-Swap, x86에서는 Compare-And-Exchange라고 한다.
• compare-and-swap 기법의 기본 개념은 ptr이 가리키고 있는 주소의 값이 expected 변수와 일치하는지 검사하는 것이다. 만약 일치한다면 ptr이 가리키는 주소의 값을 새로운 값으로 변경한다. 불일치 한다면 아무것도 하지 않는다. 원래의 메모리 값을 반환하여 compare-and-swap을 호출한 코드가 락 획득의 성공 여부를 알 수 있도록 한다.

21.7 Load-Linked 그리고 Store-Conditional

• MIPS구조에서의 load-linked와 store-conditional.
• load-linked는 일반 로드 명령어와 같이 메모리 값을 레지스터에 저장한다. 실제 차이는 store-conditional 명령에서 나타난다. store-conditional 명령어는 동일한 주소에 다른 스토어가 없었던 경우에만 저장을 성공한다. 저장이 성공하면, load-linked가 탑재했던 값을 갱신한다. 성공한 경우에는 store-conditional은 1을 반환하고 ptr이 가리키는 value의 값을 갱신한다. 실패한 경우에는 ptr이 가리키는 value 값이 갱신되지 않고 0을 반환한다.

21.8 Fetch-And-Add

• fetch-and-add 명령어는 원자적으로 특정 주소의 예전값을 반환하면서 값을 증가시킨다.
• 하나의 변수만을 사용하는 대신 이 해법에서는 티켓(ticket)과 차례(turn) 조합을 사용하여 락을 만든다. 기본 연산은 간단하다. 하나의 쓰레드가 락 획득을 원하면, 티켓 변수에 원자적 동작인 fetch-and-add 명령어를 실행한다. 결과값은 해당 쓰레드의 차례(my turn)를 나타낸다. 전역 공유 변수인 lock→turn 을 사용하여 어느 쓰레드의 차례인지 판단한다. 만약 한 쓰레드가 (my turn == turn)이라는 조건에 부합하면 그 쓰레드가 임계 영역에 진입할 차례인 것이다. 언락 동작은 차례 변수의 값을 증가시켜서 대기중인 다음 쓰레드에게 임계영역 진입 차례를 넘겨준다.
• 이전까지의 접근 방법과 이번 해법의 중요한 차이 중 하나는 모든 쓰레드들이 각자의 순서에 따라 진행한다는 것이다. 쓰레드가 티켓 값을 할당 받았다면 미래의 어느때에 실행되기 위해 스케줄 되어 있다는 것이다.

21.9 조건 없는 양보

• 하드웨어의 지원을 받아 많은 것을 해결한다. 동작이 검증된 락과 락 획득의 공정성까지도 해결할 수 있었다. 하지만 아직도 문제가 남아있다. 문맥교환이 되어 쓰레드가 실행이 되었지만 이전 스레드가 인터럽트에 걸리기 전에 락을 이미 획득한 상태라서 그 쓰레드가 락을 해제하기를 기다리며 스핀만 무한히 하는 경우에 어떻게 해야 할 것인가?
• 첫 번째 시도는 단순하고 친근한 방법이다. 락이 해제되기를 기다리며 스핀해야 하는 경우 자신에게 할당된 CPU를 다른 쓰레드에게 양보하는 것이다.
• 하나의 쓰레드는 실행중(running), 준비(ready), 막힘(blocked)이라는 세 가지 상태가 있다.
• 양보(yield)라는 시스템 콜은 호출 쓰레드 상태를 실행 중(running)에서 준비(ready)로 변환하여 다른 쓰레드가 실행 중 상태로 전이하도록 한다. 결과적으로 양보 동작은 스케줄상에서 자신을 빼는 것(deschedule)이나 마찬가지다.
• 문맥교환 비용의 낭비와 굶주림 문제가 있다.

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

• 이전 방법들의 근본 문제는 너무 많은 부분을 운에 맡긴다는 것이다. 스케줄러가 다음 실행될 쓰레드를 잘못 선택한 경우, 선택된 쓰레드는 락을 대기하면서 스핀하거나, CPU를 즉시 반납해야 하는 경우가 발생 할 수 있다.
• 다수의 쓰레드가 락을 대기하고 있을 경우, 다음으로 락을 획득할 쓰레드를 명시적으로 선택할 수 있어야 한다. 이를 위해서는 운영체제의 적절한 지원과 큐를 이용한 대기 쓰레드들의 관리가 필요하다.

21.11 다른 운영체제, 다른 지원

• linux의 경우 futex라는 것을 지원한다. futex는 특정 물리 메모리 주소 그리고 커널에 정의된 큐를 갖고있다. 호출자는 futex관련 함수를 호출하여 잠을 자거나 잠에서 깨어난다.
• futex는 두 개의 명령어가 있다. futex_wait(address, expected)명령어는 address의 값과 expected의 값이 동일한 경우 쓰레드를 블럭시킨다. 같지않다면 리턴한다. futex_wake(address)명령어를 호출하면 큐에서 대기하고 있는 쓰레드 하나를 꺠운다.
• 이 코드에서는 하나의 정수를 이용하여 락의 사용 중 여부와, 대기자 수를 동시에 표현한다. 따라서 락이 음수라면 락이 사용중인 것을 나타낸다.
• 둘 째, 이 코드는 경쟁이 없는 경우에 대해 최적화 되어있다. 하나의 쓰레드가 락 획득과 해제를 반복할 경우, 특별히 빠르게 동작한다.

21.12 2단계 락(two-phase lock)

• 2단계 락은 락이 곧 해제될 것 같으면, 회전 대기가 더 유용하다는 점에 착안하였다. 첫 번째 단계에서는 회전하며 대기한다. 락이 빠른 시간내에 해제될 것을 가정한다. 만약 첫 단계에서 락을 획득하지 못 했다면 두 번째 단계로 진입한다. 두 번째 단계에서 호출자는 차단된다. 락 해제 시 블럭된 쓰레드 중 하나를 잠에서 깨운다. 앞서 다룬 linux 락은 이런 형태를 갖는다. 일반화된 방법은 futex가 일정시간 동안 반복문 내에서 회전한 후에 블럭하는 것이다.
• 2단계 락은 두 개의 좋은 개념을 사용하여 개선된 하나를 만들어내는 하이브리드 방식이다. 물론, 이 기법의 우수성은 하드웨어 환경이나, 쓰레드의 개수, 그리고 세부 작업량 등과 같은 많은 것들에 의해 결정된다.