1. 교착상태(Dead Lock)의 개념
교착상태란 하나 또는 둘 이상의 프로세스가 더 이상 계속할 수 없는 어떤 특정 사건을 무한정으로 기다리고 있는 상태를 말한다. 여기서 '특정 사건'이란, 자원의 할당과 해제를 의미하는 것이다. 둘 이상의 서로 다른 프로세스가 자신이 요구한 자원을 할당받아 점유하고 있으면서, 상호 간에 상대방 프로세스에 할당되어 있는 자원을 요구하는 경우를 말한다.
1.1 교착상태의 발생 (필요)조건
교착상태는 한 시스템 내에서 다음의 4가지 조건이 모두 충족될 때 발생한다.
ㄱ. 상호 배제(Mutual Exclusion)
프로세서들이 자원을 배타적으로 점유하는 것으로, 한 번에 한 프로세스만이 자원 사용이 가능한 것을 말한다.
ㄴ. 점유와 대기(Hold and Wait)
일종의 부분 할당으로, 다른 종류의 자원을 부가적으로 요구하면서, 이미 어떤 자원을 점유하고 있는 것을 말한다.
그러니까 다른 프로세스가 사용 중인 자원을 사용하기 위해 대기 중인 프로세스가 존재해야 한다.
ㄷ. 비선점(Non-preemption)
자원들은 그들을 점유하고 있는 프로세스로부터 도중에 해제되지 않는다. 선점되지 않는 것이기에 비선점이라고 말하는 것이다.
ㄹ. 환형 대기(Circular Wait)
프로세스와 자원들이 원형을 이루며, 각 프로세스는 자신에게 할당된 자원을 가지면서 상대방 프로세스의 자원을 상호 요청하는 것이다. 순환 대기라고도 부른다.
2. 교착상태 대응 방법
교착상태를 예방(Prevention), 회피(Avoidance), 탐지(Detection), 복구(Recovery)함으로써 교착상태를 해결할 수 있다. 각 상태에 적합한 방식을 채택함으로써 교착상태를 해결해야 할 것이다.
- 교착상태 예방은 교착상태의 필요조건을 부정함으로써 교착상태가 발생하지 않도록 미리 예방하는 방법이다.
- 교착상태 회피는 교착상태 가능성을 배제하지 않고, 적절하게 피해 나가는 방법이다.
- 교착상태 탐지는 교착상태 발생을 허용한다. 대신, 발생 시의 원인을 규명하여 해결하려는 방법이다.
- 교착상태 복구는 교착상태 발견 후, 환형대기를 배제하거나 자원을 중단하는 메모리 할당 기법이다.
2.1 교착상태 예방
교착상태를 예방하는 것은 발생 조건을 해결하면 되는 일이다. 4가지의 조건이 발생하지 않도록 부정을 하는 방법인데, 사실 그다지 권고하지는 않는다. 왜냐하면, 이러한 기술은 비용이 많이 발생하기 때문이다. 그래서 시스템 교착상태를 없애는 것이 우선순위인 경우에만 이 기술을 사용한다.
위에서 발생조건 4가지가 모두 충족되어야만 교착상태가 발생한다고 기술했는데, 따라서 이 예방 단계에서는 필요조건 중 하나를 무효화함으로써 예방이 이뤄진다.
ㄱ. 상호 배제 조건의 부정
상호 배제 조건은 비 공유를 전제로 한다.
공유 가능한 자원들은 배타적인 접근을 요구하지 않으므로 교착상태가 될 수 없다.
ㄴ. 점유와 대기 조건의 부정
각 프로세스는 필요한 자원들을 모두 한꺼번에 요청한다.
ㄷ. 비선점 조건의 부정
이미 자원을 가지고 있는 프로세스는 자원 할당 요구가 있을 시 받아들여지지 않으면 보유 자원을 반납한다.
반납 후 필요 자원에 대한 요구를 다시 시도한다.
ㄹ. 환형 대기 조건의 부정
모든 프로세스에게 각 자원의 유형별로 할당 순서를 부여한다.
2.2 교착상태 회피
회피는 일종의 미래지향적 선택이라 할 수 있다. 우리는 은행원 알고리즘을 통해 교착상태를 회피할 수 있다.
ㄱ. 은행원 알고리즘(Banker's Algorithm)
- 안전 상태: 시스템이 교착 상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해줄 수 있는 상태이다. 안전 순서열이 존재한다.
- 불안전 상태: 안전 순서열이 존재하지 않는 상태를 말한다. 불안전 상태는 교착상태이기 위한 필요조건이기에, 교착상태는 불안전 상태에서만 발생한다.
이러한 안전 상태 개념을 이용하여 교착상태 회피 알고리즘 구성이 가능하다. 현재 가용한 자원을 프로세스 요청 시 바로 할당해 줄 것인지, 기다리게 할 것인지를 결정하는 문제라고 볼 수 있다.
2.3 교착상태 탐지
교착상태를 탐지하기 위한 기법으로는 크게 교착상태 발견 알고리즘과 자원 할당 그래프가 존재한다.
ㄱ. 교착상태 발견 알고리즘
교착상태 발생 여부를 파악하기 위하여 시스템의 상태를 검사하기 위한 알고리즘이다. 이 알고리즘은 프로세스와 리소스의 상태를 확인하여 교착 상태가 발생했는지 확인한다.
ㄴ. 자원 할당 그래프
방향 그래프를 이용하여 자원의 할당사항과 요구사항을 나타내는 기법이다. 자원 할당 그래프의 소거법을 이용하여 교착상태를 감지한다.
그밖에 시스템 모델링, 타임 스탬프, 앞서 말한 은행원 알고리즘 등으로 교착상태를 발견할 수 있을 것이다.
2.4 교착상태 회복
교착상태를 회복하는 기법에는 크게 프로세스 중지 기법과 자원 선점 기법이 존재한다.
ㄱ. 프로세스 중지
(1) 교착상태에 빠진 프로세스를 모두 중지한다. 물론, 이 방법은 단순하지만 너무 많은 비용이 들어가기 때문에 권고하는 방식은 아닐 것이다.
(2) 그렇다면 이제 교착상태 프로세스들을 하나씩 중지하는 방법이 있다. 교착상태가 해결될 때까지 프로세스를 하나씩 중지하며 교착상태가 해결되는지 확인할 것이다. 이때 등장하는 개념이 희생자 선택의 원칙인데, 어떤 프로세스를 중지할지를 선택하는 것이다. 희생자 선택의 원칙은 최소 비용으로 중지하는 방법을 찾아내는 일이다. 이것에는 프로세스 우선순위, 완료 시간 및 현재까지의 진행 상황, 프로세스에서 소비되는 자원, 프로세스를 완료하는 데 필요한 자원, 종료할 프로세스의 수, 프로세스 유형 등의 요소가 고려될 것이다.
ㄴ. 자원 선점
프로세스로부터 자원을 선점하여, 이들 자원을 교착상태가 해결될 때까지 다른 프로세스들에게 할당하는 것이다. 사실 프로세스 중지에서 조금 변형이 되었다고 봐도 무방할 것이다. 이것은 희생자 선택, 기아, 롤백 문제를 고려하여 진행된다.
※ 교착상태 무시
사실 교착상태를 무시하는 방법도 있다. 교착상태가 매우 드물다면, 그냥 냅두고 시스템을 재부팅하는 것이다. 사실 일반적으로는 이런 재부팅이 가장 친숙한 방법이기는 하다. 우리는 교착상태 무시를 위해 타조 알고리즘을 사용한다. 타조 알고리즘은 선점형 자원 할당 아이디어를 기반으로 한다. 즉, 프로세스가 리소스를 요청할 때 운영체제는 리소스가 사용 가능한지 확인하는 것이다. 리소스를 사용할 수 있으면 운영체제는 프로세스에 리소스를 부여한다. 반면, 사용할 수 없는 경우에는 운영체제는 리소스를 사용할 수 있을 때까지 프로세스를 대기 상태로 두는 것이다. 또한, 프로세스가 사용할 수 없는 리소스를 요청하는 경우 운영체제는 교착상태를 무시하고 계속해서 다른 프로세스에 리소스를 할당한다. 이는 교착상태가 발생하더라도 시스템이 계속 작동할 수 있음을 의미하는 것이다. 물론 이러한 타조 알고리즘은 모든 것이 그렇듯 장단점이 존재하기 마련이고, 결코 완벽한 솔루션은 아닐 것이다.
'보안 > 개념' 카테고리의 다른 글
| 유닉스 파일 시스템 구조 총정리 (1) | 2023.12.26 |
|---|---|
| 디스크 스케줄링 총정리 (1) | 2023.12.26 |
| 임계 영역 총정리 (0) | 2023.12.24 |
| 스펨 메일 차단 총정리 (1) | 2023.12.23 |
| CPU 스케줄링 기법 총정리 (1) | 2023.12.21 |