Lock

앞에서 Race Condition을 설명할 때 Thread가 공유 자원을 사용하면서 발생한 문제에 대해서 알아봤다.

문제의 근본적인 원인은

counter를 1 더하는 과정이 기계어로 세 단계로 나뉘는데, 이 세 단계가 atomic 하지 않기 때문에

중간에 interrupt가 걸려서 끊어질 수 있고 그렇게 끊어질 경우 우리가 기대했던 counter 값이 나오지 않는다.

 

이런 문제를 해결하는 방법은 Lock을 사용하는 것이다.

Lock은 한 쪽에서 코드에 진입을 하게 되면 다른 쪽에서 진입하려고 할 때 이를 막고 기다리도록 하는 역할을 한다.

먼저 진입한 쪽을 T1, 나중에 진입한 쪽을 T2 라고 하면

T1이 먼저 Critical Section에 진입하면 T1이 Lock을 얻고 코드를 실행하는 동안 T2는 Critical Section에 진입할 수 없다.

T1이 모든 과정을 끝내고 Lock을 풀어줘야(unlock) T2에서 접근이 가능한 방식이다.

 

이러한 Lock은 실제 프로그래밍을 할 때 이미 구현되어서 라이브러리로 제공된다.

한 줄 처럼 보이지만 사실은 코드 3개(load, add, store)로 구성된 balance에 1을 더하는 일을 lock으로 감쌌다.

이렇게 Lock을 걸면 이제 'Mutual Exclusive 하다'라고 말할 수 있다.

 

Lock을 만드는 방법에는 여러 가지가 있는데, 그렇다면 Lock을 평가하는 기준에 대해서 알아보자.

크게 다섯 가지로 나눌 수 있다.

▶ Mutual Exclusion

Critical Section 에서 하는 일이 상호 배제가 되어야 한다는 뜻이다.

다시 말하면 Critical Section에는 한 번에 하나의 Thread만 진입할 수 있어야 한다.

 

▶ 공평(Fairness) 해야 한다.

Lock을 못얻으면 기다려야 하는데, 기다리는 시간이 균등해야 한다는 뜻이다.

 

▶ 성능(Performance)이 좋아야 한다.

Race Condition을 해결해야 하는 것은 맞지만, 그 과정에서 너무 성능이 떨어지면 안된다.

 

▶ Dead Lock이 걸리면 안된다.

Lock을 잘못 만든 케이스이다. 최소한 하나의 Thread는 계속 진행이 되어야 한다.

 

▶ Starvation이 생기면 안된다.

waiting time이 균일하지 않을 때, 어떤 Thread는 무한히 기다릴 수 있다는 문제가 있다.

공평 해야 한다는 기준과 연결된다.

 

Lock을 구현하는 방법

◆ Interrupt를 이용한 방법

lock을 걸면 Interrupt를 꺼버리고, unlock을 하면 다시 Interrupt를 켜는 방법이다.

문제가 발생했던 예제를 다시 보면 load, add를 한 후 interrupt가 발생하는데,

이 방법을 사용하면 lock을 거는 시점에서 interrupt가 발생하지 않도록 차단해버리는 것이다.

따라서 load, add, store 까지 한 후 unlock을 하면 그재서야 interrupt가 발생할 수 있다.

결과적으로 보면 우리가 원했던 +2가 되는 결과를 얻을 수 있다. 즉 기본적으로 동작은 한다.

이 방법은 interrupt 자체를 꺼버렸기 때문에 time out으로 인한 interrupt도 발생할 수 없다.

즉 time out 조차 걸리지 않아서 T2로 전환이 될 가능성이 없어진 셈이다.

 

하지만 이 방법은 몇 가지 문제점이 있다.

우선 privileged operation 측면이 있다.

interrupt를 켜고 끄는 것은 일반 user program에서는 허용하지 않기 때문이다. (kernel level에서 가능하다)

 

두 번째, Multi Processor에서는 동작할 수 없다. (가장 치명적)

CPU가 하나일 때는 interrupt를 꺼버리면 방해할 수 없지만,

Multi Processor는 CPU가 2개 이상인 환경인데, CPU1에서 Lock을 걸어서 interrupt를 껐다고 해도

CPU2에서는 interrupt가 Enable 상태이다. 즉 영향을 받지 않는다.

따라서 CPU1과 CPU2에서 프로그램이 동시에 실행될 수 있고 이 프로그램이 Critical Section을 실행한다면

처음 발생했던 문제가 그대로 다시 발생할 수 있다.

게다가 오늘 날의 컴퓨터에서는 Multi Processor가 없는 컴퓨터를 찾기 힘들다.

 

세 번째, interrupt를 오랫동안 꺼둘 경우 System이 보내는 중요한 interrupt를 놓칠 수가 있다.

예제에서는 짧게 interrupt를 껐지만, Critical Section이 길어진다면 interrupt를 꺼두는 시간이 길어진다.

이 때 중요한 interrupt가 발생한다면 이를 놓칠 수 있다.

 

마지막으로, interrupt를 Control 하는 명령은 굉장히 느리다.

I/O와 관련된 셋팅도 포함하고 있기 때문에 속도가 굉장히 느리다는 단점이 있다.

 

◆ Simple Flag를 이용한 방법(Load/Store만 이용)

우선 구조체를 만들고 안에 flag 변수를 담아 두었다.

이 변수를 init()로 초기화 할 때 0으로 셋팅 해주고 lock을 하면 1로 unlock을 하면 0으로 만들어준다.

그런데 lock으로 이미 1을 만든 상태에서 lock이 들어오게 되면 flag는 이미 lock이 걸린 상태인 1이기 때문에

while문 안에서 spin을 돌면서 아무것도 안하고 기다리게 된다. (spin-wait, do nothing)

이 표로 생각해보면 mov 전에 lock(&mutex)를 실행해서 lock을 얻고나서

load, add를 하고 interrupt가 걸렸을 때 Thread2로 흐름이 넘어가는데 T2에서 lock(&mutex)를 호출하지만

이미 flag는 1이기 때문에 spin을 돌게 된다. 그러다가 time out이 발생하게 되고 다시 Thread1으로 넘어가면

마저 다 못했던 store를 이 때 해주고 unlock을 통해서 flag를 0으로 만들어준다.

이후 Thread1은 time을 다 쓸 때까지 자기 할 일을 하다가 Thread2로 interrupt가 걸려서 넘어가면

Thread2에서도 1만큼 증가시키는 일을 해서 우리가 기대했던 +2를 증가시키게 된다.

 

따라서 이 방법은 interrupt를 사용하지 않고도 우리가 기대했던 방식으로 동작했고

Multi Processor에서도 사용 할 수 있다.

다만 interrupt를 control 하는 방식은 정말로 덧셈을 하는 그 과정에서 interrupt가 발생하지 않는데

이 flag를 이용한 방식은 interrupt는 발생할 수 있다.

하지만 중요한 것은 T1이 덧셈을 할 때 T2가 개입을 하지 않는 것이다.

즉 Critical Section이 쪼개진 것은 맞지만 Critical Section에 동시에 들어오도록 허용한 것은 아니다.

 

여기까지 보면 뭔가 희망이 있는 방법이라는 생각이 든다.

하지만.. 이 방식에는 Race Condition이 존재한다.

빨간색으로 밑줄 친 부분에서 interrupt가 걸렸다고 생각해보자.

(SYSTEM은 굉장히 복잡하게 load를 하고 또 부하도 걸릴 수 있기 때문에 다양한 상황이 가정 될 수 있다.)

좀 더 자세하게, load를 통해 flag가 0이라는 판단을 했고, flag를 1로 SET 하기 직전에 interrupt가 걸렸다면

T2로 넘어가게 되고, T2에서는 현재 flag가 0이기 때문에 lock을 호출해서 flag를 1로 SET 할 것이다.

여기서 또 T2에서 flag를 1로 SET하고 나서 interrupt가 걸려서 T1으로 넘어갔다면,

T1에서는 flag를 1로 SET 하는 일을 이어서 할 것이다.

 

flag를 1로 SET 하는 일, 즉 lock을 걸었기 때문에 T1에서는 Critical Section으로 진입할 것이고

초기 예제처럼 load, add만 하고 interrupt가 걸렸을 때, T2에서도 flag를 1로 바꾼 상태에서 interrupt가 걸렸기 때문에

Critical Section으로 진입할 것이다. 즉 T1도 T2도 Critical Section에 진입했다.

이럴 경우 기존 문제처럼 결과가 +2가 안되고 +1만 되는 문제가 발생한다. 즉 Race Condition이 발생했다.

lock을 만든다고 만들었지만 제대로 기능을 못해서 동시에 Critical Section에 진입한 것이 원인이다.

따라서 운이 없었다곤 하나 Mutual Exclusive 하지 않은 잘못된 결과를 보여주는 방식이 됐다.

 

◆ 실제로 동작하는 Spin Lock with Test And Set

 

우선 Test And Set 부터 보면

위의 코드는 기계어의 동작 방식을 C 코드로 표현한 것이다.

*old_ptr가 가리키는 곳이 메모리이고 새로운 값으로 셋팅을 하기 때문에

Test And Set은 Load와 Store를 합쳐놓은 것이라고 볼 수 있다.

메모리에 있는 값을 Register로 읽어오는 동시에 메모리에 값을 Setting 하는 일을 atomic 하게 한다.

 

이것을 가지고 우리가 실패했던 Spin Lock을 완성을 해보자

위에서 봤던 코드와 lock 함수의 while문에서 차이가 있다.

문제로 지적했던 1인지 TEST 하는 Code와 값을 SET하는 코드가 TestAndSet(&lock -> flag, 1) 로 합쳐졌다.

TestAndSet 명령 하나에 Load, Store가 들어있다는 이유를 여기서도 확인할 수 있다.

 

헷갈리지 말아야 할 것은

TestAndSet이 Return 하는 값은 int old 값인데, 이 값에는 기존에 들어있던 값이 할당되는 것을 볼 수 있다.

즉 처음 인자로 줬던 *old_ptr 값이 old에 들어가고 이 값이 Return 된다.

 

이제 다시 Code의 while문으로 돌아가서 보면, &lock -> flag 값을 가져와서 그 flag를 1로 셋팅을 한다.

이 때 원래 flag값이 0이었다면 0 -> 1로 셋팅을 하게 되면서 자기가 lock을 걸었다고 볼 수 있고

Return 값은 원래 flag 값인 0이 될 것이다. 따라서 0 == 1을 만족하지 않기 때문에 while loop에서 빠져나온다.

 

하지만 원래 flag 값이 1이었다면 1->1로 셋팅을 하는데, 기존에 lock이 걸려있었다고 볼 수 있고

Return 값은 원래 flag 값인 1이 되기 때문에 1 == 1을 만족해서 spin-wait를 하게 된다.

 

이렇게 Test와 Set이 분리되면서 생겼던 문제를 TestAndSet을 통해 분리 되지 않도록 묶어버렸다.

이제 Lock이 제대로 동작하고 이러한 Lock을 Spin Lock이라고 한다.

 

그렇다면 이 Spin Lock을 위에서 제시했던 평가 기준에 따라서 평가해보면

Mutual Exclusive 하고, DeadLock도 걸리지 않는다.

하지만 Starvation-Free를 보장하지 않는다.

이는 스케쥴링이 어떻게 되냐에 따라서 달라질 수 있는데, 스케쥴러가 Lock에 대한 고려를 하지 않기 떄문이다.

따라서 Fair 하지도 않고, Spin 때문에 Performance도 좋지 않다.

평가 결과 Spin Lock은 간신히 쓸만한 정도라고 볼 수 있다.

 

Spin Lock이 Fairness 하지 않다는 것을 볼 수 있는 그림이 있다.

B는 계속해서 spin만 하고 실행되지 못하기 때문에 공평하지 않다.

이렇게 가면 아예 Lock을 못얻을 수도 있다.

 

여기까지 TestAndSet 기계어가 있다고 생각했을 때 Spin Lock에 대해서 알아보았다.

그런데 TestAndSet과 굉장히 유사한 계통의 다른 기계어가 주어졌을 때에도 비슷하게 Lock을 구현할 수도 있다.

그 첫 번째는 Compare and Swap이다.

TestAndSet 처럼 동작하지만 expected 변수를 하나 더 받아서 우리가 기대한 값과 같다면

new로 Set 해주고 그렇지 않을 때는 처음에 받은 값을 그대로 return만 해주는 방식이다.

다른 부분은 다 TestAndSet Spin Lock과 똑같고 lock 부분만 조금 다르다.

flag를 읽어와서 우리가 기대한 값 0이면 1로 셋팅하고, 우리가 기대한 값 0이 아니면 아무 일도 안한다.

자세히 살펴보면 flag가 0일 때 flag 값이 우리가 기대한 0이기 때문에 1로 셋팅을 하고 조건이 안맞기 때문에

while문에서 빠져나오고, flag가 1일 때는 우리가 기대한 0이 아니기 때문에 아무 일도 안하고 리턴 값이 1이 되서

while문에서 빠져나오지 못하고 spin을 하게 된다.

 

두 번째는 Load-Linked and Store-Conditional 이다.

위 코드 역시 기계어를 C 코드로 설명한 것일 뿐 C Function이 아니다.

LoadLinked는 메모리의 값을 그대로 읽어오는 일을 하고

StoreConditional은 LoadLinked 한 이후에 아무도 쓰지 않았을 때 즉, 자기가 첫 번째 Store라면

value를 써주고 1을 리턴한다. 그게 아니라면 value를 쓰지 않고 0을 그냥 리턴한다.

 

이것을 가지고 Lock을 만든다면 아래와 같다.

init과 unlock은 flag를 0으로 만들어주는 것으로 동일하다.

lock은 무한 loop을 도는데, 우선 flag에서 LoadLinked로 읽어온다.

이 값이 0이라면 while loop에서 빠져나가고, 이 값이 1이라면 spin을 한다.

 

while loop에서 빠져나왔다는 것은 flag가 0이라는 뜻인데, 이 때 StoreConditional은 flag를 1로 셋팅하려고 한다.

0이면 lock을 걸겠다는 뜻, 하지만 LoadLinked 이후에 첫 번째로 쓰는 Thread 일 때만 1로 셋팅할 수 있다.

StoreConditional을 통해 1로 셋팅했다는 것은 while문과 if문 사이에 아무 일도 없었다는 뜻인데,

이것을 체크하는 이유는 while문과 if문 사이에서 interrupt가 걸릴 수 있고

interrupt가 걸린 사이에 flag 값을 다른 Thread에서 바꿀 수 있기 때문이다.

그렇게 1로 셋팅을 성공적으로 했다면 return을 통해서 무한 loop에서 빠져나온다.

그런데 return 값이 0으로 성공적으로 값을 쓰지 못했다면 return이 아니라 다시 while loop을 돌면서

flag를 다시 가져오고 spin에 들어가고 이 과정을 반복하게 된다.

 

이 경우 Test&Set으로 묶었다기보다는 Set을 조금 특별하게 만든 케이스이다.

Test후 별 일이 없으면 Set, 누군가에 의해서 추월 당했다면 Set을 하지 않는 방식이다.

 

중요한 것은 Line과 Line사이에서는 언제든지 interrupt가 걸릴 수 있다는 가정을 해야하고

그럴 때 다른 Thread가 상태를 바꾸는지, 바꿨다면 어떻게 대응하는지가 중요하다.

 

여기까지 TestAndSet, Compare And Swap, Load-Linked and Store-Conditional 방식에 대해서 각각 보았다.

그런데 이들 모두 Spin Lock이라는 것은 변함이 없다.

 

Spin Lock은 다시 언급하지만 불공평하게 기다리거나, 영원히 기다리는 등의 문제를 가지고 있는데

이를 개선하기 위해서 Fetch And Add 방식을 살펴보자.

이것도 마찬가지로 기계어 작동 방식을 C Code 형태로 표현한 것이다.

동작 방식은 은행에서 접수 번호를 호출하는 발생기를 연상하면 되는데

값을 읽어서 old에 저장을 하고 읽은 값은 1만큼 더 해준다.

GCC에서는 이런 library를 atomic function으로 제공을 한다.

 

좀 더 자세히 살펴보자

초기 값은 ticket과 turn 둘 다 0이다.

ticket은 은행에서 뽑은 접수번호 종이를, turn은 창구에 표시된 번호 발생기를 연상하면 된다.

lock을 걸 때를 보면 ticket을 받아와서 기다리는데, turn이 나의 ticket 번호와 같아 질 때까지 기다린다.

unlock은 은행에서 내가 받은 서비스가 끝났기 때문에 turn을 1만큼 증가시켜주는 일을 한다고 생각하면 된다.

 

이와 관련된 하나의 예를 같이 살펴보면

초기 값은 turn = 0, ticket = 0 이고

A가 먼저 lock을 호출한다.

따라서 A는 ticket을 뽑은 것이고, 초기 값이 0이었기 때문에 A는 0을 얻고 ticket을 1로 증가시켜놓는다.

A는 turn이 0이 될 때까지 기다리기 때문에, 이미 0인 turn에 의해서 바로 Critical Section에 들어갈 수 있다.

 

A가 일을 처리하는 동안 B와 C가 도착했다.

B가 도착해서 lock을 호출하면 B는 1을 뽑고 ticket을 2로 바꿔놓는다.

turn 역시 1이 될 때까지 기다리면 되는데 아직 A에서 서비스 중이기 때문에 0에 머물러 있다.

 

C도 마찬가지로 lock을 호출하는데 C는 2를 뽑고 3으로 바꿔놓는다. turn은 2가 될 때까지 기다린다.

이 때 A가 끝나서 unlock을 하기 때문에 turn을 1만큼 증가시켜서 0->1로 만들었다.

따라서 1을 기다리고 있던 B가 서비스를 받을 수 있게 됐다.

A가 또 lock을 얻고 싶어한다.

그래서 A는 다시 ticket 3을 얻고 4로 바꿔놓는다. 그리고 A는 turn이 3이 될 때까지 기다린다.

B가 끝나서 turn이 2로 증가 했고, 이로 인해 2를 기다리고 있던 C가 실행된다.

C도 끝나면 turn이 3이 되고 다시 A를 실행 한다.

A가 끝나면 turn은 4가 되고 이후 C가 lock을 얻고자 하는데, ticket 4를 얻고 turn은

이미 4이기 떄문에 바로 실행이 될 수 있다.

 

이런 식으로 먼저 도착한 것을 먼저 처리해주면 도착한 시간에 비례해서 처리 할 수 있다.

따라서 Fair하기 때문에 이 방법으로 기존에 있었던 Fairness 문제를 해결할 수 있다.

다만 아직 Ticket Locks도 spin을 사용하기 때문에 Performance는 여전히 좋지 않다.

나중에 온 것은 turn을 기다리는 동안 CPU를 계속 쓰면서 Spin을 하기 때문이다.

 

여기까지 Lock에 대해서 알아보았다.