問題一覧
1
스택이 큐보다 캐시와의 상성이 더 좋은 이유는?
큐는 오래전에 넣은 데이터를 꺼내는 것이고 스택은 제일 최근에 넣은 데이터를 꺼내는 것이기 때문이다.
2
뮤텍스보다 카스 오버헤드가 더 크다. ( O / X )
X
3
무제한 무잠금 stack인데 코어가 늘어날수록 느려지는 이유는 무엇인가?
모든 push, pop이 충돌한다. 즉, 자료구조 자체가 병렬성이 없다. 이건 스택 자료구조의 근본적인 문제이다.
4
스택이 큐보다 ABA 문제가 생길 확률이 더 높은 이유는 무엇인가?
스택은 탑에서 계속 push, pop하기 때문에 확률이 더 높다.
5
무제한 무잠금 stack의 단점은 무엇인가?
스택의 top에 대한 성공한 cas 호출의 순서로 하나씩 진행되므로 순차병목현상이 나타날 수 있다.
6
Back off 방법이 나온 계기는 무엇인가?
무제한 무잠금 스택에서 top에 대한 경쟁이 심한 것을 좀 줄이기 위해 나왔다.
7
back off 방법에서 기다리는 시간을 똑같이 설정하지 않는 이유는?
다 똑같은 시간을 기다리면 충돌이 나기 때문이다. 따라서 각 스레드마다 랜덤한 시간을 기다리도록 해야 한다.
8
back off에서 랜덤하게 해도 제대로 돌아가지 않을 수 있는데 그렇게 하는 이유는?
순서 정해주는 것 역시 atomic 변수로 해줘야해서 오버헤드가 크기 때문이다.
9
이 코드의 문제점은 무엇인가?
sleep_for는 운영체제 호출이다. 단지 옆 스레드가 CAS 작업하는 동안만 기다리면 되는데 운영체제 들어갔다 오는 시간이 너무 길다.
10
back off의 성능은 어떠한 상황일 때 더 효율이 좋은가?
코어가 많은 프로그램에서 사용할 때 (블럭킹 알고리즘에서는 많은 성능향상을 볼 수 있다.)
11
여기서 사용된 RDTSC를 사용하면 안좋은 이유를 설명하시오.
클럭이 빠르면 빠르게 흘러가고, 느리면 느리게 흘러간다. 어셈블리어이기 때문에 64비트에서는 안돌아간다.
12
소거의 아이디어는 무엇인가?
push와 pop이 거의 동시에 일어난다면 두 연산은 스택에 접근하지 않고 취소되어 없어지게 한다.
13
Elimination Array에서 array의 크기가 가변인 이유는?
충돌이 심할 때는 크기를 늘리고, 적을 때는 줄이기 위해서이다.
14
소거에서 교환은 ( )로 이루어져야 한다.
lock-free
15
back-off는 성능 향상을 위해 사용하는 것이다. ( O / X )
X
16
소거는 성능 향상을 위한 것이다. ( O / X )
O
17
무잠금 무제한 스택에서 소거를 하기위한 무잠금 교환자에서 ABA 문제가 상관없는 이유는?
단지 교환대상이 바뀐 것 뿐이고 값도 그대로이기 때문에 아무 문제가 없다.
18
무제한 무잠금 스택에서 소거에 필요한 무잠금 교환자에서 타임아웃 시간을 고를 때 주의해야 하는 이유는?
너무 짧은 교환 시간은 항상 실패를 하게 되기 때문이다.
19
무제한 무잠금 스택에서 소거 배열의 교환이 실패했다면 원인은?
처음부터 교환이 없었거나, 같은 종류의 연산과 값이 교환되었을 경우이다.
20
EliminationBackoffStack에서 소거된 연산은 절대로 스택에 접근하지 않는다. ( O / X )
O
21
set을 실제로 사용하기 무리가 있는 이유는?
검색시간 O(n)이기 때문이다.
22
일반적인 트리구조에서는 트리 깊이의 균형을 유지하기 위해서 정기적인 ( ) 작업이 필요하다.
재균형(Rebalancing)
23
SkipList의 특징을 설명하시오.
평군 검색시간이 O(logn)이다. 재균형작업이 필요없다. 랜덤 자료구조이다. worst case O(n)이다.
24
순차 스킵리스트에서 더 높은 층의 리스트는 낮은 층의 리스트에 대한 ( )이다.
지름길
25
순차 스킵리스트에서는 계층의 각 연결은 바로 아래 계층의 ( )개의 노드를 건너 뛴다.
2의 i승 - 1
26
CAS는 하드웨어가 지원을 해주지 않아도 소프트웨어로 구현이 가능하다. ( O / X )
X
27
범위가 클 경우 skip list와 linked list 중 어떤 것을 쓰는 것이 더 좋은가?
skip list
28
잠금 기반의 병행 스킵리스트에서 노드가 스킵리스트에 언제 추가되는가? (즉, add가 언제 완료되었다고 인정되는가?)
모든 링크가 다 연결되었을 때 marking이 false일 때
29
잠금 기반의 병행 스킵리스트에서 쓰는 mutex는 어떤 것인가? 왜 그것을 사용하는가?
std::recursive_mutex 하나의 노드를 여러 번 잠글 수 있도록 하기 위해서이다. 이걸 사용하는 것이 프로그래밍이 좀 더 깔끔해진다.
30
잠금 기반의 병행 스킵리스트의 Find()에서 검색이 끝난 후 최고 레벨을 리턴하면 곤란한 이유는? 이것의 해결방안은?
위쪽 링크가 다 연결되지 않았을 경우가 있을 수 있기 때문이다. 리턴 값과 최고 레벨을 비교하여 pred, curr가 모든 레벨의 링크를 담고 있는가를 확인한다.
31
잠금 기반의 병행 스킵리스트의 Add()에서 앞 노드들을 잠그는 이유는?
노드가 추가되는 동안 앞 노드가 변경되는 것을 방지하기 위해서이다.
32
잠금 기반의 병행 스킵리스트의 Add()이다. 빨간색 안에 들어갈 코드를 쓰시오. 그리고 이유도 쓰시오.
while (!nodeFound.fullyLinked) {} 곧 add를 할 애니까 처음부터 하는게 아니라 기다렸다가 add가 끝나면 return false를 하기 위한 것이다.
33
잠금 기반의 병행 스킵리스트(게으른 동기화)의 Contains()에서는 fullyLinked를 기다릴 필요가 없는 이유는?
Add(), Remove()는 여태까지 한 것이 아까워서 기다렸지만 Contains는 locking한 것도 없기 때문이다.
34
Lock-free SkipList에서 제거는 어떻게 이루어지는가? ( 논리적, 물리적 제거)
Remove()에서 논리적으로 제거 후, 물리적 제거는 Find()에서 한다.
35
게으른 동기화 skip list와 LF 동기화 skip list의 추가되는 시점의 정의는?
게으른: 모든 리스트가 연결되면 LF: 0층이 연결되면
36
Lock-free SkipList에서 fullyLinked를 사용할 수 없는 이유는?
CAS를 한 방에 사용하기에 무리가 있기 때문이다.
37
Lock-free SkipList에서는 맨 밑바닥 층만 연결되면 문제없이 돌아간다. ( O / X )
O
38
Lock-free SkipList에서 Remove()를 할 때 어느 층부터 지워야 하는가?
최상층부터 지워나가야 한다. 절대로 최하층부터 지우면 안된다.
39
Lock-free SkiplList에서는 아래 링크만 잘 되어 있으면 위에 링크가 조금 어질러져 있어도 잘 돌아간다. ( O / X )
O
40
게으른 동기화 skiplist와 lock-free skiplist의 Find()의 차이는?
lock-free skiplist의 Find()는 marking되어 있는 것을 찾으면 지운다.
41
lock-free skiplist의 wait-free Contains()을 구현하기 위해서 Find()를 쓰면 안되는 이유는?
Find()는 wait-free가 아닌 lock-free로 구현되어 있기 때문이다.
42
우리가 만든 LF_SKIPLIST를 사용하지 못하는 이유는? 해결책은?
메모리 릭 때문이다. shared_ptr, EBR, 헤저드 포인터 등을 사용해서 재사용을 해줘야 한다.