a reference string

Suppose you want to compare two different rules for which book to put back when your desk is full. You cannot just argue about them in the abstract — you need a realistic record of which books you actually reached for, in order, and then you can replay that record under each rule and simply count how many times you had to fetch a book from the shelf. A reference string is exactly such a record for memory: the sequence of page numbers a program touches, in the order it touches them.

In practice we strip the addresses down to just their page numbers, because for replacement only the page matters, not the exact byte. We also collapse runs of references to the same page into one, since a page already in memory cannot fault again until something evicts it. So a raw address stream might become a reference string like 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2. To evaluate an algorithm you fix a number of frames, walk the string from left to right, and count a page fault every time a referenced page is not currently resident. Fewer faults means a better algorithm on that workload.

Why it matters: the reference string is the standard, honest yardstick for page-replacement algorithms — it lets us say things like FIFO faulted nine times here but LRU faulted seven. It is also how Belady's anomaly was discovered (run the same string with three frames, then four, and watch FIFO get worse). One caveat: a reference string is only one workload; an algorithm that wins on one string can lose on another, so real comparisons use many realistic traces, not a single hand-picked example.