교착상태

[dnnals]

📆 일자: 26년 7월 31일(금)

발제 의도

해당 주제는 교착 상태의 4가지 발생 조건이나 용어를 단순히 암기하는 것이 아니라, 멀티 스레드/프로세스 환경에서 발생할 수 있는 동기화 문제를 이해하고 시스템 자원 관리 관점에서 이를 어떻게 대처할지 사고 과정을 학습하기 위한 주제입니다.

1. 교착 상태(Deadlock)란 무엇이며, 기아 상태(Starvation)와는 어떤 차이가 있나요?

2. 교착 상태가 발생하기 위해 충족되어야 하는 4가지 필수 조건에 대해 설명해주세요.

3. 교착 상태를 해결하기 위한 3가지 주요 접근 방식(예방, 회피, 검출/회복)의 개념과 차이점을 설명해주세요.

[k9425mino]

1. 교착 상태(Deadlock)란 무엇이며, 기아 상태(Starvation)와는 어떤 차이가 있나요?

교착 상태(Deadlock)란 여러 프로세스가 서로가 가진 자원을 기다리면서 무한히 대기하는 상태를 의미한다. 즉, 어떤 프로세스도 작업을 계속 진행할 수 없는 것이다.

예를 들어,

• 프로세스 A는 자원 X를 점유한 채 자원 Y를 기다리고,
• 프로세스 B는 자원 Y를 점유한 채 자원 X를 기다리면,
• 서로가 서로를 기다리기 때문에 영원히 실행되지 못한다.

반면 기아 상태(Starvation)는 특정 프로세스가 계속 실행 기회를 받지 못해 무한히 대기하는 상태이다. 이는 우선순위가 높은 프로세스가 계속 CPU나 자원을 차지하는 경우 발생할 수 있다.

차이점

• Deadlock: 서로 자원을 점유한 채 기다려 모든 관련 프로세스가 멈춤
• Starvation: 특정 프로세스만 계속 실행 기회를 얻지 못함(다른 프로세스는 정상 실행 가능)

2. 교착 상태가 발생하기 위해 충족되어야 하는 4가지 필수 조건에 대해 설명해주세요.

교착 상태는 다음 4가지 조건이 모두 만족될 때 발생할 수 있다.

1. 상호 배제(Mutual Exclusion)
   • 하나의 자원은 한 번에 하나의 프로세스만 사용할 수 있다.
2. 점유 및 대기(Hold and Wait)
   • 이미 자원을 가진 프로세스가 다른 자원을 추가로 요청하며 기다린다.
3. 비선점(No Preemption)
   • 사용 중인 자원을 강제로 빼앗을 수 없으며, 해당 프로세스가 직접 반납해야 한다.
4. 순환 대기(Circular Wait)
   • 여러 프로세스가 원형 구조로 서로의 자원을 기다린다.
   • 예) P1 → P2 → P3 → P1

이 네 가지 조건이 모두 만족될 때 교착 상태가 발생한다.

3. 교착 상태를 해결하기 위한 3가지 주요 접근 방식(예방, 회피, 검출/회복)의 개념과 차이점을 설명해주세요.

1. 예방(Prevention)
   교착 상태가 발생하는 4가지 조건 중 하나 이상을 미리 제거하여 교착 상태 자체가 발생하지 않도록 하는 방법이다. 예를 들어, 자원을 항상 같은 순서로 요청하도록 하여 순환 대기를 막는다.

• 장점: 교착 상태가 절대 발생하지 않는다.
• 단점: 자원 활용률이 낮아지고 시스템 성능이 떨어질 수 있다.

2. 회피(Avoidance)
   프로세스의 자원 요청이 들어올 때 안전 상태(Safe State) 인지 판단한 후, 안전한 경우에만 자원을 할당한다. 대표적인 알고리즘으로 은행원 알고리즘(Banker's Algorithm)이 있다.

• 장점: 교착 상태를 방지하면서 자원을 비교적 효율적으로 사용할 수 있다.
• 단점: 프로세스의 최대 자원 요구량을 미리 알아야 하며 구현이 복잡하다.

3. 검출 및 회복(Detection & Recovery)
   교착 상태가 발생하는 것을 허용한 뒤, 주기적으로 교착 상태를 검사하고 발견되면 해결하는 방식이다. 회복 방법으로는 프로세스 종료, 자원 강제 회수(선점) 등이 사용된다.

• 장점: 평소에는 자원을 효율적으로 사용할 수 있다.
• 단점: 교착 상태가 실제 발생한 후에 처리하므로 복구 비용이 발생할 수 있다.

이들의 문제해결 접근 방식을 비교하면,

• 예방(Prevention): 교착 상태 발생 조건을 제거함
• 회피(Avoidance): 안전 상태일 때만 자원을 할당함
• 검출 및 회복(Detection & Recovery): 발생을 허용한 뒤, 검출 및 복구함

[eunji719]

1. 교착 상태(Deadlock)란 무엇이며, 기아 상태(Starvation)와는 어떤 차이가 있나요?

두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다려서 꽉 막혀 버려 결과적으로 어떤 작업도 진행되지 못하는 상태를 교착상태 라고 말한다.

기아상태도 자원을 할당받지 못해서 작업을 수행하지 못하는 점에서 비슷해 보일 수 있으나, 기아 상태는 시스템의 자원 할당 정책 즉 우선순위 같은 문제로 자원 할당이 미뤄져서 작업이 멈춘 상태를 말한다. 기아 상태는 오래 대기한 프로세스에게 우선순위를 주는 기법 에이징을 활용해 해결한다/

---

2. 교착 상태가 발생하기 위해 충족되어야 하는 4가지 필수 조건에 대해 설명해주세요.

교착 상태가 발생하기 위해선 4가지 필요조건이 있다.

1. 하나의 프로세스가 자원을 사용중일 때 다른 프로세스는 그 자원을 사용할 수 없는 경우인 상호배제 조건을 만족 시켜야 한다.
2. 한 프로세스가 최소 하나의 자원을 점유하고 있으면서, 다른 프로세스가 사용중인 자원을 사용하기 위해 대기하는 프로세스가 존재해야 한다.
3. 다른 프로세스가 한 자원을 사용중인 경우, 그 사용이 끝날 때 까지 다른 프로세스는 강제로 선점할 수 없다.
4. 프로세스와 자원이 그려진 그림에서 순환 모양을 갖고 있어야 한다.

---

3. 교착 상태를 해결하기 위한 3가지 주요 접근 방식(예방, 회피, 검출/회복)의 개념과 차이점을 설명해주세요.

교착상태 예방

교착상태 필요조건 4가지 중 하나라도 아예 발생하지 않도록 사전에 예방하는 방법이다.
교착상태 필요조건 4가지에 각각 대응하는 방법으로 자원을 공유 가능하게 만들어서 상호배제를 부정시킨다거나, 프로세스가 자원 사용을 대기할 때 다른 자원을 전혀 보유하지 않은 상태로 만들거나 아니면 반대인 경우로 만든다. 또는 자원을 점유한 프로세스가 다른 자원 또한 기다리고 싶은 경우, 현재 가진 자원을 강제로 반납하게 만든다. 또는 모든 자원에 고유한 번호를 매기고, 한방향으로만 자원을 요청할 수 있게 만들어 원형대기 상태를 깨뜨린다. 이렇게 교착상태를 예방하는 방법은 교착상태를 가장 강력하게 방지할 수 있지만, 제약이 많아서 자원의 활용률이 떨어지고 시스템 성능에 제약이 생길 수 있다.

---

교착상태 회피

는 자원 요청이 들어왔을 때, 교착상태가 발생할 가능성이 있는지 안전성을 검사한 뒤에만 자원을 할당해 주는 방법으로 대표적인 알고리즘으로 은행원 알고리즘이 있다. 은행원 알고리즘은 쉽게 말해서 은행에서 빌려줄 수 있는 돈을 정해놓고, 은행도 살아남을 수 있는 최소 돈(안전 상태)을 남겨 둘 수 있도록 하는 알고리즘이다. 만약 불안정 상태에 빠질 위험이 있다면 자원 할당을 거부하고 프로세스를 대기 시킨다! 이 방식은 프로세스가 실행 중에 사용할 최대 자원 요구량을 미리 명시해야 한다. 이는 현실적으로 매우 어렵고 자원이 요청 될 때 마다 매번 시뮬을 돌려야 해서 오버헤드가 크다.

---

교착 상태 검출/회복

교착상태 발생을 사전에 막지 않고 그냥 냅둔 뒤 주기적으로 검사해서 교착상태가 발생했다면 해결하는 방법을 말한다. 이 방식은 검사를 자주 하면 오버헤드가 발생할 수 있지만, 예방이나 회피 방식 보다는 자원의 제약이 적다.