길리랩blog

Banker’s Algorithm으로 안전 상태를 유지하는 자원 할당

Banker’s Algorithm의 안전 상태 판정, 자원 요청 처리, 데이터 모델과 운영 시 제약을 실무 관점에서 정리한다.

2026-08-14 · 최초 발행 2024-04-29

요청을 승인하기 전에 완료 순서를 확인한다

Banker’s Algorithm은 한정된 자원을 다루는 운영체제와 분산 시스템에서 교착 상태를 피하기 위한 고전적인 자원 관리 방식이다. 각 프로세스가 최대 요구량(Max)을 미리 선언한다는 전제에서, 현재 할당이 안전 상태(safe state)를 유지하는지 매 요청마다 확인한다.

여기서 안전 상태란 모든 프로세스가 언젠가 최대 요구량까지 자원을 확보하고, 작업을 끝낸 뒤 자원을 반환할 수 있는 실행 순서가 존재하는 상태다. 따라서 요청을 받았다고 즉시 할당하지 않는다. 먼저 가상 할당을 수행하고 안전성 검사를 통과한 경우에만 실제 할당을 확정한다.

자원 상태를 표현하는 데이터

판정에 필요한 상태는 다음 네 가지다.

  • Available[m]: 자원 타입별로 현재 남아 있는 수량
  • Max[n][m]: 프로세스별 최대 자원 요구량
  • Allocation[n][m]: 현재 프로세스에 할당된 수량
  • Need[n][m]: 아직 필요한 자원량이며 Max − Allocation으로 계산

Need는 안전성 판단의 기준이다. 각 자원 타입 k에서는 다음 일관성도 유지해야 한다.

sum(Allocation[·][k]) + Available[k] = Total[k]

음수나 총량을 넘는 값이 들어오지 않도록 입력을 검증해야 한다.

안전성 검사는 임시 가용량인 Work와 프로세스별 완료 가능 여부인 Finish를 사용한다. 아직 끝나지 않은 프로세스 중 Need[i] ≤ Work를 만족하는 프로세스를 찾으면, 해당 프로세스가 완료되었다고 가정하고 그 할당량을 Work에 돌려놓는다. 이 과정을 반복해 모든 Finish[i]가 true가 되면 안전 상태다. 그렇지 않으면 불안전 상태다.

안전성 검사 시간복잡도는 O(n^2·m) 수준이다. n은 프로세스 수, m은 자원 종류 수다. 이 방식은 모든 프로세스의 최대 요구량을 사전에 선언해야 하므로, 동적이거나 예측하기 어려운 워크로드에서는 제약이 생긴다.

요청은 가상 할당 뒤에 확정한다

프로세스 i가 Request[i]를 요청하면 먼저 두 조건을 확인한다.

  • Request[i] ≤ Need[i]를 만족하지 않으면 선언한 최대 요구량을 넘긴 요청이므로 오류를 반환한다.
  • Request[i] ≤ Available를 만족하지 않으면 자원이 돌아올 때까지 대기 큐에 넣거나 재시도한다.

두 조건을 통과하면 Available에서 요청량을 빼고, Allocation에는 더하며, Need에서는 뺀 상태를 가상으로 만든다. 이 상태에서 Safety Algorithm을 수행해 안전 순서가 존재하면 커밋한다. 실패하면 원래 상태로 롤백하고 대기 처리한다.

이 check-then-commit 구간은 전역 뮤텍스나 단일 스레드 처리로 원자성을 보장해야 한다. 타임아웃과 공정성(fairness) 정책도 함께 다루는 편이 좋다.

⤢✕NoYesNoYesYesNoRequest(i, R)R ≤ Need[i]?에러: 선언 초과 요청R ≤ Available?대기/큐잉가상 할당(Available−=R,Allocation+=R, Need−=R)안전성 검사(Safety)승인·커밋롤백 후 대기/재시도

최대 요구량을 모델링할 수 있는 곳

GPU와 메모리가 제한된 배치 스케줄러에서는 잡이 최대 GPU·메모리 요구량을 미리 선언하도록 하고, 제출 시 안전 순서를 보장하는지 검사할 수 있다. 이 방식으로 같은 시점에 과도한 할당이 이뤄지는 것을 막는다.

데이터 파이프라인에서는 ETL 단계별 동시 실행 슬롯과 I/O 대역을 자원 타입으로 모델링할 수 있다. 작업이 최대 동시점 요구량을 선언하면, 시스템은 안전 상태를 유지하는 범위에서 실행을 허용한다.

멀티테넌트 커넥션 풀도 같은 방식으로 볼 수 있다. 서비스나 테넌트별 최대 커넥션 상한을 선언하고, 순간 피크 요청은 가상 할당과 안전성 검사를 거쳐 승인하거나 대기열에서 스로틀링한다.

교착 처리 전략의 선택 기준

전략 성능 확장성 일관성 안정성 운영 편의
교착 예방(Prevention) 낮음~중간: 제약 강함 높음 매우 높음 매우 높음 중간: 정책 설계 필요
교착 회피(Banker's) 중간: 안전성 검사 오버헤드 중간: n·m 증가 시 비용 상승 높음: 안전 상태 보장 매우 높음: 모델 만족 시 교착 0% 낮음~중간: Max 선언·모델링 필요
교착 검출·복구 높음: 평시 오버헤드 낮음 높음 중간: 롤백 발생 가능 중간: 일시적 교착 허용 중간: 모니터링·복구 로직 필요
쿼터/백프레셔 혼합 높음: 경량 높음 중간: 근사적 보장 중간~높음: 튜닝 의존 높음: 운영 단순

안전 순서를 확인하는 예제

다음 상태에서 가용 자원은 Available = [3, 3, 2]다.

  • Max
    • P0: [7, 5, 3], P1: [3, 2, 2], P2: [9, 0, 2], P3: [2, 2, 2], P4: [4, 3, 3]
  • Allocation
    • P0: [0, 1, 0], P1: [2, 0, 0], P2: [3, 0, 2], P3: [2, 1, 1], P4: [0, 0, 2]
  • Need = Max − Allocation
    • P0: [7, 4, 3], P1: [1, 2, 2], P2: [6, 0, 0], P3: [0, 1, 1], P4: [4, 3, 1]

이 상태에는 ⟨P1, P3, P4, P0, P2⟩라는 안전 순서가 존재한다.

환경은 Python 3.9+이며 외부 라이브러리가 필요 없다.

from typing import List, Optional, Tuple

def leq(a: List[int], b: List[int]) -> bool:
    return all(x <= y for x, y in zip(a, b))

def add(a: List[int], b: List[int]) -> List[int]:
    return [x + y for x, y in zip(a, b)]

def sub(a: List[int], b: List[int]) -> List[int]:
    return [x - y for x, y in zip(a, b)]

def safety_sequence(available: List[int],
                    maxm: List[List[int]],
                    alloc: List[List[int]]) -> Optional[List[int]]:
    n, m = len(alloc), len(available)
    need = [[maxm[i][j] - alloc[i][j] for j in range(m)] for i in range(n)]
    work = available[:]
    finish = [False] * n
    seq = []
    changed = True
    while changed:
        changed = False
        for i in range(n):
            if not finish[i] and leq(need[i], work):
                work = add(work, alloc[i])
                finish[i] = True
                seq.append(i)
                changed = True
    return seq if all(finish) else None

def request_resources(i: int,
                      req: List[int],
                      available: List[int],
                      maxm: List[List[int]],
                      alloc: List[List[int]]) -> Tuple[bool, Optional[List[int]]]:
    n, m = len(alloc), len(available)
    need = [[maxm[p][j] - alloc[p][j] for j in range(m)] for p in range(n)]
    # Rule 1: Request <= Need
    if not leq(req, need[i]):
        return False, None
    # Rule 2: Request <= Available
    if not leq(req, available):
        return False, None
    # Pretend allocation
    available2 = sub(available, req)
    alloc2 = [row[:] for row in alloc]
    alloc2[i] = add(alloc2[i], req)
    seq = safety_sequence(available2, maxm, alloc2)
    if seq is None:
        return False, None
    # Commit allowed
    return True, seq

if __name__ == "__main__":
    available = [3, 3, 2]
    maxm = [
        [7,5,3],
        [3,2,2],
        [9,0,2],
        [2,2,2],
        [4,3,3]
    ]
    alloc = [
        [0,1,0],
        [2,0,0],
        [3,0,2],
        [2,1,1],
        [0,0,2]
    ]
    seq = safety_sequence(available, maxm, alloc)
    print("Safe sequence:", seq)  # 예: [1, 3, 4, 0, 2]

운영 시에는 음수·초과 할당을 막고 Total 불변식을 유지해야 한다. 동시 요청이 있을 때는 단일 전역 락으로 check-and-commit을 보호하거나 트랜잭션을 사용한다. 장기 대기를 막기 위해 대기열에 우선순위나 노후화(aging)를 적용할 수 있다.

최대 요구량이 정확하고 불변이며 알고리즘을 준수한다는 가정에서는 교착률 0%를 보장한다. 검출·복구 방식과 비교하면 롤백·재시도 횟수를 줄일 수 있고, 안전 순서를 기반으로 완료 가능성 100%를 보장한다. 리소스 고갈 구간에서 시스템 전체가 중단되는 일을 막아 운영 안정성을 높이며, 큐잉과 승인 정책으로 지연의 상한을 제어해 SLO 준수를 돕는다. 최대 요구량 선언은 용량 계획과 비용 예측을 더 정교하게 만드는 기반이 된다.

자원 모델이 명확하고 상한을 선언할 수 있는 워크로드에서는 이 방식이 높은 안정성과 예측 가능성을 제공한다. 반대로 대규모이거나 동적인 환경에서는 안전성 검사 오버헤드와 모델링 제약을 고려해야 하며, 쿼터·백프레셔·우선순위 스케줄링을 함께 설계하는 선택지가 있다.

운영체제교착 상태자원 할당Banker's Algorithm스케줄링