오늘은 교착 상태에 대해 알아 보도록 한다.
자원을 사용할 때 서로가 서로를 물고 놓아주지 않아서 hang up 상태가 되거나 서버가 정상적인 동작을 하지 않는 것이라고 대충은 알고 있었으나 정확히는 몰라 알아보도록 한다.
정의
교착 상태는 동일한 리소스를 공유하는 프로세스들이 서로의 리소스에 액세스하는 것이 차단되는 것을 이야기 한다.
보통 프로세스나 스레드의 경우 특정 작업을 완료하게 되면 프로세스나 스레드가 보유하고 있던 리소스를 해제한다. 그리고 다른 리소스를 할당하게 되는데 둘 이상의 프로세스가 리소스를 보유하고 있고, 리소스를 해제하고 재할당하는 과정에서 각각 서로의 리소스를 갖고자 할 때 서로 리소스가 해제되는 것을 기다리기 때문에 영원히 차단되는 것이다.
더욱 구체적으로 이야기 하면 교착 상태가 발생하는 조건은 4가지가 있다.
교착상태 발생 조건
1. 상호 배제 (Mutual exclusion)
- 주어진 시간에 단 하나의 프로세스만 리소스를 사용할 수 있다. 즉, 리소스는 공유할 수 없는것을 의미한다.
2. 점유와 대기 (Hold and wait)
- 프로세스는 한 번에 최소한 하나의 리소스를 보유하고 있으며, 다른 프로세스가 보유하고 있는 다른 리소스를 얻기를 기다리고 있다.
3. 비선점 (No preemption)
- 프로세스가 자발적으로 리소스를 해제할 수 있다.
- 프로세스 실행 후에 리소스가 해제될 수 있다.
4. 순환 대기 (Circular wait)
- 일련의 프로세스가 순환 방식으로 서로를 기다리고 있다.
- 예를 들어 A 프로세스, B 프로세스가 있다고 가정했을 때, 모든 프로세스 사이에 순환 관계를 생성하며 실행될 때까지 영원히 기다려야 한다.
위와 같은 조건들이 해당 될때 교착 상태가 발생하게 된다.
이러한 교착 상태를 해결하는 여러 전략이 있다. 교착상태 예방, 회피, 발견 및 복구, 무시 등이 있다.
교착상태 예방 (Prevention)
교착상태가 발생하는 조건들에 대해 발생하지 않도록 사전에 시스템을 제어 하도록 한다. 교착상태 예방 방법을 사용하게 되면 리소스 활용도가 낮기 때문에 처리량이 감소한다.
1. 상호 배제(Mutual Exclusion) 부정
- 여러 프로세스가 동시에 자원을 사용하게 한다.
2. 점유 및 대기(Hold and Wait) 부정
- 프로세스가 실행되기 전에 필요한 모든 자원을 요구하도록 해 점유와 대기를 하지 않도록 한다.
3. 비선점(Non-preemption) 부정
- 이미 점유중인 자원을 다른 프로세스가 요구하면 그 자원을 빼앗을 수 있도록 한다.
4. 순환 대기(Circular Wait) 부정
- 각 자원에 번호를 부여하고 각 프로세스는 번호가 낮은 자원부터 높은 자원 순으로 요구하도록 함
교착상태 회피 (Avoidance)
예방 알고리즘은 리소스 활용도가 낮기 때문에 처리량이 감소한다. 대신, 사용 가능한 리소스, 할당된 리소스, 향후 요청 및 프로세스 별 향후 릴리스를 포함하여 요청을 승인해도 교착 상태가 발생하지 않는다는 것을 명확히 확인할 수 있는 경우에만 리소스 요청을 승인하는 방법이다.
커널은 프로세스의 향후 동작에 대한 상세 지식이 부족해 교착 상태를 정확히 예측할 수 없다. 이러한 조건에서 교착 상태를 방지하기 위해서 아래와 같은 방식을 사용한다.
- 각 프로세스는 필요한 각 클래스의 최대 리소스 단위 수를 선언한다.
- 커널은 프로세스가 선언된 최대 수에 따라 이러한 리소스 단위를 단계적으로 요청할 수 있도록 허용하고 최악의 경우 분석 기술을 사용하여 향후 교착 상태 가능성을 확인한다.
- 교착상태가 발생할 가능성이 없는 경우에만 요청이 승인된다.
- 그렇지 않으면 승인될 때까지 보류 상태로 유지된다.
- Safe 상태일 때가 Deadlock이 발생하지 않는 상태이며, Unsafe 상태로 넘어가지 않도록 해야한다. Unsafe 상태는 Deadlock이 발생할 가능성이 있다.
- 프로세스에 Safe Sequence가 존재하면 해당 프로세스는 Cycle이 형성되지 않는다.
회피의 경우 Resource-Allocation Graph (RAG) Algorithm 과 Banker's Algorithm이 있다.
RAG
RAG는 일반적으로 교착 상태를 방지하는 데 사용되고, 시스템의 현재 상태를 그래프로 시각화 하는 데 사용된다. 그래프에는 모든 프로세스, 프로세스에 할당된 리소스는 물론 각 프로세스가 요청하는 리소스도 포함된다.
RAG에 cycle이 할당되어 있지 않으면 교착 상태가 발생하지 않고, cycle이 할당되어 있으면 교착 상태가 발생할 수 있다. 모든 리소스의 인스턴스가 하나만 있는 경우 교착 상태를 의미한다. RAG의 정점은 리소스와 프로세스이다.
RAG에는 request edges 와 assignment edges가 있다. 프로세스에서 리소스로의 엣지는 요청 엣지이고, 리소스에서 프로세스로의 엣지는 할당 엣지이다. calm edge의 경우 요청이 나중에 이루어질 수 있음을 나타내며 점선으로 표시된다. calm edge를 기반으로 cycle이 발생할 가능성이 있는지 확인한 다음 시스템이 다시 safe state가 될 경우 요청을 승인할 수 있다.
위 사진과 같이 calm edge 상태인 그래프를 고려해야한다.
위 그림과 같이 R2가 P2에 할당되고 P1이 R2를 요청하게되면 교착 상태가 발생한다.
3 종류의 Edge를 포함해 Cycle이 만들어지게 되면 Unsafe state이며, Deadlock 이 발생한 상태는 아니지만 발생 가능성이 있으므로 피해주어야 한다. 결론적으로 P2가 R2의 자원을 할당받는 것을 막아주는 것이 피할 수 있는 방법 중 하나가 된다.
RAG의 경우 리소스에 대한 인스턴스가 여러 개 있는 경우 그다지 유용하지 않다.
그래서 Banker's Algorithm을 사용한다.
Banker's Algorithm
Banker's Algorithm은 자원에 대한 프로세스의 모든 요청을 테스트하여 안전한 상태를 확인하고 요청을 승인한 후 시스템이 안전한 상태를 유지하며 요청을 허용하는 자원 할당 및 교착 상태 회피 알고리즘이다. 새로운 상태가 안전하지 않으면 리소스가 할당되지 않고 데이터 구조가 이전 상태로 복원된다. 이 경우 프로세스는 리소스를 기다려야 한다.
사전 정보는 Available, Max, Allocation, Need가 있으며, Available은 할당된 자원, Max는 최대로 할당할 수 있는 자원 수, Allocation은 이미 할당된 자원 수, Need는 할당된 자원에서 최대로 가능한 수를 뺀 수(Max-Allocation)이다.
Available과 Need를 비교하며 Sequence를 구한다.
Available이 Need보다 크면 실행가능하며 실행 후에는 Allocation이 Available에 더해져 더 큰 Need를 가진 프로세스도 실행 가능하다.
교착상태 감지 & 회복
교착상태 감지 (Detection)
교착상태 예방과 회피가 제대로 이루어지지 않으면 교착상태가 발생할 수 있고, 교착상태로부터 회복을 감지하는 일만 남는다.
모든 리소스 유형에 단일 인스턴스만 있는 경우 RAG의 변형인 Wait-For Graph라는 그래프를 사용할 수 있다. 여기서 Edge는 프로세스를 나타내며 P1에서 P2로 향하는 간선은 P1이 P2가 보유한 리소스를 기다리고 있음을 나타낸다.
RAG의 경우와 마찬가지로 wait 그래프의 주기는 교착 상태를 나타낸다. 따라서 시스템은 그래프 wait을 유지하고 주기적으로 주기를 확인해 교착 상태를 감지할 수 있다.
Detection Algorithm에서 사용하는 사전 정보는 Available, Allocation, Request가 있으며, Available은 할당 가능한 자원수, Allocation은 할당 된 자원 수, Request는 요구하는 자원 수를 나타낸다. Banker's Algorithm에서는 사용했던 Max가 없는데, 사전 예방하기 위한 것이 아닌 감지를 위한 것으로 최대 값 자체는 필요가 없기 때문이다.
Detection Algorithm을 실행하는 시기는 3가지로 나눌 수 있다. 그리고 각 시기별로 문제가 있다.
- 프로세스가 critical section 진입을 요청할 때마다
- 비용이 너무 크다
- 일정 주기에 한해서 실행
- 일정 시간 내 Deadlock이 발생하면 그대로 내버려두는 문제가 발생한다.
- 주기를 짧게 하더라도 주기 내에서 Deadlock이 발생할 수 있고, 비용이 높아지는 문제가 있다.
- CPU Utilization이 일정 이하로 내려갈 경우
- CPU Utilization이 떨어져도 Deadlock이 아닌 경우가 대부분이다.
- 직접적으로 Deadlock과 연관지을 수 없다.
교착상태 회복 (Recovery)
복구를 위해서는 교착상태에 있는 프로세스를 종료하거나, 교착 상태에 있는 프로세스가 점유하고 있는 자원을 선점하는 방법이 있다.
Deadlock이 발생했을 때 복구하는 방법은 다음과 같다.
- Process Kill
- 교착 상태와 관련된 모든 프로세스를 종료한다.
- 각 프로세스를 종료한 후 교착 상태를 다시 확인하고 시스템이 교착 상태에서 복구될 때까지 프로세스를 계속 반복한다.
- Resource Preemption (자원 선점)
- 교착 상태에 빠진 프로세스로부터 자원을 선점하고, 선점된 자원을 다른 프로세스에 할당해 교착 상태에서 시스템을 복구할 가능성을 높인다.
교착상태 무시 (Ignorance)
과학자들은 교착 상태를 해결하는 가장 효율적인 방법은 교착 상태 예방이라고 믿는다. 하지만 시스템을 다루는 엔제니어들은 교착상태 발생 가능성이 매우 적기 때문에 교착상태 예방에 덜 주의를 기울여도 된다고 믿는다.
몇 년에 한번 발생하는 교착 상태 문제보다 일주일에 한 번 발생하는 시스템 오류, 컴파일러 오류, 프로그래밍 버그, 하드웨어 충돌에 더 주의를 기울여야한다고 함.
결과적으로
- Deadlock이 전혀 일어나지 않을거라 가정하고 아무런 조치도 취하지 않음.
- 매우 드물게 발생하는 Deadlock에 조치를 취하는 것보다 다른 문제에 신경을 쓰는게 더 낫다.
- Deadlock이 발생해서 시스템에 이상이 생기거나 먹통이 생기면 사용자가 프로세스를 재시작하는 방법으로 대처하는 방법이 있다.
대부분의 OS가 무시 방법을 채택하고 있음
3줄 요약
- 프로세스가 자원을 사용하는 경우 자원을 다 사용하고 해제 후 재할당 과정을 거치게 되는데, 재할당 과정에서 서로의 자원을 할당하고자 할 때 해제되지 않은 서로의 자원을 각각 할당해서 영원히 서로 자원을 할당받지 못해 무한 대기 상태에 빠지게 되는 것을 교착 상태(Deadlock)라고 함.
- 이러한 교착 상태를 해결하는 방법은 교착상태 예방, 회피, 발견 및 복구, 무시 등의 방법이 있음. 그리고 몇몇 방법의 경우 특별한 알고리즘을 기반으로 해결한다.
- 허나 교착 상태는 거의 일어나지 않으며, 교착 상태를 예방하는 방법을 사용하는 것이 운영자로 하여금 Overhead를 불러 일으킬 수 있고, 대부분의 OS가 Ignorance의 방법을 사용하고 있음
내 생각
교착 상태를 보통 무시하는 방법으로 조치하고 있다니 조금 충격이다. 그래도 이제 교착 상태가 어떤 것인지 또한 어떻게 해결하려고 접근했는 지 알게 되었다.
[참조] :
https://80000coding.oopy.io/93cf1758-d5b4-41a6-9e26-5dc67f87c840
https://www.scaler.com/topics/operating-system/deadlock-in-os/
https://www.geeksforgeeks.org/deadlock-prevention/
https://javajee.com/deadlock-prevention-avoidance-detection-and-recovery-in-operating-systems
https://m.blog.naver.com/kseo712/220882367147
https://gofo-coding.tistory.com/entry/Deadlock-Handling
'CS 지식' 카테고리의 다른 글
| Keep-alive란? (0) | 2024.05.20 |
|---|---|
| LDAP( Lightweight Directory Access Protocol )이란? (0) | 2024.02.14 |
| KPI / SLI / SLO / SLA란? (1) | 2023.11.27 |
| GitOps란? (2) | 2023.11.20 |
| 부트 스트랩이란? (0) | 2023.11.15 |
