Deadlock

Deadlock에 대해 설명해 주세요.

데드락은 여러 프로세스가 서로 자원을 기다리며 무한히 대기 상태에 빠지는 상황을 의미하며, 데드락이 발생하기 위해서는 네 가지 필수 조건이 필요하다.

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

상호 배제 (Mutual Exclusion)

자원은 동시에 하나의 프로세스만 사용할 수 있다. 즉 자원이 이미 다른 프로세스에서 사용 중인 경우 다른 프로세스는 그 자원이 해제될 때까지 기다려야 한다.

점유 대기 (Hold and Wait)

이미 자원을 점유하고 있는 프로세스가 다른 자원을 추가로 요청할 때, 해당 자원이 해제될 때까지 그 자원을 기다린다. 즉 자원을 점유한 상태에서 추가 자원을 요청하는 상황이 발생한다.

예를 들어 프로세스 A가 자원 X를 점유하고 있는데 Y까지 요구할 때, Y는 B가 점유하고 있는 경우이다. 이때는 B가 Y를 놓아 주기 전까지 A가 Y를 점유할 수 없다.

비선점 (No Preemption)

다른 프로세스가 점유하고 있는 자원을 강제로 뺴앗을 수 없다. 자원은 자원을 점유하고 있는 프로세스가 자발적으로 해제할 때까지 기다려야 한다.

순환 대기 (Circular Wait)

데드락이 발생하는 프로세스들이 자원 대기 형태로 원형을 이루는 경우이다.

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

점유 대기 (Hold and Wait)

자원을 여러 프로세스가 동시에 사용할 수 있으므로 자원 사용 때문에 프로세스가 대기할 이유가 없다.

점유 대기 (Hold and Wait)

프로세스가 자원을 점유한 상태에서 다른 자원을 요청할 수 없으면 자원을 점유한 프로세스가 대기에 들어갈 일도 없다. 이미 잘 구르고 있기 때문이다.

비선점 (No Preemption)

다른 프로세스가 점유하고 있는 자원을 강제로 뺴앗아 실행하면 되기 때문이다.

순환 대기 (Circular Wait)

순환이 발생하지 않으면 모든 프로세스가 자원을 얻기 위한 대기열에 들어갈 일이 없다.

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

상호 배제 (Mutual Exclusion)

가능한 경우 자원을 공유하여 여러 프로세스가 동시에 사용할 수 있도록 한다.

점유 대기 (Hold and Wait)

프로세스가 시작될 때 필요한 모든 자원을 한 번에 할당받도록 한다. 만약 중간에 추가적인 자원이 필요한 경우 점유하고 있는 모든 자원을 해제한 후 다시 요청하도록 한다.

비선점 (No Preemption)

자원을점유하고 있는 프로세스가 추가적인 자원을 요청할 때, 바로 자원을 할당할 수 없으면 점유하고 있는 모든 자원을 해제한 후 재요청하게 한다.

순환 대기 (Circular Wait)

모든 자원 유형에 일관된 순서를 부여하고 프로세스가 자원을 요청할 때 정해진 순서대로 요청하게 하여 자원 순서를 강제한다.

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

교착 상태를 무시하는 것이 다른 처리 방법과 비교해 비용이 적게 들기 때문이다. 많은 시스템에서 교착 상태는 드물게 발생하기 때문에 처리하는 비용이 그만한 가치를 가지지 않는다.

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

Wait Free와 Lock Free는 둘 다 병렬 프로그래밍에서의 동기화 매커니즘으로 사용되며, 둘 다 동시성을 관리하면서 데드락이나 기아 현상의 문제를 방지하기 위해 고안되었다.

Lock Free

• 여러 스레드가 공유 자원에 접근할 수 있으며, 어떤 스레드도 다른 스레드로 인해 무한히 대기하지 않게 하는 알고리즘이다.
• 하나의 스레드가 실패하거나 지연되더라도, 다른 스레드는 계속해서 진행할 수 있다.

Wait Free

• Lock Free의 한 형태로 모든 스레드가 제한된 수의 단계 안에 작업을 완료할 수 있음을 보장하는 알고리즘이다.
• 시스템 전체의 처리량을 보장하며 모든 스레드가 진행될 수 있도록 한다.

특성	Wait Free	Lock Free
진행 보장	모든 스레드가 제한된 시간 내에 작업을 완료함	최소 한 스레드가 계속해서 작업을 진행함
복잡성	구현이 매우 복잡하고 성능이 낮을 수 있음	구현이 비교적 간단하고 성능이 좋을 수 있음
기아 방지	모든 스레드가 기아 상태에 빠지지 않음	일부 스레드가 기아 상태에 빠질 수 있음
사용 사례	실시간 시스템, 극단적인 고성능 요구 시스템	일반적인 병렬 프로그램, 성능이 중요한 응용 프로그램
데드락 방지	데드락을 방지함	데드락을 방지함