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