지난 글에서는 페이징(Paging)의 기본 원리와 주소 변환 과정, 그리고 TLB와 다중 레벨 페이징을 통해 성능과 효율성을 높이는 방법을 알아보았습니다. 하지만 지금까지 설명한 페이징은 프로세스를 실행하기 위해 모든 페이지를 미리 물리 메모리에 올려놓는 것을 가정했습니다. 과연 이것이 효율적일까요?
이번 글에서는 현대 운영체제 메모리 관리의 핵심인 가상 메모리(Virtual Memory) 개념을 도입하고, 그 기반 기술인 요구 페이징(Demand Paging)과 페이지 교체(Page Replacement) 알고리즘의 기초를 다뤄보겠습니다.
참고 강의 - KOCW 반효경 운영체제
반효경 [운영체제] 22. Virtual Memory 1
설명이 없습니다.
core.ewha.ac.kr
1. 가상 메모리(Virtual Memory)와 요구 페이징(Demand Paging)
- 가상 메모리란?
- 프로세스 전체가 물리 메모리에 올라와 있지 않더라도, 마치 자신만의 매우 큰 메모리 공간(가상 주소 공간)을 사용하는 것처럼 프로세스에게 보여주는 기술입니다. 실제 사용하는 부분만 물리 메모리에 적재하고 나머지는 보조 저장장치(디스크)에 두는 방식입니다.
- 이는 전적으로 운영체제가 하드웨어(MMU)의 도움을 받아 관리합니다.
- 요구 페이징 (Demand Paging): "필요할 때만 페이지를 올리자!"
- 가상 메모리를 구현하는 가장 일반적인 방법입니다.
- 프로세스 실행 시작 시 모든 페이지를 메모리에 올리는 대신, 실제로 해당 페이지가 필요하게 될 때(CPU가 그 페이지의 주소를 참조할 때) 메모리로 읽어오는 방식입니다.
- 장점:
- I/O 양 감소: 불필요한 페이지 로딩이 줄어듭니다.
- 메모리 사용량 감소: 실제로 사용하는 페이지만 메모리에 있으므로 메모리를 절약합니다.
- 빠른 응답 시간: 프로그램 시작 시 모든 페이지를 로드할 필요가 없어 초기 로딩 시간이 단축됩니다.
- 더 많은 사용자(프로세스) 수용: 각 프로세스가 차지하는 물리 메모리가 줄어들어 더 많은 프로세스를 동시에 실행할 수 있습니다 (다중 프로그래밍 정도 향상).
2. 요구 페이징 구현: 유효-무효 비트 (Valid-Invalid Bit)
요구 페이징을 구현하기 위해 페이지 테이블 항목(PTE)에 유효-무효 비트(Valid-Invalid Bit)가 추가됩니다.
- Valid-Invalid Bit: 각 페이지가 현재 물리 메모리에 있는지 없는지를 나타내는 1비트 플래그.
- valid (v): 해당 페이지가 물리 메모리에 존재하며, 페이지 테이블 항목에 있는 프레임 번호가 유효함을 의미합니다.
- invalid (i): 해당 페이지가 물리 메모리에 없음을 의미합니다. 이 비트가 설정된 경우, 페이지 테이블 항목의 나머지 부분(프레임 번호 등)은 의미가 없거나, 해당 페이지가 디스크(Backing Store, Swap Area) 어디에 저장되어 있는지 위치 정보를 담을 수 있습니다.
- invalid의 의미는 두 가지일 수 있습니다:
- 프로세스가 실제로 사용하지 않는 논리 주소 공간 영역에 해당하는 페이지 (예: 할당되지 않은 영역).
- 프로세스가 사용하는 페이지이지만, 현재는 물리 메모리에 없고 디스크에 내려가 있는 경우.
- invalid의 의미는 두 가지일 수 있습니다:
- 초기 상태: 프로세스가 처음 시작될 때는 모든 페이지 테이블 항목의 비트가 invalid로 초기화됩니다. 아직 어떤 페이지도 메모리에 올라오지 않았기 때문입니다.
- 주소 변환 시 동작:
- CPU가 논리 주소(p, d)를 생성합니다.
- MMU가 페이지 테이블에서 페이지 p에 해당하는 항목을 찾습니다.
- 해당 항목의 Valid-Invalid 비트를 확인합니다.
- valid: 정상적인 경우. 프레임 번호(f)를 얻어 물리 주소(f, d)로 변환하고 메모리에 접근합니다.
- invalid: 페이지 부재(Page Fault) 발생! 해당 페이지가 메모리에 없으므로 CPU는 정상적인 진행을 멈추고 운영체제에게 제어권을 넘깁니다 (Trap).
논리 주소 (p, d) | V +-------------+ <------- PTBR | Page Table | |-------------| | f0 | valid | (Entry 0) |-------------| | f1 | valid | (Entry 1) |-------------| | --- | invalid | (Entry 2) <-- 이 페이지 접근 시 Page Fault! p --> |-------------| | f | valid | (Entry p) |-------------| | ... | ... | +-------------+ | (valid 인 경우) V 물리 주소 (f, d) +-------+-------+ | Frame | Offset| +-------+-------+ | V [물리 메모리]
[궁금할 수 있는 포인트 🤔 & 답변 ✅]
- Q: "페이지가 물리 메모리에 없으면 페이지 테이블 엔트리는 어떤 정보를 가지고 있나요?"
- A: invalid 비트가 설정된 엔트리의 나머지 비트는 운영체제가 활용하기 나름입니다. 단순히 0으로 채워둘 수도 있고, 해당 페이지가 디스크(스왑 영역)의 어느 위치에 저장되어 있는지 그 주소 정보를 저장해둘 수도 있습니다. 후자의 경우 페이지 부재 처리 시 디스크에서 해당 페이지를 찾아오는 데 사용됩니다.
- Q: "Valid-Invalid 비트 하나만으로 페이지가 '사용되지 않는 영역'인지, 아니면 '디스크에 있는 영역'인지 어떻게 구분하나요?"
- A: Valid-Invalid 비트 자체만으로는 구분하기 어려울 수 있습니다. 운영체제는 보통 페이지 테이블 엔트리의 다른 비트나 별도의 자료구조를 이용하여 이를 구분합니다. 예를 들어, invalid 비트가 설정되어 있으면서 디스크 주소 정보가 있다면 '디스크에 있는 페이지'로, 디스크 주소 정보도 없다면 '사용되지 않는 페이지'로 간주할 수 있습니다. 만약 사용되지 않는 페이지에 접근하려고 하면 단순 페이지 부재가 아니라 세그멘테이션 오류(Segmentation Fault) 같은 더 심각한 오류로 처리될 수 있습니다.
3. 페이지 부재 (Page Fault) 처리 과정
페이지 부재는 오류(Error)가 아니라, 요구 페이징 시스템에서 정상적으로 발생할 수 있는 일종의 인터럽트(Trap)입니다. 운영체제는 페이지 부재 트랩을 받으면 다음과 같은 과정을 통해 해당 페이지를 메모리로 가져옵니다.
- Trap 발생 및 OS 개입: CPU가 invalid 페이지에 접근 시도 시 MMU가 페이지 부재 트랩(Page Fault Trap)을 발생시키고, CPU 제어권이 운영체제(커널 모드)로 넘어갑니다. 현재 실행 중이던 프로세스의 상태(PC, 레지스터 등)는 저장됩니다.
- 유효성 검사: 운영체제는 해당 메모리 접근이 유효한지 확인합니다.
- 만약 접근하려는 주소가 프로세스의 논리 주소 공간을 벗어났거나, 접근 권한(읽기/쓰기)이 없는 경우 (Protection Violation), 이는 잘못된 접근이므로 해당 프로세스를 강제 종료(Abort)시킵니다.
- 만약 유효한 주소이지만 단순히 현재 메모리에 없는 경우(Valid reference, but page not in memory), 다음 단계를 진행합니다.
- 빈 프레임 확보: 디스크에서 페이지를 읽어올 물리 메모리의 빈 프레임(Free Frame)을 찾습니다.
- 빈 프레임이 있다면: 바로 사용합니다.
- 빈 프레임이 없다면: 페이지 교체(Page Replacement) 알고리즘을 사용하여 현재 메모리에 있는 페이지 중 하나를 희생양(Victim Page)으로 선택하여 디스크로 내보냅니다(Swap-out). 이때 희생양 페이지의 내용이 디스크 내용과 비교하여 변경되었다면(Dirty Bit 확인) 디스크에 변경 내용을 기록해야 합니다. 이제 희생양이 사용하던 프레임이 빈 프레임이 됩니다. (페이지 교체는 다음 섹션에서 자세히)
- 페이지 로딩 (Disk I/O): 운영체제는 해당 페이지의 디스크 위치 정보(페이지 테이블 엔트리나 다른 자료구조에 저장된)를 이용하여 디스크에 I/O 요청을 보내 페이지 내용을 확보된 빈 프레임으로 읽어옵니다.
- 프로세스 대기 (Block): 디스크 I/O 작업은 매우 느리므로, 페이지 로딩이 완료될 때까지 해당 프로세스는 대기 상태(Blocked)가 되고 CPU는 다른 프로세스에게 넘어갑니다.
- 페이지 테이블 업데이트: 디스크 I/O가 완료되면(인터럽트 발생), 운영체제는 해당 페이지의 페이지 테이블 항목을 업데이트합니다.
- Valid-Invalid 비트를 valid로 변경합니다.
- 해당 페이지가 적재된 프레임 번호를 기록합니다.
- 프로세스 재시작 준비: 페이지 부재를 일으켰던 프로세스를 준비 큐(Ready Queue)에 넣어 다시 CPU를 할당받을 수 있도록 합니다.
- 명령어 재실행: 해당 프로세스가 다시 CPU를 할당받으면, 페이지 부재를 일으켰던 바로 그 명령어부터 다시 실행합니다. 이제는 해당 페이지가 메모리에 있으므로(페이지 테이블이 valid로 업데이트됨), 정상적으로 주소 변환이 이루어지고 실행이 계속됩니다.
[궁금할 수 있는 포인트 🤔 & 답변 ✅]
- Q: "페이지 부재(Page Fault)는 성능에 어떤 영향을 미치나요?"
- A: 페이지 부재는 상당한 성능 저하를 유발합니다. 주된 이유는 디스크 I/O 때문입니다. 메모리 접근 속도는 나노초(ns) 단위인 반면, 디스크 접근 속도는 밀리초(ms) 단위로 수만 배에서 수십만 배 느립니다. 페이지 부재가 발생하면 해당 프로세스는 디스크 I/O가 완료될 때까지 오랫동안 멈춰 있어야 합니다. 따라서 요구 페이징 시스템의 성능은 페이지 부재율(Page Fault Rate), 즉 메모리 접근 시 페이지 부재가 발생하는 비율을 얼마나 낮게 유지하느냐에 크게 좌우됩니다.
- Q: "페이지 부재 처리 중에 CPU는 무엇을 하나요?"
- A: 페이지 부재를 일으킨 프로세스는 디스크 I/O를 기다리는 동안 대기 상태(Blocked)가 됩니다. 운영체제는 이 시간에 CPU를 다른 실행 가능한 프로세스(Ready 상태)에게 할당하여 CPU 활용률을 높입니다. 이것이 다중 프로그래밍과 요구 페이징이 시너지를 내는 부분입니다.
4. 요구 페이징 성능 (Effective Access Time)
요구 페이징 시스템의 평균적인 메모리 접근 시간(EAT)은 페이지 부재율(p)을 고려하여 계산할 수 있습니다.
- 페이지 부재율 (Page Fault Rate, p): 메모리 접근 시 페이지 부재가 발생할 확률 (0 ≤ p ≤ 1).
- p = 0 이면 페이지 부재가 전혀 없음 (모든 페이지가 메모리에 있음).
- p = 1 이면 모든 메모리 접근마다 페이지 부재 발생 (매우 비효율적).
- 유효 접근 시간 (Effective Access Time, EAT):
- EAT = (페이지 부재가 아닌 경우의 접근 시간) + (페이지 부재인 경우의 처리 시간)
- EAT = (1 - p) * (메모리 접근 시간) + p * (페이지 부재 처리 시간)
- 페이지 부재 처리 시간은 매우 깁니다. 대략적으로 다음과 같은 요소들을 포함합니다:
- 페이지 부재 트랩 처리 시간 (OS 오버헤드)
- (필요시) 희생양 페이지를 디스크로 내보내는 시간 (Swap-out time)
- 요청된 페이지를 디스크에서 메모리로 읽어오는 시간 (Swap-in time) - 가장 오래 걸림!
- 프로세스 재시작 시간 (OS 오버헤드)
- 간단히 표현하면: EAT = (1 - p) * memory_access + p * page_fault_time
- page_fault_time이 memory_access보다 훨씬 크기 때문에, 페이지 부재율 p를 최소화하는 것이 성능 향상의 핵심입니다.
5. 페이지 교체 (Page Replacement): 빈 프레임이 없을 때
요구 페이징 시스템에서 페이지 부재가 발생했는데 물리 메모리에 빈 프레임(Free Frame)이 없다면, 메모리에 이미 올라와 있는 페이지 중 하나를 디스크로 내보내고(Swap-out) 그 자리에 새로운 페이지를 올려야(Swap-in) 합니다. 이때 어떤 페이지를 내보낼지(희생양, Victim Page) 결정하는 정책이 페이지 교체 알고리즘(Page Replacement Algorithm)입니다.
- 목표: 페이지 부재율(Page Fault Rate)을 최소화하는 것. 즉, 앞으로 가장 오랫동안 사용되지 않을 것 같은 페이지를 쫓아내는 것이 이상적입니다.
- 기본 과정:
- 디스크에서 필요한 페이지의 위치를 찾습니다.
- 빈 프레임을 찾습니다. 없으면 교체 알고리즘으로 희생양 프레임을 선택합니다.
- 희생양 페이지를 디스크에 기록합니다 (만약 내용이 변경되었다면 - Dirty Bit 확인).
- 희생양 페이지의 페이지 테이블 항목을 invalid로 변경합니다.
- 필요한 페이지를 디스크에서 희생양이 사용하던 프레임으로 읽어옵니다.
- 새로 올라온 페이지의 페이지 테이블 항목을 프레임 번호와 함께 valid로 설정합니다.
- 페이지 부재를 일으켰던 프로세스를 계속 수행합니다.
- 알고리즘 평가: 특정 페이지 참조열(Page Reference String) - 즉, 프로세스가 참조하는 페이지 번호 순서 - 에 대해 각 알고리즘이 얼마나 많은 페이지 부재를 일으키는지 비교하여 평가합니다.
- 예시 참조열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
6. 페이지 교체 알고리즘 ①: Optimal 과 FIFO
이제 구체적인 페이지 교체 알고리즘들을 살펴보겠습니다.
최적 알고리즘 (Optimal Algorithm, OPT, MIN, Belady's Optimal)
- 아이디어: 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체합니다. 즉, 미래의 페이지 참조 패턴을 모두 알고 있다고 가정하는 이상적인 알고리즘입니다.
-
페이지 참조열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 (프레임 4개 가정) 1 2 3 4 1 2 5 1 2 3 4 5 ------------------------------------ 1 1 1 1 1 1 1 1 1 3 3 3 <- Frame 1 2 2 2 2 2 2 2 2 2 4 4 <- Frame 2 3 3 3 3 3 3 3 3 3 5 <- Frame 3 4 4 4 5 5 5 4 4 4 <- Frame 4 ------------------------------------ F F F F F F F F (F: Page Fault) - 총 6번- 5 참조 시: 1, 2, 3, 4 중 가장 나중에 참조될 4가 교체됨.
- 3 참조 시: 1, 2, 5, 3 중 가장 나중에 참조될 1이 교체됨.
- 4 참조 시: 3, 2, 5, 4 중 가장 나중에 참조될 2가 교체됨.
- 5 참조 시: 3, 4, 5, 5 중 가장 나중에 참조될 3이 교체됨.
- 특징:
- 가장 낮은 페이지 부재율을 보장합니다.
- 실제 시스템에서는 미래를 알 수 없으므로 구현이 불가능합니다.
- 다른 현실적인 알고리즘들의 성능을 비교 평가하기 위한 기준(Lower Bound)으로 사용됩니다.
("아무리 좋은 알고리즘도 Optimal보다는 나쁠 수밖에 없다.")
FIFO (First-In, First-Out) 알고리즘
- 아이디어: 가장 먼저 메모리에 들어온 페이지를 가장 먼저 내쫓습니다. 즉, 메모리에 가장 오래 있었던 페이지를 희생양으로 선택합니다.
- 구현: 페이지가 메모리에 들어온 순서를 큐(Queue)로 관리하여 구현합니다.
-
페이지 참조열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 (프레임 4개 가정) 1 2 3 4 1 2 5 1 2 3 4 5 ------------------------------------ 1 1 1 1 5 5 5 4 4 4 <- Frame 1 (가장 오래됨) 2 2 2 2 1 1 1 5 5 <- Frame 2 3 3 3 3 2 2 2 3 <- Frame 3 4 4 4 4 3 3 3 <- Frame 4 ------------------------------------ F F F F F F F F F F (F: Page Fault) - 총 10번 - 특징:
- 구현이 매우 간단합니다.
- 성능이 좋지 않은 경우가 많습니다. 가장 오래 있었다는 것이 앞으로 사용되지 않을 것이라는 보장은 없기 때문입니다. (예: 초기화 코드 페이지)
- 벨레이디의 변이(Belady's Anomaly): 드물게, 물리 메모리 프레임 수를 늘려주었는데도 오히려 페이지 부재율이 증가하는 이상 현상이 발생할 수 있습니다. (대부분의 다른 알고리즘에서는 발생하지 않음)
[궁금할 수 있는 포인트 🤔 & 답변 ✅]
- Q: "Optimal 알고리즘은 구현 불가능한데 왜 배우나요?"
- A: Optimal 알고리즘은 우리가 달성할 수 있는 가장 이상적인 성능(최저 페이지 부재율)의 기준선을 제공합니다. 우리가 새로 개발하거나 사용하는 페이지 교체 알고리즘이 얼마나 Optimal에 가까운 성능을 내는지를 비교함으로써 그 알고리즘의 효율성을 평가할 수 있습니다.
- Q: "벨레이디의 변이(Belady's Anomaly)는 왜 발생하나요?"
- A: FIFO 알고리즘은 페이지의 실제 사용 패턴(지역성)을 전혀 고려하지 않고 단순히 메모리에 들어온 순서만 보기 때문입니다. 프레임 수가 늘어나면 오히려 중요한 페이지가 더 일찍 메모리에 들어와서, 나중에 필요할 때 이미 쫓겨나 버리는 아이러니한 상황이 발생할 수 있습니다. 이는 직관에 반하는 현상으로, FIFO의 비효율성을 보여주는 대표적인 사례입니다.
7. 페이지 교체 알고리즘 ②: LRU 와 LFU
미래를 예측할 수 없다면, 과거의 참조 기록을 바탕으로 미래를 예측하려는 알고리즘들이 등장합니다. 이는 지역성(Locality)의 원리 - 즉, 최근에 참조된 데이터는 가까운 미래에 다시 참조될 가능성이 높고, 오랫동안 참조되지 않은 데이터는 앞으로도 참조되지 않을 가능성이 높다는 경험적 법칙 - 에 기반합니다.
LRU (Least Recently Used) 알고리즘
- 아이디어: 가장 오랫동안 참조되지 않은 페이지를 교체합니다. 즉, 가장 최근 사용 시점이 오래된 페이지를 희생양으로 선택합니다. ("Least Recently Used" = "가장 덜 최근에 사용된")
- 가정: 가장 오랫동안 사용되지 않았다면 앞으로도 사용될 확률이 낮을 것이다. (시간 지역성 활용)
-
페이지 참조열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 (프레임 4개 가정) 1 2 3 4 1 2 5 1 2 3 4 5 ------------------------------------ 1 1 1 1 1 1 1 1 1 1 4 4 <- Frame 1 2 2 2 2 2 2 2 2 2 2 5 <- Frame 2 3 3 3 3 5 5 5 5 5 3 <- Frame 3 4 4 4 4 4 4 3 3 3 <- Frame 4 ------------------------------------ F F F F F F F F (F: Page Fault) - 총 8번- 5 참조 시: LRU는 3 (4,1,2는 최근 참조됨) -> 3 교체
- 3 참조 시: LRU는 4 (5,1,2는 최근 참조됨) -> 4 교체
- 4 참조 시: LRU는 5 (3,1,2는 최근 참조됨) -> 5 교체
- 5 참조 시: LRU는 1 (4,3,2는 최근 참조됨) -> 1 교체
- 특징:
- Optimal 알고리즘에 근접하는 매우 좋은 성능을 보이는 것으로 알려져 있습니다.
- 구현이 까다롭습니다. 각 페이지마다 마지막 참조 시간을 기록하거나, 참조된 순서대로 페이지 목록을 유지(예: 링크드 리스트)해야 하는데, 모든 메모리 참조마다 이 정보를 갱신하는 것은 상당한 오버헤드를 유발합니다. (하드웨어 지원 필요)
LFU (Least Frequently Used) 알고리즘
- 아이디어: 참조 횟수가 가장 적은 페이지를 교체합니다.
- 가정: 참조 횟수가 적다는 것은 중요하지 않거나 앞으로 사용될 확률이 낮은 페이지일 것이다.
- 최저 참조 횟수 페이지가 여러 개일 경우:
- 알고리즘 자체는 임의로 하나를 선택합니다.
- 성능 향상을 위해 추가적으로 LRU 개념을 도입하여, 횟수가 같다면 그중 가장 오랫동안 참조되지 않은 페이지를 선택할 수도 있습니다.
- 특징:
- 장점: LRU처럼 최근 참조 시점만 보는 것이 아니라 장기적인 참조 빈도를 고려하므로 페이지의 인기도를 더 잘 반영할 수 있습니다. (예: 초기에 잠깐 집중 사용되고 오랫동안 안 쓰인 페이지보다, 꾸준히 가끔씩 사용되는 페이지를 유지할 수 있음)
- 단점:
- 최근성(Recency)을 반영하지 못합니다. 과거에 매우 자주 사용되었지만 최근에는 전혀 사용되지 않는 페이지가 계속 메모리에 남아있을 수 있습니다.
- 참조 횟수(Count)를 관리해야 하므로 구현이 복잡하고 오버헤드가 있습니다.
- 초기에는 모든 페이지의 참조 횟수가 낮아 어떤 것을 교체할지 결정하기 애매할 수 있습니다.
- LRU와 LFU 성능 비교 예시:(LFU는 참조 횟수 관리가 필요하여 표기가 복잡해짐)
-
페이지 참조열: 1, 2, 1, 2, 3, 4, 5 (프레임 3개 가정) 참조 | 1 | 2 | 1 | 2 | 3 | 4 | 5 ------------------------------------------ LRU | 1 | 1 | 1 | 1 | 1 | 4 | 4 | F | 2 | 2 | 2 | 2 | 2 | 5 | | F | | | 3 | 3 | 3 | | | | | F | F | F Page Faults (LRU): 5 참조 | 1 | 2 | 1 | 2 | 3 | 4 | 5 ------------------------------------------ LFU | 1 | 1 | 1 | 1 | 3 | 4 | 5 Cnt | 1:1| 1:1| 1:2| 1:2| 3:1| 4:1| 5:1 | F | 2 | 2 | 2 | 2 | 2 | 2 | | F | | | 2:2| 2:2| 2:2 | | | | | F | F | F | | | | | 1:2| 1:2| 1:2 -> 교체 (3,4,5 중 빈도 1, LRU 기준?) -> 3 교체 가정 Page Faults (LFU): 5 (이 예제에서는 동일, LFU 동점 처리 방식에 따라 달라질 수 있음)
[궁금할 수 있는 포인트 🤔 & 답변 ✅]
- Q: "LRU 알고리즘은 성능이 좋다는데 왜 구현이 어렵나요?"
- A: 모든 메모리 참조가 발생할 때마다 해당 페이지의 마지막 참조 시간을 기록하거나, 페이지 목록(예: 링크드 리스트)에서 해당 페이지를 찾아서 맨 앞으로 옮기는 작업이 필요합니다. 이는 하드웨어의 특별한 지원(참조 비트, 카운터 등) 없이는 소프트웨어적으로 구현하기에 오버헤드가 매우 큽니다. 그래서 실제 시스템에서는 완전한 LRU 대신 LRU의 동작을 근사(Approximate)하는 알고리즘(예: Clock Algorithm, Second-Chance Algorithm)을 사용하는 경우가 많습니다.
- Q: "LFU는 참조 횟수를 어떻게 효율적으로 관리하나요?"
- A: 각 페이지마다 참조 횟수 카운터를 유지해야 합니다. 페이지 참조 시 카운터를 증가시키고, 페이지 교체 시에는 모든 페이지의 카운터를 비교하여 가장 작은 값을 가진 페이지를 찾아야 합니다. 단순 배열 검색은 O(N) 시간이 걸립니다. 힙(Heap) 자료구조를 사용하면 페이지 교체 시 최소 참조 횟수 페이지를 찾는 데 O(log N) 시간이 걸리지만, 페이지 참조 시 카운터를 증가시키고 힙 구조를 유지하는 데도 O(log N) 시간이 필요합니다. LRU보다 구현 및 관리 오버헤드가 더 클 수 있습니다.
- Q: "LRU와 LFU 중 어떤 것이 더 좋은 알고리즘인가요?"
- A: 정답은 없습니다. 워크로드(페이지 참조 패턴)에 따라 성능이 달라집니다. 일반적으로는 LRU가 시간 지역성을 잘 활용하여 좋은 성능을 보이는 경우가 많고 구현도 (근사 알고리즘 사용 시) 비교적 간단하여 널리 사용됩니다. LFU는 장기적인 패턴을 반영하는 장점이 있지만 최근성 반영 부족과 구현 복잡성 때문에 LRU만큼 자주 쓰이지는 않습니다. 두 알고리즘의 장점을 결합하려는 시도(예: LRFU)도 있습니다.
8. LRU 및 LFU 수도코드
참고용으로 LRU와 LFU의 기본적인 구현 아이디어를 수도코드로 나타내 보겠습니다. (실제 OS 구현은 훨씬 복잡합니다)
LRU 구현 아이디어 (링크드 리스트 + 해시 맵)
# 가정: frames는 현재 메모리에 있는 페이지 번호 저장 (최대 frame_size)
# page_map은 페이지 번호 -> 리스트 노드를 빠르게 찾기 위한 맵
# linked_list는 참조 순서 관리 (가장 최근 참조된 것이 맨 뒤)
cache = {} # page_map 역할 (key: page_num, value: list_node)
doubly_linked_list = LinkedList() # MRU(tail) <-> ... <-> LRU(head)
frame_size = 4
def access_page(page_num):
if page_num in cache:
# Cache Hit (TLB Hit과 유사)
node = cache[page_num]
# 참조되었으므로 리스트 맨 뒤(MRU)로 이동
doubly_linked_list.move_to_tail(node)
print(f"Page {page_num} accessed (Hit)")
else:
# Cache Miss (Page Fault와 유사)
print(f"Page {page_num} accessed (Miss/Fault)")
if len(cache) >= frame_size:
# 프레임이 꽉 찼다면, LRU 페이지(리스트 맨 앞) 제거
lru_node = doubly_linked_list.remove_head()
del cache[lru_node.page_num]
print(f" Replacing page {lru_node.page_num}")
# 새 페이지를 리스트 맨 뒤(MRU)에 추가하고 캐시에 등록
new_node = Node(page_num)
doubly_linked_list.add_to_tail(new_node)
cache[page_num] = new_node
# 사용 예시 (LinkedList, Node 클래스는 별도 구현 필요)
# access_page(1)
# access_page(2)
# ...- 시간 복잡도: 페이지 접근 시 O(1) (해시 맵 조회 및 리스트 연산). 교체 시 O(1).
LFU 구현 아이디어 (최소 힙 + 해시 맵)
# 가정: cache는 페이지 번호 -> (참조 횟수, 마지막 참조 시간 등) 정보 저장
# min_heap은 (참조 횟수, 마지막 참조 시간, 페이지 번호) 튜플을 저장하여
# 참조 횟수가 가장 적고, 같다면 가장 오래된 페이지를 빠르게 찾음
cache = {} # key: page_num, value: [frequency, last_access_time]
min_heap = MinHeap() # (frequency, last_access_time, page_num)
frame_size = 4
current_time = 0
def access_page_lfu(page_num):
global current_time
current_time += 1
if page_num in cache:
# Cache Hit
# 참조 횟수 증가 및 마지막 접근 시간 갱신
freq, _ = cache[page_num]
cache[page_num] = [freq + 1, current_time]
# 힙에서도 해당 정보 업데이트 (힙 재구성 필요 - O(logN))
min_heap.update_priority(page_num, freq + 1, current_time)
print(f"Page {page_num} accessed (Hit)")
else:
# Cache Miss
print(f"Page {page_num} accessed (Miss/Fault)")
if len(cache) >= frame_size:
# 프레임 꽉 찼다면, 최소 빈도 페이지(힙의 루트) 제거
_, _, victim_page = min_heap.pop()
del cache[victim_page]
print(f" Replacing page {victim_page}")
# 새 페이지 캐시에 등록하고 힙에 삽입
cache[page_num] = [1, current_time] # 초기 빈도 1
min_heap.push((1, current_time, page_num)) # O(logN)
# 사용 예시 (MinHeap 클래스는 별도 구현 필요, update_priority 구현 복잡)
# access_page_lfu(1)
# access_page_lfu(2)
# ...- 시간 복잡도: 페이지 접근 시 O(log N) (힙 업데이트). 교체 시 O(log N) (힙 pop & push).
LRU보다 복잡하고 느릴 수 있음. (특히 힙 업데이트 구현)
[마무리하며]
요구 페이징은 가상 메모리를 구현하는 핵심 기술로, 실제 필요한 페이지만 메모리에 올려 메모리 사용 효율을 크게 높입니다. 하지만 메모리에 없는 페이지 접근 시 페이지 부재(Page Fault)가 발생하며, 이는 성능 저하의 주요 원인이 됩니다. 빈 프레임이 없을 경우 페이지 교체 알고리즘을 통해 희생양 페이지를 결정해야 하며, 페이지 부재율을 최소화하는 것이 알고리즘 선택의 중요한 기준입니다.
Optimal 알고리즘은 이론적인 최적 성능을 보여주지만 구현 불가능하며, FIFO는 간단하지만 성능이 좋지 않고 이상 현상(Belady's Anomaly)이 발생할 수 있습니다. LRU와 LFU는 과거 참조 기록을 바탕으로 미래를 예측하는 현실적인 알고리즘으로, 특히 LRU가 좋은 성능을 보여 널리 연구되지만 완전한 구현에는 어려움이 따릅니다.
다음 글에서는 LRU를 근사하는 실용적인 알고리즘들과 페이지 교체 시 추가적으로 고려해야 할 사항들에 대해 알아보겠습니다.
'운영체제 > 반효경 교수' 카테고리의 다른 글
| 운영체제: 메모리 관리 ③ - 페이징 심화 및 세그멘테이션 (0) | 2025.04.14 |
|---|---|
| 운영체제: 메모리 관리 ② - 페이징 (Paging) 기초 (0) | 2025.04.14 |
| 운영체제: 메모리 관리 ① - 주소 변환과 메모리 할당 기초 (0) | 2025.04.13 |
| 운영체제: 교착 상태 (Deadlock) - 원인과 해결 전략 (0) | 2025.04.13 |
| 운영체제: 프로세스 동기화 - 모니터 (Monitor)를 이용한 병행 제어 (0) | 2025.04.13 |