Banker's ALG

  • 각 process가 앞으로 최대로 얼마나 resource를 요구할지 미리 알아야 한다.
Data Structure

OS는 다음 data를 관리한다.

Available = 지금 남은 resource Max = 각 process가 최대로 요구할 수 있는 resource Allocation = 각 process가 현재 들고 있는 resource Need = Max - Allocation

ALG — outline

When Pi requests resources:

  1. RESOURCE-REQUEST 실행
  2. 내부에서 SAFETY-CHECK 실행
  3. safe이면 grant
  4. unsafe이면 wait
SAFETY-CHECK

지금 state에서 모든 process를 끝낼 수 있는 safe sequence가 존재함?

  • Input:

    • Available
    • Allocation
    • Need

  • Init:

    • Work = Available
    • Finish[i] = false for all i

  • Loop:

    • Finish[i] == false 이고
    • Need[i] <= Work 인 process Pi를 찾기
    • 찾으면:
      • Work = Work + Allocation[i]
      • Finish[i] = true
      • Pi를 safe sequence에 추가
    • 못 찾으면:
      • loop 종료

  • Result:

    • 모든 Finish[i] == true 이면 safe
    • 하나라도 Finish[i] == false 이면 unsafe
RESOURCE-REQUEST

Pi의 request를 지금 grant해도 safe state가 유지됨?

Input:

  • Request[i]
  • Available
  • Allocation
  • Need
Step 1. Request[i] <= Need[i] 확인
  • false이면 error
  • 이유: Pi가 처음 말한 Max보다 더 많이 달라는 것이기 때문
Step 2. Request[i] <= Available 확인
  • false이면 Pi는 wait
  • 이유: 지금 줄 resource가 없기 때문
Step 3. 일단 grant한 척함
  • Available = Available - Request[i]
  • Allocation[i] = Allocation[i] + Request[i]
  • Need[i] = Need[i] - Request[i]
Step 4. SAFETY-CHECK 실행
Step 5. 결과 처리
  • safe이면 진짜 grant
  • unsafe이면 Step 3을 rollback하고 Pi는 wait