크리티컬 섹션 문제

회사에서 하는 금요 세미나. 저번주에는 K군이 크리티컬 섹션에 대해 발표했었다. K군이 발표에 삽질을 좀 했지만, 크리티컬 섹션 문제는 parallelism에서 매우 중요한 개념이므로 정리하고 넘어가자.

크리티컬 섹션이란, 두 개 이상의 쓰레드(혹은 프로세스)가 있을 때, 같은 공유자원에 접근하고자 시도하는 코드 구간을 말한다. 크리티컬 섹션이 왜 치명적인가 하면, 크리티컬 섹션이 아닌 구간에서는 패러럴리즘에 의해 잘못된 결과가 나올 리가 없기 떄문이다. 논리적으로 타당함에도 불구하고 패러럴리즘에 의해 잘못된 결과가 나올 수 있는 부분은 공유자원을 두 개 이상의 쓰레드에서 동시에 접근하려고 시도하는 곳 외에는 없다. 그래서, 다른 쓰레드와의 공유 자원에 접근하려고 하는 부분을 '치명적 구간'이라고 하는 것이다. 일부 번역서에서는 '임계영역'이라고 하기도 하는데, '제대로 관리하지 않으면 오류가 일어나는 부분'이라는 의미가 잘 살아나지 않는 것 같다. 개인적으로는 '치명적 구간'이라고 하기를 좋아하지만, 이래저래 (잘못된) 번역에 익숙해진 한국 프로그래머가 많으므로 난 그냥 '크리티컬 섹션'이라고 한다.

크리티컬 섹션을 제대로 처리해주지 않으면 잘못된 결과가 나오는 것은 전형적으로 다음과 같은 두 쓰레드를 생각하면 된다.

thread a :
int i=0;
void thread_a()
{
    i++;
}

thread b:
extern int i;
void thread_b()
{
    i--;
}

쓰레드 a와 b가 동시에 시작했다고 치면, 두 쓰레드가 종료했을 때 i의 값은 -1, 0, 1의 세 값중 어느 값이라도 가질 수 있게 된다. 이는 C++의 단항 증감연산자가 기계어로는 로드/산술연산/저장의 3가지 단계로 나뉘기 때문이다. 단순하게 생각하자면 A쓰레드의 로드/연산/저장이 순서대로 실행될 때 사이사이에 B쓰레드의 로드/연산/저장이 끼어든다고 보면 된다. 가능한 경우의 수는 많지만 대표적인 결과가 나오는 경우만 보면 다음과 같다.

A로드 > A연산 > A저장 > B로드 > B연산 > B저장 ==>  0
A로드 > B로드 > A연산 > A저장 > B연산 > B저장 ==> -1
A로드 > B로드 > A연산 > B연산 > B저장 > A저장 ==>  1

따라서 크리티컬 섹션 문제를 해결하는 것은 특정 쓰레드의 동작 사이에 다른 쓰레드가 끼어들지 못하도록 어떻게 하느냐 하는 것으로 귀결된다. 대략적으로 크리티컬 섹션 문제의 해결책은 다음과 같이 사용하게 된다.

wait( S )      // wait for entering critical section
..............    // critical section
signal( S )   // allow other threads to enter critical section

OS책에서는 크리티컬 섹션 문제의 해결책은 다음 조건을 만족해야 한다고 나온다. 중요하다.

• Mutual Exclusion (상호 배제)
• Progress (진행)
• Bounded Waiting (유한 대기)
  

상호 배제는, 크리티컬 섹션 문제의 본질인, 한 쓰레드가 자원 R에 대한 크리티컬 섹션을 수행중일 때에는, 다른 쓰레드가 같은 자원 R에 대한 크리티컬 섹션에 들어가서는 안된다는 뜻이다. 진행 조건은, R에 대한 크리티컬 섹션을 수행중인 쓰레드가 하나도 없을 때에는, 어떤 쓰레드가 R에 대한 크리티컬 섹션에 들어가려고 하면 즉시 진행이 되어야 한다는 조건이다. 유한 대기는 말 그대로, 어떤 쓰레드가 R의 크리티컬 섹션을 수행하려고 할 때에는 다른 쓰레드의 R 크리티컬 섹션 진입이 유한한 횟수만큼만 이루어져야 한다는 조건. 당연한 소리같아보이지만, OS책에 나오는 크리티컬 섹션 문제의 솔루션들은 위 3가지 조건을 만족하게 만들기 까지의 발전과정이다. 언뜻 금방 생각할 수 있는 해결책들은 위 3가지 조건을 모두 만족하기가 쉽지 않다.

크리티컬 섹션 문제 해결에 가장 중요한 개념은 wait와 signal에 atomic operation이 도입되었다는 점이다.atomic operation을 뭐라 번역해야 할지는 모르겠지만, (원자적 연산;같은 구린 번역은 꺼져라!) atom의 원래의미인 '쪼갤 수 없는' 연산이란 뜻이다. (atom을 물질계에 적용한 용어인 '원자'가 어울리는 번역이 아닌 이유) 위에서C++의 단항 증감 연산자가 로드/연산/저장의 3단계로 나뉘어서 배열될 수 있는 데 비해, 아토믹 연산은 항상 단체로몰려다니고, 쪼개져서 배열될 수 없는 연산을 가리키는 개념이다. 현대적인 CPU는 모두 다 CPU의 기본 명령어중에 아토믹 연산이 명시되어 나오므로, OS는 크리티컬 섹션 문제의 해결책에 CPU의 아토믹 명령을 쓸 수 있다. 하드웨어의 도움으로 좀 더 우아한 해결책이 나올 수 있는 것은 자명한 일.

대표적인 해결책은 위대한 컴퓨터 과학자인 Dijkstra가 제안한 세마포다. 세마포의 기본적인 아이디어는 공유자원에 동시에 접근할 수 있는 쓰레드의 갯수를 미리 정해두고 지정된 수의 쓰레드만이 크리티컬 섹션에 진입할 수 있도록 한다;는 것이다. 2개 이상의 쓰레드가 동시에 같은 자원을 공유하는 크리티컬 섹션에 들어갈 수 있으면 counting semaphore, 오직 1개만이 크리티컬 섹션에 진입할 수 있으면 binary semaphore라고 한다. 사실 counting semaphore는 binary semaphore를 이용해서 구현할 수 있으므로 binary semaphore가 더 중요하다.
세마포를 이용한 크리티컬 섹션 문제의 해결책은 크게 두가지 구현방법이 있을 수 있다. 한 가지는 busy waiting, 혹은 spinlock이라고 부르는, 쓰레드가 계속 루프를 돌면서 크리티컬 섹션에 진입하기를 기다리는 방법이고, 다른 한 가지는 쓰레드 자체를 대기 상태로 바꿔버리고 세마포의 대기 큐에 들어가게 만드는 것이다. 각기 일장 일단이 있는데, 스핀락 구현은 크리티컬 섹션 진입에 컨텍스트 스위칭에 들어가는 오버헤드가 없다는 점은 좋지만 싱글 프로세서 시스템에서는 쓸 수 없다는 단점이 있다. (한 쓰레드가 CPU에서 계속 루프를 돌고 있는데 다른 쓰레드가 CPU에 올라갈 수 있을 리가 없다) 반면, 쓰레드를 대기 상태로 바꾸는 해결책은 싱글 프로세서 시스템에서도 별다른 문제 없이 쓸 수 있지만, 컨텍스트 스위칭 비용이 들어가게 된다는 점이 좋지 못하다.
결국, 크리티컬 섹션 진입 빈도에 따라 적절한 방법을 선택하는 것이 중요하다는 말씀.