'lock free algorithm'에 해당되는 글 3건

  1. 2011.11.17 ABA Problem (2)
  2. 2011.11.15 멀티스레드 접근에 안전한 스택 - Interlocked Singly Linked List (1)
  3. 2010.06.22 spin lock 이란 (2)

ABA Problem

2011. 11. 17. 16:21 from 프로그래밍 팁/Thread
 이틀 전에 멀티스레드 접근에 안전한 스택 - Interlocked Singly Linked List을 소개하는 글을 적었다. 관련된 자료들을 검색해보니 자연스럽게 그 다음 스텝인 ABA Problem을 만나게 되어 정리해 둔다.

http://en.wikipedia.org/wiki/ABA_problem

예전에 아꿈사 스터디에서 윤석윤 님( http://seedyoon.tistory.com/ )이 말씀해주신 것을 들어서 알고 있기는 했지만, 그땐 무슨 문제인지 자세하게 몰랐다. ABA라는게 메모리의 할당된 형태를 묘사하는 줄로 이해해서, 서로 다른 크기의 메모리 할당을 번갈아가며 했을때 생기는 문제인가 했는데, ABA는 스레드 접근 순서를 묘사한 것. lock-free 알고리즘을 다룰 때 필수 요소인 CAS(Compare And Swap)연산이 공유 객체의 변경을 감지하지 못하게 되는 현상을 말한다.

왜 감지를 못하게 되는가. 일반적으로 InterlockedCompareExchange(...)를 이용해서 변수의 값을 수정할 때는 거의 걱정할 필요가 없다. 하지만 Interlocked Singly Linked List처럼 자료구조를 사용하게 될 때 주의가 필요하다. 자료구조에 담기는 데이터의 포인터가 시스템에 의해서 재 사용될 수 있기 때문. 스레드 A가 자료구조에 담긴 값(메모리 주소)만을 가지고 값이 변경 되었는지 여부를 감지하고자 하는 순간에, 다른 스레드 B에서 데이터의 push와 pop을 연달아 수행하다 우연히 지워진 메모리 주소가 재사용된다면, 실제로는 값이 변경되었음에도 불구하고 스레드 A는 값의 변경을 알아채지 못하게 된다.

그래서 윈도우에서 사용되는 Interlocked Singly Linked List를 쓸 때에는 주의가 필요하다. 뿐만 아니라 lock-free 방식으로 동작하는 다른 자료구조의 컨테이너를 제작한다 하더라도 이 ABA Problem의 발생에 대해 주의를 기울여야 한다. 

정정. 윈도우xp부터 제공되는 lockfree stack인 Interlocked Singly Linked List는 ABA문제에 대한 걱정 없이 사용 가능하다. 내부적으로 별도의 tag를 달아서 이를 해결하고 있다. 


역시나 구글링한 결과들을 몇 개 나열해 본다.


 



Posted by leafbird 트랙백 0 : 댓글 2

댓글을 달아 주세요

  1. addr | edit/del | reply Favicon of https://devnote.tistory.com BlogIcon leafbird 2012.01.27 18:42 신고

    a classic parallel problem known as ABA, where thread1 observes x == A, thread2 does x=B and then x=A and thread1 then observes x == A.
    아마존에서 책 목차인줄 알고 읽고 보니 어느 독자의 리뷰였던(...) 글 중에서.
    http://www.amazon.com/Art-Multiprocessor-Programming-Maurice-Herlihy/dp/0123705916

  2. addr | edit/del | reply Favicon of https://devnote.tistory.com BlogIcon leafbird 2012.01.27 18:48 신고

    ABA 문제의 해결을 위해서는 데이터 이외의 스탬프 정보가 필요하다는 간략한 메모글.
    http://blog.daum.net/nicegoori/8896304

윈도우 API중에 Interlocked 계열 API들은 멀티스레드 프로그래밍을 할 때 유용하게 쓰인다. 여러 종류의 함수들이 있지만 대부분은 primitive type의 데이터의 값을 증가, 감소, 비교 변경하는 기능을 제공하지만 조금 특이하게 자료구조를 다루는 함수들이 있다.

Interlocked Singly Linked List라는 이름의 이 자료구조는 윈도우에서 기본으로 제공되는, 멀티 스레드의 접근에 대해 단일 액세스를 보장해주는 stack이다. 이름만 봐서는 FIFO로 동작할 것 같지만 실제 동작은 Push/Pop이 같은 곳에서 일어나는 FILO 방식이니 주의해야 한다.

이 스레드 세이프한 스택은 일반적으로 널리 쓰이는 다른 Interlocked 계열 함수들과 연관 지어 알아두는 것보다는 연결 리스트를 다루는 함수들과 연관 짓는 것이 더 맞을지도 모른다. 윈도우는 Singly Linked List와 Doubly Linked List를 기본 지원하는데, 이 중에서 단일 스레드 접근을 보장해주는 단일 연결 리스트 기능이 Interlocked Singly Linked List이다. 기본 연결리스트 기능들은 윈도우 2000부터 지원했고, Interlocked 방식은 윈도우 XP와 Server 2003 버전 이상부터 지원된다. (http://msdn.microsoft.com/en-us/library/ff563802.aspx )

API들의 소개와 샘플 코드를 정리하려고 했는데, 검색해보니 자료가 참 많다. 그리고 이미 매우 잘 정리된 포스팅 들이 많아 무의미 할 것 같다. 구글링한 링크나 몇 개 정리해본다.

그나저나 이런 윈도우 관련 디테일한 지식들을 잘 정리해 놓은 책은 없는지 한 번 살펴봐야겠다. 그냥 작업하다 듣게 되거나 보게 되어서 알게 되는 것 말고 한 방에 싹 공부해두면 좋겠는데. 책을 사두면 레퍼런스로 쓰기도 좋잖아. 혹시 이 글 보이는 분 중에 추천해 주실 책이 있으면 지체 없이 추천 바랍니다 :)

 

Posted by leafbird 트랙백 1 : 댓글 1

댓글을 달아 주세요

  1. addr | edit/del | reply Favicon of https://devnote.tistory.com BlogIcon leafbird 2012.01.27 18:24 신고

    Windows Via C/C++ 책 스터디중.
    윈도우 API에 대한 디테일한 설명이 비교적 잘 나와있는 편이지만
    해당 포스팅에서 다루고 있는 Interlocked Singly Linked List에 대해서는 자세히 나와 있지는 않다.
    딱 네 줄 나옴(293p). API 소개하는 책이니 만큼 ABA 문제 등에 대한 설명은 없다.

spin lock 이란

2010. 6. 22. 16:41 from 프로그래밍 팁/C++
MO 스케일 게임서버 제작에서 MMO 스케일 게임서버 제작으로의 전환에서 가장 눈에 띄는 부분은
요즘엔 예전보다 좀 더 성능에 prority를 둔 code들을 자주 접하게 되고, 또 그렇게 변해야 한다는 점입니다.
제가 아는 한에서는 MMO 서버들도 비지니스 로직의 처리를 단일 스레드로 설계한 프로젝트들이 많은 걸로 아는데... 그래도 MO 프로젝트들 보다는 멀티 스레드 구조들을 더 많이 접하게 되는 건 자연스러운 부분이겠지요.
예전에는 사소한 성능 향상보다는 단순함(simplity)을 추구하겠다는 핑계(?)로 멀리했던 기법들을 새삼 정리해봅니다.
spin lock에 대한 제대로 된 검색은 이번에 처음 해보는군요. 최근에 아주 멋있는(...) 기술로 다가왔던 lock-less algorithm 혹은 lock-free algorithm도 뭐... spin lock과 유사한 의도에서 발전됐다고 볼 수 있겠습니다.

lock free 알고리즘에 대해서 한 번 더 정리할 기회가 있으면 좋겠지만...
왠지 게으름 피우다 안할 것 같아서 한마디로만 간단히 적자면, 스레드간의 context switching을 하지 말자는 접근쯤 되는군요. 재작년쯤 처음 들었을 때는 굉장히 참신한 아이디어구나! 싶었는데 그정도는 아닌 듯 ^^;...

출처 : http://www.gpgstudy.com/forum/viewtopic.php?t=13031

 

myevan 씀:

스핀락이란
"조금만 기다리면 바로 쓸 수 있는데 굳이 컨텍스트 스위칭으로 부하를 줄 필요가 있나?" 라는 컨셉으로 개발된 것으로
크리티컬 섹션에 진입이 불가능할때 컨텍스트 스위칭을 하지 않고 잠시 루프를 돌면서 재시도 하는 것을 말합니다.

Lock-Unlcok 과정이 아주 짧아서 락하는 경우가 드문 경우(즉; 적절하게 크리티컬 섹션을 사용한 경우) 유용하며
코드:
 
Lock()
memcpy(dst, src, len);
Unlock();

위처럼 시간이 오래걸리는 크리티컬 섹션이 많을 경우라던지
여기저기서 동시에 크리티컬에 진입하려는 경우가 많은 경우에는
오히려 더 나빠질 수 있습니다.


상당히 정확한 답변입니다. 첨언하면 스핀락을 잘못 사용하면 CPU 사용률 100%를 만드는 상황이 발생하므로 주의 하여야합니다. 스핀락은 기본적으로 무한 for 루프를 돌면서 lock을 기다리므로 하나의 쓰레드가 lock을 오랫동안 가지고 있다면, 다른 blocking된 쓰레드는 busy waiting을 하므로 CPU를 쓸데없이 낭비하게 됩니다.

스핀락을 잘 사용하면 context switch를 줄여 효율을 높일 수 있습니다. 그리고 윈도우즈의 스핀락은 그다지 효율적이지 않습니다. 무한 루프를 돌기 보다는 일정 시간 lock을 얻을 수 없다면 잠시 sleep하는 back off 알고리즘을 사용하는 것이 훨씬 좋습니다. 아래 논문과 위키 페이지를 참고하시기 바랍니다.

http://www.cs.washi...om/pubs/spinlock.pdf


http://en.wikipedia.org/wiki/Spinlock
Posted by leafbird 트랙백 0 : 댓글 2

댓글을 달아 주세요

  1. addr | edit/del | reply Favicon of https://serverdown.tistory.com BlogIcon 그건일 2011.09.17 16:52 신고

    최근에 이 글을 참고해서 정리했습니다.
    http://serverdown.tistory.com/239
    평가 부탁드려요 ~~

    • addr | edit/del Favicon of https://devnote.tistory.com BlogIcon leafbird 2011.09.19 18:19 신고

      안녕하세요~
      혼자 볼려고 적어둔 제 글이 참고가 된다니 영광입니다 :)