멀코 5장 non-blocking 알고리즘 - list

최댓값을 모르기 때문이다.

구현이 쉽다.

성능이 안좋다.

O

왼쪽 glock.lock(); glock.unlock(); glock.unlock(); 오른쪽 glock.lock(); glock.unlock(); glock.unlock(); 아래 glock.lock(); glock.unlock(); glock.unlock();

성긴동기화

read only 메모리이기 때문에 data race가 아니기 때문이다.

O

내부적으로 locking이 구현되어 있기 때문이다.

list 전체를 잠그는 것이 아니라 노드 개별로 잠궈서 병렬성을 높이기 위해 나온 것이다.

next field

Add()와 Remove() 시점의 pred, curr가 가리키는 노드는 locking이 되어 있어야 한다., head부터 node 이동을 할 때, lock을 잠그면서 이동해야 한다.

스레드 개수가 늘어날수록 빨라진다. 물론 어느정도 되면 다시 느려진다.

head

coarse-grained synchronization

fine-grained synchronization

optimistic synchronization

lazy synchronization

nonblocking synchronization

Add() 1: prev->lock(); 2: curr->lock(); 3: prev->unlock(); 4: curr->lock(); 5: prev->unlock(); 6: curr->unlock(); 7: prev->unlock(); 8: curr->unlock(); Remove() 1: prev->lock(); 2: curr->lock(); 3: prev->unlock(); 4: curr->lock(); 5: prev->unlock(); 6: curr->unlock(); 7: prev->unlock(); 8: curr->unlock(); Contains() 1: prev->lock(); 2: curr->lock(); 3: prev->unlock(); 4: curr->lock(); 5: prev->unlock(); 6: curr->unlock(); 7: prev->unlock(); 8: curr->unlock();

성긴 동기화

lock(), unlock()이 너무 빈번하다.

길어지는

잠금의 획득과 해제가 너무 빈번하여 이동 시 잠금을 하지 않지 않기 위해 나온 아이디어이다.

delete

validation 조건

재사용되면서 어떻게 사용될지 모르기 때문이다.

잠겨진 pred와 curr가 제거되지 않았는지, pred와 curr 사이에 다른 노드가 끼어들지 않았는지

pred->next == curr 이면 다른 노드가 끼어들지 않은 것이다.

전혀 없다. locking을 하고 검사를 하기 때문이다.

다시 처음부터 검색해서 원래 pred, curr로 다시 올 수 있는지 확인한다.

다른 스레드들이 pred와 curr를 계속 수정하는 경우 계속 재시도를 하면서 기아를 겪을 수 있다.

X

add() validate(pred, curr) false true contains() validate(pred, curr) curr.key == key

X

링크드 리스트에서 성능에 가장 영향에 미치는 것은 검색이다. 성긴 동기화는 한 번 검색하는데, 낙천적 동기화는 처음에 한 번 검색하고 validate 하면서 한 번 더 검색하기 때문에 2배 느리다.

스레드 개수가 늘어남에 따라 싱글 스레드보다 성능이 더 좋아지는 것을 확인했다.

낙천적 동기화는 코어의 개수가 많지 않으면 성능이 좋지 않다. 이것을 개선하고자 나온 것이 게으른 동기화이다.

validate()가 노드를 처음부터 다시 순회하지 않고 수행

O

read-only

marked 필드

먼저

node == pred pred.next == curr node = node.next

validate() !pred.marked && !curr.marked && pred.next == curr contains() curr = curr.next; curr.key == key && !curr.marked

curr.marked = true;

marking 되어 있지 않은 모든 node는 실제 리스트에 존재하는 살아있는 node이다. 해당 명제가 참이기 때문이다.

X

빨라진다. 스레드가 하나일 때는 더 느리지만 이 세상에 싱글코어 컴퓨터는 없다.

블럭킹 알고리즘이다., 메모리 릭이 있다.

재사용하면서 오동작할 수 있기 때문이다.

아무도 remove된 node를 가리키지 않을 때, remove 시점에서 중복실행 중인 모든 method의 호출이 종료되었을 때

O

shared_ptr을 생성할 때 reference counter도 같이 할당해서 이 카운터를 증가하고 감소하면서 0이 되면 해제한다.

shared_ptr 객체를 load, store하는 것이 atomic이 아니기 때문이다.

싱글 스레드에서만 잘 돌아가고 멀티스레드에서는 죽는다.

성긴 동기화, 게으른 동기화, 낙천전 동기화, 세밀한 동기화

게으른 동기화, 낙천적 동기화, 성긴동기화, 세밀한 동기화

잘 돌아간다. 하지만 성능이 엉망진창이다.

X

내부적으로 mutex를 사용하고 또한 하나의 lock으로 실행되기 때문이다.

local atomic shared ptr

X

X

X

if (dataReady == false) return false; temp = g_data;

O

while (true) { int old_sum = sum; int new_sum = old_sum + 2; if (true == CAS(&sum, old_sum, new_sum)) break; }

CAS는 2개의 변수에 동시에 적용할 수 없기 때문이다. 따라서 CAS를 두 번 나누어서 해주어야 하는데 그러면 그 사이에 다른 스레드가 끼어들 수 있다. 난이도가 상승한다.

critical section이 충분히 짧아졌기 때문이다.

pred의 marking을 확인하면서 변경해야 한다.

pred와 next가 curr인 것을 확인하면서 변경해야 한다.

한 장소에 주소와 marking을 동시에 저장했다.

우리의 컴퓨터가 64비트라고 그 비트를 다 사용하지 않는다. 이 중에 안 쓰는 비트를 사용하여 가능하게 한다.

마킹이되었지만 remove되지 않은 노드가 있는 있을 수 있다.

pred.next.comparedAndSet(curr, succ, false, false);

add() find(head, key) new AtomicMarkableReference(curr, false) pred.next.compareAndSet(curr, node, false, false) remove() find(head, key) curr.next.attemptMark(succ, true) pred.next.compareAndSet(curr, succ, false, false)

그냥 포인터가 아닌 합성 포인터를 사용했기 때문이다.

성능이 좋다. 메모리 재사용에 stopation이 생길 수 있다.

EPOCH

Epoch를 사용하기에 정밀하지 않다. 읽고 쓰는 오버헤드가 크다. 데이터 사이즈가 크다.

검색 대상이 아니다. 일종의 최적화 시켜주는 코드

어느 한 스레드의 thread epoch counter가 증가하지 않을 경우 메모리 릭이나 다름 없다.