[CS] 데드락

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

 

☑️ 데드락의 발생조건

• 상호 배제
  • 한 번에 프로세스 하나만 해당 자원을 사용할 수 있음.
  • 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 함
• 점유 대기
  • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 함
• 비선점
  • 이미 할당된 자원을 강제로 빼앗을 수 없음
• 순환 대기
  • 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 함

 

☑️ 데드락의 해결방법

📌 데드락 예방(Prevention)

: 데드락의 발생조건 4가지 중 하나라도 발생하지 않게 하는 것 (각각의 조건을 방지하여 발생가능성 차단)

• 자원의 상호 배제 조건 방지 : 한번에 여러 프로세스가 공유 자원을 사용할 수 있게 함
  • but, 추후 동기화 관련 문제가 발생할 수 있음
• 점유 대기 조건 방지 : 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또 다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 함
• 비선점 조건 방지 : 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선 순위의 프로세스가 해당 자원을 선점할 수 있도록 함
• 순환 대기 조건 방지 : 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 함

👉🏻 이러한 조건을 방지해서 데드락을 예방하는 방법은 시스템의 처리량이나 효율성을 떨어트리는 단점이 발생 할 수 있음

 

📌 데드락 회피(Avoidance)

• 안정 상태(Safe State) : 시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있는 상태
• 안전 순서(Safe Sequence) : 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서
• 불안정 상태는 안정상태가 아닌 상황을 말함 → 데드락 발생 가능성이 있는 상황
  • 교착 상태(데드락)는 불안정 상태일 때 발생할 수 있음
  • 즉, 불안정 상태가 교착 상태보다 좀 더 큰 집합
• 회피 알고리즘은 자원을 할당한 후에도 시스템이 항상 Safe state에 있을 수 있도록 할당을 허용하자는 것이 기본 특징 → 은행원 알고리즘
• 🔑 **은행원 알고리즘**(Banker’s Algorithm) 어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션하여 Safe state에 들 수 있는지 여부를 검사함. (즉, 대기중인 다른 프로세스들의 활동에 대한 교착 상태 가능성을 미리 조사하는 것)→ 미리 최대 자원 요구량을 알아야 하고, 할당할 수 있는 자원 수가 일정해야하는 등 사용에 있어 제약조건이 많고, 그에 따른 자원 이용도 하락 등 단점도 존재

📌 데드락 탐지(Detection) 및 회복(Recovery)

• 시스템이 데드락 예방이나 회피법을 사용하지 않았을 때 데드락이 발생할 수 있음
  → 이 데드락을 회복하기 위해 데드락을 탐지하고, 회복하는 알고리즘을 사용

• 탐지 기법
  • Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색
    → 현재 시스템의 자원 할당 상태를 가지고 파악
  • 자원 할당 그래프를 통해 탐지
• 회복 기법 : 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용
  • 단순히 프로세스를 1개 이상 중단
    • 교착 상태에 빠진 모든 프로세스를 중단시키는 방법 : 계속 연산 중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생할 수 있음
    • 프로세스를 하나씩 중단시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법 : 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 죄는 작업일 수 있음
  • 자원 선점하기
    • 프로세스에 할당된 자원을 선점해서 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해주는 방법