8. Locks

6장 thread에서 이어지는 내용이다.

 

Lock Goal

이미 한번 봤던 내용이지만, lock의 구현 목표는 다음과 같다.

Correctness	Fairness	Performance
Mutual exclusion Deadlock-free Starvation-free	wait for same amount of time	CPU is always used

 

Locking linked lists

Linked list에 node를 추가하려고 할 때, race condition에 빠질 수 있다. 이를 위해 lock을 구현해야 한다. 그러기 위해 우선 linked list에 lock을 추가한다.

Head 부분의 구조체에 mutex를 추가한다. 그리고 linked list 초기화할 때, lock을 NULL로 설정해 준다.

 

List에 insert하거나 lookup할 때, lock을 잡도록 구현한다. 또한, concurrency를 살리기 위해, lock이 필요한 ciritical section은 최대한 작게 설정한다. 

 

Peterson's algorithm

오직 2개의 thread만이 동작하며 load와 store만 수행한다고 가정한다.

Peterson 알고리즘에서 thread가 lock을 사용하는 방법이다.

 

Race condition이 발생해도, deadlock이 발생하지 않는다는 장점을 가지고 있다.

위 경우가 가장 tricky한 race condition일텐데, thread 0과 1 모두 wait이 되었다가 thread 0이 turn==0에 의해서 lock을 얻게 된다.

 

이렇듯, peterson 알고리즘은 모든 thread가 영원히 while 문을 돌지 않는다는 장점을 가지고 있다. 그러나 peterson 알고리즘은 relaxed memory consistency model을 사용하는 modern hardware에서 동작할 수 없어 사용할 수 없다. 

(*relaxed memory consistency models: 메모리 동기화 방법 중 하나, 다른 thread에 즉시 반영 안될 수 있음)

 

xchg

xchg는 Peterson 알고리즘의 대체로, atomic exchange를 통한 lock 구현이 목표로 test-and-set이라고도 불린다. xchg의 구현은 다음과 같다.

• 하는 일: pointer에 새로운 값 저장
• return value: pointer에 원래 저장되어 있던 값

 

실제로 lock은 다음처럼 사용된다. (spin-lock 구현)

test-and-set

lock의 flag에 1을 저장할 건데, 만약 lock의 flag 값이 원래 1이었으면 다른 thread에서 사용하고 있는 것이므로 spin wait한다. 그리고 다른 thread가 release를 통해 flag를 0으로 바꾸면, 현재 thread에서 이를 1로 바꾸고 lock을 얻을 수 있게 되는 것이다.

 

Other atomic HW instruction

Compare-and-swap

 

Fairness: Ticket Locks

기본적인 spinlock은 unfair하다는 것을 알아야 한다. 가령 thread가 스케쥴러의 runtime을 계산하고 runtime이 종료되기 직전에 lock을 얻는다면, 다른 thread는 spin만 하게 되어 동작할 수 없게 된다.

 

Ticket lock의 아이디어는 간단하다. 위와 같은 경우를 방지하기 위해, unlock했다가 lock을 바로 잡을 수 없게 만들었다. Thread는 lock을 잡을 때 ticket num을 잡게 되고, unlock할 때 turn++을 수행하게 된다. 이를 위해 새로운 atomic function이 제안된다.

Fetch-and-add

Lock을 얻을 때는, ticket의 값을 가져오고 ticket++를 수행한다. 그리고 가져온 ticket != turn이면 spin하게 된다. 반대로 unlock할 때는, 간단하게 turn++를 수행해 다음 ticket을 잡은 thread가 수행할 수 있게 만들어 준다. 실제 사용은 다음과 같다.

Ticket lock

 

예시 동작은 다음과 같다.

 

Spin lock problem

Spin lock의 문제점은 스케쥴러가 thread가 lock 때문에 wait하고 있는 것인지 모른다는 것이다. 그래서 A의 lock이 풀리기를 기다리는 B를 unit time동안 CPU spin을 하게 된다. 이를 해결하는 가장 쉬운 방법은 spin하지 말고, yield()를 통해 CPU 사용을 멈추는 것이다. Ticket lock에 구현하면 다음과 같다.

Ticket lock with yield()

이렇게 되면 스케쥴링은 다음처럼 빨라진다.

 

물론 여전히 thread가 많아지면 spin을 통한 lock 확인 후 yield()를 수행해야 하기 때문에, 느리다. 이를 해결하기 위해서 thread를 waiting queue를 통해 관리하는 방법을 사용한다.