[Lecture 11] 멀티쓰레딩 V - Deadlock

#Deadlock

데드락, 즉 교착상태란 2개 이상의 배타적인 자원을 2개 이상의 프로세서 또는 태스크가 부분적으로 각각 점유하고자 함에 따라 일어나는 상태이며 그것 이상 어느 쪽도 진행되지 않는 상태를 말한다. 그림은 태스크 A가 파일 A를 점유하여 파일 B의 점유해제를 기다리거나 태스크 B가 파일 B를 점유하여 파일 A의 점유해제를 기다리게 되어 양 A, B 태스크가 모두 이것 이상 처리가 진행되지 않는 상태의 예를 나타낸다.

 

쉽게 말해 하나 이상의 관련 스레드가 차단된 스레드의 원인이 되므로 절대 발생하지 않을 이벤트를 기다리는 상태이다
(리소스 에서 데드락이란: 스레드는 현재 리소스를 요청하는 스레드에 의해 보유되므로 허용되지 않는 리소스를 기다리는 동안 차단된다.)

 

• Deadlock은 리소스 경합 또는 신호 또는 통신 부족과 관련이 있을 수 있다.
• 전형적인 데드락이란
  • 스레드가 전진할 수 없는 상태
  • 스레드가 빠질 수 없는 상태
• 모든 스레드가 차단되지만 외부 이벤트가 결국에는 스레드의 차단을 해제하는 시스템인 idle 상태인 것과는 다르다

#Resource Deadlock Detection

• 교착 상태가 발생할 수 있는 상태
  • Exclusive Access: 리소스가 하나의 스레드에 의해 배타적으로 보유될 때
  • Hold and Wait 스레드가 다른 리소스를 획득하기 위해 대기하는 동안 하나의 리소스를 보유할 때
  • No preemption: 리소스에 대한 액세스를 일시적으로라도 취소할 수 없을 때
  • Circular Wait: 리소스 할당 그래프에 주기가 있을 때

(1)에서 (3)까지의 조건은 우리가 기본적으로 요구하는 조건이다. 예를 들어 자물쇠는 무언가에 대한 배타적이고 비선제적인 액세스를 제공하며, 그것들을 순차적으로 여러 개 획득하는 것이 필요할 수 있다

#교착상태에 대처하기 위한 전략

• Deadlock Recovery
• Deadlock Prevention 
• Deadlock Avoidance

#Deadlock Recovery

• 심각도 순서대로
  • 리소스에 대한 우선 액세스(가능한 경우)
  • 백업 프로세스: 비용이 많이 들고 체크포인트 및/또는 트랜잭션 메커니즘 필요
  • 교착 상태가 해결될 때까지 관련 프로세스 중지
  • 관련된 모든 스레드/프로세스 중지
  • 리부트 (Reboot)

마이크로소프트 OLE DB 데드락 사례:

안전 종료에 대한 참고 사항

• 교착 상태 복구의 일부로 스레드 또는 프로세스를 죽이는 것은 일반적으로 굉장히 까다롭다. 그렇기에 중지된 스레드가 나중에 액세스되는 조작 상태에 있는 상황을 피해야 한다
  • 예를 들어, kill -9은 모든 상태를 포함한 전체 프로세스를 중지한다. 커널은 커널 상태가 위험에 처하지 않도록 보장하지만 파일과 같은 리소스 상태에 대한 보장은 제공하지 않는다
  • 개별 스레드를 중지하는 것(예: pthread cancel())을 사용하는 것은 권장되지 않음/정확한 스레드 찾기 힘듬.

#Deadlock Prevention

다음 조건 중 하나만 이라도 제거되면 교착 상태가 발생할 수 없다.

• (Condition 1): 독점 액세스 제거
  • 리소스를 공유하거나 복제할 수 있는 경우 그렇게 하는 것이 권장된다
• (Condition 2): hold and wait 전략 회피
  • 모든 리소스를 한 번에 한 번에 요청 – 모듈식 시스템에서는 알기 어려울 수 있음
  • "try_acquire" 작업을 exploit해, 실패 시 이미 획득한 자원을 폐기- 리소스가 경합하는 경우 비효율적일 수 있음
• (Condition 3): preemption 허용
  • 리소스에 대한 선점 액세스 - 선점 기능이 있는 경우 강력한 코드를 작성하기가 어렵다
  • 리소스 가상화(저장 및 복원)
• (Condition 4): circular wait 회피
  • 동시에 보유할 수 있는 모든 리소스의 부분 순서 생성(예: C++17 std::scoped_lock)
  • 많은 실제 시스템은 종종 잠금 순서를 문서화한다.

#Deadlock Avoidance

• 필요한 4가지 조건 중 어느 것도 제거할 수 없는 경우 요청된 리소스 액세스를 허용할지 또는 거부할지를 고려할 수 있다
• 예: Banker’s algorithm (은행원 알고리즘)
  • 교착 상태를 초래할 수 있는 "안전하지 않은" 상태 방지
  • 향후 리소스 수요에 대한 지식 필요
  • 모든 종속성(dependencies)을 캡처해야 함
• 대체로 이론적이고 실무에 사용되지 않는 경우가 대부분이다

#실용적인 전략

• 가능한 모든 곳에서 예방 전략을 적용하여 교착 상태를 최소화한다
  • 불필요하게 세밀한 잠금(잠금 공유)을 피하라
  • 불가능한 경우 잠금 순서 정의
  • 잠금 순서가 위반되었을 때 플래그를 표시하는 도구 사용
  • 명확한 신호 전략사용
• 교착 상태 복구 감안
  • 교착 상태 복구로 인해 프로세스가 중단될 경우 손실되거나 반복되어야 하는 작업량을 최소화하기 위한 설계 시스템

#Deadlock vs. Starvation

• Starvation: 적절한 스케줄링 전략으로 수정할 수 있는 명백한 진행 부족
  • 높은 우선순위의 스레드가 항상 "준비" 상태인 경우 엄격한 우선순위 스케줄러는 낮은 우선순위의 스레드가 부족할 수 있다
  • 리더-라이터 잠금 장치는 리더에게만 잠금을 할당할 수 있으므로 작성자가 starve 할 수 있다.
• Deadlock: forward progress을 허용하는 스케줄링 전략은 없다

#결론

• 교착 상태는 집합의 스레드에 의해서만 생성될 수 있는 리소스나 이벤트를 기다리는 동안 스레드 집합이 차단되는 상태이다
• 재사용 가능한 리소스의 경우 리소스 할당 그래프를 사용하여 분석할 수 있다
• 교착 상태 감지 및 복구와 교착 상태 예방을 위한 전략 활용
• 일반적으로 잠금의 세분화에 따라 교착 상태가 발생할 위험이 증가한다 (확장성 대 견고성).