교착상태(Deadlock)

정적인 상태의 프로그램이, 자원을 할당받아 동적인 프로세스가 된다. 하지만 CPU, 메모리 등의 자원의 양은 제한되어있기 때문에 원하는 모든 프로세스를 무제한으로 동시에 실행시키는 것은 불가능하다. 자원이 이미 다른 프로세스에 의해 점유된 상태에서, 해당 자원을 다른 프로세스들이 너도나도 요구하게 된다면, 프로세스들이 실행되지 못하고 자원 할당을 한없이 기다리는 상태에 놓이게 될 것이다.

이번에는 이러한 '교착상태' 의 개념과 교착상태를 어떻게 해결하는 지에 대해 살펴보도록 한다.

교착상태의 개념과 발생 조건

상호배제 원칙으로 인해 서로의 공유자원을 프로세스들이 요구함으로써 무한정 대기하는 상황

• 둘 이상의 프로세스가 자원을 점유한 상태에서, 서로 다른 프로세스가 점유중인 자원을 요구하면서 무한정 기다리고 있는 현상을 말함

• 이는 상호배제(Mutual Exclusion) 로 인해 나타나는 문제점으로, 상호배제는 여러 프로세스가 공유하는 자원에 대해서, 특정 시점에서 한 개의 프로세스만이 공유자원을 점유할 수 있는 원칙 을 말함

  • 이러한 공유자원 영역을 임계영역(Critical Section) 이라고 하며, 상호배제는 임계영역을 유지하는 기법인 셈
  • 더 나아가, 결국 상호배제로 인해 두 개이상의 프로세스를 한 시점에서 동시에 처리할 수 없는 경우, 프로세스 실행 순서를 명확히 하는 것을 동기화(Synchronization) 라고 부르는 것

• 교착상태가 일어나기 위한 필요 조건은 4가지로, 여기서 하나라도 충족되지 않으면 교착상태가 발생하지 않음

  (또한 4가지 조건을 모두 충족했다고 해서 반드시 교착상태가 일어나는 것도 아님)

  • 상호배제(Mutual Exclusion)

    • 한 번에 한 개의 프로세스만이 공유자원을 점유해야 함

  • 점유대기(Hold and Wait)

    • 어떤 프로세스가 자원을 할당받아 배타적으로 점유하는 상황에서, 다른 프로세스가 자원을 사용하고자 할 경우에는 점유된 자원이 해제되기를 기다려야 함

  • 비선점(Non-preemption)

    • 어떤 프로세스에 할당된 자원은, 해당 프로세스가 자원을 스스로 반환하기 전까지는 제거되지 않음
    • 다시 말해, 프로세스 종료 후에만 해제될 수 있으며 타의에 의한 해제는 불가능한 것

  • 환형대기(Circular Wait)

    

    • 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 환형을 이루면서 대기하는 조건을 말함
    • 자원을 점유하면서 원형 구조에서 자신의 앞 혹은 뒤에 있는 프로세스의 자원을 요구하는 상황

.

교착상태의 해결

• 교착상태 처리 전략은 크게 방지 , 회피 , 탐지 및 복구 의 세가지로 나눌 수 있음

• 1) 방지 : 교착상태가 발생하기 위한 4가지 필요 조건 중 적어도 하나 이상이 발생하지 않도록 함

  • 상호배제 조건의 제거

    • 공유 가능한 자원의 경우 상호배제가 필요하지 않지만, 그렇지 않다면 반드시 상호배제를 따라야 하기 때문에 사실상 불가능한 전략임

• 점유 대기 조건의 제거

  • 점유 대기를 없애려면 프로세스가 자원을 요청할 때, 해당 프로세스는 어떠한 자원도 할당받지 않은 상태 로 만들면 됨

  • 필요한 모든 자원을 한꺼번에 요구하여 할당받도록 할 수 있음

    • 나중에 사용할 자원까지 우선 다 가지고 있기 때문에, 전체적인 자원의 이용도 측면에서 비효율적

  • 혹은, 자원을 부분적으로 요청하여 할당받도록 하되, 추가 요청시에는 이전에 가지고 있던 자원을 모두 해제하도록 할 수도 있음

    • 빈번히 사용되는 자원의 경우, 다른 자원 요청을 위해 잠시 반납한 순간 해당 자원이 다른 프로세스에 할당되버리는 문제가 발생할 수 있음
    • 기아상태(starvation) 이 발생해버리는 것

• 비선점 조건의 제거

  • 우선 어떤 자원을 점유하고 있는 프로세스가 다른 자원을 요청했을 때, 즉시 할당받지 못하는 경우에 점유중이던 자원을 해제하도록 할 수 있음

    • 이후 해제된 자원을 포함하여 모든 필요한 자원이 사용 가능해질 경우에 프로세스가 재개됨

  • 혹은 프로세스가 어떤 자원을 요청했을 때, 가용 여부를 조사하여 가용상태이면 할당하고 그렇지 않은 경우에는 해당 자원이 다른 자원을 할당받기 위해 대기중인 프로세스에 할당되어 있는 지를 조사하여, 대기중인 프로세스로부터 자원을 선점하도록 할 수도 있을 것

    • 이 경우에는 자원이 가용상태가 아니거나, 실행중인 프로세스에 할당된 경우이면 자원을 요청한 프로세스는 반드시 대기해야 함

• 환형 대기 조건의 제거

  • 순환 형태로 프로세스가 자원을 요구하며 대기하지 않고, 선형으로 프로세스가 자원을 요구하는 형태 가 되도록 함

  • 자원에 고유번호를 할당하고, 프로세스가 특정 번호를 기준으로 오름차순으로 자원을 요청하도록 할 수 있음

  • 혹은, 프로세스가 특정 자원을 요구할 때, 요구할 자원의 일련번호보다 큰 번호를 받은 자원은 모두 해제하도록 할 수도 있음

  • 이 방식은 결국 일련번호를 부여하기 위한 함수가 어떻게 정의되냐에 따라 성능이 좌우됨

    • 보통, 먼저 사용되야 하는 자원일수록 작은 일련번호를 부여

    .

• 2) 회피 : 프로세스의 자원 사용에 관한 사전 정보를 활용하여, 교착상태의 발생 여부를 예상하고 안전한 상태(Safe State)에서만 자원 요청을 하도록 하는 방법

  

  • 사전정보로는 현재 할당된 자원 , 가용 상태의 자원 , 프로세스들의 최대 요구량 의 세가지가 활용됨

  • 교착상태를 회피하면서 각 프로세스에게 최대 요구량까지 자원을 할당하 수 있는 상태를 안전한 상태(Safe State) 라고 부름

  • 안전한 상태는 다시 말해 안전 순서열(Safe Sequence) 이 존재하는 경우로 볼 수 있음

    • 특정 프로세스가 추가적으로 요구하는 자원이 가용 상태이거나, 혹은 앞 순서의 프로세스가 사용중이기 때문에 결국엔 반납될 자원까지 포함하여 할당이 가능한 경우를 말함
    • 다시 말해, 안전 순서열이 존재한다는 것은 당장 프로세스가 요구하는 자원을 받지 못하더라도, 앞의 프로세스들이 자원을 반납할 때까지만 기다리면 결국에는 얻을 수 있음을 의미함
    • 안전 순서열이 존재하지 않는 경우는 불안전 상태(Unsafe State) 라고 부름
    • 단, 불안전 상태라고 해서 무조건 교착상태인 것은 아님!

• 자원 할당 그래프(Resource-Allocation Graph Algorithm)

  

  • 자원이 하나인 경우 요청 간선 , 할당 간선 , 예약 간선 세 가지 종류의 간선을 활용하여 자원할당 그래프에서 사이클이 존재하면 교착상태가 발생할 것으로 간주
  • 위의 그림의 경우 P2 프로세스는 자원 R2를 요청하여 할당받을 경우, 사이클이 존재하기 때문에 교착상태가 발생하게 됨
  • 만일, R2가 P1에 할당된 경우에는, 예약간선 방향이 그림과 다르게 P1을 향하기 때문에 결과적으로 사이클이 존재하지 않게 됨

  위의 경우는 각 유형의 단위자원이 하나인 경우에 유효하며, 여러개인 경우에는 무조건이 아닌 교착상태 발생 가능성이 존재하는 것으로 간주해야 함

• 은행원 알고리즘 (Banker's Algorithm)

  

  • 각 유형의 단위자원이 여러개인 경우 사용하며, 기본적으로 자원을 할당한 후의 상태를 예측하여 안전상태의 유지가 보장되는 경우에만 실제로 자원을 할당하는 알고리즘
  • 만일, 불안전 상태인 경우에는 다른 프로세스가 자원을 반납할 때 까지 대기해야 함
  • 가용 자원 , 최대 요구 , 할당 자원 , 추가 요구 의 4가지 데이터 구조를 가지고 판단
  • 위의 그림에서 P0의 경우 현재 A유형의 자원이 0만큼 할당되있으며, 최대 요구량은 7만큼이고 추가적으로 7만큼의 자원을 요구하지만, 현재 가용 자원은 2만큼 밖에 없는 상황
  • 만일 추가 요구량이 가용량을 초과할 경우에는 해당 프로세스는 대기상태가 되야 함
  • 추가 요구량이 가용량 이하인 경우에는, 우선 할당 후 줄어든 가용량과 늘어난 할당량, 그리고 줄어든 추가 요구량을 고려하여 새로운 상태가 안전상태인지를 조사함
  • 안전 상태라면 자원을 할당하며, 그렇지 않으면 프로세스를 대기상태로 놓고 데이터 구조는 이전 상태로 복구(rollback)시킴

.

• 3) 탐지 및 복구 : 말 그대로 교착상태를 탐지하고 이를 회복하는 알고리즘을 활용하는 것

• 탐지 : Shoshani & Coffman Algorithm 을 활용하는 것이 대표적(은행원 알고리즘과 유사함)

  • 길이가 m과 n인 벡터 Work, Finish를 초기화

  • 각 프로세스에 대해 Work := Available(가용자원) 으로 초기화했을 때, Alloc(할당 자원) 의 양이 0이 아닌 경우에는 해당 프로세스 번호에 해당하는 Finish 벡터값을 false로 둠(반대의 경우는 true)

  • Finish[i] = false 이면서 프로세스 i의 추가 요구량이 Work 이하인 프로세스 i를 탐색

  • 위의 조건을 만족하는 프로세스 i가 존재한다면 Work = Work + (프로세스 i의 할당자원) 으로 바꾸고, 해당 프로세스 번호에 해당하는 Finish 벡터값을 true로 둠

  • 이후 다시 위의 조건을 만족하는 프로세스 i를 탐색

  • 만일 프로세스 i에 대해 Finish 벡터값이 false가 되는 상황이 발생하면, 시스템이 교착상태인 것으로 간주(Finish[i] = false인 프로세스 i는 교착상태)

    • 결국 프로세스의 요구량만큼 가용자원을 할당하다가, 가용자원의 양으로 요구량을 만족시키지 못하면 교착상태인 것

• 회복 : 탐지기법으로 교착상태를 찾아내면 이를 회복하는데, 오퍼레이터가 직접 처리할 수도 있고 시스템이 자동으로 이를 복구하도록 할 수도 있음

  • 교착상태에 빠진 프로세스를 모두 중단시키면, 간단하지만 기존에 수행되고 있던 연산의 결과가 모두 없어지는 상황이 발생함(당연히 이를 다시 복원하기 위한 비용이 필요)
  • 부분적으로 종료할 경우에는, 이를 위해 프로세스의 우선 순위, 진행 정도, 사용하던 자원에 대한 정보 등의 요소를 고려하고 프로세스를 하나씩 종료하면서 교착상태를 재확인 하기 위한 비용 또한 감수해야 함
  • 부분 종료시 사용중이던 자원을 회수하는 방법은 프로세스로부터 자원을 단계쩍으로 선점하여, 이 자원들을 교착상태(사이클)가 없어질 때까지 다른 프로세스에 할당하는 것
    • 희생자 선택 : 전체적인 종료 비용의 최소화를 하기 위해, 교착상태인 프로세스가 소유하던 자원의 양과 프로세스 수행 시간 등을 고려하여 자원 선점 순서를 결정
    • 복귀 : 프로세스로부터 자원을 선점하면, 해당 프로세스를 어떤 상태로 놓을 것인지를 결정
      • 완전 복귀(Total Rollback) 보다는 안전한 상태를 위해 필요한 정도까지 복귀시키는 것이 더욱 효율적
    • 기아 상태 : 자원들이 항상 동일한 프로세스에 의해 선점되지 않도록 해야 함
      • 단순히 비용에 기반한 선택만이 능사는 아니며 비용요소와 함께 롤백 횟수까지 포함시킴