Banker’s 알고리즘

개념
운영체제는 자원의 상태를 감시하고, 사용자 프로세스는 사전에 자신의 작업에서 필요한 자원의 수를 제시하는 교착상태 회피 알고리즘 운영체제는 안정상태를 유지할 수 있는 요구만을 수락하고 불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때까지 계속 거절하는 교착상태 회피 알고리즘

I.  Banker’s 알고리즘의 개요
    가.  Banker’s 알고리즘의 정의

  • 운영체제는 자원의 상태를 감시하고, 사용자 프로세스는 사전에 자신의 작업에서 필요한 자원의 수를 제시하는 교착상태 회피 알고리즘
  • 운영체제는 안정상태를 유지할 수 있는 요구만을 수락하고 불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때까지 계속 거절하는 교착상태 회피 알고리즘

  

 

  • 안전상태: 모든 프로세스가 교착상태를 발생시키지 않고 종료할 수 있도록 하는 자원 할당 순서가 존재하는 경우
  • 안전 상태 ≠ 교착 상태
  • 불안전 상태 = 또는 ≠ 교착상태

 

 

II.  Banker’s 알고리즘의 구조
    가.  Banker’s 알고리즘의 자료구조

자료구조

설명

수식

Available

사용 가능한 자원의 수

Available[j]=K

자원종류 Rj중 K개 사용가능

Max

프로세스 별 최대 자원의 요구

Max[i,j]=K

Pi는 자원종류 Rj중 최대 K개 요청

Allocation

현재 프로세스 별 할당되어 있는 자원 수

Allocation[i,j]=K

Pi는 현재 자원종류 Rj를 K개 할당받고 있음

Need

프로세스 별 남아있는 자원의 수

Need[i,j]=(Max-Allocation)

Pi는 자원종류 Rj를 K개 더 요구함

    나.  Banker’s 알고리즘의 사례

 

[조건] 최대 요구자원 수에 대한 정보가 있을 경우를 가정

 

(1) 현재 사용 가능한 리소스의 양을 구한다. (Available)

2) 추가 요구량을 구한다. (Request = Max – Allocation)

3) 추가 요구자원이 현재 여유자원보다 적은 프로세스(i)를 찾는다.

수행을 끝내기 위한 충분한 자원을 확보한 프로세스 검사

(Request(i) ← Available(i))

(4) 수행 가능한 프로세스가 점유한 자원을 여유 자원으로 바꿈

(끝내고 반환한 경우로 가정)한 후에 3번부터 반복

(Available = Available + Allocation)

 

 

III.  Banker’s 알고리즘의 문제점

  • 쉽게 구현할 수 있지만 추가비용이 큼
  • 은행원(Banker)에게 통신하는 메시지가 너무 많아 은행원(Banker)이 Bottleneck이 될 수 있음
  • 할당할 자원이 일정량 존재해야 함
  • 최대 자원 요구량을 미리 알아야 함
  • 프로세스 들은 유한한 시간 안에 자원을 반납해야 함

댓글
닉네임

yes

p2의 추가 요구 자원 4가 아니라 2 지 않아요?