일전에 이 블로그에서 Interlocked Singly Linked List(이하 SList)를 소개하는 포스팅을 한 적이 있다. 윈도우 XP 버전부터 지원된 기능이지만 존재 사실을 뒤늦게 알고 블로그에 적어두었다.

그리고는 그 바로 다음 포스팅으로 ABA Problem에 대해 정리하면서, SList도 ABA문제에 대한 대비가 되어 있지 않으니 사용할 때 주의해야 한다고 적어놓았다. 하지만 내용이 틀렸다. SList는 ABA문제를 내부에서 자체 방지하도록 처리되어있으므로 사용하는 입장에서는 신경 쓸 것이 없다.

변명을 좀 하자면 처음에 잘못 알고 있게 된 계기는 GPG Study의 락프리 관련 스레드에서 읽은 내용 때문이다. 스레드 가장 하단에 어느 분이 SList를 소개하면서 아래처럼 적어두셨기 때문.

…Windows API 중에 최근에 추가된 다음 API는 Lock-Free로 구현된 Single Linked List를 제공합니다. 그런데 Lock-Free에서 악명 높은 문제 중의 하나인 ABA 문제로 인해 범용 linked list로 사용하기 어려운 제약사항을 가지고 있습니다…(후략)

그래서 정말 위의 말이 사실인지 MSDN을 열심히 찾아봤었지만 ABA문제에 대한 언급을 찾지 못했다. 그래서 위에 인용한 말을 그대로 믿고 있었는데 – 사실 저도 피해자 입니다 ㅜㅜ – 우리 팀에서 SList를 아주 요긴하게 잘 사용하고 있어서 이 물건이 ABA 걱정 없이 사용 가능하다는 걸 알게 되었다 ㅎ 그러고는 블로그에 잘못된 정보를 올려놓은 게 마음이 쓰여서 정정 포스팅을 해야겠다고 마음먹은 지는 한참이 지났건만 이제야 글을 올린다…;;

꼬꼬마 시절의 몇 년 전에는 MSDN 안에서만 조금 뒤적이다가 포기했지만 구글에서 다른 글들을 검색 해보면 SList를 야무지게 잘 사용하고 있는 많은 사례들을 찾을 수 있다. 그리고 레이몬드 첸의 The Old New Thing에서는 보다 확실한 증거를 찾을 수 있는데, SList 사용시의 제약사항인 메모리 정렬이 32bit와 64bit간에 서로 다른 이유에 대해 적은 포스팅 Thy are the alignment requirements for SLIST_ENTRY so diffrent on 64-bit Windows?를 보면 아래 내용이 나온다.

Why are the alignment requirements greater than the natural word size? To avoid the ABA problem. A standard workaround for the ABA problem is to append additional information (a "tag") to the pointer so that when the value changes from B back to A, the tag ensures that the second A still looks different from the first one…(후략)

글 자체의 주제는 지금 내가 하려는 말과는 조금 다르지만, 아무튼 ABA 현상의 해결을 위해 여분의 공간을 사용해야 하고, 이 때문에 MEMORY_ALLOCATION_ALIGNMENT크기로 정렬을 해야 한다는 말이 나온다.

이 블로그를 착실히 읽는 사람이 얼마나 있겠냐 만은 혹시나 예전에 내가 잘못 적어둔 내용 때문에 SList의 사용을 망설이고 있는 사람이 있다면 이젠 걱정 없이 마음 껏 쓰시라. 구글링 해보면 주로 나오는 활용 사례는 스레드 이슈가 많은 IOCP 워커 부분이라든지, 커스텀 메모리 할당자 구현 등이다. 앞에서 말했듯이 지금 회사에서 짜는 코드에서도 잘 써먹고 있음. 메모리 정렬을 신경 써 주어야 하는 게 조금 까다롭지만, 그것만 조심하면 lockfree 자료구조를 얻는 셈이니 그리 나쁘지 않은 흥정이다.



Posted by leafbird 트랙백 0 : 댓글 0

댓글을 달아 주세요