가상 메모리와 페이지 교체 알고리즘

정보처리기사 실기를 준비하면서 운영체제를 간략히 복습했다.

---

1. 운영체제 메모리 관리

커널 적재(load)

컴퓨터가 부팅되어 하드디스크나 SSD에 저장되어 있는 운영체제의 커널이
RAM(주기억장치)으로 복사되어 올라오는 것.

가상 메모리(Virtual Memory)

CPU는 RAM에 있는 데이터에만 직접 접근할 수 있다. 그래서 안 쓰는 애는 디스크에 잠깐 내려놓고, 필요해지면 다시 RAM에 올려서 쓰는 방식으로 데이터에 접근한다. 근데 운영체제는 마치 모든 게 메모리에 있는 것처럼 속여주고, 이것이 Virtual Memory의 개념이다. CPU가 메모리에 접근하기 위해서는 가상 메모리 주소를 실제 메모리 주소(물리 주소)로 변환하는 과정을 반복해야 한다.

주소 변환

• 페이지 테이블
  가상 메모리 주소와 실제 메모리 주소 사이의 매핑 정보를 담은 테이블
• MMU(Memory Management Unit)
  페이지 테이블을 참고하여 가상 메모리 주소를 실제 메모리 주소로 변환하는 역할을 한다. CPU 내에 존재한다
• TLB(Translation Lookaside Buffer)
  MMU 내부에 있는 메모리. 자주 참조되는 페이지 테이블 entry를 저장한다.

메모리는 블록 단위로 나눠서 사용한다.

• Paging(페이징)

  고정 크기 블록 (페이지 단위). 내부 단편화가 발생 가능하다.

• Segmentation(세그멘테이션)

  가변 크기 블록 (세그먼트 단위). 외부 단편화가 발생 가능하다 - 가변 크기 블록을 반복적으로 할당하고 해제하면 작은 공간들이 생김.

지역성(Locality) : 뒤에 설명할 working set, 페이지 교체 전략(LRU, LFU)과도 관련있다.

• Temporal Locality(시간 지역성): 최근 사용한 데이터 다시 사용할 확률 ↑
• Spatial Locality(공간 지역성): 가까운 주소 접근 확률 ↑

---

2. 페이지 교체 관리

📦 책상으로 비유하자면
메모리에 페이지를 올리기: “할 일을 책상에 올려두는 것”과 유사하다.

페이지 부재(Page Fault)

• 필요한 페이지가 메모리에 없을 때 발생한다.
• Page Fault가 너무 많아지면 스래싱(Thrashing. 페이지 폴트가 너무 자주 발생해서 CPU가 대부분의 시간을 페이지 교체에만 사용하는 현상) 발생 → 성능 낮아진다.

워킹 셋(Working Set)

프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합. 워킹 셋을 RAM에 상주시켜서 페이지 폴트를 줄인다.

할 일들을 언제, 책상의 어느 부분으로, 어떻게 올릴지에 대한 policy들이 존재한다.

1. 반입전략(When?) 
   • 요구 반입(demand fetch): 필요할 때만 페이지 적재.
   • 예측 반입(anticipatory fetch): 필요를 예상하여 미리 적재. 성공하면 성능향상 실패하면 오버헤드 아닙니까?
2. 배치전략(Where?)
   • First fit: 가장 먼저 맞는 공간에 배치
   • Best fit: 가장 근접한 크기의 공간에 배치
   • Worst fit: 가장 큰 공간에 배치. 남는 공간의 개수를 많이 확보하려는 목적
3. 페이지 교체 전략(How?)
   Page fault가 났을 때 누구를 내쫓을지 결정한다 (그러니까 배치전략(Where)은 이때는 안 쓴다)
   • OPT(Optimal)
     미래를 안다고 가정하고 가장 나중에 사용될 페이지를 교체(이론상 최적)
   • FIFO(선입선출) 
     들어온 지 가장 오래된 페이지를 교체
   • LRU(Least Recently Used)
     가장 오래전에 참조된 페이지를 교체
   • LFU(Least frequently used)
     가장 사용빈도가 낮은 페이지를 교체
     

   이외에도 NUR, SCR 등의 기법이 존재한다.