교착상태 (데드락)

[JoisFe]

교착상태(데드락)란 무엇이며, 교착상태가 발생하는 조건을 설명해주세요.

• 데드락
  • Deadlock 이 동작하기 위한 4가지 조건에 대해 설명해 주세요.
  • 그렇다면 3가지만 충족하면 왜 Deadlock 이 발생하지 않을까요?
  • 어떤 방식으로 예방할 수 있을까요?
  • 왜 현대 OS는 Deadlock을 처리하지 않을까요?
  • Wait Free와 Lock Free를 비교해 주세요.

[JoisFe]

데드락 (교착상태)

• 둘 이상 thread가 각자 다른 thread가 점유한 resource를 기다리는 상황에서 무한하게 대기하는 상태에 빠지는 상황입니다.

Q) Deadlock 이 동작하기 위한 4가지 조건에 대해 설명해 주세요.

1. Mutual Exclusion (상호 배제)

• 어떤 thread가 자원을 점유하고 있을때 다른 thread가 해당 자원을 동시에 점유할 수 없는 상황입니다.
• 동시에 한 thread 만이 자원을 점유할 수 있습니다.
  • 어떤 thread가 점유한 자원을 사용하기 위해 해당 thread가 자원을 반납하기 전까지 대기해야합니다.

2. Hold and Wait (점유 대기)

• thread가 어떤 자원을 보유한 상태에서 다른 thread가 점유한 자원을 얻기 위해 대기하고 있는 상황 입니다.

3. Non Preemption (비선점)

• 어떤 thread가 점유하고 있는 자원을 다른 thread가 강제로 선점 할 수 없는 상황입니다.

4. Circular Wait (순환 대기)

• 다른 thread의 자원을 점유하기위해 대기 중인 thread들이 순환 형태로 대기하고 있는 상황입니다.
  • a thread가 자원을 선점 중
  • b thread는 a가 가진 자원을 점유하기 위해 대기
  • c thread는 b가 선점한 자원을 점유하기 위해 대기
  • a thread는 c가 선점한 자원을 점유하기 위해 대기

Q) 그렇다면 3가지만 충족하면 왜 Deadlock 이 발생하지 않을까요?

• 모든 케이스별 상황을 나열하면

1. Mutual Exclusion 만을 충족하지 않은 경우

• 특정 자원을 여러 thread에서 점유하면 동시성 문제는 발생할 수 있으나, 자원이 필요할때 점유 (동시 점유) 해버리 면 되니 dead lock 이 발생할 수는 없음 (무한하게 대기하지는 않음)

2. Hold and Wait 만을 충족하지 않은 경우

• 자원을 얻기 위해 대기하고 있는 상황이 아니라는 것이 애초에 dead lock이 될 수 없음

3. Non Preemption 만을 만족하지 않은 경우

• 다른 thread가 차지하고 있는 자원이 필요할때 강제로 점유해버리면 되기 떄문에 대기 상태가 만들어지지 않음

4. Circular Wait 만을 만족하지 않은 경우

• 순환 참조를 하지 않는다는 것은 결국 하나의 thread는 다른 thread 자원을 점유하기위해 대기하고 있지 않기 떄문에 자신의 작업이 끝나고 자원을 반환하면 차례대로 각 쓰레드들이 자원을 점유할 수 있게 되며 무한 대기 상태에 빠지지 않을 수 있게 됩니다.

왜 현대 OS는 DeadLock을 처리하지 않을까요?

• Dead Lock을 해결하는 방법

1. Ignore (무시)

• dead lock이 발생해도 무시하는 방법입니다.

장점

• 따로 dead lock을 처리하기위한 비용이 들지 않기 때문에 시스템 성능 저하가 발생하지 않습니다.
• 단점도 존재하지만 이러한 장점으로 인해 대부분 Unix, Window OS등에서 사용하는 방법이라고 합니다.

단점

• deadlock이 발생하면 해결을 하지 못하기 때문에 process 종료 혹은 OS 재부팅 등을 통해 복구를 시킵니다.
• 따라서 dead lock 상태가 드물게 발생하지 않는 경우에 사용하는 것이 좋습니다.

2. Prevention (예방)

• dead lock 발생 조건 4가지 중 하나 이상 성립하지 않도록 하여 예방하는 방법입니다.

장점

• dead lock 이 발생하지 않도록 예방할 수 있습니다.

단점

• dead lock 발생 조건 중 하나 이상을 지키기위해 자원 사용의 효율성이 떨어지게 됩니다. 따라서 방법은 비용이 크게 발생합니다.

3. Avoidance (회피)

• thread가 앞으로 어떻게 자원을 요청할지 파악하여 Circular Wait이 발생하지 않도록 자원을 할당하는 방법입니다.
• Banker's Algorithm, Resource-Allocation Graph Algorithm 등을 통해 dead lock 회피

장점

• 시스템이 자원 할당 시점에 교착상태에 빠지지 않도록 자원을 할당하여 dead lock을 회피할 수 있습니다.
• Detection and Recovery에 비해 사전에 차단하므로 대응 속도가 빠릅니다.
• 자원 요청 시점에 체크하기 떄문에 불필요하게 자원을 낭비하거나 과도하게 제한하여 성능을 낮추지 않습니다.

단점

• 프로세스가 필요로하는 자원을 예측하기 어렵기 때문에 회피 방식의 구현이 어렵고 제한적입니다.
• 각 자원 요청에 마다 dead lock 발생 여부를 체크하기에 계산 비용이 상대적으로 많이 발생합니다.

4. Detection and Recovery (탐지와 복구)

• 시스템에서 dead lock 발생 탐지하고 이를 복구 시키는 방법입니다.

장점

• dead lock을 허용하기 떄문에 자원의 사용을 제한하지 않아 시스템이 자유롭게 동작할 수 있습니다.
• Prevention 보다 상대적으로 자원 활용도를 극대화 할 수 있습니다.
• Avoidance 와 달리 자원 요구량을 사전에 알 필요 없기 때문에 동적이거나 복잡한 환경에도 적용하기 편리합니다.

단점

• dead lock 탐지를 주기적으로 해야되기 때문에 비용이 많이 발생합니다.
• Ignore과 비슷하게 dead lock이 발생할 수 있는 점이 단점입니다.
• 복구 과정 중 프로세스 중단 or 롤백 경우 시스템 영향을 줄 수 있습니다.
• 복구 과정에서 데이터 손실이 일어날 수 있습니다.
• 프로세스간 자원이 얽혀있는 등 복잡한 상황에서 복구 과정이 복잡할 수 있습니다.

==>

• 최근 OS나 응용 프로그램이 잘 설계가 되어서 교착 상태가 잘 발생하지 않습니다.
• 따라서 굳이 dead lock을 막기 위해 Prevention, Avoidance 같은 방식을 택해 많은 비용을 낭비하기 보단
• 또는 Detection and Recovery 를 통해 dead lock 탐지와 복구에 비용을 낭비하기 보단
• 그냥 dead lock을 허용해주고 dead lock 발생 시 문제된 프로세스 종료나 OS reboot 방식을 통해 해결하는 것이 효율적이기 떄문에 최신 OS에서는 Ignore 방식을 사용합니다.

Q) Wait Free와 Lock Free를 비교해 주세요.

• Wait Free 는 Lock Free의 포함관계로써 모든 Wait Free는 Lock Free

Lock Free

• 여러 thread에서 동시 호출 시 정해진 단위 시간마다 적어도 하나의 호출이 완료되는 알고리즘
  • 즉 lock이 없어도 최소한 하나의 thread는 작업을 완료할 수 있음을 보장합니다.
• dead lock이 없는 안정성을 가집니다.
• Atomic Operation (원자적 연산) 활용하여 자원에 대한 동시 접근을 제어
  • Atomic Operation : 중간에 다른 thread가 개입할 수 없는 연산 --> 일관된 상태 유지

장점

1. dead lock 발생 X : lock을 사용하지 않기에 thread간 무한하게 대기하는 dead lock 발생하지 않음
2. lock 기반 방식과 달리 특정 thread가 자원을 점유하고 있어 다른 thread가 기다릴 필요 X

단점

1. thread가 작업을 완료하는데 걸리는 시간 보장 X
2. 일부 thread가 일시적으로 더 많은 자원 사용하여 다른 thread 작업을 방해할 수 있음
3. 알고리즘이 복잡하고, 알고리즘 정확성을 증명하기 어려움

Wait Free

• 모든 thread가 유한한 시간 내 작업 완료할 수 있는 것을 보장
  • 주로 Atomic Operation 통해 race condition 없이 자원에 안전하게 접근 가능
• lock free 보다 동시성 강력하게 보장함

장점

1. 무한 대기가 없음 (dead lock 없음) : 다른 thread 로 인해 한 thread가 무한하게 대기하지 않고 모든 thread가 공정하게 작업 완료 가능

• dead lock이 없는 것은 Lock Free와 동일 (당연히 모든 Wait Free는 Lock Free이기 때문에)

2. 예측 가능성이 높음 : 모든 thread가 일정한 시간 내에 작업을 완료 하므로 실시간 시스템에서 유리합니다.

단점

1. Lock Free에 비해 요구되는 조건이 엄격하기 때문에 구현이 복잡하고, 성능상 오버헤드 발생할 수 있습니다.

참고

1. https://chfhrqnfrhc.tistory.com/entry/Lockfree-VS-Waitfree
2. https://velog.io/@ryulkim/OS-lock-based-lock-free-wait-free

[Tokwasp]

❓ 교착상태(데드락)란 무엇이며, 교착상태가 발생하는 조건을 설명해주세요.

🌱 [ deadLock ] : 두개 이상의 프로세스가 자원을 점유한 채로 서로의 자원을 기다리며 무한정 기다리는 상태

ex)
작가 : 글을 쓰기 위해 노트를 가지고 있는 상태에서 볼펜을 원합니다.
학생 : 공부한 내용을 정리 하기 위해 볼펜을 가지고 있는 상태에서 노트를 원합니다.
-> 서로 점유한 것을 원하지만 줄수 없기 때문에 교착 상태 입니다.

[ 교착 상태 발생 조건 ]

[ 자원 관점 ]

• 상호 배제 : 동시에 사용할 수 없는 자원 입니다.
• 비선점 : 점유한 자원이 다른 프로세스가 선점 할수 없는 자원 입니다.

[ 프로세스 관점 ]

• 점유와 대기 : 자원을 점유한 채로 원하는 자원을 대기 하고 있는 상태 입니다.
• 순환 대기 : 자원을 점유하고 원하는 자원을 대기하는 모습이 원의 형태를 띄고 있습니다.

❓ 그렇다면 3가지만 충족하면 왜 Deadlock 이 발생하지 않을까요? / 어떤 방식으로 예방할 수 있을까요?

🌱 [ 교착상태 예방 ]

[ 상호 배제 발생 X ]

• 만약 동시에 사용할 수 있는 자원이라면 자원을 둘다 써도 되기 떄문에 데드락은 발생 하지 않습니다.

[ 상호 배제 - 예방법 ]

• 상호 배제를 예방 하려면 모든 자원을 동시에 사용 할수 있게 해야 합니다.
• CPU, 메모리 자원을 동시에 쓰게 할 수 있을까요? 사실상 불가능 합니다.

[ 비선점 발생 X ]

• 선점 할수 있는 자원이라면 상대의 자원을 선점하여 사용 하면 데드락은 발생 하지 않습니다.

[ 비선점 - 예방법 ]

• 모든 자원을 선점 하게 만들면 어떻게 될까요? 사실상 불가능 합니다.

[ 점유와 대기 발생 X ]

• 다른 프로세스가 자원을 모두 가지고 있다면 교착 상태는 발생 하지 않습니다.

[ 점유와 대기 - 예방법 ]

• 필요한 자원을 모두 할당 합니다.
• 필요 하지 않은 순간에도 가지고 있기 때문에 자원 낭비가 발생 합니다.

[ 순환 대기 발생 X ]

• 자원을 다 가지고 있다면 교착 상태가 발생 하지 않습니다.

[ 순환 대기 - 예방법 ]

• 자원에 순서를 부여해서 오름 차순으로만 자원 요청 가능
• 프로세스 1번 ( 1,2,3,4 필요 ) : 1 -> 2번 -> 3번 점유 -> 3번 자원은 사용을 다한 상태
• 프로세스 2번 ( 1, 3 필요 ) : 1번 프로세스가 점유 했기 때문에 대기 합니다.
  -> 2번 프로세스는 3번 자원을 사용하여 작업을 할수 있지만 점유 하지 못합니다.

정리 : 교착 상태를 예방 하려면 심각한 자원 낭비가 발생 합니다.

🌱 [ 교착상태 회피 ]

• 전제 : 프로세스가 요구하는 자원의 종류와 수량을 알고 있어야 합니다. -> 비현실적

[ 회피 알고리즘 - 다익스트라 banker's ]

• 간단하게 한 종류의 자원을 여러개 가지고 있을때 시스템을 safe state로 유지 하는 방법
  

[ 회피 알고리즘2 - Habermann’s algorithm ]

• 다익스트라 방법과 같으나 자원이 여러개인 경우

정리 : 데드락의 발생은 막을수 있으나 항상 시스템을 감시 하고 있어야 하고, 필요한 자원의 종류 수를 알고 있어야 합니다.

❓ 왜 현대 OS는 Deadlock을 처리하지 않을까요?

• 데드락을 예방, 회피, 감지 하는것은 시스템의 부하를 유발 하고 자주 발생 하지 않기 때문에

❓ Wait Free와 Lock Free를 비교해 주세요.

락 기법의 한계 : 서로 필요한 자원의 락을 잡고 있으면 교착 상태가 발생 할 수 있습니다.

[ Lock-Free ] : 락 없이 최소한 하나의 스레드는 작업을 완료 할수 있는 기법

• 원자적 연산을 활용 하여 동시 접근 제어

[ Wait - Free ] : 모든 스레드가 유한 시간안에 작업 완료를 보장 하는 알고리즘

출처 : https://www.youtube.com/watch?v=wdaf2gy83uU 한기대 교수님 강의

[dy102]

• 교착상태(데드락)란 무엇이며, 교착상태가 발생하는 조건을 설명해주세요.

  교착 상태

  일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상.

  Deadlock은 두 개 이상의 프로세스가 서로 자원을 기다리며 무한히 대기하는 상태를 의미한다.

  교착 상태가 발생할 조건에는 네 가지가 있다. 아래 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 아래 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생긴다.

  발생 조건

  • 상호 배제
    • 교착 상태가 발생한 근본적인 원인은 해당 자원을 한 번에 하나의 프로세스만 이용 가능했기 때문이다. 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때, 즉 상호 배제 상황에서 교착 상태가 발생할 수 있다.
  • 점유와 대기
    • 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
  • 비선점
    • 비선점 자원은 그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있다. 즉, 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못했기 때문에 교착 상태가 발생
  • 원형 대기
    • 프로세스들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이루면 교착 상태가 발생할 수 있다. 이렇게 프로세스들이 원의 형태로 자원을 대기하는 것을 원형 대기라고 한다.

• 데드락

  • 그렇다면 3가지만 충족하면 왜 Deadlock 이 발생하지 않을까요?

    교착 상태가 발생하기 위해서는 4가지 조건을 모두 충족해야 한다. 하나라도 깨지면 교착 상태가 발생하지 않는다. 자세한 내용은 예방 방법에서 확인하자.

  • 어떤 방식으로 예방할 수 있을까요?

    운영체제가 교착 상태를 해결하는 방법에는 크게 세 가지가 있다

    교착 상태를 예방

    교착 상태를 예방하는 방법은 교착 상태 발생 필요 조건 네 가지 중 하나를 충족하지 못하게 하는 것이다. 즉, 프로세스들에 자원을 할당할 때 상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나의 조건이라도 만족시키지 않게 할당하면 교착 상태는 발생하지 않는다.

    상호 배제 제거

    자원의 상호 배제를 없앤다 = 모든 자원을 공유 가능하게 만든다.

    • 현실에서 사용하기에는 다소 무리가 있는 방식.

    점유와 대기 제거

    점유와 대기를 없애면 운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다.

    • 자원의 활용률이 낮아짐
      • 당장 자원이 필요해도 기다릴 수 밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하게 됨.
      • 많은 자원을 사용하는 프로세스는 적은 자원을 사용하는 프로세스에 비해 동시에 자원을 사용할 타이밍을 확보하기가 어려워, 많은 자원을 사용하는 프로세스가 무한정 기다리게 되는 기아 현상을 야기할 우려가 있다.

    비선점 제거

    비선점 조건을 없애면 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있다.

    • 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적임.(ex. CPU)
    • 범용성 저하
      • 모든 자원이 선점 가능한 것이 아니기 때문에, 범용성이 떨어지는 방식(ex. 프린터)

    원형 대기 제거

    모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않음.

    • 특정 자원의 활용률 저하
      • 각 자원에 어떤 번호를 붙이는지에 따라 특정 자원의 활용률이 떨어질 수 있다.
    • 복잡성
      • 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 일을 그리 간단한 작업이 아니다.

    교착 상태를 회피

    교착 상태가 발생하지 않을 정도로만 조금씩 자원을 할당하는 방식

    • 교착 상태 회피 방식에서는 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주한다.

    프로세스들에게 할당할 수 있는 자원이 충분한 상황에서 프로세스들이 한두 개의 적은 자원만을 요구한다면 교착 상태는 발생하지 않는다. 반면 프로세스들에 할당할 수 있는 자원이 한정된 상황에서 모든 프로세스들이 한 번에 많은 자원을 요구하면 교착 상태가 발생할 위험이 증가한다.

    

    안전 순서열

    교착 상태 없이 안전하게 프로세스들에게 자원을 할당할 수 있는 순서. 안전 순서열이 있는 상태를 안전 상태라고 볼 수 있다.

    안전 상태

    교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태. 안전 순서열대로 프로세스들에게 자원을 배분하여 교착 상태가 발생하지 않는 상태.

    불안전 상태

    교착 상태가 발생할 수도 있는 상황. 안전 순서열이 없는 상황이다.

    안전 순서열 방식의 단점

    • 계산 비용 증가
      • 특히 자원의 종류와 프로세스 수가 많아질수록 계산량이 크게 늘어남.
    • 미리 자원 요구량을 알아야 함
      • 각 프로세스가 실행 중 필요한 최대 자원 요구량(Maximum Need)을 사전에 제공해야 하므로, 정확한 추정이 어려운 동적 환경에서는 적용이 어렵다.
    • 실시간 처리 불가능
      • 실시간으로 요청이 발생하는 경우, 안전 순서열 계산 시간이 큰 병목이 될 수 있음.

    교착 상태를 검출 후 회복

    교착 상태 발생을 인정하고 사후에 조치하는 방식

    • 교착 상태 발생 여부를 주기적으로 검사한다.

    선점을 통한 회복

    교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식.

    교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당한다.

    프로세스 강제 종료를 통한 회복

    두 가지 방법이 존재

    1. 교착 상태에 놓인 프로세스를 모두 강제로 종료
       • 한 번에 교착 상태를 해결할 수 있는 가장 확실한 방식이지만 그만큼 많은 프로세스들이 작업 내역을 잃게 될 가능성이 있다.
    2. 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료
       • 작업 내역을 잃는 프로세스는 최대한 줄일 수 있지만 교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드를 야기한다.

    타조 알고리즘
    : 드물게 발생하는 잠재적 문제(교착 상태)를 무시로 대처하는 방식.
    문제 발생의 빈도나 심각성에 따라 최대 효율을 추구하는 엔지니어 입장에서는 때때로 이 방식이 적합할 때도 많다.

  • 왜 현대 OS는 Deadlock을 처리하지 않을까요?

    교착 상태 무시 (대부분의 현대 OS)

    • 대부분의 현대 운영체제는 교착 상태를 발생 가능성이 낮은 희소 사건으로 간주하고 무시한다.
    • 교착 상태가 발생하면 이를 탐지 후 강제 종료로 해결.
    • 이유:
      • 교착 상태를 탐지하고 해결하기 위한 오버헤드가 지나치게 높음.
      • 교착 상태가 실제로 발생하는 빈도가 낮음.

    교착 상태를 완전히 예방하기 보다는 교착 상태가 발생할 확률이 낮은 알고리즘을 사용한다.

  • Wait Free와 Lock Free를 비교해 주세요.

    락 기반 알고리즘의 단점

    Lock을 확보하지 못한 스레드는 실행되지 못하고 Lock을 획득한 스레드가 Lock을 반환할 때까지 대기 상태에 머물러야 하며 조건이 충족 될 때 다시 실행시켜야 한다. Lock을 획득하더라도 실제 CPU를 할당받기 전에 이미 CPU를 사용하고 있는 다른 스레드가 CPU 할당량을 모두 사용하고 CPU 자원을 넘겨줄 때까지 대기해야 한다.

    Lock에 대한 경쟁이 심해질수록 실제로 필요한 작업을 처리하는 시간 대비 동기화 작업에 대한 시간의 비율이 높아지면서 성능이 떨어지게 된다.

    Non-blocking 알고리즘

    공유 자원에 대한 동시 접근에서 스레드가 서로를 기다리지 않고 독립적으로 진행할 수 있도록 설계된 알고리즘. 락을 사용하지 않고도 동기화를 달성하며, 시스템의 병목현상을 줄이고 성능을 향상시킬 수 있다.

    Lock-Free

    최소 하나의 스레드는 작업을 완료함을 보장

    • 교착 상태가 발생하지 않음
    • 호출이 다른 스레드와 충돌하였을 경우, 적어도 하나의 승자가 있으며 그 승자 스레드는 딜레이 없이 완료됨

    do
    {
    tempTop = m_currentTop;
    newTop = tempTop->next;
    }
    while ( CAS(m_currentTop, tempTop, newTop));

    → 다른 스레드가 게속 방해한다면 기아상태 스레드가 발생할 것임.

    Wait-Free

    모든 스레드가 한정된 시간 내에 작업을 완료함을 보장

    • 성능과 구현이 매우 어렵지만, 가장 강력한 비차단 방식
    • 스레드 우선순위 조정
      • Wait-free 알고리즘은 각 스레드가 자원을 얻을 수 있는 기회를 공평하게 제공하며, 하나의 스레드가 계속 자원을 차지하지 않도록 한다. 예를 들어, 시간이 지나면서 기다리고 있는 스레드에게 우선순위를 주는 방식으로 기아를 방지할 수 있다.

    결론적으로, Wait-free 알고리즘은 Lock-free와 달리 특정 스레드가 기아 상태에 빠지지 않도록 보장하는 추가적인 특성을 가지고 있다.

    CAS(Compare-And-Swap)

    • 원리: 메모리의 특정 값을 비교하고, 예상된 값과 같으면 새로운 값으로 교체.

    • 장점: 락 없이도 경쟁 상태에서 안전하게 값을 갱신 가능.

    • 예제:

      public class AtomicTest {
      
          public static void main(String... args) {
              AtomicInteger atomic = new AtomicInteger(0);
              int value = 0;
              int update = 1;
              
              while(!atomic.compareAndSet(value, update)) {
                   System.out.println("CAS 실패, 재시도...");
              }
              
              System.out.println(atomic.get());
          }
      }

    논블로킹 알고리즘의 장점

    1. 교착 상태 없음
       1. 락을 사용하지 않기 때문에 교착 상태가 발생하지 않음
    2. 높은 성능
       1. 스레드 간 대기를 제거해 높은 병렬성과 자원 활용도를 제공함
    3. 향상된 시스템 성능
       1. 하나의 스레드가 실패해도 다른 스레드의 진행에 영향을 주지 않음
    4. 컨텍스트 스위칭 감소
       1. 락을 사용할 때 발생하는 컨텍스트 스위칭이 감소

    단점

    1. 복잡성
    2. CAS 실패 시 성능 저하
       1. 경쟁이 심한 환경에서는 CAS 실패로 인해 성능이 저하될 수 있음
    3. 한정된 문제에 적합
       1. 데이터 구조의 크기나 유형이 제한적일 수 있음

• 임계 영역이란?

  임계 영역

  : 공유 자원에 접근하는 코드 중 동시에 실행하면 문제가 발생하는 코드 영역.

  • 두 개 이상의 프로세스가 임계 영역에 진입하고자 하면 둘 중 하나는 대기해야 한다.

  경쟁 상태

  잘못된 실행으로 인해 여러 프로세스가 동시 다발적으로 임계 영역의 코드를 실행하여 문제가 발생한 상태.

  • 데이터의 일관성이 깨짐

  고급 언어로 한 줄로 작성할 수 있는 코드는 컴퓨터 내부에서 여러 줄의 저급 언어로 변환되어 실행된다. 이러한 저급 언어 여러 줄을 실행하는 과정에서 문맥 교환이 일어날 수 있다.

[jay200333]

Deadlock이 동작하기 위한 4가지 조건에 대해 설명해주세요.

✅ 답변

1. 상호 배제

• 해당 자원을 한 번에 하나의 프로세스만 이용 가능하기에 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때 교착 상태가 발생할 수 있다.

2. 점유와 대기

• 어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리게되면 교착 상태가 발생할 수 있다.

3. 비선점

• 비선점 자원 은 자원을 이용하는 프로세스의 작업이 끝나야만 이용할 수 있기 때문에 교착 상태가 발생할 수 있다.

4. 원형 대기

• 프로세스가 요청 및 할당받은 자원이 원의 형태를 이루게 되면 교착 상태가 발생할 수 있다.

---

그렇다면 3가지만 충족하면 왜 Deadlock이 발생하지 않을까요?

✅ 답변
Deadlock 발생에 필요한 조건이 4가지 중 하나인 "순환 대기(Circular Wait)" 조건이 포함되어 있기 때문이다. 순환 대기 예를 들어,

1. 상호 배제 조건이 없으면 두 개 이상의 프로세스가 동시에 자원을 사용할 수 있으므로, 대기할 필요가 없어짐
2. 점유 및 대기 조건이 없으면 자원을 요청한 프로세스는 해당 자원을 할당받지 못하고 바로 실패하게 되므로 대기X
3. 비선점 조건이 없으면 다른 프로세스가 자원을 강제로 해제할 수 있으므로, 프로세스들이 서로 계속해서 자원을 해제하고 점유할 수 있게 됨

따라서, 세 가지 조건만 충족된다면 순환 대기 조건이 없어서 Deadlock이 발생하지 않으며, 순환 대기 조건이 포함된 경우 4가지 조건이 모두 충족되어야 Deadlock이 발생합니다.

---

어떤 방식으로 예방할 수 있을까요?

✅ 답변
교착 상태 발생 조건에 부합하지 않게 자원을 분배

• 상호 배제 조건 제외

  • 모든 자원을 공유 가능하게 만들기

  → 이론적으로는 교착 상태를 없앨 수 있지만, 현실적으로 무리가 있음

  → 동기화 문제가 발생할 수 있음

• 점유 와 대기 조건 제외

  • 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분

  → 자원의 활용률이 낮아질 수 있음

  → 많은 자원을 사용하는 프로세스가 불리해 동시에 자원을 사용할 타이밍을 확보하기 어려운 프로세스가 생기고 결국 기아 현상 이 발생할 수 있음

• 비선점 조건 제외

  • 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있음

  → 프로세스가 할당받을 수 없는 자원을 요청하는 경우, 기존에 가지고 있던 자원을 모두 반납하고 새 자원과 이전 자원을 얻기 위해 대기하도록 합니다. (자원 낭비 발생 )

• 원형 대기 조건 제외

  • 일정하게 한 쪽 방향으로만 자원을 요구할 수 있도록 하기
  • 모든 자원에 번호 붙이기

  → 원형 대기를 없앰으로써 비교적 실용적인 방식

  → 특정 자원의 활용률이 떨어질 수 있음

---

왜 현대 OS는 Deadlock을 처리하지 않을까요?

✅ 답변

1. 빈번히 발생하는 이벤트가 아니기 때문에 미연에 방지하기 위해 훨씬 더 많은 오버헤드를 들이는것이 비효율적이라고 판단
2. 현대 시스템의 복잡성으로 인해 교착 상태를 완전히 방지하는 것은 불가능
3. 만약 시스템에서 deadlock이 발생한 경우 시스템이 비정상적으로 작동한것을 사람이 느낀후 직접접 process를 죽이는 방법으로 대처

---

Wait Free와 Lock Free를 비교해 주세요

✅ 답변
Wait-free와 Lock-free는 모두 멀티스레딩 환경에서 공유 자원에 대한 동시 접근을 처리하는 기술

Wait-free는 모든 스레드가 동시에 진행될 수 있는 것에 비해,

Lock-free는 일부 스레드가 블로킹될 가능성이 있지만, 구현이 더 쉽고 성능이 높은 경우가 많음.

	Wait-free	Lock-free
공통점	1. 스레드가 락을 획득하거나 해제하는 데 소비되는 시간이 줄어듭니다. 2. 락 경쟁으로 인한 병목 현상이 줄어들어 여러 스레드가 효율적으로 동시에 실행될 수 있습니다. 3. 무한 대기 상황을 방지함으로써 데드락과 라이브락 문제를 해결
설명	모든 스레드가 동시에 진행되고, 하나의 스레드가 멈추더라도 다른 스레드는 계속 진행될 수 있도록 구현	항상 하나 이상의 스레드가 진행할 수 있음이 보장
특징	Wait-free에서는 어떤 스레드도 블로킹(blocking) 되지 않음	공유 자원에 대한 동시 접근을 처리하기 위해 락(lock)을 사용하지 않고, 원자적(atomic) 연산을 사용
단점	1. Wait-free는 복잡하고 구현하기 어려운 경우가 많아서 일반적으로 사용되기 어려움 2. Lock-Free보다 더 많은 오버헤드가 발생할 수 있음	일부 스레드가 블로킹될 가능성이 있으므로, 높은 지연시간을 보일 수 있음
장점	모든 스레드가 한정된 시간 내에 진행할 수 있는 것을 보장	1. 구현하기 쉽고, 항상 하나 이상의 스레드가 진행할 수 있음이 보장 2. 스레드 간 상호작용 없이 공유 자원을 안전하게 사용할 수 있도록 보장

---

임계 영역이란?

✅ 답변
공유 되는 자원에서 동시 접근하지 않게 독점을 보장해줘야 하는 영역

• 임계 영역은 지정된 시간이 지난 후 종료된다. 어떤 프로세스(스레드)가 임계 영역에 들어가고자 하면 지정된 시간만큼 대기해야 함