교착 상태(DeadLock).md

교착 상태(DeadLock)

두 개 이상의 프로세스나 스레드가 서로 자원을 기다리면서 무한히 기다리게 되는 상태

교착 상태는 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에, 다음 단계로 진행하지 못하는 상태이다.

프로세스A와 B가 디스크(자원1),프린터(자원2)를 모두 얻어야 한다고 가정해보자

t1 : 프로세스A이 디스크를 얻음 / 프로세스B가 프린터를 얻음

t2 : 프로세스A은 프린터를 기다림 / 프로세스B는 디스크를 기다림

현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠짐

→ 이것이 바로 DeadLock!!!!!!

자원(Resource) :

하드웨어 자원 → 기억장치, 프로세서, 하드 디스크, 자기 테이프, 단말기, 모니터, 키보드 등

소프트웨어 자원 → 메시지, 시그널(signal), 파일, 각종 공유 소프트웨어 등

실제 시스템에서의 교착 상태

MySQL에서의 '상호 거래 패턴'

Member 테이블에 name, point라는 컬럼이 있고, 두 개의 트랜잭션으로 point에 접근한다고 가정한다. 처음 두 개의 트랜잭션이 동시에 수행되어 트랜잭션1은 name이 A인 point에 접근해서 lock을 걸고 트랜잭션2은 name이 B인 point에 접근해서 lock을 건다.

이 후, 트랜잭션1이 name이 B인 point에 접근하려고 하면 이미 점유되어 있는 상태이므로 접근이 불가하고 트랜잭션2도 마찬가지로 name이 A인 point에 접근하지 못해 교착상태가 발생한다.

교착 상태의 4 가지 필요 조건

4가지 모두 성립해야 데드락 발생

1. 상호 배제 조건(Mutual Exclusion condition) : 자원은 한 번에 한 프로세스만 사용

2. 점유와 대기 조건(Hold and Wait condition) : 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기

3. 비선점 조건(Non preemptive condition) : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음

4. 순환 대기 조건(Circle wait condition) : 점유와 대기 형태로 순환사이클에 갇혀있는 상태

교착 상태 해결 방법

예방, 회피, 탐지 및 복구, 무시방법이 있다.

1. 교착 상태 예방(Prevention) : 교착 상태 발생 조건 중 하나를 제거하면서 해결한다.

   자원가 낭비 엄청 심하고 현대엔 사용하지 않는다.

• 상호배제 부정 : 여러 프로세스가 공유 자원 사용
• 점유대기 부정 : 프로세스 실행 전 모든 자원을 할당
• 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
• 순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구

2. 교착상태 회피(Avoidance) : 교착상태를 피하는 것.

   은행원 알고리즘(Banker's Algorithm)

• 시스템을 안정 상태 / 불안정 상태로 구분
• 안정 상태면 자원 할당, 불안정 상태면 요청을 대기시킨다
• 알고리즘을 사용하려면 할당할 자원 수 고정, 프로세스 수 고정, 제한된 시간 안에 자원 반납 등 많은 조건 필요 → 자원이 동적으로 할당되는 현대시스템에서는 사용 불가
• 자원을 요청할 때마다 회피 알고리즘을 돌려야 하기 때문에 오버헤드가 심해짐 → 이를 감당할 시스템이 거의 없음

3. 교착 상태 탐지 및 복구(Detection, Recovery) : 교착 상태가 자주 발생하는 시스템에서 일반적으로 사용하는 방법

   탐지 및 복구는 교착상태가 발생할 것 같을 때 사용되기 때문에 교착상태를 해결하기 위해서 예방과 회피를 사용하지 않고 주로 오베헤드가 적은 탐지와 복구를 사용한다.

• 교착 상태 탐지 : 교착 상태 존재 여부 및 교착 상태에 연관된 프로세스와 자원을 알아낸다. 순환 대기 존재 여부에 초점을 맞춰 탐지한다.

  • 자원할당 그래프 소거 알고리즘

    

    프로세스와 자원 간의 관계를 그래프로 나타내고 자원 노드와 자원노드로 향하는 화살표를 전부 제거해서 프로세스들의 수를 알아낸다.

    탐지 알고리즘도 오버헤드가 발생하기 때문에 얼마나 자주 탐지하느냐가 중요 → 주기적으로(3일에 한 번, 1달에 한 번), 자원 즉시 할당 여부, CPU 이용률(교착상태 발생 시 프로세스의 CPU 이용률이 떨어지는데 그에 따른 기준을 설정)

    
    

• 교착 상태 복구 : 순환 대기를 깨서 교착 상태로부터 회복

  프로세스가 작업 중이던 것을 일부 손실할 수 있다.

  • 순환 대기가 깨질 때까지 프로세스 종료

  • 순환 대기에 포함된 프로세스의 제어권을 뺏고 롤백

    대상 프로세스는? 시스템마다 기준이 다르다 (남은 수행시간, 자원 유형의 수 등등)

    예) MySQL의 경우,

    • 트랜잭션 타임아웃 시 교착 상태든 아니든 가장 작은 트랜잭션 롤백
    • 트랜잭션 크기는 삽입(INSERT), 업데이트(UPDATE) 또는 삭제(DELETE)된 행 수에 의해 결정

4. 교착 상태 무시 : 교착 상태가 드물게 발생하는 시스템에서 일반적으로 사용하는 방법

   교착 상태가 드물게 발생하는데 이를 해결하는 비용을 지불한다면 비효율적이므로 교착상태가 발생하지 않는다는 가정 아래 무시한다. 교착상태를 해결하는 방법으로는 사용자가 프로세스를 죽이거나 시스템을 재부팅한다.

   예) 윈도우, 유닉스

   

Q. 면접 질문

데드락(교착 상태)가 뭔가요? 발생 조건에 대해 말해보세요.

두 개 이상의 프로세스나 스레드가 서로 자원을 기다리면서 무한히 기다리게 되는 상태입니다.

발생 조건 = 교착상태 4가지 필요조건

교착 상태의 4가지 필요 조건은 무엇입니까?

자원은 한 번에 한 프로세스만 사용할 수 있다는 상호 배제, 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 상태인 점유와 대기, 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없는 비선점, 점유와 대기 형태로 순환사이클에 갇혀있는 상태인 순환대기가 있습니다.

회피 기법인 은행원 알고리즘(Banker's Algorithm)이 뭔가요?

시스템을 안정 상태와 불안정 상태로 구분하고 안정 상태면 자원 할당, 불안정 상태면 요청을 대기시킨다. 알고리즘을 사용하려면 많은 조건 필요하기 때문에 자원이 동적으로 할당되는 현대시스템에서는 사용하지 않으며 자원을 요청할 때마다 회피 알고리즘을 돌려야 하기 때문에 오버헤드가 심해진다.