Assigned Date: Monday, Apr. 18, 2011
Due Date: Monday, May 2, 2011
Due Time: 11:50am
Last modified on April 29, 2011, at 03:18 PM (see updates)
NOTE: This homework is an extension of homework 3. The extension involves adding memory management and page replacement algorithms. It also changes the format of the input data.
This is a pair-programming assignment (i.e., you may work with one partner). You may discuss the assignment only with your partner or the instructor/grader.
This assignment focuses on Memory Management with C, and in particular:
- To gain experience with virtual memory management.
- To gain experience with page faults and paging algorithms.
- To gain more experience with linked lists and process simulation.
Create a virtual memory management simulation in C that implements a Random-Replacement (Random), First-In-First-Out (FIFO), and Not-Recently-Used (NRU) page replacement algorithms.
Using the code from homework 3, implement a First-Come-First-Serve process scheduling algorithm, which will read in processes from an input file. Each process will now have a memory requirement (i.e., number of pages it needs), which will be used in the creation and management of a page and frame table.
The Random, FIFO, and NRU page replacement algorithms will be implemented to handle loading pages into memory (and storing pages, if modified, back to the backing store). Since, program execution is simulated, the loading (and saving of modified pages) will be also simulated (i.e., not actually performed).
This simulation will output the number of page faults, the miss rate, and the number of modified pages evicted.
The first line of the input file will contain 3 integer values. The first value is the seed to the random number generator
srand() (so results can be reproduced). The second value specifies the page replacement algorithm to use (Random =
'r', FIFO =
'f', NRU =
'n'). The third value is the maximum number of frames that physical memory can store. You may assume that the first and second values are separated by a single space character.
On each additional line, the input file will contain 3 integers describing a single process to be run. The first integer is the process ID, the second integer is the total execution time for the process, and the third integer is the required memory for the process.
You should ignore anything past the third integer on each line.
The file may contain an arbitrary number of lines (processes).
Example file contents:
12345 r 20 # seed for random number generator, the scheduler to use and the number of frames
0 4 3 # first process ID is 0, it will execute in 4 seconds, and requires 3 pages
1 2 5 # ... 2 78
Your program should output a single line for each page fault, for example, as follows:
Page fault: Process 3, page 4 loaded in frame 10.
Your program should also output the total number of page faults generated, the miss rate for the current page-replacement algorithm, and the number of modified pages evicted.
Total page faults = 85
Miss rate = 34%
Modified pages evicted = 40
where miss rate is calculated as follows:
miss rate = page faults / total number of references
As in homework 3, each process should be stored in C structs as PBRs.
A single, global page table will be used to map virtual addresses to physical addresses. To differentiate between processes in the page table, the process ID is used as an initial index into the table.
Note: You may assume that the maximum possible number of processes is 100 (ID ranges from 0 to 99), and that the maximum possible number of page frames is 100.
To simulate memory references, for every time unit that a process runs, it will perform a single page reference. The page that's referenced will be decided using
rand(). For example, if a process has 5 pages then every time unit you'll generate a random number between 1 and 5 and make a memory reference to that page.
Another call to
rand() will tell you if the program will make a modification to this page (i.e., whether to set the page's modification bit). There is a 50% chance for modifications to happen.
All processes will start out with zero pages currently in memory. The first time a page is referenced it will need to be “page faulted” in. That is, a free frame in physical memory will need to be allocated and an entry in the page table will need to be created to point to it.
If physical memory is full, a page replacement algorithm will be used to select a page from memory, move it to the backing store and load in the requested page. For this simulation, we will not implement a backing store, i.e., you simply overwrite the page information.
Note: If the NRU page replacement algorithm cannot find a page to evict that is not referenced, then it should mark all pages as not referenced (aging) and try again. (Hint: a recursive call would be fine.)
Your program should deallocate all the space it allocated.
Modularize your design using meaningfully-named, well-documented functions.
The above simulation is simplistic. It stops short of creating and allocating main memory to the incoming processes. As is, each page is assigned to a page frame (in the page table), but that page frame (which is an index to the main memory area used to store the page) is unused.
So to make things more realistic, in addition to the above, have your program allocate physical memory (an array of ints) using
malloc(), at run time. The size of the array will be determined by the number of page frames stated in the (first line of) the input file. (Remember to deallocate that memory at the end of the simulation.)
For now, let's make each page be 10 ints (memory locations) long. (Hint: Define this as a constant at the top of your program.) The array is contiguous, i.e., page frame boundaries are imaginary (calculated using the page frame number and the length of each page).
(The information below is repeated/modified from above - see bold for modifications.)
- The first time a page is referenced it will need to be “page faulted” in. That is, a free frame in physical memory will need to be allocated and an entry in the page table will need to be created to point to it. For this simulation (instead of actually loading the process's data/code into the page frame, let's just store the process ID in *every* memory location of this page.
- To simulate memory references, for every time unit that a process runs, it will perform a single page reference. The page that's referenced will be decided using
rand(). For example, if a process has 5 pages then every time unit you'll generate a random number between 1 and 50 (50 = 5 pages * 10 locations per page) and make a reference to that memory location. (Hint: Recall that C arrays (i.e., your main memory) are zero-indexed - you will need to account for that in your memory references.)
- Another call to
rand() will tell you if the program will make a modification to this memory location (i.e., whether to set the page's modification bit). There is a 50% chance for modifications to happen. If a modification happens, then simply decrement this memory location by 1.
- If physical memory is full, a page replacement algorithm will be used to select a page from memory, move it to the backing store (if modified-bit is set), and load in the requested page. For the bonus part, when a page gets evicted, print the process ID, and the page frame number (of the evicted page) to the standard output. If the page was modified, also print out the modified page information (all 10 ints). (If this were a real OS, you would be storing the modified page in secondary storage.). Then, simply overwrite the page information in main memory.
Follow the Golden Rule of Style: "A program should be as easy for a human being to read and understand as it is for a computer to execute." 
In general, you should comment any variable, obscure statement, block of code, etc. you create.
Also, you should comment why something is being done, e.g.,
numStudents += 1; /* we have processed one more student */
as opposed to how it is done, e.g.,
numStudents += 1; /* increment numStudents by one */
Finally, your code should always include opening comments as follows.
(NOTE: Angle brackets signify information that needs to be filled out. Remove the angle brackets!)
Author: <Your Name(s)>
Email: <Your email address(es)>
Class: CSCI 340, Section 1
Due Date: <The assignment's due date>
Certification of Authenticity <remove one of the following>:
I certify that this lab is entirely my own work.
I certify that this lab is my own work, but I received
some assistance from: <Name(s)>
TASK: <Provide a simple, yet complete description of the task being
performed by this program. It may be several sentences long.>
INPUT: <Describe the input to this program. Be thorough.>
OUTPUT: <Describe the output to this program. Be thorough.>
You will submit your assignment via the stono
submit command, as follows:
% submit csci340 hmwk5 virtualMemorySimulation.c
No other submission mechanism will be accepted (e.g., email).
Your assignment will be graded based on the documentation, formatting, and correctness of your source code. Also the completeness / thoroughness of your work, and how well you followed the homework instructions.
- Cooper, D. and Clancy, M. (1985) "Oh! Pascal", 2nd ed., W.W. Norton & Company, New York, p. 42.