교착상태(Dead Lock)란???(feat.기아상태)

교착상태란?

• 모든 스레드가 락이 풀리기를 기다리고 있는 상태, 무한 대기 상태에 빠짐
• 프로세스가 자원을 얻지 못해서 다음 처리를 못하는 상태
• 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생

프로세스가 결코 일어나지 않을 사건을 기다리는 상태가 되면 교착 상태라고 하며, 두 프로세스가 사용하는 자원을 서로 기다리고 있을 때 발생합니다.

주로 발생하는 이유

• 멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황이 발생됩니다.
• 한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있음, 이 상황에서 프로세스는 대기 상태로 들어가며 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 교착 상태가 발생하게 됩니다.

교착 상태의 4가지 조건

교착 상태가 되기 위한 4가지 중 한개라도 해당이 안되면 교착상태가 되지 않습니다.

1. 상호배제 (Mutual exclusion)

• 자원은 한 번에 한 프로세스만 공유 자원을 사용할 수 있다.
• 공유 자원에 대한 접근 권한이 제한된다.
• 하지만 자원의 양이 제한되어 있더라도 교착상태는 발생할 수 있다.

2. 점유와 대기 (Hold and Wait)

• 공유 자원에 대한 접근 권한을 갖고있는 프로세스가, 그 접근 권한을 양보하지 않은 상태에서 다른 자원에 대한 접근 권한을 요구한다.

3. 비선점 (Non Preemptive)

• 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다.

4. 순환대기 (Circular wait)

• 두 개 이상의 프로세스가 자원 접근을 기다리는데, 그 관계에 사이클이 존재한다.

교착상태 방지

• 4가지 조건들 가운데 하나를 제거하면 된다.
• 공유 자원 중 많은 경우가 한 번에 한 프로세스만 사용할 수 있기 때문에, 1번 조건(상호배제)은 제거하기 어렵다.
• 대부분의 교착상태 방지 알고리즘은 4번조건(순환대기), 즉 대기 상태의 사이클이 발생하는 일을 막는 데 초점이 맞춰져 있다.

교착상태 처리

1. 예방(Prevention)

• 교착 상태 발생 조건 중 하나를 제거하면서 해결을 하지만, 자원의 낭비가 심하다.
  • 점유와 대기(Hold & Wait) 조건의 부정
    • 프로세스는 필요한 모든 자원을 한번에 요청하고 시스템은 요청된 자원들을 전부 할당 또는 하지 않는 방식
    • 단점으로는 자원 낭비와 비용 증가, 자원 공유 불가능, 무한 연기 발생 가능
  • 비선점(Non Preemptive) 조건의 부정
    • 어떤 자원을 가지고 있는 프로세스가 더 이상 자원 할당 요구가 없으면 가지고 있던 자원을 반납하고, 필요시에 자원을 요구 합니다.
    • 단점으로는 비용 증가, 일부 자원은 선점 불가 경우가 발생하며, 무한 연기 발생 가능
  • 환형대기(Circular Wait)의 부정
    • 모든 프로세스에게 각 자원의 유형별로 할당 순서를 부여 하는 방법입니다.
    • 시스템 설치시 모든 자원에 고유번호 부여, 자원 요청시 번호 증가 순으로 요청
    • 새 자원 추가시 재구성, 프로세스 실행중 예상한 순서와 다른 요구 조건 발생시 긴 시간 동안 자원이 낭비된다.
  • 상호 배제(Mutual Exclusion)의 부정
    • 공유 할 수 없는 자원을 사용할 때 성립되며 기억장치 CPU등이 해당합니다.

2. 회피(Avoidance)

• 교착상태 발생 가능성을 인정하고 교착상태 발생시 적절히 피해가는 방법
  1) 은행원 알고리즘

  * 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래했으며, 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착상태 회피하고, 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기합니다.

3. 탐지(Detection)

• 교착상태 발생하게 허용하지만 교착상태와 연관있는 프로세스 자원을 찾아내 조사한다.

4. 회복(Recovery)

• 교착상태의 하나 이상의 프로세를 다시 시작하거나 되돌림으로 해결합니다.
• 몇 개의 프로세스들이 수행한 작업의 일부 또는 전부를 잃는다.
  • 프로세스 중지
    • 교착상태 프로세스 모두 중지, 교착상태 사이클 제거 될때까지 한 프로세스씩 중지 한 프로세스씩 중지를 위한 희생자 선택의 원칙
  • 자원 선점
    • 교착상태 프로세스로부터 자원을 선점하여 다른 프로세스에 제공 -> 희생자 선점, 복귀, 기아문제를 생각해야 한다.

기아 상태

교착 상태가 자원을 자유롭게 할당한 결과(자원 부족)라면, 반대로 기아 상태는 작업이 결코 사용할 수 없는 자원을 계속 기다리는 결과(교착 상태)를 예방하려고 자원을 할당할 때 발생(기다림) 하는 결과이다. 작업이 결코 사용할 수 없는 자원을 계속 기다리는 결과를 예방하려고 자원을 할당할 때 발생하는 결과이다.

예상 질문

교착상태란 뭔지 설명해주세요

시스템 자원에 대한 요구가 뒤엉킨 상태를 말합니다.
둘 이상의 프로세스가 각각 점유하고 있는 자원을 포기하지 않고 다른 프로세스의 자원을 요구할때 무한 대기 상태에 빠진 것입니다.

교착상태의 발생조건에 대해 말해주세요

상호배제, 점유대기, 비선점, 순환대기 입니다.

• 상호배제는 한 번에 프로세스 하나만 해당 자원을 사용할 수 있는 것이고,
• 점유 대기는 자원을 갖고 있으면서, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하고 있는 프로세스가 존재하고 있을때 발생합니다.
• 비선점은 이미 할당된 자원을 강제로 뺏을 수 없다는 것이고
• 순환 대기는 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

교착상태의 해결법에 대해서 말해주세요

예방, 회피, 탐지, 회복이 있습니다.

예방은 교착 상태 발생조건중 하나를 제거하면서 예방을 하고
회피는 어느정도 교착상태가 발생될것을 인정하고 교착상태를 적절히 피해나가는 것입니다.
탐지는 교착상태와 연관있는 프로세스를 찾아내고
회복에서 프로세스 1개 이상을 중단시키거나, 자원을 선점해 해결을 합니다.