데드락(Dead Lock)

 

운영체제 속 데드락이란 시스템 자원에 대한 요구가 뒤엉킨 상태로, 둘 이상의 프로세스가 다른 프로세스가 소유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황

 

발생조건

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

데드락 방지

1. 예방 (Prevention)

• 상호 배제 방지 : 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.(동기화 문제 고려 필요)
• 점유 대기 방지 : 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류한다.
• 비선점 방지 : 이미 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점하도록 한다.
  • 뺏어오기 가능
• 순환 대기 방지 : 자원이 순환 형태로 대기하지 않도록 자원에 고유한 번호를 부여하고, 번호 순서대로 자원을 요구하도록 한다.※ 단점
• 시스템의 처리량이나 효율성이 떨어진다.
• 가장 제한적인 방법이다.

2. 회피 (Avoidance)

• 안전 상태 (Safe State) : 프로세스들이 요청하는 모든 자원을 데드락 없이 차례로 모두 할당해 주는 경우
• 안전 순서 (Safe Sequence) : 데드락 없이 모든 자원을 할당해 주었을 때의 순서를 의미
• 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 검사하여 교착 상태를 회피하는 기법이다.
• 안정 상태에 있으면 자원을 할당하고 그렇지 않으면 다른 프로세스들이 자원을 해제할 때까지 대기한다. 
  
  ※ 단점
  
  • 미리 최대 자원 요구량을 알아야 하고, 할당할 수 있는 자원 수가 일정해야하는 제약 조건이 존재
• ※은행원 알고리즘 다익스트라가 제안한 방법으로 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래된 기법.

3. 탐지(Detection) & 회복(Recovery)

• 탐지 기법 : Allocation, Request, Available 등으로 데드락의 발생 여부 탐지
• 회복 기법 : 데드락을 탐지했다면, 순환 대기에서 벗어나는 회복 방법 사용
  • 프로세스를 종료하는 방법
    • 데드락 상태의 모든 프로세스 중단 : 중간 단계 결과가 폐기되는 단점
    • 데드락 상태가 제거될 때까지 한 프로세스씩 중지
  • 자원을 선점하는 방법
    • 프로세스에 할당된 자원을 선점하고 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당
    • 우선순위가 낮은 프로세스, 수행된 횟수가 적은 프로세스 등을 위주로 프로세스의 자원을 선점한다.

 

※ 참고

은행원 알고리즘