데드락

교착상태 : 상대방이 가진 자원을 요구 그러나 상대방도 자기거 내놓지 않고 다른 상대방거를 요구한다.

• 데드락: 일련의 프로세스들이 서로가 가진 자원을 기다리면서 block된 상태
• 자원: HW, SW 등을 포함하는 개념
  ex> I/O Device, CPU cycle, memory space, semaphore 등

1) 데드락 상황1(HW)

• 시스템에 2개의 tape drive가 있다.
• 프로세스가 하는 역할은 하나의 tape drive에서 읽어서 다른 tape drive에다가 copy하고싶음
• 2개의 프로세스가 각각 tape 2개를 점유해야함. 그러나 각각 하나의 tape drive를 보유한채 다른 하나를 기다리면 데드락 상태가 된다.

2) 데드락 상황2(SW)

P0는 B를 요청 P1은 A를 요청 그러나 이미 서로 가지고 있는 상태이다.

데드락 발생의 4가지 조건(전부만족)

1) 상호배제(Mutual exclusion)

독점적으로 씀, 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
= 내가 가지고 있는 동안은 나 혼자 독점적으로 쓴다.

2) 비선점(No preemption)

프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

3) 보유대기(Hold and Wait)

자원을 가진 프로세스가 다른 자원을 기다릴 때 보유자원을 놓지않고 계속 가지고 있음

4) 순환대기(Circular Wait)

자원을 기다리는 프로세스간에 사이클이 형성되어야 함

데드락의 처리방법

1) Deadlock Prevention(미리 막는다)

상호배제는 예방할 수 없다.

• 1> 그러나 비선점을 선점(preemption)으로 바꾸어 뺏어올 수 있게 하는 방식으로 예방이 가능하다.

• 2> 보유대기는 프로세스가 자원을 기다리고 있을때 자원을 가지고 있지 않게 해서 예방한다.
  -> 방법1: 프로세스 시작시 모든 필요한 자원을 할당받는다.(중간에 자원 요청할 필요 없음)
  -> 방법2: 자원있는 상태에서 요청시 내가 가진 자원은 모두 뱉어내고 다시 요청

• 3> 순환대기는 모든 자원마다 순서를 지정하는 방식으로 예방이 가능하다. (싸이클이 안생긴다)

미리막는 경우의 문제점은 자원이용률이 낮아지고 성능도 낮아진다는 것이다. 또한 Starvation의 문제가 나타날 수 있다
아직 생기지도 않을 데드락에 대해 제약조건을 너무 많이 단다.

2) Deadlock Avoidance

프로세스가 시작될때 이 프로세스가 평생 쓸 자원의 최대량을 미리 알고 있다고 가정하고 데드락을 피해간다.
어떤 프로세스가 자원요청시 내가 자원할당해주면 데드락이 생길 가능성이 있겠다 싶으면 자원의 여분이 있어도 주지 않는다.

가. 자원할당 그래프 알고리즘

자원의 인스턴스가 하나씩 밖에 없는 경우에 활용 가능하다.

• 점선: 이 프로세스가 적어도 평생의 한번은 이 자원을 사용할 일이 있다.

현재상태:
R1이 P1에 할당된 상태이다.
이때 R1자원을 P2가 요청했지만 아직 할당을 못받았다.(이미 P1에 할당됨)
그 다음 P2가 R2를 요청한다. 만약 R2가 P2에게 가면 Cycle이 형성될 가능성이 존재한다. 따라서 Deadlock Avoidance가 동작한다면 R2를 P2에게 할당 하지 않는다.

나. Banker의 알고리즘

자원당 인스턴스가 여러개 있는경우에 활용이 가능하다.

3, 3, 2 는 모든 할당된 자원을 10 5 7에서 차감한 값이다.

포인트: Available로 Need를 커버할 수 있으면 받아들인다.
그 후 나에게 할당된 자원을 다시 반납한다.
-> Available + Allocation
그리고 다음 프로세스로 들어간다.

3) Deadlock Detection

데드락의 예방이 아니라 발생시 감지하는것이다.

가. 자원의 인스턴스가 1개일때 데드락 찾기

자원을 전부 빼버린다. 그렇게 해서 데드락사이클을 찾는다.

각 노드 하나당 화살표가 최대 (n-1)개씩 있을 수 있기에 n*(n-1)
O(n^2)만큼의 시간복잡도를 갖는다.

나. 자원의 인스턴스가 여러개일때 데드락 찾기

• 만약 P1이 요청시 데드락?

  낙관적으로 본다.
  1) P0는 요청하는 것이 없으므로 B1개를 반납한다.
  2) P2는 요청하는 것이 없으므로 A 3개와 C 3개를 반납한다.
  3) 그러면 A(3), B(1), C(3)개가 생겼고 P1의 요구인 A 2개와 C 2개를 들어줄 수 있다.
  4) 또한 마찬가지로 P1역시 자원 다 쓰고 다시 반납할 것임을 가정한다.

• 만약 P2가 자원 C 1개를 요청하는 것으로 변경하면?

  데드락이다.
  1) P0만이 요청하는 것이 없으므로 B 1개를 반납한다.
  2) B를 원하는 프로세스는 없음(그 다음 반납 없다)
  3) 어떤 프로세스의 요청도 들어줄 수 없다.

4) Deadlock Recovery

가. 프로세스 종료

데드락에 연루된 프로세스들을 사살
1) 모든 프로세스를 한꺼번에 죽임
2) 하나씩 죽이면서 데드락 없어지는지 확인

나. 자원 선점(Resource Preemption)

데드락에 연루된 프로세스들로부터 자원을 뺏는 방법
-> 희생양(Victim)을 선정해서 자원을 뺏는다.
-> 문제점: A의 자원을 뺏었는데 다른 프로세스가 갖기 전에 A가 그 자원 또 요청해서 다시 가져감. A가 다시 희생양이 됨(반복)
Starvation 문제 발생 따라서 Victim의 패턴을 다르게 해줘야함.

5) Deadlock Ignorance (현재 OS들이 채택)

데드락이 일어나든 일어나지 않든 아무일도 안함
-> 프로세스 정지 상황이 일어난다. -> 사용자가 알아서 처리

• why?
  1) 데드락을 안생기게 하는 방법이 자원을 비효율적으로 쓴다.
  2) 데드락을 감지하는거도 시스템의 오버헤드가 크다.