[OS] Synchronization Examples

Classic Problems of Synchronization

Bounded-Buffer Problem

• Producer-Consumer Problem
  • C기준 wait, signal의 대칭 구조가 맞아야한다.
  • 
• Pthread로 해결하기
  • 뮤텍스로 P-C모델을 구현한다
  • 세마포어로 버퍼를 관리한다.
    • sem_wait → 세마포어를 1개 감소시킨다. 여기에서 empty가 0이라면 1개가 증가할 때 까지 대기한다.
    • sem_post → 세마포어를 하나 증가시킨다.
    
  • empty, full의 세마포어로 버퍼 안에 여러개 쓸 수 있도록해주고 버퍼를 고칠 때는 mutex lock으로 상호배제가 되도록 하고있다.
• 세마포어의 wait, signal
  → 자바의 모니터락을 이용한 wait, notify

Readers-Writers Problem

• first Readers-Writers Problem
  • Reader 끼리는 Write의 참여만 상관없으면 동시에 접근해도 상관이 없다.
  • read의 개수가 많다면 계속 들어오게되고 writer가 접근못하는starvation 문제발생
  • read_count 변수를 생성 → 해당 변수가 0이되면 writer가 쓰자
  • rw_mutex → reader, writer 공유해서 쓴다.
  • mutex → read_counter할 때 상호배제보장
  • reader writer 동등한 기회를 제공하면 첫번째 문제, writer우선이면 두번째 problem이다.
  • 
• second Readers-Writers Problem
  • writer가 쓰기 위해서 기다리면, reader들은 더 이상 진입하지 못한다.
  • writer가 엄청 많으면 read가 못 읽는 경우가 생긴다 → starvation 문제발생

Dining-Philosophers Problem(철학자들의 저녁식사)

• 여러개의 리소스와 프로세스 환경
• 각 젓가락마다 세마포어 솔루션 적용 했을 때
  • 상호배제는 보장하지만, 젓가락이 모자라 데드락과 기아문제 발생
  • 해결법
    • 철학자들의 숫자를 줄이기
    • 홀짝으로 철학자들을 분류해서 서로 반댓손으로 쥐게 한다 → 가운데 젓가락이 비기 떄문에 상호배제를 보장하면서 둘이 순서를 지키면서 먹고 처음에 쥐었던 젓가락을 놔주게된다.
    • 데드락은 해결했지만, 기아 문제는 해결 못했다.
      • 기아 문제 방지하는 비용이 너무 비싸다, 발생했을 때 처리하는 것이 훨씬 효율적이다
• 동기화 도구 모니터를 이용한 해결법

Use Monitor

• 양 쪽 젓가락이 이용 가능할 때만 젓가락을 들자
• 철학자가 thinking, eating, hungry 상태로 변환이 되는데, 양쪽이 eating 상태면 안된다.
• condition variable
  • hungry 상태일 때 대기를하고, 식사 후에는 signal을 준다.
• 두 가지 operation 사용
  • pickup(), putdown()
• 하지만 기아 문제는 해결 못했다.

Alternative Approaches

---

• Thread-Safe Concurrent Applications*
• 멀티코어시스템에서 concurrent하게 잘 동작하는 어플리케이션을 말한다.
  • 이를 위해 뮤텍스 락, 세마포어, 모니터 등의 기술 사용
  • 경쟁상태, 데드락 등의 위험 리스크가 생긴다.
  • Thread-Safe의 요소를 갖춘 어플리케이션을 위해서 앞서의 동기화 이외에 방법들
    • Transactional Memory
    • OpenMP
    • Functional Programming Language