[OS] 교착 상태

📍  교착 상태란 ?

 

다중 프로세스 환경에서 발생할 수 있는 상호 배제 문제.

2개 이상의 프로세스가 서로의 자원을 기다리며 무한정 대기 상태에 빠지는 현상.

 

 

프로세스 A는 임계 구역 진입 전 lock1 을 잠그고  (lock1 = true)

프로세스 B는 임계 구역 진입 전 lock2 를 잠궜다. (lock2 = true)

만약 프로세스 A가 lock2 가 false 가 되길 기다리고,

프로세스 B가 lock1 이 false 가 되길 기다린다면 교착 상태가 발생하게 된다.

 

 

📍  교착 상태 발생 조건

 

교착 상태는 4가지 조건이 모두 충족되면 발생할 가능성이 높아진다.

 

1️⃣ 상호 배제 Mutual Exclusion

한 프로세스가 사용하는 자원을, 다른 프로세스가 사용할 수 없는 경우

하나의 프로세스가 하나의 자원을 독점한 경우

 

2️⃣ 점유와 대기 Hold and Wait

자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태

 

3️⃣ 비선점 Nonpreemption

다른 프로세스가 점유하고 있는 자원을 강제로 빼앗을 수 없는 상태

(자원을 점유한 프로세스가 스스로 자원을 해제할 때까지 기다려야 함)

 

4️⃣ 순환(원형) 대기 Circular Wait

2개 이상의 프로세스가 서로가 점유한 자원을 요구하면서 순환적으로 대기하는 상태

(교착 상태 예시와 일치하는 상황)

 

프로세스 (Process) 란 ?

운영 체제에서 실행중인 프로그램. (1:1 매칭)
하나의 프로그램은 하나의 프로세스로 관리된다.
프로그램의 형태는 다양하다. (브라우저 개별 탭, 텍스트 편집기...)

운영 체제는 여러 프로세스를 관리하기 위해
PCB (Process Control Block) 구조를 사용한다.

 

스레드 (Thread) 란 ?

프로세스 내에서 실행되는 작업의 단위
한 프로세스는 하나 이상의 스레드를 가질 수 있는데,
이를 멀티스레드 프로세스 라고 부른다.

 

 

📍  교착 상태 해결 방법

 

1️⃣ 예방

앞에서 말한 교착 상태 필요 조건 4가지 중 한 가지를 충족하지 못하게 하는 방법

 

✅ 상호 배제 (Mutual Exclusion) 를 막는다면 ?

👉 즉, 한 프로세스가 사용하는 자원을 다른 프로세스도 동시 사용가능하게 한다면 ?

현실적으로 모든 자원의 상호 배제를 없애기는 어렵다.

 

✅ 점유와 대기 (Hold and Wait) 를 막는다면 ?

👉 즉, 특정 프로세스에 자원을 모두 할당하거나,
     아예 할당하지 않는 방식으로 운영한다면 ?

 

당장 자원이 필요해도 기다릴 수밖에 없는 프로세스와,

사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문에 운영이 어렵다.

또한 많은 자원을 사용하는 프로세스가 매우 불리해진다.

자원을 적게 사용하는 프로세스에 비해 동시에 자원을 사용할 타이밍을 잡기 어렵기 때문.

 

✅ 비선점 (Nonpreemption) 을 막는다면 ?

👉 다른 프로세스가 점유하고 있는 자원을 강제로 뺏을 수 있다면 ?

 

선점하여 사용할 수 있는 일부 자원에 대해서는 효과적이다.

그러나 선점이 아예 불가능한 자원도 있음. (ex. 프린터기)

이런 경우를 모두 대비할 수 없기에 어렵다.

 

✅ 순환(원형) 대기 Circular Wait 를 없앤다면 ?

👉 서로 점유한 자원을 서로 대기하지 않게 순서를 정해 순차적으로 해결한다면 ?

 

앞선 방법 중 제일 현실적이지만

각 자원을 어떻게 효과적으로 정렬해서 사용할 것인가는 해결하기 쉬운 문제가 아님.

 

 

2️⃣ 회피

교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당하는 방법.

프로세스들에 배분할 수 있는 자원의 양을 고려하여
교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법.

안전 상태 safe state
모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태

불안전 상태 unsafe state
교착 상태가 발생할 수도 있는 상태

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

 

안전 순서열이 있는 상태  👉  안전 상태

안전 순서열이 없는 상태  👉  불안전 상태

 

교착 상태를 회피하기 위해서는 시스템 상태가

안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하면 된다.

 

 

3️⃣ 검출 후 회복

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

운영 체제는 프로세스들이 자원을 요구할 때마다 그때 그때 모두 할당하며,

교착 상태 발생 여부를 주기적으로 검사한다.

교착 상태가 검출되면 그때 회복 프로세스를 동작시킨다.

 

✅ 선점을 통한 회복

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

다른 프로세스로부터 자원을 강제로 빼앗아 한 프로세스에 계속 할당해준다.

 

✅ 프로세스 강제 종료를 통한 회복

가장 단순하지만 확실한 방법.

운영 체제는 교착 상태에 놓인 프로세스를 모두 강제종료할 수도 있고,

( 한 방에 교착 상태를 해결하지만

그만큼 많은 프로세스들이 작업 내역을 잃게 될 수 있음 )

교착 상태가 없어질 때까지 한 프로세스씩 강제 종료할 수도 있다.

( 작업 내역을 잃는 프로세스는 최대한 줄일 수 있지만

교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드 야기 가능 )

 

 

번외 - 타조 알고리즘

교착 상태를 아예 무시하는 방법도 있다.

드물게 발생하는 잠재적 문제를 무시로 대처 ... 오호

( 완벽을 추구하는 과학자나 수학자 입장에서는 납득할 수 없는 방식일지 모르나,

문제 발생의 빈도나 심각성에 따라 최대 효율을 추구하는 엔지니어 입장에서는 적합한 방법일지도 )