The aim of this assignment is to improve your learning experience in the page replacement algorithms. Following our discussion of paging in lectures, this practical will allow you to explore how real applications respond to a variety of page replacement schemes. Since modifying a real operating system to use different page replacement algorithms can be quite a technical exercise, your task will be to implement a program that simulates the behaviour of a memory system using a variety of paging schemes.

Memory Traces

We provide you with some memory traces to assist you developing your simulator.

Each trace is a series of lines, each listing a hexadecimal memory address preceded by R or W to indicate a read or a write. There are also lines throughout the trace starting with a # followed by a process ID and command. For example, a trace file for gcc might start like this:

# gcc

R 0041f7a0

R 13f5e2c0

R 05e78900

R 004758a0

W 31348900

The lines in the trace file beginning with #.

Simulator Requirements

Your task is to write a simulator that reads a memory trace and simulates the action of a virtual memory system with a single level page table.

Your memory system should keep track of which pages are loaded into memory.

• As it processes each memory event from the trace, it should check to see if the corresponding page is loaded.
• If not, it should choose a victim page in memory to replace.
• If the victim page to be replaced is dirty, it must be saved to disk before replacement.
• Finally, the new page is loaded into memory from disk, and the page table is updated.

This is just a simulation of the page table, so you do not actually need to read and write data from disk. When a simulated disk read or write occurs, simply increment a counter to keep track of disk reads and writes, respectively.

You must implement the following page replacement algorithms:

• FIFO: Replace the page that has been resident in memory longest.
• LRU: Replace the page that has been resident in memory oldest.
• ARB: Use multiple reference bits to approximate LRU. Your implementation should use an a-bit shift register and the given regular interval b. See textbook section 9.4.5.1.
  • If two pages ARB are equal, you should use FIFO (longest) to replace the frame.
• WSARB-1: Combine the ARB page replacement algorithm with the working set model that keeps track of the page reference frequencies over a given window size (page references) for each process (see textbook section 9.6.2). It works as follows:
  • Associate each page with a reference bits as the shift register (R) to track the reference pattern over the recent time intervals (for a given time interval length), and an integer counter (C) of 8 bits to record the reference frequency of pages (in the memory frames) in the current working set window. R and C are initialized to 0.
  • Page replacement is done by first selecting the victim page of the smallest reference frequency (the smallest value of C), and then selecting the page that has the smallest reference pattern value in the ARB shift register (the smallest value of R) if there are multiple pages with the smallest reference frequency.
• WSARB-2: Same as WSARB-1 in combining ARB with the working set model, but selecting a victim for page replacement is done in the reverse order:
  • First select the page having the smallest reference patten value in R, and then that of the smallest reference frequency value in C if there are multiple pages with the smallest reference patten value.

Note that for WSARB-1 and WSARB-2, same as ARB, if there are multiple pages with the same smallest values of R and C, victim will be chosen according to FIFO among them.

Test

Arguments

Your code will be compiled using following order in your SVN folder.

g++ -std=c++11 PageReplacement.cpp -o PageReplacement The simulator should accept arguments as follows:

1. The filename of the trace file
2. The page/frame size in bytes (we recommend you use 4096 bytes when testing).
3. The number of page frames in the simulated memory.

The trace provided should be opened and read as a file, **not** parsed as text input from stdin.

For example, your code might be run like this:

./PageReplacement input.txt 4096 32 FIFO Where:

• The program being run is ./PageReplacement,
• The name of the input file is input.txt,
• A page is 4096 bytes,
• There are 32 frames in physical memory,
• The page replacement algorithm to use: FIFO / LRU / ARB / WSARB-1 / WSARB-2

If the page replacement algorithm is ARB , it should accept the following additional arguments:

The number of reference bits a (1 a 8) used in the shift register (R).

The integer value of regular interval b (1 b 12) for register shifting.

If the page replacement algorithm is WSARB-1 or WSARB-2, it should accept the following additional argument:

The number of a, the shift register (R) uses an a-bit shift register (1 a 8).

The integer value of regular interval b (1 b 12) for register shifting.

The size of the working set window , in page references (b 256).

For example, your code might be run like this:

./PageReplacement input.txt 1024 16 ARB 3 3

./PageReplacement input.txt 4096 32 WSARB-1 8 3 11

Input

We will provide you with a selection of memory traces to assist you developing your simulator. These will be a mix of specific test cases and real traces from running systems. Each trace is a series of lines, containing two(2) values that represent memory accesses:

1. A character R or W that represents whether the memory access is a Read or Writerespectively.
2. A hexadecimal memory address.

A trace may also contain comment lines, # followed by a process Name.

An example of a trace:

# chrome

R 0041f7a0

R 13f5e2c0

R 05e78900

R 004758a0

W 31348900

Output

The simulator should run silently with no output until the very end, at which point it prints out a summary like this:

events in trace: 1025 total disk reads: 151 total disk writes: 92 page faults: 151

Where:

• events in trace is the number of memory accesses in the trace. Should be equal to number of lines in the trace file that start with R or W. Lines starting with # do not count.
• total disk reads is the number of times pages have to be read from disk.
• total disk writes is the number of times pages have to be written back to disk.
• page faults is the number of disk reads in a demand paging system. It may be same with total disk reads in this problem.

We will provide a set of expected outputs(on web-submission) to match the given memory traces.