자원 할당 그래프 알고리즘
자원당 인스턴스가 하나일때 사용하는 알고리즘이다.
자원 할 당 그래프는 프로세스의 자원 할당 상태를 표현해주는 그래프이다.
이미지 출처
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=three_letter&logNo=220380867227
동그라미는 프로세스, 네모는 자원, 점은 자원의 인스턴스를 의미.
프로세스 -> 자원은 프로세스가 자원을 요청하는 것.
자원 -> 프로세스는 프로세스가 자원을 소유한 것을 의미
자원 할당 그래프에 서클이 존재하지 않으면 데드락이 아님.
서클이 존재하면 데드락일수도 있고, 아닐수도 있다.
서클이 있지만 모든 프로세스가 서로의 자원을 요구하는 것이 아니면 데드락이 생기지 않음.
소유하고 있지만 요청을 하지 않으면 반납을 할 수 있기때문에 데드락이 발생하지 않음.
기본적인 자원 할당 그래프의 설명은 이렇게 된다.
이미지 출처
https://kpuls.tistory.com/61
실제로 데드락에 사용될때에는
데드락이 발생하는 상황이 되면 다른 프로세스의 요청을 받아들이지 않아서 데드락을 막는다.
은행원 알고리즘
은행원 알고리즘은 안전상태를 유지할 수 있는 요구만 수락하고 불안전 상태를 초래할 요구는 나중에 만족될 수 있을때까지 요청을 거절하는 알고리즘이다.
은행원 알고리즘이 수행되기 위해선 3가지가 필요하다.
- MAX
각 프로세스가 자원을 얼만큼 요청 할 수 있는가 - ALLOCATED
각 프로세스가 보유하고 있는 자원은 얼마인가 - AVAILABLE
시스템이 얼마나 자원을 보유하고 있는 가
시스템이 12의 자원을 가지고 있다고 가정을 할 때.
Pi에 각자 5,2,2 씩 보유하고 있다.
그러면 시스템은 총 3의 자원이 남는 상태이고, p1에 총 2개를 지원을 해줄 수 있다.
p1이 자원을 반환을 하면 시스템은 5개의 자원이 남고 p0에 나머지 자원들을 전부 할당을 해준뒤 p0가 자원을 반환을 하면 그때 p2에 나머지 필요한 자원들을 할당시켜줄 수 있다.
이렇게 데드락에 걸리지 않고 문제를 해결 할 수 있는 것을 안전 순서열이라고 한다.
하지만 시스템은 안전 상태에서 불완전 상태로 변할 수 도 있다.
단점
- 자원수가 일정해야함
- 프로세스 수가 일정해야함
- 항상 불안전 상태를 방지해야해서 자원 이용도가 낮음
- 최대 자원 요구량을 미리 알아야함
- 프로세스들은 유한한 시간안에 자원을 반납해야함
은행원 알고리즘은 매우 복잡하고, 오버헤드가 너무 크므로 현재 많이 채택하여 사용하는 방식은 아님.
학습에 참고한 사이트
