수면 이발사 문제

Sleeping barber problem

컴퓨터 과학에서, 수면 이발사 문제는 여러 운영 체제 프로세스가 있을 때 발생하는 복잡성을 보여주는 고전적인 프로세스 간 통신과 동기화 문제다.[1]

이 문제는 원래 1965년 컴퓨터 과학의 선구자인 에드제르 디크스트라에 의해 제안되었는데,[2] 그는 이 문제를 일반 세마포어가 종종 불필요하다는 점을 지적하기 위해 사용했다.[3]

문제명세서

이발사 1명, 이발사 의자 1명, 의자가 n개인 대기실(n은 0일 수도 있음)이 있는 가상의 이발소를 상상해보자. 다음과 같은 규칙이 적용된다.[4]

  • 손님이 없으면 이발사는 의자에서 잠이 든다.
  • 손님은 이발사가 잠들면 반드시 깨워야 한다.
  • 이발사가 일하고 있는 동안 손님이 도착하면, 의자가 모두 차면 손님이 떠나고, 자리가 나면 빈 의자에 앉는다.
  • 이발사는 이발을 마치면 대기실을 점검해 대기하는 손님이 있는지 확인하고, 없으면[3][5] 잠이 든다.

두 가지 주요 합병증이 있다. 첫째, 대기실 점검, 매장 출입, 대기실 의자 챙기기 등 모든 행동이 일정 시간이 걸리기 때문에 고객이 이발사를 기다리는 동안 이발사가 잠을 자는 경마 조건이 발생할 위험이 있다. 구체적으로는 머리를 깎는 이발사를 찾기 위해 고객이 도착하여 대기실로 돌아와 자리에 앉지만, 다시 대기실로 걸어가는 동안 이발사는 이발을 끝내고 대기실로 가는데, 이발사는 (손님이 천천히 걷거나 화장실에 갔기 때문에) 비어 있는 것을 발견하여 이발소에서 잠을 잔다. 둘째, 대기실에 빈자리가 하나뿐이고 둘 다 하나의 의자에 앉으려 할 때 두 고객이 동시에 도착할 때 또 다른 문제가 발생할 수 있다. 의자에 처음 도착한 사람만 앉을 수 있게 된다.[citation needed]

다중 수면 이발기 문제는 대기 중인 고객들 사이에서 여러 이발기를 조정하는 복잡성을 더한다.[6]

해결 방법

몇 가지 가능한 해결책이 있지만, 모든 해결책에는 뮤텍스(mutex)가 필요하므로 참가자 중 한 명만 한 번에 상태를 변경할 수 있다. 이발사는 투숙객을 확인하기 전에 객실 상태 뮤텍스를 취득하고 그들이 잠을 자거나 머리를 자르기 시작할 때 방 상태를 해제해야 한다. 고객은 입장하기 전에 방 상태를 파악하여 대기실이나 이발소에 앉으면 방출을 해야 하며, 또한 좌석이 없어 퇴실할 때에도 방 상태를 유지해야 한다. 이것은 위에서 언급한 두 가지 문제를 모두 해결할 것이다. 시스템의 상태를 나타내기 위해서도 여러 세마포어가 필요하다. 예를 들어 대기실에 인원수를 저장할 수도 있다.

실행

다음의 가성소드는 이발사와 고객 사이의 동기화를 보장하고 교착상태는 없지만, 고객의 기아로 이어질 수 있다. 기아 문제는 선입선출(FIFO) 큐로 해결할 수 있다. 세마포어는 두 가지 기능을 제공한다. wait() 그리고 signal()C 코드의 관점에서 보면, P() 그리고 V()각각,[citation needed] 

# 처음 두 개는 뮤텍스(가능한 0 또는 1개만) 세마포레 바버레디 = 0 세마포레 accessWRSeats = 1     # 1인 경우 대기실 좌석 수 증가 또는 감소 가능 세마포레 커스터레디 = 0         # 현재 대기실에 대기 중인 고객 수, 서비스 준비 완료 인트로 FreeWRSeats 수 = N     # 대기실 전체 좌석 수  반항하다 이발사():   하는 동안에 진실의:                   # 무한순환로 달린다.     기다리다(커스터레디)             # 고객을 확보하려고 노력하라 - 만약 이용 가능한 것이 없다면, 잠을 자라.     기다리다(accessWRSeats)         # 깨어 있음 - 사용 가능한 좌석 수를 수정하기 위해 접근하고, 그렇지 않으면 잠을 자십시오.     FreeWRSeats 수 += 1    # 대기실 의자 하나가 자유로워진다.     신호를 보내다(바버레디)         ♪ 난 자를 준비가 됐어     신호를 보내다(accessWRSeats)       ♪ 의자의 자물쇠는 더 이상 필요 없어.     # (여기서 머리를 자른다.)  반항하다 고객():   하는 동안에 진실의:                   # 무한 루프에서 실행되어 여러 고객을 시뮬레이션하십시오.     기다리다(accessWRSeats)         # 대기실 의자에 접근하도록 해     만일 FreeWRSeats 수 > 0: # 무료 좌석이 있는 경우:       FreeWRSeats 수 -= 1  # 의자에 앉다       신호를 보내다(커스터레디)         # 손님이 올 때까지 기다리는 이발사에게 알린다.       신호를 보내다(accessWRSeats)     ♪ 의자를 더 이상 잠그지 않아도 돼       기다리다(바버레디)         # 이발사가 준비될 때까지 기다리다       # (여기서 머리를 자른다.)     다른:                       # 그렇지 않으면, 무료 좌석이 없고, 운도 좋지 않다.       신호를 보내다(accessWRSeats)     # 하지만 좌석의 자물쇠를 푸는 것 잊지 마!       # (머리 자르지 말고 나가라.)

참고 항목

참조

  1. ^ John H. Reynolds (December 2002). "Linda Arouses a Sleeping Barber" (PDF). Proceedings of the Winter Simulation Conference. San Diego, CA: IEEE. doi:10.1109/WSC.2002.1166471. Retrieved 8 January 2022.
  2. ^ Allen B. Downey (2016). The Little Book of Semaphores (PDF) (2.2.1 ed.). Green Tea Press. p. 121. Retrieved 8 January 2022.
  3. ^ a b Edsger W. Dijkstra (1965). Technical Report EWD-123: Cooperating Sequential Processes. Eindhoven, The Netherlands: Eindhoven University of Technology. p. 38. Retrieved 8 January 2022.
  4. ^ Andrew S. Tanenbaum (2001). Modern Operating Systems (PDF) (2nd ed.). Upper Saddle River, NJ: Pearson. p. 129. ISBN 9780130313584. Retrieved 8 January 2022.
  5. ^ E.W.에 의한 협력 순차적 프로세스 디크스트라 기술 보고서 EWD-123, 1965, 아인트호벤 공과대학, 네덜란드.
  6. ^ Fukuda, Munehiro. "Program 2: The Sleeping-Barbers Problem" (PDF). University of Washington. Retrieved 8 January 2022.