[운영체제] Locks #2

[운영체제] Locks #1

 

 

하드웨어적으로 lock 변수를 관리하는 instruction에 대해서 알아보자

 

 

CPU에서 제공하는 Atomic Instruction을 알아보자

 

 

Test and Set

test-and-set의 동작을 c-style로 표현한 것에 불과함

 

 

test-and-set을 사용한 Spin lock 사용 예

 

기존의 TestAndSet을 알기 전에는 flag 값이 0인지 확인하기 + flag 값을 1로 바꾸기와 같은 총 2가지 동작으로 나뉘어서 수행을 했다. 

그래서 2가지 동작 사이에 context switching이 발생하면 2개의 쓰레드 모두 lock을 얻게 되는 문제(mutual exclusion)가 발생하게 된다.

 

하지만 TestAndSet을 사용하게 되면 위의 2가지 동작을 하나의 명령인 것처럼 수행하게 되어 mutual exclusion문제를 해결할 수 있게 된다.

 

 

Spin locks를 평가해 보자면

1. Correctness : Mutual Exclusion, deadlock-free, starvation-free를 보장한다.
2. Fairness : X -> 많은 쓰레드가 wait상태인 경우 다음에 동작할 쓰레드로 어떤 걸 선택할지 모른다.
3. Performance : 싱글 CPU에서는 overheads가 매우 치명적일 수 있다. 

 

---

 

Compare-And-Swap

compare-and-swap의 동작을 c-style로 표현한 것에 불과함

 

기존의 값을 특정한 값과 비교해보고 같으면 새로운 값으로 교환한다.

그리고 바뀌지 않은 기존의 값을 반환한다.

 

 

compare-and-swap을 사용한 lock 사용 예

 

lock변수가 0이면 1로 교체하고 0을 반환하라는 의미이다.

lock이 0이라는것은 free하다는 의미이고 3번째 인자로 1이 있다는 것은 lock을 획득하겠다는 의미이다.

 

기존의 값이 0이었다면 lock이 free하는 의미였으므로 while을 빠져나가서 critical-section에 진입해도 된다는 말이고,

기존의 값이 1이었다면 lock을 사용중이므로 spin-wait상태에 들어간다.

 

 

---

 

Load-Linked and Store-Conditional

c-style로 표현한 것에 불과함

 

 

 

Load-Linked and Store-Conditional 사용 예

 

Load-Linked에서 얻은 값이 0인경우 Store-Conditional을 호출한다. 그리고 lock변수를 1로 만들어준다.

만약 Load-Linked와 Store-Conditional사이에 context-switching이 발생한 경우에는 lock변수가 Load-Linked를 호출했을 당시와 값이 달라졌으므로 return한다.

 

 

위와 동일한 코드지만 좀 더 심플하게 바꾼 모습

 

---

 

Fetch-And-Add

원하는 주소의 값을 가져와서 1을 증가시킨 후 기존의 값을 반환하는 instruction을 Atomic하게 수행한다.

 

 

Ticket Lock : using fetch-and-add

도착한 순서대로 lock을 얻는 방식

 

Fairness 측면을 고려한 메커니즘이다.

lock변수가 ticket과 turn으로 총 2개가 되었다. (지금까지는 flag 하나)

 

1번 쓰레드가 오면 ticket=0, turn=0이므로 myturn == turn == 0이므로 lock을 얻을 수 있다.

lock을 얻는 과정에서 ticket이 1이된다.

그리고 2번 쓰레드가 오면 ticket=1을 myturn으로 가지게 되고,

1번 쓰레드가 unlock되어 turn이 증가할 때까지 spin-wait을 하게된다.

 

---

지금까지 Software, Hardware Instruction을 사용해서 lock을 구현하는 방법을 알아보았다.

 

---

 

지금까지의 방식에는 문제가 많은데,

어떤 문제가 있는지, 문제를 해결할 수 있는 방법에는 어떤게 있는지 다음번 포스팅에서 알아보겠다.