Memory simulation with example

Memory simulation models the behaviour of a computer's memory system (main memory, cache or virtual memory) to estimate performance measures such as hit ratio, page-fault rate and average access time. It is usually trace-driven: a sequence of memory references (an address trace), taken from a real program or generated randomly, is fed to a model of the memory and its replacement policy.

Components

• Memory structure: page size, number of frames (or cache lines), associativity.
• Replacement policy: FIFO, LRU, optimal, random.
• Reference string (input): the order in which pages are referenced.
• Output: hits, misses (faults), hit ratio, effective access time = h × t_mem + (1 - h) × t_miss.

Algorithm

1. Read the next page reference.
2. If the page is already in a frame, count a hit (and update the usage order for LRU).
3. Otherwise, count a fault; if all frames are full, remove a page according to the policy; then load the page.
4. Repeat until the end of the string and report the statistics.

reference -> [in memory?] -yes-> hit
                  |no
             [free frame?] -no-> replace (FIFO/LRU)
                  |
              load page -> fault count + 1

Example: 3 frames

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 (13 references).

FIFO

FIFO: 3 hits, 10 faults; hit ratio = 3/13 = 0.23.

LRU gives faults at 7, 0, 1, 2, 3, 4, 2, 3, 0, i.e. 9 faults and 4 hits (the 0 at position 5, the 0 at position 7, and the final 3 and 2); hit ratio = 4/13 = 0.31. So LRU performs better for this string.

With t_mem = 100 ns and t_miss = 8 ms, even a small difference in hit ratio changes the effective access time greatly: FIFO gives about (3/13)(100 ns) + (10/13)(8 ms) ≈ 6.15 ms, while LRU gives about (4/13)(100 ns) + (9/13)(8 ms) ≈ 5.54 ms. The simulation lets the designer choose the number of frames and the replacement policy; cache simulation follows the same method, using block addresses and mapping rules.