교착 상태 해결 방법
1. 교착 상태 해결 방법
해결 방법으로는 예방, 회피, 검출 회복 방법이 있습니다.
2. 교착 상태 예방
상호 배제와 비선점을 예방하긴 어렵고 점유와 대기, 원형 대기는 프로세스의 작업 방식을 제한하고 자원 낭비가 있어 사용하기 어렵습니다.
2.1 상호 배제 예방
시스템 내에 있는 독점적으로만 사용 가능한 자원을 없애버리는 방법입니다. 만약 모든 자원을 공유할 수 있다면 교착 상태가 발생하지 않습니다. 그러나 현실적으로 모든 자원을 공유할 수 없으며 상호 배제로 보호해야 하는 자원이 있습니다. 따라서 상호 배제를 무력화하는 것은 어렵다고 볼 수 있습니다.
2.2 비선점 예방
모든 자원을 빼앗을 수 있도록 만드는 방법입니다. 하지만 임계구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없을 뿐만 아니라 상호 배제도 보장할 수 없어집니다. 따라서 현실적으로 시스템의 모든 자원을 빼앗을 수 있도록 허용할 수 없습니다.
2.3 점유와 대기 예방
프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법입니다. 즉 전부 할당하거나 아예 할당하지 않는 방식(all or nothing)을 적용합니다. 프로세스는 시작 초기에 사용할 모든 자원을 한번에 점유하거나 아니면 자원을 모두 반납해야하는 방식입니다.
- 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움
실행하고 나서 추가로 필요한 자원에 대해서는 확보하기 어려움 - 자원의 활용성이 떨어짐
프로세스가 필요한 모든 자원을 미리 선점해두므로 당장 사용하지 않을 자원도 선점되어 자원 낭비가 심함 - 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리함
자원을 많이 사용하는 프로세스는 필요한 모든 자원을 확보하기 어려워 starvation이 발생함 - 결국엔 일괄 작업 방식으로 동작
키보드, 마우스 등 시스템 자원은 대부분 모든 프로세스에서 필요로 하는 자원인데 이러한 자원들을 확보한 순서대로 실행하면 그 자원을 획득한 프로세스가 작업을 끝내야 다른 프로세스가 작업을 할 수 있게 되어 효율이 떨어지게 됨
2.4 원형 대기 예방
점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법입니다. 자원을 한 방향으로만 사용하도록 설정함으로써 원형 대기를 예방할 수 있으며 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하도록 하면 됩니다.
- 프로세스 작업 진행에 유연성이 떨어짐
마우스 < 하드디스크 < 프린터 순이면 프린터를 사용한 다음 마우스를 할당받으려면 운영체제가 거부하게 됨 - 자원의 번호를 어떻게 부여할 것인지 문제
프로세스가 큰 번호의 자원을 사용한 후 작은 번호의 자원은 사용할 수 없게 되므로 자원에 번호를 붙이는 데에 신경을 써야 함
3. 교착 상태 회피
3.1 교착 상태 회피 개념
교착상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나눠주면 교착 상태가 발생하는지 파악해 그 수준 이하로 자원을 나눠주는 방법입니다. 교착상태가 발생하지 않는 범위 내에서만 자원을 할당하고 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킵니다.
자원의 총 개수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나눠 시스템이 안정 상태를 유지하도록 자원을 할당합니다. 할당된 자원이 적으면 안정 상태가 크고 할당된 자원이 커질수록 불안정 상태가 커지게 됩니다. 즉, 회피는 안정상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착 상태를 회피합니다.
3.2 Banker’s Algorithm
은행원 알고리즘은 은행이 대출해주는 방식, 대출 금액이 대출 가능한 범위 내(안정상태)이면 허용되지만 아니면 거부되는 것과 유사함에서 나왔습니다.
각 프로세스는 자신이 사용할 자원의 최대 개수를 운영체제에게 알립니다. 왜냐하면 운영체제가 자원을 할당할 때 시스템의 상태를 파악하는데 꼭 필요한 정보기 때문입니다.
은행원 알고리즘에서 사용하는 변수
- 전체 자원(Total): 시스템 내 전체 자원 수
- 가용 자원(Available): 시스템 내 현재 사용할 수 있는 자원 수, 전체 자원 - 모든 프로세스의 할당 자원
- 최대 자원(Max): 각 프로세스가 선언한 최대 자원 수
- 할당 자원(Allocation): 각 프로세스에 현재 할당된 자원 수
- 기대 자원(Expect): 각 프로세스가 앞으로 사용할 자원의 수, 최대 자원 - 할당 자원
자원을 할당할 때의 기준
- 각 프로세스의 기대 자원과 비교해 가용 자원이 하나라도 크거나 같으면 자원을 할당하고 이것은 자원을 사용해 끝낼 수 있는 프로세스가 있으므로 안정 상태입니다.
- 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않습니다. 가용 자원을 사용해 작업을 마칠 수 있는 프로세스가 없으므로 불안정 상태입니다.
안정 상태의 예
Total = 14, Available = 2
| Process | Max | Allocation | Expect |
|---|---|---|---|
| P1 | 5 | 2 | 3 |
| P2 | 6 | 4 | 2 |
| P3 | 10 | 6 | 4 |
현재 가용한 자원은 2개이고 P2 기대 자원이 2개이므로 안정상태입니다. 기대자원까지 할당받고 실행을 종료하면 6개를 반환하고 P1이나 P3에 할당해 전체 작업을 완료할 수 있습니다.
불안정 상태의 예
Total = 14, Available = 1
| Process | Max | Allocation | Expect |
|---|---|---|---|
| P1 | 7 | 3 | 4 |
| P2 | 6 | 4 | 2 |
| P3 | 10 | 6 | 4 |
가용 자원이 1인데 어떠한 프로세스의 기대 자원에 충족되지 않으므로 불안정 상태입니다.
3.3 교착 상태 회피의 문제점
- 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 함
프로세스가 미리 선언한 자원이 정확하지 않으면 교착 상태 회피에서도 교착 상태가 발생할 수 있음 - 시스템의 전체 자원 수가 고정적이여야 함
안정 상태인지 불안정 상태인지 파악하려면 시스템의 전체 자원의 수가 고정적이여야 하지만 현실은 일시적 고장이나 새로운 자원이 추가되는 일이 빈번하여 자원 수가 유동적임 - 자원의 낭비
모든 불안정 상태에서 교착 상태가 발생하지 않는데 자원을 할당하지 않는 것은 자원 낭비임
4. 교착 상태 검출
4.1 교착 상태 검출 개념
검출은 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방식입니다. 교착 상태가 발견되면 해결하기 위해서 회복 단계로 넘어가게 됩니다.
4.2 타임아웃
타임아웃을 이용한 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착상태가 발생한 것으로 간주해 처리하는 방법입니다.
- 엉뚱한 프로세스가 강제 종료될 수 있음
타임아웃 시간동안 작업이 진행되지 않은 모든 프로세스가 교착 상태때문에 작업이 이루어지지 않은 것이 아닌데, 타임아웃을 적용해버리면 다른 이유로 작업이 진행되지 못하는 모든 프로세스가 강제 종료되는 문제가 있음 - 모든 시스템에 적용하기 어려움 하나의 운영체제 내에서는 가능하지만 분산 데이터베이스 시스템의 경우 타임아웃을 적용하기 어려움
4.3 자원 할당 그래프
자원 할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지, 기다리고 있는지 알 수 있습니다. 단일 자원을 사용하는 경우 자원 할당 그래프에 사이클이 존재하면 교착상태가 발생한다고 말할 수 있지만 다중 자원일 경우 교착 상태가 아닐 수 있습니다.
자원 할당그래프를 이용해 교착 상태를 검출하는 방법은 프로세스의 작업 방식을 제한하지 않고 교착 상태를 정확히 판단할 수 있다는 장점이 있습니다. 하지만 그래프를 유지하고 갱신하고 사이클 검사까지 하는 작업으로 인하여 오버헤드가 발생한다는 단점이 있습니다. 이 문제를 해결하기 위해 자원이 할당될 때마다 사이클 검사하는 것이 아닌 일정 시간마다 주기적으로 확인하는 방법이 있습니다.
5. 교착 상태 회복
교착 상태가 검출되면 교착 상태를 푸는 후속 작업을 하는데 이것을 회복이라고 합니다. 회복 단계에서는 교착 상태를 유발한 프로세스를 강제로 종료시킵니다.
- 교착 상태를 일으킨 모든 프로세스를 동시에 종료
이 방법으로 종료될 경우, 프로세스들이 동시에 작업을 다시 시작하게 되면 교착 상태를 또 일으킬 가능성이 큽니다. 따라서 강제 종료 후 다시 실행될 때에 순차적으로 실행해야 하며 어떤 프로세스를 먼저 실행시킬지 기준이 필요합니다. - 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
해당 프로세스 중 하나를 골라 순차적으로 종료시키면서 나머지 프로세스의 상태를 파악하는 방법입니다. 프로세스를 종료할 때 어떤 프로세스부터 종료할 것인지 기준이 필요합니다.
- 우선순위가 낮은 프로세스를 먼저 종료
- 우선순위가 같으면 작업 시간이 짧은 프로세스 종료
- 이것도 같다면 자원을 많이 사용하는 프로세스 종료
회복 단계에서는 강제 종료 말고도 강제 종료된 프로세스가 실행되기전 시스템을 복구시키는 일도 해야합니다. 복구는 명령어가 실행될 때마다 체크포인트를 생성해 가장 최근의 검사 시점으로 돌아가는 식으로 합니다. 하지만 이 방식은 시스템에 큰 부하를 만들 수 있어서 무분별하게 사용하지 않도록 주의해야 합니다.
