[CS] {운영체제} 교착상태(데드락)

1. 교착상태(데드락)란?

 

> 식사하는 철학자 문제 ( 대표적인 교착상태를 나타내는 예시 )

모든 철학자가 왼쪽의 포크를 들면 그 누구도 오른쪽 포크가 없어서 식사를 할 수 없다.

철학자 : 프로세스, 포크 : 자원, 식사행위 : 실행

 

> 교착상태를 해결하기 위해서

1) 교착상태가 발생했을 때의 상황을 정확히 표현해보기

=> 자원할당 그래프

- 교착상태 발생 조건 파악 가능

- 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능

a. 프로세스는 원으로, 자원의 종류는 사각형으로 표현

b. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현

c. 프로세스가 어떤 자원을 할당 받아 사용중이라면 자원에서 프로세스를 향해 화살표를 표시

d. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시

 

교착상태가 발생한 자원할당 그래프(식사하는 철학자 문제 예시)

 

2) 교착상태가 발생할 조건

: 아래 네 조건 중 하나라도 없다면 교착상태가 발생하지 않음!

(1) 상호 배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태

(2) 점유와 대기 : 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태

(3) 비선점 : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태

(4) 원형 대기 : 프로세스들이 원의 형태로 자원을 대기하는 상태

 

---

2. 교착상태 해결 방법

1) 예방

- 애초에 교착상태가 발생하지 않도록 하는 방법

- 교착상태 발생조건(상호배제, 점유와 대기, 비선점, 원형대기) 중 하나를 없애버리기

(1) 상호 배제를 없애려면?

-> 모든 자원을 공유가능하게 만든다(현실적으로는 불가능)

(2) 점유와 대기를 없애려면?

-> 특정 프로세스한테 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분

=> 자원의 활용률을 낮출 수 있는 부작용이 있는 방식

(3) 비선점 조건을 없애려면?

-> 선점이 가능한 자원(ex.CPU)에 한해 효과적

=> 모든 자원이 선점 가능한 것은 아니다.

(4) 원형대기를 없애려면?

-> 모든 자원에 번호를 붙이고 오름차순으로 할당하면 원형 대기는 발생하지 않음

원형대기를 없애는 방법 예시

=> 자원에 번호를 붙이는 것은 어려운 작업

      어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라진다.

 

2) 회피

- 교착상태를 무분별한 자원 할당으로 인해 발생했다고 간주

- 교착상태가 발생하지 않을 만큼 조심히 할당하기

- 배분할 수 있는 자원의 양을 고려햐여 교착상태가 발생하지 않을 만큼만 자원 배

> 알아야 할 용어

(1) 안전 순서열

: 교착 상태 없이 안전하게 프로세스들에게 자원을 할당할 수 있는 순서

(2) 안전 상태

: 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료할 수 있는 상태

= 안전 순서열이 있는 상태

(3) 불안전 상태

: 교착 상태가 발생할 수도 있는 상태

= 안전 순서열이 없는 상태

 

3) 검출 후 회복

- 교착 상태의 발생을 인정하고 사후에 조치하는 방식

- 프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복

(1) 선점을 통한 회복

: 교착상태가 회복될때까지 한 프로세스씩 자원을 몰아주는 방식

(2) 프로세스 강제 종료를 통한 회복

- 교착상태가 놓인 프로세스 모두 강제 종료(-> 작업 내역을 잃을 위험)

- 교착상태가 해결될 때까지 한 프로세스씩 강제종료

(-> 교착 상태가 해결되었나를 계속 확인해야하기 때문에 오버헤드 발생 가능)