기억장치 관리와 페이지 교체
쉽게 말하면
메모리는 한정돼 있어서 운영체제가 프로그램을 어디에 둘지, 꽉 차면 무엇을 빼낼지 정해야 해요. 빈자리를 고르는 방법으로 처음 맞는 곳(최초 적합), 가장 딱 맞는 곳(최적 적합), 가장 넓은 곳(최악 적합)이 있어요. 프로그램을 같은 크기 조각(페이지)으로 나눠 두고, 새 페이지를 넣을 자리가 없으면 오래된 것(FIFO)이나 최근에 안 쓴 것(LRU)을 빼내요. 시험에는 페이지 부재 횟수를 세는 문제가 꼭 나와요.
시험용 정의
기억장치 관리 전략은 반입(언제), 배치(어디에), 교체(무엇을 내보낼지)다. 배치 전략: 최초 적합(First Fit, 처음 맞는 곳), 최적 적합(Best Fit, 단편화가 가장 작게 남는 곳), 최악 적합(Worst Fit, 가장 큰 곳). 분할 영역이 프로그램보다 커서 남는 빈 공간은 내부 단편화, 빈 영역이 프로그램보다 작아 못 쓰는 것은 외부 단편화다. 가상 기억장치는 보조기억장치를 주기억장치처럼 쓰며 페이징(같은 크기 페이지로 나눔, 내부 단편화 가능)과 세그멘테이션(논리 단위 크기로 나눔, 외부 단편화 가능)이 있다. 필요한 페이지가 메모리에 없으면 페이지 부재가 나고, 교체 알고리즘 OPT(앞으로 가장 오래 안 쓸 페이지, 이론상 최적), FIFO(가장 먼저 들어온 페이지), LRU(가장 오랫동안 쓰지 않은 페이지), LFU(사용 횟수가 가장 적은 페이지), NUR(참조·변형 비트 이용)으로 교체한다. 프로세스는 일부 페이지를 집중적으로 쓰는 지역성을 가지며, 자주 쓰는 페이지 집합을 워킹 셋, 페이지 교체가 너무 잦아 실행보다 교체에 시간을 더 쓰는 현상을 스래싱이라 한다.
비유로 이해하기
책상(메모리)이 좁아 책장(디스크)에서 책을 꺼내 쓴다. 책상이 꽉 차면 무엇을 책장에 돌려놓을까? 가장 먼저 가져온 책(FIFO), 가장 오래 펼치지 않은 책(LRU), 펼친 횟수가 가장 적은 책(LFU). 책을 바꾸느라 공부를 못 하면 스래싱이다.
자세히
먼저 알아 둘 말
| 말 | 뜻 |
|---|---|
| 페이지 / 프레임 | 가상 메모리를 같은 크기로 나눈 조각 / 실제 메모리의 같은 크기 칸 |
| 페이지 부재 | 참조한 페이지가 메모리 프레임에 없는 것 (페이지 폴트) |
| 단편화 | 메모리 빈 공간이 쓸모없이 조각난 것 |
| 지역성 | 일정 시간 동안 일부 페이지만 집중적으로 참조하는 성질 (시간·공간 지역성) |
| 워킹 셋 | 일정 시간 동안 자주 참조하는 페이지들의 집합 |
| 스래싱 | 페이지 교체가 너무 잦아 CPU 이용률이 급격히 떨어지는 현상 |
페이지 교체 계산: 참조열 7 0 1 2 0 3 0 4 2 3, 프레임 3개
| 알고리즘 | 부재 횟수 | 과정 요약 |
|---|---|---|
| FIFO | 9 | 7 0 1 채움 → 2가 7 밀어냄 → 0 적중 → 3이 0, 0이 1, 4가 2, 2가 3, 3이 0 밀어냄 |
| LRU | 8 | 7 0 1 → 2가 7 → 0 적중 → 3이 1 → 0 적중 → 4가 2 → 2가 3 → 3이 0 |
| OPT | 6 | 앞으로 가장 늦게 쓸 페이지를 교체 (이론상 최소) |
푸는 요령
- 처음 프레임이 빌 때까지 들어오는 페이지도 부재로 센다
- FIFO는 들어온 순서만 본다. 적중해도 순서가 안 바뀐다
- LRU는 적중하면 '가장 최근에 쓴 것'으로 갱신한다
- 벨레이디의 모순: FIFO에서 프레임 수를 늘렸는데 부재가 더 늘어나는 현상 (예: 1 2 3 4 1 2 5 1 2 3 4 5는 3프레임 9번, 4프레임 10번)
페이징 vs 세그멘테이션
| 구분 | 페이징 | 세그멘테이션 |
|---|---|---|
| 나누는 단위 | 같은 크기 페이지 | 논리적 단위(함수, 데이터), 크기 다름 |
| 단편화 | 내부 단편화 가능 (외부 없음) | 외부 단편화 가능 (내부 없음) |
| 주소 변환 | 페이지 맵 테이블 | 세그먼트 맵 테이블 |
시험에 이렇게 나와요
- 배치 전략 → 최초 적합(처음 맞는 곳), 최적 적합(가장 딱 맞는 곳), 최악 적합(가장 큰 곳), 단편화 크기 계산
- 페이지 교체 → FIFO·LRU·LFU·OPT·NUR로 부재 횟수 세기 (LUF는 없음)
- 자주 참조하는 페이지 집합 → 워킹 셋 / 교체에 시간을 더 쓰는 현상 → 스래싱
- 고정 크기로 나눔 → 페이징, 논리 단위로 나눔 → 세그먼테이션
- 세그먼트 주소 변환 → 시작 주소 + 변위
- 페이지가 작아지면 → 내부 단편화 감소, 페이지 맵 테이블 증가, 입출력 시간 증가
확인 문제
Q1. 빈 공간 10K, 4K, 20K, 18K가 순서대로 있다. 12K 프로그램을 최적 적합으로 배치하면 어디에 들어갈까요?
- 10K
- 4K
- 20K
- 18K
정답 보기
4번 18K
최적 적합은 들어갈 수 있는 곳 중 남는 공간이 가장 작은 곳. 12K가 들어가는 곳은 20K(8K 남음)와 18K(6K 남음) → 18K. 최초 적합이면 처음 맞는 20K, 최악 적합이면 가장 큰 20K.
Q2. 참조열 1 2 3 2 1 4 1 5 2 1, 프레임 3개일 때 LRU의 페이지 부재 횟수는?
- 5
- 6
- 7
- 8
정답 보기
2번 6
1 2 3 채움(3), 2·1 적중, 4가 3 교체(4), 1 적중, 5가 2 교체(5), 2가 4 교체(6), 1 적중 → 6번.
Q3. 프로세스가 실행보다 페이지 교체에 더 많은 시간을 써서 성능이 급격히 떨어지는 현상은?
- 지역성
- 워킹 셋
- 단편화
- 스래싱
정답 보기
4번 스래싱
스래싱이다. 페이지 부재가 너무 자주 일어나 실제 일보다 교체에 시간을 다 쓴다. 워킹 셋은 자주 쓰는 페이지 묶음으로 스래싱을 막는 방법이다.
Q4. 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘은?
- LFU
- LRU
- OPT
- FIFO
정답 보기
2번 LRU
Least Recently Used.
Q5. 세그멘테이션 기법에서 주로 생기는 단편화는?
- 내부 단편화
- 단편화가 생기지 않는다
- 외부 단편화
- 논리 단편화
정답 보기
3번 외부 단편화
크기가 제각각이라 사이사이 작은 빈 공간이 남는다.
헷갈리기 쉬운 O·X
OPT 알고리즘은 실제 운영체제에서 쉽게 구현해 쓴다.
정답 보기
X 앞으로의 참조를 알아야 해 실제 구현은 어렵다. 다른 알고리즘 성능 비교 기준으로 쓴다.
FIFO에서 프레임 수를 늘리면 페이지 부재가 오히려 늘 수 있다.
정답 보기
O 벨레이디의 모순.
페이징 기법에서는 외부 단편화가 주로 생긴다.
정답 보기
X 페이징은 내부 단편화가 생길 수 있다.