art.oriented : 자료구조 Stack 만들기 문제

minjang.egloos.com

소개 · 이전글 · 2008년 10월

컴퓨터 · 그리고 · 나머지

2008년 7월 4일에 수정: 아래 Lock-free stack을 만들라는 문제는 모 회사의 프로그래밍 면접에서 받은 문제였다. 그 당시에는 Lock-free 자료구조를 몰라 제대로 답을 할 수가 없었는데 알고보니 Lock-free data structures로 매우 많이 연구된 분야이다. 일단 Wiki에서 Compare-and-set 부터 시작해서 글 타래를 읽어보면 엄청난 자료들을 만날 수 있다.

참고문헌: Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup. Lock-free Dynamically Resizable Arrays

Stack과 Queue. 전산학과 1학년들도 만들 수 있는 매우 기초적인 자료구조. 한번 Stack 자료구조를 만들어 보시오. 단 다음과 같은 조건을 지켜야 한다.

Stack의 Push와 Pop을 구현하라.
이 Stack은 thread-safe 해야한다. 즉, 여러 스레드들이 Push와 Pop을 호출해도 자료구조는 손상 없이 제대로 작동해야한다.
그러나 lock 혹은 mutex는 쓸 수 없다. 즉, 단순히 critical section으로 만들면 안된다.
오직 atomic operation (test-and-set 혹은 compare-and-swap) 만 이용하는 Lock-free stack을 만들어라.
15분안에 푸시오.

왜 이런 문제를 내느냐? 락이 있고 없고의 성능차가 제법, 혹은 엄청나게 차이가 나기 때문이다. 보통 일반적인 critical section의 구현은 block-wait로 구현이 되어있다 (즉, kernel-user transition이 유발). 이 경우, Push/Pop이 두개 이상의 스레들로부터 매우 빈번히 불리면 block-wait에 들어가는 비용이 너무 커진다. 그래서 CPU utilization도 낮아지고 (실제로 이런 경우, 돌려보면 CPU 소비율이 꽤 낮게 측정된다) 전체적인 throughput이 저하되기 때문에 이런 전통적인 방식의 락은 최소화 해야한다.

# by object | 2008/02/12 14:54 | 컴퓨터 | 트랙백(3) | 핑백(2) | 덧글(16)

트랙백 주소 : http://minjang.egloos.com/tb/1746018
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]

Tracked from sphere burst.. at 2008/02/12 16:29

제목 : 자료구조 Stack 만들기 문제
ref. 자료구조 Stack 만들기 문제 ; object님 간단히 Stack을 구현하세요~ 하면야 모르겠지만... object님의 원 포스팅에도 있는 조건들을 다 빼고서라도... (15분으론 구상조차 무리에요 ㅠㅠ) thread-safe 조건과 lock-free 조건이 결합하면 이게... (먼산) ...정말 Queue는 어찌 방법은 있을지도 몰라. 정도의 구상은 되는데, Stack은 정말 답이 없는 느낌. ㅠㅠ 요즘 자료구조......more

Tracked from 클랴의 베이킹파우더 at 2008/02/12 19:21

제목 : atomic stack 문제...
자료구조 Stack 만들기 문제-object님 포스팅자료구조 Stack 만들기 문제-sikuru님 포스팅컴퓨터 프로그래밍 전공이 아니신 분은 back을 눌러주세요... ㅈㅅㅈㅅ질문은 atomic inc/dec/exhange 만 가지고 thread-safe 인 stack을 만들어라..인데요.queue에서는 read 부분과 write 부분이 다르니까 쉽습니다만, stack에서는 같은 메모리에 대해 접근을 하는 경우가 생기기 땜시 고민이 됩니다.........more

Tracked from 천 리 길도 한 걸음부터 at 2008/07/04 11:23

제목 : ABA problem
며칠전부터 메모리 풀을 하나 만들고 있다. 목표는 가볍고 사용하기 쉬우면서 현재 참여하고 있는 프로젝트에 쉽게 적용을 할 수 있도록 하는 것이다. 메모리 풀은 그 특성상 다수의 쓰레드에서 접근이 가능해야해서 쓰레드 안정성이 확보되어야 한다.쓰레드 안정성을 확보하는 가장 쉬운 방법은 동기화 객체를 사용하는 방법이다. 윈도우 환경하에서 가장 쉽게 쓸수 있는 객체는 CRITICAL_SECTION이고 이걸 사용하면 만드는건 껌이다. 그러나 critic......more

Linked at sungdh86님의 글 - [.. at 2008/02/14 22:41

... 는 친구들은 ← 2008년 2월 1 2 3 4 5 7 9 10 11 12 13 14 14 Feb 2008 0 metoo 학부 3학년까지 마친 컴퓨터공학과 학생이 자료구조 Stack 만들기 문제에서 Thread-safe하게 Queue를 만드는 것은 금방 알겠는데 Thread-safe하게 Stack만들기는 머리에 이해가지가 않는다. 나는 뭘 공부했는지가 궁 ... more

Linked at 미친병아리가 삐약삐약 : 20.. at 2008/02/18 12:06

... 포기하긴 어려울 것 같다.. 누가 선물로 준다면 모를까 내 돈 내고 사기엔 돈 아까울 것 같다.. '루미나리에'가 '루체비스타'로 불러진 까닭은? 이런 사연이 있었군.. 자료구조 Stack 만들기 문제 언제나 이론이 간단하다고 현실에서 부딛힐 여러가지 제약조건과 장애를 쉽게 극복할 수 있을 것이라 생각해서는 안된다.. 구글의 페이지랭크 알고리즘이 매우 어렵지는 않 ... more

Commented by rein at 2008/02/12 15:09

InterlockedCompareExchangePointer 를 쓰고 스택에 포인터 타입만 넣는다면 어찌 가능할 것도 같습니다.

Commented by rein at 2008/02/12 15:24

Pointer를 atomic swap해서 링크드 리스트를 구현하면 편법일지도 모르겠지만(...)

Commented by lifthrasir at 2008/02/12 15:25

저도 spinlock을 생각했는데 그러면 너무 문제가 쉬워지는 것 같긴 하더군요. 그런데 커널로의 스위칭을 최소화하는 게 관건이라면 그런 류의 busy-waiting lock을 써도 현실적으로는 큰 문제는 없지 않을까요? (더 이상 생각할 시간이 없어서 일단 -_-;)

Commented by lifthrasir at 2008/02/12 15:26

(그나저나 이글루스는 손님 이름에 글자수 제한을 걸어 놓아서 어쩌라는 건지...)

Commented by Sikuru at 2008/02/12 15:28

빈번히 불리는 자원에 크리티컬 섹션이 끼어들어가 시작하면 정말 답없는 성능저하가 나오더군요. orz
멀티스레드의 세계는 압박이어요오 ㅠㅠ

Commented by object at 2008/02/12 15:33

네, spinlock을 쓰면 너무 간단해지요 ㅎㅎ 현실적으로 spinlock을 쓰는 것이 간단합니다. Win32 API 같은 경우는 InitializeCriticalSectionAndSpinCount를 쓰면 제일 간단합니다. Sikuru님 이 함수를 써보세요. 성능 향상이 확실히 있습니다.

일단, 저는 큐에서 하는 것 처럼 read cursor, write cursor를 두어서 하려고 했습니다. 이 접근은 맞는 것 같더라구요. 면접보던 아저씨가 고개를 크게 끄덕이었다는;; 문제는 Queue는 이 정도에서 끝나는데 Stack은 이 두 커서를 잘 씽크 시켜야한다는 것이 문제...

실제로 CPU 아키텍처에서도 보면 큐는 굉장히 많이 나옵니다 (예를 들어, 파이프라인과 파이프라인 사이에 큐가 많이 존재하죠). 하드웨어는 모두 concurrent하게 돌아가기 때문에 직관적으로라도 큐는 락 없이 구현이 가능합니다. 그런데 하드웨어에서도 Stack은 read/write cursor 동기화가 어려워서 안 쓰는 걸로 알고 있는데 @.@ (물론 Queue도 empty/full 체크와 같은 corner case가 있습니다.)

Commented by Sikuru at 2008/02/12 15:38

그 것을 써도 접근도가 과도해지면, 접근법이 틀렸구나. 라는 느낌이 들더라구요^^;;;
(C#쪽에서는 크리티컬 세션에 스핀락이 되던가요. 아직 이쪽은 짧... ㅠㅠ)

Queue는 정답은 아닐지 몰라도 뭔가 좀 빛이 보이는데, Stack은 그냥 암흑뿐이군요. orz

Commented by 자연풍선생 at 2008/02/12 15:55

락이 있으면 성능차가 약 1000배 가까이 난다고 하는데 락안쓰고 멀티스레드 관리가 가능한가요;;;

Commented by Eminency at 2008/02/12 15:56

atomic operation이란게 어떤 걸 얘기하는거죠? 윈도 프로그래밍 해본 적이 없어서 그런건지 부연설명도 무슨 말인지 잘...-_-;

Commented by object at 2008/02/12 16:03

1. 1천배라는 수치도 터무니 없어보이지는 않습니다. 충분히 가능한 수치 같구요. 락 안쓰고 멀티스레드 관리를 하는 것이 많은 컴퓨터 과학자들의 목표죠 ㅎㅎ 대표적으로 TM (transactional memory)가 그걸 위한 것입니다.

2. Atomic 연산은 말 그대로 한 방, 더 나뉘어질 수 없는 연산을 가리킵니다. 예를 들어, i++ 이라는 구문은 아시다시피 3부분으로 나뉘죠. 메모리 읽고, 더하고, 다시 쓰고. 그런데 이 3 명령어가 항상 동시에 수행되라는 법이 없죠. 그 사이에 context switching이 일어나면 값이 잘못 되겠죠. (실제로 듀얼 코어에서 i++을 두 스레드에서 동시에 돌려보면 값 누락이 제법 생깁니다. 백만번 중에 10번 정도로) 그래서 atomic 연산은 i++ 과 같은 연산을 "한방에" 처리해주는 겁니다. 이건 CPU가 제공하는 instruction을 바로 써야 합니다. Win32 API는 그걸 저렇게 API 형태로 만들어놓았고 리눅스에는 직접 해당 asm 코드를 짜거나 아니면 CPU intrinsic을 쓰면 됩니다 (헤더 파일은 까먹었네요).

Commented by 클랴 at 2008/02/12 19:22

안녕하세요... 링크만 해놓고 자주는 못오다가, sikuru님 통해서 오랫만에 들렸습니다. (꾸벅)
구글링 해보니 atomic exchange로 해결한 방법이 있더군요. 링크는 제 포스팅에..

Commented by object at 2008/02/13 02:39

오 감사합니다. 구글링으로 찾으셨군요. 조만간 살펴보도록 하겠습니다.

Commented by abraxsus at 2008/02/13 13:18

흐음..잼있는 문제이긴한데, 제 생각으로는 문제의 본질상 어떤 형태로든지의 약간의 spinning은 피할수
없는것같습니다. -_-;;
클랴님이 구글링으로 찾으신 것도 누군가 풀어보려는것으로 보이는데, 사실상의 spinlock이 들어있는것이라고
생각되고요.. 근데 문제출제자는 뭐 이정도수준의 해법을 원하는것으로 생각됩니다.
여기서 한발 더 나아가서 spinning을 없애면 그게 RCU가 되는거구요..흠...

Commented by ipkn at 2008/02/13 15:04

win32 api의 InterlockedPushEntrySList 이런 함수들은 고려에서 제외되나요?

Commented by 조성경 at 2008/07/04 11:27

트랙백 걸었습니다. 실제로 스택 자체를 구현하는건 그다지 어려운 일이 아니더군요. ABA problem으로 진짜 쌍코피 터졌습니다.

Commented by object at 2008/07/04 18:01

감사합니다. 예전에 쓴 글이라 업데이트를 안했네요.