[병렬프로그래밍] Spin Lock

1. Shared Bus

 snooping 메모리 트래픽이 있는 걸 알아서 기다림

2. Distributed

 each processor has partial of memory, cache internal circuit. Not share big bus

 

만약 Lock이 없다면 어떻게 해야할까? "spin" or "busy-wait"

 

memory bus 에 계속 read 요청 -> 오히려 spinlock 때문에 안좋은 결과가 발생

Test-and-Set

Consensus number 2

swap true with current value

return priori value

 

Tas Lock

if ret == false -> get lock

if ret == true -> not get lock

space O(1) - 하나의 변수에 TAS를 계속 반복

 

오히려 느려지는 결과

 

TTas Lock (Test and Test and Set)

atomic instruction 이 비싼이유 - cache line을 block 하기 때문

TTAS -> keep check

T(Read)

TAS(Read Modifiy Write)

 

즉, Lurking(hide) stage & pouncing(execution) stage로 이루어짐

 

TAS보다는 빨라짐

 

 

TAS 와 TTAS가 느린 이유 : cache flag를 broadcast 해줘야함

 

Backoff Lock

계속 접근하지 않고, hybrid하게 시간을 늘리면서 sleep 했다가 시도

 

 

Anderson QueueLock

Lock 하나당 Thread 만큼의 bool flag를 둬서 각자 다른곳에서 validate를 체크

그렇지만, 여전히 같은 cache line 에 있는 bit가 많음

ex) 0~15 까진 같은 cache line

solution = padding - bit를 멀리 떨어트려 놓음

 

 

CLH Lock

L : Lock 갯수, N : Thread 개수

Anderson QueueLock 에서 space complexity 가 O(L * N) 인 것을 

O (L + N)으로 줄인 Lock

 

MCS Lock

CLH Lock은 Shared Bus Architecture 에선 좋지만, 프로세스 별 독립적인 별도의 메모리를 제공하는 Uncached NUMA Architecture에서는 좋지 않다. 왜냐하면 NUMA Machine에서는 remote memory는 느리고 할당받은 local memory는 빠르기 때문이다.

 

CLH Lock에서 Link를 추가하는 것으로 구현한다