교착상태

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

---

교착상태 회피

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

---

교착 상태 검출/회복

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

[9ga0]

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

교착 상태란 둘 이상의 프로세스나 스레드가 서로가 점유한 자원을 기다리며 정체된 상태를 말합니다. 반면 기아상태란 다른 작업은 진행되지만, 우선순위에서 밀린 특정 프로세스나 스레드가 필요한 자원을 계속해서 할당받지 못해 실행되지 않는 상태입니다.

구분	교착 상태	기아 상태
원인	서로 자원을 기다리는 순환 관계	불공정한 자원 또는 CPU 할당
시스템 진행	관련 작업들이 모두 중단	다른 작업은 계속 진행
해소 가능성	외부 개입 없이는 해소되지 않음	스케줄링 상황에 따라 실행될 수도 있음
대표 사례	서로의 락을 기다림	낮은 우선순위 작업이 계속 밀림
해결 방법	락 순서 통일, 자원 선점 등	공정한 스케줄링, Aging 등

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

교착상태가 발생하기 위해서는 다음 네가지 필요조건이 요구됩니다. (Coffman조건)

1. 상호 배제(Mutual Exclusion)
   하나의 자원은 한 번에 하나의 프로세스만 사용할 수 있어야한다.
2. 점유와 대기(Hold and Wait)
   프로세스가 하나 이상의 자원을 이미 가진 상태에서 다른 자원을 추가로 기다린다.
3. 비선점(No Preemption)
   다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없다.
4. 순환 대기(Circular Wait)
   프로세스들이 원형으로 연결되어 서로 다음 프로세스가 가진 자원을 기다린다.

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

1. 예방(Prevention)
   교착 상태의 네가지 필수 조건 중 하나를 제거하여 교착상태를 예방하는 방식이다.
   • 상호 배제 제거 : 자원을 공유하여 사용할 수 있게.
   • 점유와 대기 제거 : 필요한 자원을 한꺼번에 요청
   • 비선점 제거 : 추가 자원을 얻지 못하면 기존 자원을 반환
   • 순환 대기 제거 : 모든 자원에 순서를 정하고 해당 순서대로만 획득

   단점: 자원의 비효율적인 사용

2. 회피(Avoidance)
   자원을 할당할 때마다 시스템의 안전 상태 여부를 확인한다. 여기서 안전 상태란 모든 프로세스가 일정한 순서에 따라 필요한 자원을 할당받고 정상적으로 종료할 수 있는 상태를 말한다. 즉 자원할당그래프에 사이클이 존재하지 않았을 때를 말한다. 대표적인 알고리즘으로 은행원 알고리즘을 사용한다.

   단점: 각 프로세스가 앞으로 필요한 최대 자원량을 미리 알아야 함.

3. 검출 및 회복(Detection and Recovery)
   교착 상태가 발견되었을 때, 즉 사후에 복구하는 방식이다.
   • 검출 : 자원 할당 그래프에 사이클이 존재하는가를 확인한다.
   • 회복 :
     • 프로세스 종료 : 교착 상태에 포함된 프로세스 하나 이상을 비용이나 우선순위를 기준으로 희생자를 선택해 종료한다.
     • 자원 선점 : 프로세스가 가진 자원을 강제로 회수한다.
     • 롤백 : 작업을 이전 상태로 되돌린 뒤 다시 실행한다.

   단점: 작업 손실이 생길 수 있고, 기아 상태가 발생할 수 있고, 종료나 롤백 비용이 큼.

구분	예방	회피	검출 및 회복
핵심 아이디어	발생 조건을 사전에 차단	안전한 경우에만 자원 할당	발생을 허용한 뒤 탐지
교착 상태 발생	원칙적으로 방지	안전 상태를 유지하면 방지	발생할 수 있음
사전 정보	크게 필요하지 않음	최대 자원 요구량 필요	필요하지 않음
자원 이용률	낮을 수 있음	예방보다 높음	비교적 높음
주요 비용	자원 사용 제약	안전성 검사	탐지와 복구
대표 사례	락 획득 순서 통일	은행원 알고리즘	프로세스 종료·자원 회수

[dnnals]

기본 질문

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

교착상태란 다중 프로그래밍 시스템에서 프로세스가 절대 일어나지 않을 이벤트를 기다리는 상태를 말합니다. 즉, 둘 이상의 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리는데 실질적으론 각각 프로세스를 끝낼 수 없는 상황이라 절대 일어나지 않을 사건을 기다리는 상태입니다. 그에 반해 기아 상태는 스케줄링 알고리즘에 의해 특정 프로세스가 우선순위가 밀려 작업 할당이 미뤄지는 현상을 말합니다.

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

교착 상태가 발생하기 위해 충족되어야 하는 4가지 조건은 상호 배제, 비선점 자원, 점유와 대기, 원형 대기가 있습니다. 상호 배제는 공유할 수 없는 자원을 서로 원하는 상태, 비선점 자원은 다른 프로세스에 할당된 자원을 빼앗을 수 없는 자원을 사용하는 것, 점유와 대기는 자원 하나를 점유한채로 다른 자원을 기다리는 상태, 원형 대기는 점유 대기하는 프로세스가 순환 구조를 이루는 상태를 말합니다. 여기서 오해가 생길 수 있는 지점이 ‘4가지가 발현되면 반드시 교착 상태가 발생한다’라는 점인데 그렇지 않고 4가지가 발현되면 교착 상태가 발생할 수 있는 가능성이 존재하는 상태가 되는 것입니다.

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

교착 상태를 해결하기 위해선 예방, 회피, 검출과 회복의 방식이 있습니다. 먼저 예방은 처음부터 교착 상태 발생 조건 4가지를 만족하지 못하게 사전에 차단하는 방식입니다. 예를 들어 ‘상호 배제를 예방한다’라면 독점적으로 사용할 수 있는 자원을 없애는 것입니다. 하지만 현실적으로 상호 배제를 예방하는 것은 어려우며 다른 조건 또한 예방하는 자체는 현실적인 어려움이 있습니다. 즉, 예방은 가장 강력한 해결 방식이지만 실제 시스템에 실현하기 어렵다는 한계가 존재합니다. 회피는 어느 수준 이상의 자원을 나눠주면 교착 상태가 발생하는지 파악하고 그 수준 이하로 자원을 할당해주는 방식입니다. 이때 교착 상태가 발생하지 않는 범위를 안정 상태, 교착 상태가 발생하는 범위를 불안정 상태로 구분짓고 불안정 상태에 돌입하지 않게 관리합니다. 이때 불안정 상태의 범위는 최대한 비관적으로 예측하기에 만약 불안정 상태에 진입한다해도 교착 상태가 발생하지 않을 수도 있습니다. 검출/회복은 교착 상태를 검출하고 회복하여 교착상태에서 빠져나오는 방식입니다. 먼저 검출은 일정 시간동안 작업이 진행되지 않는 프로세스를 교착 상태에 빠졌다고 판단하는 타임아웃, 비차단 프로세스를 하나씩 지워보며 일부 엣지가 남으면 교착상태라고 판단하는 자원 할당 그래프 방식으로 교착 상태를 판단하고 이후 교착 상태를 일으킨 프로세스를 동시에 종료시키거나 우선 순위를 고려해 희생자를 선정해 희생자의 자원을 전부 회수해 다시 작업이 원활히 흐르도록 하는 방식입니다.

[JM-220]

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

교착상태란, 서로다른 프로세스가 자원을 각자 선점하여, 결국 프로세스 진행이 멈추는 상태를 의미한다. 기아상태는 프로세스가 후순위로 밀려 처리가 늦어지는 문제로, 기아상태가 지연의 문제라면 교착상태는 정지의 문제이다. 교착상태가 더 심각한 문제라고 볼 수 있다. 물론 프로세스 자원할당에 따라 기아상태도 무기한 연기될 수 있다. 다만 교착은 외부 개입 없이는 그냥 자원만 먹고 stop 되기 때문에 더 위험한 놈임.

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

교착상태가 발생하기 위해서는 네가지 필수조건을 모두 만족해야 하며, 한가지라도 만족하지 않을 시 교착상태가 발생하지 않는다.

1. 상호배제 : 하나의 자원은 동일 시간상에서 하나의 프로세스만이 사용이 가능하다. 동시 사용이 불가함
2. 점유대기 : 프로세스가 최소 하나의 자원을 보유한 상태에서 다른 프로세스에 할당된 자원을 기다리고 있는 경우가 있어야 함
3. 비선점 : 다른 프로세스가 가지고 있는 자원을 빼앗을 수 없음.
4. 원형대기 : 프로세스들이 서로가 가진 자원을 요구하며 원형으로 순환하는 형태를 가져야 함.

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

1. 예방 : 가장 엄격한 방식. 교착 상태가 발생하기 위한 조건 중 최소 한개 이상을 막아 교착 상태를 원천차단함. 필수 조건이 4가지이므로 예방 방식에도 크게 보면 4가지가 있다. 각 방식이 발생하지 않도록 하는 것이다. 다만 상호배제의 경우 구현이 어려운데. (예를들어, 프린터같은 장치를 두 프로세스가 동시 사용하면 말이 안되니까..) 다른 조건을 해결해서 예방이 가능함.
2. 회피 : 예방보다는 유도리가 있다. 교착 상태가 발생할 수 있는 가능성을 인정하고 교착상태가 될 것 같으면 자원 할당을 안해버리는 방식으로 구현한다. 은행원 알고리즘(안정 상태, 불안정 상태를 따져 할당)이 이에 해당한다. 다만 문제는 회피 방식은 특정 프로세스가 미래에 사용할 자원까지 전부 파악하고 있어햐 한다는 점이다.
3. 검출/회복 : 회피보다 유도리가 생겼다. 교착 상태가 발생할 수 있는 가능성도 인정하고 발생해도 된다. 다만 운영체제가 해당 교착상태를 인지하면 그때 회복과정을 거친다. 교착 상태가 발생하면 원인 프로세스를 강제 종료시켜 자원을 회수한다던가. 그런 방식이 있다. 데이터베이스에서 교착이 발생해 롤백 시키는 것을 예시로 들 수 있겠다.

[paiwhy]

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

교착 상태란 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고있는 자원을 요구해 계속 기다리는 현상을 말합니다
프로세스가 자원을 얻지 못해 다음 처리를 못하는 상태의 교착 상태인 반면 기아 상태는 프로세스가 원하는 자원을 계속 할당 받지 못하는 상태이다.

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

• 상호배제 (Mutual Exclusion) : 한번에 한개의 프로세스만이 공유자원을 사용할 수 있다
• 점유와 대기 (Hold and Wait) : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기위해 대기하는 프로세스가 있어야 한다
• 비선점 (Non-preemption) : 다른 프로세스에 할당된 자원은 사용이 끝날때까지 강제로 뺏을 수 없어야한다
• 순형대기 (Circular Wait) : 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되고 자신에게 할당된 자원을 점유하면서 앞뒤에있는 프로세스의 자원 요구해야함

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

예방
교착 상태 예방 방법은 4가지의 조건중 하나 이상을 부정해 방지할 수 있다
상호배제 부정: 읽기 전용 파일과 같은 공유 자원 사용
점유 및 대기부정: 프로세스 대기를 없애기 위해 실행되기 전에 모든 자원을 할당
비선점 부정: 모든 자원에 대한 선점 허용
원형대기 부정: 자원에 고유한 번호 할당, 순차적 자원 요구

회피
교착 상태 회피는 교착 상태가 발생하기 전에 교착 상태를 예상해 안전한 자원에서만 자원요청을 허용함 → 자원을 신중하게 할당하는게 중요
프로세스 수, 자원의 종류와 수가 고정되야하고 프로세스의 요구 자원수와 최대 자원수를 파악해야하고 프로세스가 자원을 사용후 반납해야한다

검출/회복
교착 상태 예방과 회피와 달리 검출 후 회복 방법은 교착 상태가 발생하는 것을 인정
사후 조치를 통해 조치를 통해 교착 상태를 해결합니다.