자원 할당 그래프 알고리즘과 은행원 알고리즘
저번 포스팅에 이어서 교착상태를 피하는 방법을 정리하려고 한다.
자원 할당 그래프
자원 할당 그래프 알고리즘을 알기 위해선 먼저 자원 할당 그래프에 대해서 알아야 한다.
프로세스가 자원을 요청하고 자원이 프로세스에게 할당되는 방향성을 가진 그래프로 교착 상태 발생 여부를 탐지할 수 있는 그래프이다.
간단한 자원 할당 그래프 예시
P는 프로세스, R은 자원을 나타낸다.
교착상태가 발생한 그래프 예시
P3은 R3에게 자원을 요청했고 R3는 P2에게 자원을 제공하고 있으며 P2는 R2에게 자원을 요청했고 R2는 P3에게 자원을 제공 중이다.
결국 P3->R3->P2->R2->P3 같은 사이클이 돌고 있다.
마찬가지로 R3에서 P1에게 제공하는 사이클로 돌게 되면 P3->R3->P1->R1->P2->R2->P3로 사이클이 만들어져 이 상태를 교착 상태가 발생했다고 한다.
사이클이 존재하지만 교착 상태가 아닌 그래프의 예시
이번에도 P2->R2->P1->R1->P2 사이클이 존재하지만 이건 교착상태가 아니다. P3 나 P4가 작업을 다 마치고 자원을 돌려주면 교착상태가 해제되기 때문이다.
정리
- 자원 할당 그래프로 교착 상태 발생 여부를 확인할 수 있다.
- 그래프에 cycle이 없으면 교착 상태가 아니다.
- 그래프에 cycle이 존재한다면
- 다른 프로세스가 작업을 완료하고 자원을 반납했을 때 자원의 무한 대기가 풀리는 상태
- 모든 프로세스가 서로의 자원을 요구하면서 무한정 대기하는 교착 상태 발생
자원 할당 그래프 알고리즘
위 내용에서 클레임 화살표라는 것이 더 추가된다. 클레임 화살표은 P(i) 프로세스가 미래에 R(j)를 요청할 수도 있다는 의미이고 주로 점선 화살표로 표시한다.
Cycle 생성 여부 조사할 때 프로세스가 n개일 때 O(N^2) 시간이 걸린다고 한다.
교착 상태 방지 예시
여기서 R1의 자원을 P2가 요청해서 할당받았다.
이때 P1이 R1에게 자원을 요청하려고 한다면 Cycle이 만들어지고 교착 상태가 발생되기 때문에 R1에 대한 요청을 받아주지 않으며 교착 상태 발생을 막는다.
은행원 알고리즘
교착상태에서 빠질 가능성을 안전상태와 불안전상태로 나누며 체크하고 안전상태를 유지할 수 있는 요구만 수락하고, 나머지 요구는 안전상태를 만족할 때까지 계속 거절하는 방식이다.
쉽게 말하면 최소한 한 프로세스가 필요한 모든 자원은 항상 가지고 있어야 된다는 개념이다.
안전상태
시스템이 교착상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄 수 있는 상태로 안전순서열이 존재하는 상태를 말한다.
안전순서열이란? 순서 있는 프로세스의 집합, 각 프로세스에 대해 추가로 요구할 수 있는 자원 소요량이 현재 가용 상태를 말한다.
불안전상태
안전순서열이 존재하지 않는 상태를 말하고 교착상태이기 위한 필요조건이다. 불안전상태라고 해서 무조건 교착상태가 발생하는 것은 아니다.
은행원 알고리즘 예시
용어 설명
- Allocated은 할당되는 자원의 양
- Maximum은 프로세스가 필요한 자원의 양
- Available은 자원 할당이 가능한 남은 자원의 양
- Need은 프로세스가 아직 더 필요한 자원의 양
Need 값 = Maximum 값 - Allocated 값으로 나타낸다.
P1~P4 순회를 하며 Need 값 <= Available 값 이 만족하는지 찾는다.
P2에서 만족을 하기 때문에 자원을 할당해 주고 작업이 끝났다고 가정하고 자원을 돌려받는다. Available = Available + Allocated 하고 다시 P1~P4까지 찾는다.
그다음 순회에서 P4에서 만족하므로 위와 같이 Available = Available + Allocated 하고 다시 P1~P4까지 찾는 과정을 반복해 모든 프로세스가 완료될 때까지 반복한다.
결과적으로 P2 -> P4 -> P3 -> P1 순서일때 안전상태가 있다.
은행원 알고리즘의 단점
- 사용자 수가 일정해야 함
- 할당할 수 있는 자원의 수가 일정해야 함
- 교착 상태 회피 알고리즘을 실행하면 시스템 과부하가 증가함
- 자원 이용 효율이 낮음
정리
- 각각의 프로세스가 지금 갖고 있는 자원에서 최대 자원 요구량의 상황까지 고려하면서 교착 상태가 일어나지 않도록 회피하는 것이 목표
- 자원이 instance가 한 개일 때는 자원 할당 그래프 알고리즘을 사용하고 자원이 instance가 여러 개일 때 은행원 알고리즘을 사용