OS : Spin Lock

학부 수업 내용을 필기한 내용입니다.
필자가 이해를 제대로 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분이 있다면 댓글로 이야기하여 수정하게 해 주시면 감사하겠습니다.

SPIN LOCK

이전 포스팅에서 본 Interrupt를 켜고 끄는 LOCK 방식의 단점을 극복한 SPIN LOCK에 대해 알아보자
단순히 구현하여 실패한 예시부터 LOCK에 성공하기 위해 여러 기계어와 결합한 다양한 버전까지 보자.

실패 예시 - Just Using Loads/Stores

---

 

 

Line 1을 보면, Lock이 어떠한 구조체로 구현되어있다.

LOCK에 걸렸는지 안걸렸는지 나타내는 flag 변수가 있다.

초기화의 경우에는 flag을 0 , LOCK을 풀어놓는다.

LOCK을 거는 것은8~11번 라인을 보자.

• 직접 LOCK을 거는 상황
  • flag가 0인 상태에서 실행되므로 while문이 실행되지 않고 flag를 1로 만든다.
• LOCK이 이미 걸려있는 상황
  • flag가 1인 상태이므로 while문에 빠져서 아무것도 하지 않으며 계속 기다린다.(Busy Waiting)

이러한 상황에 대해서 Thread Trace를 확인해보자.

T1은 Critical Section에 진입하기 전에 flag가 0이었으므로 진입하면서 flag를 1로 만든다.

그러던 중 마저 Critical Section을 다 하지 못하고 Interrupt가 발생하여 스레드 교체가 되는데

T2는 Critical Section에 진입하려 하나, flag가 1 이므로 아무 일도 하지 않는 while문을 계속해서 돈다.

이 과정에서 T2는 Time out이라던지, 여타의 이유로 Interrupt가 발생하여 다시 T1으로 돌아오게 된다.

(다른 Interrupt가 발생하지 않더라도 Time out은 필연적으로 발생하므로 Critical Section은 보호됨)

이렇게 하면 Interrupt Disable에 의존하지 않았기에 MultiProcessor에서도 사용 가능하다.

다만 혼동하지 말아야 하는 것이, 진짜 Atomic 하게 하면 Interrupt도 발생하지 않는다.

Critical Section이 쪼개진 것이다. T1이 진행 중에 T2가 들어올 수는 있다.

따라서 Race Condition이 발생하고, No Mutual Exclusion 하다.

그렇기 때문에 이러한 LOCK 구현은 실패다

while(mutex->flag == 1)
    ;
// 이 사이에 Interrupt가 발생한다면?
mutex->flag = 1;

Mutual exclusion이 되지 않는다

위와 같은 상황이 발생할 수 있다는 것이다.

T1이 lock()을 호출해서 flag를 1로 만들기 전에, 뭐 공교롭게도 Time-out이 된다거나 해서 Interrupt가 발생했고, 때 마침 공교롭게도 T2가 실행이 되어서 하필이면 lock()을 호출해서 flag를 1로 만들었다.

그리고 다시 T1으로 돌아오게 되면 T1은 아까 하지 못했던 flag = 1을 하게 되고

Critical Section에 진입하게 된다.

하지만 아까 언급했듯이 이와 같은 LOCK 구현 시도는 Critical Section이 Atomic하지 않기 때문에

T1의 Critical Section 진행 중 Interrupt가 발생하여 T2로 넘어가게 되면

T2 또한 이미 lock() 호출을 하여 Critical Section에 진입했었으므로 이 과정에서 Mutial Exclusion이 보장되지 못하는 것이다.

따라서 이와 같은 방식은 실패다.

이러한 단순한 Spin Lock의 문제를 해결하기 위해 여러 기계어가 등장하는데 그것들과 결합된 Spin Lock에 대해 알아보자.

 

Test-And-Set

---

비유로 설명을 해 보자.

메모리에 있는 값이 무엇인지 알아보며 그 값을 1로 setting 한다고 하자.

값을 읽어오는 LOAD 가 있을 것이고

Setting 하는 STORE가 있다.

그리고 그 둘이 동시에 진행된다.

• Case 1
  • 메모리에서 불러온 값이 0이다. (LOAD)
  • 메모리에 1을 Setting 했다. (STORE)
• Case2
  • 메모리에서 불러온 값이 1이다.(LOAD)
  • 메모리에 1을 Setting 했다. (STORE)

 

LOCK 성공사례 - Working Spin Locks with Test-And-Set

---

지금까지는 어딘가 하나씩 문제가 있는 LOCK 구현에 대해 보았었다.

이번에는 방금 전 예시로 살펴본 Test-And-Set을 활용한 LOCK에 대해 살펴보자.

Spin Locks With Test-And-Set이다.

즉, 아까 보았던 Spin- While을 사용하는 방식에서 Test-And-Set을 추가하면 된다는 것이다.

 

 

위의 코드가 추가되었다.

이는 기계어의 동작 의미를 C 코드로 표현하게 된 것이다.

LOAD와 동시에 STORE 한다.

while(mutex->flag == 1)
    ;
mutex->flag = 1;

아까 보았던 Spin의 경우를 보면

while(mutex->flag == 1)

이 부분이 Test에 해당하고

mutex->flag = 1;

이 부분이 Set에 해당했다.

그리고 Test와 Set이 분리되어있었기 때문에 그 분리된 사이로 문제가 발생하여

No Mutual Exclusion이 되었기에 실패했던 것인데

새로 추가된 TestAndSet 함수를 사용하여 Test-Set을 Atomic 하게 하면 문제가 해결된다.

 

 

Line 10~12를 보면 이전과는 Spin 이 달라졌다.

While 조건문이 TestAndSet 함수로 묶이면서 Atomic 해진 것이다.

이렇게 되면서 Critical Section이 분리될 수는 있으나, Race Condition은 발생하지는 않는다.

그럼 이런 구현 방법은 LOCK 평가 기준을 얼마나 충족할까?

• Mutual Exclusion - 가능하다
• Progress(deadlock-free) - Deadlock 이 발생하지 않는다 OK
• Bounded wait - 보장할 수 없다.
• Fairness - X
• Performance - Spin이 있으므로 느리다.

두 개 정도만 충족한다.

 

 

스케쥴러가 위와 같이 하게 되면

스레드 A는 계속해서 운이 좋게도 다른 스레드로 전환되기 전에 LOCK을 걸어버리고

B는 계속해서 이미 LOCK이 걸린 상태에서 전환되어서 아무것도 하지 못하고 SPIN만 한다.

이러한 부분에서 Fairness 하지 않고, Bounded wait 하지도 않다는 것이다.

 

Compare-And-Swap

---

이전에는 Test-And-Set이라는 기계어가 있다고 생각하고 LOCK을 구현했다.

그럼 또 다른 명령어 Compare-And-Swap 이 있다고 구현해보자.

 

 

인자가 3개 있다. int expected가 추가되었는데

Test-And-Set과는 다르게 LOAD 해 온 값이 Expected, 기대와는 다르면 Setting을 하지 않는다.

다만 return은 Test-And-Set과 동일하게 메모리에서 읽어온 값이다.

 

 

Test-And-Set과 사실 그렇게 큰 차이는 없다.

 

Load-Linked and Store-Conditional

---

 

메모리의 값을 Load 하는데 그 주소를 기억한다.

그리고 조건에 따라 Store 하는데

만약 메모리부터 주소를 얻고 나서 값의 변경이 없었다면 Store 하고

아니라면 하지 않는다.

 

 

참고로 현재까지 본 Test-And-Set / Compare-And-Swap / Load-Linked And Store-Conditional

C언어 코드는, 단순히 기계어를 이해하기 쉽게 C언어로 표현한 것이고

실제로는 기계어 레벨에서 실행된다고 생각해야 한다.

따라서 다양한 LOCK 구현 방법에 대해 개념적으로 이해해야 한다.

그럼 이번 코드를 봐 보자.

이중 While문이 되었다.

while(LoadLinked(&lock->flag) == 1)

메모리부터 읽은 값이 0이라면 위의 반복문을 탈출하고

if(StoreConditional(&lock->flag, 1) == 1)

위 조건문에 가는데, flag를 건드린 적이 없다.

즉, 처음 LOCK을 거는 스레드라면 STORE를 하고 return 1을 하면서

조건문이 충족되어 return 하게 되어 SPIN을 탈출하지만

두 번째로 LOCK에 접근한 스레드는

이미 flag 메모리는 Update 되었기 때문에 조건문에서 return 0이 되어

다시 계속해서 flag가 0이 될 때까지 기다리는 Spin에 빠지게 된다.

 

Fetch-And-ADD

---

이전에 보았듯이 Fair하지 않다는 큰 단점이 있었다.

이러한 부분을 보완하기 위해 새로운 기계어가 등장했다.

 

 

값을 읽어오고 STORE 하는 값은 + 1 한다.

이것은 번호표와 비슷하다.

 

 

내가 발급받은 숫자가 N이라고 가정할 시, 발급 기안에 있는 다음에 발급할 수는 N+1로 되어있다.

 

위의 코드를 보면 ticket과 turn으로 구성되어있다.

아까 번호표와 유사하다 하였는데 그런 의미에서 보면

• Ticket - 발급받은 종이
• Turn - 호출

이렇게 이해하면 이해하기 편하다.

그리고 Lock을 보면 번호표를 발급받고, 자기 차례가 아니라면 계속해서 대기한다.

그리고 차례는 언제 넘어가느냐 하면 Unlock이 되면서 차례, Turn이 증가하게 된다.

실제 사용 사례를 보며 이해해보자.

 

 

A가 Lock()을 한다.

이 상태에서 A가 받은 ticket은 0이고, 현재 turn 또한 0이므로 A는 실행이 된다.

그리고 B가 Lock()을 하면

아까 A가 ticket을 받는 순간 ticket의 메모리에는 0 + 1 -> 1이 저장됐으므로

B의 ticket은 1이 된다.

그리고 현재 A의 Lock이 끝나지 않았으므로 turn은 0이기 때문에 B는 Spin 한다.

그다음 이어서 C가 Lock() 하게 되는 경우도 마찬가지

C의 ticket은 2가 되고 turn이 0이므로 Spin

이어서 A가 Unlock() 하게 되면

그때서야 turn이 1 증가하면서 B는 Spin을 멈추고 수행한다.

C는 여전히 Spin 한다.

이러한 흐름으로 진행되는 것이다.

이렇게 되면 Lock에 접근한 순서대로 차례차례 진행할 수 있게 되기 때문에 Fair 해진다!

다만 여전히 Performance 측면에서는 나쁘다! 왜? Spin이 있기 때문에.