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
Comments	— — —
Class Average	—
Class Median	—
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.

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)

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).

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

• two command lines are provided, to compile the given version (designed to be run in the directory of the source files):
  ./compile-clock
• and the version you are to develop:
  ./compile-fifo
• in both cases, the compiled program will be installed in a directory called Run

Running

• to run the given program (once compiled) with the default trace file and 42 physical frames:
  cd Run
  ./sim-replace-clock traceset.text 42
  and to run your program
  cd Run
  ./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.

virtualMemoryFIFO.c
// 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
Portions of code © Copyright 2004 Ned Martin

04-Jun-2004