페이지 교체와 Page Replacement 알고리즘 - Operating System 10-2

Page replacement가 왜 필요한지, FIFO·OPT·LRU 같은 알고리즘이 어떤 기준으로 페이지를 교체하는지, 그리고 성능 평가를 어떻게 보는지 정리합니다.

xmoonanx 12 min
페이지 교체와 Page Replacement 알고리즘 - Operating System 10-2

가상 메모리 환경에서 free frame이 부족해지면 운영체제는 어떤 페이지를 내보내고 어떤 페이지를 남길지 결정해야 한다. 이 글은 page replacement의 필요성, 대표 알고리즘, 그리고 실제 성능 trade-off를 한 흐름으로 정리한다.

What this post covers

  • page replacement가 필요한 상황과 기본 동작 과정
  • FIFO, OPT, LRU 등 대표 알고리즘의 차이
  • frame allocation, thrashing, 성능 평가 포인트

메모리가 모두 사용되어 새로운 page를 로드할 공간이 없다면 어떻게 될까?

만약 free frame이 없다면??

Page replacement

페이지 교체가 발생함!

📚Page replacement: 메모리에 잘 사용되지 않는 page를 찾았다면 page out을 해서 공간을 만들어 냄

  • page out된 page는 swap space으로 내보내짐

✅교체 알고리즘:

  1. terminate
  2. swap out
  3. replace the page - 가장 많이 씀
    • 지역, 전역 모두 교체 가능

🎯 목표: 한 프로세스가 너무 많은 frame을 소유하지 못하게 해서 page fault를 예방하기(prevent over-allocation)

✅주요 특징:

  1. modify (dirty) bit - 변경이 되지 않은 페이지들은 굳이 overhead하지 않는다
    • → 즉, modified page들만 disk에 저장해서 효율을 높임
  2. virtual memory 확장: 물리 메모리보다 큰 논리 메모리 공간 제공
  3. Prevent over-allocation: page fault service routin에 페이지 교체 포함

alt text

B는 아직 메모리에 있지 않아서 fast disk에서 B를 가져와야 함
하지만 physical 메모리가 꽉차서 B를 부를 수 없다면?
그러면 원래 있는 페이지를 backing store에 저장하고 메모리를 비운다 그러기 위해 page replacement가 필요함!

✅page replacement 과정:

  1. disk에서 요구된 페이지의 위치를 찾음

  2. free frame 찾기:
    • 만약 free frame이 있다면, 빈 공간을 활용
    • free freame이 없다면 page replacement 알고리즘 사용(victim frame을 고르기 위함)
    • Victim Frame이 수정되었다면(dirty bit=1) 디스크에 저장
    • 수정되지 않았다면(dirty bit=0) 바로 덮어쓰기 가능

  3. 선택된 free frame에 디스크에서 원하는 page를 로드, page table과 frame table을 업데이트

  4. page fault를 발생시킨 명령어부터 재시작

alt text

victim frame을 고름(f 바로 위 frame)

이제 한 번의 페이지 폴트에 최대 2번의 페이지 전송이 발생!

  • Victim 페이지 스왑 아웃 + 새 페이지 스왑 인 → EAT 증가

Page and Frame replacement Algorithms

Page Replacement 알고리즘은 두 가지 주요 결정을 담당:

  1. Frame-allocation algorithm: 각 프로세스에 몇 개의 프레임을 할당할 것인가?
  2. Page-replacement algorithm: 어떤 프레임을 교체할 것인가?

📝성능 평가 방법:

  • Reference String을 사용하여 알고리즘 성능 평가
    • 페이지 번호의 연속된 문자열 (전체 주소가 아님)
    • 같은 페이지에 대한 반복 접근은 페이지 폴트를 일으키지 않음
    • 사용 가능한 프레임 수에 따라 결과가 달라짐

alt text

프레임 수를 늘릴 수록 page fault가 감소하는 모습

📝 예제 Reference String:
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

FIFO Algorithm

📚FIFO Algorithm: 가장 먼저 메모리에 들어온 페이지를 먼저 교체

alt text

❌FIFO 알고리즘에서는 프레임을 늘렸는데 오히려 page fault가 증가하는 경우가 존재! - Belady’s Anomaly alt text

  • page의 “나이”만 고려하고 사용 빈도는 무시하기 때문!

Optimal Algorithm

📚Optimal Algorithm: 가장 오래 사용되지 않을 페이지를 교체(미래를 내다봐야함)

alt text

9번의 페이지 폴트
참조열 S에서의 최적해와 역참조열 SR에서의 최적해가 동일한 폴트 수를 가짐

  • 미래를 예측해야하기 때문에 구현이 어려움

Least Recently Used(LRU) Algorithm

📚Least Recently Used(LRU) Algorithm: 과거의 정보를 활용하여 가장 오래 사용되지 않은 페이지를 교체(OPT 알고리즘 대안)

alt text

OPT 알고리즘과 같이 참조열 S에서의 페이지 폴트 수와 역참조열 SR에서의 페이지 폴트 수가 같다

  • LRU 구현 방법:
    1. Counter Implementation
  • 각 페이지 엔트리에 카운터 추가
  • 페이지 참조 시 시계값을 카운터에 복사
  • 교체 시 가장 작은 카운터 값을 찾음
    • 교체 과정:
      1. 모든 카운터 값 검색
      2. 최소값 찾기
      3. 해당 페이지 교체 ❌단점: 테이블 검색 필요
  1. Stack Implementation
    • 더블 링크 형태의 페이지 번호 스택 유지
    • 페이지 참조 시 스택 맨 위로 이동
    • 교체 시 스택 맨 아래 페이지 선택 ❌단점: 업데이트 비용 높음
  • LRU와 Optimal은 Stack Algorithm!
    • 이는 Belady’s Anomaly가 발생하지 않는다는 의미
    • 프레임 수를 늘리면 페이지 폴트는 절대 증가하지 않음 alt text

      stack 구현 동작 예시

LRU Approximation Algorithms

📚LRU Approximation Algorithms: LRU는 특별한 하드웨어가 필요하고 여전히 느리기 때문에 Reference Bit를 활용한 알고리즘

가장 현실적인 알고리즘!

📝Reference Bit 작동원리:

  • 각 페이지에 Reference Bit 연결 (초기값 = 0)
  • 페이지 참조 시 하드웨어가 자동으로 비트를 1로 설정
  • 교체 시 Reference Bit=0 인 페이지 중 하나 선택
    • 순서는 알 수 없지만 최근에 사용되지 않은 페이지를 보장

📚 Second-Chance Algorithm: FIFO + Reference Bit 조합

  • 기본적으로 FIFO 방식으로 동작
  • 교체 대상 페이지의 Reference Bit 확인
  • Bit = 0이면 즉시 교체
  • Bit = 1이면 “두 번째 기회” 부여 (Bit를 0으로 설정하고 큐 뒤로 이동) alt text

    second-chance algorithm

Enhanced Second-Chance Algorithm

📚Second-Chance Algorithm: Reference Bit + Modify(Dirty) Bit을 함께 사용

  • (0, 0): 최우선 교쳬 대상 - 최근에 사용되지 않았고 수정되지도 않음
  • (0, 1): 두 번째 우선순위 - 최근에 사용되지 않았지만 수정됨(→ 교체 전 디스크에 쓰기 필요)
  • (1, 0): 세 번째 우선순위 - 최근에 사용되었지만 수정되지 않음(→ 곧 사용될 가능성 있음)
  • (1, 1): 교체 회피 대상 - 최근에 사용되었고 수정됨(→ 곧 다시 사용될 가능성 + 디스크 쓰기 필요) alt text

✅추가 LRU Approximation 기법들:

  1. Additional Reference Bits Algorithm: Timer 인터럽트를 통해 주기적으로 OS가 오른쪽으로 한 비트씩 이동 alt text

  2. Demand Paging과 Reference Bit 최적화:

    • Demand Paging 시 페이지 블록되면 즉시 Reference Bit = 1로 설정
    • Second-Chance 알고리즘 수행 시 주기적으로 모든 Reference Bit = 0으로 리셋

Counting Algorithms

📚Counting Algorithms: 각 페이지에 대한 참조 횟수(Reference Count)를 추적하여 replacement를 결정하는 알고리즘

📉 LFU (Least Frequently Used):

  • 가장 적게 사용된 페이지를 교체, 참조 횟수가 가장 작은 페이지가 희생양

📈 MFU (Most Frequently Used):

  • 가장 많이 사용된 페이지를 교체, 참조 횟수가 가장 큰 페이지가 희생양

실제 사용 거의 X!

Page-Buffering Algorithms

📚Page-Buffering Algorithms: Free Frame Pool을 활용하여 페이지 폴트 시간을 찾지 않고 바로 할당!

✅동작 과정:

  1. 페이지 폴트 발생 - 필요한 페이지가 메모리에 없음
  2. Pool에서 즉시 할당 - Free Frame Pool에서 바로 프레임 제공
  3. 프로세스 재시작
  4. 백그라운드 보충 - Victim 선택하여 Pool 보충

📝 수정된 페이지들의 별도 리스트를 유지하며 Backing Store가 idle할 때 미리 쓰기 수행 - 시간 절약 가능

💾Frame Contents 보존: Free Frame의 내용을 그대로 보존하고 어떤 페이지가 들어있는지 기록하여 재사용 시 디스크 로드 생략

Applications and Page Replacement

응용프로그램 입장에서는 page replacement가 안맞을 수 있다.

그래서 application이 직접 같은 기능을 함!

  • DBSM와 같이 응용프로그램이 스스로 메모리와 I/O버퍼를 관리하면 double buffering현상이 발생할 수 있다.

OS가 제공하는 Raw dist mode(파일시스템 우회)를 사용함으로써 DBMS처럼 응용프로그램 자신에 최적화된 솔루션을 개발할 수 있다.
그럼에도 대부분의 응용프로그램은 그냥 파일시스템을 사용하는 것이 유리하다

Key takeaways

  • page replacement는 메모리가 꽉 찼을 때 어떤 페이지를 내보낼지 결정하는 가상 메모리의 핵심 메커니즘이다.
  • FIFO, OPT, LRU 같은 알고리즘은 페이지 교체 기준이 다르고, 그에 따라 page fault 수와 성능이 달라진다.
  • 이후 frame allocation과 thrashing 관점을 같이 보면 page replacement를 운영체제 전체 메모리 전략 안에서 이해할 수 있다.