Sample Traces

There are three sample traces built into PageRVis.

Traces can be imported by opening the Import menu and selecting the Sample tab.

All ARC Cases (Simple)

This trace covers all cases of ARC that will appear in the “last event” box. The trace targets ARC with c = 4.

It is a good starting point trace for testing ARC implementations.

This trace is more comprehensive than the test cases provided in A3-starter. However, this is not a fully comprehensive test case, since technically not all logical paths are covered. Also, since the trace is small so there’s a good chance implementation can ‘accidentally’ get the correct results.

Belady’s anomaly

This trace shows a pattern of accesses such that FIFO with size 4 performs way better than FIFO with size 5.

The pattern has been extended to repeat several times to make the access pattern clearer.

The main idea of the pattern is to set up the two algorithms so that there is a significant difference in the order of pages. Then, we reward the FIFO 4 for keeping the pages loaded whenever FIFO 5 evicts a page.

LRU weak to scans

This trace shows the main advantage of ARC, which is protecting frequently accessed pages during a scan.

In the trace, we see the frequently accessed pages being re-accessed each time after a scan. LRU repeatedly kicks the frequent pages out after a scan, while ARC keeps them loaded.