교착 상태
프로세스를 실행하기 위해서는 자원이 필요한데, 두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다린다면 그 어떤 프로세스도 더 이상 진행할 수 없는 교착 상태가 된다. 즉, 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 교착 상태(deadlock)라고 한다.
자원 할당 그래프
교착 상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있다. 자원 할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현한 간단한 그래프이다.
자원 할당 그래프에는 그를 그리기 위한 몇 가지 규칙이 존재한다.
1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현
2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
3. 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시
4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시
교착 상태 발생 조건
교착 상태 발생 조건에는 대표적으로 네 가지가 있다. 상호 배제, 점유와 대기, 비선점, 원형 대기이다.
1. 상호 배제(mutual exclusion)
교착 상태가 발생하는 근본적인 원인은 해당 자원을 한 번에 하나의 프로세스만 이용할 수 있기 때문인데, 프로세스도 마찬가지로 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때, 즉 상호 배제 상황에서 교착 상태가 발생할 수 있다.
2. 점유와 대기(hold and wait)
프로세스가 어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있다. 이렇게 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태를 점유와 대기라고 한다.
3. 비선점(nonpreemptive)
교착 상태가 발생하게 된 또 하나의 근본적인 문제는 프로세스가 자원을 비선점 하고 있기 때문인데, 비선점 자원은 그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있다. 즉, 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못했기 때문에 교착 상태가 발생했다고 볼 수 있다.
4. 원형 대기(circular wait)
프로세들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이루었기 때문에 교착 상태가 발생하기도 한다.
즉, 자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 수 있다. 이렇게 프로세스들이 원의 형태로 자원을 대기하는 것을 원형 대기라고 한다.
교착 상태 해결 방법
운영체제는 교착 상태를 예방, 회피, 검출 후 회복으로 해결한다.
1. 교착 상태 예방
교착 상태를 예방하는 방법은 교착 상태 발생 필요조건 네 가지 중 하나를 충족하지 못하게 하는 방법이 있다.
2. 교착 상태 회피
교착 상태 회피는 교착 상태가 발생하지 않을 정도로만 자원을 할당하는 방식이다. 이 방식에서는 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주한다.
이를 이해하기 위해서는 안전 순서열을 알아야 하는데, 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태를 안전 상태, 교착 상태가 발생할 수도 있는 상황을 불안전 상태라고 한다.
*안전 순서열은 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미한다.
3. 교착 상태 검출 후 회복
교착 상태 발생 여부를 주기적으로 검사하고, 교착 상태가 발생하면 바로바로 회복하는 방식이다.