교착 상태 처리 방법
교착 상태를 무시하고 진행하는 방법 (Deadlock Ignorance)
정의: 교착 상태가 시스템에서 발생하지 않을 것이라고 가정하고, 아무런 조치를 취하지 않는 방법입니다.
사용: 이 방법은 교착 상태가 매우 드물게 발생하는 시스템에서 사용됩니다. 교착 상태를 해결하기 위해 복잡한 알고리즘을 사용하는 것보다, 가끔 시스템을 재부팅하는 것이 더 효율적이라고 판단하는 경우입니다.
장점: 오버헤드가 거의 없습니다.
단점: 교착 상태가 실제로 발생할 경우 해결할 수 없다는 단점이 있습니다. UNIX 및 Windows를 포함한 대부분의 운영 체제가 이 방법을 사용합니다.
교착 상태 예방 (Deadlock Prevention)
정의: 교착 상태가 발생하기 위한 네 가지 필수 조건(상호 배제, 점유와 대기, 비선점, 순환 대기) 중 하나 이상을 제거하여 교착 상태를 원천적으로 방지하는 방법입니다.
각 조건 제거:
상호 배제: 이 조건은 특정 자원 유형에는 필수적이므로, 일반적으로 제거하기 어렵습니다. 예를 들어, 프린터는 한 번에 하나의 프로세스만 사용할 수 있어야 합니다.
점유와 대기: 스레드가 자원을 요청할 때 다른 어떤 자원도 소유하고 있지 않도록 보장합니다.
방법 1: 스레드가 필요한 모든 자원을 한꺼번에 요청하여 획득하거나, 아니면 아무것도 획득하지 못하도록 합니다.
방법 2: 스레드가 추가 자원을 요청하기 전에, 현재 점유하고 있는 모든 자원을 해제하도록 합니다.
비선점: 이미 할당된 자원을 강제로 빼앗을 수 있도록 허용합니다.
방법 1: 자원을 기다리는 스레드의 요청이 실패하면, 스레드는 자신이 소유한 모든 자원을 해제해야 합니다.
방법 2: 이미 자원을 가진 스레드가 새로운 자원을 요청하여 기다려야 할 경우, 현재 가진 모든 자원을 다른 스레드에게 선점당할 수 있습니다.
순환 대기: 자원 유형에 대한 전체 순서를 부여하여, 스레드가 정해진 순서대로만 자원을 요청하도록 강제합니다.
예시: 자원 A, B, C에 순서 1, 2, 3을 부여하면, 스레드는 B를 요청하기 전에 반드시 A를 먼저 요청해야 합니다.
교착 상태 회피 (Deadlock Avoidance)
정의: 시스템이 교착 상태가 발생할 가능성이 있는 할당은 피하는 방법입니다. 운영체제는 스레드에게 자원을 할당할 때마다, 이 할당이 시스템을 '안전 상태(safe state)'로 유지할지 검사합니다.
안전 상태: 교착 상태가 발생하지 않는 상태로, 모든 스레드에게 필요한 자원을 순서대로 할당할 수 있는 방법이 존재하는 상태를 의미합니다.
안전성 알고리즘:
자원 할당 그래프 알고리즘: 자원 유형당 인스턴스가 하나일 때 사용됩니다. 요청이 들어올 때, 임시로 할당을 해본 후 사이클이 발생하면 할당을 거부하고, 그렇지 않으면 허용합니다.
은행원 알고리즘(Banker's Algorithm): 자원 유형당 인스턴스가 여러 개일 때 사용됩니다. 이 알고리즘은 각 스레드의 최대 자원 요구량(maximum claim)을 미리 알고 있어야 합니다. 요청이 들어오면, 시스템은 가상의 할당을 수행하여 안전성 검사를 합니다.
교착 상태 탐지 및 회복 (Deadlock Detection and Recovery)
정의: 교착 상태를 예방하거나 회피하지 않고, 교착 상태가 발생했음을 주기적으로 탐지한 후 회복하는 방법입니다.
탐지 알고리즘: 시스템의 상태를 검사하여 교착 상태가 발생했는지 확인하는 알고리즘입니다. 이 알고리즘은 오버헤드가 발생합니다.
회복: 교착 상태가 탐지되면 다음 중 한 가지 방법으로 회복을 시도합니다.
프로세스 종료: 교착 상태에 있는 스레드 중 하나 이상을 종료하여 교착 상태를 해제합니다.
방법 1: 교착 상태에 있는 모든 스레드를 종료합니다.
방법 2: 교착 상태가 해소될 때까지 하나씩 스레드를 종료합니다.
자원 선점: 교착 상태에 있는 스레드로부터 자원을 선점하여 다른 스레드에게 할당합니다.
방법 1: 자원을 선점하여 다른 스레드에게 할당하고, 선점당한 스레드는 롤백(rollback)하여 처음부터 다시 시작합니다.
방법 2: 자원을 선점할 희생자(victim)를 선택할 때, 최소한의 비용으로 교착 상태를 해결할 수 있는 스레드를 선택합니다.
Last updated