교착 상태와 메모리 단편화

좁은 골목에서 두 차가 서로 비켜주길 기다리다 둘 다 멈추는 게 교착(Deadlock), 자리는 남는데 못 쓰는 게 단편화(Fragmentation) — 한정된 자원을 나눠 쓸 때 생기는 두 부작용을 한 강에 묶는다. 4과목에서 교착 4조건·단편화 분별이 거의 매 회차 1~2문항 굳어 나오는 빈출 단원이다. 34강 기아(Starvation)가 자원 경쟁의 부작용이었다면, 35강은 그 자원 경쟁이 상호 교착으로 번지는 단원이다. 29강 DB 트랜잭션의 교착 4조건이 여기서 OS 자원 시각으로 본격 재무대화한다.

핵심 암기: 교착 4조건 ★상점비환★(상호배제·점유와 대기·비선점·환형 대기·모두 동시) · 해결 4전략 ★예회탐복★(예방·회피·탐지·복구 — 예회는 사전 / 탐복은 사후) · 단편화 분별 ★고내가외★(고정→내부 / 가변→외부) · 은행원 알고리즘 = 회피 · 배치 3전략(최초 빠름·최적 효율·최악 큰 자투리)

PART A — 교착 상태(Deadlock)

교착 상태란? ·교착 상태·

[정의] 교착 상태(Deadlock) = 둘 이상의 프로세스가 자원을 점유한 채 서로 상대가 점유한 자원을 무한정 기다리며 어느 쪽도 진행하지 못하는 상태. 외부 개입 없이는 영원히 풀리지 않는다.

[표] 교착의 네 가지 특징

💡 좁은 일방통행 골목에서 두 차가 마주쳐, 서로 "저 차가 먼저 빠져야지" 하며 둘 다 꼼짝 못 하는 그림.

🔑 암기 "교착 = 둘 이상이 서로의 자원을 영영 기다림 + 외부 개입 없이는 안 풀림" — 이 한 문장이 정의 즉답.

⚠️ 함정 "한 프로세스만으로도 교착 발생" ❌(→ 최소 2개 이상) / "시간이 지나면 저절로 풀린다" ❌(→ 외부 개입 필요·그건 기아).

🎯 빈출 정의를 직접 묻기보다 4조건·해결 전략으로 변형 출제. 다중 프로그래밍 환경에서 CPU·메모리·파일·프린터 같은 공유 자원 경쟁이 전제.

교착 4대 필요 조건 — ★상점비환★ ·교착 상태·시험 1순위·

[정의] 교착이 발생하려면 네 가지 조건이 모두 동시에 성립해야 한다. 하나라도 깨지면 교착은 사라진다. 그 네 글자가 ★상점비환★.

[표] ★상점비환★ — 4대 필요 조건 종합

[흐름] 환형 대기 — 자원 할당 그래프의 사이클

P1 ──> R1 ──> P2 ──> R2 ──> P3 ──> R3 ──> P1
   원형 고리(사이클) 존재 → 교착 (사이클 판정은 탐지에서 본격)

[표] 29강 DB ↔ 35강 OS — 무대만 다르고 4조건은 완전 동일

🔑 암기 "상·점·비·환 4글자 매칭 + DB↔OS는 무대만 다름 + '선점' 보이면 100% 함정"

⚠️ 함정 "4조건에 선점(Preemption) 포함" ❌(→ 비선점이 조건·'선점'은 오히려 해결 방향·'비' 한 글자 함정) / "4조건 중 하나만 성립해도 교착" ❌(→ 모두 동시) / "DB와 OS의 4조건이 다르다" ❌(→ 완전 동일).

🎯 빈출 "교착 발생의 필요 조건이 아닌 것" 부정형으로 가짜 보기에 '선점'을 끼워 넣는 형태가 매 회차 시그니처. 4과목 거의 매 회차 1문항.

📝 기출 교착 4조건 (부정형) · 기출 1

교착 vs 기아 분별 ·교착 상태·

[정의] 기아(Starvation) = 우선순위에 계속 밀려 특정 프로세스가 영영 자원을 받지 못하는 상태. 34강 SJF·우선순위 스케줄링의 부작용으로 본 그 개념이다.

[표] 교착 vs 기아 — 단골 바꿔치기 함정

💡 교착 = 좁은 골목 두 차의 상호 막힘 / 기아 = 교차로에서 우선순위가 계속 밀려 못 끼어듦. Aging(에이징)은 34강에서 본 기아 전용 처방.

🔑 암기 "교착 = 둘 이상 + 상호 막힘 + 외부 개입 / 기아 = 한 명 + 우선순위 밀림 + Aging 해소"

⚠️ 함정 "기아는 외부 개입 없이 절대 안 풀린다" ❌(→ 그건 교착) / "Aging은 교착 해결 기법" ❌(→ Aging은 기아 전용·교착은 ★예회탐복★).

🎯 빈출 교착과 기아의 특징을 한 줄씩 뒤바꾸는 분별형. 34강 Aging과 묶여 출제.

PART B — 교착 해결 4전략 ★예회탐복★

해결 4전략 — ★예회탐복★ ·교착 해결·시험 1순위·

[정의] 교착 해결 전략은 네 가지. ★예회탐복★ — 예방·회피·탐지·복구. 결정 카드는 "예회는 사전 / 탐복은 사후".

[표] ★예회탐복★ — 4전략 종합

💡 교통사고에 빗대면 — 예방 = 도로 설계를 바꿔 사고를 막음 / 회피 = 내비가 막히는 길을 우회 / 탐지 = CCTV로 사고 발견 / 복구 = 견인차가 차를 치움. 예회는 사고 전, 탐복은 사고 후.

🔑 암기 "★예회탐복★ 4글자 자리 그대로 — 예회는 사전 / 탐복은 사후"

⚠️ 함정 "은행원 알고리즘은 사후 전략" ❌(→ 사전·회피) / "자원 할당 그래프는 사전 전략" ❌(→ 사후·탐지) / '발견·할당·분배' 등 ★예회탐복★ 4글자 외 단어는 모두 함정.

🎯 빈출 전략과 시점(사전/사후) 매칭, 4글자 외 가짜 단어 끼워 넣기.

📝 기출 잘못 짝지어진 것 (짝짓기) · 기출 5

예방(Prevention) — 4부정 방법 ·교착 해결·

[정의] 예방 = 교착 4조건 중 하나를 원천 부정해서 발생 자체를 막는 사전 전략. 하나만 부정해도 교착은 사라진다. 단 각 부정마다 단점이 따른다는 게 핵심.

[표] 4부정 방법 + 단점

💡 실무에서 가장 많이 쓰는 건 환형 대기 부정 — 트랜잭션이 무거운 시스템에서 '낮은 ID 자원부터 락 획득' 패턴이 표준.

🔑 암기 "예방 = 4조건 중 하나 원천 부정 — 4방법·4단점. 환형 대기 부정이 실무 1순위"

⚠️ 함정 "예방은 4조건을 모두 동시 부정해야 한다" ❌(→ 하나만 부정해도 교착 사라짐).

🎯 빈출 부정 대상과 단점 매칭. 예방 ↔ 회피 접근 차이 비교.

회피(Avoidance) + 은행원 알고리즘 ·교착 해결·시험 1순위·

[정의] 회피 = 자원 요청 매 순간 교착 가능성을 미리 판단해 안전한 경우에만 할당하는 사전 전략. 대표 기법이 은행원 알고리즘(Banker's Algorithm) — 다익스트라(Dijkstra)가 고안했다.

[표] 안전 상태 vs 불안전 상태

[흐름] 은행원 시뮬레이션 — 총 자원 12개·현재 가용 3개

프로세스   최대(Max)   할당(Alloc)   추가 필요(Need)
   P1         10           5             5
   P2          4           2             2
   P3          9           2             7
   할당 합 5+2+2=9 → 가용 12-9 = 3

판단 → P2 Need 2 ≤ 가용 3   완료·회수 2 → 가용 5
     → P1 Need 5 ≤ 가용 5   완료·회수 5 → 가용 10
     → P3 Need 7 ≤ 가용 10  완료·회수 2 → 가용 12
안전 순서열 = P2 → P1 → P3  (모두 정상 종료 = 안전 상태)

💡 은행에 1억이 있고 고객마다 대출 한도가 정해져 있을 때, 매 요청마다 "지금 빌려줘도 나머지 고객까지 모두 처리할 수 있나?"를 미리 계산해 안 되면 거절. P1에 먼저 5를 주면 가용이 0이 되어 P2·P3 모두 막히는 불안전 상태라, 은행원은 P2를 먼저 처리한다.

🔑 암기 "은행원 = 회피 = 다익스트라 = 안전 상태에서만 할당 — 매년 1순위 매칭"

⚠️ 함정 "은행원 알고리즘 = 예방" ❌(→ 회피·매년 1순위 함정) / "불안전 상태 = 반드시 교착" ❌(→ 가능성만) / "안전 순서열이 여러 개면 불안전" ❌(→ 1개 이상 존재 = 안전).

🎯 빈출 '안전 상태·은행원·다익스트라·요구량 ≤ 가용량' 중 하나라도 보이면 즉시 회피. 안전 순서열 계산도 출제.

📝 기출 은행원=회피 · 회피 원리(요구량≤가용량) · 기출 2·6

탐지(Detection) + 복구(Recovery) + 세마포어 ·교착 해결·

[정의] 탐지 = 교착이 이미 발생했는지 자원 할당 그래프의 사이클로 감시(사후). 복구 = 발생한 교착에서 벗어나는 사후 조치.

[흐름] 탐지 — 사이클 존재 = 교착

P1 ──> R1 ──> P2 ──> R2 ──> P1   사이클 존재 = 교착 (CCTV로 사고 발견)

[표] 복구(Recovery) 3가지 방법

[표] 세마포어(Semaphore) — 4전략 밖, 상호 배제 도구

🔑 암기 "자원 할당 그래프 사이클 = 탐지 / 제거·선점·체크포인트 = 복구 / 세마포어 P=대기·V=해제"

⚠️ 함정 "세마포어 = 교착 해결 4전략에 포함" ❌(→ 상호 배제 구현 도구·4전략 밖) / "P=해제·V=대기" ❌(→ P=대기·V=해제 자리 바꿔치기).

🎯 빈출 보기 키워드로 전략 찾기 — 사이클=탐지 / 제거·선점·체크포인트=복구. 세마포어 P/V 한 줄.

PART C — 메모리 단편화(Fragmentation)

메모리 할당 분류 — 연속 vs 분산 ·메모리 관리·

[정의] 프로그램은 실행되려면 주기억장치(RAM)에 적재되어야 한다. 한정된 RAM에 다양한 크기의 프로세스가 들어오고 나가며 공간은 남는데 못 쓰는 낭비가 생기는 게 단편화. 할당 기법은 크게 연속 / 분산으로 나뉜다.

[흐름] 주기억장치 할당 기법 분류

주기억장치 할당 기법
├─ 연속 할당  ← 35강 본격 (단편화의 숙제)
│   ├─ 단일 분할: 오버레이 / 스와핑
│   └─ 다중 분할: 고정(→내부 단편화) / 가변(→외부 단편화)
└─ 분산 할당  ← 36강 본격
    ├─ 페이징 (고정 크기 프레임) → 내부
    └─ 세그먼테이션 (논리 단위) → 외부

[표] 연속 vs 분산

💡 연속 = 영화관에서 일행이 나란히 앉기(편하나 연속 빈자리 없으면 못 앉음) / 분산 = 흩어져 앉기(찾기 쉬우나 관리 복잡).

🔑 암기 "연속 = 통째로 나란히 / 분산 = 조각내 흩어져. 단편화는 연속 할당의 숙제"

🎯 빈출 분산 할당(페이징·세그먼테이션)은 단편화를 줄이는 다음 단계 해법 — 36강에서 본격(★페고내·세가외★).

단일 분할 — 오버레이 vs 스와핑 ·메모리 관리·

[정의] 단일 분할 = 주기억장치를 하나의 프로세스에게 통째로 할당하는 가장 단순한 방식.

[표] 오버레이 vs 스와핑

💡 오버레이 = 좁은 책상에서 교재를 한 권씩 바꿔가며 공부(조각) / 스와핑 = 안 쓰는 교재를 통째로 서랍에 넣고 필요할 때 꺼냄(전체).

🔑 암기 "오버레이 = 프로그램 일부·번갈아 / 스와핑 = 프로세스 전체·교환"

⚠️ 함정 "오버레이 = 프로세스 전체" ❌(→ 일부) / "Swap-in = 내보내기" ❌(→ 불러오기·방향 바꾸기).

🎯 빈출 대상(일부/전체)과 방향(in/out) 바꿔치기.

다중 분할 — 고정 vs 가변 ★고내가외★ ·메모리 관리·시험 1순위·

[정의] 다중 분할 = 메모리를 여러 영역으로 나눠 여러 프로세스를 동시 적재. 고정 분할과 가변 분할 두 가지이며, 어느 쪽이냐가 단편화 종류를 결정한다. ★고내가외★ — 고정→내부 / 가변→외부.

[표] ★고내가외★ — 고정 vs 가변 종합

💡 고정 = 아파트 주차장(칸이 미리 그려져 경차가 대형 칸에 서면 안쪽이 남음 = 내부) / 가변 = 노상 주차(차 크기에 맞추나 빠지고 나면 사이에 애매한 자투리 = 외부).

🔑 암기 "★고내가외★ — 고정→내부 / 가변→외부. 36강 ★페고내·세가외★로 확장(페이징=고정→내부 / 세그먼테이션=가변→외부)"

⚠️ 함정 "고정 = 외부" ❌·"가변 = 내부" ❌(→ 두 쌍 자리 바꿔치기 매년 1순위) / 분할 시점 바꿔치기.

🎯 빈출 고정/가변 ↔ 내부/외부 매칭. 35강 단편화 최대 빈출 카드.

내부 단편화(Internal Fragmentation) ·메모리 관리·

[정의] 내부 단편화 = 할당된 메모리 영역이 프로세스가 실제 필요한 크기보다 커서, 영역 안쪽에 사용되지 않는 공간이 남는 현상. 고정 분할에서 발생.

[흐름] 시그니처 시나리오 — 100KB 파티션·70KB 프로세스

[ 100KB 고정 파티션 ]
   ├ 프로세스 70KB 사용
   └ 빈 30KB ← 영역 안쪽 낭비 = 내부 단편화

💡 택배 상자에 작은 물건을 넣고 빈 공간에 뽁뽁이를 채우는 것 — 뽁뽁이만큼이 낭비. '내부'는 파티션 안쪽에서 낭비가 나기 때문.

🔑 암기 "100KB 파티션 + 70KB 프로세스 = 30KB 안쪽 낭비 — 고정 분할(★고내가외★)"

⚠️ 함정 "내부 단편화 = 가변 분할" ❌(→ 고정) / "통합·압축으로 해결" ❌(→ 그건 외부·내부는 분할 크기를 프로세스에 맞춰 해결).

🎯 빈출 시그니처 수치(100/70/30)로 낭비량 계산, 고정 분할 매칭.

외부 단편화(External Fragmentation) ·메모리 관리·

[정의] 외부 단편화 = 메모리 전체 빈 공간은 충분하지만 연속적이지 않아 큰 프로세스를 적재할 수 없는 현상. 가변 분할에서 할당/해제가 반복되면 자연 발생.

[흐름] 시그니처 시나리오 — 빈 50+40+60KB, 80KB 적재 시도

[사용중][빈 50][사용중][빈 40][사용중][빈 60]
   빈 합계 50+40+60 = 150KB
   최대 연속 60KB < 80KB → 80KB 프로세스 적재 불가 = 외부 단편화

💡 주차장에 빈 칸이 5칸이지만 1칸씩 띄엄띄엄이라, 연속 3칸이 필요한 대형 버스가 못 서는 것. '외부'는 파티션 바깥쪽에 빈 공간이 흩어져서.

🔑 암기 "빈 50+40+60=150KB·연속 60KB뿐 → 80KB 적재 불가 — 가변 분할(★고내가외★)"

⚠️ 함정 "외부 단편화 = 고정 분할" ❌(→ 가변) / "전체 빈 공간이 많으면 외부 단편화 없음" ❌(→ 연속 공간 부족이 핵심).

🎯 빈출 연속성 부족 개념, 통합·압축 해결과 묶어 출제.

PART D — 메모리 배치 전략 & 단편화 해결

배치 3전략 + 시뮬레이션 ·메모리 관리·

[정의] 배치 전략 = 가변 분할에서 프로세스를 빈 공간 어디에 둘지 결정. 최초·최적·최악 3종 + 변형 후속(Next).

[표] 배치 3전략 + 후속

[흐름] 시뮬레이션 — 빈 공간 A:60·B:45·C:120KB, 프로세스 40KB

프로세스 40KB 가 어디에?
  최초(First) → A(60)  처음 발견한 적합   → 자투리 20
  최적(Best)  → B(45)  40에 가장 가까움   → 자투리  5
  최악(Worst) → C(120) 가장 큰 공간       → 자투리 80

💡 최초 = 처음 보이는 적당한 물건 바로 집기(빠름) / 최적 = 매장 다 돌아 딱 맞는 것(효율) / 최악 = 일부러 가장 큰 곳(자투리 커서 재할당 용이).

🔑 암기 "가장 작은(딱 맞는) = Best / 가장 큰 = Worst / 가장 빠른·첫 번째 = First / 이전 다음부터 = Next"

⚠️ 함정 "최적 = 가장 빠름" ❌(→ 최초) / "최악 = 가장 작은 공간" ❌(→ 가장 큰) / "후속 = 최적의 변형" ❌(→ 최초의 변형) / "Last Fit" ❌(→ 존재하지 않는 함정 선지·배치 전략은 First·Best·Worst·Next 4종).

🎯 빈출 '가장 작은 공간에 배치' → Best Fit. Last Fit 가짜 선지 끼워 넣기.

📝 기출 가장 작은 공간 = Best Fit · 기출 3

통합(Coalescing) vs 압축(Compaction) ·메모리 관리·

[정의] 외부 단편화 해결 두 기법. 통합 = 인접한 빈 공간을 합침 / 압축 = 흩어진 빈 공간을 한쪽 끝으로 모아 큰 블록을 만듦. 둘 다 외부 단편화 해결책.

[표] 통합 vs 압축

💡 통합 = 책장 빈 칸이 나란할 때 칸막이를 빼 큰 칸으로 / 압축 = 책들을 한쪽으로 쫙 밀어 반대쪽에 큰 빈 공간 만들기. 근본 해결은 분산 할당(페이징)으로 가는 것 — 연속 공간이 필요 없어져 외부 단편화가 원천 차단(36강).

🔑 암기 "통합 = 인접 합침·자동·가벼움 / 압축 = 전체 밀기·재배치·비쌈. 둘 다 외부 단편화 해결"

⚠️ 함정 "통합 = 모든 프로세스 재배치" ❌(→ 그건 압축) / "통합·압축 = 내부 단편화 해결" ❌(→ 외부 해결) / "현대 OS는 압축을 주로 사용" ❌(→ 페이징으로 원천 차단).

🎯 빈출 통합 ↔ 압축 정의·비용 구분, 내부/외부 해결 대상 바꿔치기.

기출 다지기

[기출 1 출제] 교착 상태(Deadlock) 발생의 필요 조건이 아닌 것은? (부정형)

• ① 상호 배제(Mutual Exclusion)
• ② 점유와 대기(Hold and Wait)
• ③ 환형 대기(Circular Wait)
• ④ 선점(Preemption)

[기출 2 출제] 교착 상태 해결 중, 사전에 시스템을 제어하여 은행원 알고리즘(Banker's Algorithm)이 사용되는 기법은? (설명→기법)

• ① 예방(Prevention)
• ② 회피(Avoidance)
• ③ 발견(Detection)
• ④ 회복(Recovery)

[기출 3 출제] 주기억장치 배치 전략 중 가용 공간 가운데 가장 작은 공간에 배치하는 전략은? (설명→용어)

• ① First Fit
• ② Best Fit
• ③ Worst Fit
• ④ Last Fit

[기출 4 출제] 분할된 주기억장치에 프로세스를 할당하고 남은 빈 공간이 너무 작아 메모리가 낭비되는 현상은? (설명→용어)

• ① 세그먼테이션
• ② 스래싱
• ③ 단편화
• ④ 스와핑

[기출 5 출제] 교착 상태 해결 전략과 설명이 잘못 짝지어진 것은? (짝짓기)

• ① 예방 — 필요 조건 중 하나를 부정하여 발생을 막음
• ② 회피 — 안전 상태에서만 자원을 할당
• ③ 탐지 — 자원 할당 그래프를 이용하여 교착 확인
• ④ 회복 — 교착 상태의 4대 조건을 모두 제거하여 해결

[기출 6 출제] 교착 상태 해결 중 '회피' 기법에 해당하는 것은? (설명→기법)

• ① 자원 할당 시 시간을 제한하고 미완료 시 회수
• ② 사용 중인 자원을 다른 프로세스가 선점
• ③ 시작 시 필요한 모든 자원을 한 번에 할당
• ④ 요구 자원 수가 현재 사용 가능한 수보다 작을 때에만 할당

한 장 요약

🎯 합격 한 끗: ★상점비환★(4조건·모두 동시) + ★예회탐복★(예회 사전·탐복 사후) + ★고내가외★(고정→내부 / 가변→외부) 세 두음 + 은행원=회피 + 배치 3전략(최초 빠름·최적 효율·최악 큰 자투리). 35강 출제 1~2문항은 거의 모두 교착 4조건·은행원 분류·단편화 분별 세 영역에서 나온다. ★고내가외★는 36강 ★페고내·세가외★(페이징=고정→내부 / 세그먼테이션=가변→외부)로 자연 확장된다.