[Synchronization] Locks(Mutex)

💡Locks의 개념

 

✅Lock 변수

: Lock 변수는 Lock의 상태를 담고 있다.

 

* unlocked: 아무 thread도 lock을 갖고있지 않다.

* locked: 딱 하나의 thread가 lock을 갖고 있으며 Critical section 내부에 있다.

 

✅lock()

: lock 획득을 시도한다.

만약 아무 thread도 lock을 갖고있지 않았다면, lock을 획득하고 Critical section에 진입한다.

이 thread가 lock을 갖고있는 동안 다른 thread는 CS 진입이 불가하다.

 

✅fine-grained approach - better concurrency

여러 개의 변수를 보호하기 위해선 변수마다 하나씩 lock이 있어야 한다.  

 

lock()

lock()

CS1

unlock()

lock()

CS2

unlock()

.

.

.

lock()

CSn

unlock()

unlock()

 

  i) 하나의 lock만 사용하는 경우

  ii) 각 CS에 각각 lock을 부여하는 경우 

 

✅locks의 평가 기준

* Correctness: mutual exclusion을 정확히 수행하는가?

* Fairness: lock을 얻고자 하는 스레드들이 공정하게 lock을 얻는가? 

* Performance: lock의 사용으로 인한 time overhead는 어느 정도인가?

 

💡Spin lock: Implementations by HW support

 

✅HW support의 필요성

 

위 코드는 mutual exclusion을 수행하지 못한다.

 

 

* 원인

만약, thread1에서 lock()을 호출하였는데,

🚩

flag를 1로 설정하기도 전에 timer interrupt가 발생하여 thread2로 switch되고 thread2에서도 lock()을 호출하면, 
thread2 입장에서도 flag는 아직 0이므로 
CS에 두 thread가 진입할 수 있게 되어버린다.

 

이러한 문제는, 현재의 flag값을 TEST한 뒤 그에 따라 필요시 flag를 SET하는 전 과정이 atomic하지 않기 때문이다.

🚩

따라서 atomic operation을 가능케 하는 HW의 support가 필요하다.

 

✅Implementation by HW support 1: Test-and-Set을 사용한 Simple spin lock

 

위 함수로써, return(TEST)과 update(SET)이 atomic하게 일어난다.

 

이 코드 상황에서 만약 위와 같은 상황

(thread1에서 lock()을 호출하였는데,
flag를 1로 설정하기도 전에 timer interrupt가 발생하여 thread2로 switch되고 thread2에서도 lock()을 호출)

이 일어났다 생각해 보자.

 

이전과 다르게 여기선 두 thread가 동시에 CS에 들어가는 문제가 발생하지 않는다.

∵ thread1에서 while(TestAndSet(&lock->flag, 1) == 1)까지 수행되고 나서 interrupt에 의해 thread2로 전환돼 버리더라도,

위 while문의 TestAndSet(&lock->flag, 1)에 의해 이미 flag가 1로 설정되어줬기 때문에,

thread2에서 while(TestAndSet(&lock->flag, 1) == 1)가 수행되는 순간에는

TestAndSet(&lock->flag, 1) == 1이기에 thread2는 spinning하게 되어 더이상 진행하지 않는다.

 

✅Implementation by HW support 2: Fetch-and-Add을 사용한 Ticket lock

 

위 함수로써, return(TEST)과 update(SET)이 atomic하게 일어난다. (입력값을 1 늘리며, 기존값을 반환)

 

출처: https://m.blog.naver.com/bell-system/221729001471/

※ ticket의 값은 식권번호, turn의 값은 전광판에 뜬 번호와 같다.

 

* lock() 

ticket += 1 → 이전 사람보다 1 늘어난 값의 식권번호를 받는다. (= myturn)

전광판의 숫자와 내 식권번호가 다르면 spin하며 기다린다.

 

* unlock() 

turn += 1 → 전광판에 다음 번호가 뜨게 된다.

 

 

✅Evaluating HW based spin lock

* Correctness: yes

* Fairness

- TSL: no ∵ fairness가 전혀 고려되지 않음, starvation 발생 가능

- Ticket lock: yes

🚩

* 모든 time slice를 단지 값의 확인에 다 써버리므로 비효율적이다.

 

 

💡Queue: Implementations by OS support

 

✅OS support의 필요성

위의 HW based spin lock의 문제점을 해결할 수 있다. 

 

✅Queue를 사용한 lock: spinning 대신 sleeping

 

※ q: lock을 얻으려 했으나 이미 다른 thread가 차지하고 있어서 못 얻은 thread들이, lock이 free되면 그것을 차지하기 위해, 온 순서대로 대기하는 queue

 

* lock()

guard TEST & SET

현재 flag == 0이었다면 → flag = 1로 설정

현재 flag == 1이었다면 →

   queue_add(): caller thread는 자기 자신을 waiting queue에 추가한다.

🚩

   park(): sleep하러 감

guard = 0로 설정

 

* unlock()

guard TEST & SET

현재 queue가 비어있었다면 → flag = 0로 설정

🚩

현재 queue에 뭔가 있었다면 → unpark(): queue의 한 thread를 wake up함

guard = 0로 설정

🚩

※ guard: flag와 queue의 조작이 atomic하도록 보호해준다. (queue: critical section임)