Lock (2)

지금까지 Lock을 구현하면서 계속 spin에 의존해왔다.

그런데 spin은 CPU를 계속 사용하기 때문에 문제가 될 수 있다.

이 문제를 Yield를 사용해서 해결해보려고 한다.

 

yield라고 하는 것은 자기 자신을 스케쥴링 해서 디스케쥴링하는 System Call이다.

spin을 사용한 코드와 비교해봤을 때, 다른 것은 다 똑같은데 spin 대신 yield가 들어갔다는 차이가 있다.

여기서 yield는 flag가 1인데 TestAndSet을 통해 1로 바꾸었을 때 작동한다.

이 yield를 호출하게 되면 Running 상태에서 Ready 상태로 바뀌어버린다.

Ready 상태로 바뀌었기 때문에 다른 프로그램이 Running 상태가 될 것이다.

즉 yield를 하게 되면 Context Switching이 일어나게 된다.

 

그림으로 나타내면 다음과 같다.

사이사이에 작은 사각형은 조금 Running 하고 Ready로 바뀌어버리는 것을 나타낸다.

다시 말하면 들어가는 시간이 Context Switching 하는 overhead에 대한 시간이라고 볼 수 있다.

yield를 사용하지 않고 A에서 lock을 얻었을 때, 다른 Thread에서는 다 spin을 하고 있는 상황보다

훨씬 나아지긴 했지만 여전히 문제가 존재한다.

만약 100개의 Thread가 들어왔고 CPU 1개를 사용한다면,

A에서 lock을 얻었을 때 다른 99개는 Context Switching으로 Ready 상태로 들어가야 한다.

이런 상황에서는 여전히 비효율적인 방법이 된다.

 

Ticket Lock에서도 적용이 가능하다.

// spin 부분에 코드가 비어있는데 이 자리에 마찬가지로 yield(); 가 들어가면 된다.

TestAndSet에다 yield를 할 경우 UnFair 한 문제가 남아있기 때문에,

Ticket Lock에 yield를 사용해서 Fair 하게 spin을 줄이는 효과를 볼 수 있다.

 

마찬가지 방법으로 Compare And Swap, Load Linked and Store Conditional에서도

spin을 사용하기 때문에 spin이 있는 자리라면 다 yield를 대신 사용할 수 있다.

 

Lock Priority Inversion(To Avoid Spinning)

그렇다면 지금까지 본 것처럼 Lock을 구현할 때 spin lock이면 안 되는 이유에 대해서 알아보자.

 

만약 T1, T2(T1 < T2, priority)가 있고 이들 사이에 Priority가 있는 스케쥴링을 한다고 가정을 하면

T1이 실행되다가도 T2가 등장하면 T2 쪽으로 preemption이 일어나서 T2가 실행될 것이다.

이때 T2에서 I/O 요청을 했고 I/O 요청이기 때문에 T2가 우선순위가 높아도 T1 쪽으로 다시 넘어가게 된다.

그리고 T1이 Lock을 걸어서 Critical Section에 들어갔고, 그 사이에 T2의 I/O가 끝나서 T1을 밀어내고

preemption이 되어서 T2가 실행될 수 있다.

이 상태에서 T2가 T1이 가지고 있는 Lock을 요청한다면, time out이 될 때까지 spin을 할 것이다.

그런데 time out이 되더라도 T2의 우선순위가 더 높기 때문에

다시 T2가 실행되는데, 또 time out이 될 때까지 spin을 할 것이고 이를 계속 반복하게 된다.

이 반복에서 빠져나갈 수 있는 길은 T1이 실행돼서 lock을 해제해주어야 하는데, 우선순위에 의해

T1이 실행될 수 있는 기회를 가질 수가 없어서 T2는 영원히 spin에서 빠져나올 수 없게 된다는 문제가 발생한다.

 

그렇다면 spin을 사용하지 않고 Lock을 만들 수 있을까?

완벽하진 않아도 spin을 줄일 수 있다.

lock을 얻으면 critical section에 진입을 하지만, 못얻으면 sleep(또는 Blocked) 상태로 진입하게 하는 방법이다.

이럴 경우 lock을 얻을 때 까지 CPU를 놓아준 것이나 마찬가지 이다.

 

여기서 Priority Inverion 현상에 대한 예를 보고 가자면, T1, T2, T3(T1 < T2 < T3, priority) 가 있을 때

T2가 실행되다가 T3가 들어왔고, T3에서 I/O 요청이 발생해서 다시 T2로 넘어갔는데

T2에서도 I/O 요청이 발생해서 T1으로 실행흐름을 넘겼다.

T1에서 lock을 얻게 되고 T2에서 I/O 요청이 끝나서 다시 T2로 흐름이 넘어가게 됐고

이어서 T3의 I/O 요청도 끝이 나서 T3로 넘어가게 됐다.

여기서 lock을 호출 했을 때 T3는 이미 T1이 lock을 호출 했기 때문에 Blocked/Sleep 상태에 들어가게 되고

따라서 T2가 실행되게 되는데, T2에서 I/O 요청 등에 의해서 T1으로 실행 흐름을 넘길 수 있는 상황이

되지 않는 이상 T2만 계속 실행이 될 것이다.

T3가 우선순위가 더 높지만 Blocked/Sleep 상태로 빠지게 됐고 T1은 실행 될 기회가 없기 때문에

사실 상 T2의 독점이라고 볼 수 있고 이 상황이 Priority Inversion(역전) 현상이다.

 

그래서 이런 문제를 해결하기 위해서 많은 방법들 중에서 Priority Inheritance 라는 방법을 사용한다.

이 방법은 자신의 우선순위를 일시적으로 빌려주는 방법인데,

방금 살펴본 예로 보면, T1에게 T3의 우선순위를 빌려주는 것이다.

따라서 T1이 T2 보다 잠시동안 우선순위가 높아져서 T1을 실행하게 되고,

T1에서 critical section을 마저 실행하고 unlock을 할 수 있게 된다.

그러면 이 unlock 한 시점에서 받은 우선순위를 T3에게 반납을 한다.

결국 T3가 lock을 얻게 되고 T3도 critical section에 진입할 수 있게 된다.

Sleeping Instead of spinning (using Queues)

이제부터는 spin 대신 sleep을 하는 방법을 사용할 것이다.

그러기 위해서는 기다릴 곳이 필요하기 때문에 Queue(waiting queue)를 사용해야한다.

또한 waiting 뿐만 아니라 실행을 위해 기다리는 Ready Queue도 필요하기 때문에 사용한다.

 

go to sleep을 한다는 것은 waiting queue에 넣는 것을 의미하고,

wake up(Blocked/Sleep -> Ready)은 Queue에서 꺼내서 Ready Queue로 넣어주는 것을 의미한다.

여기에 더해서 OS의 지원이 필요한데, park(), unpark(thread ID) 을 OS에서 지원한다고 가정을 한다.

park이라는 함수는 go to sleep을 해주고, unpark은 wake up을 해준다.

주의할 점은 park을 하기 전에 waiting queue에 넣어주는 작업, unpark을 하기 전에 Ready Queue로 넣어주는

작업이 선행 되어야 한다는 것이다.

 

lock에 대한 구조체를 먼저 보면,

flag가 0이면 아무도 사용을 안하는 상태, 1이면 사용하고 있는 상태를 의미한다.

또한 guard 라고 하는 새끼 lock이 있는데, 큰 lock을 잠그고 풀기 위한 작은 lock이라고 생각하면 된다.

중요한 것은 q인데, lock을 못얻었을 때 기다리는 곳이 된다.

 

이 코드의 핵심은 lock에 있는데, flag가 0이면 1로 바꿔주고 (lock을 걸었다.) 반대로 1이면 기다린다.

이 때 기다리는 것은 queue에 자신의 thread_id를 얻어서 등록을  하고 실제 go to sleep을 한다.

 

여기서 guard의 역할은 m->flag == 0 과 m->flag =1 이 나뉘어져 있어서 Test And Set이 다시 분리가 됐다.

이들을 묶어주기 위해서 작은 자물쇠를 사용하는데, 이 자물쇠를 잠그는 것이 while문에 해당하고

그것을 풀어주는 것이 guard를 0으로 만들어주는 것이다.

따라서 Test와 Set 사이에 interrupt 발생으로 문제가 발생하지 않도록 lock을 걸어주거나

못잠궈서 기다리는 것을 atmoic 하게 만들어주는 역할을 한다.

 

unlock에서는 flag를 0으로 바꿔주거나 누군가 lock을 기다리고 있다면 wake up 해주는 역할을 한다.

여기서도 마찬가지로 상태를 바꿀 때 atomic 하도록 lock을 걸고 끝나면 unlock을 해준다.

 

이 guard가 사용하는 lock에서는 spin이 존재한다.

하지만 얼마나 spin이 걸리게 될 지 어느정도 예상이 가능하고 이는 작고 간단한 정도이다.

 

결국 서로 lock을 공유하게 되고 이 공유하는 상태를 잘 보존 하는 것은 굉장히 중요하다.

 

그런데 현재 이 방식에는 Race Condition에 대한 문제가 있다.

작은 lock을 걸고 unlock 하는 과정과 Queue에 넣고 Sleep 하는 것이 겹치게 된다.

그래서 확률은 매우 낮을지라도 작은 lock을 풀자마자 interrupt가 걸려서 다른 Thread로 넘어갈 수 있다.

또 넘어간 Thread에서 unlock을 하게 되면 guard를 얻게 되고 spin은 하지 않는다.

이 때 queue에는 이미 넣어둔 상태이기 때문에 empty가 아니라서 unpark을 하게 된다.

기껏 깨워달라고 넣어둔 것이 제거되어버렸다.

그러고 나서 다시 돌아오면 문제가 발생한다.

다음 할 일이 go to sleep 이기 때문에 sleep 상태로 들어갈텐데 이미 깨울 방법이 지나갔기 때문에

더 이상 m->q에는 아무것도 없고 깨울 수도 없다.

 

그래서 언제 unlock을 할 것이냐에 대한 고민이 있다.

 

만약 unlock과 sleep 하는 것의 순서를 바꾸면 문제가 발생한다.

sleep을 먼저 하기 때문에 go to sleep 하게 되면 lock을 풀 방법이 없기 때문이다.

lock이 풀려야 다른 Thread에서 일을 할 수 있기 때문에 이 방법은 안된다.

 

그래서 setpark() 이라는 park의 의미를 살짝 바꾼 코드를 추가한다.

그 위치는 queue에 add를 한 다음이 된다.

또한 코드에는 안보이지만 m->guard = 0; 밑에 park(); 줄이 있다.

동작 방식은 setpark()과 park() 사이에 unpark()이 있었다면 go to sleep을 하지 않고 바로 return을 한다.

만약 unpark()이 없다면 예정대로 go to sleep을 한다.

 

따라서 운영체제에서 park, setpark, unpark을 지원해준다면 queue와 sleep을 도입한 lock을 만들 수 있다.

Spinning vs Sleeping (UniProcessor vs MultiProcessor)

지금까지의 내용을 바탕으로 Uniprocessor(단일 프로세서), Multi Processor로 나누어서 비교해보면

단일 프로세서에서는 spin을 할 경우 time out 될 때까지 spin을 하기 때문에 sleep이 더 유리하다.

하지만 멀티 프로세서 환경에서는 critical section의 길이에 따라 달라지는데,

critical section의 길이가 길 때는 sleep이 유리하다.

T1에서 critical section을 처리하는 동안 T2에서는 sleep을 하고

그 시간 동안 T3나 T4 같은 쪽에서 다른 일을 할 수 있기 때문이다.

하지만 critical section의 길이가 짧다면 spin이 유리할 것이다.

잠깐의 시간만 기다리면 lock을 얻을 수 있기 때문이다.

참고로 우리의 환경은 대부분 Multi Processor이고

잘 만들어진 일명 좋은 프로그램은 critical section의 길이가 짧기 때문에 기본적으론 spin이 유리하다.

Two Phase Lock

여기서 Two Phase Lock이라는 것에 대해서 알아보자.

Two Phase Lock에서는 일단은 spin을 하면서 조금 기다려본다.

그 때까지 lock을 못얻으면 sleep을 하는데, 이 때 spin 하는 시간을 c라고 둔다.

c는 context switching 하는데 걸리는 시간 만큼으로 본다.

c만큼이 지나도 계속 spin을 한다면 그 때 sleep을 한다.

이 때는 실제로 context switching을 하기 때문에 c만큼의 시간이 들어간다.

따라서 Two Phase Lock에 들어가는 비용은 2c라고 할 수 있다.

하지만 문제는 context switching time이 고정되어있지 않다는 것이다.

즉 c를 정하는 것이 어려워서 Two Phase Lock는 사용하기가 조금 까다롭다.