2023년 9월 2일
자원 할당 그래프 (Resource Allocation Graph)
1. 자원할당 그래프 (Resource Allocation Graph)의 개념
- 교착상태 발견을 위해 프로세스와 자원과의 관계와 할당 상태를 표현하는 그래프
2. 자원 할당 그래프의 구성요소
구분 | 구성요소 | 표현 | 설명 |
---|---|---|---|
Vertex (정점) | 프로세스 | – 자원을 표현하는 프로세스 – 원으로 표현 | |
자원 | – 자원들의 집합을 표현 – 자원의 개수는 사각형 점으로 표현 | ||
Edge (간선) | 요청선 | – 프로세스에서 자원으로의 연결 – 자원에 있는 하나의 사각형 점 요청 | |
할당선 | – 자원에서 프로세스로 연결 – 프로세스는 자원을 할당 받아 점유 상태 |
- 요청선과 할당선의 화살표 시작점과 끝점을 명확하게 표시
3. 자원 할당 그래프 기반 교착상태 발생 시 회피 동작
상태 | 그래프 | 설명 |
---|---|---|
교착상태 발생 | – 순환구조에 의해 교착상태 발생 ① R1은 P1에게 자원 할당 ② R2는 P2에게 자원 할당 ③ P1은 R2에게 자원 요청 ④ P2는 R1에게 자원 요청 | |
교착상태 회피 | – 자원의 추가 투입으로 교착상태 회피 ① R1은 P1에게 자원 할당 ② R2는 P2에게 자원 할당 ③ R1은 P3에게 추가 자원 할당 ④ P1은 R2에게 자원 요청 ⑤ P2는 R1에게 자원 요청 |
- 교착상태 발견 및 회피를 위해 자원할당 그래프와 은행가 알고리즘(Banker’s Algorithm) 사용