잠자는 이발사 문제

컴퓨터 과학에서 잠자는 이발사 문제(sleeping barber problem)는 운영체제의 프로세스 간 통신과 그들의 동기화 문제를 다루는 고전적인 문제이다.

문제

이 문제는 이발사가 손님이 있을 때는 일하고 없을 때는 쉬는 것을 반복하는 일련의 과정을 비유로 들었다. 이발소에 이발사 한 명이 있다고 해 보자. 이 이발소에는 이발용 의자 하나가 있고, 대기실에는 많은 의자들이 있다. 이발사가 손님 한명의 머리를 다 깎고 나면, 손님을 보내고 다른 기다리는 손님이 있는지 확인하러 대기실로 간다. 만약 대기실에 손님이 있으면 이발용 의자로 데려와 머리를 깎는다. 대기실에 아무도 없으면 이발사는 자기 의자에 앉아서 잔다.

모든 손님은 이발소에 도착하면 이발사가 무엇을 하고 있는지 확인한다. 만약 자고 있으면 이발사를 깨우고 이발용 의자에 앉는다. 다른 사람을 이발하고 있으면 대기실로 간다. 대기실에 빈 의자가 있으면 거기에 앉고, 없으면 이발소를 떠난다. 단순하게 분석하면, 위 사례에서 더 이상 손님이 없으면 도착하는 모든 손님의 머리를 깎아주고, 다음 손님이 오기 전까지만 자는 이발사를 이용해 이발소가 제대로 운영되도록 해야 한다. 실제로, 위 사례에서 일반적인 스케줄링 (scheduling) 문제를 묘사할 수 있는 여러 가지 문제가 나타날 수 있다.

모든 문제들은 이발사와 손님들의 행동 시간 (대기실 확인하기, 이발사의 상태보기, 대기실 의자에 앉기 등의 시간)이 분명하지 않다는 것과 엮여 있다. 예를 들어, 손님이 이발소에 도착해서 이발사가 머리를 깎고 있으면 대기실로 간다. 그 손님이 대기실로 가고 있는 동안, 이발사가 머리를 다 깎고, 대기실을 확인한다. 손님이 아직 대기실에 도착하지 않아 그 곳에 아무도 없으면, 자기 자리로 돌아가 자 버린다. 이발사는 이제 다음 손님을 기다리고, 손님은 이발사를 기다리게 된다. 다른 예로, 대기실에 의자가 하나 남아 있을 때 두 손님이 동시에 이발소에 도착하는 경우가 있을 것이다. 이발사가 머리를 깎는 것을 보고 두 손님은 대기실로 가서 둘 다 하나 남은 의자를 차지하려고 한다. 잠자는 이발사 문제는 컴퓨터 과학의 선구자 중 한 사람인 에츠허르 데이크스트라가 만들었다고 보통 여겨져 왔다 (1965).

해법

이 문제에는 많은 솔루션이 적용 가능하다. 모든 핵심은 뮤텍스에 있는데, 한 번에 한 명만이 자신의 동작상태를 바꿀 수 있게 하는 것이다. 이 이발사는 뮤텍스를 반드시 얻은 후 대기실에 손님을 확인할 수 있고, 다시 잠을 자든지 머리를 깎을 때 뮤텍스를 다시 반납해야 한다. 손님은 뮤텍스를 반드시 얻은 후에 이발소에 들어갈 수 있고, 대기실 의자에 앉거나 이발용 의자에 앉을 때 뮤텍스를 반납해야 한다. 물론 대기실에 자리가 없어서 이발소를 떠날 때도 반납해야 한다. 이렇게 위에서 언급한 두가지 문제점을 모두 해결할 수 있다. 많은 세마포어 역시 시스템의 상태를 알려주기 위해 필요하다. 예를 들어, 한 이발소의 대기실에 많은 수의 사람들을 모아 둘 경우가 있기 때문이다. 대기 손님들과 여러명의 이발사를 다루는 복수의 잠자는 이발사 문제는 추가적인 복잡성을 가지고 있다.

구현

다음의 의사코드는 이발사와 손님의 동기화를 보장하고 교착상태가 일어나지 않는다. 하지만 손님의 기아상태가 발생할 수 있다. 기아상태의 문제는 손님이 이발소에 도착하여 그 수가 늘어날 때 큐를 이용하여 해결할 수 있다. 그리하여 이발사는 선착순 (선입 선출)으로 이발을 해줄 수 있다. 함수 wait() 와 signal() 은 세마포어로 제공되는 함수이다. c-code 표기법에서, wait()는 P() 이고, signal() 은 V()이다.

# 처음 두 변수는 mutex 임. (0과 1만 가능)
Semaphore barberReady = 0
Semaphore accessWRSeats = 1 # 1이 되면 남은 대기실 의자가 늘어났거나 줄어듬.
Semaphore custReady = 0 # 현재 대기실에서 이발을 기다리는 손님들의 수
int numberOfFreeWRSeats = N # 빈 대기실 의자의 개수

def Barber():
  while true:                   # 무한 루프의 시작
    wait(custReady)             # 대기실의 손님 확인 – 아무도 없으면 잠.
    wait(accessWRSeats)         # 기상 – 빈 대기실 의자 개수를 바꾸려 함, 안되면 잠.
    numberOfFreeWRSeats += 1    # 손님을 부름. 대기실의 빈 의자 하나가 늘어남.
    signal(barberReady)         # 이발사가 이발할 준비가 끝남.
    signal(accessWRSeats)       # 빈 대기실 의자 수에 대한 록(lock)이 필요없음.

    # (이발을 한다.)

def Customer():
    wait(accessWRSeats)         # 빈 대기실 의자 개수를 바꾸려 함.
    if numberOfFreeWRSeats > 0: # 만약 빈 자리가 있으면:
      numberOfFreeWRSeats -= 1  # 빈 자리에 앉는다. 빈 자리가 하나 없어짐.
      signal(custReady)         # 기다리는 사람이 있다고 이발사에게 말한다.
      signal(accessWRSeats)     # 빈 대기실 의자 수에 대한 록(lock)이 필요 없음
      wait(barberReady)         # 이발사가 준비될 때까지 기다린다.

      # (이발을 받는다.)

    else:                       # 그렇지 않고 자리가 없으면; 운이 없네…
      signal(accessWRSeats)     # 대기실 빈 의자 수에 대한 록(lock)은 반납!

      # (이발을 받지 못하고, 이발소를 떠난다.)

같이 보기

• 식사하는 철학자들 문제

참고 문헌

• 앤드루 타넨바움, Modern Operating Systems (2nd Edition) (ISBN 0-13-031358-0)
• The Little Book of Semaphores by Allen B. Downey, http://greenteapress.com/semaphores
• Cooperating sequential processes by E.W. Dijkstra. Technical Report EWD-123, 1965, Eindhoven University of Technology, The Netherlands.