UQ Students should read the Disclaimer & Warning
Note: This page dates from 2005, and is kept for historical purposes.
COMP3300 – Assignment Two – Virtual Memory
|My Result||— out of 100|
|Class Standard Deviation||—|
The purpose of this assignment is to further develop you proficiency in C programming and at the same time to improve your understanding of virtual memory.
This assignment is part of a project to investigate simplifications of popular page replacement strategies, aimed at small-scale computers with limited memory. The rationale is that small-memory systems are a growing niche, and rethinking operating system strategies may be necessary to suit them.
- a simulator which can read trace files and simulate operation of the virtual memory system, with a simple forward page table, and report statistics on page replacement and page faults
- a simplified implementation of a clock approximation to least-recently-used (LRU)
You need to:
- add a new module to the simulator to simulate first in first out
You are required to edit exactly one file, virtualMemoryFIFO.c , which is provided with some initial content. This file may be completely rewritten for your solution. However, it must define functions required by the rest of the program, as defined in the header file virtualMemory.h :
- // set up status information for replacement
void initVM (Address maxPage);
- this is called before any of the other functions in the file and can be used for any general initialization
- // tell VM a page has been added
void informVMNewPage (int pid, Address vAddress, Address pAddress, void *entryInPT);
- this is called whenever the paging system starts using a page for the first time: use this to record any status information for future use
- // tell VM a page has been used
void informVMPageUsed (int pid, Address vAddress, Address pAddress, void *entryInPT);
- this is called whenever the paging system uses a page which is currently in main memory: use this to update any status information if necessary (for example, the clock algorithm sets the clock bit)
- // find a replacement victim for a page fault for process pid
Address selectVictim (int pid);
- here you should use the FIFO strategy to find a page in your internal record of frames, and modify its state information to indicate its new owner, as well as the fact that it is now the most recently allocated page
- // mark a frame as unused: call in conjunction with
// deallocatePage which adds it back to the free page list
void freeFrame (Address frame);
- here you should mark the page in your internal data structures as no longer available
Your solution must compile with the given command line, without any modifications to any of the other files. It also must run with any number of trace files in PDATs format, to simulate running a multitasking workload. The other files (the ones you will not modify) handle managing the trace files; your solution will only have to handle keeping track of usage of physical page frames and deciding which one to give up when the virtual memory system has to replace as page (when it runs out of free memory).
- command line:
- traceset file name
- this file contains names of trace files, one to a line: each trace file should be a complete path, or path relative to the location where you are running the program. A file traceset.text is supplied with the name of the give trace file, as well as a file traceset-full.text , containing names of a set of 19 trace files, available via the student UNIX machines at
- number of physical pages
You will want to run an example or two to see how many pages are actually used across all the processes in the trace file or files; your program will be tested with significantly fewer pages than the processes need (high number of replacements and faults) as well as with more physical memory than is needed
- traceset file name
- a file spec026.ucomp.pdt is supplied with the code. This file can be used for testing; you can repeat its name in the traceset file to fake the effect of multiple traces
- you may produce any output you like; your program will be tested using a special test version of the given files, which will send output to a file (not part of the given code)
- the program as supplied dumps a fair amount of output, including
displaying a “.” every 1,000,000 addresses so you can see it’s making
progress. The most useful output it produces is the summary at the end of the
Total pages used 4144; total page faults 96795; total victims 95437
this output gives you some idea of how well the simulated strategy has performed (page faults is a measure of how often a real implementation would have had to go to disk; victims is a measure of how often a frame which is occupied by a page has been taken over, as opposed to taking over an unused frame).
- The program also produces output showing statistics per process.
- two command lines are provided, to compile the given version
(designed to be run in the directory of the source files):
- and the version you are to develop:
- in both cases, the compiled program will be installed in a directory called Run
- to run the given program (once compiled) with the default trace
file and 42 physical frames:
./sim-replace-clock traceset.text 42
and to run your program
./sim-replace-fifo traceset.text 42
Early hand-in 24 hours or more before the deadline will attract a bonus of 5% of available marks provided your assignment scores at least 50% without the bonus. Late hand-ins unless a medical certificate has been approved by the course coordinator will receive a mark of zero.
Portions of code © Copyright 2004 Ned Martin