운영체제: 임계 구역(Critical Section) 문제와 해결 방법 소개

이전 글에서 우리는 CPU 스케줄링과 함께 여러 프로세스(또는 스레드)가 동시에 실행되는 환경에 대해 알아보았습니다. 이렇게 여러 실행 단위가 협력하거나 자원을 공유할 때, 공유 데이터(Shared Data)에 대한 접근을 안전하게 관리하는 것은 매우 중요합니다. 잘못 관리하면 데이터가 꼬이고 프로그램 전체가 오작동할 수 있죠.

 

이번 글에서는 여러 프로세스가 공유 자원에 접근할 때 발생하는 임계 구역(Critical Section) 문제가 무엇인지 정의하고, 이 문제를 해결하기 위한 기본적인 요구 조건과 고전적인 알고리즘들, 그리고 하드웨어 기반의 해결책까지 단계별로 살펴보겠습니다. 마지막에는 이러한 고전적 방법들의 한계를 극복하기 위한 중요한 개념인 세마포어(Semaphore)를 간단히 소개하겠습니다.

---

1. 임계 구역 문제란 무엇인가?

By Akhande5 - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=51598924

• 임계 구역 (Critical Section): 여러 프로세스(또는 스레드)가 공유 데이터에 접근하여 읽거나 쓰는 코드 영역(부분)을 의미합니다. 임계 구역 외의 나머지 코드 영역은 비임계 영역(Remainder Section)이라고 합니다.
• 경쟁 상태 (Race Condition): 둘 이상의 프로세스가 동시에 임계 구역에 진입하여 공유 데이터를 조작하려고 할 때, 실행 순서(Timing)에 따라 결과가 달라지는 예측 불가능한 상황입니다.
• 핵심 문제: "누가 먼저 공유 데이터를 안전하게 사용할 것인가?"에 대한 규칙(프로토콜)이 없으면, 경쟁 상태로 인해 데이터의 일관성(Consistency)이 깨지고 프로그램 전체가 잘못된 결과를 내놓을 수 있습니다. 이를 해결하기 위해, 임계 구역에 진입하는 프로세스들의 순서와 접근을 조율하는 메커니즘, 즉 동기화(Synchronization)가 필요합니다.

[Q&A]

• Q: "모든 공유 데이터 접근 코드가 임계 구역인가요?"
• A: 아닙니다. 여러 프로세스가 공유 데이터를 읽기(Read)만 하는 경우에는 동시에 접근해도 문제가 발생하지 않습니다. 임계 구역은 주로 공유 데이터를 수정(Write)하거나, 읽기와 수정이 혼재되어 데이터 일관성이 깨질 위험이 있는 코드 영역을 의미합니다.
• Q: "경쟁 상태는 왜 발생하나요? 코드 한 줄은 한 번에 실행되는 것 아닌가요?"
• A: 고급 언어에서 한 줄인 코드(예: count++)도 컴파일되면 여러 개의 기계어 명령어(예: load, increment, store)로 변환됩니다. CPU는 이 기계어 명령들을 하나씩 실행하는데, 각 명령어 실행 사이에 인터럽트나 문맥 교환(Context Switch)이 발생하여 다른 프로세스가 끼어들 수 있습니다. 이 때문에 코드 한 줄의 실행이 원자적(Atomic), 즉 중간에 방해받지 않고 한 번에 완료되는 것을 보장할 수 없어 경쟁 상태가 발생합니다.

---

2. 임계 구역 문제 해결을 위한 3가지 필수 조건

임계 구역 문제를 해결하는 어떤 방법(알고리즘, 기법)이든 반드시 다음 세 가지 조건을 만족해야 합니다.

1. 상호 배제 (Mutual Exclusion):
   • 가장 중요한 조건입니다. 어떤 프로세스가 임계 구역에서 코드를 실행하고 있다면, 다른 어떤 프로세스도 해당 임계 구역에 동시에 진입할 수 없어야 합니다. 즉, 임계 구역은 한 번에 오직 하나의 프로세스만 사용할 수 있도록 배타적으로 보호되어야 합니다.
2. 진행 (Progress):
   • 임계 구역에 아무런 프로세스도 없고, 임계 구역에 진입하기를 원하는 프로세스가 하나 이상 있다면, 오직 그 원하는 프로세스들 중에서만 다음에 임계 구역에 들어갈 프로세스를 선택해야 합니다. 이 선택은 무한정 연기되어서는 안 됩니다. 즉, 아무도 사용하지 않는데 괜히 못 들어가게 막거나, 엉뚱한 프로세스가 들어가는 것을 방지해야 합니다.
3. 유한 대기 (Bounded Waiting):
   • 어떤 프로세스가 임계 구역에 진입하기 위해 요청한 후, 그 요청이 허용될 때까지 다른 프로세스들이 해당 임계 구역에 진입하는 횟수에 한계가 있어야 합니다. 즉, 어떤 프로세스도 임계 구역에 들어가기 위해 무한정 기다리는(Starvation) 상황이 발생해서는 안 됩니다.

주의: 이 조건들을 만족하는 동기화 코드를 작성할 때는, 해당 코드 자체가 원자적으로 실행되거나, 또는 원자성을 보장하는 다른 메커니즘(하드웨어 명령어 등)의 도움을 받아야 합니다. 그렇지 않으면 동기화 코드 자체에서 경쟁 상태가 발생할 수 있습니다!

---

3. 알고리즘을 통한 임계 구역 문제 해결 시도 (2개 프로세스 가정)

과거에는 소프트웨어적인 방법만으로 임계 구역 문제를 해결하려는 시도가 있었습니다. (주로 두 개의 프로세스 P₀, P₁ 간의 동기화를 가정)

알고리즘 1: '차례(Turn)' 변수 사용 방식

• 아이디어: 하나의 공유 변수 turn을 사용하여, 어느 프로세스가 임계 구역에 들어갈 차례인지를 명시적으로 지정합니다.
• 동기화 변수: int turn; (초기값: 0 또는 1)
• 코드 예시 (Pᵢ 기준, 상대는 Pⱼ):

• do {
      while (turn != i); // 내 차례(turn == i)가 될 때까지 기다린다 (Busy Waiting)
      // --- Critical Section ---
      critical_section();
      // --- Critical Section End ---
      turn = j; // 차례를 상대방(Pj)에게 넘긴다
      // Remainder Section
      remainder_section();
  } while (1);

• 평가: 상호 배제, 유한 대기는 만족하지만, 진행(Progress) 조건을 만족하지 못합니다. (엄격한 교대 방식의 한계)

알고리즘 2: '깃발(Flag)' 변수 사용 방식

• 아이디어: 각 프로세스가 임계 구역에 들어가고 싶다는 '의사'를 flag 변수를 통해 표시합니다.
• 동기화 변수: boolean flag[2]; (초기값: 모두 false)
• 코드 예시 (Pᵢ 기준, 상대는 Pⱼ):

• do {
      flag[i] = true;   // "나 임계 구역 들어가고 싶어!" 깃발을 든다
      while (flag[j]);  // 상대방도 깃발을 들고 있다면(들어가고 싶어하면) 기다린다 (Busy Waiting)
      // --- Critical Section ---
      critical_section();
      // --- Critical Section End ---
      flag[i] = false;  // "나 임계 구역 다 썼어!" 깃발을 내린다
      // Remainder Section
      remainder_section();
  } while (1);

• 평가: 상호 배제와 진행 조건을 만족하지 못합니다. (교착 상태 또는 동시 진입 가능성)

알고리즘 3: 피터슨 알고리즘 (Peterson's Algorithm)

• 아이디어: 알고리즘 1(Turn)과 알고리즘 2(Flag)의 아이디어를 결합하여 세 가지 조건을 모두 만족시킨 최초의 올바른 소프트웨어적 해결책입니다.
• 동기화 변수: boolean flag[2];, int turn;
• 코드 예시 (Pᵢ 기준, 상대는 Pⱼ):

• do {
      flag[i] = true;
      turn = j;
      while (flag[j] && turn == j); // 상대가 원하고, 내가 양보했으면 기다린다 (Busy Waiting)
      // --- Critical Section ---
      critical_section();
      // --- Critical Section End ---
      flag[i] = false;
      // Remainder Section
      remainder_section();
  } while (1);

• 평가: 상호 배제, 진행, 유한 대기를 모두 만족합니다. 하지만 여전히 바쁜 대기(Busy Waiting) 방식이라는 단점이 있습니다.

[Q&A]

• Q: "피터슨 알고리즘은 왜 턴(turn)과 플래그(flag)를 둘 다 사용하나요? 하나만 쓰면 안 되나요?"
• A: 알고리즘 1(Turn)은 진행(Progress) 문제를, 알고리즘 2(Flag)는 상호 배제와 진행 문제를 모두 가졌습니다. 피터슨 알고리즘은 이 둘을 절묘하게 조합합니다. flag로 진입 의사를 표시하고, turn으로 동시에 진입하려는 경우 누구에게 양보할지 결정합니다. while (flag[j] && turn == j) 조건 덕분에 세 가지 필수 조건을 모두 만족시킬 수 있게 됩니다.
• Q: "바쁜 대기(Busy Waiting)는 왜 CPU 자원 낭비인가요?"
• A: 프로세스가 while 루프를 계속 돌면서 조건을 확인하는 동안, CPU는 실질적으로 아무런 유용한 작업을 하지 못하고 계속 루프만 실행하게 됩니다. 이 시간에 CPU는 다른 유용한 작업을 처리할 수도 있었을 텐데 말이죠. 그래서 바쁜 대기는 특히 대기 시간이 길어질수록 비효율적인 방식입니다.

---

4. 하드웨어 기반 동기화: 원자적 연산의 힘

소프트웨어 방식의 한계(복잡성, 바쁜 대기, 성능 문제)를 극복하기 위해, 대부분의 현대 CPU는 동기화를 위한 특별한 하드웨어 명령어를 제공합니다. 이 명령어들은 원자적(Atomic)으로 실행되는 것이 보장됩니다.

Test-and-Set 명령어 활용

• 개념: 특정 메모리 위치의 값을 읽는 동시에(Test) 그 값을 무조건 true로 설정(Set)하는 원자적 명령어. 원래 값을 반환합니다.
• 동기화 변수: boolean lock = false; (초기값: false - 잠금 해제)
• 코드 예시 (임계 구역 진입/퇴출 부분):

• // Entry Section
  while (Test_and_Set(&lock)); // lock이 원래 false였다면 false 반환 -> 루프 탈출 (동시에 lock=true 됨)
                               // lock이 원래 true였다면 true 반환 -> 루프 계속 (Busy Waiting)
  // --- Critical Section ---
  critical_section();
  // --- Critical Section End ---
  
  // Exit Section
  lock = false; // 잠금 해제

• 평가: 상호 배제를 하드웨어적으로 보장하며 구현이 간단합니다. 하지만 여전히 바쁜 대기 방식이며, 유한 대기를 보장하지 못할 수 있습니다.

[Q&A]

• Q: "하드웨어 명령어는 어떻게 원자적 실행을 보장하나요?"
• A: CPU 내부적으로 명령어 실행 파이프라인을 제어하거나, 메모리 버스(Bus)를 잠그는 등의 메커니즘을 사용하여 해당 명령어 실행 동안 다른 CPU 코어나 장치가 동일한 메모리 위치에 접근하는 것을 막습니다. 이는 하드웨어 설계 수준에서 보장됩니다.
• Q: "Test-and-Set 방식은 유한 대기(Bounded Waiting)를 보장하지 못할 수 있다는데, 왜 그런가요?"
• A: lock이 풀리는 순간 여러 프로세스가 동시에 Test_and_Set을 시도할 경우, 어떤 프로세스가 성공할지는 운에 따라 결정될 수 있습니다. 특정 프로세스가 계속 경쟁에서 밀려 무한히 대기할 가능성(이론적으로)이 존재합니다.

---

5. 세마포어 (Semaphore) 소개: 더 나은 기다림을 향하여

지금까지 살펴본 소프트웨어적, 하드웨어적 해결책들은 모두 '바쁜 대기(Busy Waiting)'라는 공통적인 비효율성을 가지고 있었습니다. 즉, 기다리는 동안 CPU를 계속 소모하며 자원을 낭비했죠.

 

이러한 바쁜 대기 문제를 해결하고 동기화를 좀 더 추상적이고 편리하게 관리하기 위해 세마포어(Semaphore)라는 개념이 등장했습니다.

• 핵심 아이디어: 세마포어는 단순히 CPU를 돌며 기다리는 대신, 프로세스가 기다려야 할 때 스스로를 잠들게(Block/Sleep) 하고 CPU를 다른 프로세스에게 양보할 수 있는 메커니즘을 제공합니다. 나중에 다른 프로세스가 자원을 사용할 수 있게 되면, 잠들어 있던 프로세스를 깨워서(Wakeup) 다시 실행될 수 있도록 합니다.

세마포어는 정수 값을 가지는 변수와 P, V라는 두 개의 원자적 연산으로 구성됩니다. 이를 통해 개발자는 복잡한 저수준의 바쁜 대기 로직 대신, 더 높은 수준에서 동기화 문제를 해결할 수 있게 됩니다. 세마포어의 구체적인 동작 방식과 종류, 활용법에 대해서는 다음 글에서 자세히 다루겠습니다.

---

6. 추가: 데커 알고리즘 (Dekker's Algorithm)

• 피터슨 알고리즘 이전에 임계 구역 문제를 해결하기 위해 제안된 최초의 올바른 소프트웨어적 해결책 중 하나입니다. (두 프로세스 간)
• 세 가지 필수 조건을 모두 만족하지만, 역시 바쁜 대기(Busy Waiting)를 사용하며 로직이 다소 복잡하여 현재는 주로 이론적/교육적 중요성으로 언급됩니다.

---

[마무리하며]

 

임계 구역 문제는 동시성 프로그래밍의 가장 기본적인 도전 과제입니다. 이를 해결하기 위한 노력은 다양한 소프트웨어 알고리즘 시도(Turn, Flag, Peterson, Dekker)를 거쳐 하드웨어의 원자적 연산 지원(Test-and-Set 등)으로 이어졌습니다. 하지만 이들 방법은 '바쁜 대기'라는 한계를 가지고 있었습니다.

 

다음 글에서는 이 바쁜 대기 문제를 해결하고 보다 효율적인 동기화를 가능하게 하는 강력한 도구인 세마포어(Semaphore)에 대해 자세히 알아보겠습니다. 운영체제의 동기화 메커니즘을 이해하는 중요한 단계가 될 것입니다!