Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Practical 2: Virtual Memory Management
Critical Information
Submission
Your code will be submitied using SVN to the Web Submission System
Your code should be writen in C.
It will be compiled using gcc -std=c11 *.c -o memsim
It will be run using ./memsim input_file.trace PAGESIZE NUMPAGES ALGORITHM INTERVAL (see
section Running your code below for more details)
For late code submissions 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.
Postgraduate students must complete and submit this assignment individually, making individual
submissions.
Undergraduate students may choose to complete and submit in teams of at most two students.
Marking scheme
This assignment is out of 20:
4 marks for Part 1 (second chance algorithm, automarked)
4 marks for Part 2 (enhanced second chance algorithm, automarked)
4 marks for Part 3 (additional reference bits algorithm, automarked)
4 marks for Part 4 (enhanced additional reference bits algorithm, automarked)
4 marks for Implementation quality (compila?on, running, structure and comments in english; manually
marked)
Task Description
Following our discussion of memory management in lectures, this practical allows you to explore the techniques an
operating system uses to manage virtual memory. Your task is to implement a program that simulates the behaviour
of a memory system that performs demand paging using 4 different page replacement strategies.
The Virtual Memory Simulator
You will need to write a simulator that reads a memory trace and simulates the ac?on of a virtual memory system
with a single level page table. The system needs to simulate swapping to disk and use a specified algorithm for page
replacement.
1 of 5
Your simulator should keep track of the status of the pages, including which page frames would be loaded in
physical memory and which pages reside on disk.
The size of a page (in bytes) will be passed as the 2nd argument on the command line (See Running
your code below for details).
The number of page frames that can be held in main memory will be passed as the 3rd argument on
the command line (See Running your code below for details).
As the simulator processes each memory event from the trace:
It should check to see if the corresponding page is in physical memory (hit), or whether it needs to be
swapped in from disk (pagefault).
If a pagefault has occurred, your simulator may need to choose a page to remove from physical
memory. When choosing a page to replace, your simulator should use the algorithm specified by the
4th argument passed on the command line (See Running your code below for details).
If the page to be replaced is dirty, it would need to be saved back to the swap disk. Your simulator
should track when this occurs.
Finally, the new page is to be loaded into memory from disk, and the page table is updated.
Remember: This is just a simula?on of the page table, so you do not actually need to read and write data
from disk or memory. You just need to keep track of the events that would occur if this was a real system.
See textbook sec?on 9.4 and the lecture slides for more details on page replacement.
See Input/Output Details section below for details on input file structure and output forma?ng.
The page replacement strategies that you will be implementing are as follows:
Part 1 - Second Chance Algorithm
The least recently used (LRU) page replacement algorithm consistently provides near-op?mal replacement, however
implementing true LRU can be expensive. A simple way of approxuima?ng LRU is the Second Chance (SC) algorithm,
which gives recently referenced pages a second chance before replacement.
Your task is to set up your simulator to use the Second Chance algorithm.
Your simulator should use the Second Chance page replacement algorithm if the 4th argument passed on the
command line is set to SC (See Running your code below for details).
This algorithm is described in the Text Book in section 9.4.5.2
A copy of this algorithm’s descrip?on will also be available on MyUni (see assignment descrip?on).
Part 2 - Enhanced Second Chance Algorithm
The Second Chance algorithm is simple, but many systems will try to improve on this using an algorithm that takes
into account the added delay of wri?ng a modified page to disk during replacement. The Enhanced Second Chance
(ESC) algorithm tracks whether a page has been modified or not and uses that informa?on as well as whether the
page was recently referenced to choose which page to replace.
Update your simulator to use the Enhanced Second Chance algorithm.
Your simulator should use the Enhanced Second Chance page replacement algorithm if the 4th argument
passed on the command line is set to ESC (See Running your code below for details).
This algorithm is described in the Text Book in sec?on 9.4.5.3
Addi?onal details on this algorithm are available in the Lecture Slides for Chapter 9
A copy of this algorithm’s descrip?on will also be available on MyUni.
2 of 5
Part 3 - Additional Reference Bits Algorithm
A closer approximation of LRU than the second chance algor?hm is the Addi?onal Reference Bits (ARB) algorithm,
which uses multiple bits to keep track of page access history. These bits are stored in a shit register that regularly
shits right, removing the oldest bit.
Your task is to update your simulator to use the Addi?onal Reference Bits algorithm.
Your simulator should use the Addi?onal Reference Bits page replacement algorithm if the 4th argument
passed on the command line is set to ARB (See Running your code below for details).
This algorithm is described in the Text Book in sec?on 9.4.5.1
Your implementa?on should use an 8-bit shi? register, that shi?s to the right.
Bit shiting (right) should occur at a regular interval specified by the 5th argument passed on the command
line (See Running your code below for details).
For example, if the interval provided is 5, then bit shi?ing should occur for all pages every 5th
memory access.
A copy of this description will also be available on MyUni.
Part 4 - Enhanced Additional Reference Bits Algorithm
Let’s combine the best aspects of ESC and ARB to create a new algorithm, Enhanced ARB (EARB). This algorithm will
combine the improved access history of ARB with the awareness of modified pages from ESC.
Your task is to update your simulator to use the Enhanced ARB algorithm described below.
Your simulator should use the Enhanced Additional Reference Bits page replacement algorithm if the 4th
argument passed on the command line is set to EARB (See Running your code below for details).