운영체제 6강
교착상태 (Deadlock)
✅ 교착상태란?
- 둘 이상의 프로세스가 서로 자원을 점유한 상태에서,
상대방의 자원을 기다리며 무한 대기에 빠지는 상황
● 예시
- 프로세스 1: 자원 A 보유 → 자원 B 요청
- 프로세스 2: 자원 B 보유 → 자원 A 요청
→ 둘 다 상대방의 자원을 기다리며 멈춤
✅ 교착상태 발생 조건 (4가지 모두 만족 시 발생 가능)
-
상호배제(Mutual Exclusion)
- 자원은 한 번에 하나의 프로세스만 점유 가능
-
점유와 대기(Hold and Wait)
- 자원을 점유한 상태에서 다른 자원을 기다림
-
비선점(No Preemption)
- 자원을 강제로 회수할 수 없음
-
환형 대기(Circular Wait)
- 프로세스들이 원형 구조로 자원을 대기함
✅ 교착상태 모델 (자원 할당 그래프)
- 프로세스: 원으로 표현
- 자원: 사각형으로 표현
- 요구 간선: 프로세스 → 자원
- 할당 간선: 자원 → 프로세스
- 사이클 존재 시 교착상태 발생 가능
✅ 교착상태 처리 방법
1. 예방 (Deadlock Prevention)
- 4가지 조건 중 하나라도 제거
● 상호배제 제거
- 읽기 전용 자원에만 가능
● 점유대기 제거
- 모든 자원을 한 번에 요청 → 비현실적
● 비선점 제거
- 자원 회수 필요 → 적용 불가한 자원 있음 (프린터 등)
● 환형대기 제거
- 자원에 번호 부여, 오름차순으로만 요청 허용
2. 회피 (Deadlock Avoidance)
- 프로세스가 필요로 하는 최대 자원 수를 미리 파악
- 안전 상태(Safe State) 내에서만 자원 할당
● 은행원 알고리즘 (Banker’s Algorithm)
- 자원 할당 전 가상 할당 수행 → 안전성 판단 후 실제 할당
3. 탐지 및 회복 (Deadlock Detection & Recovery)
- 사이클 탐지 알고리즘으로 교착상태 탐지
- 발생 시 아래 방식으로 복구:
- 프로세스 종료
- 자원 회수
- 체크포인트/롤백 등 활용
✅ 교착상태가 아닌 예
- 사이클이 존재하더라도 자원이 충분하면 발생하지 않음
✅ 요약
- 교착상태는 자원 경쟁의 대표적인 문제
- 발생 조건은 상호배제, 점유대기, 비선점, 환형대기
- 예방 / 회피 / 탐지 및 회복의 세 가지 방식으로 처리 가능
운영체제 강의 7 요약
교착상태 회피 & 탐지 및 복구
✅ 교착상태 회피 (Deadlock Avoidance)
● 개념
- 교착상태를 사전에 방지하기 위해, 자원 요청 시 시스템이 안전 상태인지 판단하여 할당 여부 결정
- 최대 요구량을 알고 있어야 함
✅ 안전 상태 vs 불안전 상태
| 상태 | 설명 |
|---|---|
| 안전 상태 | 모든 프로세스가 최대 요구량을 만족할 수 있는 순서열 존재 |
| 불안전 상태 | 최대 요구량까지 자원을 할당할 수 있는 순서열 없음 → 교착상태 가능성 |
✅ 자원 할당 그래프 확장
- 선언 간선 추가: 앞으로 자원을 요청할 것이라는 의미
- 요구 간선과 구분 위해 점선으로 표시
- 요구 시, 선언 간선을 요구 간선으로 바꾸고 할당 가능 여부 판단
✅ 은행원 알고리즘 (Banker's Algorithm)
- 가용 자원 상태를 시뮬레이션하여 안전성 확인 후 할당
- 프로세스가 요청한 자원 수가 남은 필요량 및 가용 자원보다 작거나 같은지 검사
void bank(Pi) {
if (!(request_i <= need_i)) 오류;
if (!(request_i <= available)) Pi 대기;
// 가상 할당
available -= request_i;
alloc_i += request_i;
need_i -= request_i;
if (safe()) Pi 할당;
else {
Pi 대기;
상태 복구;
}
}✅ 안전성 검사 알고리즘 (Safe Algorithm)
boolean safe() {
for (i = 1 to n) FINISH[i] = false;
while (true) {
for (i = 1 to n) {
if (FINISH[i] == false && need_i <= work) {
work += alloc_i;
FINISH[i] = true;
break;
}
}
if (i > n) break;
}
if (모든 FINISH[i] == true) return true;
else return false;
}✅ 교착상태 탐지 (Deadlock Detection)
- 시스템 자원 사용 현황을 주기적으로 분석
- 사이클 존재 여부 검사로 교착상태 여부 판단
boolean detect() {
for (i = 1 to n)
if (request_i != 0) FINISH[i] = false;
else FINISH[i] = true;
while (true) {
for (i = 1 to n) {
if (FINISH[i] == false && request_i <= work) {
work += alloc_i;
FINISH[i] = true;
break;
}
}
if (i > n) break;
}
if (FINISH[i] == false for some i) return true;
else return false;
}✅ 교착상태 복구 방법
1. 프로세스 종료
- 모든 교착 상태 프로세스를 종료
- 하나씩 종료하여 사이클 제거
2. 자원 선점
- 교착 상태 프로세스가 가진 자원을 회수하여 다른 프로세스에 할당
- 선점 기준: 우선순위, 자원 수, 기여도 등
- 기아 상태 방지 고려
✅ 요약
- 회피: 사전 검사로 안전 상태에서만 자원 할당 (은행원 알고리즘)
- 탐지 및 복구: 발생 후 사이클 탐지 알고리즘 사용, 프로세스 종료 또는 자원 선점으로 해결
운영체제 8강
프로세스와 메모리 관리 (연속 할당, 단편화, 배치 전략 등)
✅ 프로세스 메모리 적재 시 고려사항
- 언제 새로운 프로세스를 메모리에 둘 것인가?
- 다음에 실행될 프로세스를 어디에 둘 것인가?
- 메모리가 꽉 찼을 때, 어떤 프로세스를 제거할 것인가?
✅ 메모리 계층 구조
- CPU 레지스터 > 캐시 메모리 > 메인 메모리 > 보조기억장치
- 속도는 빠를수록 용량이 작고 비용이 비쌈
✅ 연속 메모리 할당
● 단일 프로그래밍 환경
- 하나의 프로세스만 메모리에 존재
- CPU, I/O 대기로 인한 비효율
● 다중 프로그래밍 환경
- 여러 프로세스가 메모리에 존재 가능
- CPU 활용도 향상
✅ 고정 분할 할당 (Fixed Partition)
● 절대 번역 방식
- 분할별 고정 큐 존재, 해당 큐에만 적재 가능
- 단점: 효율 낮음, 자원 낭비
● 재배치 번역 방식
- 모든 분할에 하나의 큐, 어디든 적재 가능
- 단점: 복잡도 상승
✅ 내부 단편화 (Internal Fragmentation)
- 프로세스가 할당받은 공간보다 작아 남는 메모리 낭비
- 고정 분할 시 발생
✅ 외부 단편화 (External Fragmentation)
- 메모리 내 작은 빈 공간들이 흩어져 전체 공간이 부족한 문제
- 해결 방법:
- 통합 (Compaction): 인접된 공백을 하나로
- 집약 (Defragmentation): 모든 공백을 한곳으로 모음
✅ 배치 전략 (메모리 할당 알고리즘)
● 최초 적합 (First Fit)
- 처음 발견된 충분한 공간에 배치
● 최적 적합 (Best Fit)
- 가장 작은 충분한 공간에 배치 → 내부 단편화 최소
● 최악 적합 (Worst Fit)
- 가장 큰 공간에 배치 → 큰 공백 유지
● 후속 적합 (Next Fit)
- 마지막 검색 위치 이후부터 탐색 → 순환 구조
✅ 메모리 보호 기법
- 상한 레지스터 / 하한 레지스터를 이용하여 접근 범위 제한
- 시스템 호출 시 예외 처리 수행
✅ 요약
- 연속 할당은 고정된 공간에 프로세스를 적재하는 방식
- 내부/외부 단편화는 메모리 사용 비효율을 유발
- 통합/집약은 외부 단편화를 해소하는 기법
- 배치 전략은 메모리 낭비 최소화를 위한 알고리즘
Working Abroad ...