[운영체제-양희재 교수님]13강 생산자-소비자 문제

경성대학교 양희재 교수님의 운영체제 13강

전통적 동기화 예제

• Producer and Consumer Problem(생산자-소비자 문제)
  • 유한 버퍼 문제(Bounded Buffer Problem)라고도 한다.
• Readers-Writers Problem
  • 공유 데이터베이스 접근에서 발생하는 문제
• Dining Philosopher Problem
  • 식사하는 철학자 문제

Producer-Consumer Problem

• 생산자-소비자 문제
  • 생산자가 데이터를 생산하면 소비자는 그것을 소비
  • 예) 컴파일러(어셈블리 코드 생산) → 어셈블러(어셈블리 코드 소비)
  • 예) 파일 서버(HTML 생산) → 클라이언트(HTML 소비)
• Bounded Buffer
  • 생산과 소비의 속도는 다르다 ⇒ 생산된 데이터는 버퍼에 저장
  • 현실 시스템에서 버퍼 크기는 유한(Bounded Buffer)
    • 생산자는 버퍼가 가득 차면 더 넣을 수 없다.
    • 소비자는 버퍼가 비면 뺄 수 없다.

첫 번째 문제

• 최종적으로 버퍼 내에는 0개의 항목이 있어야 하지만 잘못된 결과가 나온다.
  • 잘못된 결과
    • 실행이 불가한 경우
    • count ≠ 0(생산된 항목 숫자 ≠ 소비된 항목 숫자)인 경우

원인

• 공통변수 count, buf[]에 대한 동시 업데이트
• 공통변수 업데이트 구간(임계구역)에 대한 동시 진입

해결

• 임계구역에 대한 동시 접근 방지(상호배타)

  • 세마포를 사용한 상호배타(mutual exclusion)

      // mutual exclusion semaphore => mutex
      mutex.value = 1 // # of permit
    

      Producer             Consumer
            
      mutex.acquire()      mutex.acquire()
      Critical Section     Critical Section
      mutex.release()      mutex.release()
    

두 번째 문제

• Busy-wait
  • 생산자는 버퍼가 가득 차면 빈(empty) 공간이 나올 때까지 기다려야 한다.
  • 소비자는 버퍼가 비면 찬(full) 공간이 있을 때까지 기다려야 한다.
  • CPU는 아무 일도 하지 못한 채 기다려야 한다 ⇒ 낭비 ⇒ CPU 효율 감소

해결

• 세마포를 사용한 busy-wait 회피

  • 생산자 ⇒ 버퍼가 가득 차면 빈(empty) 공간이 나올 때까지 block 시킨다.

      empty.acquire() // # of permit = BUF_SIZE
    

      Producer             Consumer
            
      empty.acquire()
      mutex.acquire()      mutex.acquire()
      Critical Section     Critical Section
      mutex.release()      mutex.release()
                           empty.release()
    

  • 소비자 ⇒ 버퍼가 비면 찬(full) 공간이 있을 때까지 block 시킨다.

      full.acquire() // # of permit = 0, 처음에 소비할 수 있는 게 없기 때문
    

      Producer             Consumer
            
      empty.acquire()      full.acquire()
      mutex.acquire()      mutex.acquire()
      Critical Section     Critical Section
      mutex.release()      mutex.release()
      full.release()       empty.release()
    

Readers-Writers Problem

• 공통 데이터베이스에 접근하는 경우
  • Readers 프로세스: read data, never modify it
  • Writers 프로세스: read data and modifiy it
  • 한 번에 한 개의 프로세스만 데이터베이스에 접근(상호 배타) ⇒ 비효율적
• 효율성을 높이기 위해서는
  • Each read or write of the shared data must happen within a critical section
  • Guarantee mutual exclusion for writers
    • data를 modify 할 수 있기 때문에
  • Allow multiple readers to execute in the critical section at once
    • data를 modify 할 수 없기 때문에
• 변종
  • The first R/W problem(readers-preference)
    • Readers 프로세스가 우선권을 갖는다.
  • The second R/W problem(writers-preference)
    • Writers 프로세스가 우선권을 갖는다.
  • The Third R/W problem
    • 우선권을 가진 프로세스가 없다.

Dining Philosopher Problem

• 식사하는 철학자 문제
  • 상황) 5명의 철학자와 5개의 젓가락 존재
  • 철학자의 행동 패턴) 생각 → 식사 → 생각 → 식사 → …
  • 조건) 식사하려면 양옆의 2개의 젓가락 필요
• 프로그래밍에 적용한다면
  • 젓가락 ⇒ 세마포 (# of permit = 1, 젓가락은 한 명만 들 수 있기 때문)
  • 젓가락과 세마포에 일련번호(0 ~ 4) 부여
  • 왼쪽 젓가락 → 오른쪽 젓가락 순으로 acquire
• 잘못된 결과 발생
  • 모든 철학자가 왼쪽 젓가락을 들고 오른쪽 젓가락을 기다리는 상황이 발생하면 식사를 할 수 없게 된다.
  • 모든 철학자가 식사하지 못해 굶어 죽는 상황 ⇒ starvation
• 원인
  • 교착 상태(deadlock)