은행가 알고리즘

왜 배우는가: 교착상태는 여러 프로세스가 자원을 점유한 채 서로를 기다릴 때 시스템 전체가 멈추는 현상이다. 운영체제 설계와 동시성 문제에서 반드시 다뤄지며, 교착상태를 사전에 막는 대표 기법인 은행가 알고리즘은 기술사 시험에서 정의, 자료구조, 안전성 검사 절차를 묻는 문제로 반복해 출제된다.

출제 이력: 제138회 1교시 11번, 제124회 3교시 4번, 제101회 3교시 3번

1. 한 줄 정의와 핵심 키워드

답안 첫 줄 정의: 은행가 알고리즘은 프로세스의 최대 자원 요구를 미리 선언받아 자원 할당 전에 안전 상태를 검사함으로써 교착상태를 회피하는 알고리즘이다.

핵심 키워드

• 교착상태 회피: 자원 할당 전에 교착상태가 생기지 않는다는 것을 확인하는 방식
• 안전 상태(Safe State): 모든 프로세스가 교착 없이 끝까지 실행될 수 있는 상태
• 안전 순서열(Safe Sequence): 프로세스가 실행되어 자원을 반납하는 순서
• 최대 요구량(Max): 프로세스가 일생 동안 요구할 수 있는 자원의 최대량
• 할당량(Allocation): 프로세스가 현재 보유한 자원의 양
• 필요량(Need): Max에서 Allocation을 뺀 추가로 필요한 자원의 양
• 가용 자원(Available): 시스템에 현재 남아 있는 자원의 양

2. 개념 풀이

쉬운 말로 풀면, 은행이 대출을 내주기 전에 모든 고객이 상환을 마칠 수 있는지 따져 보는 것과 같다. 운영체제도 자원을 주기 전에 모든 프로세스가 끝까지 실행될 수 있는지 가상으로 계산해 본다. 계산 결과 안전하면 자원을 주고, 위험하면 요청을 보류한다.

정식 정의는 다음과 같다. 다중프로그래밍 환경에서 프로세스 n개와 자원 m종류가 있을 때, 자원 요청마다 요청 후의 상태가 안전 상태인지 검사한다. 안전 상태이면 할당하고 불안전 상태이면 요청을 거부하거나 연기한다. 이 방식으로 순환대기가 생기지 않도록 사전에 막는다.

핵심 용어는 다음과 같이 풀이한다.

• 안전 상태: 어떤 순서로든 모든 프로세스가 자원을 받아 실행을 마치고 반납할 수 있는 상태다. 안전 순서열이 하나라도 존재하면 안전 상태다.
• 불안전 상태: 안전 순서열이 존재하지 않는 상태다. 불안전 상태가 곧 교착상태라는 뜻은 아니다. 다만 교착상태로 갈 가능성이 있으므로 할당을 막는다.
• Max: 프로세스가 선언하는 자원 최대 요구량이다. 실제 요청은 이 값을 넘을 수 없다.
• Allocation과 Need: Allocation은 현재 보유량이고 Need는 Max에서 Allocation을 뺀 값이다. 식으로 쓰면 $Need_{ij} = Max_{ij} - Allocation_{ij}$ 이며, i는 프로세스 번호, j는 자원 종류다.
• Available: 전체 자원에서 모든 Allocation을 뺀 남은 양이다. 식으로 쓰면 $Available_j = Total_j - \sum_{i} Allocation_{ij}$ 이다.

안전성 검사는 다음 순서로 진행한다. 아직 실행되지 않은 프로세스 중 Need가 Available 이하인 것을 고른다. 그 프로세스가 끝나면 보유 자원을 모두 반납하므로 Available에 더한다. 이 과정을 모든 프로세스에 대해 반복하여 모두 끝나면 안전 상태다. 요청 검사 시에도 요청량이 Need 이하이고 Available 이하여야 한다.

3. 등장 배경과 필요성

다중프로그래밍 환경에서는 여러 프로세스가 같은 자원을 나누어 쓴다. 이때 프로세스가 자원을 쥔 채 다른 자원을 기다리면 교착상태가 생길 수 있다. E. G. Coffman은 1971년 교착상태가 생기는 네 가지 필요조건을 제시했다. 상호 배제, 점유와 대기, 비선점, 순환 대기가 그것이다. 네 조건이 동시에 성립해야 교착상태가 생긴다.

이 네 조건 중 하나를 막는 것을 교착상태 예방이라고 한다. 예방은 확실하지만 자원 사용 효율을 떨어뜨릴 수 있다. 예를 들어 자원을 한꺼번에 모두 요청하게 하면 대기 시간이 길어진다. 탐지 후 회복 방식은 교착상태가 생긴 뒤에 프로세스를 종료하거나 자원을 빼앗아야 하므로 비용이 크다. 특히 한 번에 여러 프로세스를 중단하면 그동안의 계산 결과가 모두 사라진다.