COMP3300 - Operating Systems Assignment 2

COMP3300 – Assignment 2, 2005

Updated on Tuesday, 21 June 2005

COURSE PROFILE

ASSIGNMENTS
First assignment
Second assignment

CONTACT
email to
<comp3300@itee.uq.edu.au>
Lecturer
Philip Machanick
<philip@itee.uq.edu.au>
Tutors
Timothy Brown <s4006402@student.uq.edu.au>
Richard Woon <woon@itee.uq.edu.au>

EXAM

ITEE

What’s New:

–don’t forget to test on the student UNIX system–

21 June 2005: A solution is now available.

16 June 2005: Results are now available.

17 May 2005: provided more debug.csv files for the traceset-2.text and traceset-full.text data set (the latter traceset file is also added to the web site).

16 May 2005: provided a debug.csv file for the traceset-2.text data set.

10 May 2005: updated debug.csv file (see Files page for details).

Due 26 May 11:30pm, to be submitted electronically (or at this URL for COMP7303): as before, 5% bonus for submission 24 hours or more early (provided it is worth at least 50% before the bonus).

The second assignment in 2005 relates to page replacement strategies. Your task is to implement a least recently used (LRU) strategy within the framework of given code. You should only modify one file, and provide documentation in a README file.

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.

Given:

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)
a simple implementation of first in first out

You need to:

add a new module to the simulator to simulate LRU page replacement

The program will be tested with a test module based on the given code, but which writes out the virtual and physical page number on each page fault and replacement to a file, for comparison with a reference implementation. Any solution should produce the same output in this test environment, since LRU is a well-defined order.

The Textbook
Operating System Concepts by Silberschatz, Galvin, & Gagne

Assignment 2 Details

what to do

You are required to edit exactly one file, virtualMemoryLRU.c, which is provided with some initial content. You should also supply a README file containing a description of how you have implemented the required functionality. The virtualMemoryLRU.c 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 LRU 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).

Look at the supplied code as well as the FIFO and clock examples to see how the calls you are meant to implement are used.

input

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
traces
- 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

output

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 run:

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.

compiling

Note: the code is designed for a 32-bit architecture; if you have a 64-bit machine to work on, make sure you compile and run in 32-bit mode. This may require some adjustment to the compile scripts.

three command lines are provided, to compile the given versions (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

running

to run the given programs (once compiled) with the default trace file and 42 physical frames:
cd Run ./sim-replace-clock traceset.text 42 ./sim-replace-fifo traceset.text 42
and to run your program
cd Run ./sim-replace-lru traceset.text 42

Files

You can fetch all the files except the full benchmark set in a file in tar-gzipped format comp3300-a2-2001-v1.0.tgz, or fetch the files one at a time at the Files directory.

Mark Scheme

Early handin 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 handins unless a medical certificate has been approved by the course coordinator will receive a mark of 0.

Mark caps apply in various categories. If your solution is good other than the reason for the mark cap, subtraction for other deficiencies will be from 100% but the cap will apply. Clarity of your solution is an important criterion which will apply globally, not just to subtraction of marks in a specific area, because you need to show understanding of virtual memory concepts. If your solution is very unclear, expect more marks to be deducted for other deficiencies.

if your program fails to compile, it will receive a maximum mark of 40%.
if your program fails to run to completion or has errors in results, it will receive a maximum mark of 50% (after other aspects of the mark scheme are taken into account).
if your program fails to achieve obvious design efficiencies it will receive a maximum mark of 70%.
if your program fails to achieve less obvious design efficiencies it will receive a maximum mark of 95%.

Marks will be deducted for each of the following, with the maximum set by each of the above criteria:

inadequate documentation: code must be explained at the level of each function, as well as high-level design decisions
deviation from specification (less than the extreme case of failure to compile)
unclear approach -- over and above the documentation, it must be clear what your solution does
obscure coding style -- potentially obvious things done in ways which are hard to understand

Work of no academic merit may receive a mark of 0. Please be sure that you understand the University policy on plagiarism. You are required to read and understand the School Statement on Misconduct, available on the ITEE web site at: http://www.itee.uq.edu.au/about/student-misconduct.jsp.

* In case you are interested, the trace file format is a compressed format called PDATS – see http://wotug.ukc.ac.uk/parallel/simulation/architectures/pdats/docs/ for more detail, including where to find trace files.