멀코 7장. STACK, SKIP-LIST

큐는 오래전에 넣은 데이터를 꺼내는 것이고 스택은 제일 최근에 넣은 데이터를 꺼내는 것이기 때문이다.

X

모든 push, pop이 충돌한다. 즉, 자료구조 자체가 병렬성이 없다. 이건 스택 자료구조의 근본적인 문제이다.

스택은 탑에서 계속 push, pop하기 때문에 확률이 더 높다.

스택의 top에 대한 성공한 cas 호출의 순서로 하나씩 진행되므로 순차병목현상이 나타날 수 있다.

무제한 무잠금 스택에서 top에 대한 경쟁이 심한 것을 좀 줄이기 위해 나왔다.

다 똑같은 시간을 기다리면 충돌이 나기 때문이다. 따라서 각 스레드마다 랜덤한 시간을 기다리도록 해야 한다.

순서 정해주는 것 역시 atomic 변수로 해줘야해서 오버헤드가 크기 때문이다.

sleep_for는 운영체제 호출이다. 단지 옆 스레드가 CAS 작업하는 동안만 기다리면 되는데 운영체제 들어갔다 오는 시간이 너무 길다.

코어가 많은 프로그램에서 사용할 때 (블럭킹 알고리즘에서는 많은 성능향상을 볼 수 있다.)

클럭이 빠르면 빠르게 흘러가고, 느리면 느리게 흘러간다. 어셈블리어이기 때문에 64비트에서는 안돌아간다.

push와 pop이 거의 동시에 일어난다면 두 연산은 스택에 접근하지 않고 취소되어 없어지게 한다.

충돌이 심할 때는 크기를 늘리고, 적을 때는 줄이기 위해서이다.

lock-free

X

O

단지 교환대상이 바뀐 것 뿐이고 값도 그대로이기 때문에 아무 문제가 없다.

너무 짧은 교환 시간은 항상 실패를 하게 되기 때문이다.

처음부터 교환이 없었거나, 같은 종류의 연산과 값이 교환되었을 경우이다.

O

검색시간 O(n)이기 때문이다.

재균형(Rebalancing)

평군 검색시간이 O(logn)이다. 재균형작업이 필요없다. 랜덤 자료구조이다. worst case O(n)이다.

지름길

2의 i승 - 1

X

skip list

모든 링크가 다 연결되었을 때 marking이 false일 때

std::recursive_mutex 하나의 노드를 여러 번 잠글 수 있도록 하기 위해서이다. 이걸 사용하는 것이 프로그래밍이 좀 더 깔끔해진다.

위쪽 링크가 다 연결되지 않았을 경우가 있을 수 있기 때문이다. 리턴 값과 최고 레벨을 비교하여 pred, curr가 모든 레벨의 링크를 담고 있는가를 확인한다.

노드가 추가되는 동안 앞 노드가 변경되는 것을 방지하기 위해서이다.

while (!nodeFound.fullyLinked) {} 곧 add를 할 애니까 처음부터 하는게 아니라 기다렸다가 add가 끝나면 return false를 하기 위한 것이다.

Add(), Remove()는 여태까지 한 것이 아까워서 기다렸지만 Contains는 locking한 것도 없기 때문이다.

Remove()에서 논리적으로 제거 후, 물리적 제거는 Find()에서 한다.

게으른: 모든 리스트가 연결되면 LF: 0층이 연결되면

CAS를 한 방에 사용하기에 무리가 있기 때문이다.

O

최상층부터 지워나가야 한다. 절대로 최하층부터 지우면 안된다.

O

lock-free skiplist의 Find()는 marking되어 있는 것을 찾으면 지운다.

Find()는 wait-free가 아닌 lock-free로 구현되어 있기 때문이다.