운영체제: 프로세스 동기화 - 세마포어 (Semaphore)

지난 글에서는 임계 구역 문제와 이를 해결하기 위한 고전적인 알고리즘들(피터슨 알고리즘 등) 및 하드웨어 기반의 해결책(Test-and-Set)에 대해 알아보았습니다. 하지만 이들 방법은 대부분 바쁜 대기(Busy Waiting), 즉 기다리는 동안 CPU 자원을 낭비하는 문제를 안고 있었습니다.

 

이번 글에서는 이러한 바쁜 대기 문제를 해결하고 동기화를 보다 추상적이고 효율적으로 관리할 수 있게 해주는 강력한 도구, 세마포어(Semaphore)에 대해 자세히 알아보겠습니다. 세마포어는 운영체제 동기화 메커니즘의 핵심 개념 중 하나입니다.

 

 

반효경 [운영체제] 13. Process Synchronization 2

 

---

1. 세마포어 (Semaphores)란? - 동기화 문제의 추상화

세마포어는 앞서 살펴본 복잡하고 저수준의 동기화 방식들을 추상화하여 프로그래머가 더 쉽게 동기화 문제를 다룰 수 있도록 고안된 도구입니다. 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger Dijkstra)가 제안했습니다.

• 정의: 세마포어 S는 다음과 같이 구성된 추상 자료형(Abstract Data Type)입니다.
  1. 정수 변수 (Integer Variable): 세마포어의 현재 상태 또는 사용 가능한 자원의 개수를 나타내는 정수 값.
  2. 두 개의 원자적 연산 (Atomic Operations): 이 정수 변수에 접근하고 조작하는 유일한 방법은 아래 두 가지 원자적 연산뿐입니다. (원자성은 하드웨어나 커널 수준에서 보장되어야 합니다.)
     • P(S) 또는 wait(S): 자원을 획득하거나, 사용 가능할 때까지 기다리는 연산. (Proberen - '테스트하다'의 네덜란드어)
     • V(S) 또는 signal(S) 또는 post(S): 사용이 끝난 자원을 반납하거나, 대기 중인 다른 프로세스에게 자원이 사용 가능함을 알리는 연산. (Verhogen - '증가시키다'의 네덜란드어)
• 원자성(Atomicity)의 중요성: P와 V 연산 자체가 원자적으로 실행되어야 합니다. 즉, 연산이 실행되는 도중에 다른 프로세스가 끼어들어 세마포어 값을 동시에 변경하는 일이 없어야 합니다. 그렇지 않으면 세마포어 자체에서 경쟁 상태가 발생하여 동기화 메커니즘이 깨지게 됩니다.

초기 (바쁜 대기) 세마포어 정의

세마포어의 개념을 처음 설명할 때는 이해를 돕기 위해 다음과 같이 바쁜 대기(Busy-Wait) 방식으로 P 연산을 정의하기도 합니다.

• P(S):

• while (S <= 0) do no-op; // S가 0보다 클 때까지 (자원이 있을 때까지) 계속 확인하며 기다린다 (Busy Waiting)
  S--; // 자원이 있으면 S 값을 1 감소시키고 임계 구역 등으로 진입한다 (자원 획득)

• V(S):

• S++; // 자원 사용이 끝나면 S 값을 1 증가시킨다 (자원 반납)

• 문제점: 이 정의는 여전히 while 루프를 돌며 CPU를 낭비하는 바쁜 대기(Busy Waiting) 문제를 가지고 있습니다. 이를 스핀락(Spin Lock)이라고도 부릅니다. 실제 효율적인 구현에서는 이 방식을 개선합니다.

[Q&A]

• Q: "P와 V라는 이름은 왜 사용하는 건가요? wait와 signal이 더 직관적이지 않나요?"
• A: P(Proberen)와 V(Verhogen)는 세마포어를 처음 제안한 다익스트라가 사용한 네덜란드어 용어입니다. 역사적인 이유로 P/V 연산이라는 이름이 널리 사용되고 있습니다. 현대에는 wait()/signal() 또는 acquire()/release() 등 더 직관적인 이름을 사용하기도 하지만, OS 교재나 문헌에서는 여전히 P/V가 자주 등장하므로 알아두는 것이 좋습니다.
• Q: "세마포어 연산은 왜 반드시 원자적이어야 하나요?"
• A: 만약 P 연산(while 검사와 S--)이나 V 연산(S++)이 원자적이지 않다면, 여러 프로세스가 동시에 이 연산들을 수행하는 도중에 끼어들 수 있습니다. 예를 들어, 두 프로세스가 동시에 S > 0임을 확인하고 둘 다 S--를 실행하면, 실제로는 자원이 하나인데 두 프로세스가 모두 자원을 획득하는 결과(상호 배제 실패)가 발생할 수 있습니다. 따라서 연산 자체의 원자성 보장은 세마포어가 올바르게 동작하기 위한 필수 조건입니다.

---

2. 세마포어를 이용한 임계 구역 문제 해결

세마포어를 사용하면 n개의 프로세스가 있는 환경에서도 임계 구역 문제를 간단하게 해결할 수 있습니다. 이때는 주로 값이 0 또는 1만 가지는 이진 세마포어(Binary Semaphore)를 사용하며, 이를 뮤텍스(Mutex - MUTual EXclusion)라고 부르기도 합니다.

• 동기화 변수:

• semaphore mutex = 1; // 세마포어 변수 mutex 선언 및 초기화.
                 	  	// 초기값 1은 현재 임계 구역에 아무도 없으며, 1개의 프로세스가 진입 가능하다는 의미.

• 프로세스 Pᵢ의 구조:

• do {
      P(mutex); // 임계 구역 진입 전 lock 획득 시도
                // 만약 mutex > 0 이면, mutex를 0으로 만들고 진입 (lock 성공)
                // 만약 mutex <= 0 이면, 다른 프로세스가 사용 중이므로 대기
  
      // --- Critical Section ---
      critical_section();
      // --- Critical Section End ---
  
      V(mutex); // 임계 구역 작업 완료 후 lock 해제
                // mutex를 1 증가시킴 (이제 mutex는 1).
                // 만약 대기 중인 프로세스가 있었다면 그 중 하나를 깨움.
  
      // Remainder Section
      remainder_section();
  } while (1);

• 동작:
  • 어떤 프로세스가 임계 구역에 들어가려면 먼저 P(mutex)를 호출합니다. mutex가 1이면 0으로 만들고 진입합니다.
  • 다른 프로세스가 P(mutex)를 호출하면 mutex가 0이므로 대기하게 됩니다(초기 정의에서는 busy-wait).
  • 임계 구역을 나온 프로세스는 V(mutex)를 호출하여 mutex를 다시 1로 만듭니다.
  • 이제 대기하던 다른 프로세스가 P(mutex)를 통과하여 임계 구역에 진입할 수 있게 됩니다.
  • 이를 통해 상호 배제(Mutual Exclusion) 조건이 만족됩니다.

---

3. 바쁜 대기 극복: Block/Wakeup 방식의 세마포어 구현

앞서 언급했듯이, 초기 정의의 세마포어는 여전히 바쁜 대기(Spin Lock) 문제를 안고 있습니다. 이는 CPU 자원 낭비입니다. 대부분의 현대 운영체제는 Block & Wakeup 방식을 사용하여 세마포어를 구현합니다. 이를 Sleep Lock이라고 부르기도 합니다.

• 아이디어: 프로세스가 P 연산에서 기다려야 할 때, CPU를 계속 돌면서 확인하는 대신, 프로세스 자신을 대기 상태(Blocked/Waiting)로 만들고 CPU를 양보합니다. 나중에 다른 프로세스가 V 연산을 수행하여 자원이 사용 가능해지면, 대기 중인 프로세스 중 하나를 깨워서(Wakeup) 다시 실행될 수 있도록 합니다.
• 구현을 위한 자료구조:
  • 세마포어를 단순한 정수 변수가 아닌, 구조체로 정의합니다.

  • typedef struct {
        int value;          // 세마포어 값 (자원의 개수 또는 상태)
        struct process *L;  // 해당 세마포어를 기다리는 프로세스들의 연결 리스트 (대기 큐)
    } semaphore;

• 커널 지원 함수 (가정):
  • block(): 현재 실행 중인 프로세스를 대기 상태로 전환하고, 해당 세마포어의 대기 큐(S.L)에 추가한 후, CPU 스케줄러를 호출하여 다른 프로세스에게 CPU를 넘깁니다.
  • wakeup(P): 대기 상태에 있는 프로세스 P를 준비 상태(Ready)로 전환하여, 준비 큐(Ready Queue)로 옮겨 다시 CPU를 얻을 기회를 갖도록 합니다.
• Block/Wakeup 방식의 P() 및 V() 연산:

• P(S): // 자원 획득 시도 또는 대기
      S.value--; // 일단 자원 수를 감소시킨다. (음수 가능!)
      if (S.value < 0) { // 감소시킨 결과가 음수인가? (즉, 자원이 없었는가?)
          // 현재 프로세스를 세마포어 S의 대기 큐(S.L)에 추가한다.
          add this process to S.L;
          block(); // 자신을 대기 상태로 만들고 CPU를 양보한다.
      }
      // S.value >= 0 이면 그냥 통과 (자원 획득 성공)
  
  V(S): // 자원 반납 또는 대기 프로세스 깨우기
      S.value++; // 자원 수를 증가시킨다.
      if (S.value <= 0) { // 증가시킨 결과가 0 이하인가? (즉, 증가시키기 전에 음수였는가? -> 누군가 기다리고 있었는가?)
          // 세마포어 S의 대기 큐(S.L)에서 기다리던 프로세스 P 하나를 제거한다.
          remove a process P from S.L;
          wakeup(P); // 제거한 프로세스 P를 깨워서 준비 큐로 보낸다.
      }
      // S.value > 0 이면 아무도 기다리지 않으므로 그냥 값만 증가시키고 끝낸다.

• 핵심 변화: P 연산에서 더 이상 while 루프를 돌지 않습니다. 기다려야 하면 block()을 통해 CPU를 양보하고 잠듭니다. V 연산은 단순히 값을 증가시키는 것 외에, 누군가 잠들어 있었다면(S.value <= 0) 깨우는 역할까지 수행합니다. S.value의 절댓값은 이제 해당 세마포어를 기다리는 프로세스의 수를 의미하게 됩니다.

[Q&A]

• Q: "Block/Wakeup 방식에서 세마포어 값(S.value)이 음수가 될 수 있는 이유는 무엇인가요?"
• A: P 연산은 먼저 S.value를 감소시킨 후 조건을 검사합니다. 만약 S.value가 0일 때 P 연산이 호출되면, 값은 -1이 되고 해당 프로세스는 block됩니다. 또 다른 프로세스가 P 연산을 호출하면 값은 -2가 되고 그 프로세스도 block됩니다. 즉, S.value의 절댓값은 현재 해당 세마포어의 대기 큐에서 기다리고 있는 프로세스의 수를 나타내게 됩니다. V 연산은 이 음수 값을 보고 깨워야 할 프로세스가 있는지 판단합니다.
• Q: "Block/Wakeup 방식은 바쁜 대기보다 항상 더 좋은가요?"
• A: 일반적으로는 그렇습니다. CPU 자원을 낭비하지 않기 때문입니다. 하지만 Block/Wakeup 과정 자체에도 오버헤드가 있습니다. 프로세스 상태 변경, PCB를 큐에 넣고 빼는 작업, 문맥 교환 등 커널 레벨의 작업이 필요합니다. 만약 임계 구역의 길이가 매우 짧아서 대기 시간이 거의 없을 것으로 예상된다면, 차라리 짧은 시간 동안 Busy-Wait(Spin Lock)하는 것이 Block/Wakeup 오버헤드보다 더 효율적일 수도 있습니다. (특히 멀티코어 환경에서는 다른 코어에서 lock이 금방 풀릴 것을 기대하며 잠시 스핀하는 것이 유리할 수 있습니다.) 하지만 대부분의 경우 Block/Wakeup 방식이 더 선호됩니다.

---

4. 세마포어의 종류

세마포어는 value 변수가 가질 수 있는 값의 범위에 따라 두 가지 종류로 나뉩니다.

1. 카운팅 세마포어 (Counting Semaphore):
   • value가 0 이상의 임의의 정수 값을 가질 수 있습니다.
   • 주로 사용 가능한 자원의 개수를 나타내는 데 사용됩니다. 예를 들어, 프린터가 3대 있다면 세마포어 초기값을 3으로 설정하고, 프린터를 사용할 때마다 P 연산, 사용 후 반납할 때 V 연산을 수행하여 동시에 최대 3개의 프로세스만 프린터를 사용하도록 제어할 수 있습니다.
2. 이진 세마포어 (Binary Semaphore):
   • value가 0 또는 1의 값만 가질 수 있습니다.
   • 오직 하나의 프로세스만 특정 자원에 접근하도록 보장하는 상호 배제(Mutual Exclusion) 목적으로 주로 사용됩니다. 동작 방식이 잠금(Lock) 메커니즘과 매우 유사하여 뮤텍스(Mutex)라고도 불립니다. (단, 엄밀히 말하면 뮤텍스는 소유권 개념 등 세마포어와 약간의 차이가 있을 수 있습니다.) 위에서 임계 구역 문제를 해결한 예시가 바로 이진 세마포어를 사용한 경우입니다.

---

5. 세마포어 사용 시 주의점: 교착 상태와 기아

세마포어는 강력한 동기화 도구이지만, 잘못 사용하면 심각한 문제를 일으킬 수 있습니다.

• 교착 상태 (Deadlock):
  • 정의: 둘 이상의 프로세스가, 각자 자신이 가진 자원을 놓지 않으면서 상대방이 가지고 있는 자원을 얻기 위해 서로를 무한정 기다리는 상태입니다. 시스템 전체가 멈출 수 있습니다.
  • 세마포어 사용 예시: 두 개의 세마포어 S와 Q가 있고, 초기값은 모두 1이라고 가정합니다.
    • 프로세스 P0: P(S); P(Q); ... V(Q); V(S); 순서로 실행
    • 프로세스 P1: P(Q); P(S); ... V(S); V(Q); 순서로 실행
    • 발생 시나리오:
      1. P0가 P(S) 실행 (S=0).
      2. P1가 P(Q) 실행 (Q=0).
      3. P0가 P(Q) 실행 시도 → Q=0이므로 대기.
      4. P1가 P(S) 실행 시도 → S=0이므로 대기.
    • 결과: P0는 Q를 기다리고, P1은 S를 기다리는데, 서로가 원하는 자원을 상대방이 점유한 채 놓지 않으므로 영원히 대기하는 교착 상태에 빠집니다.
  • 해결책 (단순 예): 모든 프로세스가 세마포어(자원)를 항상 동일한 순서로 획득하도록 규칙을 정하면 교착 상태를 예방할 수 있습니다. (예: 무조건 S → Q 순서로 획득)
• 기아 상태 (Starvation) 또는 무한 봉쇄 (Indefinite Blocking):
  • 정의: 특정 프로세스가 자원을 얻기 위해 기다리고 있는데, 다른 프로세스들에게 계속 순서가 밀려 영원히 자원을 얻지 못하고 기다리게 되는 상태입니다. (교착 상태는 아니지만 심각한 문제입니다.)
  • 세마포어 관련 원인: 세마포어의 대기 큐(S.L)에서 프로세스를 깨울 때, 어떤 순서(정책)로 깨우느냐에 따라 발생할 수 있습니다. 예를 들어, 큐가 LIFO(Last-In, First-Out) 방식으로 관리된다면 나중에 들어온 프로세스가 먼저 처리되어 먼저 들어온 프로세스는 계속 기다릴 수 있습니다. (일반적으로는 FIFO - 즉, 공정한 큐 관리 정책을 사용합니다.)
  • (고전적인 예시) 철학자들의 식사 문제(Dining Philosophers Problem)는 교착 상태와 기아 상태가 발생할 수 있는 대표적인 동기화 문제입니다.

[Q&A]

• Q: "뮤텍스(Mutex)와 이진 세마포어는 같은 건가요?"
• A: 매우 유사하며 많은 경우 혼용되어 사용되지만, 엄밀하게는 차이가 있을 수 있습니다. 가장 큰 차이는 소유권(Ownership) 개념입니다. 뮤텍스는 일반적으로 lock을 획득한 스레드만이 해당 lock을 해제(unlock)할 수 있습니다. 반면, 이진 세마포어는 P 연산으로 값을 0으로 만든 스레드가 아니더라도 다른 스레드가 V 연산을 통해 값을 1로 만들 수 있습니다. 하지만 기본적인 상호 배제 기능은 동일하게 수행합니다.
• Q: "교착 상태(Deadlock)와 기아 상태(Starvation)는 어떻게 다른가요?"
• A: 교착 상태는 여러 프로세스가 서로가 가진 자원을 기다리며 모두 멈춰버린 상태입니다. 외부 개입 없이는 절대 진행될 수 없습니다. 기아 상태는 특정 프로세스가 자원을 얻을 기회를 계속 놓쳐 영원히 기다리는 상태입니다. 다른 프로세스들은 정상적으로 실행될 수 있지만, 굶주리는 프로세스만 계속 대기합니다. 교착 상태는 기아 상태를 유발할 수 있지만, 기아 상태가 반드시 교착 상태를 의미하는 것은 아닙니다.

---

[마무리하며]

세마포어는 임계 구역 문제 해결을 위한 고전적이면서도 강력한 동기화 도구입니다. 바쁜 대기 문제를 해결하는 Block/Wakeup 메커니즘을 통해 CPU 효율성을 높였으며, 카운팅/이진 세마포어를 통해 다양한 동기화 시나리오에 적용될 수 있습니다.

 

하지만 세마포어 사용 시 발생할 수 있는 교착 상태나 기아 상태와 같은 문제점들을 항상 염두에 두고 신중하게 사용해야 합니다. 다음 단계에서는 세마포어를 활용한 고전적인 동기화 문제 해결 예시와, 세마포어보다 더 고수준의 동기화 도구들(모니터 등)에 대해 알아볼 것입니다.