[OS/OSTEP] 28.threads-locks , 쓰레드 Spin, Test-And-Set, Comapre-And-Swap, futex, wait, park, unpark,

[OS/OSTEP] 27.threads-api , 쓰레드 락(lock), 컨디션 변수, 쓰레드 사용시 주의할점

 

[OS/OSTEP] 28.threads-locks

# 시작하며

 저번 챕터에서는 락을 일단 사용해봤다. 락을 사용하면서 임계영역에 대해 동시접근을 막는 상호배제가 가능한 것을 알았고, 임계영역에 대한 접근을 할때 락을 가지지 못하면 리턴하지 않는다 했다. 여기서 나는 가장 큰 궁금증이 들었다. 락은 어떻게 이루어져있기에 리턴하지 않는거지? 그 속에서는 무슨 일을 하고 있는걸까? 라는 의문이었다. 그래서 락내부의 구현을 찾아봐야하나 고민하던 찰나 바로 다음 챕터에서 락을 어떻게 만드는지에 관한 방법을 배울 수 있었다. 가장 중요한 건, 한가지 방법만 있는 것은 아니라는 것이다. 락을 꽤 여러 방법으로 구현할 수 있었다. 

 

# 락(Lock)의 기본 개념

 락의 사용을 가장 와닿게 설명하는 방법은 특정한 전역변수에 대해서 여러 쓰레드가 접근하여 +1씩 하는 과정이었다. 지나번에 살펴보았던거와 같이 +1을 해주는 연산자체가 3개의 어셈블리코드로 이루어져있기 때문에 그냥 사용한다면 원하는 결과를 얻지 못했다. 그래서 락을 이용해 상호배제를 구현해야 했다.

 락또한 하나의 변수이기 때문에 글로벌로 선언해준다. 락은 두개의 flag를 가지게 되는데, 사용가능과 사용중상태로 나눌 수 있을 것이다. 그리고 락을 가지고 있는 쓰레드를 락 소유자라고 부를 수 있다. 

 

# Pthread 락

상호 배제(mutual exclusion)기능을 쓰레드간에 제공하기 때문에 POSIX 라이브러리에서는 락을 mutex라고 부른다. 기본개념에서 설명했던거와 같이 락을 가지고 있으면 다른 쓰레드는 접근을 할 수 없고, 락을 아무도 소유하고 있지 않다면 락을 가져와 사용할 수 있게 된다.

 

# 락의 평가

 락이 잘 동작하기 위해서는 몇가지의 기준을 충족해야 한다.

1. 상호배제(mutual exclusion)를 잘 구현 했는가
2. 공정성(fairness) - 락 획득에 대해 쓰레드가 공정하게 획득하여 굶주림(starve)현상이 없는가?
3. 성능(performance)를 만족 하는가?

 위 평가 기준중 3번째 성능에 대해서는 여러 쓰레드가 단일 CPU상에서 락을 획득하려고 경쟁하는지, 여러 쓰르데가 여러 CPU에서 락을 획득하려고 경쟁하는지에 따라서 다를 수 있다는 것을 알아야 한다.

 

# 락을 구현하는 방법1 - 인터럽트 제어

 단일 CPU상에서 상호배제방법을 지원하기 위해서 즉 락을 구현하기 위해서는 인터럽트를 비활성화하는 방법을 사용 할 수 있다. 이 방법은 매우 간단하다. 현재 임계영역에서 실행중이라면 인터럽트를 막아 다른 쓰레드로 스케줄링 되지 못하도록 막는 것이다.

그러나 이 방법은 많은 단점이 존재한다. 첫번째로는 쓰레드가 인터럽트를 활성/비활성하는 특권명령을 실행할 수 있어야 한다. 이는 앞서 배운거와 같이 매우 위험한 행동인데, 해당 코드를 신뢰할 수 있어야 한다. 시작과 동시에 lock을 호출하여 인터럽트를 막아 독점하여 cpu를 사용하거나 나쁜 사용자의 경우는 lock을 획득하고나서 무한루프를 돌리게 할 수 있다. 그렇게 된다면 운영체제는 다시 제어권을 획득 할 수가 없게 된다.

 두번쨰로는 멀티프로세스( 여러 CPU )에서는 적용할 수 없다. 인터럽트를 막는 행위는 해당 명령어를 받게되는 CPU에만 적용이 되기 때문에 다른 CPU에서는 인터럽트가 가능하여 똑같은 문제점을 야기할 것이다.

 세번째 단점은 장시간 인터럽트를 중지시키는 경우 놓치게되는 인터럽트가 생기게 되고 큰 문제를 야기 할 수 있다는 것이다.

 마지막으로는 비효율적이다. CPU에서 인터럽트를 활성/비활성화 시키는 코드는 다른 코드들에 비해 느리게 실행된다고 한다.

위 문제들이 있기 때문에 인터럽트를 제어하여 얻어내는 상호배제방법에 대해서는 제한된 범위에서만 사용할 수 있어야 한다.

 

# Test-And-Set이 필요한 이유

 Test-And-Set은 락의 flag를 확인하는 것과 바꾸는 것을 동시에 진행하는 것이다. 이것을 이해하기 위해서는 Test-And-Set이 사용되지 않는 코드를 먼저 보고 그 코드가 일으키는 문제를 먼저 이해한다면 더 쉽게 이해할 수 있을 것이다.

 먼저 우리가 상호배제를 위해서 사용하는 lock()과 unlock()을 실행하면 위에서 정의한 코드들이 실행 될 것이다. lock은 단순히 flag를 살펴보고 0이면 락을 아무도 사용하지 않고 있다는 뜻이므로 락을 얻어 임계영역에 진입할 수 있고, 1이라면 누군가 락을 사용중이기때문에 임계영역에 진입하지 못하고 기다려야 한다는 뜻이다.

 쓰레드 A와 쓰레드 B가 어떤 임계영역에 접근하게 된다는 가정하에 위 코드를 생각해보자. A가 lock을 호출하고 9번라인이 실행되면서 flag를 검사하게 될 것이다. 현재는 아무도 락에 접근하지 않았기 때문에 9번은 false가 될 것이다. 쓰레드 A는 TEST과정을 끝냈다. 그런데 이시점에서 인터럽트가 걸려 쓰레드B가 실행되고 똑같이 lock을 얻기위해 9번라인으로 진입한다. 이 역시 쓰레드 A는 TEST과정만을 거치고 인터럽트 되었기 때문에 lock의 flag는 아무런 변화가 없을 것이고 똑같이 9번라인은 false가 될 것이다. 이제 11번 라인이 실행되면서 쓰레드 B는 락을 얻었음을 표시한다. 그리고 다시 쓰레드 A로 인터럽트가 걸려 이어서 11번라인이 실행되어 쓰레드A역시 lock을 얻었음을 표시한다. 락은 한쓰레드만 얻어야하는데 두 쓰레드가 락을 얻어버리는 문제가 생겼다. 상호배제에 어긋나버렸다.

 만일 쓰레드A가 이미 락을 가진 상태에서 쓰레드B가 락을 얻기 위해 lock()을 호출한다면 9번라인에 걸려 계속해서 TEST를 진행할 것이다. while문이 반복적으로 돌면서 락을 확인할텐데, 자원을 낭비하게 된다. 이렇게 반복적으로 락의 상태를 확인하는 것을 spin-wait 한다.

이렇게 중간에 인터럽트가 걸려 생기는 문제를 방지하기 위해서 Test-And-Set을 사용한다. TEST와 SET과정을 Atomic하게 수행하여 TEST후에 인터럽트가 걸려도 생기는 문제를 없도록 한다. 

 

# Test-And-Set ( Spin-lock ) 

Test-And-Set은 위와 같이 구현되어 있다. 이전 값을 반환시키고, 새로 들어온 값을 바꿔버린다. 이 동작 자체가 한번에 일어나게 된다. 이를 통해 spin-lock을 구현해보면 아래와 같다.

 이전에 TEST와 SET사이에서의 인터럽트가 발생할 수 없게 된다.

대신 위 처럼 구현한 락이 잘 작동하려면 스케줄러는 time-out으로 스핀상태일때 다른 쓰레드로 바꿔 줄수 있어야한다. 즉 선점형 스케줄러(preemptive scheduler)이어야 한다. 그렇지 않으면 while문이 돌고있는 쓰레드가 무한히 반복문을 돌면서 CPU를 독점하게 될 것이다.

 

# Spin-lock 평가

스핀으로 구현한 락에대해서 정확성, 공정성, 성능을 평가해보자.

먼저 정확성은 상호배제를 구현해야한다. Test-And-Set으로 Atomic하게 구현했기 때문에 정확성 측면은 올바르게 구현했다.

스핀락을 통해 대기중인 쓰레드들은 굶주림없이 또 공정하게 실행 될 수 있을까? 그 답은 아니다. while문에서 회전중인 쓰레드는 경쟁에 계속해서 밀리며 그상태에 남을 수 있게 된다.

 성능을 평가하기 위해서는 단일CPU와 다중CPU상황을 고려해야한다. 먼저 단일 CPU인 경우에는 while문을 돌며 락을 얻기위해 spin하는 쓰레드들의 CPU사용이 낭비된다. 힘들게 얻은 CPU사용권한을 단지 락을 확인하다가 끝내야한다. 여러개의 쓰레드가 있으면 그 만큼 CPU를 배정받으며 단순 spin을하며 아깝게(비효율) 사용한다. 그러나 다중CPU의 경우는 다르다. A쓰레드는 CPU1에서 B쓰레드는 CPU2에서 실행되고 있고 A쓰레드가 락을 점유중이라면, 그 임계영역은 매우 짧다고 하면 락은 곧 사용가능 상태가 되기 때문에 스케줄링하는 일련의 과정을 거치면서 자원을 낭비하지 않고 단순히 조금만 기다리면 락을 얻게 되기때문에 효율적일 것이다.

 

# Compare-And-Swap

Test-And-Set가 유사하다. CompareAndSwap을 사용해서도 똑같은 방법으로 락을 구현할 수 있다. Compare-And-Swap은 ptr이 가르키는 곳의 값과 두번째인자(expected)의 값이 일치한다면 new의 값으로 ptr을 바꿔주고 그렇지 않다면 바꾸지 않는다.

즉 위처럼 Test-And-Set가 똑같은 방식으로 구현이 가능하다. 락의 flag가 0이라면 flag를 1로 바꾸어 락을 획득했다고 알리고 0을 반환하고, 락의 flag가1이라면 이미 락을 다른 쓰레드가 점유하고 있는 것이기 때문에 1을반환하며 아무것도 하지 않는다.

 

# Load-Linked와 Store-Conditional

MIPS에서는 Load-Linked와 Store-Conditional을 사용해서 락을 구현하고 병행 연산을 위한 자료구조를 만들 수 있다고 한다. 

LoadLinked는 단순히 메모리값을 레지스터에 저장시킨다. StoreConditional이 중요한 역할을 담당하는데, StoreConditional에 인자로 준 주소에 다른 어떤 값을 STORE(저장)하지 않았더라면 성공하여 1을 반환하고 그렇지 않다면 그사이 누군가 인터럽트를 하여 락의 flag을 바꿨다는 의미임으로 갱신에 실패한다. 

즉 위와같이 락을 구현 할 수 있다.

 

# Fetch-And-Add

Fetch-And-Add기법을 사용해서는 티켓락을 구현 할 수 있다. 티켓을 증가시켜 다음 티켓을 가진 쓰레드를 실행시킨다. 

 

# 결국 Spin으로 인한 낭비

 지금까지의 락구현 방법은 Spin을 돌며 무작정 내 차례가 오기를 기다린다. 비효율적이라는것을 알 수 있었다. 그렇다면 양보를 통해 Lock을 얻기 위해 대기하는 쓰레드라면, 반복문을 무한정 돌지 않고 한번만 돌며 락을 기다리는 상태임을 확인하고 다음 쓰레드에게 CPU를 양보할 수 있을 것이다. Yield()를 통해서 양보하자 ! 

이제 무한정 돌지 않고 한번만 돌고 현재 쓰레드는 READY상태로 바뀌고 다음 쓰레드가 스케줄링 될 것이다. 어느정도 괜찮아졌지만 100개의 쓰레드가 실행된다면 여전히 99개의 쓰레드가 락을 위해서 실행 후 양보(run-and-yield)과정을 반복하게 될 것이다. 조금 괜찮아졌지만 여전히 효율적이라고는 말할 수 없다.

 

# Sleep으로 대기중인 쓰레드를 재우기 - 큐의 사용

 그렇다면 락을 대기중인 쓰레드를 실행하지 않고 Sleep해놓고 락을 얻는 상태가 온다면 깨워 준다면 조금 괜찮아 질 것이다. 그러기 위해서는 큐를 사용하여 Sleep하는 쓰레드를 정리해놓고 깨워줄 필요가 있을때 큐에서부터 순서대로 깨워주면 될 것이다.

 Solaris에서는 park()와 unpark(threadID)라는 방법을 사용하여 위의 행동을 구현했다. park는 호출하는 쓰레드를 재우는 함수이고, unpark(threadID)는 threadID로 명시된 쓰레드를 깨워주는 함수이다.

 그러기 위해서는 guard라는 락을 추가적으로 구현하여 안전장치를 마련해야 한다. guard는 큐의 삽입과 삭제동작을 스핀락으로 보호하는데 사용한다. 즉 완벽히 spin상태를 배제하지는 못했다. 그러나 이 과정에서 lock(guard)을 얻는 임계영역은 짧기 때문에 spin시간이 적어 합리적인 접근법이다.

 lock이 실행되면 guard 락을 획득하고 자신이 락을 가지고 있지 않기때문에 19의 else절이 실행되면서 현재 쓰레드를 큐에 넣고, 다시 가드락을 반납하고 park를 호출하여 sleep상태로 들어간다. park()호출 후 guard 락을 반납하면 잠이 먼저 들어 가드락을 반납할 수 없게 되고 어떤 쓰레드도 가드락을 얻지 못하기 때문에 순서가 중요하다.

 unlock을 통해 unpark이 실행되면 flag락을 획둑하면서. 깨어난 쓰레드는 park에서 리턴하여 그 다음이 실행된다. unpark하여 깨어난 쓰레드 안에서 flag를 바꿔줄 수 없는 이유는, 깨어난 시점에서는 guard를 가지고 있지 않기 때문에 불가능하기 때문이다. 

그러나 여기서도 문제가 발생한다 21번과 22번라인 사이에서, lock이 guard락을 반납하고 해당 쓰레드를 재우려는 직전에 다른 쓰레드가 실행되어 락을 반납하고 인터럽을 하여 다시 park에서 sleep하게 되면 일어날 방법이 없다. 그렇기 때문에 setpark()을 통하여 상태 검사를 한번 더 하게 된다.

만약 그 순간에 인터럽트가 발생하여 다른 쓰레드가 unpark을 호출했다면 park는 잠을 자지 않고 리턴하여 넘어가게 된다.

 

# futex-lock

리눅스에서는 futex를 통해 Solaris에서 구현한것과 비슷한 락을 구현한다. futex_wait(address, expected)와 futex_wake(address)를 통해 sleep을 관리하는데, wait가 실행될때는 address와 exprected가 동일한지 한번더 검사를 함으로써 setpark과 비슷한 효과를 낸다.

futex-lock은 퀴즈와 과제에서도 다루었지만, 여러번 락을 확인한다. 특히 mutex락은 32비트로써 맨 앞자리를 lock을 위한 용도로 사용하고, 그 뒤에 값들이 1씩 증가하는 것의 의미는 기다리는 쓰레드의 갯수가 된다. 특히 주의해야할점은 32비트에서 맨앞자리가 1이라면 즉 락을 소유하고있다면 음수이기 때문에 16번째 라인에서 flase가 되어 wait가 되는데 이점을 주의해야한다. 

 

 

# 마치며 

unpark()이 호출될때 락을 자동적으로 해체해주는지에 대해서 교수님께 따로 질문을 드려야 할 것 같다. 보라색 줄로 표시해 두었는데, 확실히 맞는지는 잘 모르겠다. 교수님 강의를 다시 확인해봤는데 unpark후 락이 획득 됐다는 부연설명은 없지만 이미 락이 반납된 상태로 설명하셨기 때문에 질문후에 확실히 추가하도록 하곘다.