[운영체제] 교착상태

교착 상태(DeadLock)

두 가지 이상의 작업이 서로 상대방의 작업이 끝나기를 무한정 기다리는 상태.

멀티 쓰레드 프로그래밍에서 동기화를 통해 락을 획득하여 자원을 여러 곳에서 함부로 사용하지 못하게 한다. 두 개 이상의 쓰레드에서 서로 가지고 있는 락이 해제되기를 기다리는 상태(교착상태)가 되는 것을 막기 위함이다.

---

임계영역

두 개 이상의 스레드가 특정 자원을 공유하고 있을 때, 한 번에 하나의 스레드에게만 접근을 허용하고자 하는 영역

한 스레드가 자원을 점유하면, 다른 스레드는 자원을 점유한 스레드가 종료될 때까지 기다려야 한다.

---

교착상태 발생조건

상호배제(mutual exclusion) :

• 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 사용중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.

점유대기(Hold And Wait) :

 

• 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.

비선점(Non - Preemptive) :

• 이미 할당된 자원을 강제로 빼앗을 수 없다.(비선점)

순환대기(Circle Wait)

• 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

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

자원에서 프로세스로 향하는 간선(R → P) 은 P가 R을 점유 중이라는 뜻이고 프로세스에서 자원으로 향하는 간선(P → R)은 P가 R을 대기 중이라는 뜻이다. 프로세스는 동그라미, 자원은 네모로 나타낸다.

---

교착상태 해결방법

상호배제(mutual exclusion) :

• 상호배제가 필요하지 않은 작업의 경우 자원을 공유하여 사용
• 읽기 전용 파일

점유대기(Hold And Wait) :

• 프로세스가 자원을 요청하려면 다른 자원들을 가지고 있지 않다는 것을 보장함으로써 교착상태를 예방한다.
• 첫번째 방법은 프로세스가 실행되기 전에 반드시 모든 자원을 요청하여 할당 받게 하는 것이다.
• 두번째 방법은 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 강제하는 것이다.

첫번째 방법 : 자원 낭비 발생 위험이 있다.

두번째 방법 : 프로세스의 우선순위가 낮은 경우 계속해서 자원을 할당 받을 수 없어 기아 상태 발생이 가능하다.

 

비선점(Non - Preemptive) :

• 자원을 섬점 가능하게 한다.
• 어떤 프로세스가 하나의 자원을 점유하고 있는 상태에서 즉시 할당할 수 없는 다른 자원(무조건 대기해야하는 자원)에 대해 요청을 하면, 현재 점유 중인 자원이 선점되게 하는 것이다.

* 기존에 실행중이던 프로세스가 중단되어 작업 내용을 잃을 수 있다. 자원 낭비 발생

 

순환대기(Circle Wait) :

• 모든 자원에 할당 순서를 부여하여 제어한다.
• 불필요한 자원을 할당 받아 자원 낭비가 발생할 수 있고, 자원 할당 순서로 인해 불필요한 점유 시간이 길어져 전체적으로 비효율적인 처리가 발생할 수 잇다.

* 프로세스 1, 자원 A, B가 잇을 때, 자원 할당 순서를 A > B 라고 가정하면, 프로세스 1번은 자원 B를 점유하기 위해서는 반드시 자원 A를 먼저 점유해야 한다.

---

교착상태 회피

 

시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있다면 안정 상태(Safe State)에 있다고 한다.

 

이처럼 특정한 순서로 프로세스에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 교착상태가 발생하지 않는 순서를 찾을 수 있다면 그것을 안전 순서(Safe Sequence)라고 한다.

 

반면 불안정 상태는 안정 상태가 아닌 상황을 말한다. 즉, 교착상태 발생 가능성이 있는 상황이며, 교착상태는 불안정 상태일 때 발생할 수 있다.*교착상태는 불안정 상태의 부분집합

 

회피 알고리즘은 자원을 할당한 후에도 시스템이 항상 Safe State에 있을 수 있도록 할당을 허용하는 것이 특징이다.

 

회피 알고리즘 중 가장 유명한 것은 은행원 알고리즘이다.

---

은행원 알고리즘

• 프로세스 시작시 자신이 필요한 각 자원의 최대 개수를 미리 선언한다.
• 각 프로세스에서 자원 요청이 있을 때 요청을 승인하면 시스템이 안전한 상태(Safe State)로 유지되는 경우에만 자원을 할당한다.
• 불안정 상태(Unsafe State)가 예상되면 다른 프로세스가 끝날 때까지 대기 한다.

예를 들어,

• 어떤 은행이 100만원을 가지고 있다고 가정하자.
• 은행에 돈을 빌리려는 3명의 고객이 있다. 고객이 돈을 빌릴 때 빌리려는 돈이 충족되어야 일을 해결할 수 있고, 다시 빌린 돈을 갚을 수 있다.

예를 들어, 20만원이 필요하면 20만원이 있어야 해결하고, 빌린 돈을 갚을 수 있다. 10만원만 있을 경우, 해결하지도 못하고 다시 갚지도 못한다.

 

• 고객 세 명이 있고, 각각 40만원, 50만원, 60만원이 필요하다.
• 은행에서 세 명에게 각각 25만원씩 주기로 했다.
• 고객 세 명은 각각 15만원, 25만원, 35만원이 필요하다.

* 고객은 빌려러는 돈이 충족되어야 일을 해결하고, 돈은 다시 갚을 수 있다.

 

은행에는 지금 25만원이 남아있다.

이 경우,  15만원이 더 필요한 첫번째 고객에게 15만원을 빌려주고 일을 해결하고 갚을 때까지 기다렸다가 다른 고객에게 돈을 빌려주는 방법이 있다.

 

또 다른 방법은 두 번째 고객에게 남은 25만원을 빌려주고 일을 해결하고 갚을 때까지 기다리는 방법이 있다.

 

하지만 세 번째 고객은 은행에서 전부 빌려주더라도 일을 해결할 수 없다. 그러므로 돌려 받을 수 없다.

• 고객 1 - 고객 2 - 고객 3
• 고객 2 - 고객 1 - 고객 3 
• 고객 2 - 고객 3 - 고객 1

이 순서대로 모든 고객에게 돈을 빌려줄 수 있고, 이를 안전 순서열이 존재한다고 한다.

 

만약 60만원이 필요한 고객 3이 25만원이 아닌 45만원을 빌려달라고 한다면 은행에는 남은 돈이 5만원 밖에 없게 된다.

이 상황에서는 세 고객 중 아무도 일을 해결할 수 없고, 이 상태를 불안정 상태 또는 교착상태라고 한다.

 

은행원 알고리즘은 은행이 최소한 한 명에게 대출해줄 수 있는 금액을 항상 보유하고 있어야 한다는 개념에서 나온것이다.

 

은행원 알고리즘이 수행되기 위해서는 3가지가 필요하다.

• Max : 각 프로세스가 자원을 최대로 얼마까지 요청할 수 있는지
• Allocated : 각 프로세스가 현재 보유하고 있는 자원이 얼마인지
• Available : 시스템이 자원을 얼마나 보유하고 있는지

 

안전 상태는 시스템이 교착상태를 일으키지 않고, 각 프로세스가 요구한 양만큼 자원을 할당해줄 수 있는 상태로, 안전 순서열이 존재하는 상태이다.

 

불안전 상태는 안전 순서열이 존재하지 않는 상태, 즉 아무런 방법이 없는 상태이다. 교착상태는 불안전 상태일 때만 발생한다. 불안전 상태라고 해서 무조건 교착 상태인 것은 아니다.

 

교착상태 탐지

시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 것을 의미한다.

• 교착상태 발견 알고리즘, 자원 할당 그래프

교착상태 회복

 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것을 의미한다.

 

1. 프로세스 종료

교착상태에 있는 프로세스를 종료하는 것.

• 교착상태에 있는 모든 프로세스 종료
• 교착상태에 있는 프로세스들을 하나씩 종료해가며 교착상태 해결

2. 자원 선점

교착 상태에 있는 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하여 해당 프로세스를 일시정지 시키는 방법

 

자원 선점시 고려사항

 

- 희상자 선택(selection of a victim)

• 피해가 최소인 프로세스 선택
• 한 프로세스가 계속 선점되는 기아현상을 방지하기 위해 선점될 때마다 프로세스 우선순위를 높이는 것과 같은 방법을 사용

- 롤백(rollback)

• 선점된 프로세스를 문제가 없는 이전 상태로 롤백

* 프로세스가 실행되는 중간마다 해당 시점의 상태를 표시 해두는 검사점 지정(checkpoint) 방식을 이용

• 프로세스를 중지시키고 재시작

---

참고 :

https://oingbong.tistory.com/87

임계영역이란?

https://math-coding.tistory.com/175

[Java] 자바 쓰레드 교착상태(deadlock)

https://velog.io/@mdy0102/DeadLock

DeadLock이란?

https://drcode-devblog.tistory.com/297

[java/개념] 세마포어(Semaphore)와 뮤텍스(Mutex)

https://chanhuiseok.github.io/posts/cs-2/

[운영체제] 데드락(Deadlock, 교착 상태)이란?

https://jerry92k.tistory.com/20

[OS] Deadlock : 교착상태

https://velog.io/@seorim0801/%EC%9D%80%ED%96%89%EC%9B%90-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

은행원 알고리즘?