가상 메모리 ⭐⭐⭐
가상 메모리 ⭐⭐⭐¶
개요¶
가상 메모리(Virtual Memory)는 물리 메모리보다 큰 프로그램을 실행할 수 있게 하는 메모리 관리 기법입니다. 요구 페이징, 페이지 폴트 처리, Copy-on-Write 등 핵심 개념을 학습합니다.
목차¶
1. 가상 메모리의 개념¶
1.1 가상 메모리란?¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 가상 메모리 개념 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 프로세스 관점: 실제 상황: │
│ │
│ "나는 4GB 메모리를 물리 메모리: 2GB │
│ 독점 사용한다!" + 디스크 스왑: 8GB │
│ │
│ ┌──────────────────┐ ┌──────────────────┐ │
│ │ 가상 주소 공간 │ │ 물리 RAM │ │
│ │ (4GB) │ │ (2GB) │ │
│ │ │ │ │ │
│ │ ┌──────────────┐ │ 일부만 │ ┌──────────────┐ │ │
│ │ │ 페이지 0 │─┼───메모리에───▶│ │ 프레임 100 │ │ │
│ │ ├──────────────┤ │ │ ├──────────────┤ │ │
│ │ │ 페이지 1 │─┼─────────────▶│ │ 프레임 205 │ │ │
│ │ ├──────────────┤ │ │ ├──────────────┤ │ │
│ │ │ 페이지 2 │ │ │ │ 다른 프로세스 │ │ │
│ │ ├──────────────┤ │ │ │ ... │ │ │
│ │ │ ... │ │ │ └──────────────┘ │ │
│ │ │ (대부분 │ │ │ │
│ │ │ 디스크에) │ │ ┌──────────────────┐ │
│ │ ├──────────────┤ │ │ 디스크 │ │
│ │ │ 페이지 N │ │ 나머지는 │ (스왑 영역) │ │
│ │ └──────────────┘ │ 디스크에 │ │ │
│ └──────────────────┘ ──────▶ │ 페이지 2, 3... │ │
│ └──────────────────┘ │
│ │
│ 핵심: 자주 사용하는 부분만 메모리에, 나머지는 디스크에 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
1.2 가상 메모리의 장점¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 가상 메모리 장점 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 1. 물리 메모리보다 큰 프로그램 실행 │
│ - 4GB 프로그램을 2GB RAM에서 실행 가능 │
│ - 필요한 부분만 메모리에 로드 │
│ │
│ 2. 더 많은 프로세스 동시 실행 │
│ - 각 프로세스가 전체 메모리를 사용하지 않음 │
│ - 다중 프로그래밍 수준 향상 │
│ │
│ 3. 메모리 공유 용이 │
│ - 공유 라이브러리 (libc.so 등) │
│ - 공유 메모리 IPC │
│ - fork() 후 Copy-on-Write │
│ │
│ 4. 프로세스 생성 가속화 │
│ - fork(): 페이지 테이블만 복사 │
│ - exec(): 필요한 페이지만 로드 │
│ │
│ 5. I/O 최적화 │
│ - 파일을 메모리에 매핑 (mmap) │
│ - 불필요한 복사 감소 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
2. 요구 페이징¶
2.1 개념¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 요구 페이징 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 전통적 방식: 요구 페이징: │
│ ┌──────────────────┐ ┌──────────────────┐ │
│ │ 프로그램 시작 시 │ │ 프로그램 시작 시 │ │
│ │ 전체를 메모리에 │ │ 아무것도 로드 │ │
│ │ 로드 │ │ 하지 않음 │ │
│ └──────────────────┘ └──────────────────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────┐ │
│ │ 첫 명령어 실행 │ │
│ │ → 페이지 폴트 │ │
│ │ → 해당 페이지 │ │
│ │ 로드 │ │
│ └──────────────────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────┐ │
│ │ 계속 실행하며 │ │
│ │ 필요한 페이지만 │ │
│ │ 로드 │ │
│ └──────────────────┘ │
│ │
│ Lazy Loading: "필요할 때 로드" │
│ Pure Demand Paging: 절대 미리 로드하지 않음 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
2.2 유효/무효 비트¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 페이지 테이블과 유효 비트 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 페이지 테이블 │
│ ┌────────────┬────────────┬─────────┐ │
│ │ 페이지 번호 │ 프레임 번호 │ V 비트 │ │
│ ├────────────┼────────────┼─────────┤ │
│ │ 0 │ 4 │ 1 │ ← 메모리에 있음 │
│ │ 1 │ - │ 0 │ ← 디스크에 있음 (페이지 폴트) │
│ │ 2 │ 7 │ 1 │ ← 메모리에 있음 │
│ │ 3 │ - │ 0 │ ← 아직 할당 안 됨 │
│ │ 4 │ 2 │ 1 │ ← 메모리에 있음 │
│ │ 5 │ - │ 0 │ ← 디스크에 있음 │
│ │ 6 │ - │ i │ ← 유효하지 않음 (불법 접근) │
│ └────────────┴────────────┴─────────┘ │
│ │
│ V=1: 유효 (Valid) - 페이지가 메모리에 있음 │
│ V=0: 무효 (Invalid) - 페이지가 메모리에 없음 │
│ │
│ 무효인 경우: │
│ 1. 디스크의 스왑 영역에 있음 → 로드 필요 │
│ 2. 아직 한 번도 접근 안 함 → 할당 필요 │
│ 3. 잘못된 주소 → Segmentation Fault │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3. 페이지 폴트¶
3.1 페이지 폴트 처리 과정 (10단계)¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 페이지 폴트 처리 과정 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 1. CPU가 메모리 참조 → 페이지 테이블 조회 │ │
│ │ ↓ │ │
│ │ 2. 유효 비트 = 0 발견 → 페이지 폴트 트랩 발생 │ │
│ │ ↓ │ │
│ │ 3. 운영체제가 제어권 획득 │ │
│ │ - 레지스터, 프로세스 상태 저장 │ │
│ │ ↓ │ │
│ │ 4. 주소 유효성 검사 │ │
│ │ - 불법 주소면 프로세스 종료 │ │
│ │ - 정상이면 계속 │ │
│ │ ↓ │ │
│ │ 5. 빈 프레임 찾기 │ │
│ │ - 없으면 페이지 교체 수행 │ │
│ │ ↓ │ │
│ │ 6. 디스크에서 페이지 읽기 시작 │ │
│ │ - 디스크 I/O 요청 │ │
│ │ - 프로세스는 대기 상태로 │ │
│ │ ↓ │ │
│ │ 7. CPU는 다른 프로세스 실행 │ │
│ │ - 컨텍스트 스위칭 │ │
│ │ ↓ │ │
│ │ 8. 디스크 I/O 완료 인터럽트 │ │
│ │ - 페이지가 프레임에 로드됨 │ │
│ │ ↓ │ │
│ │ 9. 페이지 테이블 업데이트 │ │
│ │ - 프레임 번호 기록 │ │
│ │ - 유효 비트 = 1 │ │
│ │ ↓ │ │
│ │ 10. 원래 명령어 재실행 │ │
│ │ - 프로세스 재개 │ │
│ │ - 이번에는 페이지 폴트 없음 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3.2 하드웨어 지원 요구사항¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 페이지 폴트 처리를 위한 하드웨어 요구사항 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 1. 페이지 테이블 │
│ - 유효/무효 비트 지원 │
│ - 참조 비트, 수정 비트 │
│ │
│ 2. 보조 메모리 (스왑 공간) │
│ - 페이지 저장용 디스크 공간 │
│ - 일반 파일 시스템보다 빠른 접근 │
│ │
│ 3. 명령어 재시작 (Instruction Restart) │
│ - 페이지 폴트 후 동일 명령어 재실행 │
│ - 부분 실행된 명령어 복구 │
│ │
│ 예: ADD 명령어가 페이지 폴트 발생 시 │
│ ┌──────────────────────────────────────────────────────────────────┐ │
│ │ ADD R1, [A], [B] ; A와 B 주소의 값을 더해 R1에 저장 │ │
│ │ │ │
│ │ 1. [A] 페치 중 페이지 폴트 → 명령어 처음부터 재시작 │ │
│ │ 2. [B] 페치 중 페이지 폴트 → A 값 다시 페치 필요 │ │
│ │ │ │
│ │ 복잡한 경우: │ │
│ │ MVC (Move Character) - 블록 복사 명령어 │ │
│ │ - 복사 중간에 페이지 폴트 → 부분 복사 취소 필요 │ │
│ │ - 소스와 대상이 겹치면 더 복잡 │ │
│ └──────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
3.3 페이지 폴트 처리 코드 (의사 코드)¶
#include <stdint.h>
#include <stdbool.h>
#define NUM_FRAMES 1024
#define PAGE_SIZE 4096
typedef struct {
uint32_t frame_number;
bool valid;
bool dirty;
bool referenced;
} PageTableEntry;
typedef struct {
bool allocated;
int process_id;
int page_number;
} Frame;
Frame frame_table[NUM_FRAMES];
PageTableEntry* current_page_table;
int current_process_id;
// 페이지 폴트 핸들러
void page_fault_handler(uint32_t virtual_address) {
uint32_t page_number = virtual_address / PAGE_SIZE;
printf("[Page Fault] Process %d, Page %u\n",
current_process_id, page_number);
// 1. 주소 유효성 검사
if (!is_valid_address(current_process_id, virtual_address)) {
// 불법 접근 - 프로세스 종료
printf("Segmentation Fault!\n");
terminate_process(current_process_id);
return;
}
// 2. 빈 프레임 찾기
int frame = find_free_frame();
if (frame == -1) {
// 빈 프레임 없음 - 페이지 교체 필요
frame = select_victim_frame(); // LRU 등 사용
evict_page(frame); // 희생 페이지 제거
}
// 3. 디스크에서 페이지 로드
uint32_t disk_address = get_disk_address(current_process_id, page_number);
schedule_disk_read(disk_address, frame);
// 4. 프로세스를 대기 상태로 전환
block_process(current_process_id);
// 5. 다른 프로세스 실행 (스케줄러)
schedule_next_process();
// --- 디스크 I/O 완료 후 인터럽트 핸들러에서 ---
}
// 디스크 I/O 완료 인터럽트 핸들러
void disk_io_complete_handler(int frame, int process_id, int page_number) {
// 6. 페이지 테이블 업데이트
PageTableEntry* pte = get_page_table_entry(process_id, page_number);
pte->frame_number = frame;
pte->valid = true;
pte->dirty = false;
pte->referenced = true;
// 7. 프레임 테이블 업데이트
frame_table[frame].allocated = true;
frame_table[frame].process_id = process_id;
frame_table[frame].page_number = page_number;
// 8. 프로세스 준비 상태로 전환
unblock_process(process_id);
// 프로세스가 다시 스케줄되면 명령어 재실행
}
4. Copy-on-Write¶
4.1 개념¶
┌─────────────────────────────────────────────────────────────────────────┐
│ Copy-on-Write (COW) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ fork() 호출 시 전통적 방식: │
│ ┌───────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 부모 프로세스 자식 프로세스 │ │
│ │ ┌──────────────┐ ┌──────────────┐ │ │
│ │ │ 메모리 공간 │ 복사 │ 메모리 공간 │ │ │
│ │ │ (100MB) │ ──────▶ │ (100MB 복사) │ │ │
│ │ └──────────────┘ └──────────────┘ │ │
│ │ │ │
│ │ 문제: 200MB 메모리 사용 │ │
│ │ 자식이 exec() 호출하면 복사한 메모리 전부 버려짐! │ │
│ └───────────────────────────────────────────────────────────────┘ │
│ │
│ Copy-on-Write 방식: │
│ ┌───────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ fork() 직후: │ │
│ │ 부모 PT 자식 PT 물리 메모리 │ │
│ │ ┌──────┐ ┌──────┐ ┌──────────────┐ │ │
│ │ │ 페이지0│──┼──────┼───────────▶│ 공유 페이지0 │ (읽기전용) │ │
│ │ │ 페이지1│──┼──────┼───────────▶│ 공유 페이지1 │ (읽기전용) │ │
│ │ │ 페이지2│──┼──────┼───────────▶│ 공유 페이지2 │ (읽기전용) │ │
│ │ └──────┘ └──────┘ └──────────────┘ │ │
│ │ │ │
│ │ 메모리 사용: 100MB (공유!) │ │
│ │ │ │
│ └───────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
4.2 쓰기 시 복사¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 쓰기 시 COW 페이지 복사 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 자식이 페이지 1에 쓰기 시도: │
│ │
│ 1. 쓰기 보호 위반 발생 (페이지가 읽기 전용) │
│ 2. OS가 COW 페이지임을 확인 │
│ 3. 새 페이지 할당 및 복사 │
│ 4. 자식의 페이지 테이블 업데이트 │
│ 5. 쓰기 실행 │
│ │
│ 결과: │
│ 부모 PT 자식 PT 물리 메모리 │
│ ┌──────┐ ┌──────┐ ┌──────────────┐ │
│ │ 페이지0│──┼──────┼───────────▶│ 공유 페이지0 │ (읽기전용) │
│ │ 페이지1│──┼──────┼──┐ ├──────────────┤ │
│ │ 페이지2│──┼──────┼──┼───────▶│ 공유 페이지2 │ (읽기전용) │
│ └──────┘ └───┬──┘ │ └──────────────┘ │
│ │ │ │
│ │ └────────▶┌──────────────┐ │
│ │ │ 부모 페이지1 │ (읽기/쓰기) │
│ │ └──────────────┘ │
│ │ │
│ └──────────────▶┌──────────────┐ │
│ │ 자식 페이지1 │ (읽기/쓰기) │
│ │ (복사본) │ │
│ └──────────────┘ │
│ │
│ 이제 페이지 1은 각자 독립적, 페이지 0,2는 여전히 공유 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
4.3 COW 구현¶
// COW 페이지 폴트 핸들러 (쓰기 시)
void cow_page_fault_handler(int process_id, uint32_t virtual_address) {
uint32_t page_number = virtual_address / PAGE_SIZE;
PageTableEntry* pte = get_page_table_entry(process_id, page_number);
// COW 페이지인지 확인
if (!pte->cow_flag) {
// 진짜 보호 위반 - 프로세스 종료
terminate_process(process_id);
return;
}
int old_frame = pte->frame_number;
int ref_count = get_reference_count(old_frame);
if (ref_count > 1) {
// 다른 프로세스도 이 페이지 사용 중 - 복사 필요
int new_frame = allocate_frame();
if (new_frame == -1) {
new_frame = select_victim_and_evict();
}
// 페이지 내용 복사
memcpy(frame_to_address(new_frame),
frame_to_address(old_frame),
PAGE_SIZE);
// 참조 카운트 감소
decrement_reference_count(old_frame);
// 페이지 테이블 업데이트
pte->frame_number = new_frame;
pte->cow_flag = false;
pte->writable = true;
// 새 프레임 참조 카운트 = 1
set_reference_count(new_frame, 1);
} else {
// 이 프로세스만 사용 중 - 복사 불필요, 쓰기 허용
pte->cow_flag = false;
pte->writable = true;
}
// TLB 무효화
invalidate_tlb_entry(virtual_address);
}
5. 메모리 매핑 파일¶
5.1 mmap() 개념¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 메모리 매핑 파일 (mmap) │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 전통적 파일 I/O: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 프로세스 커널 디스크 │ │
│ │ ┌──────────┐ ┌──────────┐ ┌──────────┐│ │
│ │ │ 버퍼 │◀── read() ──│ 커널버퍼 │◀──────────│ 파일 ││ │
│ │ └──────────┘ └──────────┘ └──────────┘│ │
│ │ │ │
│ │ 1. 시스템 콜 오버헤드 │ │
│ │ 2. 데이터 복사 2번 (디스크→커널→사용자) │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
│ 메모리 매핑: │
│ ┌─────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 프로세스 가상 주소 공간 │ │
│ │ ┌──────────────────────────────────────────────┐ │ │
│ │ │ ... │ │ │
│ │ ├──────────────────────────────────────────────┤ │ │
│ │ │ 매핑된 영역 │ │ │
│ │ │ ┌────────────────────────────────────┐ │ │ │
│ │ │ │ 파일 내용 │◀────┼─┐ │ │
│ │ │ │ (직접 접근 가능) │ │ │ │ │
│ │ │ └────────────────────────────────────┘ │ │ │ │
│ │ ├──────────────────────────────────────────────┤ │ │ │
│ │ │ ... │ │ │ │
│ │ └──────────────────────────────────────────────┘ │ │ │
│ │ │ 페이지 │ │
│ │ 디스크 │ 폴트로 │ │
│ │ ┌──────────────────────────────────────────────┐ │ 자동 로드│ │
│ │ │ 파일 │◀┘ │ │
│ │ └──────────────────────────────────────────────┘ │ │
│ │ │ │
│ │ 장점: │ │
│ │ - 복사 없음 (Zero-Copy) │ │
│ │ - 포인터로 직접 접근 │ │
│ │ - 여러 프로세스가 파일 공유 가능 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────┘
5.2 mmap() 사용 예제¶
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>
// 파일 읽기 예제
void read_file_with_mmap(const char* filename) {
int fd = open(filename, O_RDONLY);
if (fd == -1) {
perror("open");
return;
}
// 파일 크기 확인
struct stat sb;
fstat(fd, &sb);
// 파일을 메모리에 매핑
char* addr = mmap(NULL, // 커널이 주소 선택
sb.st_size, // 매핑 크기
PROT_READ, // 읽기 전용
MAP_PRIVATE, // 개인 매핑
fd, // 파일 디스크립터
0); // 오프셋
if (addr == MAP_FAILED) {
perror("mmap");
close(fd);
return;
}
// 이제 addr을 통해 파일 내용에 직접 접근 가능
printf("파일 크기: %ld 바이트\n", sb.st_size);
printf("처음 100바이트:\n%.100s\n", addr);
// 매핑 해제
munmap(addr, sb.st_size);
close(fd);
}
// 파일 수정 예제 (공유 매핑)
void modify_file_with_mmap(const char* filename) {
int fd = open(filename, O_RDWR);
if (fd == -1) {
perror("open");
return;
}
struct stat sb;
fstat(fd, &sb);
// 공유 매핑 - 변경사항이 파일에 반영됨
char* addr = mmap(NULL, sb.st_size,
PROT_READ | PROT_WRITE,
MAP_SHARED, // 공유 매핑!
fd, 0);
if (addr == MAP_FAILED) {
perror("mmap");
close(fd);
return;
}
// 파일 내용 수정
if (sb.st_size >= 5) {
memcpy(addr, "Hello", 5); // 첫 5바이트 변경
}
// 변경사항 강제 동기화
msync(addr, sb.st_size, MS_SYNC);
munmap(addr, sb.st_size);
close(fd);
printf("파일 수정 완료\n");
}
// 익명 매핑 (공유 메모리용)
void* create_shared_memory(size_t size) {
void* addr = mmap(NULL, size,
PROT_READ | PROT_WRITE,
MAP_SHARED | MAP_ANONYMOUS, // 파일 없이 매핑
-1, 0);
if (addr == MAP_FAILED) {
return NULL;
}
return addr;
}
int main() {
read_file_with_mmap("/etc/passwd");
return 0;
}
5.3 매핑 옵션¶
┌─────────────────────────────────────────────────────────────────────────┐
│ mmap() 옵션 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 보호 플래그 (prot): │
│ ┌───────────────┬────────────────────────────────────┐ │
│ │ PROT_READ │ 읽기 허용 │ │
│ │ PROT_WRITE │ 쓰기 허용 │ │
│ │ PROT_EXEC │ 실행 허용 │ │
│ │ PROT_NONE │ 접근 불가 (가드 페이지) │ │
│ └───────────────┴────────────────────────────────────┘ │
│ │
│ 플래그 (flags): │
│ ┌───────────────┬────────────────────────────────────┐ │
│ │ MAP_SHARED │ 변경사항 파일에 반영, 공유 가능 │ │
│ │ MAP_PRIVATE │ COW - 변경사항 개인만 볼 수 있음 │ │
│ │ MAP_ANONYMOUS │ 파일 없이 메모리만 (fd=-1) │ │
│ │ MAP_FIXED │ 지정한 주소에 정확히 매핑 │ │
│ │ MAP_LOCKED │ 페이지를 메모리에 고정 (스왑 안 함)│ │
│ └───────────────┴────────────────────────────────────┘ │
│ │
│ 사용 예: │
│ - 실행 파일 로드: MAP_PRIVATE, PROT_READ|PROT_EXEC │
│ - 데이터 파일: MAP_SHARED, PROT_READ|PROT_WRITE │
│ - 힙 확장: MAP_PRIVATE|MAP_ANONYMOUS │
│ - 공유 메모리: MAP_SHARED|MAP_ANONYMOUS │
│ │
└─────────────────────────────────────────────────────────────────────────┘
6. 성능 분석¶
6.1 유효 접근 시간 (페이지 폴트 포함)¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 페이지 폴트를 포함한 유효 접근 시간 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ 파라미터: │
│ - p: 페이지 폴트 확률 (0 ≤ p ≤ 1) │
│ - ma: 메모리 접근 시간 (예: 100ns) │
│ - pft: 페이지 폴트 처리 시간 (예: 8ms = 8,000,000ns) │
│ │
│ 유효 접근 시간 (EAT): │
│ EAT = (1 - p) × ma + p × pft │
│ │
│ 예제: │
│ ma = 100ns, pft = 8ms, 10% 성능 저하 허용 │
│ │
│ 허용 EAT = 100ns × 1.1 = 110ns │
│ │
│ 110 = (1-p) × 100 + p × 8,000,000 │
│ 110 = 100 - 100p + 8,000,000p │
│ 10 = 7,999,900p │
│ p = 10 / 7,999,900 │
│ p ≈ 0.00000125 │
│ p ≈ 1/800,000 │
│ │
│ 결론: 80만 번 접근당 1번 이하의 페이지 폴트만 허용! │
│ │
│ 이것이 페이지 교체 알고리즘이 중요한 이유 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
6.2 페이지 폴트 시간 분해¶
┌─────────────────────────────────────────────────────────────────────────┐
│ 페이지 폴트 처리 시간 분해 │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ 1. 인터럽트 처리 1-100 μs │ │
│ │ - 트랩 발생 │ │
│ │ - 레지스터/상태 저장 │ │
│ │ │ │
│ │ 2. 페이지 폴트 처리 1-100 μs │ │
│ │ - 주소 유효성 검사 │ │
│ │ - 빈 프레임 찾기 │ │
│ │ │ │
│ │ 3. 디스크 I/O 8-10 ms ◀── 대부분 시간! │ │
│ │ - 탐색 시간 │ │
│ │ - 회전 지연 │ │
│ │ - 전송 시간 │ │
│ │ │ │
│ │ 4. 인터럽트 처리 1-100 μs │ │
│ │ - I/O 완료 인터럽트 │ │
│ │ - 테이블 업데이트 │ │
│ │ │ │
│ │ 5. 프로세스 재개 1-100 μs │ │
│ │ - 레지스터 복원 │ │
│ │ - 명령어 재실행 │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ │
│ 총 시간: 약 8-10ms (대부분 디스크 I/O) │
│ │
│ SSD의 경우: 0.1-0.5ms로 대폭 감소 │
│ │
└─────────────────────────────────────────────────────────────────────────┘
연습 문제¶
문제 1: 페이지 폴트 시나리오¶
프로세스가 다음 순서로 페이지에 접근합니다. 메모리에는 3개의 프레임만 있고, 초기에 모두 비어있을 때 페이지 폴트 횟수를 구하시오.
접근 순서: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
정답 보기
FIFO 교체 알고리즘 가정:
접근 메모리(3프레임) 폴트?
1 [1, -, -] 폴트
2 [1, 2, -] 폴트
3 [1, 2, 3] 폴트
4 [4, 2, 3] 폴트 (1 교체)
1 [4, 1, 3] 폴트 (2 교체)
2 [4, 1, 2] 폴트 (3 교체)
5 [5, 1, 2] 폴트 (4 교체)
1 [5, 1, 2] 적중
2 [5, 1, 2] 적중
3 [3, 1, 2] 폴트 (5 교체)
4 [3, 4, 2] 폴트 (1 교체)
5 [3, 4, 5] 폴트 (2 교체)
총 페이지 폴트: 10번
문제 2: EAT 계산¶
메모리 접근 시간이 50ns이고 페이지 폴트 처리 시간이 10ms일 때, 성능 저하를 5% 이내로 유지하려면 페이지 폴트 확률이 얼마 이하여야 하는가?
정답 보기
ma = 50ns
pft = 10ms = 10,000,000ns
허용 EAT = 50 × 1.05 = 52.5ns
EAT = (1-p) × ma + p × pft
52.5 = (1-p) × 50 + p × 10,000,000
52.5 = 50 - 50p + 10,000,000p
2.5 = 9,999,950p
p = 2.5 / 9,999,950
p ≈ 2.5 × 10^-7
p ≈ 1 / 4,000,000
결론: 400만 번 접근당 1번 이하의 페이지 폴트
문제 3: Copy-on-Write¶
부모 프로세스가 100개의 페이지를 가지고 있고 fork()를 호출합니다. 자식이 10개의 페이지를 수정한 후 종료하면, 총 몇 개의 페이지가 물리적으로 존재하는가?
정답 보기
1. fork() 직후:
- 100개 페이지가 부모와 자식이 공유 (읽기전용)
- 물리 페이지: 100개
2. 자식이 10개 페이지 수정:
- 각 수정 시 COW 발생, 새 페이지 할당
- 물리 페이지: 100(기존) + 10(복사본) = 110개
3. 자식 종료 후:
- 자식의 10개 복사본 해제
- 공유 90개의 참조 카운트 감소 (1로)
- 물리 페이지: 100개 (부모만 남음)
각 시점별 물리 페이지:
- fork() 직후: 100개
- 자식 수정 후: 110개
- 자식 종료 후: 100개
문제 4: mmap() 분석¶
다음 코드의 출력을 예측하시오.
int fd = open("test.txt", O_RDWR); // 내용: "AAAAAAAAAA"
char* p1 = mmap(NULL, 10, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
char* p2 = mmap(NULL, 10, PROT_READ|PROT_WRITE, MAP_PRIVATE, fd, 0);
p1[0] = 'B';
p2[1] = 'C';
printf("p1: %.10s\n", p1);
printf("p2: %.10s\n", p2);
// 파일을 다시 읽으면?
정답 보기
p1: MAP_SHARED - 변경이 파일에 반영
p2: MAP_PRIVATE - 변경이 프로세스 내에서만 보임 (COW)
p1[0] = 'B':
- 파일의 첫 번째 문자가 B로 변경
- p1은 파일과 공유하므로 변경 반영
p2[1] = 'C':
- COW 발생 - p2의 페이지 복사
- 복사본의 두 번째 문자가 C로 변경
- 파일은 변경되지 않음
출력:
p1: BAAAAAAAAA (p1[0]이 B, 파일도 변경됨)
p2: BCAAAAAAAA (p1의 변경 + p2만의 변경)
파일을 다시 읽으면: BAAAAAAAAA
(p2의 C는 프로세스 내에서만 보이고, 파일에는 반영 안 됨)
문제 5: 요구 페이징 설계¶
새 운영체제를 설계할 때, 순수 요구 페이징(Pure Demand Paging) 대신 프리페칭(Prefetching)을 사용할지 결정하려 합니다. 각 접근법의 장단점을 설명하시오.
정답 보기
순수 요구 페이징:
장점:
- 불필요한 페이지 로드 없음 (정확히 필요한 것만)
- 초기 메모리 사용량 최소화
- 구현 단순
단점:
- 프로그램 시작 시 많은 페이지 폴트
- 지역성이 없는 접근 패턴에서 성능 저하
프리페칭:
장점:
- 예상되는 페이지를 미리 로드하여 폴트 감소
- 순차 접근 패턴에서 효과적
- 지역성의 원리 활용
단점:
- 예측 실패 시 메모리 낭비
- 구현 복잡 (좋은 예측 알고리즘 필요)
- 불필요한 I/O 발생 가능
실제 시스템:
- Linux: 둘 다 사용
- 기본: 요구 페이징
- 순차 접근 감지 시: readahead (프리페치)
- madvise(MADV_SEQUENTIAL): 프리페치 힌트
권장:
- 기본은 요구 페이징
- 순차 접근 패턴 감지 시 적응적 프리페칭
다음 단계¶
15_Page_Replacement.md에서 페이지 교체 알고리즘을 배워봅시다!
참고 자료¶
- Silberschatz, "Operating System Concepts" Chapter 10
- Linux man pages:
mmap(2),fork(2) - Tanenbaum, "Modern Operating Systems" Chapter 3
- Linux kernel source:
mm/memory.c,mm/mmap.c