Lab 5: Virtual Memory

Due: Thursday, March 29, 2012 by 10:00 PM

Lab description

For this lab you will simulate virtual memory and handling page faults. There will be very small secondary and primary memories. Specifically:

Page / frame size: 64 bytes
Primary memory size: 8 frames (RAM)
Secondary memory size: 64 frames (disk)
Virtual memory size: 64 pages

Simulate the memories with one dimensional char arrays. Keep the page table in the last frame in primary memory. Additionally, for page replacement, use the FIFO algorithm.

More specific instructions

Read in secondary memory from a filename passed in as the first command-line argument.
Read in the list of memory references from a filename passed in as the second command-line argument. Each line of the file will contain a memory reference (in decimal). You can think of each one of these references as an instruction to read and print a byte at a specified memory location. There will not be more than 100 references.
Using the reference, calculate the page number and page offset.
Using the page number, check the page table. If the page is resident in primary memory, then it should locate the byte at the respective offset and print it to stdout. If the page is not resident in primary memory, then the program should:
1. Determine a victim frame using the FIFO algorithm
2. Invalidate any previous page table entries that used that frame
3. Load the frame into primary memory
4. Update the page table
5. Calculate the location of the byte in primary memory and print it
When the program has finished all the references, it should print three blank lines. Then, print the non-page table frames of primary memory, each on a separate line (replacing the '\n' characters with '#'s). Then, print "Page Table Contents: " followed by the page table entries as ints, separated by commas. Use a "-1" to indicate that a frame is not resident in memory. Print two newlines. Finally, print "Page Faults: " followed by the number of page faults. Your stdout should match the Example Output below exactly.
Print any debugging or extra information to stderr. For the grading scripts to work correctly (and you want them to work correctly), stdout must contain only the specified information.
As with a real system, you should only be reading the individual bytes from primary memory. Only while handling a page fault should the program access secondary memory.

Note: While page table entries are normally larger than a byte, for this lab just use a single byte for each page table entry.

Testing

For testing purposes, use at least the following files:
Set 1:

Secondary Memory File: secondary.txt
References File: references.txt
stdout File: set1-stdout.txt

Set 2:

Secondary Memory File: ascii-repeated.txt
References File: ascii-repeated-references.txt
stdout File: ascii-repeated-stdout.txt

If your program is correct, use of either of the test sets will cause something legible to be printed.
Use can use the labTester.sh (right-click on link to download) script to test the output of your program. The parameters to the script are:

Filename of expected stdout output
Filename of executable
Command-line argument(s) to the executable file

For example:

  chmod 755 labTester.sh
  ./labTester.sh  ascii-repeated-stdout.txt  lab5  ascii-repeated.txt  ascii-repeated-references.txt

If the stdout of the executable matches that of the key, then all you should see is the following:

The output and the answer key match perfectly!!!

After logging into ranger, you can copy labTester.sh with the following command:

  cp /nfshome/hcarroll/public_html/3250/labTester.sh .

Example Output

Example output is for set 2 of the testing files.
$ ./lab5 ascii-repeated.txt ascii-repeated-references.txt

stdout: (shown as formatted to 80 characters wide for display reasons)
OS class ROCKS


 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_
`abcdefghijklmnopqrstuvwxyz{|}~# !"#$%&'()*+,-./0123456789:;<=>?
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~#
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~#
`abcdefghijklmnopqrstuvwxyz{|}~# !"#$%&'()*+,-./0123456789:;<=>?
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~#
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~#
Page Table Contents: -1,1,2,-1,4,6,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-
1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,5,-1,

Page Faults: 8

stderr:
Found 14 references in ascii-repeated-references.txt
reference: 47
	pageNum: 0, pageOffset: 47
	page table entry: -1
	page fault (victim frame: 0)
reference: 51
	pageNum: 0, pageOffset: 51
	page table entry: 0
reference: 96
	pageNum: 1, pageOffset: 32
	page table entry: -1
	page fault (victim frame: 1)
reference: 163
	pageNum: 2, pageOffset: 35
	page table entry: -1
	page fault (victim frame: 2)
reference: 172
	pageNum: 2, pageOffset: 44
	page table entry: 2
reference: 3809
	pageNum: 59, pageOffset: 33
	page table entry: -1
	page fault (victim frame: 3)
reference: 275
	pageNum: 4, pageOffset: 19
	page table entry: -1
	page fault (victim frame: 4)
reference: 4019
	pageNum: 62, pageOffset: 51
	page table entry: -1
	page fault (victim frame: 5)
reference: 96
	pageNum: 1, pageOffset: 32
	page table entry: 1
reference: 338
	pageNum: 5, pageOffset: 18
	page table entry: -1
	page fault (victim frame: 6)
reference: 47
	pageNum: 0, pageOffset: 47
	page table entry: 0
reference: 419
	pageNum: 6, pageOffset: 35
	page table entry: -1
	page fault (victim frame: 0)
	invalidating page table entry index: 0
reference: 331
	pageNum: 5, pageOffset: 11
	page table entry: 6
reference: 3987
	pageNum: 62, pageOffset: 19
	page table entry: 5

Submission

Submit the source code file using the handin program. For example, to submit the code for this lab, type the following in a terminal exactly as it appears:

  handin  lab5  lab5.cpp

Alternatively, you can submit the assignment from any computer via PeerSpace. After successfully logging into PeerSpace, go to Tools, then Assignments. Click on the Submit link.

Rubric:

Points          Item
----------      --------------------------------------------------------------
_____ / 40      Correctly outputs individual chars to stdout
_____ / 25      Correctly outputs primary memory contents to stdout  
_____ / 25      Correctly outputs page table to stdout		      
_____ / 10      Correctly outputs number of page faults to stdout    

_____ / 100

Hints

Start by writing the major steps as pseudocode and saving them as comments. Then, fill out the next level of steps as pseudocode (same them as comments in the code as well).
Use a "-1" to indicate that a frame is not resident in memory.
Each entry in the page table is a char (one byte). To print the each entry as a number, do something like the following:
```
printf( "%d,", (int) primaryMem[ PAGE_TABLE_START + pageTableIndex ]);
```
where pageTableIndex is a loop variable that ranges from 0 to the number of pages in virtual memory.
Q: I overheard that we had to copy the files in a specific manner. Will copy and paste work?
A: As with all of the labs, it's better to download the file or copy the entire file on the command-line. Copying and pasting may not get the last character correctly. To download the file, use a browser and either choose something like "save link as..." or pull-up the page and choose "save". To copy it on the command-line, execute something similar to "cp /nfshome/hcarroll/public_html/3250/ascii-repeated.txt .".
In the Example Output above, the display width was artificially set to 80 characters wide. The page table contents should all be on one line.

Source: Recycled (with numerous modifications) from Dr. Pettey.

CSCI 3250

Operating Systems