Important Notes

• Handins:

– The deadline for submission of your assignment is 23:30pm, 22nd Oct, 2020.

– For undergraduate students, you may do this assignment as a team of two stu- dents and hand in one submission per team.

– For postgraduate students, you have to do this assignment individually and make individual submissions.

– All implementations have to be done in C++.

– You need to submit your source code using the web submission system. You should

attach you and your partner’s name and student number in your submission.

– Late submissions will attract a penalty: the maximum mark you can obtain will be reduced by 25% per day (or part thereof) past the due date or any extension you are granted.

• Marking scheme: 20 marks for online testing in total:

– 4 marks for FIFO (First In First Out) implementation (4 random cases, automarked)

– 4marksforLRU(LeastRecentlyUsed)implementation(4randomcases,automarked)

– 4 marks for ARB (Additional Reference Bits) implementation (4 random cases, au- tomarked)

– 4 marks for WSARB-1 (Working-Set Additional Reference Bits 1) implementation (4 random cases, automarked)

– 4 marks for WSARB-2 (Working-Set Additional Reference Bits 2) implementation (4 random cases, automarked)

If you have any questions, please send them to the student discussion forum. This way you can all help each other and everyone gets to see the answers.

The assignment Introduction

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 correspond- ing 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 page’s 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.