[CS] 데드락

두두·2023년 3월 25일

CS

목록 보기

1/14

📌 데드락

데드락(DeadLock)이란?

두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태
즉, 무한히 다음 자원을 기다리게 되는 상태를 말한다!
교착 상태라고도 함
➡️ 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생

✅ Process 1은 Resource1을 사용하고 있으면서 Resource2를 기다리고 있다.
✅ Process 2는 Resource2를 사용하고 있으면서 Resource1을 기다리고 있다.
➡️ 서로 자원 하나씩 가지고 다른 자원을 기다리고 있기 때문에 끝나는 프로세스가 없다.
즉, 두 프로세스는 무한정 wait에 빠져있음!

데드락의 발생 조건

아래 4가지 조건이 모두 만족해야 데드락이 발생할 수 있음

1️⃣ 상호 배제(Mutual Exclusion)
자원은 한번에 한 프로세스만 사용할 수 있음

2️⃣ 점유 대기(Hold and Wait)
프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다림

3️⃣ 비선점(No Preemption)
다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음
= 프로세스가 작업을 마친 후 자원을 자발적으로 반환할 때까지 기다림

4️⃣ 순환 대기(Circular Wait)
프로세스의 자원 점유 및 점유된 자원의 요구 관계가 원형을 이루면서 대기하는 조건.
각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있음

데드락 상태 해결 방법

예방과 회피 두가지가 있다.
각각에 대해서 정리를 해보자면!

예방(prevention)

위에서 정리한 4가지 교착 상태 발생 조건 중 하나를 제거하면서 해결하는 방법

상호배제 부정 : 모든 자원의 공유를 허용
점유대기 부정 :
필요한 모든 자원을 할당 ▶️ 자원 낭비 발생
자원을 점유하고 있지 않을 때만 다른 자원을 요청할 수 있도록 ▶️ 기아 상태 가능성
비선점 부정 : 할당 받을 수 없는 자원을 요청할 때 점유하고 있는 모든 자원을 반납하고 대기하게 함. ▶️ 자원 낭비 발생
순환대기 부정 : 자원을 선형으로 분류하여 고유 번호를 할당하고,
각 프로세스는 현재 점유한 자원의 고유번호보다 앞이나 뒤 한쪽 방향으로만 자원을 요구하도록 함 ▶️ 자원 낭비 발생

‼️ 이 방법들은 자원 사용의 효율성이 떨어지고 비용이 많이 드는 문제점이 있다.

회피(avoidance)

교착상태가 발생하기 전 교착상태를 예측하고 회피하는 방법

자원이 어떻게 요청될지에 대한 추가정보를 제공하도록 요구해
시스템에 circular wait가 발생하지 않도록 자원 할당 상태를 검사한다!

크게 자원할당 그래프 알고리즘과 은행원 알고리즘이 있다.

자원할당 그래프 알고리즘

자원 유형마다 인스턴스가 하나 있는 경우 사용!

자원 할당 그래프에 예약 간선을 추가한다.
- 예약 간선(claim edge) : 향후 요청할 수 있는 자원을 가리키는 점선으로 표시된 간선
프로세스 시작 전에 모든 예약 간선들을 자원할당 그래프에 표시한다.
프로세스는 예약 간선으로 설정한 자원에 대해서만 요청할 수 있고 주기가 형성되지 않을 때에만 자원을 할당 받는다.

그림이랑 같이 살펴보자.

여기서 프로세스P2가 자원R2를 요청하여 자원을 할당받는다면?!

짜잔~😇 Cycle이 생김!
따라서 자원 요청을 승인할 수 없음!

하지만 반대로 프로세스P1이 자원R2를 요청하여 자원을 할당받는다면 주기(cycle)가 발생하지 않아 자원을 요청하여 할당받을 수 있다!

은행원 알고리즘

각 자원 유형마다 다수의 인스턴스를 갖는 경우 사용!

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

그런데 이 회피알고리즘은
‼️ 회피할 수 있는 조건을 달성하기 어렵고
‼️ 자원을 요청할 때마다 회피 알고리즘을 사용하면 오버헤드가 크기 때문에
현실성 없는 방법이라고 한다

데드락 회복

교착상태 회복기법은 교착상태가 발생했을 때, 이 상황을 해결하는 기법이다!
아래와 같이 두가지 방법이 있다.

1. 사용자가 직접 처리

교착상태에 걸려있는 프로세스 중, 어느 하나의 프로세스를 사용자가 강제로 종료시켜 버리면 된다.

이를 통해 교착상태를 해결할 수 있다.

2. 시스템에 의해 처리

✅ 프로세스 중지

한 개 이상의 프로세스를 중지시킴으로써 교착상태를 회복하는 기법이

중지를 시키는 방법에는 또 두 가지가 있다.

교착 상태에 속해 있는 모든 프로세스를 중지
확실하게 교착상태 해결이 가능하지만, 비용이 많이 든다는 단점이 있다. 왜냐하면 프로세스들이 오랫동안 연산을 했을 경우, 이 결과들을 다 폐기하고 다시 처음부터 진행을 해야 하기 때문이다.
교착 상태가 해결될 때까지 한 프로세스씩 중지
모든 프로세스를 중지하는 것 만큼 비용이 많이 들지는 않지만, 모든 프로세스들을 탐색하면서 '교착상태 탐지 알고리즘'을 호출하여 교착상태 여부를 확인해야 하기 때문에 오버헤드가 크다는 단점이 있다.

✅ 자원 선점

프로세스들로부터 자원을 빼앗아서 교착상태가 해결 될 때 까지 다른 프로세스들에게 할당해 주는 방식

다만 아래와 같은 조건들을 고려해야 함!

선점 프로세스 선택
필연적으로 종료되어야 할 프로세스의 선택(희생자 선택)은 비용 최소화를 위해 선점의 순서를 결정해야 한다. 비용의 요인으로는 "프로세스가 점유하고 있는 자원의 수", "프로세스가 지금까지 실행하는데 걸린 시간" 등이 된다.
복귀(Rollback)
어떤 프로세스는 교착 상태 해결을 위해 완전히 중지시킨 후 재시작 해야 한다.
기아(Starvation)
비용에 근거한 희생자의 선택은 계속해서 동일한 프로세스가 희생자로 선택될 수 있다는 문제점이 있다. 따라서, 똑같은 프로세스가 계속해서 선점되지 않도록 방지해 주어야 한다. 하나의 방법으로는 비용에 "희생자로 선택된 횟수"를 포함시켜 주면 된다.