Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

CSC369 Lab

The learning goals of this lab are as follows.

  • learn to use PageRVis
  • demonstrate Belady’s anomaly
  • understand ARC

Using PageRVis

PageRVis has documentation for all it’s features. If you’re lost, consult the docs!

Your first task is to familiarize yourself with the controls. We provide links to relevant documentation for extra help if you’re stuck.

Here are some suggested tasks to familiarize yourself.

  1. access a few pages
  2. step back and forth through your sequence
  3. edit your sequence
  4. try some keyboard shortcuts
  5. explore the alternate layouts for an algorithm
  6. change the algorithm policy and size
  7. clear the sequence (without reloading the page!)
  8. add a second algorithm and access some pages

Demonstrate Belady’s anomaly

In A3, you will produce access sequences that show when one algorithm outperforms another. PageRVis can help you create and test these sequences.

Your task on PageRVis:

  1. add two algorithms that will run simultaneously: FIFO with size 4, FIFO with size 6
  2. create a sequence that ends with the smaller FIFO algorithm getting more hits

There are examples of Belady’s anomaly with different sizes in the lecture slides, and PageRVis has a Belady’s anomaly sample trace for reference.

Understanding ARC

ARC is the most complex algorithm you will implement in A3. ARC has many subtle details we will explore.

Your task on PageRVis:

  1. remove all algorithms and add an ARC algorithm
  2. demonstrate that when no pages are accessed twice, only T1 is not empty, and B1 remains empty
  3. create a sequence that leads ARC to have c pages in T2 and c pages in B2 (all blue)
  4. create a sequence that leads ARC to have c pages in T1 and c pages in B2 (is all red possible?)
  5. create a trace that covers all PageRVis-recognized cases of ARC with c = 5

These traces may be useful for testing your own ARC implementation! Consider exporting them for use later.

Hint: Cleared your sequence? PageRVis has infinite undo, so you can probably recover your sequence by undoing (unless you reloaded).

Bonus: ARC and Belady’s anomaly

Is ARC susceptible to Belady’s anomaly? Try to find a trace or prove it can’t.

Hint 1: Does a larger memory size guarantee for ARC that the memory holds a strict superset of the elements that a smaller memory size would hold for all access patterns?

Hint 2: Try working with very small memory sizes.