기억장치 배치 전략은 새로 실행할 프로그램을 주기억장치의 빈 영역 가운데 어디에 넣을지 정하는 규칙입니다. 빈 영역이 여럿일 때 어느 영역을 고르느냐에 따라, 빈칸이 있는데도 쓰지 못하는 단편화의 크기가 달라집니다.
프로그램은 주기억장치(메모리)에 올라와야 실행됩니다(프로세스와 스레드). 이 레슨은 주기억장치를 미리 크기가 다른 영역 몇 개로 나눠 두고, 한 영역에 프로그램 하나를 넣는 경우를 봅니다. 영역과 프로그램의 크기가 꼭 맞는 일은 드물어서, 어느 영역에 넣든 빈칸이 생기기 쉽습니다. 아래 그림은 10K 프로그램을 세 전략으로 넣어 남는 칸을 견주고, 이어서 온 20K 프로그램이 들어갈 영역을 찾지 못하는 모습을 보입니다.
1배치 전략 셋 — 최초·최적·최악 적합
세 전략은 빈 영역을 고르는 기준이 다릅니다.
- 최초 적합(first fit): 빈 영역을 앞에서부터 짚어 가다가, 프로그램이 들어가는 첫 영역에 넣습니다.
- 최적 적합(best fit): 빈 영역을 끝까지 견주어, 프로그램이 들어가는 영역 가운데 가장 작은 곳에 넣습니다.
- 최악 적합(worst fit): 빈 영역을 끝까지 견주어, 가장 큰 영역에 넣습니다.
| 가르는 기준 | 최초 적합 | 최적 적합 | 최악 적합 |
|---|---|---|---|
| 고르는 영역 | 들어가는 첫 영역 | 들어가는 영역 중 가장 작은 곳 | 가장 큰 영역 |
| 빈 영역을 끝까지 보나 | 아니다 | 그렇다 | 그렇다 |
| 넣고 남는 칸 | 영역 차례에 따라 다르다 | 가장 작다 | 가장 크다 |
세 전략 모두 프로그램보다 작은 영역은 처음부터 고르지 않습니다. 최적 적합이 '가장 작은 곳'을 고를 때도 들어가는 영역 가운데에서 고릅니다.
배치 전략은 빈 영역이 있을 때 어디에 넣을지를 정합니다. 빈 영역이 없어 이미 들어 있는 것을 내보내야 할 때 무엇을 내보낼지는 교체 전략이 정하고, 페이지 교체 알고리즘에서 배웁니다.
2내부 단편화와 외부 단편화
단편화(fragmentation)는 주기억장치에 빈칸이 있는데도 프로그램이 쓰지 못하는 것입니다. 빈칸이 남는 자리에 따라 둘로 나눕니다.
내부 단편화(internal fragmentation)는 프로그램을 넣은 영역 안에 남은 칸입니다. 한 영역에는 프로그램 하나만 들어가므로, 16K 영역에 10K 프로그램을 넣으면 남은 6K는 다른 프로그램이 쓰지 못합니다.
외부 단편화(external fragmentation)는 프로그램보다 작아서 쓰이지 못하고 비어 있는 영역입니다. 빈 영역을 다 합치면 프로그램보다 커도, 한 영역에 들어가지 못하면 쓸 수 없습니다.
| 가르는 기준 | 내부 단편화 | 외부 단편화 |
|---|---|---|
| 빈칸이 남는 자리 | 프로그램을 넣은 영역 안 | 프로그램을 넣지 못한 빈 영역 |
| 생기는 때 | 영역이 프로그램보다 클 때 | 영역이 프로그램보다 작을 때 |
| 크기 세는 법 | 영역 크기 − 프로그램 크기 | 쓰이지 못한 빈 영역의 크기 |
흩어진 빈 영역은 모아서 다시 쓸 수 있습니다.
- 통합(coalescing): 주소가 이웃한 빈 영역을 하나로 합칩니다. 그림에서 이웃한 영역 1(8K)과 영역 2(16K)를 합치면 24K가 되어 20K 프로그램이 들어갑니다.
- 압축(compaction): 쓰는 영역을 한쪽으로 옮겨, 떨어져 있던 빈 영역까지 큰 덩어리 하나로 모읍니다. 옮겨 적는 동안 프로그램을 멈춰야 해서 시간이 많이 듭니다.
예제
그림의 주기억장치에 10K 프로그램을 넣습니다. 빈 영역은 주소 차례로 영역 1(8K)·영역 2(16K)·영역 4(30K)·영역 5(12K)이고, 영역 3은 사용 중입니다.
| 전략 | 고르는 과정 | 들어가는 영역 | 내부 단편화 |
|---|---|---|---|
| 최초 적합 | 영역 1은 작아 지나치고 영역 2에서 멈춘다 | 영역 2(16K) | 16 − 10 = 6K |
| 최적 적합 | 들어가는 16K·30K·12K 가운데 가장 작은 것 | 영역 5(12K) | 12 − 10 = 2K |
| 최악 적합 | 넷 가운데 가장 큰 것 | 영역 4(30K) | 30 − 10 = 20K |
최악 적합으로 넣은 뒤 20K 프로그램이 오면, 남은 빈 영역 8K·16K·12K가 모두 20K보다 작습니다. 셋을 합치면 36K인데도 들어갈 영역이 없어, 이 36K가 외부 단편화입니다.
시험 포인트
- 필기: 최초 적합은 들어가는 첫 영역, 최적 적합은 들어가는 영역 가운데 가장 작은 영역, 최악 적합은 가장 큰 영역에 넣습니다. 프로그램보다 작은 영역은 셋 모두 고르지 않습니다. 내부 단편화는 넣은 영역 안에 남은 크기(영역 − 프로그램)이고, 외부 단편화는 프로그램보다 작아 쓰이지 못한 빈 영역입니다. 흩어진 빈 영역은 이웃한 것끼리 합치는 통합과, 쓰는 영역을 한쪽으로 옮겨 하나로 모으는 압축으로 다시 씁니다. 빈 영역 목록과 프로그램 크기를 주고 들어갈 영역과 단편화 크기를 묻습니다.
- 실기: 계산 — 들어갈 영역과 단편화 크기를 단위(K)까지 씁니다. 이름은 최초 적합(First Fit), 최적 적합(Best Fit), 최악 적합(Worst Fit), 내부 단편화(Internal Fragmentation), 외부 단편화(External Fragmentation), 통합(Coalescing), 압축(Compaction)으로 씁니다.
확인 문제
1. 빈 영역이 주소 차례로 다음과 같습니다. 13K 프로그램을 최적 적합(best fit)으로 넣을 때 들어가는 영역을 고르세요.
| 영역 | A | B | C | D | E |
|---|---|---|---|---|---|
| 크기 | 9K | 20K | — | 14K | 25K |
| 상태 | 빈 | 빈 | 사용 중 | 빈 | 빈 |
- ① 영역 A(9K)
- ② 영역 B(20K)
- ③ 영역 D(14K)
- ④ 영역 E(25K)
정답
③입니다. 13K가 들어가는 빈 영역은 B(20K)·D(14K)·E(25K)이고, 그 가운데 가장 작은 D에 넣습니다. 남는 칸은 1K입니다.
- ① 빈 영역 가운데 가장 작은 곳을 골랐습니다. 최적 적합은 들어가는 영역 가운데에서 가장 작은 곳을 고르고, 9K에는 13K가 들어가지 않습니다.
- ② 앞에서부터 짚어 처음 들어가는 영역을 골랐습니다. 최초 적합으로 넣을 때의 답입니다.
- ④ 가장 큰 영역을 골랐습니다. 최악 적합으로 넣을 때의 답입니다.
2. 빈 영역이 주소 차례로 18K·30K·12K이고, 11K 프로그램을 넣습니다. (가)~(다)처럼 넣은 방식의 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
- (가) 18K 영역을 보자마자 넣었습니다. 뒤의 30K·12K 영역은 보지 않았습니다.
- (나) 세 영역을 모두 견준 뒤 12K 영역에 넣었습니다.
- (다) 세 영역을 모두 견준 뒤 30K 영역에 넣었습니다.
정답
받는 답: (가) 최초 적합(First Fit) · (나) 최적 적합(Best Fit) · (다) 최악 적합(Worst Fit)
(가)의 실마리는 '들어가는 영역을 만나자 멈췄다', (나)는 '들어가는 것 가운데 남는 칸이 1K로 가장 작은 영역', (다)는 '가장 큰 영역'입니다.
- 틀리는 꼴 최적 적합 — (가)에: 끝까지 견주어 들어가는 것 가운데 가장 작은 곳을 고르는 전략입니다. 그랬다면 12K 영역에 넣었습니다.
- 틀리는 꼴 최악 적합 — (나)에: 가장 큰 영역을 고르는 전략입니다. 12K는 셋 가운데 가장 작습니다.
3. (가)·(나)는 쓰지 못하는 빈칸의 이름이고, (다)·(라)는 그 빈칸을 다시 쓰는 방법의 이름입니다. 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
- (가) 24K 영역에 21K 프로그램을 넣었습니다. 남은 3K는 비어 있지만 다른 프로그램을 받을 수 없습니다.
- (나) 빈 영역 7K·9K·6K가 있는데 15K 프로그램이 어디에도 들어가지 못합니다. 셋을 더하면 22K입니다.
- (다) (나)의 7K와 9K는 주소가 붙어 있어, 둘을 16K 영역 하나로 만들고 15K 프로그램을 넣었습니다.
- (라) 쓰는 영역을 모두 앞쪽으로 옮겨 적었더니, 흩어져 있던 빈 영역 셋이 뒤쪽에 22K 하나로 모였습니다.
정답
받는 답: (가) 내부 단편화(Internal Fragmentation) · (나) 외부 단편화(External Fragmentation) · (다) 통합(Coalescing) · (라) 압축(Compaction)
(가)는 프로그램을 넣은 영역 안에 남은 칸이고, (나)는 더하면 넉넉한데 한 영역에 들지 않아 쓰이지 못한 빈 영역입니다. (다)는 붙어 있던 두 빈 영역을 하나로 만들었을 뿐 아무것도 옮기지 않았고, (라)는 쓰는 영역을 옮겨 떨어져 있던 빈 영역까지 모았습니다.
- 틀리는 꼴 외부 단편화 — (가)에: 프로그램을 넣지 못한 빈 영역입니다. 3K는 프로그램이 들어간 24K 영역 안에 있습니다.
- 틀리는 꼴 내부 단편화 — (나)에: 넣은 영역 안의 남은 칸입니다. (나)의 세 영역에는 아무것도 들어가지 못했습니다.
- 틀리는 꼴 압축 — (다)에: 쓰는 영역을 옮겨 떨어진 빈 영역까지 모으는 방법입니다. (다)는 이미 이웃해 있던 빈 영역만 하나로 만들었습니다.
- 틀리는 꼴 통합 — (라)에: 이웃한 빈 영역만 하나로 만듭니다. (라)는 쓰는 영역을 옮겨 떨어져 있던 빈 영역까지 모았습니다.
4. 그림과 같은 주기억장치에 10K 대신 15K 프로그램을 넣습니다. 세 전략마다 들어가는 영역과 내부 단편화 크기(K)를 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
정답
받는 답: 최초 적합 영역 2(1K) · 최적 적합 영역 2(1K) · 최악 적합 영역 4(15K)
15K가 들어가는 빈 영역은 영역 2(16K)와 영역 4(30K) 둘뿐입니다. 영역 1(8K)과 영역 5(12K)는 15K보다 작아 셋 모두 고르지 않습니다.
| 전략 | 들어가는 영역 | 내부 단편화 |
|---|---|---|
| 최초 적합 | 영역 2(16K) | 1K |
| 최적 적합 | 영역 2(16K) | 1K |
| 최악 적합 | 영역 4(30K) | 15K |
- 틀리는 꼴 최적 적합 영역 5: 10K일 때의 답을 옮겼습니다. 12K에는 15K가 들어가지 않아, 최적 적합도 최초 적합과 같은 영역 2를 고릅니다.
- 틀리는 꼴 최악 적합 영역 4(20K): 10K일 때 남은 칸을 옮겼습니다. 30 − 15 = 15K입니다.
더 보기: 프로그램을 같은 크기의 조각으로 나눠 흩어 놓는 방법은 가상 메모리: 페이징과 세그먼테이션에서 봅니다.