PE Notes · CA/OS
교착상태(Deadlock)/은행가 알고리즘(Banker's Algorithm)
교착상태(Deadlock): 둘 이상의 프로세스가 서로가 점유한 자원을 기다리며 무한히 대기해 아무도 진행하지 못하는 상태
교착상태(Deadlock): 둘 이상의 프로세스가 서로가 점유한 자원을 기다리며 무한히 대기해 아무도 진행하지 못하는 상태. 은행가 알고리즘(Banker's Algorithm): 다익스트라가 제안한 교착상태 회피(Avoidance) 기법 — 자원 요청을 허용했을 때 시스템이 (Safe State)를 유지하는 경우에만 할당.
구조와 칸
| 방법 | 전략 | 기법 | 장단점 |
|---|---|---|---|
| 예방(Prevention) | 4조건 중 하나를 원천 제거 | 상호 배제 부정(공유 가능 자원화), 점유 대기 부정(한 번에 전부 요청), 비선점 부정(대기 시 반납), 순환 대기 부정(자원 순서 번호 부여 후 오름차순 요청) | 확실 / 자원 이용률·처리량 저하, 기아 |
| 회피(Avoidance) | 요청마다 안전 상태 검사 | 은행가 알고리즘, 자원 할당 그래프(단일 인스턴스) | 이용률 높음 / 최대 요구량 사전 신고 필요, 검사 비용 |
| 탐지·회복(Detection & Recovery) | 발생 허용 후 주기적 탐지 | (Wait-for Graph) 사이클 탐지, 탐지 알고리즘 / 회복: 프로세스 종료·자원 선점·롤백 | 평상시 오버헤드 적음 / 회복 비용, 작업 손실 |
| 무시(Ostrich) | 드물다고 보고 방치 | 재부팅·운영자 개입 | 범용 OS 대부분(유닉스·윈도) / 발생 시 수동 대응 |
Available[m]: 현재 가용 자원 수. Max[n][m]: 각 프로세스의 최대 요구량. Allocation[n][m]: 현재 할당량. Need[n][m] = Max − Allocation: 앞으로 더 필요한 양.
예방 vs 회피 vs 탐지·회복 vs 무시
| 프로세스 | Allocation (A B C) | Max (A B C) | Need (A B C) |
|---|---|---|---|
| P0 | 0 1 0 | 7 5 3 | 7 4 3 |
| P1 | 2 0 0 | 3 2 2 | 1 2 2 |
| P2 | 3 0 2 | 9 0 2 | 6 0 0 |
| P3 | 2 1 1 | 2 2 2 | 0 1 1 |
| P4 | 0 0 2 | 4 3 3 | 4 3 1 |
| 기준 | 예방 | 회피 | 탐지·회복 | 무시 |
|---|---|---|---|---|
| 접근 | 조건 제거 | 안전 상태 유지 | 발생 후 해결 | 방치 |
| 사전 정보 | 불필요 | 최대 요구량 필요 | 불필요 | 불필요 |
| 자원 이용률 | 낮음 | 중간~높음 | 높음 | 높음 |
| 오버헤드 | 설계 제약 | 요청마다 검사 | 주기적 탐지·회복 비용 | 없음 |
| 적용 | 락 순서 규칙 | 은행가 알고리즘 | DBMS | 범용 OS |
DBMS: 교착 탐지 후 비용이 가장 적은 트랜잭션 롤백, 락 대기 시간 초과. 멀티스레드 프로그래밍: 락 순서 규칙(항상 A → B 순서로 획득)으로 순환 대기 예방, tryLock 타임아웃. 분산 시스템: 분산 락의 리스(Lease)·만료 시간, 타임스탬프 기반 기법.
답안은 교착상태(Deadlock)/은행가 알고리즘(Banker's Algorithm)의 정의, 칸, 비교 축을 한 장에 닫습니다.
기술사 답안 포인트
관련 용어
관련 토픽
CA/OS
세마포어(Semaphore) - 모니터/뮤텍스와 비교
세마포어(Semaphore): 에츠허르 다익스트라(Dijkstra, 1965)가 제안한 동기화 도구 — 정수 변수 S와 이를 원자적으로 조작하는 두 연산 P(wait, down)·V(signal, up)로 임계 구역 상호 배제와 프로세스 간 실행 순서
CA/OS
우선순위 역전(Priority Inversion, 해결기법 포함)
우선순위 역전(Priority Inversion): 우선순위 기반 선점 스케줄링에서 높은 우선순위 태스크(H)가 낮은 우선순위 태스크(L)가 가진 공유 자원(락)을 기다리는 동안, 중간 우선순위 태스크(M)가 L을 선점해 실행되면서 결과적으로 H가 M
CA/OS
OS 스케줄링 알고리즘(SJF/SRT/SSTF/SLTF, RM vs EDF)
스케줄링(Scheduling): 한정된 자원(CPU·디스크 등)을 여러 요청에 어떤 순서로 배정할지 결정하는 OS 기능