/ OS

OS(6) - Classical Synchronization Problems

OS 관련 포스팅

Producer-Consumer Problem

  • producer(생산자)가 data를 생산하면 consumer(소비자)가 소비
  • e.g.) compiler(= producer)와 assembler(= consumer)의 경우,
    compiler가 high level language를 low level language(assembly어)로 번역하면, assembler가 번역된 assembly어를 기계어로 번역
  • e.g.) 파일 서버(= producer)와 클라이언트(= consumer)의 경우,
    web browser가 요청을 보내면, server가 file안의 data를 처리해 응답하고, web brower가 web page형태로 보여줌
  • Bounded Buffer(유한 버퍼)
    → 생산한 데이터는 버퍼에 우선 저장함
    → buffer의 사이즈는 유한함
    → producer는 buffer가 가득 차면 더이상 데이터를 넣을 수 없으며,
    → consumer는 buffer가 비면 더이상 데이터를 뺄 수 없음
  • 같은 수의 생산(insert)과 소비(remove)가 이루어졌다면, 결괏값은 0이 나와야 함
  • common variable인 count와 buf[]를 업데이트하는 C.S.(critical-section)에 동시 진입이 이루어져 최종 결괏값으로 0이 나오지 않음
  • solution
    → mutual exclusion
    → semaphore를 이용해 동시접근 방지
    → number of permit = 1
  • Busy-wait
    → producer: buffer가 가득차면 기다려야하며,
    → consumer: buffer가 비면 기다려야 함
    → OS의 ‘효율성 증가’의 목적에 위배됨
    → semaphore를 사용해 busy-wait회피
    → 무한 loop(while문)를 돌며 기다리지않고 semaphore에 가둠
    → CPU 서비스를 받지 않고 block됨
    → 빈공간이 생기면 producer를 깨우고, 데이터가 들어오면 consumer를 깨움

Readers-Writers Problem

  • Reader: C.S.을 편집하지 않고 읽기만 함
  • Writer: C.S.를 읽고 편집함
  • Reader에 mutual exclusion을 적용하면 비효율적임
  • Reader가 들어왔는데 다른 Writer가 들어오려하면 block
  • Writer가 들어와 있으면 Reader는 block
  • Reader가 들어와 있는데 다른 Reader가 들어온다면 허용(효율성 제고)

Dining Philosopher Problem

  • 5명의 철학자와 5개의 젓가락이 서로 엇갈려 한 테이블에 존재
  • ‘생각 → 식사’의 반복
  • 왼쪽 젓가락을 든 뒤, 오른쪽 젓가락을 듬
  • number of permit = 1 : 두 철학자 중 한 명만 젓가락 드는 것이 허용됨
  • 결과: starvation: 모든 철학자들이 굶어 죽는 상황 발생
  • 모두가 동시에 젓가락을 드는 상황이 있으면 deadlock에 빠짐