[OS/운영체제] Deadlock / 교착상태

1. Deadlock이란?

• 두개 이상의 프로세스나 스레드가 서로의 작업이 끝나기만을 기다리며 무한정 대기하며 자원을 얻지 못하는 상태.

2. Deadlock 해결 방법

Deadlock을 해결하는 방법은 간단히 아래와 같이 요약해볼 수 있다.

1. Deadlock 예방 : Deadlock이 발생하기 이전에 데드락 발생원인 중 하나를 제거함으로써 Deadlock을 예방하는 방법

2. Deadlock 회피 : 각 프로세스가 프로세스를 실행하는데 필요한 정보를 추가적으로 받아서 Deadlock을 일으키지않는다고 판단되면 자원을 할당해주는 방법

3. Deadlock 탐지 : 교착 상태가 발생했을 때마다 복구 기법을 활용하여 시스템을 회복시키는 방법. 

4. Deadlock 무시 : 그냥 데드락이 일어날 때 까지 방치했다가 데드락이 발생하면 프로세스를 종료하는 것과 같이 사용자에게 선택을 위임하는 방법. 데드락은 자주 발생하는 문제가 아니기 때문에 최신 OS들은 모두 이 방법을 사용하고 있다. 

위의 방법들을 아래에서 자세히 살펴보자

3. Deadlock 예방 방법

Matual Exclusion

Critical Section에서 발생하는 문제를 해결하기 위해 matual Exclusion은 반드시 지켜져야 할 원칙이다. 동기화 문제가 발생할 수 있는 자원의 경우 반드시 성립해야하는 조건이기 때문에 현실적으로 불가능하다.

Hold and Wait

Hold and Wait을 해결하는 방법은 두가지가 있다. 차례대로 살펴보자

1. 프로세스를 시작할 때 실행에 필요한 모든 자원을 할당받고 실행하는 방법

- 위의 문장만 읽어봐도 엥 이게 맞나? 라는 생각이 들것이다. 이 방법은 처음에 이미 다 할당받았기 때문에 중간에 다른 자원을 필요로하는 상황이 생기지 않아 Deadlock을 발생시키지 않기 때문에 결론적으로는 예방한 게 맞다. 하지만 언제 쓸지 모르지만 조금이라도 필요한 가능성이 있으면 전부 할당받기 때문에 비효율적이다.

2. 자원이 필요할 경우 가지고 있던 모든 자원을 다 반납하고 다시 할당받는 방법

1번 방법처럼 모든 자원을 할당받지 않기 때문에 자원을 보다 효율적으로 사용할 수 있다. 또한 추가적으로 자원이 필요할 경우 점유하고 있던 모든 자원을 반납한 후 필요한 자원만 다시 할당받기 때문에 Deadlock을 예방할 수 있다.

No Preemption

자원을 필요로하는 다른 프로세스가 요청을 할 경우 자원을 넘겨줄 수 있도록 해서 Deadlock을 해결하는 방법이다. 프로세스는 Context Switching할 때 진행 상황을 PCB에 저장하고 다시 자원을 할당 받으면 이전에 실행되면 부분부터 다시 실행한다. 이처럼 진행 상황을 쉽게 저장하고 불러올 수 있는 CPU와 Memory자원에 한해 사용할 수있다. 

Circular Wait

자원을 할당받을 수 있는 순서를 정해놓고 무조건 순서대로만 할당받을 수 있도록 하는 방법이다.

예를들어 자원2를 할당받기 위해서는 자원1을 소유해야 한다는 조건을 걸어놓고 자원1을 소유한 프로세스한테만 자원2를 할당해주는 방법이 있다

 

여기까지만 읽어보면 이상한데?

읽어보면 굳이 이렇게까지 해야하나?라는 생각이 든다. Hold and Wait부분에서는 자원낭비가 심하고, Circular Wait부분에서는 효율성이 낮아질 것 같다. 그리고 Deadlock은 실제로 흔하게 발생하는 상황이 아니기 때문에 Deadlock이 일어나기 전에 지레 겁먹고 예방하는건 자원낭비며 효율성이 떨어지기 때문에 현대의 운영체제에서는 실제로도 적용하지 않는다.

4. Deadlock 회피 

데드락 을 회피하기 위해서는 프로세스를 실행하며 데드락 이 발생할 상황인지를 체크하고 만약 데드락 이 발생할 가능성이 있으면 그 상황 자체를 피해버리는 방법이다. 하지만 데드락을 회피하기 위해서는 아래와 같이 어느정도 상황을 정해놓아야 한다.

1. 프로세스에게 자원을 할당하기 전에 이미 프로세스가 얼마 만큼의 자원을 요구하는지 파악해야한다.

2. 할당할 수 있는 자원의 갯수와 종류가 고정되어 있어야 한다.

3. 프로세스의 갯수 또한 고정되어 있어야 한다.

4. 프로세스는 자원을 사용 후 반드시 반납해야 한다.

회피하는 방법의 대표적인 알고리즘인 Banker's Algorithm에 대해 너무 길어져서 포스팅을 나눴다.

 

[OS/운영체제] Banker's Algorithm / 은행원 알고리즘

5. Deadlock Detection & Recovery

Deadlock Detection

5-1. 자원의 인스턴스가 하나일 때

출처 : https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/7_Deadlocks.html

(a) Resource-Allocation-Graph. (b) Wait-For-Graph

자원의 인스턴스가 하나일 경우 자원 대기 그래프를 사용해서 데드락의 사이클을 확인할 수 있다.

우측의 Allocation-Graph를 보면 P4는 P1이 자원을 놓아줄 때 까지 기다려야 한다. 이처럼 자원에 대한 관계도를 서로가 필요로 하는 인스턴스를 가지고있는 프로세스로 이은 Wait-For-Graph로 바꿔보면 우측과 같아진다. 위의 Wait-For-Graph에서는 P1-P2-P3 / P1-P2-P3-P4 총 두개의 사이클이 존재함으로 데드락이 있다고 판단할 수 있다.

5-2. 자원의 인스턴스가 두개 이상일 때

자원의 인스턴스가 두개 이상일 때 탐지 알고리즘을 사용해서 브루트 포싱을 통해 자원을 정상적인 상태를 유지하며 할당해줄 수 있는지를 조사한다. 먼저 탐지 알고리즘에 사용되는 변수에 대해 알아보자

Allocation : 각 프로세스에게 할당된 자원의 갯수.

Request : 각 프로세스가 요청하는 자원의 갯수

Available : 프로세스가 요청시 할당해줄 수 있는 자원의 갯수

아래의 그림을 통해 살펴보자

출처 : https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/7_Deadlocks.html

결론부터 말하자면 위의 상태는 Deadlock이 발생하지 않는 상황이다.

프로세스는 실행을 완료하면 할당받은 자원을 모두 반납한다. 그렇기 때문에 P2를 먼저 실행하고 완료하면 Available은 A-3, B-0, C-3으로 가용 자원이 늘어나게 된다. 그럼 A자원 2개, C자원 2개를 요청하는 프로세스 P1또한 실행시킬 수 있고 완료하게 되면 원래 P1이 가지고 있던 자원인 A자원 2개가 추가로 반납되기 때문에 계속해서 다른 프로세스들에게 할당해줄 자원이 늘어나는 것이다. 그래서 <P2, P1, P0, P3, P4> 순서대로 실행시키게 되면 교착상태 없이 실행이 가능하다. 당연히 <P0, P2, P1,P3, P4>와 같이 다른 순서로도 실행 가능하다.

이번에는 반대의 경우를 살펴보자

이전 상황과 비슷하지만 여기서는 P2가 C자원 하나를 추가적으로 요청하는 차이가 있다.

이 상황에서는 C자원 하나가 있어야  P2의 자원을 회수하고 P2의 자원을 회수해서 다른 프로세스들의 자원 요청을 처리줄 수 있지만, 아무것도 요청하지 않는 프로세스인 P0를 실행 완료하고 자원을 회수해봤자 다른 프로세스들의 요구를 충족시켜줄 자원이 없기 때문에 P1, P2, P3, P4가 Deadlock에 놓이게 된다.

 

이처럼 데드락이 발생하는 상황에서 그냥 냅두면 시스템이 멈추기 때문에 상태를 회복시켜줘야 한다. 이제 회복에대해 알아보자

Deadlock Recovery

1. 프로세스 종료(Process Termination)

실행중인 모든 프로세스를 종료하는 방법

• 확실하게 데드락을 해결할 수 있는 방법이다.
• 하지만 실행중인 프로세스가 진행했던 연산 과정을 전부 무시하고 지우기 때문에 프로세스를 재실행 했을경우 처음부터 다시 연산을 시작해야하기 때문에 해결비용이 크다

실행중인 프로세스를 하나씩 종료하는 방법

아래와 같은 분류 기준을 통해 선별해서 데드락이 풀릴 때까지 프로세스를 종료한다. 아래의 기준은 항상 적용되는 것이 아닌 이런 유형이 사용될 수 있다는 의미이다.

1. 낮은 우선순위
2. 프로세스 실행 유지시간이 짧은것부터
3. 가지고있는 자원이 선점하기 쉽고 저장하기 쉬운지
4. 어떤 자원을 얼만큼 가지고있는지
5. 프로세스가 실행을 완료하는데 얼만큼의 자원을 필요로하는지
6. 몇개의 프로세스를 종료해야하는

하나씩 종료하는 방법은 프로세스 하나를 종료하고 데드락이 풀렸는지 확인하는 과정을 풀릴 때까지 반복하기 때문에 오버헤드가 크다.

2. 자원 선점(Resource Preemption)

자원 선점 방식을 선택하게 되면 아래의 문제 상황을 고려해야 한다.

1. 희생자 선택(Selecting a victim)

데드락이 걸린 상황에서 각 프로세스들이 할당받은 자원을 먼저 선점해서 실행을 완료하고 반납한 자원을 가지고 교착상태를 풀기 때문에 우선적으로 자원을 뺏길 프로세스를 정해야 한다.

2. Rollback

프로세스를 safe한 상태로 rollback 시켜놨더니 또 다른 프로세스가 동일한 자원을 요청해서 또다시 동일한 상황의 데드락이 발생할 수도 있다. 그렇기 때문에 적절한 상황을 잘 찾아야하지만 어렵다.

3. 기아 문제(Starvation)

하나의 프로세스만 계속 자원 선점 대상에 선정되면 영원히 실행을 못하기 때문에 기아 문제를 고려해야 한다. 

6. Deadlock Ignorance

데드락의 마지막 해결방법이자 가장 간단하고 현대의 대부분의 운영체제가 채택한 방법인 데드락을 그냥 신경쓰지 않는 방법이다.

Deadlock은 매우 드물게 발생하고 앞에서 봤듯이 해결하는 방법 자체의 오버헤드가 데드락이 발생했을 때의 오버헤드보다 크기 때문에 Deadlock이 일어날 상황 자체를 생각하지 않고 만약 데드락이 발생했다면 사용자가 직접 프로세스를 종료하는것과 같은 방법으로 대처한다.

 

CS 지식을 공부하고 기록하는 개인 공부 블로그입니다.
내용 중 틀린 부분 피드백 혹은 궁금한 점이 있으면 댓글로 남겨주시면 참고 및 답변 달아드리겠습니다🧐