gimmesilver's blog

Agbird.egloos.com

포토로그



하스켈을 이용한 병렬 프로그래밍...1 하스켈 스프링노트

Software Transactional Memory(STM) - '만약 다른 놈이 방해했으면 난 다시 시도한다.'

 예, 병렬 프로그래밍(혹은 멀티 쓰레딩 프로그래밍이나 동시성 프로그래밍이라고도 불리는) 은 어렵습니다. - 여러 가지 이유가 있겠지만 - 일반적으로 1) 특정 상황에 대한 재현이 힘들고 2) 프로그램의 흐름을 예측하기가 거의 불가능하기 때문입니다. 더 불행한 사실은 많은 프로그래밍 언어들이 기본적으로 병렬 처리를 위한 플랫폼 독립적이면서 안전한 기법을 제공하지 못한다는 것입니다. 때문에 아마도 가장 좋은 방법은 최대한 병렬 프로그래밍을 피하는 것일 겁니다.

 하지만 - 개발자들에게는 불행하게도 - 병렬 프로그래밍은 점점 중요해지고 있습니다. 다시말하면 우리가 앞으로 비싼 밥 먹고 살아가려면 병렬 프로그래밍을 능숙하게 할 줄 알아야 한다는 뜻입니다. 심지어 몇 년전 - 아직도 이 자리에 있는지는 모르겠지만 - C++ 표준 위원장이자 MS VC++개발팀 책임자였던 허브 슈터는 CUJ의 한 컬럼에서 '90년대가 객체 지향 프로그래밍의 시대였다면 2000년대는 병렬 프로그래밍의 시대가 될 것이다.'라고 주장하기도 했습니다.(그런데 재밌게도 이 컬럼의 주제는 '제대로 된 병렬 프로그래밍은 정말 어렵다!' 입니다.) 

 그리고 실제로 멀티 코어 혹은 멀티 프로세서 시스템이 많이 사용되면서 이를 효과적으로 활용하기 위한 병렬/분산 처리 기법이나 Erlang과 같이 병렬 처리를 효과적으로 수행할 수 있는 프로그래밍 언어가 점차 주목을 받고 있습니다.

 병렬 프로그래밍에서 맞닥뜨리게 되는 가장 큰 문제는 공유 자원을 여러 쓰레드에서 동시에 접근하면서 생기는 경쟁 상태입니다. 그리고 이런 경쟁 상태를 제어하기 위해 가장 많이 사용하는 방법이 뮤텍스나 세마포어와 같은 락을 이용한 동기화 방법입니다. 락을 이용한 동기화는 그 원리가 비교적 단순하기 때문에 많은(거의 대부분의) 언어에서 표준 라이브러리나 혹은 언어 차원에서 지원하고 있습니다.

 하지만 락을 이용한 동기화 방법은 주의 깊게 사용하지 않으면 데드락과 같은 문제가 쉽게 발생하기 때문에 결코 좋은 방법이라 할 수 없습니다. 말그대로 '울며 겨자먹기'식으로 사용할 뿐이죠...

 이런 단점에 대한 대안으로 제시되는 방법 중 Software Transactional Memory(이하 STM)가 있습니다. STM은 이름에서 미루어 짐작할 수 있듯이 DB의 트랜잭션 기법과 유사한 방식입니다. DB의 트랜잭션은 원자적으로 데이터를 처리하는 기능 단위를 말합니다. 

 '원자적(atomic)'이라는 말은 이름 그대로 더 이상 쪼갤 수 없는 기본 단위를 말합니다. 이 말은 문맥에 따라 약간씩 다른 의미를 가지는데 병렬 프로그래밍에서 '원자적' 이라고 하면 이것은 실행 도중 다른 쓰레드에 의해 방해 받지 않는 기능 단위를 말합니다. 예를 들어 동기화 기법 중 하나인 크리티컬 섹션은 락을 이용해 인위적으로 어떤 작업을 '원자적'으로 수행하는 방법입니다. 크리티컬 섹션 내에 위치한 코드들은 - 제대로 구현하였다면 - 언제나 한번에 하나의 쓰레드만이 접근 가능합니다.

 한편 DB에서 말하는 '원자적'이란 중간 상태를 갖지 않는 기능 단위를 말합니다. 가령 은행에서 A에서 B로 계좌 이체를 한다고 할 때, 이 작업은 실제로 1) A계좌에서 예금 인출, 2) B계좌로 인출액 입금 이라고 하는 두 작업으로 나뉘게 됩니다. 하지만 DB에서는 이 두 작업을 하나의 트랜잭션으로 처리하기 때문에 어떤 경우에도 (심지어 정전이나 시스템 오류와 같은 최악의 상황에도) 중간 상태 즉, A에서는 예금이 인출되었지만 B계좌에는 입금이 안된 상태를 갖지 않습니다. 단지 전체 이체 작업의 성공과 실패만이 존재할 뿐입니다. 그리고 실패 시에는 항상 해당 트랜잭션 작업이 수행되기 직전의 상태로 복구됩니다. 이것을 보통 'All or nothing'이라고 합니다.

 STM은 이런 DB트랜잭션의 특징을 병렬 프로그래밍에 적용한 기법입니다. 다만 차이가 있다면 DB 트랜잭션은 쿼리 작업의 실패와 같은 비정상 경우에 전체 작업이 복구되지만 STM에서는 작업 수행 도중 다른 쓰레드에서 동일한 트랜잭션에 접근할 경우 전체 작업이 복구됩니다. 다시 말하면 A라는 작업을 하나의 쓰레드가 수행할 때 A 작업이 마치는 시점에서 다른 쓰레드가 이 A 작업에 동시에 접근했는지를 확인하고 만약 다른 쓰레드들이 접근하지 않았으면 수행한 작업을 실제로 반영을 하고, 만약 그렇지 않으면 A작업 전체를 다시 원상 복구하고 다시 시도하는 것입니다. 이것을 의사코드(psuedo code)로 표현하면 아래와 같습니다.

begin
  STM_task:
    write_access_log(cur_log)    // 스레드가 이 코드에 접근할 때마다 접근 기록을 남김
    do something                     // 작업 수행
    new_log = check_access_log() // 작업 완료 직전에 접근 기록을 다시 확인,
    if (cur_log != new_log)             // 만약 접근 기록이 달라졌으면
        roll_back                            // 수행한 작업을 원상 복구하고
        goto STM_task                    // 다시 처음부터 작업 수행
    commit        // 다른 스레드가 접근하지 않았으면 수행 작업 적용
end

 위 코드가 잘 이해가 가지 않는다면 단지 이 한 문장만 기억하십시오. '만약 다른 놈이 방해했으면 다시 시도한다!'

 혹시 눈치 채셨을지 모르지만 STM과 락 기반 동기화는 기본적으로 접근 방식이 크게 다릅니다. 락 기반 동기화는 언제 다른 놈이 접근할지 모르기 때문에 항상 사전에 접근을 차단한다는 생각에 기초한 구현 방식입니다. 반면, STM은 대개의 경우 다른 놈이 접근하지 않으므로 일단 그냥 수행해보고 만약 다른 놈이 방해하면 - 공유 자원이 훼손됐을 수 있으므로 - 지금까지 했던 것 다시 원상 복구 시켜놓고 다시 시도한다는 주의입니다. 따라서 전자를 '비관적 동기화' 후자를 '낙관적 동기화'라고 합니다.

 어쨌든 이런 STM의 특징은 데드락을 발생시키지 않습니다. 동기화 프로그래밍 시 가장 큰 문제가 되는 것이 데드락이라는 것을 생각해볼 때 이것은 매우 큰 장점이 됩니다. 게다가 STM 처리가 된 기능 모듈들은 락의 획득과 해제에 대한 문제를 신경쓰지 않아도 되기 때문에 모듈들의 융합이 - 락 기반 동기화에 비해 - 쉽습니다. 
 심지어 STM은 뛰어난 예외 안정성을 가지고 있습니다. 락 기반 동기화 모듈에서 예외 안정성을 획득하기란 대단히 까다로운 작업입니다. 하지만 STM에서는 작업이 성공하지 못하면 작업 수행 이전 상태로 복구되기 때문에 별다른 처리없이 예외 안정성을 유지할 수 있습니다.

 제목에서 짐작하셨듯이 하스켈에서는 STM을 지원합니다. ghc라는 - 실질적으로 표준인 - 하스켈 컴파일러에는 Control.Concurrent.STM 이라는 라이브러리 모듈이 있는데 이것이 바로 STM을 사용할 수 있는 라이브러리입니다. 이 모듈은 - 대부분의 유용한 하스켈 라이브러리들이 그렇듯이 - 모나드 기반으로 동작합니다.

 그럼 하스켈에서 STM을 어떻게 지원하고 그 특성이 어떠한 지는 다음 글에서 이어가도록 하겠습니다.

덧글

  • corba 2007/08/02 10:01 # 삭제 답글

    굉장히 기대되는 포스팅입니다~~~
  • silverbird 2007/08/09 00:19 # 답글

    // corba
    기대가 크면 실망이 큰 법인데... ^^;
댓글 입력 영역