교착상태와 기아상태

교착상태와 기아상태

 

교착상태(DeadLock)란?

• 다중 프로그래밍 시스템에서는 프로세스가 결코 일어나지 않을 사건을 기다리는 상태가 되면 교착상태에 빠졌다고 말합니다. 두 개 이상의 프로세스들이 사용할 자원을 할당받기 위해 기다리고 있어서 결과적으로 아무것도 완료되지 못하는 상태를 말합니다.
• 교착상태는 하나 이상의 작업에 영향을 주기 때문에 무한 대기나 기아상태보다 더 심한 문제를 일으킵니다.
• 교착상태는 시스템 자원에 요구가 뒤엉킨 상태로, 두 프로세스가 사용하는 자원(비공유)을 서로 기다리고 있을 때 발생합니다.
• 따라서 둘 이상의 작업이 중단되고 프로세스들은 서로 사용할 자원을 기다리고만 있게 됩니다.
  

  

• 그림에서 P1 프로세스는 P2 프로세스가 사용 중인 자원 R1을 할당받기 위해 기다리고 있고, P2 프로세스는 P1 프로세스가 사용중인 R2를 할당받기 위해 기다리고 있습니다. 따라서, 두 프로세스는 서로 차단되어 영원히 기다리게 되는데 이 상황이 바로 교착상태입니다.
• 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때, 교착상태가 발생합니다.
• 초기 일괄 처리 시스템에서는 교착상태가 자주 발생하지 않았습니다. 일괄 처리 시스템에서는 운영체제가 요청한 자원을 준비 큐로 이동시키기 전에 먼저 사용 가능 여부를 확인했습니다. 반면, 대화식 시스템에서는 동적 자원을 공유하여 자원의 사용률을 높이는 과정에서 교착상태가 발생할 가능성이 있습니다.

 

교착상태 발생 조건

1. 상호배제(Mutual Exclusion)
   • 자원이 최소 하나 이상의 프로세스에 의해 비공유되어야 합니다. 즉, 한 번에 한 프로세스만 해당 자원을 사용할 수 있어야 합니다.
2. 점유와 대기(Hold and Wait)
   • 자원을 최소한 하나 보유하고 다른 프로세스에 할당된 자원을 얻으려고 기다리는 프로세스가 있어야 합니다.
   • 프로세스가 한 개 이상의 자원을 할당받은 후, 다른 프로세스에 할당된 자원을 기다리는 상태입니다.
3. 비선점(No Preemption)
   • 다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없습니다.
   • 즉, 사용 중인 자원을 다른 프로세스에게 양보하지 않는 것입니다.
4. 순환대기(Circular Wait)
   • 프로세스들이 순환(원형)을 이루어서 존재합니다. 이를 구성하는 각 프로세스는 이전 프로세스가 요청하는 자원을 점유하고 다음 프로세스가 점유하고 있는 자원을 요청하는 경우입니다.
   • 순환대기는 점유와 대기, 비선점, 상호배제 조건을 만족해야 발생할 수 있는 현상입니다.

 

선점 자원과 비선점 자원

컴퓨터의 자원은 성질에 따라 선점 자원과 비선점 자원으로 구분하여 생각할 수 있습니다. 선점 자원은 부작용 없이 소유한 프로세스에서 빼앗아 선점할 수 있는 자원입니다. 선점 자원의 예로는 메모리, 버퍼, 프로세스 등이 있습니다. 반면에 비선점 자원은 하나의 프로세스에서 빼앗아 선점할 수 없고, 부작용 없이 다른 프로세스에 할당할 수 없는 자원입니다. 비선점 자원의 예로는 프린터, CD 드라이브, 스캐너, 디스크 드라이브, 임계영역 등이 있습니다. 보통 교착 상태는 비선점 자원이 발생시킵니다.

 

교착상태 해결 방법

• 교착 상태를 해결하는 방법은 크게 다음 세 가지로 나눌 수 있습니다.
  1. 교착 상태가 발생하지 않도록 예방(Prevention)하는 방법
  2. 교착 상태의 발생 가능성을 배제하지 않고 이를 적절히 회피(Avoidance)하는 방법
  3. 교착 상태를 허용하되, 교착 상태를 탐지(Detection)하여 다시 회복하는 방법

1. 교착 상태 예방

1. 자원의 상호배제 조건 방지
   • 상호배제는 자원의 비공유가 전제되어야 합니다. 공유 자원은 배타적인 접근이 필요 없으므로 교착 상태가 발생하지 않습니다. 그러나 일반적으로 상호배제 조건을 허용하지 않으면 교착 상태를 예방할 수 없습니다.
   • 즉, 비현실적인 방법입니다.
2. 점유와 대기 조건 방지(일부 자원만 할당 방지)
   • 프로세스가 실행에 필요한 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류하여 대기 조건이 성립하지 않도록 하여 교착 상태를 예방합니다. 시스템 호출된 프로세스 하나를 실행하는 데 필요한 모든 자원을 먼저 할당하여 실행한 후 다른 시스템 호출에 자원을 할당하는 것입니다. 또다른 방법은 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용하는 것입니다.
   • 단점
     • 자원의 효율성이 너무 낮습니다.
     • 기아 상태가 발생할 수 있습니다.
3. 비선점 조건 방지(할당된 자원의 반납 가능)
   • 전제 조건은 이미 할당된 자원에 선점권이 없어야 한다는 것입니다.
   • 단점
     • 프로세서 레지스터나 기억장치 레지스터와 같이 쉽게 저장되고 이후 다시 복원하기 쉬운 자원에 사용 가능합니다. 하지만 프린터와 같은 자원에는 적용하기 어렵습니다.
4. 순환(환형) 대기 조건 방지(순환 대기 상황 회피)
   • 모든 자원에 일련의 순서를 부여하고 각 프로세스가 오름차순으로만 자원을 요청할 수 있도록 합니다.
   • 단점
     • 순환 대기 조건 방지는 프로세스의 속도를 떨어뜨리고 자원 접근을 불필요하게 거부하기 때문에 비효율적입니다.

교착 상태 회피

• 교착 상태의 예방은 장치의 효율성과 시스템 처리량을 떨어뜨리는 결과를 초래했습니다. 교착 상태 회피 방법은 덜 엄격한 조건을 요구하여 자원을 좀 더 효율적으로 사용하는 것이 목적입니다. 교착 상태의 회피 방법은 다음 두 가지로 설명할 수 있습니다.
1. 프로세스의 시작 중단
   • 교착 상태 회피 알고리즘은 시스템이 순환 대기 조건이 발생하지 않도록 자원 할당 상태를 검사합니다. 자원 할당 상태는 사용 가능한 자원 수, 할당된 자원 수, 프로세스들의 최대 요청 수로 정의합니다. 시스템의 상태는 안정 상태와 불안정 상태로 나눌 수 있습니다. 교착 상태는 불안정 상태에서 발생합니다. 그러나 불안정 상태가 교착 상태인 것은 아닙니다. 단지 불안정 상태는 교착 상태가 되기 쉬울 뿐입니다.
     

     

     
     여분 자원 수가 3개 이므로, P2 → P0 → P1 → P3 순서로 할당을 하면 안정 조건을 만족합니다.
     

     

     
     불안정 상태에서는 사용 가능한 자원 한 개를 어떤 프로세스에 할당해도 만족시킬 수가 없습니다. 그러나 프로세스 P0에 남은 장치를 할당하고 반납하기 전까지 다른 프로세스가 자원을 요청하지 않으면 교착 상태를 회피할 수 있습니다. 불안정 상태는 교착 상태가 발생할 수 있는 가능성이 있다는 의미이지 반드시 교착 상태가 발생한다는 의미는 아닙니다. 위의 안정 상태 자원에서 P0와 P1이 자원을 한 개 더 요청했다면 P0와 P1의 요청의 허용 여부에 따라 안정 상태 또는 불안정 상태로 변합니다.
2. 자원 할당 거부 (은행가 알고리즘)
   • 은행가 알고리즘은 프로세스가 자원을 요구할 때 시스템이 자원을 할당한 후 안정 상태로 남아있게 되는지를 사전에 검사하여 교착 상태를 회피하는 방법입니다.
   • 여러 유형의 자원을 가진 시스템에서 사용되며, 시스템이 자원을 할당한 후에도 안정 상태로 남아있는지 검사하여 안정 상태에 있으면 자원을 할당하고, 그렇지 않으면 다른 프로세스들이 자원을 해제할 때까지 대기합니다.
     

     

     1. START 단계에서는 자원 상황과 자원 종류의 최대 수를 파악합니다.
     2. 자원 할당 요청 단계에서는 프로세스의 자원 할당 요구를 요청받습니다.
     3. 안정한가? 단계에서는 안정 알고리즘을 사용하여 시스템의 상태를 점검한 후, 자원 할당 여부를 결정하게 됩니다.

      

   • 자원 할당을 효율적으로 수행하여 교착 상태를 회피하는 알고리즘인 은행가 알고리즘은 n은 프로세스 수, m을 자원의 수라고 하면 다음 자료구조가 필요합니다.
     • Available : 각 형태 별로 사용 가능한 자원 수(사용 가능량)를 표시하는 길이가 m인 벡터입니다. Available[j] = k이면, j번째 자원을 k개 사용할 수 있다는 의미입니다.
     • Max : 각 프로세스 자원의 최대 요청량(최대 요구량)을 표시하는 n*m 행렬입니다. Max[i,j] = k이면, 프로세스 Pi는 자원 Rj를 최대 k개까지 요청할 수 있다는 의미입니다.
     • Allocation : 현재 각 프로세스에 할당되어 있는 각 형태의 자원 수(현재 할당량)를 정의하는 n*m 행렬입니다. Allocation[i,j] = k이면, 프로세스 Pi는 자원 Rj개를 k개 할당받고 있다는 의미입니다.
     • Need : 각 프로세스에 남아있는 자원 요청(추가 요구량)을 표시하는 n*m 행렬입니다. Need[i,j] = k이면, 프로세스 Pi는 자신의 작업을 종료하기 위해 자원 Rj가 k개 더 필요하다는 의미입니다.
     • 여기서 Need[i,j] = Max[i,j] - Allocation[i,j] 라는 식이 성립합니다. 이 알고리즘을 간단하게 구현하려면, 먼저 다음 제약을 두어야 합니다.
       • 시간이 흐르면서 벡터의 크기와 값이 변합니다.
       • X와 Y는 길이가 n인 벡터입니다.
       • X[i] <= Y[i]이고, i = 1,2,...,n 일때만 X <= Y 입니다.
       • X = (0,3,2,1)이고, Y = (1,7,3,2)이면 X <= Y 입니다.
       • X <= Y이고, X != Y이면, X < Y 입니다.
   • 프로세스 Pi가 자원을 요청하면 다음과 같은 동작이 일어납니다.
     • 1단계 : Request[i] <= Need[i] 이면 2단계로 이동하고, 그렇지 않으면 프로세스가 최대 요청치를 초과하기 때문에 오류 상태가 됩니다.
     • 2단계 : Request[i] <= Available[i] 이면 3단계로 이동하고, 그렇지 않으면 자원이 부족하기 때문에 Pi는 대기합니다.
     • 3단계 : 시스템은 상태를 다음과 같이 수정하여 요청된 자원을 프로세스 Pi에 할당합니다.
       • Available[i] = Available[i] - Request[i];
       • Allocation[i] = Allocation[i] + Request[i];
       • Need[i] = Need[i] - Request[i];

        

       
       

       

       
       현재 이 시스템은 안정 상태에 있다고 할 수 있습니다. 그 이유는 현재 Available 자원이 [3,3,1] 인데, P1, P2 프로세스에는 할당할 수 없지만, P3 프로세스에 할당하여 프로세스 P3를 실행한 후 할당된 자원을 해제하면 Available 자원은 [5,4,4]가 됩니다.
       따라서 <P3, P2, P1> 또는 <P3, P1, P2> 순서는 안정 조건에 해당됩니다.
   • 은행가 알고리즘의 한계
     • 할당할 수 있는 자원의 수가 일정해야 하는데 남아 있는 자원 수를 파악하기가 매우 어렵습니다.
     • 사용자 수가 항상 변합니다.
     • 시스템 과부하가 증가합니다.
     • 프로세스는 자원을 보유한 상태로 끝낼 수 없습니다.
     • 사용자의 최대 필요량을 파악하기 어렵습니다.
     • 항상 불안정 상태르 방지해야 하므로 자원 이용도가 낮습니다.

교착 상태 회복

• 교착 상태에서 회복하려면 다음 알고리즘이 필요합니다.
  • 시스템 상태를 검사하는 교착 상태 탐지 알고리즘
  • 교착 상태에서 회복시키는 알고리즘
• 교착 상태를 파악하기 위해 교착 상태 탐지 알고리즘을 언제 수행해야 하는지 결정하기는 쉽지 않습니다. 교착 상태 탐지 알고리즘을 자주 실행하면 시스템의 성능은 떨어지지만, 교착 상태에 빠진 프로세스를 빨리 발견하여 자원의 유휴 상태를 방지할 수 있습니다. 하지만 자주 실행하지 않으면 반대의 상황이 발생합니다. 또, 탐지와 회복 방법은 필요한 정보를 유지하고 탐지 알고리즘을 실행시키는 비용뿐만 아니라 교착 상태에서 회복하는데 필요한 부담까지 요구합니다.

 

기아상태(Starvation)란?

• 기아상태란 프로세스의 우선순위가 낮아서 필요한 자원을 결코 할당받지 못하고 계속 기다리고 있는 상태를 의미합니다.
• 식사하는 철학자 문제

  

  • 식사하는 철학자 문제는 다수의 프로세스가 다수의 자원을 할당할 때의 상황을 나타낸 것으로, 철학자를 프로세스에, 젓가락(포크)을 자원에 비교하여 설명하는 문제입니다. 철학자들은 서로 대화할 수 없고, 스파게티를 먹기 위해서는 양쪽의 젓가락(포크)을 사용해야 합니다.
  • 만약, 모든 철학자들이 모두 왼쪽 젓가락을 잡고 오른쪽 젓가락을 집으려 하면 교착 상태에 빠지게 되어 모두 굶게 됩니다.
  • 교착 상태에 빠지지 않기 위해 철학자 4명만 테이블에 동시에 앉게 하는 방법, 양쪽 젓가락(포크) 모두 사용 가능할 때 젓가락(포크)을 집을 수 있도록 허용하는 방법 등으로 교착 상태를 방지할 수 있지만, 기아 상태를 해결해주지는 못합니다.
  • 철학자 4명이 동시에 식사를 하는 방법을 선택했는데 나머지 한 명의 철학자에게 젓가락(포크)을 사용할 기회가 오지 않아서 굶주리는 상황을 기아 상태(Starvation)라고 합니다.

   

 

 

References

• https://robodream.tistory.com/561
• https://m.blog.naver.com/dong5053/220717510273