[OS] 운영체제 - 병행제어 4

운영체제 - 병행제어 4

Two type of Semaphores

Counting semaphore

• 도메인이 0 이상인 임의의 정수값
• 주로 resource counting에 사용한다.

Binary semaphore (=mutex)

• 0 또는 1 값만 가질 수 있는 semaphore
• 주로 mutual exclusion (lock / unlock)에 사용한다.

Deadlock and Starvation

Deadlock

• 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

Starvation

• Indefinite blocking
• 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
• 데드락을 각각의 프로세스 입장에서는 일종의 starvation이 발생했다고 볼 수도 있다.

Classical Problems of Synchronization

Bounded-Buffer Problem

• 크기가 유한한 버퍼를 가진다.

• Shared data

  • buffer 자체 및 buffer 조작 변수 (empty/full buffer의 시작 위치)

• Synchronization variables

  자원의 개수를 세는 작업에 있어 semaphore 사용이 적합하다.

  • mutual exclusion
    • shared data의 mutual exclusion을 위해 binary semaphore가 필요하다.
  • resource count
    • 남은 full/empty buffer의 수를 표시하기 위해 integer semaphore가 필요하다.

Readers-Writers Problem

• 한 프로세스가 DB에 write 중일 때, 다른 프로세스가 접근하면 안된다.
• read는 동시에 여럿이 해도 된다.
• Solution
  • writer가 DB 접근 허가를 아직 얻지 못했으면 모든 대기중인 reader들은 DB에 접근 가능
  • writer는 대기 중인 reader가 하나도 없을 때 DB 접근 가능
  • 일단 writer가 DB에 접근 중이면 reader들은 접근 금지
  • writer가 DB에서 빠져나가야만 reader의 접근 허용
• Shared data
  • DB 자체
  • readcount
    • 현재 DB에 접근 중인 리더의 수
• Synchronization variables
  • mutex
    • 공유 변수 readcount에 접근하는 코드(critical section)의 mutual exclusion 보장
  • db
    • reader, writer가 공유 DB에 올바르게 접근하도록 하는 역할
• Starvation
  • 이론적으로 reader가 계속해서 들어오면 writer 처리가 밀릴 수 있다.
  • 해결책
    • writer가 처리될 수 있는 주기를 만들어주면 된다.

Dining-Philosophers Problem

• 공유 데이터
  • 젓가락
• 문제 사항
  • 모두 왼쪽의 젓가락을 동시에 잡아버리면 Deadlock에 빠진다.
• 해결 방안
  • 4명만이 테이블에 동시 착석 가능하도록 한다.
  • 젓가락 두 개를 집을 수 있을 때, 젓가락을 집는 행위가 가능하게 한다.
  • 짝수/홀수에 따라 왼쪽/오른쪽 젓가락을 집을 수 있는 여부를 비대칭하게 결정한다.