예방 > 회피(프로세스 시작 거부, 자원 할당 거부)
프로세스 시작 거부
- 클레임이 너무 많아지면 할당을 하지 않는 것
자원 할당 거부
- 자원 할당했을 때 불안전 상태가 되면 할당 하지 않는 것
- 은행가 알고리즘이 대표 알고리즘입니다.
- 일단 할당해 봅니다.
- 할당 후에도 안전상태인지 검사합니다.
은행가 알고리즘 예시를 봅시다.
최대 사용량 - 클레임의 수입니다.
지금 자원의 타입이 1가지 밖에 없습니다.
왼쪽, 오른쪽 예시 둘 다 자원의 총 수는 10개입니다.
현재 안전, 불안전 상태를 판별했으면 -> 결과를 자원 할당할지 안 할지를 결정합니다.
즉, 현재 사용량의 할당을 그대로 갈지 결정하는 것입니다.
왼쪽 예시를 봅시다.
P0은 5개를 필요로 합니다.
P1은 7개를 필요로 합니다.
P2는 2개가 필요로 합니다.
P3는 8개가 필요합니다.
P2를 끝내고 나면 여분 자원의 수는?
7개입니다.
아녔습니다.
3개 중에 2개를 사용 -> 여분 자원의 수 1 -> P2 끝나면 4 남음 -> 여분 자원의 수 5개
다음에 끝낼 수 있는 곳은 P0입니다.
P0를 끝내고 나면 여분 자원의 수는?
7개입니다.
다음에 끝낼 수 있는 곳은 P1입니다.
P1를 끝내고 나면 여분 자원의 수는?
8개입니다.
다음에 끝낼 수 있는 곳은 P3입니다.
P3를 끝내고 나면 여분 자원의 수는?
10개입니다.
끝납니다.
이렇게 안전하게 끝내는 순서가 있습니다.
오른쪽은 안전하게 끝내는 순서가 없습니다.
왜냐하면
P0은 2개를 필요로 합니다.
P1은 7개를 필요로 합니다.
P2는 2개가 필요로 합니다.
P3는 6개가 필요합니다.
남은 자원 수로 끝낼 수 있는 프로세스가 없기 때문입니다.
은행가 알고리즘은 유형당 자원이 한 개인 경우 적용할 수 있다?
P0이 1만큼 요청한 것이고
P1이 1만큼 요청한 것입니다.
위의 경우는
P2를 끝낼 수 있는 자원이 남아 있기 때문입니다.(안전 순서가 존재하기 때문입니다.)
아래의 경우는
자원의 수가 4개가 되면 P0,1,3 모두 끝낼 수 없기 때문에 불안전 상태입니다.
아래 경우는 교착상태인가요?
하지만 교착상태는 아닙니다.
P0에 자원 할당, P1에 자원 할당하는 것이 resource-Requesst algorithm입니다.
그것이 안전하지 불안 전하 지를 판별하는 것이 safy algorithm입니다.
문제)
안전상태입니다. 그러면 A는 어떤 값을 가져야 할까요
Allocation이 Max보다는 작아야 합니다.
남은 자원의 수는 2개입니다.
프로세스 B가 끝나야 하니 필요한 클레임은 4~6일 것 같습니다.
4 <= A <= 6입니다.
은행가 알고리즘으로 자원할당을 거부하는 과정
P2 -> R1을 클레임으로 바꿔봤습니다.
그런데 R2는 자원이 남기 때문에(resource-request algorithm) P2에 할당을 해본 것입니다.
그리고 할당해도 되는지 안되는지 safety algorithm을 봐야 합니다.
안전 상태일까요 불안전 상태일까요? 불안전 상태입니다.
그래프에서 사이클이 있다면 불안전 상태입니다.
P2를 끝낼라고 하면 R1을 할당해줘야 하는데 할당을 못합니다.
P1을 끝낼라고 하면 R2를 할당해줘야 하는대 할당을 못합니다.
그래서 안전 순서가 없습니다.
그래서 safe 한 지를 봅니다.
safe 한가요? no
유형당 자원이 1개(= 리소스 박스에 동그라미)에 은행가 알고리즘은 적용할 수 있습니다.
상세한 설명
왼쪽 그림에서 P2가 R2를 요청하면 Resource-Request Algorithm으로 R2를 할당하여 오른쪽 그림같이 됩니다.
단순히 available하기 때문에 할당하는 것입니다. 정확히는 할당한다기 보다 할당한 '척' 해보는 것이죠.
오른쪽 그림에 safety algorithm을 적용하면 safe sequence가 없으므로 불안전상태로 판별됩니다.
결론적으로 P2가 R2를 요청한 것은 거부됩니다.
이것이 은행가 알고리즘으로 자원할당을 거부하는 과정입니다.
은행가 알고리즘(자원 요청 알고리즘)
문제)
P0이 B에게 요청하는 클레임이 2개라는 것입니다.
Max = 필요로 하는 클레임입니다.
Allocation - 할당된 자원입니다.
Need = Max - Allocation 값입니다.
프로세스를 끝내기 위한 자원의 수입니다.
A, B, C, D라는 자원들의 총 수는?
각각 안에 들어가 있는 원이 몇 개인지를 봐야 할 것 같습니다.
8597입니다.
할당된 것(7375)에 available(1222)을 더하면 됩니다.
available는 활용 가능한 자원입니다.
1222로 끝 넬 수 있는 프로세스가 있을까요? P2가 있습니다.
1102는 할당 가능합니다.
P2 종료 후 :
allocation 된 것을 모두 돌려받습니다.
1222 + 4003 = 5225
work(활용 가능한 자원) = 5225
P0, P4를 끝낼 수 있습니다.
P0를 먼저 끝내봅시다.
5225 + 2011 = 7236
현재 work와 P0에 할당돼있던 것을 더하면 됩니다.
은행가 알고리즘을 위한 자료구조
위 예시에서
m, n은 무엇일까요?
n:5(P0,1,2,3)
m:4(A, B, C, D)
Max [i, j]
- 프로세스 Pi의 최대로 요청하는 유형 j 자원 수.
Max [3,2]는? 프로세스 P3에서 최대로 요청하는 클레임의 수 = 3
A, B, C에서 C
Max [2,1]은? 1(B)
- 프로세스 Pi가 점유한 유형 j 자원 수
A [0,3]은? 1(D)
- 프로세스 Pi가 추가로 요청하는 유형 j 자원 수
N [3,1]은? 3(B)
이 식은 무슨 뜻일까요?
최대 필요량 = 할당된 자원 + 필요한 자원
i = 프로세스 수
j = 자원의 수
- 남은 유형 j 자원 수
- 남은 자원의 수 이기 때문에 프로세스가 필요하지 않습니다.
다른 값들은 "어떤 프로세스"라는 수식어가 앞에 붙습니다.
만약 자원 유형이 하나 하면(네모 박스가 하나라면)
위에 m은 1입니다.
m은 자원 유형의 수입니다.
'Computer Science > OS' 카테고리의 다른 글
| 교착 상태 회복, 기아상태,교착상태 정리, 프로세스 스케줄링 (0) | 2021.11.22 |
|---|---|
| 은행가 알고리즘 코드, 시간복잡도, 회복 알고리즘 (0) | 2021.11.16 |
| 교착상태 회피하는법 (0) | 2021.11.09 |
| 교착상태 자세히 보기 (0) | 2021.11.08 |
| 모니터 추가설명, 교착 상태와 기아 상태 (0) | 2021.11.02 |
