Computer Structure & OS(13) - 교착 상태

1) 교착 상태란

    1-1) 식사하는 철학자 문제

    1-2) 자원 할당 그래프

    1-3) 교착 상태 발생 조건

2) 교착 상태 해결 방법

    2-1) 교착 상태 예방

    2-2) 교착 상태 회피

    2-3) 교착 상태 검출 후 회복

 

 

 

 

 

 

1) 교착 상태란

1-1) 식사하는 철학자 문제

• 식사하는 철학자 문제(dining philosphers problem) : 교착 상태의 발생을 보여 주는 고전적인 예시
  • 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어듦
  • 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어듦
  • 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간 동안 식사를 함
  • 식사 시간이 끝나면 오른쪽 포크를 내려놓음
  • 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓음
  • 다시 맨 첫 번째 과정부터 반복함
  • 하지만 위의 과정은 결과적으로 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황이 발생할 수 있음
• 교착 상태(deadlock) : 일어나지 않을 사건을 기다리며 무한히 대기하는 현상
• 뮤텍스 락에서도 교착 상태는 발생할 수 있음
• 교착 상태를 해결하기 위해서는 첫째, 교착 상태가 발생했을 때의 상황을 정확히 표현해 보고, 둘째, 교착 상태가 일어나는 근본적인 이유에 대해 알아야 함

 

1-2) 자원 할당 그래프

• 자원 할당 그래프(resource-allocation graph) : 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 간단한 그래프
• 즉, 자원 할당 그래프를 이용해 교착 상태를 표현할 수 있음
• 자원 할당 그래프의 작성 규칙
  • 첫째, 프로세스는 원으로, 자원의 종류는 사각형으로 표현함
  • 둘째, 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현함
  • 셋째, 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시함
  • 넷째, 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시함
• 교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띄고 있음

 

1-3) 교착 상태 발생 조건

• 교착 상태 발생 조건은 '상호 배제', '점유와 대기', '비선점', '원형 대기'임
• 상호 배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때, 즉 상호 배제(mutual exclusion) 상황에서 교착 상태가 발생할 수 있음
• 점유와 대기 : 프로세스가 어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있음(여기서 '점유와 대기(hold and wait)'는 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태를 의미함)
• 비선점 : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못했기 때문에(비선점; nonpreemptive) 교착 상태가 발생했다고 볼 수 있음
• 원형 대기 : 자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 수 있는데 이렇게 프로세스들이 원의 형태로 자원을 대기하는 것을 원형 대기(circular wait)라고 함
• 단, 자원 할당 그래프가 원의 형태를 띄지 않는다면 교착 상태는 발생하지 않으나, 원의 형태를 띈다고 해서 반드시 교착 상태가 발생하는 것은 아님

 

 

2) 교착 상태 해결 방법

2-1) 교착 상태 예방

• 교착 상태 예방 : 프로세스들에 자원을 할당할 때 상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나의 조건이라도 만족시키지 않게 할당하면 교착 상태는 발생하지 않는다는 것을 의미함(즉, 교착 상태의 발생 조건 중 하나를 충족하지 못하게 하는 방법을 의미함)

 

2-2) 교착 상태 회피

• 교착 상태 회피 : 교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당하는 방식(즉, 안전 상태를 유지할 수 있는 경우에만 자원을 할당하는 방법을 의미함)
• 교착 상태 회피 방식에서는 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주함
• 안전 상태(safe state) : 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
• 불안전 상태(unsafe state) : 교착 상태가 발생할 수도 있는 상황
• 안전 순서열(safe sequence) : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
• 즉, 안전 상태는 안전 순서열이 존재하는 상태를 의미하고, 불안전 상태는 안전 순서열이 없는 상태를 의미함
• 프로세스와 스레드는 자원을 사용하기 위해 1) 우선 자원을 운영체제에게 요청하고, 2) 운영체제로부터 자원을 할당받아 사용하고, 3) 자원의 사용이 끝났다면 자원을 반환함
• 운영체제가 교착 상태를 회피하기 위해서는 시스템 상태가 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하면 됨(즉, 교착 상태 회피 방식은 항시 안전 상태를 유지하도록 자원을 할당하는 방식이라 보면 됨)

 

2-3) 교착 상태 검출 후 회복

• 교착 상태 검출 후 회복 : 교착 상태 발생을 인정하고 사후에 조치하는 방식(즉, 교착 상태 발생 여부를 주기적으로 검사하고, 교착 상태가 발생하면 그때그때 회복하는 방식을 의미함)
• 교착 상태 회복 방식
  • 선점을 통한 회복 : 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식으로, 즉 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식을 의미함
  • 프로세스 강제 종료를 통한 회복
    • 운영체제는 교착 상태에 놓인 프로세스를 모두 강제 종료할 수도 있고, 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료할 수도 있음
    • 전자는 한 방에 교착 상태를 해결할 수 있는 가장 확실한 방식이지만 그만큼 많은 프로세스들이 작업 내역을 잃게 될 가능성이 있음
    • 후자는 작업 내역을 잃는 프로세스는 최대한 줄일 수 있지만 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기함
• 교착 상태를 아예 무시하는 방법도 있는데 드물게 발생하는 잠재적 문제를 무시로 대처하는 방식으로 타조 알고리즘(ostrich algorithm)이라는 방식도 있음