교착 상태의 개요
교착 상태의 정의
- 교착 상태: 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태.
- 교착 상태 vs 아사 상태: 아사 상태는 운영체제가 잘못된 정책을 사용하여 특정 프로세스 작업이 지연되는 문제고, 교착 상태는 여러 프로세스가 작업을 진행하다 자연적으로 발생하는 문제다.
- 교착 상태는 시스템 자원, 공유 변수(또는 파일), 응용 프로그램 등을 사용할 떄 발생할 수 있다.
자원 할당 그래프
자원 할당 그래프: 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지 방향성이 있는 그래프로 표현한 것이다.
- 프로세스는 원으로, 자원은 사각형으로 표현된다.
- 자원을 할당한 경우는 자원으로부터 프로세스로 향하는 화살표로 표시한다.
- 프로세스가 자원을 대기하는 경우는 프로세스로부터 자원으로 향하는 화살표로 표시한다.
- 자원이 2개 이상의 프로세스를 동시에 허용하는 경우는 다중 자원이라고 부른다. 다중 자원은 수용할 수 있는 프로세스의 수를 사각형 안에 작은 동그라미로 표현한다.
식사하는 철학자 문제 예시
- 철학자 4명이 둥그런 식탁에 둘러앉아 식사를 한다.
- 왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야만 식사가 가능하다.
- 모두가 왼손으로 포크를 잡은 경우 아무도 식사를 하지 못하는 상태가 된다.
교착 상태 필요조건
교착 상태 필요조건
- 상호 배제(mutual exlusion): 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 지원이어야 한다.
- 비선점(non-preemption): 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.
- 점유와 대기(hold and wait): 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.
- 원형 대기(ciurcular wait): 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다.
식사하는 철학자 문제와 교착 상태 필요조건
- 상호 배제: 포크는 한 사람이 사용하면 다른 사람이 사용할 수 없는 배타적인 자원이다.
- 비선점: 어떤 사람이 다른 사람의 포크를 빼앗을 수 없다.
- 점유와 대기: 왼쪽 포크를 점유하면서 오른쪽 포크를 대기하고 있어야된다.
- 원형 대기: 서로 대기하는 포크가 원형을 이루고 있다.
교착 상태 해결 방법
교착 상태 해결 방법
- 교착 상태 예방: 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식이다. 하지만 이 방법은 실효성이 적다.
- 교착 상태 회피: 자원 할당량을 조절하여 교착 상태를 해결하는 방식이다. 그러나 자원을 얼마만큼 할당해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적다.
- 교착 상태 검출과 회볼: 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착 상태를 검출한다. 만약 교착 상태가 발생하면 교착 상태 화복 단계가 진행된다.
교착 상태 예방
- 상호 배제 예방: 시스탬 내에 있는 상호 배타적인 모든 자원을 없애버리는 방법이다. 그러나 현실적으로 모든 자원을 공유할 수 없다.
- 비선점 예방: 모든 자원을 빼앗을 수 있도록 만드는 방법이다. 하지만 임계구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없으므로 현실적이지 못하다. 또한, 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 등도 결정하기 어렵다. 이러한 방법은 아사 현상이 발생할 수도 있다.
- 점유와 대기 예방: 자원을 전부 할당하거나 아예 할당하지 않는 방식을 사용한다. 다음과 같은 단점이 있다.
- 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵다.
- 자원의 활용성이 떨어진다. 프로세스가 앞으로 사용할 자원까지 미리 선점하기 때문에 자원 낭비가 발생한다.
- 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다.
- 모든 자원을 확보해야 실행되기 때문에 결국 일괄 작업 방식으로 동작한다.
- 원형 대기 예방: 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법이다. 자원을 한 방향으로만 사용하도록 설정함으로써 원형 대기를 예방할 수 있다. 즉 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것이다. 그러나 이 또한 다음과 같은 단점이 있다.
- 프로세스 작업 진행에 유언성이 떨어진다. 프린터를 사용한 다음 마우스를 할당받으려면 운영체제가 거부하는 것이 사용자 입장에서는 납득하기 어렵다.
- 자원의 번호를 어떻게 부여할 것인지가 문제이다.
교착 상태 회피
- 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어 주는 방법이다.
- 교착 상태 회피는 자원의 총수와 할당된 자원의 수를 기준으로 시스템을 안정 상태(safe state)와 불안정 상태(unsafe state)로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다.
은행원 알고리즘
- 할당하려는 자원의 수가 안정 상태이면 허용되지만 그렇지 않으면 거부되는 알고리즘
- 은행원 알고리즘에서 각 프로세스는 자신이 사용할 자원의 최대 수를 운영체제에 알려준다.
| 변수 | 설명 |
| — | — |
| 전체 자원(Total) | 시스템 내 전체 자원의 수 |
| 가용 자원(Available) | 시스템 내 현재 사용할 수 있는 자원의 수(가용 자원=전체 자원-모든 프로세스의 할당 자원) |
| 최대 자원(Max) | 각 프로세스가 선언한 최대 자원의 수 |
| 할당 자원(Allocation) | 각 프로세스에 현재 할당된 자원의 수 |
| 기대 자원(Expect) | 각 프로세스가 앞으로 사용할 자원의 수(기대 자원=최대 자원-할당 자원) |
- 각 프로세스의 기대 자원가 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다. 가용 자원이 기대 자원보다 크다는 것은 그 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 있다는 의미이므로 안정 상태이다.
- 가용 자원이 어떤 기대 자원보다 크기 않으면 할당하지 안흔ㄴ다. 가용 자원을 사용하여 작업을 마칠 수 있는 프로세스가 없다는 의미이므로 불안정 상태이다.
교착 상태 회피의 문제점
- 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다. 모든 프로세스가 자신이 사용할 자원을 미리 선언하는 것은 쉬운 일이 아니다.
- 시스템의 전체 자원 수가 고정적이어야 한다. 하지만 일시적인 고장이나 새로운 자원이 추가되는 일이 빈번하므로 시스템 자원의 수는 유동적이다.
- 자원이 낭비된다. 실제로 교착 상태가 발생하지 않는데도 발생할 것이라고 예상함으로써 프로세스에 자원을 할당하는 데 제약을 둔다.
교착 상태 검출
- 타임아웃을 이용한 교착 상태 검출
- 일정 시간동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다.
- 장점: 특별한 알고리즘이 없어 쉽게 구현할 수 있다.
- 단점
- 엉뚠한 프로세스가 강제 종료될 수 있다.
- 모든 시스템에 적용할 수 없다. 분산 데이터베이스의 경우는 원격지에 있는 프로세스의 응답이 없는 것이 교착 상태 때문인지, 네트워크 때문인지, 단순히 처리가 늦어지는 것인지 정확히 알 수 없다.
- 위와 같은 문제에도 불구하고 타임아웃은 대부분의 데이터베이스와 운영체제에서 많이 선호한다.
- 데이터베이스의 경우 데이터의 일관성이 깨지면 안되기 때문에 교착 상태 처리가 복잡하다.
- 이 문제를 해결하기위해 체크포인트(check point)와 롤백(roll back)을 사용한다.
- 체크포인트: 작업을 하다가 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시. 체크포인트를 설정하면 현재의 시스템 상태가 하드디스크에 저장되는데, 이렇게 저장된 데이터를 스냅숏(snap shot)이라고 한다.
- 롤백: 작업을 하다가 문제가 발생하여 과거 체크포인트로 되돌아가는 것.
- 데이터베이스는 중요한 데이터에 잠금 요청하면 체크포인트를 만들고 해당 시점의 스냅숏을 저장한다. 만약 타임 아웃이 걸려서 프로세스를 중단하거나 잠금을 포기해야 한다면 롤백을 사용하여 체크포인트 지점으로 시스템을 복귀시킨다.
- 자원 할당 그래프를 이용한 교착 상태 검출
자원 할당 그래프에 사이클이 존재하면 교착 상태가 있는 것으로 판단한다.
만약 다중 자원을 사용하는 경우에는 자원 할당 그래프에 사이클이 있다고 해서 모두 교착 상태라고 판단할 수 없다.
장점: 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다.
단점: 자원 할당 그래프를 유지하고, 갱신하고, 사이클을 검사하는 추가 작업으로 인해 오버헤드가 발생한다. 이러한 추가 작업ㅇ르 줄이기 위해서 자원이 할당될 때마다 사이클 검사하는 것이 아니라 일정 시간마다 하는 방법도 있다.
교착 상태 회복
- 교착 상태를 유발한 프로세스를 강제로 종료한다. 프로세스를 강제로 종료하는 방법은 두 가지가 있다.
- 교착 상태를 일으킨 모든 프로세스를 동시에 종료
- 이 방법은 종료된 프로세스들이 동시에 작업을 시작하면 다시 교착 상태를 일으킬 가능성이 크다.
- 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
- 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료하면서 나머지 프로세스의 상태를 파악한다.
- 어떤 프로세스부터 종료할 것인지 다음과 같은 기준이 필요하다.
- 우선순위가 낮은 프로세스를 먼저
- 우선순위가 같은 경우 작업 시간이 짧은 프로세스를 먼저
- 위 두조건이 같은 경우 자원을 많이 사용하는프로세스를 먼저
- 교착 상태 회복 단게에서는 관련 프로세스를 강제 종료하는 일뿐 아니라 강제 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일도 해야한다.
- 시스템 복구는 명령어가 실행될 때마다 체크포인트를 만들어 가장 최근의 검사 시점으로 돌아가는 식으로 한다.
- 그러나 이 방법은 장업량이 상당하여 시스템에 부할르 주므로 체크포인트를 무분별하게 사용하지 말고 선택적으로 사용해야 한다.
다중 지원과 교착 상태 검출
다중 자원과 사이클
- 다중 자원의 경우에는 자원 할당 그래프에 사이클이 있다고 모두 교착 상태가 되는 것은아니다.
- 다중 자원이 포함된 자원 할당 그래프에서는 대기 그래프와 그래프 감소 방법을 이용하여 사이클을 찾는다.
대기 그래프와 그래프 감소
- 대기 그래프: 자원 할당 그래프에서 프로세스와 프로세스 간에 기다리는 관계만 나타내는 그래프.
- 그래프 감소: 대기 그래프에서 작업이 끝날 가능성이 있는 프로세스의 화살표와 관련 프로세스의 화살표를 연속적으로 지워가는 작업을 말한다.
연습 문제
- 교착 상태
- 자원 할당 그래프
- 아래
- 상호 배제: 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없어야된다.
- 비선점: 한 프로세스가 사용중인 자원을 다른 프로세스가 뺏을 수 없다.
- 점유와 대기: 프로세스가 한 자원을 점유하면서 다른 자원을 대기하는 상태여야한다.
- 원형 대기: 점유와 대기를 하는 프로세스 간 관계가 원형을 이루어야한다.
- 교착 상태 예방
- 교착 상태 회피
- 교착 상태 검출과 회복
- 교착 상태 검출
- 교착 상태 회피
- 교착 상태 예방, 원형 대기 예방
- 교착 상태 예방, 점유와 대기 예방
- 교착 상태 회복
- 사이클
심화 문제
- 아래
- 프로세스가 자신이 필요한 자원을 처음에 모두 아는 것이 사실상 불가능하다.
- 프로세스가 앞으로 사용할 자원까지 미리 선점하기 때문에 자원 낭비가 심해진다.
- 필요한 자원이 많은 프로세스가 불리한 구조다.
- 일괄 작업 방식으로 동작한다.
- 아래
- 프로세스가 자신이 필요로 하는 자원을 미리 선언하는 것은 어렵다.
- 시스템의 자원의 수가 고정적이어야한다. 하지만 일시적인 고장이나 새로운 자원이 추가되는 일이 빈번하므로 시스템 자원의 수는 유동적이다.
- 시스템의 성능을 제대로 활용할 수 없다는 문제가 있다.
- 아래
- 장점: 구현이 간단하다.
- 단점: 잘못된 프로세스가 종료될 수도 있다. 네트워크를 사용하는 프로세스는 지연의 원인이 네트워크가 문제인지 교착 상태인지 파악하기 어렵다.