[OS] 데드락, DeadLock

Deadlock 이란

• 시스템 자원에 대한 요구가 뒤엉킨 상태
• 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황

시스템이 자원을 획득하는 과정

1. 요청 (Request)

프로세스가 시스템에게 특정 자원을 요청하면 시스템은 현재 이 자원이 사용 가능한지를 판단한 후 가능하다면 프로세스에게 할당한다. 만일 자원이 다른 프로세스에게 점유되어 있다면 요청한 프로세스는 요청한 자원이 사용 가능해질 때 까지 기다린다.

2. 사용 (Use)

자원에 대한 허가가 떨어지면 프로세스는 자원을 사용할 수 있다.

3. 해제 (Release)

프로세스는 자원의 사용이 끝나면 시스템에게 반환 요청을 한다. 시스템은 사용이 끝난 자원을 반환 받아 해당 자원을 필요로 하는 프로세스가 있다면 할당해준다.

💡'요청 -> 사용 -> 해제' 과정의 예)
프로세스가 파일(자원)에 대한 권한을 획득하고 돌려주기 위해 open과 close 시스템 콜을 호출 한다던지, 메모리(자원)를 확보하고 해제하기 위해 allocate와 free를 호출하는 것과 같은 모든 행동들이 위에서 언급한 '요청 -> 사용 -> 해제' 과정에 속하는 것들이다. 

데드락은 특정 셋(set)에 속한 모든 프로세스가 '자원이 사용 가능해 질때까지 기다리는 상태', 즉, 대기 상태(wait state) 상태에서 빠져 나오지 못하는 상태를 말한다.

Deadlock 발생 조건

아래 네가지 조건이 모두 성립해야 데드락이 발생한다!

1. 상호 배제 (Mutual Exclusion)

• 한번에 오로지 하나의 프로세스만이 자원 선점 가능
• 여러 프로세스가 공유하는 공유 자원에 대한 접근이 제한됨
• 만약 자원이 A 프로세스에게 할당 되어 있는 중 B 프로세스가 이 자원에 대한 요청(Request)를 한다면, 그 B 프로세스는 A 프로세스가 자원을 반환 할 때 까지 대기 상태에 머무른다.

2. 점유와 대기 (Hold and wait)

• 공유 자원에 대한 접근 권한을 가지고 있는 프로세스가 다른 자원에 해단 접근을 요구할 수 있음

3. 선점 불가 (Preemption)

• 한 프로세스가 다른 프로세스의 자원 접근 원한을 강제로 뺏어올 수 없음
• 자원 획득에 우선권이 존재하지 않음
• 자원을 획득 할 수 있는 유일한 방법은 다른 어떤 프로세스도 해당 자원을 점유하고 있지 않을 때 뿐!

4. 순환 대기 (Circular Wait)

• 두 개 이상의 프로세스가 자원 접근을 기다리는데 그 사이에 순환이 존재함

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

• 프로세스가 자원을 요청하고 자원이 프로세스에게 할당되는 방향성을 가진 그래프
• 데드락 발생 여부를 탐지할 수 있다!
• 자원들은 모두 mutual exclusion 이라 가정함

(Resource 내의 까만 점들은 각 자원 타입이 할당 가능한 자원 인스턴스 갯수를 의미)

• P1은 R2의 자원을 점유하고 R1의 자원을 대기 중
• P2는 R1과 R2의 자원을 점유하고 R3의 자원을 대기 중
• P3은 R3의 자원을 가지고 있지만 아무런 추가 자원을 요청하지 않음
• P3가 끝나면 P2가 R3 를 점유할 수 있으므로 순환 대기 상태가 아님!

• P3 -> R2 -> P2 -> R3 -> P3ㅁ
• P3 -> R2 -> P1 -> R1 -> P2 -> R3 -> P3
• 순환 대기 상태, 데드락 발생!

데드락 예방 (Deadlock Prevention)

• 데드락의 발생 조건 4가지 중 한가지를 제거

1. 상호 배제 조건 제거

• 상호 배제(mutual exclusion)이라는 것은 공유가 불가능한 자원을 소유하고 있는것을 의미
• 그렇다면 자원을 공유 가능하도록 만들면 데드락은 발생하지 않음!

  예) Read-only 파일
  만일 업데이트가 필요 없는 파일이라면 read-only권한으로 자원을 점유 할 수 있다. 파일에 변경이 없으니 여러 프로세스가 동시에 이 파일에 접근 가능하고, 이는 자원을 점유하기 위해 대기하는 프로세스가 없다는 뜻이다. 이로써 상호 배제 조건이 만족하지 않으므로 데드락은 발생 할 수 없다. 하지만 업데이트가 필요한 파일과 같이 어떠한 이유로든 동시에 접근하는 것을 허용하지 못하는 자원의 경우 상호 배제 방지는 적용 할 수 없다!

• 한 번에 여러 프로세스가 공유 자원을 사용할 수 있도록 해 상호 배제를 방지한다면 추후 동기화 관련 문제가 발생할 수 있음!

2. 점유 대기 조건 방지

• 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류
• 나중에 또다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록
• 당장 사용하지 않는 자원을 작업이 끝날때까지 불필요하게 점유하고 있을 수 있는 성능상 단점이

3. 비선점 조건 방지

• 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록

첫번째 방법

• 어떤 자원을 이미 점유하고 있는 프로세스가 당장 할당 받을 수 없는 다른 추가 자원을 요청한다면 요청 프로세스가 가지고 있는 모든 자원들을 선점형으로 바꿈
• 요청 대기 상태에 빠지는 프로세스의 모든 자원을 암묵적으로 해제(Release)
• 해제된 리소스들은 요청 대기 자원 리스트에 들어가고, 프로세스는 새로 요청한 자원과 이전에 가지고 있던 자원 모두를 획득 했을 때만 대기 상태에서 벗어나 작업을 다시 시작 할 수 있음

두번째 방법

• 프로세스가 자원을 요청하면 대상 자원이 현재 아무런 프로세스에게 할당 되어있지 않은지 확인
• 어떤 프로세스도 해당 자원을 점유하고 있지 않다면 요청 프로세스에게 자원을 할당
• 만일 대상 자원이 이미 다른 프로세스에게 할당 되어 있고, 그 다른 프로세스가 추가 자원을 대기 중이라면, 다른 프로세스로 부터 해당 자원을 빼앗아 요청 프로세스에게 할당
• 만일 대상 자원이 이미 다른 프로세스에 의해 사용 중이라면 요청 프로세스는 대기 상태로
• 이 상태에서 만일 다른 프로세스가 요청 프로세스가 가지고 있는 자원을 요구하면 그 자원을 해제하여 선점 가능하도록
• 요청 프로세스는 필요한 모든 자원이 할당 될때까지 대기 상태에 머무른다

4. 순환 대기 조건 방지

• 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 함
• 모든 프로세스가 획득 하는 자원의 순서를 동일하게 맞춤
• 모든 자원마다 고유의 번호를 부여하고 필요한 자원을 번호가 작은 것 부터 큰 순서대로 획득하도록 한다면 추가로 필요한 자원들이 어떠한 프로세스에게도 점유 되어 있지 않음을 보장

간단히 데드락을 해결할 수 있을 듯 보이지만, 사실 이러한 예방 방법은 시스템의 처리량이나, 효율성을 떨어뜨리는 단점이 존재한다. 이렇듯 이것저것 안되는게 많은 예방 보다 좀 덜 제한적인 회피 방법도 존재 한다.

데드락 회피 (Deadlock Avoidance)

• 데드락 예방 방법은 프로세스는 당장 사용하지 않는 자원을 점유하고 있어야 하거나, 이미 할당 되었던 자원을 반납해야 하는 등의 전체 성능을 낮추어야 하는 단점이 존재함!
• 데드락 회피 알고리즘들은 자원 요청 시 '추가 정보(알고리즘 마다 다름)'도 함께 요구
• 요청한 정보들을 바탕으로 현재 자원 할당 상태를 검사하여 순환 대기 상태가 발생하는 것을 원천적으로 막음

프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 데드락을 회피하는 방법! 안정 상태면 자원 할당하고 아니면 다른 프로세스들이 자원을 해지하기까지 대기한다.

안정 상태 (safe state)

• 시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있다면 안정 상태 (safe state)에 있다고 함
• 시스템이 각 프로세스들에게 데드락을 피할 수 있는 안전한 순서(safe sequence)로 자원을 배분 할 수 있는 상태를 의미

안전 순서 (safe sequence)

특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면, 그것을 안전 순서(safe sequence)라 함

불안정 상태

• 안정 상태가 아닌 상황
• 락 발생 가능성이 있는 상황이며, 교착 상태(데드락)는 불안정 상태일 때 발생
• 불안정 상태가 교착 상태보다 좀 더 큰 집합 즉, 교착 상태가 불안정 상태의 부분집합

1. 자원 할당 그래프 알고리즘 (Resource-Allocation Graph Algorithm)

• 각 자원 타입들이 하나의 인스턴스만을 가질 때 사용
• 자원 할당 그래프 에 예약 간선 (claim edge) 라는 개념이 추가됨
  • 예약 간선 (claim edge) : 미래에 해당 프로세스가 가리키고 있는 자원을 요청할 것이라는 것을 의미함
• 예약 간선을 그렸을 때 cycle 이 탐색되지 않으면 해당 자원을 할당 해 주어도 시스템은 안정상태에 머무름
• cycle 이 생긴다면 해당 자원 할당 시 시스템이 불안정 상태가 될 수 있음을 의미

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

• 각 자원이 여러개의 인스턴스를 가질 때
• 새로운 프로세스가 시작할 때 자신이 가지고 있어야 할 자원의 최대 개수를 선언한다.
• 시스템은 이 요청을 들어주었을 때 시스템이 그대로 안전한지를 판단하고
• 안전하다면 해당 요청을 들어주고, 불안전해진다면 해당 프로세스는 다른 프로세스가 끝날 때 까지 대기한다.

필요한 자료구조

1. Available

• 길이 m, 각 종류 별로 사용 가능한 자원의 개수를 나타내는 벡터
• Available[j] = k라는 뜻은 현재 j라는 자원을 k개 사용할 수 있음을 뜻함

2. Max

• 크기 n x m, 각 프로세스가 최대로 필요로 하는 자원의 개수를 나타내는 행렬
• Max[i,j] = k 라면, i라는 프로세스가 j라는 자원을 최대 j개까지 요청할 수 있음을 뜻함

3. Allocation

• 크기 n x m, 각 프로세스들이 현재 사용하고 있는 자원의 개수를 나타내는 행렬
• Allocation[i, j] = k라면 현재 i라는 프로세스가 j라는 자원을 k개 사용하고 있음을 뜻함

4. Need

• 크기 n x m, 각 프로세스가 사용할 수 있는 남은 자원의 개수
• Need[i,j] = k 라면 i라는 프로세스가 j라는 자원을 k개까지 더 요청할 수 있음을 뜻함
• Need[i,j] = Max[i,j] - Allocation[i,j]

안정성 알고리즘 (Safety Algorithm)

• 현재 시스템이 안전한 지를 검사하는 알고리즘은
• Work는 크기가 m, Finish는 크기가 n인 벡터

1. Work = Available로 초기화해주고, 모든 i에 대해 Finish[i] = false로 초기화해줍니다.
2. Finish[i] == false이고, Need[i] <= Work인 i를 찾습니다. 만약 찾을 수 없다면 4번째 단계로 넘어갑니다.
3. Work = Work + Allocation[i], Finish[i] = true를 해준 뒤, 2번째 단계로 돌아갑니다.
4. 모든 i에 대해 Finish[i]==true라면, 해당 시스템은 안전하다고 할 수 있습니다.

2. 자원 요청 알고리즘 (Resource-Request Algorithm)

• 자원 요청을 안전하게 승인해 줄 수 있는지에 대해 검사하는 알고리즘
• Request[i]는 i라는 프로세스의 요청 벡터
• 만약 Request[i][j] = k라면, i라는 프로세스가 j라는 자원을 k개 요청하고 있다는 뜻
• 프로세스 i가 자원을 요청하게 되면

1. 만일 Request[i] <= Need[i] 라면, 즉, 프로세스의 요청이 시스템이 허용해 줄 수 있는 개수보다 적다면, 2번째 단계로 갑니다. 그렇지 않다면, 이미 시스템에 남아있는 개수보다 더 많은 요청이므로, 오류로 처리합니다.

2. 만일 Request[i] <= Available 이면, 즉, 요청한 자원이 현재 남아있다면, 3단계로 갑니다. 그렇지 않다면, 현재 요청한 자원이 당장은 없으므로 프로세스는 대기해야 합니다.

3. 시스템이 자원을 할당해 줄 수 있으므로, 다음과 같이 상태를 변경해줍니다.

• Available = Available - Request[i]
• Allocation[i] = Allocation[i] + Request[i]
• Need[i] = Need[i] - Request[i]

이렇게 변경한 상태가 안전하다면, 프로세스 i에게 요청받은 자원들을 할당해줍니다. 그렇지 않다면, 다시 원래의 상태로 되돌려줍니다.

데드락 탐지(Detection)

필요한 자료 구조

1. Available

• 길이 m, 각 종류 별로 사용 가능한 자원의 개수를 나타내는 벡터
• Available[j] = k라는 뜻은 현재 j라는 자원을 k개 사용할 수 있음을 뜻함

2. Allocation

• 크기 n x m, 각 프로세스들이 현재 사용하고 있는 자원의 개수를 나타내는 행렬
• Allocation[i, j] = k라면 현재 i라는 프로세스가 j라는 자원을 k개 사용하고 있음을 뜻함

3. Request

• 크기 n x m, 각 프로세스가 요청한 자원 수를 의미함
• Request[i,j] = i 프로세스가 자원 j를 요청한 수를 의미

데드락 탐지 알고리즘

• 남아있는 프로세스들의 할당 가능 순서를 찾는다
• Work : 크기 m (자원의 개수) 의 1차원 벡터
• Finish : 크기 n (프로세스의 수) 의 1차원 벡터

1. Work = Available 로 초기화, Allocation[i] 가 0이 아니면 Finish[i] = false 로 그렇지 않으면 true로 Finish 를 초기화

2. Finish[i] 가 false 이고 Reques <= Work 인 프로세스를 찾는다. (요청한 자원들이 할당 가능한 프로세스 찾기) 없다면 4번으로 이동

3. Work += Allocation[i] (할당 후 프로세스가 끝나면 반환되는 자원원처리), Finish[i] = true (프로세스 종료) 후 2로 이동

4. 어떤 i 에 대해 Finish[i] = false 라면 (모든 실행 순서를 적용해도 실행하지 못하는 프로세스가 있다면) 이 시스템은 교착 상태에 빠져 있으며 해당 프로세스는 데드락 상태이다.

실행

1. 3가지 자원 A,B,C 에 대해 Work = (0,0,0), 5개의 프로세스에 대해 Finish = (F,F,F,F,F) 초기화

2. i=0

• Allocation[0] = (0,1,0) (P0 에 할당되어 있는 양)
• Request[0] = (0,0,0) <= Work 이므로 P0 실행 가능

3. P0 실행 후 자원이 해제되면

• Work += Allocation[0] (P0 이 원래 쥐고 있던 양) = (0,1,0)
• Finish = (T,F,F,F,F)

4. 0 다음으로 Finish = false 인 프로세스 중 실행 가능한 프로세스를 찾으면 P0 -> P2 -> P3 -> P1 -> P4 순서로 실행 가능

5. 모든 프로세스가 실행 되고 종료 후 Finish = (T,T,T,T,T) 가 되고 현재 교착 상태가 아님을 확인

은행원 알고리즘 VS 교착 상태 탐지 알고리즘

은행원 알고리즘	교착상태 탐지 알고리즘
Need : 각 프로세스나 스레드가 향후 요청할 수 있는 자원의 수	Request : 각 프로세스나 스레드가 현재 할당된 자원 말고도 요청하는 자원의 수
프로세스나 스레드가 자원을 요청할 때 데드락을 피하기 위해 최악의 상황까지 고려함	데드락이 발생했는지 확인하기 위해 탐색, 발생했다면 회복 알고리즘을 통해 회복함

교착 상태 탐지 알고리즘의 사용

교착 상태 탐지 알고리즘을 언제 사용해야 하는걸 까?

• 데드락이 얼마나 자주 일어나는가?
• 데드락 발생 시 통상 몇개의 스레드가 연류 되는가?

에 따라 결정할 수 있음

만약 데드락이 지나치게 자주 발생한다면 요청 할 때 마다 탐지 알고리즘을 호출하지만 그럴 경우 오버헤드가 커진다. 이러한 경우에는 지정된 시간 간격으로 (한시간에 한번 이라던지, CPU 이용률이 40% 이하로 떨어질 때 라던지) 알고리즘을 호출할 수 있다.

데드락 회복

데드락 회복을 위해서는 데드락 탐지 알고리즘과 데드락 회복 알고리즘이 필요하다! 데드락 탐지 알고리즘을 너무 자주 호출하게 되면 시스템 성능이 떨어질 수 있지만 교착 상태에 빠진 프로세스들을 빠르게 발견해 자원의 낭비를 방지할 수 있다.

데드락을 탐지 기법을 통해 발견했다면 다음 두가지 방법으로 대응 할 수 있다.

• 데드락 발생을 운영자에게 알려 직접 처리하도록
• 시스템이 자동으로 데드락으로부터 회복하도록

시스템이 자동으로 데드락으로부터 회복하도록

순환 대기를 깨뜨리기 위해 한 개 이상의 프로세스나 스레드를 중지시킨다.

• 교착상태인 프로세스를 모두 중지 시키기
  • 프로세스들의 연산 결과들을 모두 버리게 되므로 비용이 크다.
• 교착 상태가 해결될 때 까지 프로세스나 스레드를 하나씩 중지시키기
  • 각 프로세스가 중지될 때 마다 교착 상태 탐지 알고리즘을 호출해야 하므로 오버헤드가 커진다.

데드락 상태인 하나 이상의 프로세스나 스레드로부터 자원을 선점한다.

• 프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해 주는 방법

이 때 어떠한 자원을 선점할 프로세스를 경정하는 데에 세 가지 고려 사항이 있다.

• 희생자 선택
  • 각 프로세스가 점유하고 있는 자원의 수, 지금까지의 프로세스 실행 소요 시간과 같은 매개변수들을 고려해서 선택한다.
• 후퇴 : 자우너을 선점당한 프로세스를 어떻게 할 것인가?
  • 간단한 방법은 프로세스 자체를 종료하고 재시작하는 것
  • 교착 상태를 해결할 정도로만 프로세스를 후퇴시키는 것에는 많은 정보가 필요하다.
• 기아상태 : 희생자 선택 시 동일한 프로세스가 항상 희생자로 선택될 수 있음
  • 희생자 선택 시 한정된 시간 동안만 희생될 것을 보장해서 기아상태를 방지해야한다.

Reference

[운영체제] 데드락(Deadlock, 교착 상태)이란?
데드락이란?
[운영체제] Deadlock (3) - Deadlock Avoidance
[OS] 교착상태 해결 방법 예방, 회피, 탐지