교착상태

서론

---

• 멀티 프로세스 애플리케이션 환경에서 여러 스레드가 한정된 자원을 사용하려고 서로 경쟁할 수 있습니다. 한 스레드가 자원을 요청했을 때, 그 시각에 그 자원을 사용할 수 없는 상황이 발생할 수 있고, 해당 스레드는 대기 상태로 들어가게 됩니다. 이처럼 대기중인 스레드들이 다시는 그 상태를 변경시킬 수 없으면 이런 상황을 교착 상태라 부릅니다.
• 스레드는 한정된 자원을 사용하기 위해서는 반드시 자원을 요청해야하고, 사용 후에는 반드시 방출해야 합니다. 스레드는 한정된 task를 수행하기 위해 필요한 만큼의 자원을 요청할 수 있습니다. 명백히 스레드가 요청한 자원의 수는 시스템에서 사용 가능한 전체 자원의 수를 초과할 수 없습니다. 
• 세마포어에서 자원의 획득과 방출은 wait, signal 연산을 통해, 그리고 뮤텍스에서는 acquire, release 연산을 통해서 이루어 질 수 있습니다. 스레드가 커널이 관리하는 자원을 사용할 때마다 매번 운영체제는 스레드가 자원을 요청했는지와 그 자원을 할당받았는지 확인합니다. 또한 시스템 테이블에서는 각 자원이 가용상태인지, 또는 할당되었는지 기록하며, 각 할당된 자원에 대해서는 어느 스레드에게 할당되었는지도 기록합니다. 
• 좋은 예는 20세기 초 캔사스 주 의회가 통과한 법률에서 찾아볼 수 있습니다. 그 내용은 "두 기차가 교차로에 서로 접근할 때는, 둘 다 완전히 정지해야하며 상대방이 없어지지 않는 한 그 누구도 다시 출발할 수 없다" 라는 내용입니다. 

 

데드락, 라이브락, 스핀락이란?

---

💡 데드락(DeadLock)

 

• 두 개 이상의 프로세스나 스레드가 상대방의 작업(Task)이 끝나기만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태입니다.

💡 라이브락(LiveLock)

 

• 라이브락은 데드락과 비슷한 결과를 초래하지만 다른 과정에 의해 발생하는 현상입니다. 라이브락은 스레드들이 동시에 실행되면서 락의 해제와 획득을 반복적으로 수행하면서 정상적으로 동작하는 것처럼 보이지만 실상은 아무것도 못하고 무한히 반복만할 뿐입니다.
• 라이브락은 일반적으로 스레드가 실패한 작업을 동시에 재시도할 때 발생합니다. 일반적으로 각 스레드가 실패한 행동을 재시도하는 시간을 무작위로 정하면 회피할 수 있습니다.
• Ethenet 네트워크에서 네트워크 충돌이 발생하면 서로 패킷을 재전송하려는 시도 대신, 충돌한 호스트는 재전송을 시도하기 전에 임의의 시간동안 한 발 뒤로 물러나고 다시 시간이 지나면 재시도하게 됩니다.

💡 스핀락(SpinLock)

 

• 임계구역에서 하나의 스레드가 작업중이라면 다른 스레드가 락을 획득하기 위해 반복문을 순회하면서 락을 얻고자 하는 과정입니다.

 

교착상태의 특성

---

교착상태는 다음 네 가지 조건이 동시에 성립될 때 발생할 수 있습니다.

 

💡 상호 배제

 

• 한정된 자원에 대해 스레드가 자원을 요청하여 작업을 수행하는 동안 다른 스레드들은 해당 스레드가 락을 방출하기 전까지 대기하고 있어야 합니다.

💡 점유 대기

 

• 상호 배제로 인해 다른 스레드에게 할당된 자원을 점유하기 위해, 대기 하는 스레드가 무조건 하나 이상은 존재해야 합니다. 대기하고 있는 스레드가 없다면 교착 상태는 발생하지 않습니다.

💡 비선점

 

• 자원을 선점할 수 없어야합니다. 즉 자원이 강제적으로 방출될 수 없고, 스레드가 정상적으로 종료되든지, I/O 작업으로 인해 대기 큐에 적재되어 자발적으로 방출하든지 둘 중 하나에 의해서만 할 수 있습니다.

💡 순환 대기

 

• 자원을 기다리는 스레드간 사이클이 형성되어야 합니다.
• 대기하고 있는 스레드의 집합 {T0, T1, T2, T3, TN....} 이 형성되어 있는 경우 T0은 T1이 점유한 자원을 대기하고 T1은 T2가 점유한 자원을 대기하고 있는 상황이어야 합니다.

 

💡 자원 할당 그래프

 

• 아래 사진은 R1은 하나의 자원을, R2는 두 개의 자원을 R3는 하나의 자원이 있습니다. 이때 어떻게 진행되는지 살펴보겠습니다.
• R1 -> T2에 점유, R2 -> T1, T2에 점유 R3 -> T3 점유하고 있으며 T1 -> R1 요청, T2 -> R3 요청을 하고 있습니다.

 

    교착 상태가 발생하는 자원 할당 그래프

 

• 아래는 DeadLock이 발생하는 그래프입니다. T2가 R2의 자원을 점유하고 있는 상태에서 R3의 자원을 필요로 하는데 R3의 자원은 T3가 점유하고 있습니다. 이때 T3가 R2의 자원을 요청하게 된다면 교착 상태가 발생하게 됩니다. 그 이유는 R2는 현재 T1, T2가 점유하고 있기 때문입니다. 이러한 문제를 극복하기 위해서는 T1이나 T2 중 R3의 점유를 방출해야 합니다.

 

    교착 상태가 발생하지 않는 자원 할당 그래프

 

• 아래의 사진에서는 DeadLock이 발생하지 않습니다. 그 이유는 T1이 자신의 작업을 끝내고 R1의 자원을 필요로 하지 않고 작업이 끝나는 동시에 R2의 자원을 방출하게 됩니다. 그리고 T3는 R2의 자원을 점유할 수 있게 되므로 DeadLock은 발생하지 않습니다.

 

 

 

데드락 해결 방법

---

• 데드락이 발생하지 않도록 예방하는 방법입니다.
• 데드락 발생 가능성을 인지하면서도 적절히 회피하는 방법입니다.
• 데드락 발생을 허용하지만 데드락을 탐지하여 복구하는 방법입니다.

 

데드락 예방

---

데드락을 예방하는 방법은 아래 4가지 방법이 있습니다. 하지만 이는 시스템의 처리량이나 효율성을 떨어트리는 단점이 있습니다.

 

 

💡 상호 배제

 

• 상호 배제 조건을 부정하는 방법입니다. 한정적인 자원을 사용하기 위해서는 배타적 접근이 필요로 한데, 공유 가능한 자원들은 이러한 배타적 접근을 필요로 하지 않습니다. 따라서 교착 상태에 빠질 수 없게 됩니다. 
• 그러나 상호 배제 조건을 부정함으로써 교착 상태를 예방하는 것은 현실적으로 불가능합니다. Mutex의 경우는 상호 배체제 필수이기 때문입니다. 그리고 이러한 조건을 배제하면 동기화 이슈화 발생하게 됩니다.

💡 점유 대기

 

• 스레드가 실행되기 전 실행에 필요한 모든 자원을 요청하고, 모든 자원이 할당될 때까지 작업을 보류해서, 나중에 또 다른 자원을 점유하기 위한 대기 조건이 성립되지 않도록 합니다. 만약 추가 자원을 요청할 수 있으려면 자신에게 할당되어 있는 모든 자원을 반드시 먼저 방출해야 합니다.

    점유 대기의 문제점

 

• 기아 상태가 발생할 수 있습니다. 인기 있는 자원을 필요로 하는 스레드가 있을 때 해당 자원이 있기가 많아 다른 스레드들이 우선적으로 점유하게 된다면 무한정 기다리게 되므로 기아 상태가 발생할 수 있습니다.
• 자원이 할당되어 있지만 장기간 사용되지 않을 수 있기 때문에 자원 이용률이 낮을 수 있습니다. 이는 자원 낭비의 우려가 있습니다.

💡 비선점

 

• 우선순위가 높은 스레드에게 자원이 선점될 수 있도록 합니다.
• CPU 레지스터나 데이터베이스 트랜잭션처럼 그 상태가 쉽게 저장되고, 복원될 수 있는 자원에는 적용될 수 있지만 일반적으로 뮤텍스나 세마포어 같은 자원에는 사용될 수 없습니다. 

💡 순환 대기

 

• 상호배제, 점유 대기, 비선점은 대부분의 상황에서 일반적으로 실용적이지 않습니다. 그러나 순환 대기 조건은 필요 조건 중 하나를 무효화하여 해결책을 제시할 수 있습니다.
• 순환 대기 조건이 성립되지 않도록 하는 방법은 모든 자원에 전체적인 순서를 부여하여, 각 프로세스가 열거된 순서대로 자원을 요청하도록 요구하는 것입니다.

 

데드락 회피

---

💡 Safe State

 

• 시스템 상태가 안전하다는 말은 시스템이 어떤 순서로든 스레드들이 요청하는 자원을 교착 상태를 발생시키지 않고 차례대로 모두 할당할 수 있다는 의미입니다. 즉 안전 순서(safe sequence)를 찾을 수 있다면 시스템은 안전합니다.
• T1, T2, T3, TN ... 와 같은 스레드 순서가 안전하다는 말은 Ti가 요청한 자원을 시스템에 현재 남아있는 자원과 앞서 수행을 끝낼 스레드 Tj가 반납하는 자원들로 Ti를 만족시켜 줄 수 있음을 말합니다. 만약 Ti가 요청한 자원들을 즉시 만족시킬 수 없을것으로 판단되면 Ti는 앞선 Tj들이 끝날때까지 기다리게 됩니다. 그리고 Ti는 Tj가 반납한 자원을 사용하게 됩니다.
• 시스템의 상태가 안전하다면 물론 교착 상태가 아닙니다. 하지만 시스템이 불안전 하다고해서 교착 상태에 빠졌다는 것도 아닙니다. 불안전하는 것은 교착 상태에 빠질우려가 있다는 의미입니다.
• 시스템이 불안전한 상태에 들어가게 되면 운영체제는 교착 상태가 일어날 수도 있는 자원의 요청을 막을 수 없습니다. 그 이유는 스레드들의 행동 양태가 불안전 상태를 제어하기 때문입니다.
• 기본 원칙은 시스템의 상태가 항상 안전 상태를 떠나가지 않도록 지키는 것입니다. 최초의 상태는 안전합니다. 하지만 그 후 스레드들이 자원을 요청하면 시스템은 자원을 즉시 할당할 수 있는지 아니면 스레드가 대기해야 하는지 결정해야 합니다. 요청 자원을 즉시 승낙해주는 경우에는 시스템의 상태가 안전 상태에서 안전 상태로 옮길 때뿐입니다.

 

    예시

 

• 시스템에 12개의 자원이 있고 P1, P2, P3 세 개의 프로세스가 있다고 가정하면 P1에는 10개의 자원을 필요로하고, P2에는 4개, P3에는 9개 자원을 최종적으로 필요로 합니다.
• 위 상황에서 safe sequece는 P2 -> p1 -> p3의 순서가 됩니다. 그 이유는 추가로 필요한 자원의 수의 순서입니다.

    순서

 

1. P2는 현재 2개의 자원을 할당받았고, 2개의 자원을 추가적으로 필요로하게 됩니다. 이때 시스템에서 가용할 수 있는 자원의 수는 3개이므로 여기서 2개를 추가적으로 사용하여 자신의 작업을 수행하고 이후 자원을 반납하게 됩니다. 결국 자원을 해제하면 시스템은 가용 자원이 5개가 됩니다.
2. 이후 P1에 추가적으로 자원 5개를 할당하게 됩니다. 자원을 할당받게된 P1은 자신의 작업을 수행하고 이후에 자원을 반납하게 됩니다. 결국 자원을 해제하면서 시스템은 가용 자원이 10개가 됩니다.
3. 이후 P3에 추가적으로 자원 7개를 할당하게 됩니다. 자원을 할당받게된 P3는 자신의 작업을 수행하고 이후에 자원을 반납하게 됩니다. 결국 자원을 해제하면서 시스템은 가용 자원이 12개가 됩니다.

 

    unsafe state 예시

 

• 동일한 상황에서 P3만 추가적으로 자원을 하나 더 할당받게 되었습니다. 
• 이때 P2는 시스템의 보유한 자원을 사용하여 정상적으로 작업을 수행하고 반납하게 됩니다. 이때 시스템이 보유한 자원의 수 는 4개가 되는데 이 4개를 사용하여 수행할 수 있는 프로세스는 없어지게 됩니다.결국 교착상태가 발생하게 됩니다.

 

 

💡 자원 할당 그래프 알고리즘

 

• 자원 타입당 사용할 수 있는 인스턴스가 하나일 때만 사용할 수 있는 알고리즘입니다.
• 앞서 본 자원 할당 그래프에서 예약 간선이 추가된 개념입니다.
• 스레드는 실행되기 전에 스레드의 모든 예약 간선이 자원 할당 그래프에 표시되어 있어야 합니다. 해당 스레드가 자원을 요청하면 예약 간선은 요청 간선으로 바뀌게 됩니다.또한 자원이 할당되면 할당 간선으로 바뀌게 됩니다. 그리고 자원이 반환되면 다시 예약 간선으로 변경되게 됩니다.

 

    예시

 

1. 아래 사진에서 T1은 R1을 점유하고 있고, T2는 R1을 요청하고 있습니다. 그리고 T1과 T2는 R2 자원을 예약하고 있습니다.
2. 이때 P2가 R2에 대한 요청을 한다면, 시스템은 현재 R2가 어느 스레드에게 할당되지 않은 상태라 할지라도 T2에게 바로 할당하지 않고 대기 시킵니다.
3. 그 이유는 T1의 예약 간선 때문인데, T1이 언제든 R2의 자원을 요청할 수 있다는 것을 의미하고, 만일 T2가 R2를 할당하고 나서 T1이 R2에 대해 자원을 요청하게 된다면 아래 사진처럼 DeadLock이 발생하게 됩니다. 그렇기 때문에 시스템은 T2의 요청을 거부함으로써 DeadLock을 회피하게 됩니다.

💡 은행원 알고리즘

 

• 자원 할당 그래프 알고리즘은 자원마다 하나의 인스턴스만 존재해야하는데 은행원 알고리즘은 하나의 자원에 여러개의 인스턴스가 존재할 수 있습니다.
• 이 시스템에서는 스레드가 시작할 때 스레드가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 미리 신고해야 합니다. 물론 이 자원의 개수가 자원의 총 보유 수를 넘어가면 안됩니다.
• 스레드가 자원들을 요청하면 시스템은 그것을 들어주었을 때 시스템이 계속 안전 상태에 머무르게 되는지 여부를 계속 판단해야 합니다. 계속 안전하다면 그 요청을 들어줍니다. 그렇지 않다면 스레드의 요청은 허락이 안된 채 다른 스레드의 작업이 끝날때까지 기다리게 됩니다.

 

교착상태 회복

---

• 교착 상태를 처리하기 위한 방법으로는 운영자에게 알려 운영자가 수작업으로 처리하게끔 하거나, 시스템이 자동으로 교착상태로부터 회복하게 하는 방법이 있습니다.
• 교착 상태를 깨트리는 방법에는 순환 대기를 깨뜨리기 위해 한 개 이상의 스레드를 종료하는 방법과 교창 상태에 있는 하나 이상의 스레드를 선점하는 방법이 있습니다.

 

💡 종료(abort)

 

• 프로세스나 스레드를 종료시킴으로써 교착 상태를 제거하기 위해 우리는 다음과 같은 방법을 사용할 수 있습니다. 다음과 같은 방법은 종료된 스레드에게 할당되었던 자원을 모두 시스템이 회수합니다.

 

    교착 상태 스레드를 모두 종료

 

• 이 방식은 확실하게 교착 상태의 사이클을 깨뜨리지만, 비용이 큽니다. 그 이유는 할당되었던 자원을 모두 회수하고 처음부터 다시 자원을 얻어 다시 작업을 처리해야 하기 때문입니다.

    교착 상태가 제거될 때까지 한 스레드씩 종료

 

• 이 방법은 각 스레드가 종료될 때마다 교착 상태 탐지 알고리즘을 호출해 프로세스들이 아직도 교착 상태에 있는지 확인해야 하므로 오버헤드가 큽니다.

 

    종료의 문제점

 

• 프로세스나 스레드를 종료시키는 것은 상당히 어려운 문제입니다. 만약 파일을 업로드 하는 중 종료를 하게되면 해당 파일은 부정확한 상태가 됩니다. 또한 Mutex Lock을 획득하여 공유 데이터를 갱신하는 중이라면 공유 데이터의 무결성을 보장할 수 없게되고, 시스템은 Lock을 다시 가용한 상태로 복구해야 합니다.
• 만약 부분적으로 종료를 한다면 교착 상태인 스레드 중에서 교착 상태를 깨뜨리기 위해 어느 스레드들 종료해야할지 결정해야 합니다. 
  이러한 결정은 스레드를 종료했을 때 가장 비용이 적게드는 스레드를 종료시켜야 하는데 하지만 최소 비용은 정확히 무엇을 의미하는지 모르기 때문에 어렵습니다.

 

    최소 비용을 나타내는 요건

 

• 스레드의 우선순위가 무엇인지
• 지금까지 스레드가 수행된 시간과 지정된 일을 종료하는데 필요한 시간
• 스레드가 사용한 자원의 유형과 수
• 스레드가 종료하기 위해 더 필요한 자원의 수 
• 얼마나 많은 수의 스레드가 종료되어야 하는지

 

💡 자원 선점

 

• 자원 선점을 이용해 교착 상태를 제거하려면, 교착 상태가 깨질 때까지 스레드로부터 자원을 계속 선점해 해당 자원을 다른 스레드에게 할당해줘야 합니다.

    희생자 선택

 

• 어떤 자원과 어떤 스레드가 선점했을 때 최소 비용이 드는지 선점의 순서를 결정해야 합니다. 이러한 최소 비용은 위에서 언급한 내용이 있습니다.

    후퇴

 

• 스레드로부터 자원을 선점하기 위해서는 해당 스레드를 안전한 상태로 후퇴시키고 다시 시작해야 합니다.
• 이때 안전한 상태가 어떤 상태인지 결정하기 어렵기 때문에 간단한 방법으로는 스레드를 종료한 후 재시작하여 완전히 후퇴시킵니다.
• 조금 더 좋은 방법은 스레드가 교착 상태를 깨뜨릴 수 있을정도로 후퇴시키는 것인데 이러한 방법은 실행되는 스레드들이 더 많은 정보를 유지할 것을 필요로 합니다.

    기아 상태

 

• 자원들이 동일한 스레드로부터 항상 선점되지 않도록 보장해야 합니다.
• 희생자 선택 시 계산한 비용에 의해 완료되지 못하는 기아 상태가 발생할 수 있습니다. 대부분의 해결 방법은 비용 요소에 후퇴 횟수를 포함시키는 것입니다.

 

 

참고자료

• https://kukuta.tistory.com/281