[OS]교착상태(2)

📚교착상태 회피

교착상태 회피는 프로세스 자원 사용의 사전 정보를 활용하여 교착상태가 발생하지 않는 상태에 머물도록 하는 방법이다. 현재 할당된 자원, 가용상태의 자원, 프로세스들의 최대 요구량이 사전 정보로 활용된다.

📄안전상태와 안전순서열

안전상태는 교착상태가 발생하지 않는 상태를 말한다. 교착상태를 회피하면서 각 프로세스에 최대 요구량까지 자원을 할당할 수 있는 상태를 의미한다. 안전상태는 안전순서열이 존재하는데 이로 인해 프로세스가 당장 자원을 할당받지 못하더라도 다른 프로세스가 자원을 해제할 때까지 대기하면 결국 자원을 얻을 수 있어 교착상태에 빠지지 않을 수 있다.

불안전 상태는 안전순서열이 존재하지 않는 경우를 말한다. 교착상태는 불안전상태에 포함되지만 불안전상태라고 해서 무조건 교착상태인 것은 아니다.

교착상태는 불안전상태에서만 발생될 수 있으므로 교착상태를 회피하려면 항상 안전상태를 유지해야 한다. 안전상태를 유지하기 위해 프로세스가 자원을 요구하더라도 할당하지 않고 대기상태가 될 수 있다. 이에 따라 자원이용률은 낮아질 수 있다.

📚교착상태 회피 알고리즘

📄단위자원이 하나일 경우

변형된 자원할당 그래프를 이용하여 교착상태를 회피할 수 있다. 변형된 자원할당 그래프에서는 자원 정점에 표시하던 단위자원 개수는 사라지고 선언간선이 추가되었다. 선언간선은 요구간선과 동일하게 방향을 가지고 있지만 점선으로 표시한다.

프로세스가 자원을 요구할 때 선언간선은 요구간선으로 바뀐다. 그래프에서 요구가 할당간선으로 바뀌고나서 사용이 끝나고 자원이 프로세스에서 해제될 때 할당간선은 선언간선으로 바뀐다. 프로세스가 자원을 다시 요구할 수 있기 때문에 선언간선으로 바뀌는 것이다.

요구간선은 자원이 가용한 상태이고 프로세스에 할당해도 사이클이 생기지 않는 경우에만 할당간선으로 바꾼다. 할당간선으로 바꿨을 때 사이클이 생기면 안전순서열이 존재하지 않아 불안전상태가 되므로 자원을 할당하지 않고 요구간선인 채로 둔다. 간단하게 말하면, 교착상태를 회피하기 위해 변형된 자원할당 그래프에서 사이클이 생기지 않게 만들면 되는 것이다.

위 그래프에서 프로세스 p1이 자원 r2를 요구한다고 했을 때 r2는 가용상태이고 이를 할당하면 아래 그림처럼 사이클이 발생하지 않아 안전상태가 된다.

하지만 프로세스 p2가 자원 r2를 요구한다고 했을 때 r2가 가용상태이고 이를 할당하면 아래처럼 사이클이 발생하여 불안전상태가 된다. 따라서 자원을 할당하지 않고 요구간선(p2, r2)인 상태를 유지한다.

📄단위자원이 여러 개일 경우

단위자원이 여러 개일 경우 보통 은행원 알고리즘을 이용하여 교착상태를 회피할 수 있다. 은행원 알고리즘은 자원을 요구받으면 그 자원을 할당해주고 그 뒤의 상태를 여러 데이터를 이용하여 계산해서 안전상태인지 아닌지 확인 후, 안전상태일 때만 자원을 할당하는 방법이다.

void bank(REQ)
{
    if(!(REQ <= NEED))
    {
        오류;
    }
    
    if(!(REQ <= AVAIL))
    {
        p를 대기시킴;
    }

    // REQ<=NEED이고 REQ <= AVAIL인 경우
    // 할당 후와 같은 상태로 만듦
    ALLOC = ALLOC + REQ
    NEED = NEED - REQ
    AVAIL = AVAIL - REQ
    // 할당 후의 상태가 안전상태인지 조사
    
    status = safe(상태 데이터);

    if(status == true)    // 안전상태
    {
        REQ대로 할당;
    }
    else                  // 불안전상태
    {
        P를 대기시킴;
        상태 데이터 복구;
    }
}

📚교착상태 탐지 및 복구

교착상태 탐지 및 복구는 사후에 처리하는 방법이다. 주기적으로 쇼사니와 코프만 알고리즘을 수행하여 교착상태 여부를 조사하고 교착상태를 복구한다.

boolean detect(상태 데이터)
{
    // WORK와 FINISH 초기화
    WORK = AVAIL;

    for(i = 1; i <= n; ++i)
    {
        if(ALLOC != 0)
        {
            FINISH[i] = false;
        }
        else
        {
            FINISH[i] = true;
        }
    }

    // 교착상태가 아닌 프로세스 찾기
    for(l = 1; l <=n; ++l)
    {
        for(i = 1; i <= n; ++i)
        {
          if(FINISH[i] == false && REQ <= WORK)
          {
              WORK = WORK + ALLOC
              FINISH[i] = true;
              break;
          }
        }

        if(i > n)
        {
          break;
        }
    }

    if(FINISH[i] == false인 i 존재)
    {
        return true;    // 교착상태
    }
    else
    {
        return false;   // 교착상태 아님
    }
}

📄탐지

Shoshani와 Coffman 알고리즘은 은행원 알고리즘의 안전 알고리즘과 유사하지만 현재 상태의 모든 자원 요구량을 고려하여 교착상태 여부를 확인한다는 점에서 차이가 있다.

📄복구

교착상태 복구의 주체는 두 가지가 있다. 프로그래머에게 교착상태가 발생했다는 것을 알려 직접 수작업으로 처리하도록 하는 것과 운영체제가 자동으로 복구하는 방법이 있다.

교착상태 복구 방법은 프로세스를 종료시키거나 프로세스가 할당받은 자원을 해제하는 방법이 있다.

• 프로세스를 종료하는 방법
  
  1. 모든 교착상태 프로세스를 종료시키는 것
     이 방법은 교착상태를 확실하게 종료한다는 장점이 있지만 프로세스들이 진행했던 내용에 대한 복원비용이 크다는 단점이 있다.
     
     
  2. 사이클이 제거될 때까지 프로세스를 하나씩 종료시키는 것
     종료할 프로세스를 선택하기 위해 우선순위, 사용된 자원 유형 등 다양한 요소를 고려해야 한다. 프로세스 종료 후 교착상태를 재확인하기 위한 오버헤드가 필요하다.

• 할당받은 자원을 해제하는 방법
  교착상태 사이클이 제거될 때까지 프로세스에 할당된 자원을 단계적으로 선점하여 자원을 다른 프로세스에 할당하는 방법이다.

교착상태를 복구하더라도 다시 교착상태가 발생할 수 있다. 그때마다 동일한 프로세스가 복구를 위해 선택되면 기아상태에 빠질 수 있다. 따라서 복구를 위한 프로세스를 선택할 때 기아상태에 빠지지 않도록 해야 한다.