CS OS Dead Lock(교착상태)

 

두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태

무한히 다음 자원을 기다리게 되는 상태를 말한다.

각각 자원을 점유한 상태에서 다른 프로세스가 점유한 자원을 기다리며 무한히 대기하는 상황이다.

 

 

ㅇ 데드락 발생 조건

데드락이 발생하려면 다음 네 가지의 조건을 동시에 만족해야한다. Coffman 조건이라고도 한다.

• 상호 배제
  자원은 한 번에 하나의 프로세스만 사용할 수 있어야한다. 다른 프로세스가 그 자원을 사용할 수 없도록 배타적으로 점유하는 상황을 말한다.
• 점유와 대기
  자원을 이미 점유한 프로세스가 다른 자원을 추가로 요청하면서 현재 점유한 자원을 놓지 않고 계속 보유한 채로 대기하는 상황이다.
• 비선점
  자원을 강제로 뺏을 수 없다. 프로세스가 자원을 스스로 해제할 때까지 다른 프로세스가 그 자원을 선점할 수 없는 경우다.
• 환형 대기
  프로세스 간에 자원을 기다리는 관계가 원형을 얽혀 있는 경우다. 
  A  → B → C → A 의 형태로 자원을 기다리는 상태

 

ㅇ 해결방법

예방
발생 조건 중 하나 이상의 조건을 제거하여 데드락이 발생하지 않도록 한다.

• 상호 배제 조건 제거
  자원을 공유할 수 있도록 변경(일부 자원에서는 불가능)
• 점유와 대기 조건 제거
  프로세스가 자원을 요청할 때 필요한 모든 자원을 한꺼번에 요청한다.
• 비선점 조건 제거
  자원을 점유한 프로세스가 다른 자원을 요청시, 점유한 자원을 반납하도록 한다.
• 환형 대기 조건 제거
  자원에 고유한 순서를 지정해, 그 순서에 따라 자원을 요청하도록 한다.

회피

시스템 상태를 추적하여 가능성을 검토하고 상황을 회피한다.

** 은행원 알고리즘
은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함

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

탐지와 회복

데드락이 발생했는지 주기적으로 검사하고 발생 시 이를 해결하는 방법

• 탐지
  자원 할당 그래프를 사용해 데드락 상태를 탐지할 수 있다.
• 복구
  데드락을 해결하기 위해 한 프로세스를 종료하거나, 자원을 선점하여 다른 프로세스에 할당할 수 있다.

 

1. 데드락이 뭔가요? 발생 조건을 설명해보세요
2. 은행원 알고리즘이 뭔가요?
3. 식사하는 철학자 문제를 해결해보세요
   n명이 앉을 수 있는 테이블에서 철학자를 n-1명만 앉힘
   한 척할자가 포크 두개를 모두 집을 수 있는 상황에서만 포크를 집도록 허용
   누군가는 왼쪽이아닌 오른쪽 포크를 먼저 집도록 허용