[6주차] 병행 제어(2)

세마포어는 프로그램에 아주 작은 이슈만 있어도 동작 X

• 데드락 (Deadlock)
  : 두 개 자원을 각각의 프로세스가 차지하고 있어 영원히 진행이 안되는 상황
  : 일종의 Starvation (프로세스 각각에서 발생)

Classical Problems of Synchronization

동기화와 관련된 전통적 문제

1. Bounded-Buffer Problem (Producer-Consumer Problem)

생산자-소비자 문제
: 크기가 유한한 공유 버퍼에 여러 프로세스가 접근할 때 발생

• 생산자 프로세스
  : 데이터를 버퍼에 넣어준다

• 소비자 프로세스
  : 데이터를 버퍼에서 꺼내간다

• 공유 버퍼
  (1) 공유 데이터 문제
  : 비어있는 버퍼에 생산자가 데이터를 넣으려고 쳐다보는데, 다른 생산자에게 CPU 빼앗기는 문제
  : 소비자도 마찬가지! 동시에 동일 데이터에 접근할때 문제 발생 가능
  : 락 걸어서 해결
    => 생산자는 빈 버퍼 생길 때까지(소비자가 데이터 꺼내갈 때까지) 대기
    => 소비자는 버퍼가 채워질 때까지 (생산자가 데이터 넣어줄 때까지) 대기

  생산자에게는 빈 버퍼가 자원, 소비자에게는 찬 버퍼가 자원
  자원의 수를 셀 때도 semaphore 사용
  

2. Readers and Writers Problem

읽기-쓰기 문제
: 누군가 읽고 쓸 때는 DB 접근을 막아야 한다.

• Reader은 동시에 일어나도 상관 없다!
  : Reader에 대해서는 lock 거는게 비효율적 - readcount 변수로 관리
  : Write만 배타적으로 동시 접근 막아두기

• mutex
  : 공유변수 readcount에 대한 lock 관리 목적
  : 만약 readcount=1으로 동시 접근하는 reader가 있다면 writer는 lock 걸고 읽는다
  : 만약 readcount=0으로 DB에 접근하는 사람이 없다면(내가 마지막) DB에 걸린 lock을 풀어준다

Writer는 Reader를 계속 기다리는 Starvation 발생 가능
일정 시간 간격으로 도착한 writer에게 권한 주는 방식으로 해결할 수 있다

3. Dining-Philosophers Problem

식사하는 철학자 문제

• 철학자들이 동시에 배가 고파졌는데, 젓가락이 공유 데이터라서 동시에 밥을 먹을 수 없는 경우
  : 철학자가 굶어 죽으면 안된다는 점도 고려해야 함! (=기아상태 방지 필요)
  • binary semaphore를 이용
    : 잡은 젓가락(공유 데이터)를 절대 내려놓지 않기에 Dead lock 발생가능

    
    두 젓가락을 모두 잡을 때만 available되도록 설정해서 해결하자!
    : Monitor 방식을 semaphore 방식으로 구현한 방법
    

Monitor

세마포어의 문제 해결

• 세마포어의 문제
  (1) 코딩하기 힘듬
  (2) 정확성 입증 힘듬
  (3) 자발적 협력이 필요
  (4) 한번의 실수가 모든 시스템에 치명적 영향

• 모니터
  
  : 공유데이터에 대한 접근은 모니터 안에 정의된 함수로만 가능하도록 한다
  : 모니터 안에서 active되는 것은 하나로 제한을 둔다

• 모니터의 추상적 표현
  
  : 모니터 안에있는 공유 데이터에 여러 프로세스가 접근할 때 모니터 안의 Operations로만 공유 데이터에 접근할 수 있다.
  : 공유 데이터에 대한 접근을 모니터가 큐를 이용해 알아서 막아준다.

• 모니터의 condition variable
  
  : 자원의 여분 여부를 기반으로 큐에 줄 세울지를 결정한다.
  : 만약 여분 없으면 wait, 여분 있으면 줄 서있는 애를 깨우는 signal

Bounded-Buffer problem의 Monitor 해결

• 세마포어 코드와 비교했을 때
  : 락을 걸고 푸는 부분이 없다! 플머 입장에서 매우 편리
  : 버퍼가 비었을 때만 가능했는데, 자원 여부만 확인하면 됨 = 추상적 의미 몰라도 됨. 간단
  : 세마포어는 세마포어 변수값을 변동하면서 계속 체크해야 하는데, 모니터는 모니터 변수를 변경하지 않아도 된다.
  => 세마포어는 원자적으로 사용자가 계속 관리해야함! 모니터는 알아서 해주니까 공수를 줄여줌

Dining-Philosophers problem의 Monitor 해결

• 공유 데이터(젓가락)에 대한 접근을 모니터 안에 구현
  : 상태 변수도 공유 데이터로 둔다 - 젓가락에 대한 접근과 관련되기 때문
  : condition - 다섯명의 철학자를 잠재우기 위한 큐

Deadlock (교착 상태)

프로세스들이 서로가 가진 자원을 기다리면서 생기는 block 된 상태

The Deadlock Problem

Deadlock 발생의 4가지 조건

• Mutual Exclusion (상호 배제)
  : 프로세스들이 자원을 동시에 사용할 수 없다

• No preemption (비선점)
  : 자원을 빼앗을 수 없다

• Hold and wait (보유 대기)
  : 내가 가진걸 내어놓지 않는다
  : 비선점은 빼앗을 수 있느냐 없느냐, 보유대기는 기다리는 애들이 있는데 양보하지 안는 것

• Circular wait (환형 대기)
  : 자원을 기다리는 프로세스간 사이클이 형성된다

Resource-Allocation Graph (자원할당그래프)

• 자원에서 프로세스로 가는 화살표
  : 이 자원을 이 프로세스가 점유하고 있다

• 프로세스에서 자원으로 가는 화살표
  : 이 프로세스가 이 자원을 기다리고 있다

• 점의 개수 의미
  : 자원의 인스턴스 개수. 4번 자원이 3개 있는 상황

• 왼쪽 그래프
  : 데드락 생김
  : 자원의 인스턴스 개수대로 사이클 생겼으니까!

• 오른쪽 그래프
  : 데드락 안생김
  : 한 자원 인스턴스에는 사이클이 생겼지만, 나머지 한 자원 인스턴스는 사이클이 안생김

Deadlock 처리 방법

Deadlock Prevention, Deadlock Avoidance
: 데드락 안생기게 하는 법

• Deadlock Prevention
  : 자원할당할 때 데드락 발생조건 중 하나를 막아서 구현
  : 비효율적인 방법.
  

• Deadlock Avoidance
  : 자원 요청에 대한 추가 정보를 이용해서 데드락을 막는 방법
  

• 그래프로 표현한 Deadlock Avoidance
  
  : 데드락 avoidance는 점선을 통해 '요청할 수 있음'을 표시한다
  : '자원 요청 가능한 경우'까지 고려하여 사이클을 생성하기에 데드락을 방지한다
  : 평생의 데드락 가능성을 고려한 방법!

Deadlock Detection and recovery
: 데드락 발생 생겼을 때 발견되면 recover하는 법

Deadlock Ignorance
: 데드락 무시