CppCon 2014: Herb Sutter "Lock-Free Programming (or, Juggling Razor Blades)"

Boost libarary를 공부하고 있는데,

Chapter 10: Concurrency with Boost 부분을 마치고, reference에 Herb Sutter의 강연 동영상 링크가 있길래 호기심에 찾았다가, 좋은 내용인것 같아서 이틀에 걸쳐 시청을 완료했다.

Lock-free programming에 대해 친절하게 설명해 주고 있어, 나중에 다시 참고할 필요가 있을 것 같아 갈무리 해 둔다. (시간이 지나면 또 잊어 버릴 수 있으니... oTL)

Multi-threaded programming을 많이 하지 않다보니, 취약한 부분인데 많은 도움이 되었던 것 같고, 중요(?) 키워드는 다음과 같다.

• std::atomic 또는 std::atomic_xxx()
• ABA problem - 첫 번째 thread가 최초 참조한 object가, 두 번째 thread에 의해 변경(삭제 후 다시 생성하였지만, 동일한 주소 또는 위치를 유지)되었지만, 실제로는 다른 object로 변경된 경우 발생하는 문제
• Linearizability - concurrent programming에서, 두 operation이 겹쳐진 경우(overlapped)에도, 결과적으로는 순차적으로 실행된 것처럼 동작하는 성질(?)
• Constructor와 destructor는 concurrency관련 이슈가 없다. (instance의 lifetime은 destructor가 호출 되는 순간 끝난다)
  

다음에 짬 내서, "Herb Sutter - atomic<> Weapons"도 봐야겠다.

find와 pop_front를 생각 해 보면,
find가 먼저 시작되고, 나중에 pop_front가 실행되는 경우,
1) find는 head pointer를 먼저 획득한 상태.
2) pop_front가 first node(A)를 제거하고, head를 변경하였더라도,
   기존의 find는 (A)의 strong ref를 가지고 있기 때문에,
   이를 가지고 find를 이어나갈 수 있다. (만약 (A)의 next를 변경 한 경우는?)
   그리고 새로운 find는 새로운 head를 가지고 수행할 수 있다.
3) pop_front를 호출한 놈은, (A)를 가지고 지지고 복고 한 후, scope를 벗어나더라도 ref count만 감소 시키므로,
   (A)는 find에서 여전히 유효하다.
4) 다음 operation을 수행하는 thread는 pop_front에서 변경된 head를 기반으로 수행하기 때문에,
   별 문제가 되지 않는다.
5) (A)는 find가 찾던 node가 아니면 reference가 사라지므로 제거
               찾던 node라면 move()반환 되므로, find caller가 지지고복고 한 후 보관하던 제거되던 한다.

              
    void push_front(T t) {
        std::shared_ptr<Node> p = std::make_shared<Node>();
        p->t = t;
        p->next = head;
        while (!std::atomic_compare_exchange_weak(/* p */&head, /* expected */&p->next, /* desired */p)) {}
        //Compares the shared pointers pointed-to by p and expected.
        //If they are not equivalent, assigns *p into *expected
        //using the memory ordering constraints specified by failure and returns false.
    }

    여기서 내가 하고자 하는 것은, 내가 p->next에 저장했던 head와 현재의(다른 thread에 의해 변경되었을지도 모르는) head를 비교해서,
    같으면, 변경이 되지 않았으므로 head를 p(새로운 node)로 변경하면 성공. std::atomic_compare_exchange_weak이 true를 반환하므로 바로 끝난다.
    다르다면, 다른 thread에 의해 head(공유변수)가 변경된 것이므로, 내가 저장했던 p->next는 새로 업데이트 되어야 하고, head로 변경이 되고 false를 반환.
            그러면 while에 의해 다시 확인을 하게 되고, 다른 thread가 상태를 변경하지 않을 때까지 반복한다.