교착상태 회피 알고리즘 (은행가 알고리즘)

교착상태(Deadlock) 회피 알고리즘은 멀티스레드 및 멀티프로세서 환경에서 발생할 수 있는 교착상태를 예방하는 중요한 기술입니다. 특히, "은행가 알고리즘(Banker’s Algorithm)"은 자원을 할당할 때 교착상태를 방지하기 위한 방법으로, 안전한 상태에서만 자원을 할당하는 방식으로 동작합니다. 이번 글에서는 교착상태 회피 알고리즘의 개념과 은행가 알고리즘의 작동 원리, 장단점, 실제 응용 사례 등을 다루어보겠습니다.

1. 교착상태(Deadlock)란?

교착상태란 두 개 이상의 프로세스가 서로 자원을 기다리며 무한 대기 상태에 빠지는 현상을 말합니다. 교착상태가 발생하면 시스템의 성능이 저하되거나 시스템이 멈추는 문제가 발생할 수 있습니다. 교착상태의 발생 조건은 다음과 같습니다:

• 상호 배제(Mutual Exclusion): 자원은 한 번에 하나의 프로세스만 사용할 수 있다.
• 점유 및 대기(Hold and Wait): 이미 일부 자원을 점유한 프로세스가 추가 자원을 요청하며 대기한다.
• 비선점(Non-preemption): 자원이 할당되면 강제로 회수할 수 없다.
• 원형 대기(Circular Wait): 여러 프로세스가 원형으로 자원을 기다린다.

교착상태를 회피하는 알고리즘은 "안전한 상태(Safe State)"에서만 자원을 할당하여 교착상태를 방지합니다.

2. 은행가 알고리즘 (Banker’s Algorithm)

은행가 알고리즘은 자원의 할당을 할 때 시스템이 교착상태에 빠지지 않도록 하는 교착상태 회피 알고리즘입니다. 이 알고리즘은 안전한 상태에서만 자원을 할당하여, 시스템이 교착상태에 빠질 가능성을 사전에 차단합니다. 이 알고리즘의 동작 방식은 마치 은행에서 고객이 대출을 요청할 때, 은행이 고객에게 대출할 수 있는지 미리 판단하는 방식과 유사합니다.

 

2.1 작동 원리

 

은행가 알고리즘은 "안전한 상태(Safe State)"와 "위험한 상태(Unsafe State)"를 구분하고, 시스템이 자원을 요청할 때마다 안전성을 체크합니다. 안전한 상태란, 시스템이 자원을 할당한 후에도 결국 모든 프로세스가 자원을 완료하고 종료할 수 있는 상태입니다.

• 자원 요청: 프로세스가 자원을 요청하면, 시스템은 먼저 요청된 자원을 할당해도 안전한지 검사합니다.

• 안전성 검사: 시스템은 각 프로세스가 자원을 요청했을 때, 모든 프로세스가 자원을 완료할 수 있는지 확인합니다.

• 자원을 할당한 후, 프로세스가 종료되었을 때 반환된 자원을 다른 프로세스가 사용할 수 있게 됩니다.

• 시스템이 자원을 할당하여도, 자원을 다 사용하고 종료할 수 있는 순서가 존재하면 안전한 상태로 간주합니다.

• 할당: 만약 요청이 안전하다면 자원을 할당하고, 그렇지 않으면 요청을 대기시킵니다.

 

2.2 은행가 알고리즘의 주요 요소

• 자원의 총량: 시스템에서 사용 가능한 총 자원의 수입니다.
• 각 프로세스의 최대 요구량: 각 프로세스가 필요로 하는 최대 자원의 수입니다.
• 각 프로세스의 할당된 자원: 현재 각 프로세스에 할당된 자원의 수입니다.
• 각 프로세스의 남은 자원 요청: 각 프로세스가 아직 요청하지 않은 자원의 수입니다.

 

2.3 안전성 검사 알고리즘

• 1단계: 각 프로세스의 남은 자원 요청이 현재 시스템에서 제공할 수 있는 자원보다 적거나 같으면 해당 프로세스를 완료시킵니다.
• 2단계: 완료된 프로세스의 자원을 반환받고, 이 자원을 다른 프로세스에게 할당할 수 있도록 합니다.
• 3단계: 모든 프로세스가 완료되면, 시스템은 안전한 상태입니다. 그렇지 않으면, 자원을 할당하지 않고 요청을 대기시킵니다.

3. 장점과 단점

3.1 장점

• 교착상태 회피: 은행가 알고리즘은 교착상태가 발생하지 않도록 자원을 할당하기 전에 안전성을 검사합니다.
• 효율성: 은행가 알고리즘은 자원의 상태를 동적으로 관리하며, 교착상태를 사전에 방지하는데 효과적입니다.
• 확장성: 시스템에 자원과 프로세스가 추가되어도 알고리즘을 적용할 수 있습니다.

3.2 단점

• 과도한 자원 요구: 은행가 알고리즘은 모든 프로세스가 자원의 최대 요구량을 정확히 알아야 하며, 이를 미리 선언해야 하므로 현실적인 시스템에서는 적용이 어려운 경우가 많습니다.
• 성능 문제: 자원을 할당할 때마다 안전성 검사를 수행해야 하므로, 시스템 부하가 커질 수 있습니다.
• 비효율성: 자원 할당이 보수적으로 이루어져, 자원의 활용도가 낮을 수 있습니다.

4. 응용 사례

항공기 제어 시스템

 

항공기 제어 시스템에서는 여러 프로세스(예: 비행기 엔진 제어, 항로 관리, 날씨 정보 수집 등)가 동시에 실행됩니다. 이 시스템에서는 은행가 알고리즘을 사용하여 교착상태를 방지하고, 자원의 할당을 안전하게 관리합니다. 예를 들어, 엔진 제어와 항로 관리 프로세스가 자원을 동시에 요청할 경우, 시스템은 은행가 알고리즘을 사용해 안전성을 확인하고 자원을 할당합니다.

 

실시간 데이터베이스 시스템

 

실시간 데이터베이스 시스템에서 여러 사용자들이 동시에 데이터베이스에 접근할 때, 은행가 알고리즘을 사용하여 교착상태를 방지하고 데이터의 일관성을 유지할 수 있습니다. 이 시스템은 각 사용자에 대한 요청을 확인하고, 자원을 할당하는 순서를 미리 결정하여 교착상태를 방지합니다.

은행 시스템

 

은행 시스템에서는 여러 고객이 동시에 대출을 요청할 때, 은행가 알고리즘을 사용하여 교착상태를 방지합니다. 예를 들어, 각 고객은 대출 가능한 금액의 최대 한도를 알고 있으며, 은행은 고객이 요청하는 금액이 교착상태를 일으킬 가능성이 없을 때만 대출을 승인합니다.

 

멀티태스킹 운영체제

 

운영체제에서는 여러 프로세스가 동시에 자원을 요청할 때 은행가 알고리즘을 사용하여 교착상태를 예방합니다. 예를 들어, 파일 시스템이나 메모리 자원 등을 여러 프로세스가 동시에 요청할 때, 은행가 알고리즘은 프로세스가 자원을 안전하게 할당받을 수 있도록 도와줍니다.

---

1. 은행가 알고리즘 코드 예제

 

문제 설정

• 시스템에 3개의 자원 유형이 있고, 5개의 프로세스가 자원을 요청합니다.
• 각 프로세스의 최대 자원 요구량, 현재 할당된 자원, 남은 자원 요청이 주어집니다.
• 은행가 알고리즘을 사용하여 각 요청이 안전한지 확인하고 자원을 할당합니다.

 

코드 예시:

class BankersAlgorithm:
    def __init__(self, available, max_resources, allocated):
        self.available = available  # 시스템에서 현재 사용 가능한 자원
        self.max_resources = max_resources  # 각 프로세스의 최대 요구 자원
        self.allocated = allocated  # 각 프로세스가 이미 할당받은 자원
        self.need = self.calculate_need()  # 각 프로세스의 남은 자원 요청

    def calculate_need(self):
        need = []
        for i in range(len(self.max_resources)):
            need.append([self.max_resources[i][j] - self.allocated[i][j] for j in range(len(self.max_resources[i]))])
        return need

    def is_safe(self):
        work = self.available[:]  # 시스템에서 사용할 수 있는 자원의 현재 상태
        finish = [False] * len(self.max_resources)  # 각 프로세스의 완료 상태
        safe_sequence = []  # 안전한 실행 순서

        while len(safe_sequence) < len(self.max_resources):
            progress_made = False
            for i in range(len(self.max_resources)):
                if not finish[i] and all(self.need[i][j] <= work[j] for j in range(len(self.need[i]))):
                    # 프로세스를 실행할 수 있는 경우
                    safe_sequence.append(i)
                    finish[i] = True
                    for j in range(len(work)):
                        work[j] += self.allocated[i][j]
                    progress_made = True
                    break

            if not progress_made:  # 실행 가능한 프로세스가 없으면 교착 상태
                return False, []

        return True, safe_sequence  # 안전한 상태이면 실행 순서 반환

    def request_resources(self, process_id, request):
        if all(request[j] <= self.need[process_id][j] for j in range(len(request))):
            if all(request[j] <= self.available[j] for j in range(len(request))):
                # 자원 요청이 유효한 경우
                for j in range(len(request)):
                    self.available[j] -= request[j]
                    self.allocated[process_id][j] += request[j]
                    self.need[process_id][j] -= request[j]

                safe, safe_sequence = self.is_safe()
                if safe:
                    return True, safe_sequence
                else:
                    # 요청이 안전하지 않으면 롤백
                    for j in range(len(request)):
                        self.available[j] += request[j]
                        self.allocated[process_id][j] -= request[j]
                        self.need[process_id][j] += request[j]

        return False, []

# 시스템 상태 예시
available = [3, 3, 2]  # 시스템에서 사용할 수 있는 자원
max_resources = [
    [7, 5, 3],  # 프로세스 0의 최대 자원 요구
    [3, 2, 2],  # 프로세스 1의 최대 자원 요구
    [9, 0, 2],  # 프로세스 2의 최대 자원 요구
    [2, 2, 2],  # 프로세스 3의 최대 자원 요구
    [4, 3, 3],  # 프로세스 4의 최대 자원 요구
]
allocated = [
    [0, 1, 0],  # 프로세스 0의 할당된 자원
    [2, 0, 0],  # 프로세스 1의 할당된 자원
    [3, 0, 2],  # 프로세스 2의 할당된 자원
    [2, 1, 1],  # 프로세스 3의 할당된 자원
    [0, 0, 2],  # 프로세스 4의 할당된 자원
]

# 은행가 알고리즘 인스턴스 생성
banker = BankersAlgorithm(available, max_resources, allocated)

# 프로세스 1이 [1, 0, 2] 자원을 요청하는 예
process_id = 1
request = [1, 0, 2]

safe, safe_sequence = banker.request_resources(process_id, request)

if safe:
    print(f"요청된 자원을 할당한 후의 안전한 실행 순서: {safe_sequence}")
else:
    print("요청된 자원을 할당할 수 없습니다. 교착상태 발생 가능성 있음.")

설명:

1. 클래스와 메서드:

• BankersAlgorithm: 은행가 알고리즘을 구현하는 클래스입니다.
• is_safe: 자원을 할당하기 전에 시스템이 안전한 상태인지 확인합니다.
• request_resources: 프로세스가 자원을 요청하면, 시스템이 자원을 할당해도 안전한지 검사합니다.

2. 시스템 예시:

• available: 현재 사용 가능한 자원의 수를 나타냅니다.
• max_resources: 각 프로세스가 필요로 하는 최대 자원 수입니다.
• allocated: 각 프로세스에 이미 할당된 자원 수입니다.
• need: 각 프로세스가 더 필요한 자원 수입니다.

3. 요청 예시:

• 프로세스 1이 자원 요청 [1, 0, 2]을 하면, 은행가 알고리즘은 자원을 할당해도 시스템이 안전한지 확인하고, 안전하다면 자원을 할당합니다. 그렇지 않으면 요청을 거부합니다.

 

 

 

5. 결론

 

은행가 알고리즘은 교착상태를 회피할 수 있는 강력한 방법입니다. 자원 할당을 동적으로 관리하여 시스템이 안전한 상태를 유지하게 돕고, 교착상태를 방지하는 데 중요한 역할을 합니다. 그러나 이 알고리즘은 자원의 최대 요구량을 미리 예측해야 하고, 성능상 부하가 발생할 수 있다는 단점도 존재합니다. 따라서 교착상태 회피를 위한 알고리즘을 선택할 때는 시스템의 특성과 요구 사항을 고려해야 합니다.