교착상태 필요조건과 해결방법

교착상태는 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 말한다.

 

교착상태는 시스템 자원, 공유 변수, 데이터베이스와 같은 응용프로그램에서 발생할 수 있다.

 

자원 할당 그래프는 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것이다. 

 

💡 교착상태 필요조건

상호 배제, 비선점, 점유와 대기, 원형 대기 이 4가지 모두를 충족해야 교착상태가 발생

 

자원이 어떤 특징을 가지는가 ❓

1️⃣ 상호배제: 배타적인 자원은 임계 구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없다. 배타적인 자원을 사용하면 교착상태 발생

2️⃣ 비선점: 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없다.

 

프로세스가 어떤 행위를 하고 있는가 ❓

3️⃣ 점유와 대기: 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.

4️⃣ 원형대기: 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다. 

 

 

👀 교착상태와 아사(기아)현상은 다르다 ❗

교착상태는 아사현상과 달리 정책상 잘못이나 오류가 없어도 자연적으로 발생한다. 그러나 기아 현상은 정책상 잘못이나 오류로 인해 특정 프로세스의 작업이 이루어지지 않는 것이라서 에이징과 같은 방법으로 해결 가능하다.

 

 

💡 교착상태 해결방법

해결방법	특징
교착상태 예방	교착상태를 유발하는 4가지 조건 무력화
교착상태 회피	교착상태가 발생하지 않는 수준으로 자원을 할당
교착상태 검출	자원할당그래프를 사용하여 교착상태를 발견
교착상태 회복	교착상태를 검출한 후 해결

 

교착상태 예방

상호 배제 예방: 현실적으로 자원을 공유할 수 없는 자원이 생길 수밖에 없어서 불가능

 

비선점 예방: 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 등을 정하는 것이 까다롭고 모든 자원을 빼앗을 수 있으면 아사 현상이 발생 -> 에이징으로 해결할 시 에이징으로 올라가면 다시 비선점 자원이 되어 무력화할 수 없다.

 

점유와 대기 예방: 전부 할당하거나 아예 할당하지 않는 방식을 적용, 시작 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나 그렇지 못할 시 전부 반납 -> 자원의 활용성이 떨어진다, 많은 자원을 사용하는 프로세스는 불리, 일괄 작업방식으로 동작

 

원형 대기 예방: 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당, 숫자가 작은 자원을 잡은 상태에서 큰 숫자를 잡는 것은 허용하지만 숫자가 큰 자원을 잡은 상태에서 작은 숫자를 잡는 것은 허용 불가능하다. -> 프로세스 작업 진행에 유연성 하락, 자원의 번호를 어떻게 부여할지 문제

 

교착상태 회피

프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착상태가 발생하는지 파악해서 그 이하로 자원을 나누어주는 방법이다.

자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나눈다.

교착상태는 불안정 상태의 일부분

안정상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착상태를 회피

 

✌ 은행원 알고리즘

교착상태 회피를 구현하는 가장 대표적인 알고리즘

 

변수	설명
전체 자원(Total)	시스템 내 전체 자원의 수
가용 자원(Available)	전체자원 - 모든 프로세스의 할당자원
최대 자원(Max)	각 프로세스가 선언한 최대 자원의 수
할당 자원(Allocation)	각 프로세스에 현재 할당된 자원의 수
기대 자원(Expect)	각 프로세스가 앞으로 사용할 자원의 수(최대자원 - 할당자원)

자원을 할당하는 기준은 무엇일까 ❓

각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한번 이상이면 할당한다. 그 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 있다는 뜻이므로 안정상태

 

🙆‍♀️ 안정상태

안정 상태

교착상태 회피의 문제점

1. 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.

2. 시스템 전체 자원의 수가 고정적이어야 한다.

3. 자원이 낭비된다.

 

교착 상태 검출

교착 상태 해결 방법 중 가장 현실적인 방법으로 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방법이다. 교착 상태가 발견되면 이를 해결하기 위해 교착상태 회복 단계를 거친다.

 

1️⃣ 타임아웃을 이용한 교착상태 검출(= 가벼운 교착상태 검출)

의미: 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법

단점: 엉뚱한 프로세스가 강제 종료될 수 있고 모든 시스템에 적용할 수 없다. (ex. 분산 데이터베이스 시스템)

 

2️⃣ 자원 할당 그래프를 이용하여 교착상태 검출(= 무거운 교착상태 검출)

의미: 자원 할당 그래프에 사이클이 발생할 시 교착상태가 발생. (단일 자원일 경우만 해당)

장점: 프로세스의 작업 방식을 제한하지 않으면서 교착 상태 파악 가능

단점: 자원 할당 그래프 유지, 갱신, 사이클 검사하는 추가 작업 발생으로 인해 오버헤드 발생

 

교착 상태 회복

1️⃣ 교착 상태를 일으킨 모든 프로세스를 동시에 종료하는 방법 -> 모든 프로세스를 강제 종료한 후 다시 실행할 때는 순차적으로 실행하는 것이 필요함

 

2️⃣ 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료

어떤 프로세스부터 종료할까 ❓

1. 우선순위가 낮은 프로세스 먼저 종료

2. 우선순위가 같은 경우 작업 시간이 짧은 프로세스 먼저 종료

3. 위 두 조건이 같을 경우 자원을 많이 사용하는 프로세스 먼저 종료

 

회복 상태에서 중요한 점은 프로세스 강제 종료와 더불어 강제 종료된 프로세스가 실행하기 전에 시스템을 복구하는 일이 필요하다. 따라서 체크포인트를 만들어서 가장 최근의 검사 시점으로 돌아간다.

 

💡 다중 자원과 교착 상태 검출

다중 자원이 있는 대기 그래프에서 그래프 감소를 완료한 후에도 사이클이 남아있다면 교착상태 발생으로 판단한다.

대기 그래프: 자원 할당 그래프에서 프로세스와 프로세스 간에 기다리는 관계만 나타낸 그래프

그래프 감소: 끝날 가능성이 있는 프로세스의 화살표와 관련 프로세스의 화살표를 연속적으로 지워나가는 작업

자원 할당 그래프

 

다중 자원일 경우 사이클이 발생했을 시 대기 그래프를 그려봐야 한다 ❗

대기 그래프

 

1. P2가 끝날 수 있는 프로세스이기에 1번 화살표를 지운다.

2. P1이 끝날 수 있는 프로세스이기에 2번을 지운다.

3. P4가 끝날 수 있는 프로세스이기에 3번을 지운다.

4. P3이 끝날 수 있는 프로세스이기에 4번을 지운다.

 

그래프 감소가 가능하므로 교착상태가 발생하지 않는다.