Operating Systems #8 — Memory Management and Page Replacement

This post comes from lab questions rather than lecture slides. It got written by answering them, so it's shorter than the earlier posts — but it does contain my own calls on which option to pick.

Allocation strategies — best fit, first fit, worst fit

When placing a process into free memory, which hole do you choose?

Best fit allocates the hole closest in size to what's needed. External fragmentation stays low. But finding the smallest adequate hole takes time.

First fit allocates the first free hole it finds. Easy to implement and fast. But external fragmentation can get bad.

Worst fit allocates the largest hole. Since the largest hole gets subdivided, you get fewer of the unusable slivers best fit leaves behind.

Which one is better depends on the situation. But xv6 uses paging, so external fragmentation isn't a concern. That erases best fit's advantage, so my conclusion at the time was that first fit, the fastest, is the right choice.

The trade-off between the three strategies is really "how much external fragmentation will you accept to save how much search time." The point of this question was that when paging removes one of those axes, only one axis is left.

Page replacement — FIFO, LRU, LFU

FIFO replaces the oldest page. It can end up producing more page faults as you add frames.

LRU replaces the least recently accessed page, so recently accessed pages tend to stay resident.

LFU uses a count and replaces the least frequently accessed page, so a page that was touched recently but is rarely used overall can still be evicted.

Server or client — which one?

The lab question here was a fun one: which policy suits a server, and which suits a client?

A server doesn't exchange data with only one client. It's better off holding the pages that many clients access frequently, so I argued for LFU.

A client might access the same data repeatedly, or might access data it touched recently. So either LFU or LRU seems fine.

If you put it in xv6

Give each page a count variable such that the most recently used page has the highest count, and on a page fault replace the page with the smallest count. That is, LRU.

Copy-on-write

CoW lets several processes share common data or code and creates a new copy only when data is modified. Memory use drops, as does the overhead of producing data nobody needed.

The implementation: share the page table so the pages are shared, and mark shared pages read-only in the flags. When a modification is needed, copy the page then and modify the copy.

Why fork and exec need it in particular

In xv6, CoW matters most for the fork + exec combination.

Without CoW, fork has to copy every page. But exec is usually called right after fork, which makes that whole copy pointless — you copy everything and immediately overwrite it with a different program.

With CoW, no needless copy happens at fork time, so you save memory and the operations run faster.

In #3 I noted that fork() just duplicates the parent's address space and it's exec() that fills it with a program. CoW is best understood as a way of postponing that "just duplicates" for as long as possible.