'컴퓨터과학'에 해당되는 글 7건

  1. 2010.12.18 동기화 기법: Read-Copy-Update (2)
  2. 2010.12.05 프로그래밍 언어 만들기 上
  3. 2010.12.03 무한대의 처리율과 용량을 가진 컴퓨터가 나온다면?
  4. 2010.04.28 멀티 쓰레드 프로그래밍이 어려운 까닭
  5. 2009.11.01 Local search
  6. 2009.10.22 Informed search
  7. 2009.10.21 Uninformed search

동기화 기법: Read-Copy-Update

컴퓨터 과학 2010.12.18 02:55

2.6 시대에 리눅스 커널을 뜯어본 사람이라면 RCU라는 것을 알지도 모르겠다. RCU란 리눅스 커널 내에서 주로 읽기 연산만 일어나고 쓰기 연산의 비중은 매우 작은 객체에 주로 쓰이는 동기화 기법이다. Reader-Writer lock과 비슷한 동기화 기법인데, RW lock에 대해 RCU가 가지는 상대적 강점으로는 읽기 연산이 Wait-free이며 (다시 말해 블럭이 일어나지 않으며) 그 오버헤드가 극도로 작다는 점 등이 있다. (리눅스에서는 kernel preemption을 끄고 컴파일하면 RCU로 보호되는 메모리를 읽을 때 동기화 오버헤드가 제로다!) 그 대신 쓰기 연산의 오버헤드가 꽤 큰데다 무슨 일을 하건 쓰기에 필요한 동기화의 시간 복잡도가 최소한 RCU로 보호되는 객체의 크기에 비례한다.


RCU의 아이디어는 꽤 심플하다. 그 기저에 깔린 전제들만 알면 쉽게 이해할 수 있는데, 내 생각엔 그 목록은 대충 아래와 같다.

  • 불변 Immutable 객체는 쓰레드 안전하다. 좀 더 구체적으로, 어떤 코드 영역을 수행하는 동안 공유되는 메모리 구간이 불변이라면 해당 코드로 인한 상태의 변화는 항상 예측가능하다. 다시 말해 코드 수행의 결과가 결정적 Deterministic 이다.
  • 메모리 배리어 등을 통해 가시성이 확보한 경우 단일 워드에 대한 쓰기 연산은 대개 원자적이다. 적어도 다른 쓰레드 입장에선 그렇게 보인다.
  • 어떤 객체의 상태를 변경하는 코드를 수행할 때, 그 변경이 다른 쓰레드의 입장에서 한 순간에 원자적으로 이루어지는 것처럼 보인다면 연관된 코드들의 수행 내역은 단일 쓰레드로도 재현 가능하다. 쓰레드 간 코드 수행 순서에 대한 구체적인 합의가 필요한 경우는 드믈기 때문에 대부분은 이 정도만 보장되어도 동기화로써 충분한 역할을 할 수 있다.

이러한 전제들을 사용하면 흥미로운 결과를 도출해 낼 수 있다. 우선 가비지 컬렉션을 지원하는 요즘 언어들에서는 객체를 직접 변경하는 대신 불변 객체를 새로 만들어서 쓰는 것은 드믈지 않은 일이다. 이를테면 문자열 객체를 불변으로 다루는 Java 같은 언어에서는 문자열을 변경하려 하는 경우 전역적으로 관리되는 문자열 객체 풀에서 변경된 결과의 불변 문자열을 가져와서/새로 만들어서 사용한다. (이를 보통 String Internalization이라 한다.) 굳이 객체 풀을 만들 필요까지도 없고 이미 노출된 객체를 변경하는 대신 새로운 불변 객체를 만드는 방법을 이용하면 쓰레드 안전성을 쉽게 확보할 수 있다.

그렇다면 이를 안전하게 노출시키기만 하면 된다. 세 번째 전제에 따르면 객체의 갱신 과정이 원자적으로 보이기만 하면 실용적인 동기화 방식으로 활용할 수 있는데, 두 번째 전제에 따라 레퍼런스 역할을 하는 포인터의 값으로 새로운 객체의 주소를 집어 넣기만 하면 된다. 다만 그냥 대입하면 새로운 객체가 완성되기 전에 CPU나 컴파일러의 비순차 실행 최적화에 의해 포인터의 대입 연산이 먼저 수행될 수 있다. 이 경우 객체의 변경이 완료되기 전에쓰레드 외부로노출될 우려가 있으므로 메모리 배리어로 포인터의 대입이 객체의 생성 이후에 이루어지도록 보장할 필요가 있다.


여기까지 설명한 것만으로도 이미 RCU의 기본적인 동작 방식을 절반 이상 설명했다. RCU로 보호되는 객체에 대한 읽기를 하려는 경우 평소처럼 포인터를 가져와서 읽기 전용으로 해당 객체를 다루면 된다. RCU로 보호되는 객체를 변경하려는 경우 객체를 직접 변경하는 대신 새로 할당한 메모리 영역에 객체를 복사한 뒤 새로 만든 객체를 변경한다. 기존의 객체는 불변이므로 이 과정은 안전하다. 변경이 완료되면 RCU로 보호되는 포인터에 새로운 객체의 포인터를 대입한다. 이러면 대입 이전에 이 객체를 읽어서 사용하던 쓰레드는 이전의 객체를 계속 사용하게 될 것이고, 대입 이후에 사용하는 쓰레드는 새로운 버젼의 객체를 읽어 사용하게 될 것이다. 각각의 쓰레드에서 여러 버젼의 객체가 동시에 사용된다는 점에서 데이터베이스에서 사용되는 동시성 관리 기법인 MVCC[각주:1]와도 비슷하다. 아래는 RCU를 사용하는 방식을 보여주는 가짜 코드이다.

SomeObject object;

 // RCU로 보호되는 객체
RCU<SomeObject> rcu(object);

...

// reader thread
rcu.beginRead();

// Wait-free로 구현됨.
SomeObject* ptr = rcu.getPointer();
ReadOnlyOperation(ptr);
rcu.endRead();

...

// writer thread
rcu.beginWrite();

// 일반적인 락과 유사. 어차피 객체의 갱신은 직렬적으로 처리되어야 한다.
SomeObject* ptr = rcu.copyObject();

// 객체를 복사함.
WriteOperation(ptr);
rcu.endWrite();
rcu.setPointer(ptr);

이 쯤에서 자원 관리가 어떻게 될까 의문을 가질 것이다. 사실 RCU 구현의 핵심도 바로 이 부분이다. 자원 관리에 신경을 쓰지 않아도 되는 언어라면 굳이 이런 개념을 도입할 필요도 없었을 것이다. 하지만 수동으로 자원을 관리해줘야 하는 언어를 사용하는 경우라면 RCU 차원에서 더 이상 사용되지 않는 객체를 적절하게 해제할 수 있도록 도와줘야 할 필요가 있다. reader 입장에서 더 이상 접근할 방도가 없는 객체인 경우만 해제해주면 되므로 위의 가짜 코드에서 setPointer를 한 이후 예전 객체를 읽는 reader들의 코드 수행이 전부 종료되는 시점에 해제를 해주면 된다. 물론 이를 구현하는 방법은 여러 가지가 있겠지만, 가장 직관적인 방법으로는 레퍼런스 카운팅이 떠오른다.


이 정도면 누구라도 쉽고 재미있게 구현할 수 있을 것 같다. ... 정말 그럴까?

아쉽게도 그렇지 않다. -_- 만약 레퍼런스 카운팅을 한다 치면 읽기 영역에 진입/이탈 시 원자적인 정수 연산이 적어도 한 번씩은 일어날 것이다. 그런데 일반적인 RW lock도 경쟁이 없다는 전제 하에선 읽기에 대해 원자적인 연산 두어개의 오버 헤드만을 가지도록 구현하는 것이 가능... 아마 가능할 것이다 -_-; 즉 RW lock과 차별화되는 강점 하나가 사라진다. 물론 읽기가 Non-blocking이라는 매력적인 조건이 있지만 이 것만 가지고 쓰기 시의 추가적인 오버헤드를 용납하기는 어렵다. RCU 자체가 읽기에 수반되는 동기화의 Critical path를 최소화하려는 시도이므로 읽기의 오버헤드는 최소화되어야 한다.

리눅스 커널에서는 이걸 아주 간단하게 해결하고 있다. RCU는 커널 코드 내에서만 쓰이며, 커널 모드에서의 수행이 끝나면 RCU의 읽기 구간 수행 역시 끝날 것이다. 따라서 위 가짜 코드의 setPointer를 수행하는 시점에 돌아가고 있는 모든 CPU들에 대해 해당 CPU로의 문맥 전환을 한번씩 요청한다. 커널 모드에서 문맥 전환이 일어나지 않는 비선점형 커널을 사용하고 있는 경우 이 과정이 끝나면 해당 시점에 커널 모드에서 돌아가던 모든 동작들이 종료된 것이므로 (= 기존 객체에 대한 읽기가 끝난 것이므로) 메모리를 안전하게 해제할 수 있다. 선점형 커널인 경우는 읽기 구간에 들어간 동안에만 커널 선점을 꺼버리는 방법을 사용하고 있다고 한다. (요즘의 구현은 다를지도 모르겠다. 논문들을 보면 Hazard pointer 등을 이용한 구현도 있는 모양이다.)

헌데 유저 모드에서 적은 오버헤드로 RCU를 구현하려고 생각해보면 암담하다. -_-; OS의 지원을 받지 못하니 선점 모드를 끄는 등의 작업은 명백하게 월권이다. 특정 쓰레드가 읽기 구간에 있다는 것을 알리는 변수를 세팅한다고 해도 해제하는 쓰레드가 이에 대한 가시성을 얻고 코드 수행의 순서 일관성을 보장하기 위해서는 메모리 배리어가 필요하다. 허나 메모리 배리어의 사용 역시 만만치 않은 오버헤드를 가지고 있기 때문에 이를 사용하려 들면 문제는 원점으로 돌아가 버린다. 결론은 답이 없다 되겠다. -_-;


그런데 사실 오버헤드가 좀 있다손 치더라도 읽기의 동기화 과정이 Wait-free라는 것만으로도 RCU는 상당히 매력적인 모델이다. 이 말은 곧 읽기에 대해서는 최대한의 병행적인 확장성을 제공한다는 이야기이기 때문이다. 또한 읽기를 위한 동기화는 넌블럭이고 쓰기 역시 하나의 락만 사용하므로 데드락의 가능성이 거의 없다는 것 역시 강점이다. 또한 쓰기에 걸리는 락 역시 쓰기 동기화를 위해서는 당연히 필요한 오버헤드이기 때문에 결국 RCU로 인해 생기는 오버헤드는 객체 복사 및 추가적인 할당/해제 정도가 전부이다.

개인적으로는 이렇게 시점 별로 여러 버젼의 불변객체를 유지하는 MVCC 류의 동시성 제어 기법은 가비지 컬렉터가 지원되는 언어에서 더욱 빛을 발할 것이라 생각한다. 자원 해제 관련된 부분이 완전히 투명해지므로 (심지어는 성능적인 부분에 있어서도) 사용하기가 훨씬 간편해지며, 메모리 압축을 지원하는 언어에서는 할당 오버 헤드 역시 매우 작으니 큰 문제가 되지 않는다. 복사로 인한 오버헤드는 읽기에서 락을 사용하지 않음으로 얻는 퍼포먼스 이득 및 데드락으로부터의 해방을 생각해보면 충분히 감수할만한 가치가 있다.

물론 이 방식이 은탄환인 건 절대 아니다. 일단 원하는 데이터가 연속된 메모리 공간에 위치하지 않은 경우에는 이 기법을 적용할 수 없다. 즉, 이 기법만을 사용해서는 임의의 메모리 공간들에 대해 원자적인 갱신을 할 수 없다.졸면서 쓴 부분을 수정한다. -_-; 정확히는 다루는 객체가 의미적으로 불변인 객체여야 한다는 제약이다. 이러면 포인터를 바꿔칠 수 없으므로 RCU로 동기화되는 객체들을 조합해서 마찬가지로 RCU로 동기화되는 더 큰 객체를 만드는 등의 작업은 불가능하고, 그냥 불변 객체를 생으로 만들고 복사하는 방식으로 써야 한다. 다르게 말하자면 객체 간의 합성이 까다로운 동기화 기법인 셈이다. 방법이 있는데 내가 모르는 것일지도 모르겠지만... 하지만 이 방법은 높은 병행성을 가지는 자료구조나 알고리즘을 구현하기 위한 빌딩 블럭으로써 꽤 괜찮은 기법이다. 실제로 리눅스에서는 RCU를 이용해서 리스트를 관리하기도 한다. 개인적으로는 RCU를 잘 정제해서 동시성을 제어하는 기본 요소로 언어에 도입해보는 것도 좋은 시도가 아닐까 생각한다. (이미 있을지도 모르겠다)
  1. Multi version concurrency control [본문으로]
Trackback 0 : Comments 2

프로그래밍 언어 만들기 上

컴퓨터 과학 2010.12.05 14:11
소프트웨어 엔지니어들에게 있어서 로망이 있다고 하면 OS, DB, 컴파일러, 프로그래밍 언어 같이 컴퓨터 과학의 정수를 담은 물건을 직접 만들어 보는 게 하나다. 특히나 프로그래머들이 직접 사용하는 도구인 프로그래밍 언어가 그런 경향이 좀 있다. 좀 쓰다보면 다른 언어와 비교되는 아쉬운 점이 계속 보이는데, 진행 중인 프로젝트에서 사용하는 언어를 갈아 타는 일은 대개 불가능해서 입맛만 다신다.

나는 C++을 주로 사용하는데, 이 언어는 여러 가지 문제점을 가지고 있는 언어다. 그런데 표준화 위원회에 의해 개발되기 때문에 발전 속도도 무척 느리다. [각주:1] 다른 언어들에서는 언어 차원에서 기본적으로 지원되는 기능이 C++에서는 차기 표준은 커녕 검토 목록에도 아직 올라오지 않은 것을 보면 배가 아프다. 이런 문제에 대한 가장 근본적인 해법은 그냥 새로 언어를 만드는 것이다. 그런데 그게 쉬운 일은 아니니 공상부터 하게 된다.

서두가 쓸데 없이 길었다. 제목에 낚시성이 농후한데, 조금 더 정확한 제목은 "프로그래밍 언어 상상해보기" 정도일 것이다. 쓰는 언어의 근본이 C++이라 학계의 최신의 연구 결과를 반영하는 것까진 감히 상상하지 못하고, 그저 C++을 내 취향대로 다시 reengineer한다면 이런 모양이 아닐까 이런 느낌이다.


1. 기본적인 문법

언어의 기본적인 성격과 문법들, 이를테면 절차 지향 언어라는 점 혹은 사용하는 표현식 문법이나 변수 선언, 블록, 상수성 등에 있어서는 C 계열의 언어로 분류될 수 있을 것이다. C/C++이 복잡한 문법을 가지는 언어로 지탄받지만, 이런 부분은 의외로 직관적이고 괜찮은 편이다. 다만 함수 문법은 약간 수정되어야 할 필요가 있다고 생각한다. 이를테면 아래와 같은 코드가 있다고 하면

someclass someobject(someargument);

현재의 C++과 같은 문법으로는 이게 someclass 타입의 실체화인지 아니면 someclass라는 타입을 반환하는 함수의 선언인지 문맥을 파악하기 전까지는 알 수 없다. 다른 사례를 들자면

// ScopedLock은 operator bool 함수를 오버 로딩하고 있으므로
// 필요한 경우 암묵적으로 false로 캐스팅이 된다.

// 컴파일 에러
#define synchronized(lock) \
    if (ScopedLock<decltype(lock)> __scope(lock)) {} else
// 컴파일 됨
#define synchronized(lock) \
    if (ScopedLock<decltype(lock)> __scope = lock) {} else

이건 자바의 synchronized 키워드를 에뮬레이션하기 위해 만들어 본 매크로인데, 안타깝게도 전자는 함수 선언을 if 문에 넣은 것으로 간주하여 컴파일이 되지 않는다. 왜 이렇게 되는지가 쉽게 이해가질 않는데, 어쨌든 직관성이라는 부분에 있어서 이 부분은 빵점이다. 애초에 전역 함수가 없거나 선언과 정의라는 개념을 분리하지 않는다면 간단하게 해결될 문제긴 하지만.


2. 정적 강타입 언어

나는 코딩할 때 실수가 잦은 편이라 정적 강타입 언어를 선호한다. IDE의 도움을 받지 않으면 코드를 살짝만 수정해도 에러가 5~6개씩 뜨는건 기본이다. 그런데 만약 여기에서 타입 안전성 체크가 없었다면 어떤 재앙이 일어났을지 생각해보면 좀 무섭다. 사실 이게 lua를 쓸 때 가장 난감했던 점이기도 하다. 변수나 멤버 이름 하나를 오타 내도 런타임에 nil을 꺼내 쓸 뿐 컴파일 시점에서 아무런 경고가 뜨지 않는다. 이런 걸 디버깅하는 것은 무척 괴로운 일이다. 변수를 명시적으로 선언해서 쓰는 언어에서는 이런 문제가 덜하지만, 타입 정보가 없음으로 인해 프로그래머가 가정할 수 있는 내용이 적다는 것은 여전히 약점이다.

정적 타입 언어의 강점은 또 하나 있다. 타입 정보가 컴파일 시점에 완전히 알려지기 때문에 최종적으로 수행되는 코드의 효율성은 동적 타입 언어의 그 것과 비교가 되질 않는다는 것이다. 아래와 같은 코드가 있다고 치자.

var a = 10, b = 2.0f, c = "haha";
var d = a+b+c;

동적 타입 언어에서는 우선 a, b의 타입을 체크해서 어떻게 타입 캐스팅을 하고 덧셈 연산을 수행할 지 판단한 뒤에야 실제 덧셈 연산이 수행될 수 있다. 위 같은 코드는 그나마 컴파일 시점에 최적화를 해볼 여지가 있지만, 함수 인자 등으로 넘어오는 경우는 얄짤 없다. 하지만 정적 타입 언어는 모든 타입 정보를 컴파일 시점에 가지고 있기 때문에 타입 캐스팅과 수행할 덧셈 연산이 컴파일 시점에 전부 결정된다. 분기문이 완전히 사라지므로 CPU 파이프라인을 훨씬 효율적으로 사용할 수 있다. 당연히 수행 효율은 동적 타입 언어가 범접할 수 없는 수준이다. 물론 요즘 컴파일러/가상머신 기술들이 좋아져서 그 격차가 많이 줄어들긴 했지만, 이건 내가 직접 만든다는 가정하에 공상을 하는 것이므로 내가 구현할 수 없는 내용엔 큰 의미를 두지 않겠다. (...)

물론 강타입 언어의 사용성은 동적 타입 언어에 비해 현저히 떨어진다. C++의 iterator 삽질만 해도 그렇다. 좀 오버스러운 사례지만, std::vector<std::list<std::pair<someclass::key, someclass::value> >::iterator >::iterator 이런 것을 일일히 쳐주다 보면 내가 무슨 일을 하는건지 알 수 없는 경지에 도달하게 된다. 하지만 기본적인 수준의 타입 유추 기능이라도 도입하면 이런 문제는 많이 완화시킬 수 있다. 사실 템플릿을 지원 안 하는 것도 좋은 방법이다. 취미 수준으로 만들기에 C++ 같은 템플릿은 너무 방대하고 복잡하다.


3. 구조적 타이핑 Structural typing

객체 지향 프로그래밍을 한다고 할 때 보통 각각의 객체에는 부여된 책임이 있을 것이고, 이를 수행하기 위해 필요한 연산의 집합이 있을 것이다. 전통적인 OOP 언어에서는 해당되는 연산의 집합을 정의하는 상위 클래스를 만든 뒤 이를 상속받아서 다형성을 이용한다.
class Duck {
public:
    virtual void walk() = 0;
    virtual void swim() = 0;
    virtual void quack() = 0;
};
// 새끼 오리
class BabyDuck : public Duck {
    ...
};
// 나는 오리
class FlyingDuck : public Duck {
    ...
};
Duck* duck = new FlyingDuck;

반면 덕 타이핑을 지원하는 언어에서 조금 다른 방식의 다형성이 지원된다. 이는 "오리처럼 걷고, 오리처럼 수영하고, 오리처럼 꽥꽥거리는 새를 본다면 이를 오리라고 한다."라는 설명에서 유래한 용어다. 동일한 메타포를 이용하여 상속 기반 다형성을 표현하자면 "오리란 오리처럼 걷고 오리처럼 수영하고 오리처럼 꽥꽥거리는 새이다" 정도가 될 수 있다.

이 개념을 지원하는 언어에서는 상속과 같이 코드에 선언된 타입 정보와는 무관하게 런타임에 객체가 지원하는 연산 집합을 판단, 사용하려는 문맥에 의미적으로 호환되는지를 확인한다. 따라서 타입 호환 여부를 런타임 환경에서 직접 검증해야 하는 대부분의 동적 타입 언어에서는 덕타이핑을 어렵지 않게 지원할 수 있다. 하지만 정적 타입 언어에서는 이야기가 다르다. 컴파일되고 나면 대부분 심볼 및 타입 정보가 날아가 버리며, 설령 타입 관련 메타 데이터들이 남아 있다고 해도 이를 실시간으로 찾아서 디스패칭해주는 오버헤드를 감수하는 것은 있을 수 없는 일이다. 게다가 타입 안전성을 런타임에 체크하려면 굳이 정적 타입 언어를 쓸 이유가 없다.

구조적 타이핑은 그 사이의 중간점을 취한다. 상속과 같은 타입 구조가 아닌 지원하는 연산에 따라 타입을 판별하는 것은 덕 타이핑과 똑같다. 하지만 타입 간의 호환성은 컴파일 시점에 검증함으로써 타입 안전성과 더불어 수행 효율을 증대시키는 방법이다.
interface Duck {
public:
    void walk();
    void swim();
    void quack();
};
// 새끼 오리
class BabyDuck {
    ...
};
// 나는 오리
class FlyingDuck {
    ...
};
Duck duck = new FlyingDuck;

구조적 타이핑을 지원하면 얻을 수 있는 이점으로는 여러 가지가 있겠지만 가장 큰 것으로는 각각의 객체들이 타입 정의에 종속되지 않기 때문에 프로그램 내부의 결합도가 크게 낮아진다는 강점이 있다. 요구하는 인터페이스와 구현 사이의 관계가 칼 같이 분리되기 때문이다. 다형성을 활용하기 위해 상속 구조를 고민할 필요가 없어지고, 그저 인터페이스에서 요구하는 연산을 구현해주기만 하면 된다. 그리고 타입에 대해 필요한 가정이 객체가 지원하는 연산 집합으로만 한정되므로 C++의 템플릿을 이용하는 것처럼 일반화 프로그래밍 Generic programming이 가능해지는 것도 한 가지 장점이다.

이렇게 좋은 개념이 있음에도 불구하고 그간의 주류 OOP 언어에서 지원하지 않은 이유는 이를 효율적으로 구현하는 데에 있어 난점이 있었기 때문이다. 상속 기반 다형성을 구현하기 위해서 보통 가상 함수 테이블을 사용하는데, 이는 상속이라는 개념을 통해 해당 클래스가 어떤 인터페이스에서만 사용될지를 예측할 수 있어서 가능한 것이다. 하지만 구조적 타이핑 언어에서는 비슷한 방법을 쓰려면 프로그램 전체에 대한 분석을 수행하던지 모든 클래스와 모든 인터페이스에 대해 필요한 디스패치 테이블을 만들어줘야 한다. 이런 이유로 구조적 타이핑을 지원하는 언어가 흔치 않았는데 비교적 최신 언어인 haskell이나 구글의 go 등에서는 타입의 메타 데이터를 이용, 실제로 사용되는 클래스-인터페이스 조합에 대해서만 런타임에 딱 한번 디스패치 테이블을 만들어 사용하고 컴파일 시점에는 타입 안전성만을 체크하는 방법을 통해 효율적인 구현을 해냈다.


4. 가비지 컬렉션 Garbage collection

C++ 프로그래머들에게 Java에서 가장 부러운 것을 들라고 하면 아마도 첫 번째로는 방대한 표준 라이브러리가 나올 것이고, 두 번째로는 가비지 컬렉션이 나올 거라고 생각한다. 적어도 난 그렇다. 그래도 전자는 boost라는 괴물이 있기 때문에 많은 부분 상쇄될 여지가 있지만, 후자는 그 구현의 난이도 때문에 당분간은 가망이 보이질 않는다. [각주:2]

다행스럽게도 하위 호환성 신경 쓸 필요 없는 완전히 새로운 언어를 만드는 경우의 가비지 컬렉션 지원은 "비교적" 간단하다. 그런데 멀티 쓰레드 환경에 들어가면 그 비교적이라는 단어의 의미가 좀 무색해지긴 한다. orz

가비지 컬렉션의 가장 분명한 강점은 당연히 메모리 관리가 수월해진다는 점에 있다. 하지만 그 외에 얻을 수 있는 것으로는 추가적으로 메모리 압축 memory compaction을 지원함으로써 얻는 성능적인 이점이다. 메모리 압축이 이루어지면서 단편화 문제도 원천적으로 사라지고, 캐쉬 지역성을 조금 더 잘 활용할 수 있다는 점 등으로 인해 가비지 컬렉션으로 인한 성능적인 약점이 어느 정도 상쇄된다. 또한 메모리를 어떻게 할당해도 최종적으로는 공간을 최적으로 활용한다는 보장이 있기 때문에 새로운 메모리를 할당하는 속도가 일반적인 메모리 할당자와는 비교도 안 될 정도로 빨라진다는 점도 있다. [각주:3]

허나 가비지 컬렉션이 아무리 빨라져도 수동으로 해제하는 것에 비해서는 빠르기가 어렵다. 이게 단순히 프로그램 전반의 throughput이 떨어지는 정도라면 큰 문제가 아니겠지만, 그 부하가 한 순간에 집중됨으로써 반응 속도가 느려지는 것이 문제다. 이를 해결하기 위해 사용되는 다양한 알고리즘들이 있지만 모든 경우에 대해 완벽하게 적용 가능한 일반적인 알고리즘은 없다. 또한 가비지 컬렉션을 사용하는 경우 프로그래머가 객체의 수명을 직접 컨트롤할 수 없다는 것 역시 큰 문제다. 따라서 가비지 컬렉션에 사용되는 정책을 필요에 따라 적절하게 조절할 수 있는 기능과 더불어 소유권이 명백한 객체에 대해서는 사용자가 수동으로 관리할 수 있도록 하는 방법을 공존시킬 방안을 모색해봐야 한다.


어쩐지 너무 길어지고 있다. 다음에 꼐속.
  1. C++0x가 2012년에 공표된다는 이야기를 보면 마이너 패치였던 C++03을 제하면 첫 표준 이후로 다음 표준까지의 기간이 14년이나 걸리는 셈이다. [본문으로]
  2. 소멸자가 호출되는 시점이 결정적(deterministic)이라는 C++의 특성과 연관된 부분들에서 많은 문제점들이 발생한다. 포인터를 값으로 직접 다룰 수 있는 언어의 특성도 한 몫한다. [본문으로]
  3. 오라클의 JVM 구현에서는 메모리 할당이 10사이클 내외에 이루어진다. [본문으로]
Trackback 1 : Comment 0

무한대의 처리율과 용량을 가진 컴퓨터가 나온다면?

컴퓨터 과학 2010.12.03 23:22
 얼마 전에 생각해본 망상인데, 무한대의 처리율과 무한대의 용량을 가진 컴퓨터가 나온다면 프로그래밍에 있어서 어떤 변화가 생길까? 그냥 일반인의 관점에서 본다면 컴퓨터가 빨라지겠네, 이런 정도일지 모르겠으나, 소프트웨어 엔지니어의 관점에서 생각해보니 많은 부분들이 근본적으로 변할 것 같다는 생각이 들었다.


 알고리즘의 변화

 가장 먼저 생각할 수 있는 것은 알고리즘의 변화이다. 무한대의 처리율을 가진다는 것은 유한한 단계를 밟아 수행되는 모든 연산이 시작하는 순간 바로 끝난다는 것을 의미한다. 이렇게 되면 굳이 효율적인 알고리즘이 필요 없어진다. 정답만 낼 수 있으면 되니까 가능한 경우라면 대부분 무식하게 Brute force로 풀면 된다. 효율적인 코드를 짤 필요가 없으니 시공간 복잡도 같은 것을 신경 써가며 골치 아프게 코딩할 필요도 없고, 그냥 경우의 수만 잘 따져서 올바른 답안만 낼 수 있으면 된다. P != NP 문제도 큰 의미가 없어진다. 문제의 크기가 유한하기만 하면 곧바로 답이 나오는데 누가 신경 쓰겠는가?

 그렇지만 알고리즘 자체의 중요성이 떨어지는 것은 아니다. 오히려 이런 시대가 되면 더더욱 알고리즘의 중요성이 부각될 수도 있다. 이 분야에서는 문제를 효율적으로 푸는 것도 목표 중 하나지만 문제를 올바르게 푸는 것 역시 중요한 목표다. 심지어는 "올바르게" 푸는 방법이 따로 없거나 풀더라도 그 결과에 대한 기준 자체가 모호하거나 공식화하기 어려운 경우도 많다. 정지 문제 Halting problem 같이 아예 풀 수 없는 문제도 있고, 괴델의 불완전성 정리에 의해 밝혀진 바와 같이 풀 수 있는지의 여부조차 알 수 없는 문제도 있다. 이런 문제들에 대한 해법을 연구하는 것은 무한대의 처리율을 가진 시대에도 여전히 큰 의미를 가진다. 다만 문제를 푸는 방법 자체보다는 현실의 문제를 수학적으로 엄밀하게 정의하고 도식화시키는 과정이 더 부각될 뿐이다. 

 다만 자료 구조 사용에 있어서는 혁명적인 변화가 예상된다. 일단 대부분의 자료 구조는 리스트 하나로 통합 가능해진다. 연관 배열이 필요하다면 키과 값을 함께 넣고 그때 그때 찾아서 쓰면 된다. 정렬된 순서에 따라 자료에 접근하고 싶다면 리스트를 복사한 뒤 정렬해서 쓰면 된다. 대부분의 경우 프로그래밍을 할 때 자료 구조에 대해 고민할 필요 없이 설계만 신경 쓰면 되는 것이다. 하지만 그래프까지 필요한 경우에는 여전히 공부가 필요할 것 같다. 그래프 관련 문제들은 대개 쉽게 일반화 되지 않는 경향이 있기 때문이다. 그렇지만 Brute force라는 녀석이 우리의 친구이니 문제 풀기는 예전보다 훨씬 쉬울 것이다.


 운영체제의 변화

 현대 컴퓨팅에서도 운영체제가 맡는 가장 중요한 역할로는 컴퓨팅 자원의 배분을 꼽을 수 있다. 그 중 으뜸은 각 프로세스/쓰레드에 프로세서 시간과 메모리를 배분하는 것인데, 이 둘이 무한하다고 가정하면 이들을 굳이 관리해 줄 필요가 없다. 코드를 수행시켜도 잡아 먹는 시간이 0 이니 그냥 들어오는 작업 목록을 하나하나 수행시켜주는 것으로 프로세스/쓰레드 스케쥴링이 끝난다. 또 메모리는 그냥 스택 형식으로 관리하면서 요청이 들어오면 원하는 만큼 퍼주기만 하면 된다. 게다가 모든 코드의 수행 시간이 0이니 원칙적으로 시간으로 인한 예외적인 상황이 발생하지 않는다. 고로 실시간 OS라는 개념도 무의미해진다.

 그렇지만 다양한 서비스의 추상화로써 운영체제가 가지는 의미는 그대로 유지될 것 같다. 이를테면 다양한 프로그램의 독립적인 수행을 보장하는 프로세스라는 개념은 여기에서도 여전히 유용하다. 아무리 무한대의 처리율을 가진 프로그램이라고 해도 현재의 폰 노이만 구조에서 멀티 프로그래밍의 개념을 지원하려면 밑단을 적절하게 추상화할 필요가 있다. 프로세서 시간 배분이야 간단하게 관리 가능하겠지만 물리적인 메모리는 모든 프로세스가 공유하니 운영체제 차원에서 주소 공간을 적절하게 배분/관리해 줄 필요가 있다. 그 외에도 시간/네트워크/파일/장치 등을 관리하는 것은 여전히 운영체제가 해줘야 할 일이다. 이리 생각해보면 운영체제가 맡는 역할은 모든 프로그램들이 공유하는 기능의 집합, 일종의 라이브러리 수준으로 격하되는 셈이다.


 프로그래밍 방법의 변화

 같은 문제를 풀기 위해 필요한 프로그래밍의 난이도는 대폭 낮아질 것이다. 굳이 C/C++ 같이 성능을 위해 많은 것들을 포기한 언어를 쓸 필요가 없다. 고로 성능을 희생하여 강력한 표현력을 가지게 된 여타 언어들을 사용하는 것만으로도 생산성의 큰 향상을 얻을 수 있다. 게다가 최적화라는 개념 자체가 무의미해지고 그저 문제 도메인을 잘 기술하기만 하면 되니 효율적이진 않더라도 우아하게 프로그래밍 할 수만 있으면 된다.

 또 지금은 프로그래밍을 할 때 적지 않은 개발 자원을 예외/에러 처리에 투입하는데, 이 부분도 아주 간단해진다. 예외/에러가 발생하는 대부분의 상황은 그 근본적인 원인을 따져나가면 결국 자원 부족으로 귀결되기 때문이다. 혹은 자원 부족이 아니라면 시간/타이밍 문제일텐데, 처리율이 무한대라는 것은 시간적으로 발생하는 예외적인 상황을 신경 쓸 필요가 크게 줄어든다는 이야기다. 이러한 처리들이 사라지고 신경써야 할 것은 오로지 프로그램 자체적인 논리 에러만이 남게 되므로 견고한 프로그램을 만들기가 훨씬 쉬워질 것이다.

 멀티 쓰레드 프로그래밍의 난이도 역시 급감하게 된다. 일단 성능을 올리기 위해 멀티 쓰레드를 사용하는 경우 자체가 사라지니 멀티 쓰레드가 필요한 부터가 많이 줄어든다. 설령 동시 처리 자체가 도메인에 잘 맞아서 사용하는 경우도 많은 부분이 단순해진다. 모든 연산이 즉각적으로 처리된다는 것은 모든 코드가 선형화 가능 Linearizable해진다는 의미인데, 이건 이상적인 트랜잭셔널 메모리 Transactional memory와 등가이다. 이렇게 되면 각 문맥 사이의 코드 인터리빙이 완전히 사라지니 락 같은 원시적인 동기화의 개념은 필요 없어지고, 조건 변수 Condition variable 같이 코드 수행의 전후 인과 관계를 결정하는 기본적인 동기화 방법만 필요하게 된다. 이건 협력적 쓰레딩인 코루틴 Coroutine을 쓰는 것과 하등 다를 게 없다. 동시 처리 모델이 엄청나게 간단해지는 것이다.

 그런데 결과적으로 프로그래머들이 접하는 프로그래밍의 난이도가 낮아질까 하면 또 그건 아닐 것 같다. 알고리즘과 비슷한 이유인데, 아무리 프로그래밍이 쉬워지고 편리해져도 그 난이도가 풀어야 하는 문제 자체의 복잡도 아래로 내려갈 수는 없다. 그런데 처리력이 올라가는 만큼 풀고 싶은 문제의 도메인은 훨씬 크고 넓어질 것이다. 고로 현재 프로그래머에게 복잡도를 관리할 수 있는 능력이 가지는 의미를 생각해 볼 때 프로그래밍 자체가 크게 쉬워지진 않을 것 같다. 하지만 문제 도메인과 무관한 다른 영역들에 신경 쓸 필요 없이 문제 자체에 집중할 수 있게 된다는 것은 꽤나 즐거운 일이 아닐까?


 게임 개발의 변화

 지금은 내가 게임 프로그래머니까 이걸 한 번 따로 떼서 생각해보기로 했다. 충분한 연산 능력을 가지고 있는 경우 많은 렌더링 테크닉들이 글로벌 일루미네이션 Global illumination 하나로 통합될 수 있다고 한다. 그래픽 프로그래밍을 잘 모르는 나로써는 참으로 신나는 일이다. 하지만 이건 포토 리얼리스틱에 한해서고, 스타일리쉬한 그래픽을 창조하는 것은 여전히 큰 일일 것 같다. 이건 아트 스타일과도 직결된 문제라 이렇게 되면 예술적인 감각을 가진 사람들이 좀 더 대우를 받지 않을까.

 애니메이션이나 물리 프로그래밍은 그리 쉬워질 것 같지 않다. 이 쪽은 성능도 문제지만 그걸 그럴싸하게 보이도록 만드는 것도 중요하다. 물론 성능 때문에 각종 꼼수를 써야 했던 부분들은 사라지겠지만 그걸 감안해봐도 애니메이션 프로그래밍은 그리 간단한 문제가 아니다. "그럴싸하게 보인다"에는 특정한 기준이 없고 또 가치 판단에 가깝기 때문에 결국 프로그래머가 좋은 의사 결정을 내리는 수 밖에 없다. 또 애니메이션은 제 아무리 일반화를 시키려고 해도 게임 플레이 로직과도 밀접한 연관을 가지므로 그 복잡도가 어느 정도 이하로 내려가기는 어려울 것이라 생각한다.

 네트워크 프로그래밍은 많이 쉬워질 것 같다. 네트워크 프로그래밍에서 중요한 것으로는 성능과 동기화 문제가 있는데, 일단 성능 문제는 바로 해결되고 동기화 역시 타이밍 문제가 사라진다 치면 네트워크 프로그래밍은 직렬화 로직의 문제로 간소화된다. 게다가 무한대의 처리율 덕분에 대부분의 예외 사항들을 굳이 고려할 필요가 없어질테니 더더욱 편해진다. 직렬화 루틴만 잘 만들어놓으면 사실상 게임 플레이에 그대로 통합될 수 있는 부분이다.

(이 주제로 올린 글에 대한 한 게임 기획자의 반응)

 게임 플레이 프로그래밍에서는 그 동안은 성능 문제로 불가능했던 것들이 가능해지긴 할텐데... 일반적인 기획자들의 성향을 볼 때 그게 가능해지면 게임 플레이 로직 자체가 훨씬 복잡해질 가능성이 높다. (...) 플레이어 100만명이 한 필드에 모여서 조낸 치고 박고 싸우는 것도 쉽게 구현할 수 있겠지만 그 와중에 뭔가 재미 요소를 방해하는 요인이 잔뜩 발견되어 이리저리 예외가 추가되고 로직이 복잡해지면서 유지 보수가 까다로워지는 것은 무한대의 처리율을 가지고 있는 컴퓨터라고 해도 예외는 아닐 것이다. 뭐 그렇다고 해도 같은 수준의 게임을 개발할 때엔 이 쪽이 훨씬 간편할 것이라는 점은 명백하다.


 그 외에 떠오르는 생각
 
 아마도 보안이라는 개념 자체가 크게 달라져야 할 것이다. 현대 컴퓨터 과학에서 보안에 사용되는 메커니즘들은 전부 Brute force로 풀어낼 수 있다. 다만 가능한 경우의 수가 너무나 많기 때문에 암호를 의미 있는 시간 내로 풀어내지 못하는게 문제인데, 이건 처리율이 무한대면 아무 문제도 되지 않는다. 즉, 보안을 유지하기 위해서는 지금과 같이 키를 이용한 방식과는 완전히 다른 메커니즘의 보안이 필요하다. 아니면 적어도 암호에 사용되는 키가 이산적인 Discrete 형태여서는 안 된다.

 디버깅 역시 무척이나 편리해질 것이다. 메모리 제한이 없고 모든 연산에 들어가는 시간이 0이니 일단 매 인스트럭션을 처리할 때마다 프로세스의 메모리 상태를 전부 스냅샷 찍어 놓으면 브레이크 포인트를 찍고 앞 뒤로 상태를 전부 확인해보며 디버깅이 가능해진다. 또 지금은 현실적으로 무리인 작업들, 이를테면 원하는 모든 메모리 지역에 전부 브레이크를 걸어서 변수가 변하는 시점들에 맞춰 로직을 하나 하나 확인해보는 꿈 같은 일도 연산 속도가 무한대니 가능해진다.


(이 주제로 다른 게시판에 올린 글을 본 일부인들의 반응)

 정리해보니 무한대의 처리율/메모리를 가진 컴퓨터가 나오면 그 동안 컴퓨터 과학이 만들어 낸 대부분의 성과가 의미 없어진다는 결론을 내릴 수 있다. 이걸 거꾸로 말한다면 그간 컴퓨터 과학 분야에선 이상적이지 못한 컴퓨팅 환경을 최대한 추상화하고 극복하기 위해 대부분의 노력을 기울여 왔다고 할 수도 있다. 글의 주제를 생각해보면 역설적이겠지만, 이 분야에서 효율이라고 하는 것은 그만큼이나 중요한 테마라고 볼 수도 있다. 물론 시대가 지날 수록 컴퓨터의 속도는 빨라지지만, 소프트웨어가 느려지는 속도는 그보다 더 빠르다는 Writh's law를 생각해보면 안심할 수 없다. 따라서 우리가 좋은 밥을 먹고 살기 위해서는 효율적인 프로그램을 만들기 위해 쉴 새 없이 수련해야 한다는 결론을 내릴 수 있다.
Trackback 0 : Comment 0

멀티 쓰레드 프로그래밍이 어려운 까닭

컴퓨터 과학 2010.04.28 21:48

보통 멀티 쓰레드 프로그래밍 하면 손사레부터 치는 사람들이 대단히 많다. 이 쪽에 대해 나름 공부를 하고 있다 생각하지만 아직까지 버그가 없으면서 높은 병렬성을 가진, 어느 정도 이상 규모를 가진 프로그램을 일반적인 순차적 프로그래밍을 짜듯 쉽게 만들 자신은 없다. 팀 스위니 같은 천재조차도 멀티 쓰레드 프로그래밍은 쉽지 않다고 고백하는 것을 보면 현재 주된 개발 방식 어딘가에 동시성과 맞지 않는 근본적인 한계가 존재한다는 추측을 하게 된다.

 
 멀티 쓰레드 프로그래밍이 어려운 까닭을 파고 들어가면 현재 가장 주류를 이루고 있고 또 성공적으로 적용 중인 구조적 프로그래밍이라는 개념 자체가 동시성 프로그래밍에 적합하지 않다는 점에 그 근본적인 원인이 있음을 알게 된다.[각주:1] 이러한 원인을 알기 위해서는 우선 구조적 프로그래밍에 대한 이해가 필요하다.


 구조적 프로그래밍이란 프로그램의 논리를 작은 단위로 나누어 생각할 수 있도록 하위 구조(sub-structure)라는 논리적인 단위를 제공한다. 이러한 하위 구조의 가장 작은 단위는 일반적으로 문장(statement)인데, 구조적 프로그래밍에서는 이들을 순차적으로, 혹은 필요에 따라 비순차적으로 수행하도록 적합한 제어 구조를 제공함으로써 작은 하위 구조로 부터 더 큰 프로그램을 조립해나간다.

 여기에서 중요한 것은 프로그램의 문맥이 특정한 상태에서 어떤 하위 구조로 진입했을 때, 프로그램 작성자가 그 결과를 결정적으로(deterministic) 예측할 수 있다는 점에 있다. 하위 구조의 동작 결과를 알고 있기 때문에 이러한 하위 구조를 조립한 상위 구조들의 동작 결과도 미리 예측 가능하며, 이러한 전제 하에 상방식(bottom-up), 혹은 하방식(top-down) 설계가 가능해진다. 이 때 각각의 하위 구조가 다른 구조에 영향을 적게 줄 수록 유지 보수가 쉬워지는 경향이 있는데, 이를 위해 그 범위를 가능한 하나의 객체로 좁히기 위한 노력들이 훗날 객체 지향 패러다임에 상당한 영향을 주었다고 한다.

 이 구조적 프로그래밍에서 가장 강력한 도구를 들라면 역시 서브루틴, 혹은 메쏘드이다. 잘 짜여진 서브루틴이라면 전제 조건(pre-condition)과 사후 조건(post-condition), 부가 효과(side-effect)가 명확하게 정의될 수 있다. 전제 조건이란 서브루틴에 진입하기 이전 프로세스[각주:2]의 상태가 가져야 하는 전제 조건들을 의미하며, 사후 조건이란 서브루틴을 수행한 이후 반환되는 결과 값 및 변화한 프로세스의 상태이다. 부가 효과란 해당 서브루틴의 수행으로 인해 발생한 프로세스의 변화 자체를 의미한다. 현재의 컴퓨터 모델에서는 서브루틴을 수행하는 사이에 발생한 메모리 영역의 변화 일체가 서브루틴 수행의 부가 효과라고 볼 수 있다.[각주:3]


 헌데 기존의 프로그램에 동시성이라는 개념이 등장하는 순간 기존의 이런 도구들이 전부 의미가 없어진다. 두 개 이상의 실행 문맥이 동시에 한 메모리 영역을 읽고 쓰는데에 아무런 제약이 가해지지 않기 때문이다. 헌데 서브루틴이건 하위 구조이건 수행 자체에는 시간이 필요하고, 그 사이에 한 메모리 영역을 두 쓰레드가 동시에 조작하려 시도하면 비결정적(non-deterministic)인 결과, 이른바 데이터 레이스가 나오게 된다.

 문제는 이 뿐만이 아니다. 설령 데이터 레이스가 존재하지 않는다고 하여도 싱글 쓰레드와 멀티 쓰레드 사이에는 프로그래밍 방식에 있어 현격한 차이가 있다. 만약 단일 쓰레드가 특정 객체를 수정하는 서브루틴를 수행한다 하면 일반적으로 진입 이전과 이후의 객체 상태는 모두 의미 있는 상태일 것이다. 이러한 가정 하에 구조적 프로그래밍이 가능해지는 것이다. 그러나 두 개 이상의 쓰레드가 그러한 서브루틴을 수행한다면 수정이 완전히 이루어지지 않는 불완전한 상태의 객체에 접근하게 될 가능성이 있다. 동시에 접근될 가능성이 있는 모든 객체에 대해 가능한 모든 불완전한 상태에 대한 대비를 해야 한다는 것이다. 이러면 당연히 프로그램의 복잡도가 현격하게 상승하게 되며, 이는 구조적 프로그래밍의 강점 하나가 그대로 사라지는 것을 의미한다.

 여기에서 구조적 프로그래밍의 가장 큰 전제가 무너지는 것이다. 구조적 프로그래밍에 있어 그 결과를 신뢰할 수 없는 하위 구조는 존재 가치가 없으며, 그러한 하위 구조를 단 하나 가지고 있는 것 만으로도 해당 프로그램은 전혀 신뢰할 수 없는 프로그램이 되고 만다. 그렇지 않은 하위 구조를 짜는 것은 싱글 쓰레드에 비해 몇 배의 노력이 들어가며, 뒤에서도 설명하겠지만 특정 조건을 만족하지 않는 이상 이러한 하위 구조들은 서로 조합이 불가능하다는 치명적인 문제가 존재한다.


 그간 연구자들이 이에 대해 손을 놓고만 있었던 것은 아니다. 컴퓨터 과학계에서는 수십년 전부터 동시성에 대한 연구가 시작되었고, 특히나 CPU 자원의 공평한 분배가 중요한 운영체제론에서는 동시성에 대한 연구가 광범위하게 진행되어 왔다. 쓰레드나 락, 데이터 레이스 등의 개념을 프로그래밍 자체보다는 운영체제나 시스템 프로그래밍 등의 테마를 공부하며 배우는 사람이 많은 것은 바로 이런 까닭이다.


 가장 먼저 나온 방안은 (그리고 현재까지 가장 널리 통용되는 방안은) 필요한 경우 락을 이용하여 프로그램 수행을 직렬화하는 것이다. 간단히 말해 의미 없는, 불완전한 상태의 객체에 관한 서브루틴이 수행될 가능성이 있는 경우 진입 지점에 적당히 락을 걸어 두 개 이상의 쓰레드가 동시에 객체를 수정하지 못하도록 막는 것이다. 이 방법은 구현이 쉽고, 가장 기계 친화적인 방식이기 때문에 아직까지 널리 쓰인다.

 그러나 구조적 프로그래밍과 이 방식이 잘 맞느냐를 묻는다면 회의적이다. 구조적 프로그래밍은 말 그대로 하위 구조의 조합을 통해 프로그램을 만들어가지만, 일반적으로 락 기반 프로그래밍은 객체 단위로 락을 할당한다는 점을 생각해보면 이 방식은 런타임에 존재하는 실제 객체의 상태에도 다분히 의존적이다. 기존에는 주로 하위 구조들이 이루는 프로그램의 구조에 대해서만 신경쓰면 됐다면 [각주:4] 이제는 여기에 런타임의 프로세스 상태라는 새로운 차원까지 치밀하게 신경써야 한다. 이로 인해 락을 이용한 하위 구조들끼리는 별 다른 조치 없이 그대로 조합하는 것은 불가능하며, 악명 높은 동시성 버그인 데드락이 발생하는 까닭의 99%는 여기에 있다. [각주:5]

 이런 방식 대신, 프로세서가 제공하는 원자적 명령어[각주:6]를 통해 서브루틴을 수행하는 구간에 대해 해당 객체가 항시 유효한 상태임을 보장하는 방식인 이른 바 Lock-free, Wait-free로 대변되는 non-blocking 동기화 기법도 존재한다. 여기에서는 보통 프로그램의 복잡도를 제어 가능한 수준으로 낮추기 위해 선형화(Linearization)라는 개념을 도입한다. 선형화의 아이디어는 간단히 말해 특정 쓰레드가 특정 객체에 대한 작업를 수행한다 치면 다른 쓰레드에 있어서는 이 작업이 한 순간에 일어난 것처럼 보이도록 하자는 것이다. 데이터베이스의 트랜잭션과 어느 정도 유사한데, 이런 방식으로 접근을 하면 동시적으로 수행되는 각 작업들 사이의 선후 관계를 판별하는게 가능해지고, 또한 락을 이용한 방법과는 달리 하위 구조끼리의 조합도 가능해진다.


 허나 non-blocking 동기화 기법은 기존의 알고리즘을 선형화시켜야 한다는 제한이 있기 때문에 코딩하기가 대단히 까다롭다. 이는 현대 프로세서들이 제공하는 원자적 연산 명령들의 한계 때문인데, 대부분의 경우 근접해있는 64비트 변수 두 개를 원자적으로 바꾸는 명령 정도가 한계이다. 이러한 명령만을 이용하여 프로그래밍하는 것은 락을 이용한 프로그래밍에 비해 절대 쉽다고 할 수 없다. 그렇기 때문에 대개의 경우는 아주 기초적이고 자주 사용되는 자료구조에 한해 이러한 프로그래밍 기법을 사용하는 것이 대부분이다.

 그러나 선형화라는 아이디어 자체는 상당히 유용하기 때문에 동시성 모델을 만들고 사고하는데 있어 (락을 이용하는 경우에도) 쓸만하며, 또한 하위 구조간 조합이 아무 제약 없이 가능하다는 강점 덕분에 구조적 프로그래밍과 상당히 궁합이 잘 맞는다. 여기에서 더 나아가 특정 코드 구간에서 일어나는 모든 연산이 원자적으로 일어난다는 것을 보장할 수 있으면 어떨까? 이런 아이디어에서 Transactional memory라는 개념이 등장한다. Transactional memory란 간단히 말해 특정 수행 구간에서 일어난 메모리 변화를 원자적으로 반영시키는 개념으로, 메모리 버젼의 트랜잭션이라고 생각하면 된다. Transactional memory가 구현되면 모든 코드를 아주 쉽게 선형화 할 수 있게 되므로 동기화에 대한 시름거리를 하나 덜어버리는 셈이 되나, 안타깝게도 아직까지는 이를 실용적인 수준까지 구현한 사례는 존재하지 않는다.


 현재까지는 어느 쪽이든 그 난이도가 낮지 않다. 이 외에도 수많은 방법들이 제안되었고 또 제안되고 있지만, 아직까지는 확실하게 은탄환이라 불릴 만한 해법은 나오지 않은 상태이다. 병렬, 동시성 프로그래밍은 로직 자체를 고민하는 것도 만만치 않은데 여기에 이런 다양한 문제들이 엮이면서 그 난이도가 살인적인 수준까지 올라간다. 마땅한 방법이 없는 현재로써는 이를 하나 하나 공부하며 그때 그때 맞는 방법론을 찾아 적용하는 수 밖에 없어 보인다.

  1. 물론 이게 goto를 쓴다고 해결된다는 의미는 절대 아니다. [본문으로]
  2. 여기에서 프로세스란 시스템 프로그래밍적 관점에서의 그 용어가 아닌, 프로그램의 인스턴스로써의 프로세스를 의미한다. [본문으로]
  3. 물론 이에 한정되지는 않는다. I/O도 부가 효과라고 볼 수 있으니까. [본문으로]
  4. 꼭 그렇지만은 않지만, 대부분은 좋은 설계에 의해 해결된다. [본문으로]
  5. 이 뿐만 아니라 lock contention, lock convoying등 락으로 인한 문제점은 셀 수도 없이 많다. [본문으로]
  6. Compare and swap등. [본문으로]
Trackback 1 : Comment 0

Local search

컴퓨터 과학 2009.11.01 14:37

내용 보기

Trackback 0 : Comment 0

Informed search

컴퓨터 과학 2009.10.22 20:28

내용 보기

Trackback 0 : Comment 0

Uninformed search

컴퓨터 과학 2009.10.21 02:49


내용 보기

Trackback 0 : Comment 0

티스토리 툴바