80년대 알고리즘으로 경쟁 조건(Race Condition) 막기: 실패의 이유와 교훈

소프트웨어를 개발하다 보면 '경쟁 조건(Race Condition)'이라는 골치 아픈 버그를 마주하게 됩니다. 두 개 이상의 쓰레드가 동시에 데이터를 건드리며 예상치 못한 결과를 만드는 이 문제, 겉보기엔 간단해 보여도 실제로는 복잡한 원리가 숨겨져 있습니다. 이번 포스팅에서는 80년대에 고안된 유명한 알고리즘이 어떻게 경쟁 조건 문제를 해결하려 했는지, 그리고 왜 오늘날엔 이 방법이 통하지 않는지 흥미롭게 풀어봅니다. 동시에, 현대 컴퓨터 구조의 복잡성이 프로그램 동작에 어떻게 영향을 미치는지까지 쉽게 설명합니다.

경쟁 조건이란? 소프트웨어에서 왜 무서운 버그일까

경쟁 조건이란, 여러 개의 쓰레드나 프로세스가 동시에 데이터를 수정할 때 발생하는 예측 불가한 버그를 의미합니다. 예컨대, 두 쓰레드가 하나의 카운터를 동시에 증가시키면 카운터 값이 맞지 않게 됩니다. 단순히 '1씩 더한다'는 연산도 컴퓨터 내부에서는 여러 단계로 나뉘어 처리되며, 이 과정이 겹치면 의도와 다른 결과가 나올 수밖에 없습니다.

CPU의 연산 방식: 왜 '원자적(atomic)'이지 않을까?

'counter = counter + 1'처럼 단순해 보이는 코드도 CPU 입장에선 '메모리에서 읽기 → 레지스터에서 증가 → 메모리에 저장'의 세 단계로 동작합니다. 이처럼 한 연산이 여러 조각으로 쪼개지기 때문에, 동시에 여러 쓰레드가 같은 데이터를 만질 경우 중간 상태에서 엉킨 결과가 나타날 수 있습니다. 이를 '원자적이지 않다'고 부르며, 이 덕에 경쟁 조건이 쉽게 발생합니다.

임계 구역과 상호 배제: 해법의 기본 원리

쓰레드들이 동시에 접근해서 문제가 생길 수 있는 부분을 '임계 구역(critical section)'이라고 합니다. 이때 중요한 건 '상호 배제(mutual exclusion)', 즉 한 번에 단 하나의 쓰레드만 임계 구역을 실행하도록 만드는 것입니다. 이렇게 해야만 데이터의 일관성이 보장되죠.

초보자의 함정: 단순한 제어 변수로는 경쟁 조건 막기 어렵다

많은 개발자가 처음엔 '현재 임계 구역에 있는 쓰레드를 표시하는 변수를 두면 되지 않을까?'라고 생각합니다. 예를 들어, 'isSafe' 같은 변수를 둬서 한 쓰레드가 임계 구역에 들어가면 false로 바꾸고, 나올 때 true로 되돌리는 방식입니다. 하지만 이 변수 자체도 여러 쓰레드가 동시에 읽고 쓰기 때문에, 결국 또 다른 경쟁 조건이 생깁니다. 단순한 제어 변수로는 문제를 근본적으로 해결할 수 없는 이유입니다.

페터슨(Peterson)의 알고리즘: 80년대의 고전적 해법

1980년대에 고안된 '페터슨 알고리즘(Peterson's Algorithm)'은 경쟁 조건을 막는 고전적인 방법입니다. 두 쓰레드가 각자 'flag'와 'turn'이라는 공유 변수를 사용해 임계 구역 접근을 조율합니다. 각 쓰레드는 자신의 진입 의사를 'flag'로 표시하고, 상대방에게 'turn'을 넘긴 후 기다립니다. 상대편이 임계 구역에서 나오면 진입을 허락받는 구조이죠.

이 방식은 '상호 배제', '진행성(progress)', '한정 대기(bounded waiting)'라는 세 가지 필수 조건을 만족합니다. 이론적으로 매우 훌륭한 해법입니다.

현대 컴퓨터에서 왜 페터슨 알고리즘이 잘 작동하지 않는 이유

문제는 컴파일러와 CPU가 실제로 명령어를 임의로 재배열한다는 점입니다. 컴파일러는 속도를 높이기 위해 코드의 명령 순서를 바꿀 수 있고, CPU 내부의 파이프라인이나 out-of-order 실행 시스템도 제어 순서를 뒤섞습니다. 이때 두 쓰레드가 공유 변수에 진입 의사를 표시하는 순서가 뒤바뀌거나, 캐시에 최신 값이 반영되지 않으면 페터슨 알고리즘으로도 경쟁 조건이 발생할 수 있습니다.

실제로 페터슨 알고리즘을 적용해서 카운터를 보호하려 해도, 현대 CPU와 컴파일러 환경에서는 값이 계속 엉키는 경우가 빈번합니다. 순수 소프트웨어 방식만으로는 더 이상 신뢰할 수 없는 셈이죠.

캐시 메모리와 멀티코어: 동시성 버그의 복병

타 코어에서 동작 중인 쓰레드가 자신의 캐시에 있는 값만 읽을 경우, 다른 코어 쓰레드가 수정한 최신 값이 반영되지 않을 수 있습니다. 즉, 물리적으로 동시에 동작하는 멀티코어 환경에서는 공유 변수의 변경 사항이 즉각 전달되지 않아 동기화 문제가 더욱 심각해집니다.

경쟁 조건의 진짜 해법: 하드웨어가 지원하는 원자적 연산

결국 경쟁 조건을 확실히 막으려면, 하드웨어 레벨에서 '원자적(atomic) 연산'을 지원해야 합니다. 이러한 연산은 컴파일러 최적화, CPU 재배열, 캐시 무결성 등 다양한 요소에 의해 영향을 받지 않고 오직 하나의 쓰레드만이 해당 데이터를 건드리도록 보장합니다. 그래서 현대의 동시성 프로그래밍에서는 하드웨어가 보장하는 'atomic operation'을 적극 활용합니다.

실무에서 경쟁 조건과 임계 구역을 다루는 방법

동시성 프로그래밍에서는 OS나 언어에서 제공하는 '뮤텍스(Mutex)', '락(Lock)', '세마포어' 등 하드웨어 지원 동기화 도구를 적극적으로 사용해야 합니다. 소프트웨어만으로 임계 구역을 보호하려 하기보다는, CPU에서 제공하는 'atomic instruction'을 이용하는 것이 안전합니다.

마무리: 알고리즘과 실제 하드웨어의 괴리에서 얻는 교훈

페터슨 알고리즘처럼 오래된 고전적인 해법도, 현대의 복잡한 하드웨어와 컴파일러 환경에서는 더 이상 완벽히 통하지 않습니다. 동시성 버그를 잡으려면 하드웨어 동작 원리에 대한 이해와 함께 시스템에서 제공하는 동기화 도구를 적극적으로 활용해야 합니다.

결론적으로, 코드를 짤 때는 프로그래밍 언어만 믿지 말고, '내가 만든 동기화 방식이 정말 하드웨어에서도 철저하게 작동하는가?'를 꼭 점검하세요. 가장 안전한 선택은 검증된 락과 atomic 연산을 사용하는 것입니다. 더 깊은 내용을 알고 싶다면, 다음 편을 기대해 주세요!

출처 및 참고 :