교착상태(Deadlock)
교착상태의 정의
교착상태(Deadlock)는 두 개 이상의 프로세스가 서로 다른 자원을 기다리고 있을 때, 각 프로세스가 자신이 기다리는 자원을 영원히 얻을 수 없게 되어 시스템이 멈추는 상태를 말합니다. 즉, 모든 프로세스가 더 이상 진행되지 않고 대기 상태에 빠져 아무 것도 수행하지 않는 상황을 의미합니다.
교착상태의 필요조건
교착상태가 발생하려면 다음 네 가지 조건이 모두 충족되어야 합니다. 이 네 가지 조건을 교착 상태의 필요조건이라고 합니다.
1. 상호 배제(Mutual Exclusion):
• 자원은 한 번에 한 프로세스만 사용할 수 있습니다. 즉, 자원을 다른 프로세스가 사용할 수 없다는 조건입니다.
2. 점유와 대기(Hold and Wait):
• 자원을 이미 점유하고 있는 프로세스가 다른 자원을 기다리며 대기하는 상태입니다. 예를 들어, 프로세스 A가 자원 X를 사용 중일 때 자원 Y를 기다리고, 프로세스 B는 자원 Y를 사용 중이면서 자원 X를 기다리고 있는 상황입니다.
3. 비선점(Non-preemption):
• 자원은 점유한 프로세스가 자발적으로 반납하지 않으면, 다른 프로세스가 강제로 빼앗을 수 없습니다. 즉, 자원을 점유한 프로세스가 자원을 반환하기 전까지 다른 프로세스는 해당 자원을 사용할 수 없습니다.
4. 원형 대기(Circular Wait):
• 여러 프로세스가 서로 자원을 기다리면서 원을 형성하는 상태입니다. 예를 들어, 프로세스 A는 자원 X를 기다리고, 프로세스 B는 자원 Y를 기다리고, 프로세스 C는 자원 Z를 기다리며, 프로세스 A가 자원 Z를 기다리고 있는 형태로 원형이 형성됩니다.
이 네 가지 조건이 동시에 만족되면 교착상태가 발생할 수 있습니다.
교착상태 회피 방법: 뱅커 알고리즘(Banker’s Algorithm)
뱅커 알고리즘의 목적
뱅커 알고리즘(Banker’s Algorithm)은 교착상태를 예방하기 위한 알고리즘으로, 시스템의 자원이 부족하여 교착상태에 빠질 가능성이 있는 상황을 사전에 회피하기 위해 사용됩니다. 이 알고리즘은 프로세스가 자원을 요청할 때 이 요청이 교착상태를 유발할 가능성이 없는지 검사하고, 안전한 상태일 때만 자원을 할당하는 방식으로 동작합니다.
뱅커 알고리즘의 동작 원리
1. 안전 상태(Safe State)와 불안전 상태(Unsafe State)
• 안전 상태는 시스템의 현재 상태에서 자원 할당이 이루어져도, 모든 프로세스가 자원을 종료할 수 있는 순서가 존재하는 상태를 의미합니다.
• 불안전 상태는 모든 프로세스가 자원을 종료할 수 있는 순서를 찾을 수 없는 상태입니다. 즉, 자원의 할당이 순차적으로 이루어져 교착상태를 유발할 위험이 있는 상태입니다.
2. 프로세스의 자원 요청
• 각 프로세스는 최대 요구 자원(Maximum Need), 현재 보유 자원(Allocated Resources), 그리고 **남은 자원(Need)**을 정의합니다.
• Maximum Need: 프로세스가 실행을 끝내기 위해 필요로 하는 자원의 최대량
• Allocated Resources: 현재 프로세스가 이미 보유하고 있는 자원
• Need: 프로세스가 실행을 완료하기 위해 아직 요청해야 하는 자원량 (Need = Maximum Need - Allocated Resources)
3. 자원 요청 시 체크 과정
• 프로세스가 자원을 요청하면, 뱅커 알고리즘은 그 요청이 안전한 상태로 시스템에 반영할 수 있는지를 검토합니다.
• 시스템이 자원을 할당할 수 있는지 여부를 판단하기 위해, 가상적으로 자원을 할당한 후 모든 프로세스가 자원을 완료할 수 있는지를 체크합니다. 이 과정을 통해 안전한 상태일 경우에만 자원을 할당합니다.
4. 안전성 검증
• 시스템이 자원 요청을 승인하려면, 가상적인 할당 후 시스템이 안전한 상태로 돌아갈 수 있는지 검사합니다. 안전한 상태란, 모든 프로세스가 결국 자원을 할당받고 종료할 수 있는 상태입니다.
• 자원이 할당된 후, 시스템에 남은 자원과 각 프로세스의 요구 자원을 비교하여 할 수 있는 프로세스들을 찾아 자원을 할당하고, 이를 반복합니다. 이 과정에서 모든 프로세스가 끝날 수 있으면 안전한 상태로 간주하고, 자원을 할당합니다.뱅커 알고리즘 절차
1. 자원 요청을 받으면, 요청이 최대 자원 요구를 초과하지 않음을 확인합니다.
2. 요청한 자원이 시스템에 현재 남아 있는 자원 내에서 충족 가능한지 확인합니다.
3. 요청을 승인하기 전에, 가상적으로 자원을 할당하여 안전성 검사를 수행합니다.
4. 시스템이 안전한 상태로 유지될 수 있다면 요청을 승인하고, 그렇지 않으면 거부합니다.뱅커 알고리즘 예시
가정:
• 시스템에 총 10개의 자원이 있고, 각 프로세스가 최대 4개의 자원을 요청할 수 있습니다.
• 각 프로세스가 보유한 자원과 요구하는 자원량은 다음과 같습니다:
프로세스 보유 자원(Allocated) 최대 자원(Maximum) 남은 자원(Need)
P1 3 4 1
P2 2 3 1
P3 2 3 1
• 만약 P1이 자원 1개를 요청하면, 뱅커 알고리즘은 이 요청이 승인될 수 있는지 안전성 검사를 합니다.
• 자원을 할당한 후, 가상적으로 시스템을 시뮬레이션하여 모든 프로세스가 종료될 수 있는지 확인합니다.장점과 단점
• 장점: 뱅커 알고리즘은 교착상태를 사전 예방할 수 있으며, 시스템이 안전한 상태에서만 자원을 할당하므로 교착상태를 피할 수 있습니다.
• 단점: 알고리즘은 자원 할당 전에 모든 최대 요구 자원을 미리 알아야 하므로 과도한 자원 정보가 필요하고, 실시간 시스템에서는 비효율적일 수 있습니다. 또한 복잡성이 높고, 실행 시간에 비용이 많이 들 수 있습니다.요약
교착상태는 시스템에서 프로세스가 서로 자원을 기다리며 영원히 멈추는 상황을 의미하며, 이를 방지하기 위해 뱅커 알고리즘은 자원 할당 시 안전한 상태인지 검사하여 교착상태를 회피합니다. 뱅커 알고리즘은 최대 자원 요구량과 현재 보유 자원을 기준으로 요청을 검토하여 교착상태를 예방하는 유용한 방법이지만, 복잡성과 과도한 자원 정보 요구 등의 단점이 있습니다.
