컴퓨터 사이언스/운영체제

Demand Paging (Memory Management Policy)

kimjingyu 2025. 4. 8. 16:38

What Page Fault Handler does

  1. Stop the instruction that is trying to translate the address until we can retrieve the contents
  2. Allocate a page in memory to hold the new page contents
  3. Locate the page on disk using the page table entry
  4. Copy the contents of the page from disk
  5. Update the page table entry to indicate that the page is in memory
  6. Load the TLB
  7. Restart the instruction that was addressing the virtual address we retrieved

To swap a page to disk

  1. Remove the translate from the TLB, if it exists
  2. Copy the contents of the page to disk
  3. Update the page table entry to indicate that the page is on disk

Key Issues in Demand Paging

  1. Page selection : When to bring pages into memory and which?
  2. Page replacement : Which pages should be thrown out and when?
  3. Page frame allocation : Global vs. local
  4. In local page frame allocation
    • Static : page frames are fixed (LRU algorithm)
    • Dynamic : page frames are varying (working set algorithm)

Page Selection Policies

  1. Demand Paging
    • It starts up process with no pages loaded. So load a page when a page fault for it occurs.
  2. Prepaging
    • It brings a page into memory before referenced. And then bring in the next one, just in case
    • So it hards to do effectively. But it sometime works(sequential read-ahead)
  3. Request Paging
    • User decides which pages are needed.
    • But most users don't always know best and aren't always impartial.

Page Replacement Algorithms

  1. OPT
    • 현재 시점에서부터 가장 미래에 엑세스될 페이지를 교체하는 기법(이상향적 기준, 척도로 활용)
  2. FIFO
    • Throw out the page that has been in memory the longest
  3. LRU(Least Recently Used)
    • Throw out the page that hasn't been used in the longest time
    • It uses the past to predict the future(with locality, LRU approximates OPT)

Page Replacement Algorithms

FIFO-based algorithm

It's used int VAX/VMS operating system.

Each process has a residence set list ordered in FIFO. For a process, the residence set is the set of pages in memory.

And it keeps a system-wide free wide list. It's used alongside to offset weakness of FIFO. Also size of the free page list is maintained at run-time.

operation

  • On page fault, frames are taken from the head of the free list (free list ---page faulted pages---> residence set list)
  • Old pages are freed from the residence set list to the free list (residence set list ---old pages---> free list)
  • Maintains a system-wide modified page list. So when the swap device is idle, they are written out and become clean.

아래부터는 해당 주제와 관련된 GPT의 답입니다.

VAX/VMS에서의 page replacement policy 구조

🔧 구조 요약

  • Resident Set List (Per-Process):
    • 각 프로세스마다 고정된 수의 페이지 프레임을 갖고 있고
    • 이 리스트는 FIFO 방식으로 페이지를 교체합니다.
  • Global Free List:
    • 시스템 전체에서 사용 가능한 빈 프레임들의 목록입니다.
    • 모든 프로세스가 공유합니다.

❗ 의문 포인트: Free List도 FIFO이면 안 되는 이유?

그렇습니다. Free List가 FIFO이면 안 되는 이유는 다음과 같습니다:

  1. 캐시 효율성 저하
    • FIFO로 가장 오래된 빈 프레임부터 재사용하면, 최근에 사용되었던 (하지만 지금은 free인) 프레임을 우선순위에서 밀어내게 됩니다.
    • 이건 locality (특히 temporal locality)를 무시하는 동작이 되어, 성능 저하로 이어질 수 있어요.
  2. Page Replacement는 Eviction + Allocation인데...
    • Resident set에서 페이지를 빼낼 때는 FIFO를 쓸 수 있어요 (제일 오래 머문 페이지를 교체).
    • 하지만 **free frame을 할당할 때는 "어떤 프레임이 가장 적절한가?"**가 더 중요합니다.
    • VAX/VMS에서는 freelist는 일반적으로 LRU-ish 하거나 usage-based 방식으로 구성합니다.
  3. Free list 자체가 완전히 비는 경우
    • 이 경우는 working set trimming을 유도합니다 (다른 프로세스의 resident set에서 페이지를 빼냄).
    • 따라서 free-list는 단순한 queue가 아니라, 어느 정도 intelligence가 있는 구조로 관리되어야 합니다.

✅ 실제 VAX/VMS의 Free List 구현 방식

VAX/VMS는 단순한 FIFO 큐가 아닌, aging mechanism을 활용한 방식을 사용합니다.

  • 즉, 페이지가 free 상태가 된 후에도 어느 정도 "냉각 기간"을 두고 다시 할당합니다.
  • 이건 일종의 Second Chance Algorithm과 유사하게 작동하며, LRU를 approximate 하는 방식이죠.

💡 요약

  • ✔️ Resident Set: FIFO OK (단일 프로세스 내부에서 오래된 페이지를 빼냄).
  • ❌ Free List: FIFO는 안 좋음. 대신 LRU나 usage-aware한 방식을 써야 함.

 

🧠 실제 VAX/VMS의 Free List 동작 방식

1. Free List 자체는 FIFO 큐처럼 생겼지만, 사용하는 방식이 다름

  • VAX/VMS에서는 freelist를 head-tail 구조로 관리해서 큐처럼 보이지만,
  • 페이지를 무조건 순서대로 꺼내 쓰지 않고, 조건에 따라 건너뛰거나, delay를 줍니다.

2. Page Life Cycle: Active → Inactive → Free

VAX/VMS는 페이지 상태를 크게 세 가지로 나눠서 다룹니다:

상태 설명

Active 현재 프로세스에서 사용 중인 페이지.
Inactive 사용되지 않지만 아직 free가 되지 않은 페이지. Evict 후보.
Free 완전히 비어 있고, 새로운 프로세스에 할당 가능한 상태.
  • Active 페이지는 일정 시간 동안 참조가 없으면 Inactive로 이동합니다.
  • Inactive 상태가 계속되면 OS는 이 페이지를 Free List에 추가합니다.

이건 LRU와 Second-Chance의 중간 단계처럼 작동합니다.

3. Free List에 들어가기 전 냉각 기간 (cooling-off period)

  • 페이지가 Free List로 들어가기 전에 일정 시간 동안 inactive 상태로 대기합니다.
  • 이 시간 동안 다시 접근되면 Active로 복귀합니다.
    → 이게 바로 Second-Chance 메커니즘이에요.

4. Allocation 시에도 무조건 맨 앞에서 꺼내지 않음

  • 어떤 페이지를 할당할지 결정할 때, 최근까지 사용되었던 페이지는 건너뜀.
  • 즉, 단순 FIFO에서 맨 앞을 뽑는 게 아니라, "충분히 식은 페이지"를 우선 할당합니다.

🔍 정리

구조 요소 구현 방식

Resident Set FIFO queue (Per-process)
Free List FIFO-like queue + Cooling-off + Second-Chance
Replacement 정책 WSClock 또는 비슷한 LRU Approximation 사용

💡 VAX/VMS의 설계 철학

  • VAX/VMS는 성능을 위해 working set model을 강하게 밀고 갔어요.
  • 그래서 프로세스마다 working set을 유지하고, 그 외의 페이지만 evict 대상으로 봅니다.
  • 이 모델 덕분에 VMS는 당시 시스템 중에서도 꽤 고성능을 자랑했습니다.
저작자표시 비영리 변경금지 (새창열림)