問題一覧
1
queue에는 contains() 메소드가 없다. ( O / X )
O
2
set에는 contains() 메소드가 없다. ( O / X )
X
3
Pool 객체는 같은 아이템의 ( ) 존재를 허용
복수
4
제한 큐를 멀티 스레드에서 사용하지 못하는 이유는?
제한 큐가 꽉 찼을 경우 블럭킹이 되는데 이는 넌블럭킹의 취지와 맞지 않기 때문이다.
5
제한 큐의 장점을 말하시오.
구현하기 쉽다. 메모리 릭이 없다. 성능이 빠르다.
6
무제한 큐의 push에는 제한이 없다. ( O / X )
O
7
부분 큐를 멀티 스레드 프로그래밍에서 사용하지 않는 이유는?
큐가 비어있으면 누군가가 넣을 때까지 기다려야 하는데 이것은 블럭킹이기 때문이다.
8
무제한 완전 큐 구현 시 성긴 동기화(Coarse Grain)으로 구현할 시 2배 성능향상을 보는 방법은?
enq와 deq는 동시에 해도 상관이 없으니 enq_lock과 deq_lock을 따로 두어서 하면 된다.
9
이 코드의 문제점은 무엇인가?
자체적으로 문제가 없지만 다른 스레드를 기다리는 알고리즘이므로 블럭킹 알고리즘이다.
10
이 코드의 문제점은?
엄청난 data race이다. 실패해서 tail을 수정하려고 할 때, 또 중간에 다른 스레드가 끼어들 수 있다.
11
빈칸에 들어갈 코드를 쓰세요.
CAS(&tail, last, e); CAS(&tail, last, next);
12
이 코드의 문제점과 해결책을 말하시오.
문제점 head->next는 내가 관리하는 것이 아니다. 따라서 head->next를 다른 스레드가 delete하면 문제가 발생한다. 해결책 head->next의 값도 미리 읽어서 중간에 다른 스레드가 끼어들었는지 추가로 검사해야 한다.
13
이 코드에 문제점은 무엇인가?
enq와 deq가 만나는 순간 오류가 발생할 수 있다. enq가 들어와서 화살표를 바꾸고 tail을 옮기려고 하는데 그 때 deq가 들어와서 head를 전진하고 원래 가르키던 노드를 delete하는데 tail은 아직 전에 노드를 보고 있다. 그러면 다음 enq 때 죽게 된다.
14
빈칸에 들어갈 코드를 적으시오.
CAS(&tail, last, next);
15
멀티스레드가 죽는 이유는 무엇들이 있는가?
data race compile 최적화 out of order cache line ABA
16
lock-free 무제한 큐에서 드물게 죽는 이유는 무엇인가?
node를 재사용해서 생기는 문제 중에 하나인 ABA 문제 때문이다.
17
set에서는 ABA 문제가 없었던 이유는?
메모리를 삭제하지 않았기 때문이다.
18
shared_ptr를 사용하면 ABA 문제가 없다. ( O / X )
O
19
EBR은 ABA 문제가 있다. ( O / X )
X
20
ABA 문제의 해결책에는 무엇들이 있는가?
스템프드 포인터 / LL, SC shared_ptr 사용 별도의 메모리 관리 기법 사용 (EBR, Hazard pointer)
21
ABA 문제를 해결하기 위한 stamped pointer에 대한 설명을 하시오.
포인터에 버전도 같이 할당하는 것이다. stamped pointer를 사용해도 ABA 문제가 완전히 해결되는 것은 아니지만 확률은 지극히 낮아진다. 32비트에서는 0, 1, 2, 3밖에 표현되지 않아서 64비트 CAS로 변경해서 사용해주어야 한다.
22
ABA 문제의 해결책인 LL, SC에 대해 설명하시오.
LL로 읽고, SC로 적는다. 값이 같아도 다른 스레드가 건드렸으면 실패를 리턴한다. 값을 검사하는 것이 아니라 변경 여부를 검사하는 것이다.
23
LL, SC가 wait-free가 불가능한 이유는?
wait-free라면 충돌해도 전진해주어야 하는데, 전진이 막힐 수 있다.
24
shared_ptr을 ABA 문제의 해결책이지만 사용하지 않는 이유는?
shared_ptr이 lock-free가 아니기 때문이다. 이것을 사용하는 순간 lock-free 알고리즘이 아니게 된다.
25
stemped pointer의 단점을 적으시오.
ABA문제에만 최적화 되어 있다. 구현이 어렵다. 메모리 재사용 문제를 완벽히 해결할 수 없다.
26
우리가 구현한 lock-free queue의 문제점은 무엇이었는가?
메모리 릭 존재 ABA 문제 존재