Deadlock

- 두 프로세스가 각자 자원을 가지고 있으면서 상대방이 가지고 있는 자원을 요구하는 경우 아무것도 진행되지 않아 데드락이 걸림

- 하드웨어던 소프트웨어던 공유자원을 서로 보유한 채 서로껄 요구하면 데드락이 걸림

- 데드락이 걸리는 4가지 조건:

1. 해당 자원을 독점적으로 가지고 있을때

2. 가지고 있는 자원을 강제적으로 빼앗을수 없을때

3. 가지고 있는 자원은 내놓지 않고 가지고 있으면서 추가적인 데이터를 요구할때

4. 서로가 가진자원을 요구하는 사이클이 형성될 때

 

- 데드락이 걸려있는지 확인 여부는 자원할당 그래프를 통해 할수있음

- 원형은 프로세스(P)

- 사각형은 자원, 검은 동그라미는 자원 개수

- 자원->프로세스 화살표: 해당 자원을 해당 프로세스가 가지고 있다

- 프로세스->자원 화살표: 해당 프로세스가 해당 자원을 요청하고 있다

- 화살표로 싸이클이 형성되어 있지 않으면 데드락이 아님, 일단 왼쪽 오른쪽 둘다 싸이클은 가지고 있음

- 싸이클이 있으면 데드락일 가능성이 있음

- 싸이클이 있을때, 자원이 하나밖에 없으면 100% 데드락, 자원이 여러개일경우 데드락 가능성은 있음

- 왼쪽은 R2의 자원이 여러개지만 싸이클이 2개가 형성되므로 데드락

- 오른쪽은 싸이클이 있지만 자원이 여러개므로 데드락이 안생길수도 있음

 

- 데드락 처리하는 방법

- 위에 있을수록 강도가 높은 방법, 위 2개는 사전 차단, 3번째는 시스템이 느려졌을경우 데드락 체크, 4번째는 데드락 상관 안함

- 현 OS 대부분이 4번째를 선택, OS가 데드락을 관리하는게 아닌 사용자가 직접 kill 하는 방식으로 해결

- 데드락이 발생할 확률이 높지 않기 때문에 미연에 방지하기 위해 거는 오버헤드가 오히려 비효율적이라 현대에는 4번 방법을 주로 사용

 

1) deadlock prevention

- 데드락이 발생하는 4가지 조건중 하나를 원천적으로 차단해서 데드락이 발생하지 않게 함

1. mutial exclusion: 여러 프로세스가 접근할수 있는 공유 자원의 경우 무조건 한번에 하나의 프로세스만 접근하도록 해야 하므로 이 조건은 막을 수 없음

2. hold and wait: 모든 프로세스가 자원을 기다리고 있는 상황에서는 자원을 하나도 가지고 있지 않으면 된다

방법1: 프로세스가 시작할때 프로세스가 실행될 동안 필요한 모든 자원을 할당하고 시작한다. 이 경우 모든 자원을 hold하고 있고 wait할 일이 없으므로 데드락은 안걸리나 잠깐동안만 사용하는 자원도 프로세스 생명주기 내내 들고있어야 하기때문에 비효율적임

방법2: 똑같이 프로세스를 실행하다가 자원을 wait할일이 있을때 쥐고 있던 모든 자원을 내려놓고 다시 받음, 필요로 하는 자원을 다 얻거나 하나도 없거나 이기 때문에 데드락이 걸리진 않음

3. no preemption: 자원을 빼앗을수 있게함, CPU와 메모리의 경우 중간에 preemption을 당해도 그 시점을 정확하게 기억하고 있으므로 다시 시작하는데 문제가 없음, 하지만 중간에 preemption을 당하면 공유 자원에 문제가 생기는 경우 이 방법은 사용할 수 없음

4. circular wait: 모든 자원의 할당 순서를 매김, r1, r2, r3이 있을때 무조건 1->2->3 이 순서대로 자원을 가질수 있게함 그럴 경우 모든 프로세스가 3번을 얻기 위해선 1번을 먼저 얻어야 하므로 데드락은 걸리지 않음

 

- 1,3 번은 사용하기 힘들고 2,4번은 사용 할수는 있으나 자원 이용률이 낮아지고, 성능이 감소하고, starvation 문제가 발생할 수 있으므로 많이 사용하지는 않음

 

2) Deadlock Avoidance

- 공유 자원에 대한 부가정보를 사전에 입력받고 그걸로 계산해서 데드락이 발생하는 상황을 피함

- 보통은 각 프로세스가 시작될때 각 자원의 최대 사용량을 사전에 입력받는다

- 남는 자원과 자원 최대 사용량을 계산해서 남는 자원이 있어도 데드락이 발생할수도 있는 상황이면 빌려주지 않음

- 자원의 instance가 하나밖에 없을때와 자원이 여러개일때 사용하는 알고리즘이 다름

 

1. Resource Allocation Graph algorithm: 자원이 하나밖에 없을때

- 네모는 자원, 동그라미는 프로세스

- 네모 -> 동그라미 화살표는 해당 프로세스가 해당 자원을 가지고 있는 상태

- 동그라미 -> 네모 화살표는 해당 프로세스가 해당 자원을 요청한 상태

- 동그라미 -> 네모 점선은 프로세스 생명주기동안 적어도 한번은 해당 자원을 요청할수 있는 상태

- 맨 오른쪽 사진의 경우, 점선으로라도 사이클이 생길때는 데드락이 걸릴 수 있는 상황이기 때문에, 2번째 사진에서 R2가 자원이 있어도 P2에게 자원을 주지 않음 하지만 P1에게는 줘도 사이클이 생길 경우의 수가 없기 때문에 P1에게는 줌, 그러다가 사이클이 생길 위험이 하나도 없을 경우 P2에게 줌

 

2. Bankers algorithm

- P0~5는 프로세스 개수, A(10) B(5) C(7)는 자원개수

- 각 프로세스마다 테이블을 4개씩 만든다

Allocation: 지금 할당되어 있는 자원 개수

Max: 프로세스가 실행되는 동안 요청할수 있는 자원 최대 개수

Available: 남은 자원 개수(총자원수 - Alllcation)

Need: 남은 최대 요청 가능 자원(Max - Alllcation)

- 프로세스가 자원 요청이 들어올때, Need 테이블과 Available 테이블을 본다

- Need 테이블 < Available 테이블일 경우 자원을 최대로 요청해봤자 남는 자원으로 수용이 가능하므로 문제없이 자원을 빌려준다

- Need 테이블 > Available 테이블일 경우 자원을 최대로 요청했을때 데드락이 걸릴 확률이 있으므로 아예 자원을 빌려주지 않음

- 나머지 프로세스들이 다 끝나서 Need 테이블 < Available 테이블일때 다시 자원을 빌려주도록 한다

- 그래서 프로세스에 순번(safe sequence)이 정해짐, 가용 자원으로 완전히 끝낼수 있는 프로세스부터 자원을 줘 먼저 끝내면 자원을 반환받아 더 큰 가용자원으로 더 자원을 많이 요구하는 프로세스를 끝냄

- 데드락은 안생기나 비효율적

 

 

3) Deadlock Detection and Recovery

- 데드락은 빈번히 발생하는 이벤트가 아니기 때문에 이걸 미연에 방지하기 위해서 비효율적인 방법을 쓰느니 자원 요청하면 있는만큼 주다가, 데드락이 발생해서 느려지게되면, 그때 데드락을 찾아내서 recovery 시킴

 

1. 단일 인스터스 일때

- 똑같이 사이클을 찾음, 하지만 자원인 네모를 빼고 프로세스만 존재하는 wait-for 그래프로 더 간단하게 찾을 수 있음

- 프로세스가 점이고, 자원요청 화살표가 선이라고 하면, 각 점은 최대 n-1개의 선을 가질 수 있음

- 그러면 O(n^2)의 시간이 소요됨

- 매번 그정도의 시간을 소모하여 주기적으로 사이클을 체크, 데드락이 있을경우(단일 인스턴스에서 사이클이 존재하는 경우) 찾아서 recovery

 

2. 멸티 인스턴스 일때

- 미연에 방지하는게 아니기 때문에 Need같은건 필요 없음

- Request 테이블은 지금 각 프로세스가 요청한 자원 개수

- 요청이 들어왔을때, Request가 0,0,0인 프로세스는 더이상 요청할 자원이 없다고 보고, Allocation에 있는 자원도 언젠가 반납할거기 때문에 Available에 포함시킴, 그래서 포함시킨 Available 테이블로 해당 요청을 들어줄수 있는지 없는지 체크

- 합쳐진 available 테이블로도 해당 요청을 처리할수 없으면 deadlock이라고 판단, 그때 recovery시킴 

 

recovery 방법:

1. process termination: 데드락에 연루된 프로세스를 다 kill함

2. resource preemption: 비용을 최소화할 프로세스부터 하나씩 kill(safe state로 롤백)해서 원인을 찾음, starcation 현상이 발생할수 있으므로 롤백횟수도 같이 고려

 

 

4) Deadlock Ignorance