주니어 백엔드 개발자 인터뷰

# 페이지 교체 알고리즘

메모리는 한정되어 있기 때문에 스와핑이 발생합니다. 스와핑이 자주 발생하면 성능저하가 일어나기 때문에 페이지 교체 알고리즘을 기반으로 스와핑이 많이 일어나지 않도록 설계해야 합니다.

# 오프라인 알고리즘(Offline Algorithm)

앞으로 가장 오랫동안 사용되지 않은 페이지부터 먼저 교체하는 알고리즘이며 가장 좋은 방식입니다.

  • 앞으로 어떤 페이지가 사용될 지 미리 알 수 없으니 실제 구현이 불가능한 알고리즘입니다.
  • 이론상 최적의 알고리즘이기 때문에, 다른 알고리즘과의 성능 비교에 대한 기준을 제공하는 역할입니다.
  • Optimal Algorithms 이라고도 부릅니다.

# FIFO(First In First Out)

가장 먼저 온 페이지를 교체 영역에 가장 먼저 놓는 방법을 의미합니다.

fifo

  • 가장 단순한 알고리즘입니다.
  • FIFO Queue를 이용해 구현이 가능합니다.
  • 멀티미디어 데이터로 인해 주목을 받았습니다.
  • 구현이 간단하지만, 성능이 좋지 않은 편입니다.
  • 페이지가 늘어남에도 불구하고 페이지 폴트가 증가하는 Belady's Anomaly가 발생할수도 있습니다.

# LFU(Least Frequently Used)

가장 참조 횟수가 적은 페이지를 교체하는 방식입니다. 쉽게 말해, 많이 사용되지 않는 것을 교체하는 것입니다.

LFU

  • 프로그램 실행 초기에 많이 사용된 페이지는, 그 후로 사용되지 않더라도 프레임을 계속 차지하는 문제가 있습니다.

# LRU(Least Recently Used)

가장 오랜 시간 참조되지 않은 페이지부터 교체하는 방법입니다.

LRU

  • 페이지 사용의 지역성을 고려하여, Optimal Algorithms과 유사하며 실제 구현이 가능한 알고리즘입니다.
  • 구현 방법 : 오래된 것을 구별하기 위한 Counter와 Queue 사용합니다.
    • Counter : 참조된 시간을 기록합니다.
    • Queue : 한번 사용한 페이지를 큐의 가장 위로 이동시킵니다. (가장 최근에 사용된 페이지는 가장 위에 있고, 가장 오래전에 사용된 페이지는 가장 아래에 있습니다.)

# NUR(Not Used Recently)

최근에 접근하지 않은 페이지를 바꾸는 방법입니다.

  • 참조 bit(Reference bit)와 변형 bit(Modified Bit)를 사용합니다.
  • reference bit (최근에 참조된 경우에는 1, 최근에 참조되지 않은 경우에는 0)
    • 최초로 프레임에 로드 될 때와 페이지가 참조되었을 때마다 1로 설정됩니다.
    • 일정 주기바다 다시 0으로 리셋됩니다.
  • modified bit (wirte된 페이지는 1, 그렇지 않은 페이지는 0)
    • 최초로 프레임에 로드 될때는 0으로 설정됩니다.
    • 페이지의 내용이 바뀔때는 1로 설정됩니다.
  • 페이지 교체가 필요한 시점에 다음 순서대로 교체 대상으로 삼습니다.
    1. 참조 0, 변형 0
    2. 참조 1, 변형 0
    3. 참조 0, 변형 1
    4. 참조 1, 변형 1

NUR과 유사한 알고리즘

SCR Algorithms(Second Chance Replacement Algorithms)
: 변형 비트 없이 참조 비트만을 사용한다.

Clock Algorithms
: 참조 비트를 사용하고 환형 큐를 사용하여 프레임을 관리한다.

# 참고자료

← 프로세스 →