정보보안 공부를 하면서도 가끔 보였던 개념중에 하나지만 머릿속에 잘 들어오지 않아서 따로 정리해보고자 함
📝페이지
❓페이지란
메모리를 나눈 작은 조각,
메모리와 디스크의 자원을 효율적으로 관리하기 위해, 프로그램의 데이터를 작은 덩어리(페이지)로 나누어 관리하는 방식
페이지개념을 사용하는 이유
메모리 크기는 한정적이라, 한꺼번에 모든 프로그램 데이터를 메모리에 넣을 수 없음
따라서,
전체 데이터를 메모리에 올리는 것이 아니라, 필요한 부분만 올려서 실행함
-
ex) 100KB 프로그램을 실행할 때, 페이지 크기가 4KB 일 때
: 프로그램은 25개의 페이지로 나눠짐메모리에는 필요한 페이지만 올라가고, 나머지 페이지는 디스크에 저장
페이지 동작 원리
1️⃣ 프로그램이 실행되면, 메모리에 데이터를 일부만 올림
2️⃣ 필요로 하는 데이터가 메모리에 데이터가 없으면?
➡️ 디스크에서 해당 페이지를 가져옴(= 페이지 폴트(Page Fault) 발생)3️⃣ 프로그램 실행 중, 메모리와 디스크 사이에서 페이지를 교환하면서, 메모리 공간을 효율적으로 사용함
🧾페이지 폴트(Page Fault)
프로세스가 필요한 페이지가 메모리에 없을 때 발생하는 이벤트
- Fault(:부재)
- 페이지 폴트 발생 시
→ 디스크에서 페이지를 읽어와 메모리에 로드
→ 페이지 교체가 필요할 수도 있음
페이지 폴트가 많으면 성능 저하(O.S.가 디스크 I/O에 너무 많은 시간을 소모)
📝페이지 교체 알고리즘
대표적인 페이지 교체 알고리즘
⭐1.FIFO (First In, First Out)
가장 먼저 들어온 페이지를 가장 먼저 제거하는 방식
예시: [1, 2, 3, 4, 1] (메모리 크기 3) 요청1 : [1] → 페이지 폴트 발생 요청2 : [1, 2] → 페이지 폴트 발생 요청3 : [1, 2, 3] → 페이지 폴트 발생 요청4 : [2, 3, 4] → 1번 페이지 교체 → [3, 4, 2] → 페이지 폴트 발생 요청5 : [4, 2, 1] → 3번 페이지 교체 → [1, 2, 4] → 페이지 폴트 발생 결과 : 총 5번의 페이지 요청 중, 4번의 페이지 폴트가 발생
- 큐(Queue) 구조 사용
- ✅ 장점: 구현이 단순함
- ❌ 단점: 오래된 페이지가 자주 사용되더라도 무조건 제거됨
- 주 사용처 : 단순한 임베디드 시스템, 기본적인 운영체제(OS) 메모리 관리
⭐2.LRU (Least Recently Used)
가장 오랫동안 사용되지 않은(최근에 사용하지 않은) 페이지를 제거하는 방식.
예시: [1, 2, 3, 1, 4] (메모리 크기 3) 요청1 : [1] → 페이지 폴트 발생 요청2 : [1, 2] → 페이지 폴트 발생 요청3 : [1, 2, 3] → 페이지 폴트 발생 요청4 : [1, 3, 2] → 페이지 폴트 발생 (2번 페이지가 가장 오래되었으므로 교체됨) 요청5 : [3, 2, 4] → 페이지 폴트 발생 (1번 페이지가 가장 오래되었으므로 교체됨) 결과 : 총 5번의 페이지 요청 중, 4번의 페이지 폴트가 발생
- 과거의 사용 이력을 기반으로 판단
- ✅ 장점: FIFO보다 성능이 좋음
- ❌ 단점: 매번 페이지 사용 순서를 갱신해야 하므로 추적 비용이 큼
- 주 사용처 : CPU 캐시 관리, 웹 브라우저 캐시, DB 버퍼 캐시
⭐3.LFU (Least Frequently Used)
가장 적게 사용된(참조 된) 페이지를 제거하는 방식.
예시: [1, 2, 1, 3, 4] (메모리 크기 3) 요청1 : [1] → 페이지 폴트 발생 요청2 : [1, 2] → 페이지 폴트 발생 요청3 : [1, 2] → 페이지 폴트 발생 (1번 페이지가 두 번째로 자주 사용되었으므로 남음) 요청4 : [1, 2, 3] → 페이지 폴트 발생 (2번 페이지가 가장 적게 사용되었으므로 교체됨) 요청5 : [1, 3, 4] → 페이지 폴트 발생 (2번 페이지가 가장 적게 사용되었으므로 교체됨) 결과 : 총 5번의 페이지 요청 중, 4번의 페이지 폴트가 발생
- 페이지의 사용 횟수를 카운트하여 판단
- ✅ 장점: 자주 사용하는 페이지를 오래 유지할 수 있음
- ❌ 단점: 단기적으로 자주 사용된 페이지가 오래 남아 있을 수 있음
- 주 사용처 : CDN(콘텐츠 전송 네트워크), 데이터베이스 쿼리 캐시
⭐4.NUR (Not Used Recently)
최근에 사용되지 않은 페이지 제거하는 LRU를 단순화한 방식
- 참조 비트(Reference Bit)와 수정 비트(Modified Bit)를 사용하여 교체할 페이지를 결정
예시: [1, 2, 3, 1, 4] (메모리 크기 3) 요청1 : [1] → 페이지 폴트 발생 요청2 : [1, 2] → 페이지 폴트 발생 요청3 : [1, 2, 3] → 페이지 폴트 발생 요청4 : [2, 3, 1] → 페이지 폴트 발생 (참조 비트가 0인 1번 페이지 교체됨) 요청5 : [3, 1, 4] → 페이지 폴트 발생 (참조 비트가 0인 2번 페이지 교체됨) 결과 : 총 5번의 페이지 요청 중, 4번의 페이지 폴트가 발생
- ✅ 장점: LRU보다 구현이 쉬우면서도 비슷한 성능
- ❌ 단점: 참조 비트가 최신 상태를 반영하지 못하는 경우가 있을 수 있음
- 주 사용처 : 가상 메모리 시스템 (OS 메모리 관리)
⭐5.Clock (Second Chance)
FIFO를 개선한 방식으로, 참조 비트(Reference Bit)를 사용하여 교체할 페이지를 결정.
참조 비트가 0이면 교체, 1이면 다시 0으로 초기화하고 다음 페이지 검사
- 모든 페이지를 한 번씩 순차적으로 검사한다는 점에서 효율적
예시: 페이지 요청: [1, 2, 3, 4, 1] (메모리 크기 3) 요청1 : [1] → 페이지 폴트 요청2 : [1, 2] → 페이지 폴트 요청3 : [1, 2, 3] → 페이지 폴트 요청4 : [2, 3, 4] → 1번 페이지 교체 요청5 : [3, 4, 1] → 2번 페이지 교체 결과 : 4번의 페이지 폴트가 발생했지만, FIFO보다 효율적인 페이지 교체가 가능해짐
- ✅ 장점: LRU보다 구현이 쉬우면서 FIFO보다 성능이 좋음.
- ❌ 단점: 페이지를 하나씩 검사해야 하므로 약간의 오버헤드 발생.
- 주 사용처 : 리눅스(Linux) 및 유닉스(Unix) 운영체제의 가상 메모리 관리
| 알고리즘 | 원리 | 장점 | 단점 |
|---|---|---|---|
| FIFO | 가장 오래된 페이지 제거 | 구현 쉬움 | 자주 쓰이는 페이지도 제거됨 |
| LRU | 가장 오래 사용되지 않은 페이지 제거 | 성능 좋음 | 추적 비용 큼 |
| LFU | 가장 적게 사용된 페이지 제거 | 자주 쓰이는 페이지 유지 | 단기적으로 많이 사용된 페이지가 오래 남을 수 있음 |
| NUR | 최근 사용되지 않은 페이지 제거 (참조 비트 활용) | LRU보다 간단 | 참조 비트가 정확하지 않을 수도 있음 |
| Clock | FIFO + 참조 비트 사용 | 성능과 구현 균형 | 참조 비트 관리 필요 |
- 이 중에서 Clock 알고리즘은 실제 OS에서 가장 많이 쓰이는 방식 중 하나이며
리눅스의 Second Chance 기법도 사실상 Clock 기반임- LRU는 캐시 최적화에 많이 활용되고, FIFO는 단순한 구조라 기본적인 시스템에서 사용됨
- 추가로, Windows는 LRU와 Clock을 조합한 Working Set Model을 사용하며
Linux는 Clock 변형 알고리즘을 사용함
