교착 상태
교착 상태를 해결하는 것은 운영체제가 해야하는 중요한 임무이다. 교착 상태란 무엇일까?
프로세스를 실행하기 위해서는 자원이 필요하다. 두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다리면 둘 중 어느 프로세스도 더이상 진행할 수 없는 교착상태가 된다.
위의 이미지와 같이 게임 프로세스는 자원 A를 점유하고 있고, 웹 브라우저 프로세스는 자원 B를 점유하고 있다고 가정해보자.
그리고, 게임 프로세스는 자원 A를 점유한 채 자원 B의 사용이 끝나길 기다리고, 웹 브라우저 프로세스는 자원 B를 점유한채 자원 A의 사용이 끝나기를 기다리는 상황이 발생할 수 있다.
이 경우 두 프로세스는 계속해서 실행도 못한 채 서로 끝나기를 기다리게 될 것이다. 이를 교착상태라고 한다.
자원 할당 그래프
교착 상태는 자원 할당 그래프(resource-allocation graph)를 통해 단순하게 표현할 수 있다. 자원 할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 프로세스가 어떤 자원을 기다리고 있는지 표현하는 간단한 그래프이다.
자원 할당 그래프는 아래와 같은 규칙으로 그려진다.
-
프로세스는 원으로, 자원의 종류는 사각형으로 표현.
-
사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현한다.
예를 들어, 하드 디스크가 세 개 있는 경우, 자원의 종류는 하드 디스크 하나, 사용 가능한 하드 디스크 개수는 세 개이다. 즉, 하드 디스크 사각형 안에 세 개의 점으로 표현한다.
-
프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다.
교착 상태 발생 조건
교착 상태가 발생할 조건에는 네 가지가 있다. 상호 배제, 점유와 대기, 비선점, 원형 대기이다.
교착 상태를 발생 시키는 조건을 하나씩 알아보자.
상호 배제
교착 상태가 발생한 근본적인 원인은 하나의 자원을 한 번에 하나의 프로세스만 이용 가능했기 때문이다.
한 프로세스가 사용하고 있는 자원을 다른 프로세스가 사용할 수 없을 때, 상호 배제(mutual exclusion) 상황에서 교착 상태가 발생할 수 있다.
점유 대기
위에서 예시로 든 상황에서, 게임 프로세스와 웹 브라우저는 자원을 점유한 채 다른 자원을 기다렸기 때문에 문제가 발생 했었다. 이렇게 자원을 할당받은 상태에서 다른 자원을 할당받기 기다리는 상태를 점유와 대기(hold and wait)라고 한다.
비선점
만약, 게임 프로세스가 웹 브라우저가 점유 중이었던 자원을 강제로 빼았을 수 있었다면 교착 상태는 발생하지 않았을 것이다. 즉, 프로세스가 자원을 비선점(nonpreemptive) 하고 있었기 때문에 교착 상태가 발생했다고 볼 수 있다.
원형 대기
