교착상태(DeadLock)가 무엇인가?

gooweon.tistory.com/137

프로세스와 스레드의 차이

위의 글에서 설명했듯이 멀티 프로세스와 멀티 스레드 프로그래밍에서 발생할 수 있는 이슈인 데드락에 대해 알아보자!

개념

• 데드락이란, 두 개 이상의 작업이 서로 상대의 작업이 끝나기만을 기다리느냐 결국 모두 아무것도 하지 못하는 상태

• t1 : 프로세스 1이 자원1을 얻었고 프로세스 2가 자원 2를 얻었다.
• t2 : 프로세스 1은 자원 2를 기다리고 프로세스2는 자원 1을 기다린다.
• 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠지게 된다.

 

위의 설명만으로는 조금 부족할 수 있다. 그렇다면 정확히 어떤 조건을 만족하면 교착상태에 빠지는지 대해 보도록 하자

발생조건

• 발생조건은 총 4가지가 있고 4가지 모두 성립해야 데드락이 발생
• 반대로 보면 하나라도 성립하지 않으면 데드락 문제 해결이 가능하다는 뜻이 된다.

1. 상호 배제 (Mutual Exclusion) - 자원의 특성
   • 프로세스 간의 공유 자원은 한 번에 하나의 프로세스만 할당된다. 즉 여러 프로세스가 동시에 공유 자원을 사용할 수 없다.
2. 점유 대기 (Hold and Wait) - 프로세스의 특성
   • 프로세스가 공유 자원을 점유하면서, 다른 공유 자원을 얻기 위해 대기하고 있는 상태를 말한다.
   • 프로세스 1이 자원 B를 점유하고, A를 사용하기 위해 대기하고 있다고 가정해본다. 동시에 다른 프로세스 2는 B를 사용하기 위해 대기하고 있는 상황! 프로세스 2는 1의 작업이 끝날 때까지 대기할 수밖에 없다.
3. 비선점 (No poreemption) - 자원의 특성
   • 프로세스가 한 자원을 점유하고 있으면 다른 프로세스가 뺏을 수 없다.
4. 순환 대기 (Circular Wait) - 프로세스의 특성
   • 다른 프로세스의 자원을 가지기 위해 대기하는 상황이 동그란 형태로 만들어 진 것 (사이클) 즉! 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 한다.

위 내용을 정리하면 상호배제에 의해 한 번에 프로세스 하나만 자원을 사용할 수 있고 비선점 특성으로 다른 프로세스는 강제로 자원을 빼앗을 수 없다. 여기서에서 서로 다른 공유 자원을 얻기 위해 점유 대기 상태가 되게 되는데 그 형태가 순환 대기를 띄어야 한다.

그렇다면 위에서 얘기 했듯이 발생조건 중 하나라도 해결하게 된다면 데드락이 안 걸리게 된다. 그 해결법은 크게 3가지로 분류할 수 있다.

• 데드락이 발생하지 않도록 예방(prevention) 하기
• 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance) 하기
• 데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복하기

1. 데드락 예방(prevention)

• 데드락의 발생조건 중 하나라도 발생하지 않게 하여 예방하는 방법
• 각각의 조건을 방지(부정)하여 데드락 발생 가능성을 차단한다.
• 하지만 시스템의 처리량이나 효율성을 떨어뜨리고 비현실적이다!

1. 자원의 상호 배제 조건 방지 : 모든 자원을 공유하는 것을 허용 
   
   • 동기화 관련 문제 발생
2. 점유 대기 조건 방지 : 필요자원을 한 번에 모두 할당하는 한다.
   • 필요하지 않은 순간에도 자원을 가지고 있는다.
3. 비선점 조건 방지 : 모든 자원에 대해 선점을 허용한다.
   • 다른 자원을 요구할 때 점유하고 있는 자원을 반납 하는 과정에서 자원 낭비가 심하다.
4. 순환 대기 방지 : 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.
   • 프로세스 순서의 증가 방향으로만 자원을 요청한다.

2. 데드락 회피(Avoidance)

• 교착 상태 발생시 피해 가는 방법
• 회피에서는 안정 상태(Safe State)와 불안정 상태(Unsafe State)가 있다.
  • 안정 상태 : 시스템이 어떤 순서든 교착 상태를 일으키지 않으면서 프로세스들이 요청하는 모든 자원을 할당해 줄 수 있는 상태이며 이처럼 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면, 그것을 안전 순서(Safe Sequence)라고 부른다.
  • 불안전 상태 : 안전 순서열이 존재하지 않는 상태, 즉! 데드락 발생 가능성이 있는 상황
• 불안정 상태가 교착 상태보다 좀 더 큰 집합( 교착 상태가 불안정 상태의 부분집합)
• 교착 상태는 불안정 상태이지만, 불안정 상태는 교착 상태가 아닐 수 도 있다.

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

은행원 알고리즘(Banker's Algorithm)

• 프로세스에서 리소스 요구 시 프로세스에 리소스를 할당한 후에도 이상이 없으면 리소스를 할당하고 그렇지 않으면 할당하지 않는다.
• 안정 상태가 될 것이 100%로 보장되는 경우에만 요청을 받아들인다.
• 은행에 2000원이 있고, 고객 3명이 동시에 대출을 요청하는 상황이라고 가정해보자

• 이때 현재 가지고 있는 자원인 2000원으로 안정 상태를 만들 수 있는 고객은? A와 C이다.
• 이렇게 현재 가지고 있는 자원으로 안전 상태를 만들 수 있는 경우에만 자원을 할당해준다.

문제점

• 할당할 수 있는 자원의 수가 일정해야 한다.
• 사용자 수가 일정해야 한다.
• 항상 불안전 상태를 방지해야 하므로 자원 이용도가 낮다.
• 최대 자원 요구량을 미리 알아야 한다.
• 프로세스들은 유한한 시간 안에 자원을 반납해야 한다.

위 같은 문제점들로 인해 실제 돌아가는 프로그램에 적용하기가 어렵다.

 

3. 탐지(Detection) 및 회복(Recovery)

• 데드락이 발생하면 빠르게 발견하여 문제를 해결하는 방법

탐지 기법

• Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색한다.
• 이외에도 RAG(Resource Allocation Graph)라는 그래프의 Graph reduction 방법을 사용해서 알 수 있다.

회복 기법

• 데드락을 발견했다면, 순환 대기 조건에서 벗어나 데드락으로부터 회복하기 위한 방법
• 프로세스 종료 방법
  • 교착 상태의 프로세스를 모두 중지
  • 교착 상태가 제거될 때까지 하나씩 프로세스 중지 및 재시작
• 자원 선점 방법
  • 데드락 상태 해결을 위해 선점할 자원을 선택
  • 데드락 상태의 프로세스가 점유하고 있는 자원을 선점해서 다른 프로세스에게 할당

 

 

출처

• jwprogramming.tistory.com/12
• chanhuiseok.github.io/posts/cs-2/