UQ Students should read the Disclaimer & Warning
Note: This page dates from 2005, and is kept for historical purposes.
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>COMP3300 - Assignment 2 - Virtual Memory</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<style type="text/css">
<!--
.wrong {
background: #FF9999;
}
body {
background: url(_img/DSC04989.jpg) fixed center;
font-family: "Arial Unicode MS", Arial, Helvetica, sans-serif;
}
th, td, textarea {
border: 1px solid #000000;
padding: 0 1ex;
background: transparent;
overflow: hidden;
}
table {
border: none;
}
-->
</style>
</head>
<body>
<h1>COMP3300 – Assignment Two – Virtual Memory</h1>
<p> </p>
<table border="1">
<tr>
<td>My Result </td>
<td>— out of 100 </td>
</tr>
<tr>
<td>Comments</td>
<td><ul>
<li> —</li>
<li> —</li>
<li> —</li>
</ul></td>
</tr>
<tr>
<td>Class Average</td>
<td>—</td>
</tr>
<tr>
<td>Class Median</td>
<td>—</td>
</tr>
<tr>
<td>Class Standard Deviation </td>
<td>—</td>
</tr>
</table>
<p>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. </p>
<p>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. </p>
<p>Given: </p>
<ul>
<li>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 </li>
<li>a simplified implementation of a clock approximation to least-recently-used
(LRU) </li>
</ul>
<p>You need to: </p>
<ul>
<li>add a new module to the simulator to simulate first in first out </li>
</ul>
<p>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 : </p>
<ul>
<li> // set up status information for replacement <br />
void initVM (Address maxPage);
<ul>
<li> this is called before any of the other functions in the file
and can be used for any general initialization </li>
</ul>
</li>
<li> // tell VM a page has been added <br />
void informVMNewPage (int pid, Address vAddress, Address pAddress,
void *entryInPT); </li>
<li> 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 </li>
<li> // tell VM a page has been used <br />
void informVMPageUsed (int pid, Address vAddress, Address pAddress,
void *entryInPT);
<ul>
<li> 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) </li>
</ul>
</li>
<li> // find a replacement victim for a page fault for process pid <br />
Address selectVictim (int pid);
<ul>
<li> 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 </li>
</ul>
</li>
<li> // mark a frame as unused: call in conjunction with <br />
// deallocatePage which adds it back to the free page list <br />
void freeFrame (Address frame);
<ul>
<li> here you should mark the page in your internal data structures
as no longer available </li>
</ul>
</li>
</ul>
<p>Your solution <em>must</em> 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). </p>
<h2>Input </h2>
<ul>
<li> command line:
<ul>
<li> traceset file name
<ul>
<li> 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 </li>
</ul>
</li>
<li> number of physical pages <br />
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 </li>
</ul>
</li>
<li> traces
<ul>
<li> 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 </li>
</ul>
</li>
</ul>
<h2>Output </h2>
<ul>
<li> 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) </li>
<li> 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: <br />
<em>Total pages used 4144; total page faults 96795; total victims 95437 <br />
</em>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). </li>
<li> The program also produces output showing statistics per
process.</li>
</ul>
<h2>Compiling</h2>
<ul>
<li> two command lines are provided, to compile the given version
(designed to be run in the directory of the source files):<br />./compile-clock </li>
<li> and the version you are to develop:<br />./compile-fifo </li>
<li> in both cases, the compiled program will be installed
in a directory called Run</li>
</ul>
<h2>Running</h2>
<ul>
<li> to run the given program (once compiled) with the default trace
file and 42 physical frames:<br />
cd Run <br />
./sim-replace-clock traceset.text 42<br />
and to run your program<br />
cd Run <br />
./sim-replace-fifo traceset.text 42 </li>
</ul>
<p>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. </p>
<p>virtualMemoryFIFO.c<br />
<textarea name="c" cols="82" rows="358" readonly="readonly" title="C Code - Copyright 2004 Ned Martin">// virtualMemoryFIFO.c -- functions for simulating virtual memory
// initial version uses a simple first-in first-out strategy
// Philip Machanick
// 3 May 2004
// Rewritten by Ned Martin #40529927, using some existing code
// 22-MAY-2004, Initial Coding
// 25-MAY-2004, Debug, Testing, Code cleanup
// Version 42.0 (actually version 83 but that's embarassing)
#include "virtualMemory.h"
#include "generalTypes.h"
#include <stdio.h>
#include <assert.h>
// types, functions and data for use only in this file
static const Byte unused = 0x0, used = 0x1;
// node for linked list
struct FrameNode;
// representation of page file
typedef struct PhysicalStatus {
int ownerPID; // owner process ID
void * PTentry; // keep general for diff. page tables
struct FrameNode *fifoEntry; // pointer to corresponding FrameNode
Byte status; // unused in this implementation
} PhysicalStatus;
typedef struct FrameNode {
struct FrameNode *previous, *next; // pointers to nodes
Address statusIndex; // index into PhysicalStatus
} FrameNode;
// linked list holds FrameNodes
typedef struct FrameList {
FrameNode *head, *tail;
} FrameList;
// translate between index into free memory table and frame
// number -- here just >> or << DISPLACEMENTBITS, but should
// allow for space used up by OS
static Address freeMemoryFrame (int index);
static int freeMemoryIndex(Address pFrame);
static PhysicalStatus * memoryState;
static int numberOfFrames;
// linked list
static FrameList * fifoList;
//-----------function implementations-------------
// set up status of physical frames, all originally unused, unallocated
void initVM
(
Address maxPage // maximum number of page files
)
{
int i;
// malloc space for fifoList
fifoList = (struct FrameList*) malloc (sizeof(struct FrameList));
// initialise fifoList, set head and tail to null
fifoList->head = fifoList->tail = NULL;
// copied from virtualMemoryClock.c
// physical pages numbered 0..maxPage (displacement bits included)
// must add 1 to allow highest page number as an array index
// should resize to subtract OS memory but that sounds hard
numberOfFrames = freeMemoryIndex (maxPage) + 1;
// copied from virtualMemoryClock.c
memoryState = (struct PhysicalStatus*)
malloc (sizeof(struct PhysicalStatus)*numberOfFrames);
// copied from virtualMemoryClock.c
// set all frames to unused, unallocated
for ( i = 0; i < numberOfFrames; i++ )
{
memoryState[i].ownerPID = -1;
memoryState[i].PTentry = NULL;
memoryState[i].fifoEntry = NULL;
// we don't use this but keep for compatibility
memoryState[i].status = unused;
}
} // end initVM
// tell VM a page has been added and add it to fifoList
void informVMNewPage
(
int pid, // owner process id
Address vAddress, // unused
Address pAddress, // physical address
void *entryInPT // pointer to entry in page table
)
{
// convert pAddress into pFrame
Address pFrame = freeMemoryIndex (pAddress);
if (pFrame < numberOfFrames)
{
// make new node
FrameNode *newNode =
(struct FrameNode*) malloc (sizeof(struct FrameNode));
// set memoryState
memoryState[pFrame].ownerPID = pid;
memoryState[pFrame].PTentry = entryInPT;
// link fifoEntry to the new node
memoryState[pFrame].fifoEntry = newNode;
// link node back to memoryState frame
newNode->statusIndex = pFrame;
// add node to end of fifoList
// if fifoList is empty
if( NULL == fifoList->head )
{
// point head and tail to this node which is first node
// [new_node]
fifoList->head = newNode;
fifoList->tail = newNode;
// node is only node, so next and previous to null
// they are already null
}
// else fifoList is not empty so add node to list
else
{
// add node to list
// handle existing tail node
// set next in tail node to new node
// ...[<-tail->][new_node]
fifoList->tail->next = newNode;
// set previous in new node to tail node
// ...[<-tail->][<-new_node]
newNode->previous = fifoList->tail;
// set next in new node to null
// already set to null
// point tail to new node
// ...[<-old_tail->][<-new_tail]
fifoList->tail = newNode;
}
}
// else physical frame is larger than number of frames
else
{
// copied from virtualMemoryClock.c
// make error message
char message [80];
sprintf (message,
"attempt to use frame 0x%x bigger than largest physical"
" frame 0x%x",
freeMemoryIndex(pFrame),
freeMemoryIndex(numberOfFrames));
handleError (message, EXIT, PHYSFRAMETOOBIG);
}
} // end informVMNewPage
// This is not needed for this implementation
void informVMPageUsed
(
int pid, // unused
Address vAddress, // unused
Address pAddress, // unused
void *entryInPT // unused
)
{
// We do nothing for this implementation
} // end informVMPageUsed
// memory manager tells VM this page is no longer in use
// so modify its status in our local data structures to no longer available
void freeFrame
(
Address frame // address of frame to free
)
{
// convert frame into pFrame
Address pFrame = freeMemoryIndex(frame);
// attempt to free unused page
// copied from virtualMemoryClock.c
// if frame was not used/allocated
if (memoryState[pFrame].ownerPID == -1
|| memoryState [pFrame].PTentry == NULL)
{
char message [80];
sprintf (message,
"attempt to use deallocate unused page frame 0x%x",
(int) pFrame);
handleError(message, EXIT, FREEUNUSEDMEM);
}
// set that frame to unused, unallocated again
memoryState[pFrame].ownerPID = -1;
memoryState[pFrame].PTentry = NULL;
// remove node from list
// need to handle case when it's the last or first node
// if the node was the tail, fix tail
// if node's next == null
// ...[<-prev->][<-tail]null
// point tail to prev
// set prev->next to null
if( NULL == memoryState[pFrame].fifoEntry->next )
{
fifoList->tail = memoryState[pFrame].fifoEntry->previous;
memoryState[pFrame].fifoEntry->previous = NULL;
}
// if the node was the head, fix head
// if node's previous == null
// null[head->][<-next->]...
// point head to next
// set next->previous to null
if( NULL == memoryState[pFrame].fifoEntry->previous )
{
fifoList->head = memoryState[pFrame].fifoEntry->next;
memoryState[pFrame].fifoEntry->next = NULL;
}
// if not head or tail
if( memoryState[pFrame].fifoEntry->next &&
memoryState[pFrame].fifoEntry->previous )
{
// fix node pointers to remove node
// ...[<-prev->][<-node->][<-next->]...
// prev->next
// prev<-next
memoryState[pFrame].fifoEntry->previous->next =
memoryState[pFrame].fifoEntry->next;
memoryState[pFrame].fifoEntry->next->previous =
memoryState[pFrame].fifoEntry->previous;
}
// free the node
free (memoryState[pFrame].fifoEntry);
// set the frame's fifoEntry to null
memoryState[pFrame].fifoEntry = NULL;
} // end freeFrame
// find a replacement victim for a page fault for process pid in the
// case of a global replacement policy, ignore pid for a local policy,
// we will need to have one physical memory table per process return
// the page number
//
// return the page number: in this simple implementation, just the index to the
// table left-shifted DISPLACEMENTBITS
//
// SHOULD ONLY BE CALLED IF ALL PHYSICAL FRAMES ALLOCATED
// otherwise the free memory handler will instead provide
// a free frame
Address selectVictim
(
int pid // process id
)
{
// set a temporary variable so I can free head node
Address tempAddress = fifoList->head->statusIndex;
// list cannot be empty
assert (NULL != fifoList->head);
// if this is not the last node in the list
// [head->][<-next->]...
if( fifoList->head->next )
{
// remove head node
// set head to next which is head->next
// null[head->][<-next->]...
// temporary pointer to the next node
FrameNode *tempPointer = fifoList->head->next;
// free the old head node
free (fifoList->head);
// set the list head to the next node
// [...undef...][<-new_head->][<-next->]...
fifoList->head = tempPointer;
// set previous in new head to null
// note head here is the new head, not the old head
// null[new_head->][<-next->]...
fifoList->head->previous = NULL;
}
// else there is no head->next (was the last node) so set head to null
// null[head]null
else
{
// free the old head node
free (fifoList->head);
// set head to null
fifoList->head = NULL;
// list is now empty
}
// copied from virtualMemoryClock.c
// invalidate the memory
invalidate(memoryState[tempAddress].PTentry);
// copied from virtualMemoryClock.c
// in case more stats needed
addVictimToStats(pid);
// return address that was held by head of fifoList
return freeMemoryFrame(tempAddress);
} // end selectVictim
//-----------local function implementations-------------
// copied from virtualMemoryClock.c
// translate between index into free memory table and frame
// number -- here just >> or << DISPLACEMENTBITS, but should
// allow for space used up by OS
static int freeMemoryIndex
(
Address pFrame
)
{
return pFrame >> DISPLACEMENTBITS;
}
static Address freeMemoryFrame
(
int index
)
{
return index << DISPLACEMENTBITS;
} // end
</textarea>
<br />
Portions of code © Copyright 2004 Ned Martin</p>
<p>04-Jun-2004</p>
</body>
</html>