교착상태
=> 2개 이상의 작업이 동시에 이루어지는 경우, 다른 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태이다. 여러 프로세스가 작업을 진행하다 보니 발생하는 자연적인 현상이다.
아사현상
=>잘못된 정책으로 특정 프로세스의 작업이 지연되는 문제
=>교착상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다. 또한 잠금을 사용할 때도 발생한다. 임계구역 문제를 해결하기 위해서 잠금을 구현한 코드로 무한 대기를 막지 못해 교착상태가 발생한다. 데이터베이스는 데이터의 일관성을 유지하기 위해 잠금을 사용하는데 이때 교착 상태가 발생할 수 있다.
자원할당 그래프
=> 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것이다.
다중 지원
=> 여러 프로세스가 동시에 사용하는 자원
교착상태 발생 조건
- 자원을 서로 공유하지 못한다.
- 자원을 빼앗을 수 없으며 자원을 놓을 때까지 기다려야 하므로 교착상태가 발생한다.
- 자원 하나를 잡은 상태에서 다른 자원을 기다리면 교착 상태가 발생한다.
- 자원을 요구하는 방향이 원을 이루며 양보를 하지 않기 때문에 교착상태가 발생한다.
교착상태 필요조건
=>상호 배제, 비선점, 점유와 대기, 원형대기 4가지의 조건을 동시에 모두 만족해야 한다.
- 상호배제: 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없다. 교착상태는 배타적인 자원을 여러 프로세스가 사용하는 경우에 발생한다. 즉 배타적인 자원이여야 한다.
- 비선점: 한 프로세스가 사용중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이여야 한다. 자원을 빼앗을 수 있다는 것은 시간 간격을 두고 그 자원을 공유할 수 있다는 의미이므로 상호 배제가 성립하지 않는다. 또한 교착상태는 비선점 자원을 사용할 때 발생한다.
->임계 구역을 보호하기 위해 잠금 장치를 사용하면 상호 배제와 비선점 조건이 보장되기 때문에 교착 상태가 발생할 수 있다.
- 점유와 대기: 프로세스가 어떤 자원을 할당 받은 상태에서 다른 자원을 기다리는 상태여야 한다. 한 프로세스가 자원을 점유한 상태에서 다른 프로세스의 자원을 기다리면 서로 진행을 방해하기 때문에 교착 상태가 발생한다.
- 원형대기: 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다. 점유와 대기를 하는 프로세스들이 서로 방해하는 방향이 원을 이루면 프로세스들이 서로 양보를 하지 않기 때문에 교착상태에 빠진다.
아사 현상은 에이징으로 해결할 수 있으며, 교착상태는 정책상 잘못이나 오류가 없어도 자연적으로 발생한다.
교착상태 해결방법
=> 예방, 회피, 검출/회복 이 있다.
- 예방: 교착 상태를 유발하는 4가지 조건이 발생하지 않도록 무력화하는 방법이다.
- 상호 배제 예방: 시스템 내의 모든 자원을 공유할 수 있다면 교착상태가 발생하지 않는다 하지만 상호배제를 무력화하기는 사실상 어렵다.
- 비선점 예방: 모든 자원을 빼앗을 수 없게 만드는 방식이다. 임계구역을 보호하기 위해 잠금을 사용하면, 빼앗을 수 없을 뿐만 아니라 상호 배제 예방도 보장할 수 없다. 사실상 시스템의 모든 자원을 빼앗기는 어렵다.
- 점유와 대기 예방: 전부 할당하거나 아예 할당하지 않는 방식을 적용한다. 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다. 프로세스는 작업 초기에 자신이 사용하는 모든 자원을 한꺼번에 점유하거나, 그러지 못할 경우 자원을 모두 반납해야 한다. 점유야 대기 예방은 자원이 아닌 프로세스의 자원 사용 방식을 바꿔 교착 상태를 처리한다는 점에서 의미가 있다.
점유와 대기 예방의 단점
- 프로세스가 자신이 사용하는 모든 자원을 알기 어렵다는 점: 추가로 필요한 자원이 생기면 이를 다시 확보하기가 어렵다.
- 자원의 활용성이 떨어진다: 앞으로 사용할 자원까지 선정해버리기 때문에 당장 사용하지도 않을 자원을 선점하므로 자원 낭비가 심하다.
- 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다: 자원을 많이 사용하는 프로세스는 적게 사용하는 프로세스보다 자원을 동시에 확보하기 어렵다.
- 결국 일괄 작업 방식으로 동작한다: 점유야 대기 예방을 실제 구현한다면 거의 모든 프로세스가 일괄 작업 방식으로 처리된다. => 즉 모든 작업이 일괄 작업 방식으로 처리되어 시스템 효율이 떨어진다.
원형 대기 예방
=> 점유와 대기를 하는 프로세스들이 원형을 이루지 못하게 막는 방법이다. 자원을 한 방향으로만 사용하도록 설정하면 원형 대기를 예방할 수 있다. 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당한다.
원형 대기 예방의 단점
- 프로세스 작업 진행에 유연성이 떨어진다
- 자원에 번호를 어떻게 부여할지 문제이다: 자원에 번호를 붙일 때 신중해야 한다. 자원에 어떻게 번호를 붙이든 자원 사용에 제약이 따른다.
=> 상호 배제 예방과 비선점 예방은 사용하기 어렵고, 점유와 대기 예방, 원형 대기 예방은 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 사용할 수 없다.
회피
=> 자원 할당량을 조절하여 교착 상태를 해결하는 방식이다. 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보는 것이다.
- 교착상태 회피의 개념: 교착상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어 주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어 주는 방식이다. 교착상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킨다.
- 할당되는 자원의 수를 조절하여 교착상태를 회피하며, 자원의 수를 기준으로 시스템을 안정상태, 불안정상태로 나누고 자원을 할당한다. 할당된 자원이 적으면 안정상태가 크고, 할당된 자원이 늘어나면 불안정 상태가 커진다.
--은행원 알고리즘이 대표적으로 회피를 사용하는 예제이다.
교착 상태 회피의 문제점
- 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다: 교착 상태 회피 방식을 사용하려면 모든 프로세스가 자신이 사용할 자원을 미리 선언해야 한다. 만약 미리 선언한 자원이 정확하지 않으면 교착상태 회피에서도 교착상태가 발생할 수 있다.
- 시스템 전체 자원수가 고정적이여야 한다: 시스템 전체 자원수가 고정적이여야 하지만 시스템 자원 수는 늘 유동적이다.
- 자원이 낭비된다: 교착 상태 회피에서는 실제로 교착상태가 발생하지 않는데도 발생할 것이라고 예상하고 프로세스에 자원을 할당하는데 제약을 둔다.
검출, 회복
=> 자원 할당 그래프를 모니터링 하면서 교착 상태가 발생하는지 살펴보는 방식이다. 교착 상태가 발생하면 교착 상태 회피 단계가 진행된다.
- 타임아웃을 이용한 교착상태 검출은 일정 시간동안 작업이 진행되지 않은 프로세스를 교착상태가 발생한 것으로 간주하여 처리하는 방법이다. 타임아웃을 이용하는 방법은 가벼운 교착상태 검출이라고 하고, 자원 할당 그래프를 이용하는 방법을 무거운 교착상태 검출이라고 한다.
타임 아웃을 이용한 교착상태 검출의 문제점
--엉뚱한 프로세스가 종료될 수 있다: 교착 상태 외의 다른 이유로 작업이 진행되지 못하는 모든 프로세스가 강제종료 될 수 있다.
- 모든 시스템에 적용할 수 없다. 시스템에서는 원격지에 있는 프로세스의 응답이 없는 것이 교착상태 때문인지, 네트워크 문제인지, 단순 처리가 늦어서인지 알 수 없다. 따라서 타임 아웃을 적용하여 교착 상태를 파악하기 어렵다.
- 가장 큰 문제점은 시스템에 따라 교착 상태가 발생하는 빈도나 시스템에 미치는 영향이 다르다는 것이다.
- 데이터베이스는 특히 일관성이 깨지면 안 된다. 데이터를 조작할 때에는 반드시 잠금(lock)을 얻은 후 작업을 시작해야 한다. 타임아웃으로 프로세스가 종료되면 일부 데이터에 문제가 생길 수도 있다.
- 데이터베이스에서는 체크포인트와 롤백을 사용한다. 체크포인트를 설정하면 현재의 시스템 상태가 하드디스크에 저장되며 이러한 데이터를 스냅숏이라고 한다. 롤백은 작업을 하다가 문제가 발생하여 과거의 체크포인트로 돌아가는 것이다. 데이터베이스에서 가장 중요한 데이터에 잠금을 요청하면 체크포인트를 만들고, 해당 시점의 스냅숏을 저장한다.
자원 할당 그래프를 이용한 교착 상태 검출
=> 자원 할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지 혹은 기다리고 있는지를 알 수 있다. 그래프를 그렸을 때 겹치는 점 없이 한 붓 그리기가 성공이면 교착상태가 없는 것이다.
- 단일 자원을 사용하는 경우 자원 할당 그래프에 사이클이 있으면 교착 상태이다.
- 자원 할당 그래프를 이용하여 교착 상태를 검출하는 방법은 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 파악할 수 있다는 것이 장점이다.
-단점: 자원 할당 그래프를 유지하고 갱신하고 사이클을 검사하는 추가 작업으로 오버헤드가 발생한다는 단점이 있다.
교착상태 회복
=>교착 상태가 검출되면 이를 푸는 후속작업을 하는 것을 교착 상태 회복이라고 한다.
프로세스를 강제로 종료하는 방법
- 교착 상태를 일으킨 모든 프로세스를 동시에 종료한다: 어떤 프로세스를 먼저 실행할 것인지 기준을 정해야 한다.
- 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료한다. (다음과 같은 기준을 따름)
-- 우선순위가 낮은 프로세스를 먼저 종료한다.
-- 우선순위가 같으면 시간이 짧은 프로세스를 먼저 종료한다.
-- 위의 두 조건이 같으면 자원을 많이 사용하는 프로세스를 먼저 종료한다.
교착 상태 회복 단계에서는 관련 프로세스를 강제로 종료하는 일 뿐만 아니라 강제로 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일을 해야 한다. 시스템 복구는 명령어가 실행될 때마다 체크포인트를 만들어 가장 최근의 검사 시점으로 돌아가는 식으로 한다. 하지만 이 방법은 작업량이 상당하여 시스템에 부화를 주므로 체크포인트를 무분별하게 사용하지 말고 선택적으로 사용해야 한다.