8 운영체제(OS)
프로세스·메모리·디스크 자원을 관리하는 핵심 이론. 계산·순서 문제 단골.
CPU 스케줄링
| 구분 | 기법 | 설명 |
|---|---|---|
| 비선점 (Non-preemptive) | FCFS(FIFO) | 도착 순서대로 처리(선입선출) |
| SJF | 실행시간(버스트) 가장 짧은 작업 우선 | |
| 우선순위(Priority) | 우선순위 높은 작업 우선(기아 발생 가능) | |
| HRN | SJF의 기아 보완, 응답률 높은 순 | |
| 선점 (Preemptive) | SRT | 남은 실행시간 짧은 작업이 선점 |
| RR(Round Robin) | 시간 할당량(Time Quantum)씩 순환 | |
| 다단계 큐(MLQ) | 우선순위별 여러 큐로 분리, 큐 간 이동 없음 | |
| 다단계 피드백 큐(MFQ) | 큐 간 이동 허용, 하위 큐일수록 할당량 증가 |
기출포인트 HRN 우선순위(응답률) 공식 =
(대기시간 + 서비스시간) / 서비스시간. 값이 클수록 우선순위 높음.페이지 교체 알고리즘
| 기법 | 의미 | 교체 대상 |
|---|---|---|
| FIFO | First In First Out | 가장 먼저 적재된 페이지 |
| LRU | Least Recently Used | 가장 오래 참조 안 된 페이지 |
| LFU | Least Frequently Used | 참조 횟수 가장 적은 페이지 |
| NUR | Not Used Recently | 참조·변형 비트로 최근 미사용 추정 |
| OPT(최적) | Optimal | 앞으로 가장 오래 안 쓸 페이지(이론상 최적) |
함정주의 FIFO는 프레임 수를 늘렸는데 오히려 페이지 부재(폴트)가 증가하는 벨레이디의 모순(Belady's Anomaly)이 발생할 수 있다.
교착상태(Deadlock)
암기팁 4대 발생조건 = 상호배제 · 점유와 대기 · 비선점 · 환형 대기 → 상 점 비 환 (4가지 모두 성립해야 발생)
| 발생조건 | 내용 |
|---|---|
| 상호배제(Mutual Exclusion) | 자원을 한 번에 한 프로세스만 사용 |
| 점유와 대기(Hold & Wait) | 자원 점유한 채 다른 자원 대기 |
| 비선점(No Preemption) | 이미 할당된 자원을 강제로 뺏지 못함 |
| 환형 대기(Circular Wait) | 서로 상대 자원을 원형으로 대기 |
| 해결 범주 | 방법 |
|---|---|
| 예방(Prevention) | 4대 조건 중 하나를 미리 제거(사전 차단) |
| 회피(Avoidance) | 안전 상태 유지 — 은행원 알고리즘(Dijkstra) |
| 발견(Detection) | 교착 발생 여부를 자원 할당 그래프로 탐지 |
| 회복(Recovery) | 프로세스 강제 종료·자원 선점으로 복구 |
메모리 관리 · 단편화
| 구분 | 페이징(Paging) | 세그먼테이션(Segmentation) |
|---|---|---|
| 분할 단위 | 고정 크기 페이지 | 논리적 가변 크기 세그먼트 |
| 단편화 | 내부 단편화 발생 | 외부 단편화 발생 |
| 주소 변환 | 페이지 테이블 | 세그먼트 테이블(시작+길이) |
핵심 내부 단편화 = 할당 영역이 요청보다 커서 남는 공간. 외부 단편화 = 남은 총 공간은 충분하나 연속 배치 불가. 해결: 압축(Compaction).
가상메모리
| 개념 | 설명 |
|---|---|
| 지역성(Locality) | 시간 지역성(최근 참조를 곧 재참조) / 공간 지역성(인접 주소 참조) |
| 워킹셋(Working Set) | 일정 시간 동안 자주 참조하는 페이지 집합(주기억장치에 상주시킴) |
| 스래싱(Thrashing) | 페이지 교체가 과도해 처리보다 교체에 시간을 더 쓰는 현상 |
암기팁 스래싱 해결: 워킹셋 확보, 다중 프로그래밍 정도(degree) 조절, 페이지 부재 빈도(PFF) 조정.
디스크 스케줄링
| 기법 | 동작 |
|---|---|
| FCFS | 요청 도착 순서대로 처리 |
| SSTF | 현재 헤드에서 탐색거리 가장 짧은 요청 우선 |
| SCAN | 한 방향 끝까지 이동 후 반대로(엘리베이터 방식) |
| C-SCAN | 한 방향만 처리, 끝에서 시작점으로 복귀 후 재스캔 |
| LOOK | SCAN이되 요청 없으면 끝까지 안 가고 방향 전환 |
| C-LOOK | C-SCAN이되 마지막 요청까지만 이동 후 복귀 |
✅ 자가점검
Q1. 교착상태(Deadlock)의 4대 발생조건은?
상호배제 · 점유와 대기 · 비선점 · 환형 대기 (4가지 모두 성립 시 발생)
Q2. HRN 스케줄링의 우선순위(응답률) 계산식은?
(대기시간 + 서비스시간) / 서비스시간 — 값이 클수록 우선순위가 높다.
Q3. 페이지 교체 알고리즘 5가지와, 벨레이디 모순이 발생하는 기법은?
FIFO · LRU · LFU · NUR · OPT(최적). 벨레이디(Belady)의 모순은 FIFO에서 발생한다.