deadlock

deadlock(교착상태)

일련의 프로세스들이 서로가 가진 자원을 기다리면 block된 상태를 말한다.

프로세스가 자원을 사용하는 절차

request - allocate - use - release

deadlock 발생조건 4가지

mutual exclusion (상호 배제)

매 순간 하나의 프로세스만이 자원을 사용할 수 있다.

no preemption (비선점)

프로세스는 자원을 스스로 내어놓기만 할 뿐 강제로 뺏기지 않는다.

hold and wait (보유대기)

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

circular wait (순환대기)

자원을 기다리는 프로세스간에 사이클이 형성되어야 한다.
서로가 가진 자원을 기다리며 꼬리에 꼬리를 물어 사이클이 형성된다.

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

그래프에 사이클이 없으면 데드락이 아니다.
그래프에 사이클이 있을 때

• 만약 자원당 인스턴스가 하나밖에 없으면 데드락이다.
• 만약 자원당 인스턴스가 여러개 있으면 데드락일 수도 있고 아닐 수도 있다.
  
  네모는 자원이고 동그라미는 프로세스다.
  자원에서 프로세스로의 화살표는 자원을 얻은 상태고 프로세스에서 자원으로의 화살표는 자원을 기다리는 상태다.
  왼쪽의 경우에는 데드락이지만 오른쪽의 경우에는 데드락이 아닌데 P2나 P4가 자원을 반납하면 사이클이 없어지게 되기 때문이다.

deadlock의 처리 방법

Deadlock Prevention

자원 할당 시 데드락의 4가지 필요 조건 중 하나가 만족되지 않도록 하는 것이다.
이렇게 하면 자원의 이용률이 떨어지고 시스템의 성능이 나빠지며 스타베이션이 발생할 수 있다.

• Mutual Exclusion
  공유해선 안되는 자원의 경우 반드시 성립해야 한다.
• Hold and Wait
  자원을 잡은채로 다른 자원을 요청할 때 생기는 문제니 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않게 한다.
  첫번째 방법은 프로세스가 시작될 때 평생에 필요로하는 모든 자원을 할당받게 하여 wait할 일을 없게하면 되는데 자원의 비효율성이 생기게 된다.
  두번째 방법은 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청한다.
• no Preemtion
  가지고 있는 자원을 뺏을 수 없기 때문에 생기는 문제니 뺏을 수 있게 한다.
  아무 자원이나 뺏어올 순 없고 상태를 쉽게 저장하고 복구할 수 있는 자원에서 주로 사용한다.(CPU, memory)
• Circular Wait
  자원에 순서를 정해 낮은 번호의 자원을 먼저 획득해야 높은 번호의 자원을 획득할 수 있게 한다.
  프로세스A가 1번을 가지고 있으면서 3을 기다리고 프로세스B가 3번을 가지고 있으면서 1번을 기다리면 데드락이 되는데 1번을 먼저 획득하게 만들면 사이클이 생기지 않는다.

Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해서 데드락의 가능성이 없는 경우에만 자원을 할당한다.
프로세스가 평생에 쓸 자원의 최대량을 미리 알고있다고 가정할 때의 경우다.

자원당 인스턴스가 하나일 때는 자원할당 그래프를 사용한다.
자원당 인스턴스가 여러개일 때는 Banker’s Algorithm을 사용한다.

Banker’s Algorithm

전체 자원 개수 A(10), B(5), C(7)

	Allocation	Max	Available	Need
	A B C	A B C	A B C	A B C
P0	0 1 0	7 5 3	3 3 2	7 4 3
P1	2 0 0	3 2 2		1 2 2
P2	3 0 2	9 0 2		6 0 0
P3	2 1 1	2 2 2		0 1 1
P4	0 0 2	4 3 3		4 3 1

Allocation은 현재 할당받은 자원의 개수
Max는 평생에 최대로 필요로 할 때의 자원의 개수
Available은 전체 자원 개수에서 Allocation들을 뺀 현재 가용할 수 있는 자원의 개수
Need는 Max에서 Allocation을 뺀 값으로 추가로 더 요청할 수 있는 개수

여기서 P1이 (1, 0, 2)를 요청하면 가용자원에서 줄 수 있지만 바로주지 않고 Need를 확인한다. P1의 need는 (1, 2, 2)이므로 자원을 더 요청하더라도 현재 가용자원으로 충족이 가능하니 자원을 넘겨주게 된다.
하지만 P4가 (0, 2, 0)를 요청하면 가용자원에서 줄 수는 있지만 추가요청시에 현재 가용자원으로 충족이 안되니 넘겨주지 않는다.

Deadlock Detection and recovery

데드락의 발생은 허용하되 그에 대한 detection루틴을 두어 데드락 발견시 recovery를 한다.

자원당 인스턴스가 하나일 때는 자원할당 그래프를 사용한다.
자원당 인스턴스가 여러개일 때는 아래의 표를 사용한다.

먼저 데드락 detection을 한다.

전체 자원 개수 A(7), B(2), C(6)

	Allocation	Request	Available
	A B C	A B C	A B C
P0	0 1 0	0 0 0	0 0 0
P1	2 0 0	2 0 2
P2	3 0 3	0 0 0
P3	2 1 1	1 0 0
P4	0 0 2	0 0 2

이 방식은 어떤 프로세스가 최대로 자원을 얼마나 요청할지 알필요 없다.

데드락을 확인할 때는 최대한 낙관적으로 판단해야 한다.
추가로 요청하는 자원이 없을 때 무조건 반납한다고 가정할 때
현재 가용자원이 없지만 P0과 P2가 추가로 요청하지 않으니 반납할거라 생각하면 가용자원이 (3, 1, 3)이 되고 여기서 P1이 자원을 가져간 후에 다시 반납하고…를 반복한다고 보면 데드락이 아니다.

여기서 P2의 Request가 (0, 0, 1)이 됐다고 생각하면 P0이 B하나를 반납했지만 B하나로는 어떠한 요청도 받아들일 수 없기 때문에 데드락이다.

데드락이 발견이 되면 recovery를 한다.
데드락에 연관된 프로세스들을 모두 죽이거나
데드락에 연관된 프로세스들을 데드락이 없어질 때 까지 하나씩 죽여본다.

자원을 뺏어오는 방법도 있다.
다만 동일한 프로세스의 자원을 뺏어오면 스타베이션이 발생하니 몇번 자원을 뺏겼는지도 고려해야 한다.

Deadlock Ignorance

데드락을 시스템이 책임지지 않고 사용자가 알아서 해결해야 한다.
데드락은 잘 일어나지 않기 때문에 데드락을 미연에 방지하기 위해서 오버헤드를 키우는 것 보단 그냥 놔두는게 대부분의 OS들의 방식이다.