0528 OS 수업노트 (ch7.2)

Ji·2021년 5월 28일

Banker’s Algorithm

다익스트라가 개발
Deadlock 회피의 대표적 알고리즘
교착상태에 빠질 가능성이 있는지 없는지 판단 -> 상태를 ‘안전 상태(safe state)’와 ‘불안전 상태(unsafe state)’로 나눔.
OS는 안전상태(safe state)를 유지할 수 있는 요구만 수락. 나머지 요구들은 안전상태를 만족할 때까지 계속 거절.
각 프로세스는 Need<=Work 일 때, 프로세스가 끝나면 자원을 해제하면서 Allcation 자원을 Work가 갖게됨. Work=Work+Allocation

(ex) 은행은 100원 갖고 있음. A,B,C는 각각 40,50,60원이 필요함. 빌리려는 돈이 충족되어야 일을 할 수 있고, 돈을 갚을 수 있는 상황.
-> 일단 25원씩 주기로함. 그러면 A,B,C는 각각 15,25,35원이 더 필요. 은행이 남은 돈은 25원

sol)
1. 15원이 필요한 A에게 15원을 빌려줌 -> A가 일을 해결, 갚을 때까지 기다렸다가 다른 고객에게 돈을 빌려주면 됨.
2. 25원이 필요한 B에게 25원을 빌려줌 -> B가 일을 해결, 갚을 때까지 기다리고 다른 고객에게 빌려줌
but) C에게는 35원이 필요하기 때문에 돈을 빌려줄 수 없음.
-> 돈을 빌려줄 수 있고, 다시 돌려받을 수 있는 상태 : safe state

A-B-C
B-A-C
B-C-A
순으로 모든 고객에게 돈을 빌려줄 수 있음. 이를 안전순서열이 존재한다고 함.

if) 60원이 필요한 고객3이 45원을 요구. -> 세 고객 중 아무도 해결해 줄 수 없는 상황 (unsafe state/ deadlock)

Banker's Algorithm의` 자료 구조

Available : 사용 가능한 자원 수를 표시하는 길이가 m인 벡터.

Available[j]=k: j번째 자원을 k개 사용할 수 있다는 의미.

Max : 각 프로세스 자원의 최대 요구량 표시 (n*m 행렬).

Max[i,j]=k : 프로세스 Pi는 자원 Rj를 최대 k개까지 요청 가능

Allocation : 현재 각 프로세스에 할당된 각 형태의 자원 수 (현재할당량) 정의하는 n*m행렬.

Allocation[i,j]=k: 프로세스 Pi는 자원 Rj를 k개 할당 받고 있음.

Need: 각 프로세스에 남아 있는 자원 요청(추가요구량) 표시

Need[i,j]=k: 프로세스 Pi는 자신의 작업을 종료하려고 Rj를 k개 더 필요로 함.

banker's algorithm 예시 풀이

Need(i)=Maximum(i)-Allocated(i) 계산.
P1: Need[1]=(7,4,3)
P2: Need[2]=(1,2,2)
P3: Need[3]=(5,0,3)
P4: Need[4]=(0,1,1)

Work, Finish 초기화.
Work의 초기값은 Available 값과 같고, Finish의 길이는 process의 수, false로 초기화.
Work=(3,3,2)
Finish=(False,False,False,False)
각 프로세스 별로 자원이 할당 가능한지 체크한다.
만족 조건은 Finish[i]=False & Need[i]<=Work 이어야 함.

(1) P1 : (7,4,3) <=(3,3,2) : 부등호가 성립하지 않음. P1에는 자원 할당 X
(2) P2: (1,1,2)<=(3,3,2) : 부등호가 성립. P2에 할당 가능. 근데 P4도 가능 (여러가지 순서로 safe state가 성립 가능)
(3) Work=Work+Allocation[i]=(3,3,2)+(2,0,0)= (5,3,2)/ Finishi[i]=True 로 수정.
이제 다시 P1 부터 확인..

-> P2-P4-P1-P3 순서로 safe state 조건이 성립한다.