운영체제 강의노트 정리 - 교착상태
교착상태
시스템 모델
시스템은 자원과 프로세스로 구성된다.
자원은 주기억 장치 공간, CPU 시간, 파일, 입출력 장치 등을 뜻하며, 유한하다.
여러 프로세스가 유한한 자원을 차지하기 위해 경쟁한다.
프로세스가 요청할 수 있는 자원의 수는 제한이 없으나, 시스템에 존재하는 자원보다 많은 수의 자원을 요청할 수 없다.
프로세스는 자원을 사용하기 전에 요청해야 하며, 사용이 끝났다면 해제해야 한다.
- 요쳥request : 프로세스는 자원을 사용하기 위해 요청하며, 바로 사용할 수 없다면 대기한다.
- 사용use
- 해제release : 획득한 자원의 사용이 끝나면 다른 프로세스들이 사용할 수 있도록 해제한다.
자원의 요청과 해제는 시스템 호출을 통해 이루어진다.
자원에 대한 대기는 세마포어를 이용하여 구현할 수 있다.
어떤 집합 내에 있는 모든 프로세스가 대기 상태이며, 이 집합 내에 있는 각 프로세스가 이 집합 내의 다른 프로세스가 가지고 있는 자원을 기다리고 있으면, 교착 상태에 있다고 말한다.
교착상태의 특징
필요 조건
다음 네 개의 요구 조건이 충족되어야 교착 상태가 발생한다.
- 상호 배제 : 최소한 하나는 비공유 방식으로 점유되어야 하며, 이는 한 번에 하나의 프로세스만 자원을 사용할 수 있음을 말한다.
- 점유 및 대기 : 프로세스는 최소한 하나의 자원을 점유하고 있고, 다른 프로세스가 점유하고 있는 다른 자원을 기다리고 있어야 한다.
- 비선점 : 점유된 자원은 강제로 해제될 수 없으며, 해당 자원의 사용을 끝마칠 때까지 다른 프로세스는 해당 자원을 획득할 수 없어야 한다.
- 순환 대기 : 자원을 대기하는 그래프가 사이클을 이룬다.
자원 할당 그래프
- 노드 : 프로세스 노드 / 자원 노드. 자원 노드는 직사각형으로 그려지며 내부에 같은 유형의 자원의 인스턴스를 나타낸다.
- 선 : 프로세스 노드에서 자원 노드로 화살표가 이어지면, 프로세스가 자원을 요청하였음을 의미한다(요청선). 자원 노드에서 프로세스 노드로 화살표가 이어지면, 프로세스가 자원을 획득하였음을 의미한다(할당선).
요청선의 경우 자원 노드를 나타내는 직사각형을 가리키나, 할당선의 경우 자원 노드의 특정 인스턴스와 프로세스가 연결된다.
주어진 자원 할당 그래프에 사이클이 없으면 교착 상태가 없는 것이고, 있으면 교착 상태가 존재할 수 있는 가능성이 있음을 나타낸다.
각 자원이 하나의 인스턴스만을 가지고 있다면, 사이클을 이루는 것은 교착 상태의 필요충분조건이 된다.
교착상태를 처리하는 방법
교챡 상태 예방prevention 방법 : 네 가지 필요 조건 중 한 가지가 발생하지 않도록 하여 예방한다. 자원 요청을 제한한다.
교착 상태 회피avoidance 방법 : 프로세스가 어떠한 자원을 요청할지 운영체제가 미리 알아야 한다. 이 정보를 이용하여 프로세스가 자원을 요청할 때 허용 여부를 결정한다.
교착 상태 탐지detection 방법 : 교착 상태를 발견하는 알고리즘과 교착 상태로부터 시스템을 복구하는 알고리즘을 제공하여 교착 상태 문제를 해결한다.
교착 상태를 무시하는 경우 결국에는 시스템을 다시 시작해야 한다.
교착상태 예방
상호 배제
어떠한 자원은 근본적으로 공유를 할 수 없으므로, 상호 배제 조건을 통해 교착 상태를 예방하기 어렵다.
점유 및 대기
실행되기 전에 필요한 모든 자원을 점유하도록 하거나, 한 자원을 점유한 상태에서 다른 자원을 요청할 수 없도록 할 수 있다.
이 경우 할당받은 자원을 오랜 시간 사용하지 않을 수 있으므로 효율이 떨어지고, 여러 자원이 필요한 프로세스는 영원히 기다릴 가능성이 있다.
비선점
프로세스가 자원을 점유하고 있으면서 바로 할당될 수 없는 자원을 요청하면, 그 프로세스가 점유하고 있는 모든 자원을 해제하게 한다.
A 프로세스가 A 자원을 요청하였을 때, B 자원을 기다리고 있는 B 프로세스가 A 자원을 점유하고 있다면, B 프로세스로부터 A 자원을 해제하고 그것을 A 프로세스에게 할당한다.
순환 대기
각 자원의 인스턴스에 번호를 부여하고 낮은 번호의 자원 인스턴스부터 할당받도록 한다.
프로세스가 어떠한 자원 인스턴스를 점유하고 있다면, 이 프로세스는 그보다 높은 번호를 가진 자원 인스턴스만 요청할 수 있으며, 자원을 요청하기 전 그보다 낮은 번호를 가진 자원 인스턴스를 해제해야 한다.
교착상태 회피
프로세스가 필요로 하는 자원의 정보를 이용하여, 프로세스가 해당 자원을 요청했을 때 교착 상태가 발생하지 않도록 지연하거나 할당해주는 방법이다.
현재 사용 가능한 자원, 각 프로세스에게 할당된 자원, 각 프로세스의 미래 요청과 해제를 고려하여 할당 또는 지연을 결정한다.
안전한 상태
교착 상태 회피 알고리즘은 안전한 상태safe state를 정의하고, 프로세스가 자원을 요청하면 안전한 상태를 유지하는지 검사한 다음 할당해준다.
이를 위해 각 프로세스는 미리 각 유형의 자원마다 필요로 하는 최대 개수를 선언해 주어야 한다.
시스템에 안전한 순서safe sequence가 있으면 그 시스템은 안전하다고 하며, 이 때 교착 상태는 발생하지 않는다.
안전한 순서는, 어떠한 프로세스의 요청이 현재 사용 가능한 자원과 이전 순서의 프로세스가 점유하고 있는 자원에 의해 만족될 수 있음을 의미한다.
자원 할당 그래프 알고리즘
각 유형의 자원마다 하나의 인스턴스가 존재할 때 사용할 수 있다.
기존 자원 할당 그래프에 점선으로 표시하는 요청가능선claim edge를 추가한다. 이는 미래에 프로세스가 자원을 요청할 수 있음을 나타낸다.
프로세스가 자원을 요청하면 요청가능선을 할당선으로 바꾸어 사이클이 형성되는지 검사하여 형성되지 않는 경우에만 요청을 허용한다.
은행가 알고리즘
일반적인 경우에 사용할 수 있는 교착 상태 회피 알고리즘.
각 프로세스는 생성되기 전에 각 자원의 유형마다 필요한 최대 자원 인스턴스 수를 선언해야 하며, 이는 시스템의 전체 자원의 수를 초과할 수 없다.
프로세스가 자원을 요청하면 시스템이 안전한 상태를 유지하는지 검사한다.
n이 프로세스 개수이고, m이 자원의 유형 수라고 할 때, n by m 행렬을 사용하여 각 프로세스의 각 자원에 대한 최대 수요 및 할당되어 있는 각 자원의 인스턴스 개수, 남은 수요를 나타낸다.
교착상태 탐지
교착 상태를 허용하고 주기적으로 교착 상태를 발견하여 시스템을 복구하는 방법이다.
교착 상태를 발견하기 위해 필요한 정보를 시스템에서 유지해야 하며, 교착 상태로부터 회복하는 과정에서 본질적으로 손실이 발생한다.
각 자원의 유형마다 단일 인스턴스로 구성된 경우
자원 할당 그래프를 이용하여 교착 상태를 발견할 수 있다.
자원 할당 그래프를 대기 그래프wait-for graph로 변경한다. 이는 프로세스 간 연결 상태를 나타내며, 화살표 방향은 A 프로세스는 B 프로세스가 점유하고 있는 자원을 기다리고 있음을 나타낸다.
교착 상태는 대기 그래프에 사이클이 있는지 검사하여 발견할 수 있다.
각 자원의 유형이 여러 인스턴스로 구성된 경우
은행가 알고리즘과 유사한 데이터 구조를 이용한다.
탐지 알고리즘의 사용
탐지 알고리즘은 교착 상태가 발생하는 빈도, 교착 상태가 발생하였을 때 영향을 받는 프로세스의 개수에 따라 그 사용 빈도가 결정된다.
교착 상태가 자주 발생하면 탐지 알고리즘을 자주 실행해야 하며, 교착 상태를 오래 방치하면 교착 상태에 포함되는 프로세스의 수는 증가한다.
교착 상태는 프로세스가 바로 할당받을 수 없는 자원을 요청하였을 때 발생한다. 이럴 때마다 탐지 알고리즘을 실행할 수 있으나 비용 때문에 현실성이 없다.
자원의 유형이 많으면 하나의 요청이 여러 사이클을 형성할 수 있다.
교착상태로부터의 회복
시스템 운영자에게 통보하여 수동으로 처리하거나, 시스템이 자동으로 복구한다.
시스템 차원에서는 순환 대기하는 프로세스를 종료하거나, 교착 상태에 포함되어 있는 프로세스에서 하나 이상의 자원을 강제로 해제하여 해결할 수 있다.
프로세스 종료
교착 상태에 포함된 모든 프로세스를 종료하거나, 순환 대기하는 프로세스 중 하나를 종료한다.
전자의 경우 교착 상태가 바로 해결되나 비용이 많이 들며, 후자의 경우 비용은 적지만 교착 상태가 바로 해결되지 않을 수 있어 추가적인 프로세스 종료가 필요할 수 있다.
작업 중간에 프로세스가 강제 종료되면 일관성 문제가 발생할 수 있고, 하드웨어를 초기화해주어야 하는 경우가 발생할 수 있다.
순환 대기하는 프로세스 중 하나를 종료할 때, 다음의 요소를 고려하여 종료할 프로세스를 선택한다.
- 프로세스의 우선순위
- 프로세스의 실행 시간 및 남은 시간
- 프로세스가 점유하고 있는 자원의 수와 유형 (선점하기 쉬운 자원을 가지고 있는 프로세스를 종료하는 것이 유리함)
- 프로세스가 필요로 하는 자원의 수
- 교착 상태를 해결하기 위해 종료해야 하는 프로세스의 수
- 프로세스의 종류 (시스템, 상호작용 등)
자원의 강제 해제
다음의 요소를 고려한다.
- 희생자 선택 : 어떤 자원을 어떤 프로세스로부터 해제할지 결정한다.
- 복귀rollback : 어떤 프로세스로부터 자원을 강제 해제하면 그 프로세스가 다시 정상 수행될 수 있도록 해야 한다.
- 굶주림 : 같은 프로세스로부터 자원을 계속 해제하면 이 프로세스는 영원히 실행되지 못할 수 있다. 희생자로 선택될 수 있는 횟수를 제한하여 해결할 수 있다.