暗記メーカー
ログイン
멀코 7장. STACK, SKIP-LIST
  • ユーザ名非公開

  • 問題数 42 • 12/4/2023

    記憶度

    完璧

    6

    覚えた

    16

    うろ覚え

    0

    苦手

    0

    未解答

    0

    アカウント登録して、解答結果を保存しよう

    問題一覧

  • 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, 헤저드 포인터 등을 사용해서 재사용을 해줘야 한다.