8주차

[stemmmm]

• 데드락

[jihojivenchy]

정의

• 둘 이상의 프로세스 혹은 스레드가 서로의 자원을 기다리며 영원히 실행을 멈춘 상태

데드락의 발생 원인

1. 상호 배제 (Mutual Exclusion): 한 번에 하나의 프로세스만 자원에 접근할 수 있도록 함
2. 점유 대기 (Hold and Wait): 자원을 가진 프로세스가 다른 자원의 할당을 기다릴 수 있음
3. 비선점 (No Preemption): 프로세스가 자원을 강제로 빼앗길 수 없음
4. 순환 대기 (Circular Wait): 서로 자원을 기다리는 프로세스들이 원형 고리처럼 연결되어 있음

• 위 네 가지 조건이 모두 만족할 때, 데드락이 발생할 수 있게 된다.

1. 상호 배제

• 한 번에 하나의 프로세스만 공유 자원에 접근할 수 있음

왜 데드락의 발생 원인이 되는 것인지?

• 프로세스 A와 프로세스 B가 있다고 가정
• A가 자원 X를 사용 중일 때, B는 자원 X에 접근할 수 없음. (상호 배제)
• 따라서 B는 X에 대한 A의 접근이 끝날 때까지 대기하게 된다.
• 결국 상호 배제는 프로세스의 대기 상태를 만들어낼 수 있음
• 상호 배제가 없을 경우, 여러 프로세스가 동시에 자원을 공유할 수 있기 때문에 데드락이 발생할 이유가 없다.

2. 점유 대기

• 프로세스가 공유 자원을 점유하고 있으면서, 다른 자원에 접근하기 위해 대기할 수 있는 특성

왜 데드락의 발생 원인이 되는 것인지?

• 프로세스 A와 프로세스 B가 있다고 가정
• A는 자원 X를 점유하고 있으면서, 자원 Y에 대한 접근이 필요함
• B는 자원 Y를 점유하고 있으면서, 자원 X에 대한 접근이 필요함
• 프로세스 A, B가 동시에 각각 자원 Y, X에 대한 접근을 요청하게 되면, 서로에게 필요한 자원을 점유하면서 대기하는 형태가 이루어짐
• 따라서 프로세스가 상호 의존적인 상태로 인해 데드락을 발생시킬 수 있다.

3. 비선점

• 특정 프로세스가 점유하고 잇는 공유 자원을 다른 프로세스가 강제로 선점할 수 없음

왜 데드락의 발생 원인이 되는 것인지?

• 프로세스 A와 프로세스 B가 있다고 가정
• A는 자원 X를 점유하고 있으면서, 자원 Y에 대한 접근이 필요함
• B는 자원 Y를 점유하고 있으면서, 자원 X에 대한 접근이 필요함
• A나 B중 하나의 프로세스가 다른 프로세스가 점유하고 있는 자원에 대해서 강제로 선점할 수 없기 때문에 지속적으로 대기 상태가 발생하게 되는 것
• 비선점은 결국 점유 대기 상태를 만들게 되고, 데드락의 발생 원인이 될 수 있음

4. 순환 대기

• 여러 프로세스가 원형 고리처럼 서로의 자원을 기다리는 상태를 의미

왜 데드락의 발생 원인이 되는 것인지?

• 프로세스 A, B, C가 있다고 가정
• A는 자원 X를 점유하고, 자원 Y에 대한 접근을 위해 대기하고 있음
• B는 자원 Y를 점유하고, 자원 Z에 대한 접근을 위해 대기하고 있음
• C는 자원 Z를 점유하고, 자원 X에 대한 접근을 위해 대기하고 있음
• 이런 형식으로 프로세스가 원형으로 연결되어 있음
• 각 프로세스는 순환적으로 상호 의존적인 상태가 되면서, 자신이 원하는 자원을 절대 얻을 수 없음
• → 데드락의 발생 원인
• 데드락의 여러 특징은 이러한 순환성에서 기인하고, 위의 세 조건에 비해 예측하기도 탐지하기도 가장 어려운 문제임
• 일반적인 순환대기의 경우, 자원에 우선순위를 매기는 등의 방식으로 해결이 가능

데드락 해결 방법

• 크게 예방, 회피, 탐지, 복구 4가지의 방법이 있음

1. 예방

• 말 그대로 데드락이 일어날 상황 자체를 미연에 방지하는 것임
• 데드락이 발생할 수 있는 네 가지 조건 중 하나 이상을 사전에 제거하여, 데드락이 발생할 수 없도록 설계하는 방법

[상호 배제 제거]

• 상호 배제는 한 번에 하나의 프로세스만 공유 자원에 접근할 수 있는 것이었음
• 따라서 여러 프로세스가 동시에 공유 자원을 접근할 수 있다면 데드락도 발생하지 않음
• 하지만, 많은 상황에서 데이터 레이스를 방지하기 위해 상호 배제가 사용되기 때문에 이를 제거하는 것은 현실적으로 적절하지 않은 방법임
• 공유 자원에 대해 읽기 작업만 이루어지는 경우, 상호 배제를 제거하는 것은 좋은 선택이다.

[점유 대기 제거]

• 점유 대기는 이미 프로세스가 자원을 점유한 상태에서 다른 자원을 추가로 요청하며 대기하는 상황이었음
• 따라서 이를 없애면, 특정 자원이 대기 상태에 놓여있지 않기 때문에 데드락이 발생하지 않음
• 점유 대기 제거 방법
  1. 프로세스가 실행을 시작할 때, 필요한 자원을 한번에 요청함
     • 필요한 자원을 모두 받고 시작하기 때문에 추가 자원 요청으로 인한 대기 상황이 발생하지 않음
     • 하지만 자원 활용에 대한 효율성이 떨어질 수 있음
  2. 점유 전 자원 해제
     • 프로세스가 추가 자원을 요청하기 전에 점유하고 있는 자원을 모두 해제 하기 때문에 다른 프로세스가 해제된 자원에 접근할 수 있음
     • 자원의 빈번한 해제 및 요청에 따른 오버헤드가 발생할 수 있음

[비선점 해제]

• 비선점은 한 프로세스가 자원을 점유하고 있는 다른 프로세스의 해당 자원을 강제로 선점할 수 없다는 것이었음
• 따라서 자원을 강제로 선점할 수 있다면, 데드락은 발생하지 않음
• 예를 들어, 프로세스 A가 자원을 점유한 상태에서 추가 자원을 요청할 때, 대기가 이루어져야 한다면, 점유한 자원을 강제로 해제하고, 대기 상태로 들어가게 할 수 있음
• 자원 회수 및 요청에 따른 오버헤드가 발생할 수 있음

[순환 대기 방지]

• 순환 대기는 여러 프로세스가 원형으로 서로의 자원을 기다리는 상태였음
• 프로세스가 자원을 요청하는 순서를 정함.
• 자원 요청이 고정된 순서대로만 이루어지기 때문에 서로가 자원을 기다리는 순환 고리가 형성되지 않음
• 프로세스의 복잡성이 증가할 수 있음

2. 회피

• 데드락이 발생 가능성을 확인하고, 조정하는 방법임
• 예방은 발생 조건을 미리 차단했다면, 회피는 미리 차단하지 않고 방지함

[안정 상태와 비완전 상태]

• 안전 상태: 시스템이 자원을 할당할 때, 모든 프로세스가 필요한 자원을 최대한 획득하고, 실행을 완료할 수 있는 상태
• 비안전 상태: 자원을 할당한 후, 일부 프로세스가 필요한 자원을 얻지 못해 교착 상태에 빠질 가능성이 있는 상태
• 회피 방법에서는 프로세스에 자원을 할당할 때, 데드락의 가능성을 확인함.
• 만약 자원 할당 후, 안전한 상태가 유지된다면 할당을 허용함
• 반면, 비안전 상태가 될 가능성이 있다면 자원 할당을 대기시킴

[은행가 알고리즘]

• 은행이 여러 고객에게 대출을 해줄 때, 모든 고객이 자원을 회수할 수 있는지 확인하는 방식과 유사함
• 프로세스들이 자원을 요청할 때, 시스템이 안전한 상태를 유지할 수 있는지 평가함

[은행가 알고리즘 작동 방식]

1. 최대 자원 요구량 정의: 각 프로세스가 필요로 할 수 있는 자원의 최대 요구량을 미리 선언함.
2. 현재 자원 상태 평가: 자원이 요청되면, 자원 할당 후에도 모든 프로세스가 실행을 마칠 수 있을지를 평가
3. 자원 할당 후, 안전성 평가: 자원 할당 후에 각 프로세스가 자원을 순서대로 얻을 수 있는지를 평가함.

[은행가 알고리즘 예시]

• 프로세스 A, B가 있다고 가정함
  1. 최대 자원 요구량: 프로세스 A는 최대 10개의 자원이 필요, 프로세스 B는 최대 7개의 자원이 필요힘
  2. 현재 자원 할당: 현재 A에게 5개의 자원이 할당되어 있고, B에게 3개의 자원이 할당되어 있음
  3. 새로운 자원 요청: A가 2개의 자원을 추가로 요청함
  4. 안전 상태 평가: A에게 2개의 자원을 할당한 후에도, 남은 자원을 활용해 모든 프로세스가 필요한 자원을 얻고 실행을 완료할 수 있는지 평가함.
  5. 유지할 수 있으면 자원을 할당해줌
  6. 유지할 수 없으면 자원 할당을 거부하고, A를 대기시킴

[장점]

• 예방처럼 모든 조건을 강제하지 않고, 실시간으로 데드락의 가능성을 평가하기 때문에 자원의 활용에 대한 효율성이 증가함.

[단점]

• 자원의 최대 요구량을 미리 알아야 함. → 현실에서는 예측이 힘듬
• 실시간 가능성 확인으로 인한 오버헤드가 발생할 수 있음

3. 탐지 및 복구

• 시스템이 데드락 상태에 빠졌는지 주기적으로 모니터링하고, 데드락이 발생했을 경우 이를 탐지하여 복구하는 방식
• 예방과 회피와 달리, 실제로 데드락이 발생했는지를 확인하는 데 중점을 둔다.

[탐지 방법]

• 자원 할당 그래프를 분석하는 것
• 자원 할당 그래프란 자원의 관계를 그래프로 표현한 것으로, 이를 분석하여 데드락 여부를 판단할 수 있음
• 해당 그래프를 탐지하기 위해 DFS, BFS 알고리즘을 사용하고, 만약 순환이 발견되면 데드락이 발생한 것으로 간주함

[장점과 단점]

• 장점: 자원 활용도 극대화
• 단점
  • 복구하기 위해 프로세스를 강제로 종료하거나 자원을 회수해야 하기 때문에 작업 손실 문제가 있을 수 있음
  • 탐지 주기에 대한 설정이 어려움
  • 탐지로 인한 오버헤드 발생