DeadLock

들어가기 전에

데드락을 알기위한 사전 지식들
위의 링크를 한번 읽고 오는 게 좋겠다. 데드락이 왜 발생할 수 밖에 없었는지에 대한 개념 설명 글이다.

무엇

프로세스가 자원을 얻지 못해서 다음 처리를 하지 못하는 상태

→ 교착 상태 라고도 부른다.

→ 시스템적으로 한정된 자원을 여러 곳에서 사용하려고할 때 발생.

왜(발생?)

프로세스 1과 2가 자원 1, 2를 모두 얻어야할 때, p1이 자원 1을 가지고, p2가 자원 2를 가지고 있는 상태라면,

서로 원하는 자원이 상대방에 할당되어 두 프로세스는 무한정 wait 상태에 빠진다.

→ 멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황 발생

→ 한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있다. 이때 프로세스는 대기 상태로 들어간다.

→ 대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 교착상태 발생

데드락 발생 조건

데드락이 일어나는 조건 4가지가 있음.

이 4가지를 모두 만족해야 데드락이 발생함!

• Mutual exclusion(상호 배제): 자원은 한번에 한 프로세스만 사용할 수 있음.
• Hold and Wait(점유 대기): 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위하여 대기하는 프로세스가 존재해야 한다.
• No Preemtion(비선점): 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 뺏을 수 없다.
• Circular Wait(순환 대기): 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야한다.

어떻게(해결?)

데드락 예방 & 회피

• 예방: 교착 상태 발생 조건 중에 하나를 제거하여 해결한다(자원 낭비가 심하다)
  • 상호배제 부정: 여러 프로세스가 공유 자원 사용
  • 점유대기 부정: 프로세스 실행 전에 모든 자원을 할당
  • 비선점 부정: 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
  • 순환대기 부정: 자원에 고유번호 할당 후 순서대로 자원 요구
• 회피: 교착 상태 발생 시 피해나가는 법
  • Banker’s Algorithm(은행원 알고리즘)
    • 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래
    • 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착상태 회피
    • 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기
  • 단점
    -시스템 과부하가 증가
    • 일정하게 남아있는 자원 수 파악 힘듦
    • 다중 프로그래밍 시스템에서는 사용자 수가 항상 변함

데드락 탐지 & 회복

→ 교착 상태가 되는 것은 허용하고, 그 후에 회복시키는 방법
-> (걍 다시 돌아갈 수 있을 때 까지 프로그램을 강제 종료하는 것!)

• 탐지
  • 자원 할당 그래프를 통해 교착 상태를 탐지
  • 자원 요청 시, 탐지 알고리즘을 실행시켜서 그에 대한 오버헤드 발생함
• 회복: 교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
  • 프로세스 종료 방법
    • 교착 상태의 프로세스를 모두 중지
    • 교착 상태가 제거될 때까지 하나씩 프로세스 중지
  • 자원 선점 방법
    • 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당(뺏긴 프로세스들은 일시정지 상태)
    • 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점