혼자 공부하는 컴퓨터 구조 + 운영체제를 읽고 공부한 내용입니다.교착상태란
두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다리면 그 어떤 프로세스도 진행이 될 수 없는 상태를 교착 상태라고 말한다.
식사하는 철학자 문제
식사하는 철학자 문제는 교착 상태를 이해하는데 아주 좋은 예시이다.
원탁에 책상에 다섯 명의 철학자가 앉아 있다.
이 철학자들 앞에는 식사가 있고 철학자들 사이에는 포크가 있다.
여기서 한가지 조건을 걸면 식사를 먹기 위해서는 두 개의 포크를 사용해서만 먹어야 한다.
여기서 순서를 잘 정해서 식사를 하면 모두가 식사를 맛있게 할 수 있다.
하지만 모든 철학자 동시에 포크를 들개 되면 모두가 1개의 포크만을 들고 있고
나머지 포크가 생길 때까지 기다리기만 한다면 그 누구도 식사를 할 수 없다.
이렇게 일어나지 않을 일에 대해서 기다리면 진행이 되지 않는 상황을 교착 상태라고 한다.
이를 프로세스에 적용을 하면 A프로세스와 B프로세스가 있을 때,
각각 서로 필요한 자원이 2개가 같고 각각 1개씩 가지고 있을 때
나머지 하나의 자원을 기다리면서 A프로세스, B프로세스 모두 진행이 되지 않는 상황이다.
자원 할당 그래프
교착 상태를 단순하게 표현하고 한 눈에 알아볼 수 있는 방법으로 자원 할당 그래프가 있다.
자원 할당 그래프는 다음과 같은 규칙으로 그려진다.
먼저, 프로세스는 원으로 자원은 사각형으로 그린다.
사용할 수 있는 자원의 갯수는 자원의 사각형 내의 점으로 표현한다.
프로세스가 어떤 자원을 할당 중이라면 자원에서 프로세스로 화살표를 그린다.
프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 그린다.
이 자원 할당 그래프를 식사하는 철학자 문제에 적용을 해보면 아래 그림과 같이 나타난다.
식사하는 철학자 문제의 자원 할당 그래프를 보면 교착 상태의 그래프는 원을 그린다는 특징이 있다.
교착 상태 발생 조건
교착 상태 발생 조건으로 상호 배제, 점유와 대기, 비선점, 원형 대기가 있다.
위 4가지 조건이 모두 충족이 되면 교착 상태가 발생을 한다.
상호 배제는 해당 자원을 한 번에 하나의 프로세스만 이용 가능한 것인데
교착 상태의 문제는 하나의 자원을 하나의 프로세스만 이용 가능하기 때문에 다른 프로세스가 이용할 수 없어서
끝날 때까지 기다릴 수 밖에 없기 때문에 교착 생태가 발생을 한다.
만약, 여러 프로세스가 이용이 가능했다면 교착 상태가 발생하지 않을 수도 있었을 것이다.
점유와 대기는 자원을 보유한 체 다른 자원을 기다리는 상태이다.
내가 자원을 보유한 체 가다리면 보유하고 있는 자원을 필요로 하는 다른 프로세스도 계속 기다려야 하기 때문이다.
이 점유와 대기가 겹친다면 교착 상태가 발생한다.
비선점은 다른 프로세스가 사용중인 자원을 빼앗지 않는 것이다.
선점하지 않고 비선점하기 때문에 프로세스가 끝날 때까지 기달리 수 밖에 없다.
즉, 프로세스가 끝나지 않고 계속 가지고 있다면 무한 대기를 해야 한다.
원형 대기는 자원 할당 그래프의 모양이 원형이라는 것이다.
위에서 언급을 했듯이 교착 상태가 발생한 자원 할당 그래프의 특징은 원을 그린다는 것이다.
이렇게 자원을 기다리는 그래프의 형태가 원을 그릴 때, 교착 상태가 발생한다.
교착 상태 해결 방법
교착 상태의 해결 방법으로 예방, 회피, 검출과 회복이 있다.
교착 상태 예방
교착 상태 예방은 프로세스들이 자원을 할당 받을 때, 상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나의 조건이라도 발생하게 하지 않은 것이다.
상호 배제의 경우, 모든 자원을 공유하게 만드는 것이다.
하지만 현실적으로 모든 자원의 상호 배제를 없애는 것은 어렵다.
그래서 현실에서 사용하기가 어렵다.
점유와 대기의 경우, 특정 프로세스에게 자원을 모두 할당하거나,할당하지 않는 방식으로 배분을 하면 예방이 된다.
하지만 이렇게 되면 자원를 필요로 하는 프로세스에게 자원이 할당이 되지 않을 것이고 기다려야 한다.
이는 오래 기다라는 프로세스와 할당이 되어서 쓰지 못하는 자원이 발생하면 자원의 활용률이 낮아진다.
비선점은 다른 프로세스의 자원 선점함으로 막을 수 있다.
하지만 모든 자원을 선점할 수 있는 것은 아니다.
즉, 프린터와 같이 이용 중에는 선점이 불가능한 자원들이 있다.
그래서 범용성이 떨어진다.
원형 대기은 모든 자원의 번호를 붙히고 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않는다.
식사하는 철학자 문제를 예시로 들면
포크에 번호를 붙히고 낮은 포크를 들지 못하게 하면 원형이 생기지 않고 일렬로 식사를 하는 것과 마찬가지이다.
교착 상태 회피
교착 상태 회피는 교착 상태가 발생하지 않을 만큼만 조금씩 자원을 할당 받는 것이다.
프로세스들에 분배할 수 있는 양을 고려해서 교착 상태가 발생하지 않을 만큼만 배분을 하는 것이다.
이 방법을 안전 상태, 불안전 상태, 안전 순서열을 알아야 한다.
안전 순서열은 교착 상태가 없이 프로세스에 자원을 할당할 수 있는 순서을 말한다.
이 안전 순서열에 의해서 교착 상태가 발생하지 않는 상태를 안전 상태라고 한다.
반면, 불안전 상태는 안전 순서열이 없는 상태이다.
예시로
할당할 수 있는 자원이 12개,
프로세스 A,B,C에 할당한 자원이 9개
이제 할당할 수 있는 자원이 3개라고 하자.
프로세스 A가 요구하는 자원 10개중 할당한 자원 5개,
프로세스 B가 요구하는 자원 4개중 할당한 자원 2개,
프로세스 c가 요구하는 자원 9개중 할당한 자원 2개라고 하자.
그러면 먼저 프로세스 B에게 2개를 할당하고 작업이 완료되면 자원을 반화함으로
남은 자원을 5개가 된다.
이 5개를 프로세스 A에게 할당을 하고 작업이 완료되면 자원을 반환하고
남은 자원은 총 10개 된다.
이제, 프로세스C에게 7개를 할당해서 프로세스C의 작업도 마무리를 한다.
프로세스 B -> 프로세스 A -> 프로세스 C 순이 안전 순서열이고
이 상태를 언전 상태라고 한다.
교착 상태 검출 후 회복
교착 상태 검출 후 회복은 교착 상태가 발생한 것을 인정하고 사후 조치를 받는 것이다.
이 방법에는 선점을 통한 회복, 프로세스 강제 종료를 통한 회복이 있다.
선점을 통한 회복은 교착 상태가 회복이 될 때까지 한 프로세스에게 자원을 몰아주는 방법이다.
프로세스 강제 종료를 통한 회복은 가장 단순하면서 확실한 방법이다.
교착 상태가 발생한 프로세스를 모두 종료할 수 있다.
이는 확실한 방법이지만 그 만큼 작업내용을 잃어버리는 단점이 있다.
다른 방법은 교착 상태가 발생 했을 때, 교착 상태가 없어질 때까지 프로세스를 종료하는 방법이다.
이 방법은 작업내용을 잃어버리는 것을 최소화할 수 있지만 교착 상태를 확인하는 과정에서 오버헤드가 발생을 할 수 있다.
