교착 상태 (Deadlock)
데드락이란?
두 개 이상의 프로세스/스레드가 서로의 자원을 기다리며 영원히 대기하는 상태.
시각화
| 스레드 | 갖고 있는 락 | 기다리는 락 |
|---|
| Thread A | X | Y |
| Thread B | Y | X |
서로가 상대의 락을 기다리므로 스스로는 영원히 풀리지 않습니다.
데드락 4가지 조건 (모두 충족 시 발생)
| 조건 | 설명 |
|---|
| 상호 배제 | 자원은 한 번에 한 프로세스만 |
| 점유 대기 | 자원 보유 + 다른 자원 대기 |
| 비선점 | 강제로 뺏을 수 없음 |
| 순환 대기 | A→B→C→A 형태의 대기 |
해결 전략
| 전략 | 방법 | 비용 |
|---|
| 예방 | 4조건 중 하나 제거 | 높음 |
| 회피 | 은행원 알고리즘 | 중간 |
| 탐지+복구 | 주기적 검사 후 프로세스 종료 | 낮음 |
| 무시 | 발생 시 재시작 (대부분 OS) | 최저 |
서비스에서 실제로 나는 모양
교착은 이론 예제보다 평범한 코드에서 납니다. 두 곳이 같은 행 두 개를 다른 순서로
잠그면 그것으로 충분합니다.
| 상황 | 왜 순서가 어긋나나 |
|---|
| 계좌 이체 | 보내는 쪽과 받는 쪽을 인자 순서대로 잠근다 |
| 목록을 한꺼번에 갱신 | 목록의 순서가 요청마다 다르다 |
| 부모와 자식 행 | 어떤 경로는 부모부터, 어떤 경로는 자식부터 |
첫째는 한 줄로 사라집니다. 두 계좌를 번호가 작은 쪽부터 잠그면 순서가 항상 같아집니다.
순환을 만들지 않는 것이 감지하고 되돌리는 것보다 훨씬 쌉니다.
잡혔을 때 무엇을 하나
DB 는 교착을 감지하면 한쪽을 골라 실패시킵니다. 그 실패는 다시 시도하면 대개 성공합니다.
교착으로 인한 실패는 다른 오류와 구분해 다시 시도한다
같은 순서로 다시 들어가면 이번에는 상대가 없어 통과한다
그래서 이 오류를 사용자에게 그대로 보여 주지 않고 한 번 더 시도합니다. 다만 무한히
반복하지는 않습니다. 계속 난다면 순서가 어긋난 자리를 찾아야 합니다.
실무 포인트
- DB 데드락: 트랜잭션 간 Lock 순서 불일치
→ 해결: 항상 같은 순서로 Lock 획득
- Java:
synchronized 블록 순서 주의
- 대부분의 서비스는 탐지+타임아웃으로 처리
Q.데드락 발생 4가지 조건을 설명해주세요
넷이 동시에 성립해야 데드락입니다.
| 조건 | 뜻 |
|---|
| 상호 배제 | 한 자원을 한 번에 하나만 쓴다 |
| 점유 대기 | 하나를 쥔 채 다른 것을 기다린다 |
| 비선점 | 남이 쥔 것을 뺏을 수 없다 |
| 순환 대기 | 서로가 서로를 기다리는 고리가 있다 |
A 는 X 를 쥐고 Y 를 기다린다
B 는 Y 를 쥐고 X 를 기다린다
이 넷은 필요조건이자 충분조건입니다. 하나만 깨면 데드락이 생기지 않습니다.
흔한 실수: 조건을 외우고 끝내는 것. 각각이 왜 필요한지 대는 것이 좋습니다. 상호 배제가 없으면 기다릴 이유가 없고, 점유 대기가 없으면 손에 든 것이 없어 남을 막지 않고, 선점이 가능하면 뺏어서 풀 수 있고, 고리가 없으면 언젠가 끝나는 순서가 존재합니다.
Q.데드락을 해결하는 방법은?
네 가지 접근이 있고 비용이 다릅니다.
| 접근 | 방법 | 비용 |
|---|
| 예방 | 4조건 중 하나를 원천 차단 | 자원 활용률이 떨어진다 |
| 회피 | 안전 상태인지 확인하고 할당 | 최대 요구량을 미리 알아야 한다 |
| 감지와 복구 | 생기면 찾아서 하나를 죽인다 | 감지 비용과 롤백 비용 |
| 무시 | 드물면 그냥 둔다 | 생기면 재시작 |
실무에서는 예방(잠금 순서 고정)과 감지 후 재시도를 함께 씁니다. 예방으로 대부분을 없애고, 남은 것은 DB 가 감지해 한쪽을 롤백하면 애플리케이션이 재시도합니다.
회피(은행원 알고리즘)는 최대 요구량을 미리 알아야 해서 범용 시스템에서는 쓰기 어렵습니다.
일반 운영체제는 사실상 무시 전략입니다. 데드락 감지 비용이 발생 빈도에 비해 크기 때문입니다.
흔한 실수: 예방만으로 완전히 없앨 수 있다고 답하는 것. 잠글 대상을 미리 알 수 없는 경로가 남아 재시도가 필요합니다.
Q.은행원 알고리즘이란?
자원을 할당하기 전에 모두가 끝날 수 있는 순서가 존재하는지 확인하고, 없으면 할당을 미루는 회피 기법입니다.
각 프로세스가 앞으로 최대 얼마를 더 요구할지 미리 선언한다
요청이 오면 가정해서 할당해 보고
남은 자원으로 어떤 순서로든 전부 끝낼 수 있으면 -> 안전. 할당한다
그런 순서가 없으면 -> 불안전. 기다리게 한다
은행이 대출을 내줄 때 모든 고객의 최대 한도를 감당할 수 있는지 보는 것에서 이름이 왔습니다.
| 필요한 것 | 왜 실무에서 어려운가 |
|---|
| 최대 요구량 사전 선언 | 프로그램이 얼마를 쓸지 미리 알기 어렵다 |
| 프로세스 수 고정 | 실제로는 계속 생기고 사라진다 |
| 매 요청마다 검사 | 계산 비용이 든다 |
흔한 실수: 불안전 상태를 데드락과 같은 것으로 답하는 것. 불안전은 데드락이 될 수도 있는 상태이고 반드시 되는 것은 아닙니다. 알고리즘은 그 가능성 자체를 피합니다.
먼저 스스로 답해보고 아래 답변과 견줘보세요. 막히는 부분은 문제로 확인할 수 있어요.
읽었으면 문제로 확인해보세요
운영체제 문제를 풀면 틀린 문제가 자동으로 노트에 쌓입니다. 가입 없이 5문제를 먼저 풀어볼 수도 있어요.