기억장치 관리는 여러 프로세스가 제한된 주기억장치를 안정적이고 효율적으로 사용할 수 있도록 저장 공간을 할당하고 회수하는 운영체제의 기능입니다. 운영체제는 가상기억장치를 통해 프로세스마다 독립적인 주소 공간을 제공하고, 필요한 경우 보조기억장치를 활용하여 실제 주기억장치보다 큰 논리적 주소 공간을 사용할 수 있도록 합니다.
이 장에서는 반입·배치·교체 전략을 구분하고, 가상기억장치를 구현하는 페이징과 세그멘테이션의 차이를 정리합니다. 또한 지역성, 워킹 세트, 페이지 부재와 스래싱의 관계를 살펴보고, FIFO와 LRU 페이지 교체 과정에서 페이지 부재 횟수를 계산하는 방법을 설명합니다.
이 장의 핵심 내용
- 반입 전략은 프로그램이나 데이터를 언제 주기억장치로 가져올지를 결정합니다.
- 배치 전략은 주기억장치의 빈 공간 가운데 어느 위치에 프로그램을 배치할지를 결정합니다.
- 교체 전략은 빈 페이지 프레임이 없을 때 어떤 페이지를 내보낼지를 결정합니다.
- 가상기억장치는 보조기억장치를 활용하여 실제 주기억장치보다 큰 논리적 주소 공간을 제공합니다.
- 페이징은 고정 크기의 페이지와 페이지 프레임을 사용하고, 세그멘테이션은 의미에 따라 나눈 가변 크기의 세그먼트를 사용합니다.
- 시간 지역성과 공간 지역성은 프로그램이 일부 주소를 집중적으로 참조하는 경향을 설명합니다.
- 워킹 세트는 일정 기간 동안 프로세스가 자주 참조하는 페이지의 집합입니다.
- 페이지 부재가 지나치게 증가하여 실제 작업보다 페이지 교체에 더 많은 시간을 사용하는 현상을 스래싱이라고 합니다.
기억장치 관리는 왜 필요할까?
프로세스가 실행되려면 프로그램 코드와 실행에 필요한 데이터가 주기억장치에 적재되어야 합니다. 그러나 주기억장치의 용량은 제한되어 있고 여러 프로세스가 동시에 메모리를 요구하므로, 운영체제는 각 프로세스에 필요한 공간을 할당하고 사용이 끝난 공간을 회수해야 합니다.
기억장치 관리에서는 프로그램을 언제 적재할지, 메모리의 어느 위치에 배치할지, 공간이 부족할 때 어떤 내용을 내보낼지를 결정합니다. 이러한 결정은 각각 반입 전략, 배치 전략과 교체 전략으로 구분할 수 있습니다.
| 관리 전략 | 핵심 질문 | 대표 기법 |
|---|---|---|
| 반입 전략 | 프로그램이나 페이지를 언제 주기억장치로 가져올 것인가? | 요구 반입, 예상 반입 |
| 배치 전략 | 주기억장치의 어느 빈 공간에 배치할 것인가? | 최초 적합, 최적 적합, 최악 적합 |
| 교체 전략 | 공간이 부족할 때 어떤 페이지를 내보낼 것인가? | OPT, FIFO, LRU, LFU, NUR·NRU, Second Chance |
반입 전략이란 무엇인가?
반입 전략(Fetch Strategy)은 보조기억장치에 있는 프로그램이나 페이지를 어느 시점에 주기억장치로 가져올지를 결정합니다. 대표적인 방식은 요구 반입과 예상 반입입니다.
요구 반입
프로세스가 실제로 특정 페이지를 요구했을 때 해당 페이지를 주기억장치로 가져오는 방식입니다. 사용하지 않는 페이지를 미리 적재하지 않으므로 메모리를 절약할 수 있습니다.
필요한 페이지가 메모리에 없으면 페이지 부재가 발생하여 보조기억장치에서 페이지를 읽어 와야 합니다.
예상 반입
앞으로 필요할 가능성이 높은 프로그램이나 페이지를 미리 주기억장치로 가져오는 방식입니다. 순차적으로 접근하는 데이터에서는 대기 시간을 줄일 수 있습니다.
예측이 틀리면 사용하지 않는 페이지가 메모리를 차지하고 불필요한 입출력이 발생할 수 있습니다.
| 비교 항목 | 요구 반입 | 예상 반입 |
|---|---|---|
| 반입 시점 | 실제 참조가 발생한 시점 | 앞으로 참조할 것으로 예상되는 시점 이전 |
| 장점 | 불필요한 페이지 적재 감소 | 예측이 맞으면 페이지 부재와 대기 시간 감소 |
| 한계 | 최초 참조 시 페이지 부재 발생 | 예측 실패 시 메모리와 입출력 낭비 |
| 관련 개념 | 요구 페이징 | 미리 읽기, 선행 반입 |
배치 전략이란 무엇인가?
배치 전략(Placement Strategy)은 연속된 메모리 공간을 할당할 때 여러 빈 공간 가운데 어느 공간에 프로그램이나 데이터를 배치할지 결정하는 방식입니다. 최초 적합, 최적 적합과 최악 적합이 대표적입니다.
| 배치 전략 | 선택 기준 | 장점 | 한계 |
|---|---|---|---|
| 최초 적합 First Fit | 앞에서부터 검색하여 처음 발견한 충분한 크기의 공간 | 검색이 빠르고 구현이 단순함 | 앞부분에 작은 빈 공간이 많이 남을 수 있음 |
| 최적 적합 Best Fit | 할당 가능한 공간 중 요청 크기와 가장 가까운 작은 공간 | 할당 직후 남는 공간을 최소화함 | 전체 공간을 많이 검색하며 매우 작은 조각이 생길 수 있음 |
| 최악 적합 Worst Fit | 할당 가능한 공간 중 가장 큰 공간 | 할당 후에도 비교적 큰 빈 공간을 남길 수 있음 | 가장 큰 공간을 빠르게 소모하고 검색 비용이 발생함 |
혼동 주의: 최적 적합의 ‘최적’은 항상 전체 시스템 성능이 가장 우수하다는 의미가 아닙니다. 요청 크기에 가장 가까운 빈 공간을 선택한다는 의미이며, 작은 외부 단편화를 많이 만들 수 있습니다.
내부 단편화와 외부 단편화
| 구분 | 내부 단편화 | 외부 단편화 |
|---|---|---|
| 발생 위치 | 할당된 공간의 내부 | 할당되지 않은 공간 사이 |
| 발생 원인 | 고정된 할당 단위가 실제 요청보다 큼 | 가변 크기 할당과 해제를 반복하면서 빈 공간이 흩어짐 |
| 대표 관련 기법 | 고정 분할, 페이징의 마지막 페이지 | 가변 분할, 연속 메모리 할당, 세그멘테이션 |
| 특징 | 공간은 할당됐지만 일부가 사용되지 않음 | 빈 공간의 합은 충분해도 연속된 큰 공간을 확보하기 어려움 |
페이지 교체 전략이란 무엇인가?
페이지 교체 전략(Page Replacement Strategy)은 필요한 페이지를 주기억장치로 가져와야 하지만 사용 가능한 페이지 프레임이 없을 때, 현재 적재된 페이지 가운데 어떤 페이지를 내보낼지 결정하는 방식입니다.
교체 대상으로 선택된 페이지가 수정된 상태라면 보조기억장치에 변경 내용을 기록한 뒤 새로운 페이지를 적재해야 할 수 있습니다. 따라서 적절한 교체 전략은 페이지 부재와 디스크 입출력을 줄이는 데 중요합니다.
| 교체 전략 | 교체 기준 | 주요 특징 |
|---|---|---|
| OPT | 앞으로 가장 오랫동안 참조되지 않을 페이지 | 이론적으로 페이지 부재가 가장 적지만 미래 참조를 알아야 하므로 실제 구현에는 사용하기 어려움 |
| FIFO | 주기억장치에 가장 먼저 들어온 페이지 | 구현이 단순하지만 최근 사용 여부를 반영하지 않음 |
| LRU | 가장 오랫동안 참조되지 않은 페이지 | 지역성을 반영하지만 정확한 사용 순서 관리 비용이 큼 |
| LFU | 참조 횟수가 가장 적은 페이지 | 사용 빈도를 반영하지만 과거에 많이 사용된 페이지가 오래 남을 수 있음 |
| NUR·NRU | 참조 비트와 수정 비트를 이용해 최근에 사용되지 않은 페이지 | LRU를 비교적 적은 비용으로 근사함 |
| Second Chance | FIFO 순서를 따르되 참조된 페이지에는 한 번 더 기회를 부여 | 참조 비트를 이용해 FIFO의 단점을 완화함 |
OPT 교체 전략
OPT(Optimal replacement)는 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체합니다. 주어진 페이지 참조열에서 이론적으로 가장 적은 페이지 부재를 발생시키므로 다른 알고리즘의 성능을 비교하는 기준으로 사용할 수 있습니다.
실제 실행 중에는 미래의 페이지 참조 순서를 완전히 알 수 없으므로 온라인 운영체제의 교체 알고리즘으로 직접 구현하기는 어렵습니다.
FIFO 교체 전략
FIFO(First In, First Out)는 메모리에 가장 먼저 적재된 페이지를 가장 먼저 교체합니다. 페이지의 적재 순서만 관리하면 되므로 구현이 간단하지만, 자주 사용 중인 페이지도 오래 적재되었다는 이유로 교체될 수 있습니다.
벨레이디의 모순: FIFO에서는 페이지 프레임 수를 늘렸는데도 특정 참조열에서 페이지 부재 횟수가 오히려 증가할 수 있습니다. 이를 벨레이디의 모순 또는 Belady’s Anomaly라고 합니다.
LRU 교체 전략
LRU(Least Recently Used)는 현재 시점을 기준으로 가장 오랫동안 사용되지 않은 페이지를 교체합니다. 최근에 사용한 페이지는 다시 사용될 가능성이 높다는 시간 지역성을 이용합니다.
정확한 LRU를 구현하려면 페이지마다 마지막 참조 시점이나 참조 순서를 관리해야 하므로 추가적인 하드웨어 또는 소프트웨어 비용이 필요합니다.
LFU 교체 전략
LFU(Least Frequently Used)는 참조 횟수가 가장 적은 페이지를 교체합니다. 자주 사용된 페이지를 메모리에 유지할 수 있지만, 과거에 많이 사용되고 현재는 사용하지 않는 페이지가 높은 참조 횟수 때문에 계속 남을 수 있습니다.
NUR·NRU 교체 전략
NUR 또는 NRU는 페이지의 참조 비트와 수정 비트를 이용해 최근에 사용되지 않은 페이지를 구분합니다. 참조되지 않았고 수정되지 않은 페이지를 우선적으로 교체하고, 최근에 참조되었거나 수정된 페이지는 상대적으로 나중에 교체합니다.
| 참조 비트 | 수정 비트 | 상태 | 교체 우선순위 |
|---|---|---|---|
| 0 | 0 | 최근에 참조되지 않았고 수정되지 않음 | 가장 높음 |
| 0 | 1 | 최근에 참조되지 않았지만 수정됨 | 높음 |
| 1 | 0 | 최근에 참조되었지만 수정되지 않음 | 낮음 |
| 1 | 1 | 최근에 참조되었고 수정됨 | 가장 낮음 |
Second Chance 교체 전략
Second Chance는 FIFO 순서를 기본으로 사용하면서 참조 비트가 설정된 페이지에는 한 번 더 메모리에 남을 기회를 부여합니다. 가장 오래된 페이지의 참조 비트가 0이면 교체하고, 1이면 비트를 0으로 바꾼 뒤 다음 페이지를 검사합니다.
가상기억장치란 무엇인가?
가상기억장치(Virtual Memory)는 프로그램이 실제 주기억장치보다 큰 연속된 주소 공간을 사용하는 것처럼 보이게 하는 기억장치 관리 기법입니다. 프로그램의 전체 내용을 항상 주기억장치에 적재하지 않고 현재 필요한 일부만 적재하며, 나머지는 보조기억장치에 보관할 수 있습니다.
프로세스는 가상주소를 사용하고, 운영체제와 하드웨어의 메모리 관리 장치는 가상주소를 실제 물리주소로 변환합니다. 가상주소와 물리주소의 대응 관계는 페이지 테이블이나 세그먼트 테이블과 같은 자료구조에 저장됩니다.
장점
- 물리 메모리보다 큰 프로그램 실행 가능
- 필요한 부분만 적재하여 메모리 이용률 향상
- 프로세스별 독립적인 주소 공간 제공
- 프로세스 간 보호와 메모리 공유 지원
비용과 한계
- 주소 변환을 위한 페이지 테이블 필요
- 페이지 부재 발생 시 보조기억장치 접근 지연
- 페이지 교체와 관리에 따른 운영체제 부담
- 프레임이 부족하면 스래싱 발생 가능
페이징 기법은 어떻게 동작할까?
페이징(Paging)은 프로세스의 가상주소 공간을 동일한 크기의 페이지로 나누고, 물리 메모리를 같은 크기의 페이지 프레임으로 나누어 페이지를 프레임에 배치하는 방식입니다.
가상주소는 페이지 번호와 페이지 내부 위치를 나타내는 오프셋으로 구분됩니다. 페이지 번호는 페이지 테이블을 통해 물리 프레임 번호로 변환되고, 오프셋은 그대로 사용되어 최종 물리주소를 구성합니다.
| 구분 | 가상기억장치 | 주기억장치 |
|---|---|---|
| 분할 단위 | 페이지 | 페이지 프레임 |
| 크기 | 모든 페이지가 동일 | 페이지와 동일한 고정 크기 |
| 배치 | 논리적으로 연속 | 물리적으로 떨어진 프레임에 배치 가능 |
| 주소 변환 | 페이지 번호와 오프셋 사용 | 프레임 번호와 오프셋으로 변환 |
페이지 테이블의 역할
- 가상주소에서 페이지 번호를 분리합니다.
- 페이지 테이블에서 해당 페이지가 적재된 물리 프레임 번호를 찾습니다.
- 프레임 번호와 페이지 내부 오프셋을 결합하여 물리주소를 만듭니다.
- 페이지가 메모리에 없으면 페이지 부재를 발생시켜 운영체제가 필요한 페이지를 적재하도록 합니다.
주소 변환 보조 장치: 주소 변환 보조 장치(Translation Lookaside Buffer, TLB)는 최근 사용한 페이지 테이블 항목을 저장하는 고속 캐시입니다. TLB에서 주소 변환 정보를 찾으면 매번 주기억장치의 페이지 테이블을 조회하는 비용을 줄일 수 있습니다.
페이지 크기가 달라지면 무엇이 바뀔까?
| 비교 항목 | 페이지 크기가 큰 경우 | 페이지 크기가 작은 경우 |
|---|---|---|
| 페이지 테이블 | 페이지 수가 줄어 테이블 항목 수가 감소 | 페이지 수가 늘어 테이블 항목 수가 증가 |
| 내부 단편화 | 사용하지 않는 페이지 내부 공간이 커질 수 있음 | 상대적으로 감소 |
| 한 번의 입출력량 | 한 번에 더 많은 데이터를 이동 | 한 번에 더 적은 데이터를 이동 |
| 지역성 활용 | 순차 접근에서는 주변 데이터를 함께 가져오는 데 유리 | 필요한 부분을 세밀하게 적재하는 데 유리 |
| 불필요한 데이터 반입 | 증가할 수 있음 | 감소할 수 있음 |
| 관리 부담 | 페이지 수가 적어 관리 항목 감소 | 페이지와 페이지 테이블 항목 증가 |
표현 주의: 페이지 크기가 크면 디스크 접근 횟수가 반드시 항상 감소한다고 단정할 수는 없습니다. 순차 접근에서는 입출력 횟수를 줄일 수 있지만, 실제로 사용하지 않는 데이터까지 읽어 오는 비용이 증가할 수 있습니다.
세그멘테이션 기법은 어떻게 동작할까?
세그멘테이션(Segmentation)은 프로그램을 코드, 데이터, 스택, 함수와 배열 등 의미가 있는 논리적 단위인 세그먼트로 나누어 관리하는 방식입니다. 각 세그먼트는 내용에 따라 서로 다른 크기를 가질 수 있습니다.
세그먼트 주소는 세그먼트 번호와 세그먼트 내부 위치를 나타내는 오프셋으로 구성됩니다. 세그먼트 테이블에는 각 세그먼트가 물리 메모리에서 시작하는 기준 주소와 세그먼트의 길이 또는 한계값이 저장됩니다.
장점
- 프로그램의 논리적 구조를 그대로 반영
- 세그먼트별 보호 권한 설정 가능
- 코드와 데이터의 선택적 공유가 편리함
한계
- 세그먼트 크기가 서로 다름
- 연속 공간에 배치할 때 외부 단편화 가능
- 빈 공간 검색과 압축이 필요할 수 있음
페이징과 세그멘테이션은 무엇이 다를까?
| 비교 항목 | 페이징 | 세그멘테이션 |
|---|---|---|
| 분할 기준 | 물리적 관리 편의를 위한 고정 크기 | 프로그램의 의미와 논리적 구조 |
| 분할 단위 | 페이지 | 세그먼트 |
| 단위 크기 | 동일한 고정 크기 | 서로 다른 가변 크기 |
| 주소 구성 | 페이지 번호 + 오프셋 | 세그먼트 번호 + 오프셋 |
| 관리 자료구조 | 페이지 테이블 | 세그먼트 테이블 |
| 주요 단편화 | 내부 단편화 | 외부 단편화 |
| 사용자 관점 | 페이지 경계를 일반적으로 인식하지 않음 | 코드·데이터·스택 등 논리 단위를 인식할 수 있음 |
| 보호와 공유 | 페이지 단위로 가능 | 의미 있는 논리 단위로 설정하기 편리함 |
지역성이란 무엇인가?
지역성(Locality)은 프로그램이 실행되는 동안 모든 메모리 주소를 균등하게 참조하는 것이 아니라, 일정한 시간 동안 특정 주소나 그 주변 주소를 집중적으로 참조하는 경향을 의미합니다.
운영체제는 지역성을 이용해 가까운 미래에 다시 사용할 가능성이 높은 페이지를 주기억장치에 유지합니다. 캐시와 가상기억장치가 효과적으로 동작할 수 있는 중요한 근거이기도 합니다.
| 구분 | 시간 지역성 | 공간 지역성 |
|---|---|---|
| 의미 | 최근에 참조한 주소를 가까운 미래에 다시 참조할 가능성이 높음 | 참조한 주소와 가까운 주변 주소를 곧 참조할 가능성이 높음 |
| 대표 사례 | 반복문, 함수 재호출, 변수 재사용, 스택 사용 | 배열 순차 탐색, 명령어 순차 실행, 연속 데이터 접근 |
| 관련 교체 기법 | LRU | 페이지 단위 반입과 미리 읽기 |
워킹 세트란 무엇인가?
워킹 세트(Working Set)는 프로세스가 최근 일정한 시간 또는 일정한 페이지 참조 구간 동안 한 번 이상 참조한 페이지의 집합입니다. 프로세스가 원활하게 실행되려면 현재 워킹 세트에 포함된 페이지를 가능한 한 주기억장치에 유지해야 합니다.
프로세스에 할당된 페이지 프레임 수가 워킹 세트를 수용하기에 부족하면 필요한 페이지가 계속 교체되어 페이지 부재가 급격히 증가할 수 있습니다.
페이지 부재란 무엇인가?
이 글에서 다루는 요구 페이징의 페이지 부재(Page Fault)는 프로세스가 참조한 가상 페이지가 현재 주기억장치에 적재되어 있지 않을 때 발생하는 사건입니다. 요구 페이징 환경에서는 정상적인 메모리 관리 과정에서 페이지 부재가 발생할 수 있습니다.
유효한 가상주소에 대한 페이지 부재가 발생하면 운영체제는 필요한 페이지를 보조기억장치에서 가져오고 페이지 테이블을 수정한 뒤 중단했던 명령을 다시 실행합니다. 허용되지 않은 주소를 참조한 경우에는 단순한 요구 페이징 처리가 아니라 접근 오류로 처리될 수 있습니다.
- 프로세스가 가상주소의 페이지를 참조합니다.
- 페이지 테이블을 확인한 결과 해당 페이지가 주기억장치에 없음을 발견합니다.
- 하드웨어가 페이지 부재 예외를 발생시켜 운영체제로 제어를 넘깁니다.
- 운영체제가 주소 참조의 유효성을 확인합니다.
- 빈 프레임을 찾거나 페이지 교체 알고리즘으로 희생 페이지를 선택합니다.
- 필요하면 수정된 희생 페이지를 보조기억장치에 기록합니다.
- 요청된 페이지를 주기억장치로 읽어 옵니다.
- 페이지 테이블과 관련 주소 변환 정보를 갱신합니다.
- 중단되었던 프로세스의 명령을 다시 실행합니다.
페이지 부재율
페이지 참조 전체에서 페이지 부재가 어느 정도 발생했는지는 다음과 같이 계산할 수 있습니다.
페이지 부재율이 높으면 보조기억장치 접근이 자주 발생해 프로세스의 실제 실행 시간이 크게 늘어날 수 있습니다.
스래싱이란 무엇인가?
스래싱(Thrashing)은 프로세스에 필요한 페이지 프레임이 부족하여 페이지 부재와 페이지 교체가 지나치게 자주 발생하고, 실제 명령 실행보다 페이지를 보조기억장치와 주기억장치 사이에서 이동하는 데 더 많은 시간을 사용하는 현상입니다.
프로세스의 워킹 세트보다 적은 프레임을 할당하거나 너무 많은 프로세스를 동시에 실행하면 스래싱이 발생할 수 있습니다. 스래싱이 심해지면 디스크 입출력은 증가하지만 CPU 이용률과 처리량은 오히려 감소합니다.
| 구분 | 페이지 부재 | 스래싱 |
|---|---|---|
| 의미 | 참조한 페이지가 현재 주기억장치에 없는 사건 | 페이지 부재와 교체가 과도하게 반복되는 상태 |
| 발생 여부 | 요구 페이징에서 정상적으로 발생 가능 | 시스템 성능이 심각하게 저하된 비정상적 상황 |
| 주요 원인 | 필요한 페이지가 아직 적재되지 않음 | 프레임 부족, 지나친 다중 프로그래밍, 워킹 세트 미수용 |
| 영향 | 한 번의 페이지 적재 지연 | 지속적인 입출력 증가와 CPU 이용률 감소 |
| 대응 | 페이지를 적재하고 실행 재개 | 프레임 추가 할당, 프로세스 수 조절, 워킹 세트 관리 |
시험 포인트: 프로세스가 일정 기간 동안 자주 참조하는 페이지의 집합은 워킹 세트이고, 페이지 교체가 지나치게 증가하여 실제 처리보다 페이지 이동 시간이 커지는 현상은 스래싱입니다.
LRU 페이지 교체 계산
페이지 프레임이 3개이고 페이지 참조열이 다음과 같다고 가정합니다.
페이지 참조열: C → D → E → B → D → E → C
교체 방식: LRU — 가장 오랫동안 사용하지 않은 페이지를 교체
| 페이지 참조 | C | D | E | B | D | E | C |
|---|---|---|---|---|---|---|---|
| 프레임 1 | C | C | C | B | B | B | C |
| 프레임 2 | — | D | D | D | D | D | D |
| 프레임 3 | — | — | E | E | E | E | E |
| 페이지 부재 | 발생 | 발생 | 발생 | 발생 | — | — | 발생 |
FIFO 페이지 교체 계산
페이지 프레임이 3개이고 페이지 참조열이 다음과 같다고 가정합니다.
페이지 참조열: 4 → 3 → 4 → 1 → 5 → 4 → 3 → 5
교체 방식: FIFO — 주기억장치에 가장 먼저 적재된 페이지부터 교체
| 페이지 참조 | 4 | 3 | 4 | 1 | 5 | 4 | 3 | 5 |
|---|---|---|---|---|---|---|---|---|
| 프레임 1 | 4 | 4 | 4 | 4 | 5 | 5 | 5 | 5 |
| 프레임 2 | — | 3 | 3 | 3 | 3 | 4 | 4 | 4 |
| 프레임 3 | — | — | — | 1 | 1 | 1 | 3 | 3 |
| 페이지 부재 | 발생 | 발생 | — | 발생 | 발생 | 발생 | 발생 | — |
시험에서 자주 혼동되는 개념
반입과 배치
반입은 보조기억장치의 내용을 언제 가져올지를 결정하고, 배치는 가져온 내용을 주기억장치의 어느 위치에 둘지를 결정합니다.
최적 적합과 최악 적합
최적 적합은 요청을 수용할 수 있는 가장 작은 공간을 선택하고, 최악 적합은 가장 큰 빈 공간을 선택합니다.
FIFO와 LRU
FIFO는 가장 먼저 적재된 페이지를 교체하고, LRU는 가장 오랫동안 참조되지 않은 페이지를 교체합니다.
LRU와 LFU
LRU는 마지막으로 사용한 시점을 기준으로 하고, LFU는 누적 참조 횟수를 기준으로 합니다.
페이징과 세그멘테이션
페이징은 고정 크기로 나누는 물리적 관리 방식이고, 세그멘테이션은 코드·데이터·스택과 같은 논리적 단위로 나누는 방식입니다.
페이지 부재와 스래싱
페이지 부재는 필요한 페이지가 메모리에 없는 한 번의 사건이고, 스래싱은 이러한 부재와 교체가 지나치게 반복되는 상태입니다.
지역성과 워킹 세트
지역성은 특정 주소를 집중 참조하는 경향이고, 워킹 세트는 일정 기간 동안 실제로 자주 참조한 페이지의 집합입니다.
내부와 외부 단편화
내부 단편화는 할당된 공간 안의 낭비이고, 외부 단편화는 할당되지 않은 빈 공간이 여러 곳에 흩어진 상태입니다.
이번 장 핵심 요약
- 반입 전략은 주기억장치로 가져올 시점을 결정하며 요구 반입과 예상 반입으로 구분합니다.
- 배치 전략은 빈 공간을 선택하는 방식이며 최초 적합·최적 적합·최악 적합이 있습니다.
- 최초 적합은 처음 발견한 공간, 최적 적합은 가장 작은 적합 공간, 최악 적합은 가장 큰 공간을 선택합니다.
- OPT는 미래에 가장 늦게 참조될 페이지, FIFO는 가장 먼저 들어온 페이지를 교체합니다.
- LRU는 가장 오랫동안 참조되지 않은 페이지, LFU는 참조 횟수가 가장 적은 페이지를 교체합니다.
- NUR·NRU는 참조 비트와 수정 비트를 사용하고, Second Chance는 FIFO에 참조 비트를 추가합니다.
- 가상기억장치는 주소 변환과 보조기억장치를 이용해 물리 메모리보다 큰 논리적 주소 공간을 제공합니다.
- 페이징은 고정 크기의 페이지와 프레임을 사용하고, 세그멘테이션은 가변 크기의 논리 단위를 사용합니다.
- 페이징은 주로 내부 단편화, 세그멘테이션은 연속 배치 시 외부 단편화와 관련됩니다.
- 시간 지역성은 최근 주소의 재사용, 공간 지역성은 주변 주소의 연속 참조를 의미합니다.
- 워킹 세트는 최근 일정 기간 동안 자주 참조한 페이지의 집합입니다.
- 페이지 부재는 참조 페이지가 메모리에 없는 사건이며, 스래싱은 페이지 교체가 과도하게 반복되는 현상입니다.
- 주어진 LRU 예제에서는 페이지 부재가 5회, FIFO 예제에서는 6회 발생합니다.
복습 문제
반입 전략·배치 전략·교체 전략은 각각 무엇을 결정할까?
반입 전략은 언제 주기억장치로 가져올지, 배치 전략은 어느 위치에 둘지, 교체 전략은 공간이 부족할 때 어떤 내용을 내보낼지를 결정합니다.
입력된 작업을 가장 큰 빈 공간에 배치하는 전략은?
최악 적합(Worst Fit)입니다.
최초 적합과 최적 적합의 차이는?
최초 적합은 앞에서부터 검색해 처음 발견한 충분한 공간을 선택하고, 최적 적합은 요청을 수용할 수 있는 공간 중 가장 작은 공간을 선택합니다.
미래에 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘은?
OPT 또는 최적 페이지 교체 알고리즘입니다.
가장 먼저 적재된 페이지를 가장 먼저 교체하는 알고리즘은?
FIFO입니다.
가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘은?
LRU입니다.
페이지마다 참조 비트와 수정 비트를 사용해 교체 대상을 선택하는 알고리즘은?
NUR 또는 NRU입니다.
페이징과 세그멘테이션의 가장 중요한 차이는?
페이징은 프로그램을 동일한 크기의 페이지로 나누고, 세그멘테이션은 코드·데이터·스택 등 의미가 있는 서로 다른 크기의 논리적 단위로 나눕니다.
페이지 크기가 작아지면 페이지 테이블에는 어떤 변화가 생길까?
같은 가상주소 공간을 더 많은 페이지로 나누므로 페이지 테이블의 항목 수와 크기가 증가합니다.
반복문과 자주 사용하는 변수는 어떤 지역성과 관련될까?
시간 지역성과 관련됩니다.
배열의 순차적인 탐색은 어떤 지역성과 관련될까?
공간 지역성과 관련됩니다.
프로세스가 최근 일정 기간 동안 자주 참조하는 페이지의 집합은?
워킹 세트(Working Set)입니다.
페이지 이동 시간이 실제 프로세스 실행 시간보다 커지는 현상은?
스래싱(Thrashing)입니다.
페이지 부재와 스래싱은 어떻게 다를까?
페이지 부재는 참조한 페이지가 메모리에 없는 개별 사건이고, 스래싱은 페이지 부재와 교체가 과도하게 반복되어 실제 처리보다 페이지 이동에 더 많은 시간을 사용하는 상태입니다.
참조열 C·D·E·B·D·E·C를 3개의 프레임에서 LRU로 처리하면 페이지 부재는 몇 번 발생할까?
총 5번 발생합니다.
참조열 4·3·4·1·5·4·3·5를 3개의 프레임에서 FIFO로 처리하면 페이지 부재는 몇 번 발생할까?
총 6번 발생합니다.
참고자료
- 학습 범위 — 사무자동화산업기사 제1과목 사무자동화 시스템, 기억장치 관리 전략과 가상기억장치
- Q-Net — 사무자동화산업기사 국가자격 종목별 상세정보 및 출제기준
- Linux Kernel Documentation — Memory Management
- Linux Kernel Documentation — Memory Management Concepts
- Linux Kernel Documentation — Page Tables
- Linux Kernel Documentation — Userfaultfd and On-Demand Paging
이 글은 사무자동화산업기사 시험 범위에 포함된 기억장치 관리 전략, 가상기억장치, 페이징, 세그멘테이션과 페이지 교체 기법을 이해하고 복습할 수 있도록 재구성한 정리입니다. 실제 운영체제의 메모리 관리 구조와 페이지 교체 정책은 하드웨어 및 운영체제 구현에 따라 더 복잡할 수 있으므로 실제 시험 준비 시에는 최신 Q-Net 출제기준을 함께 확인해야 합니다.