reorder와 lock-free algorithm

volatile 과 memory barrier에서 트랙백

회사에서 일하다가 T아저씨의 꼬임에 빠져 함께 몇가지 자료를 수집했다. 정리해보자면

Fun programming problem: a simple lock-free algorithm에 따르면 volatile keyword는 원래 MM I/O를 위해 고안되었었고, C++ Standard에 명시된 기능은 아래와 같다.

1. volatile 변수에 대한 R/W 작업은 compiler에 의해 삭제되지 않는다.
2. volatile 변수에 대한 R/W 작업 간의 순서는 compiler에 의해 reorder되지 않는다.

그리고 MS VC Compiler는 여기에 세가지를 추가했다.

3. global 변수(volatile이 아닐지라도)에 대한 R/W작업은 volatile 변수에 대한 read 이전으로 reorder되지 않는다.
4. global 변수(volatile이 아닐지라도)에 대한 R/W작업은 volatile 변수에 대한 write 이후로 reorder되지 않는다.
5. 이 규칙들은 hardware level에서도 적용된다.

위 포스팅에서, Eric Eilebrecht는 volatile만으로 구현했을 때 오류가 발생할 수 있는 간단한 lock-free algorithm을 소개하고 있다. 포스팅에서 언급한 바와 같이, reorder에 의해 발생한 버그는

1. 발생 확률이 극단적으로 낮고
2. 어셈블리를 직접 보지 않고서는 왜 발생했는지 찾기가 불가능하다.

이는 단순히 compiler level에만 국한되지 않는다. 많은수의 CPU는 Out-of-Order로 동작하며, 때문에 byte code의 순서가 옳다 하더라도 CPU level에서 변경될 수 있다.(In-Order CPU라고 무조건 예외는 아니다. Lockless Programming Considerations for Xbox 360 and Microsoft Windows) 다행히 주종인 x86/x64 CPU의 경우 이러한 문제점을 방지하기 위한 몇가지 규칙을 가지고 있는데 Who ordered memory fences on an x86?에 따르면

1. Load명령어끼리는 서로 reorder되지 않는다.
2. Store명령어끼리는 서로 reorder되지 않는다.
3. Store명령어는 이전의 Load명령어와 reorder되지 않는다.
4. MP환경에서 reorder는 인과 관계를 따른다.(transitive visibility)
5. MP환경에서 같은 메모리 주소에 대한 Store는 total order를 가진다.(모든 CPU의 시점에서 같은 순서로 값이 저장된다.)
6. MP환경에서, locked instruction들은 total order를 가진다.
7. Load/Store명령어는 locked instruction과 reorder되지 않는다.

와 같은 규칙을 가지고 있고, 1, 2, 3번 규칙만으로도 대부분의 경우에 발생할 수 있는 문제는 해결된다. (포스팅에서 문제가 되는 경우에 대한 간단한 예제를 확인할 수 있다.)

CPU에 의한 reorder를 명시적으로 막기 위한 instruction들을 Memory Barrier(memory fence, fence instruction)라고 부른다. 다만, x86/x64의 경우 locked instruction을 호출하는 것만으로 reorder를 방지할 수 있기 때문에, How Does KeMemoryBarrier Work?에서처럼 명시적인 fence instruction을 호출하지 않고, 의미없는 locked instruction을 호출함으로써 fence instruction을 대체할 수 있다.

compiler reorder를 방지하기 위해서는

1. 인라인 어셈블리를 사용하여 어셈블리 구문 위 아래로 최적화를 방지해 reorder를 막거나
2. compiler에게 hint를 주는 intrinsic(_ReadWriteBarrier)을 사용하여 방지할 수 있다.

문제는, 위에서도 언급했듯 reorder로 인해 발생하는 버그는 디버깅이 극히 어렵기 때문에(compiler reorder의 경우 byte code를 보고 찾을 가능성이라도 가지고 있지만, hardware reorder는 천부적인 감각으로 찾아내는 방법 외엔 답이 없다.) 검증되지 않은 lock-free algorithm을 쓰는 것은 매우 위험하다. 더군다나 quick-sort가 만들어졌을 때와 마지막 버그가 잡혔을 때 사이의 시간 간격을 생각해보면, 충분히 검증되었다고 생각되는 알고리즘도 그렇지 않을 가능성이 충분하다.(거기에 platform dependent하기까지 하다.)

한줄요약. 어지간히 크리티컬한 게 아니라면, 쓸데없는 곳에 로망을 꽃피우지 말고 lock과 함께 사는 것이 정신건강에 이롭다.