Spring 2012»CSCI 340 Homework 4

CSCI 340 Homework 4

Big textAssigned Date: Monday, Apr. 16, 2012
Due Date: Monday, Apr. 30, 2012
Due Time: 7:50am

Last modified on April 29, 2012, at 09:27 PM (see updates)

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.

Purpose

This assignment focuses on Memory Management with C, and in particular the following learning objectives:

  • Learn and apply the C programming language for systems development (on Unix environments).
    • Gain more experience with linked lists and process simulation.
  • Understand the principles of memory management
    • Gain experience with page faults and paging algorithms.

Assignment

Create a virtual memory management simulation in C that implements a Random-Replacement (random.c), First-In-First-Out (fifo.c), and Not-Recently-Used (nru.c) page replacement algorithms.

We will utilize a multi-level page table, as follows:

  • Virtual address size is 16 bits (i.e., it can address 65536 memory cells):
    • 4 most significant bits indicate index within the 1st-level page table (i.e., this location contains the address of a 2nd-level page table);
    • 4 middle bits indicate index within the specific 2nd-level page table (i.e., this location is a traditional page-table entry - described below); and
    • 8 least significant bits indicate index (offset) within the particular memory frame (as specified the page-table entry above); the pointed frame location contains the desired information.

Details

  1. The memory management data structure should be implemented as follows:
    • The 1st-level (or meta) page table is an array of 16 entries (24). Each entry is a pointer to a page table.
    • Each 2nd-level (or regular) page table is an array of 16 entries (24). Each entry is a PAGE_TABLE_ENTRY C struct.
    • Each PAGE_TABLE_ENTRY struct contains the following fields:
      • Field referenced is a single bit (declare as unsigned referenced:1; - this will tell the compiler to use a single bit, if possible). This is 0 if the corresponding page frame is unreferenced, 1 otherwise. When a page is first loaded into memory is unreferenced. When an address on a given page is accessed for read or write, the page becomes referenced.
      • Field modified is a single bit (see above). This is 0 if the corresponding page frame is unmodified, 1 otherwise. When a page is first loaded into memory is unmodified. When an address on a given page is accessed for write, the page becomes modified.
      • Field inMemory is a single bit. This is 0 if the page is not in memory, 1 if the page is currently occupying a frame. This bit is set when we load a page into memory (reacting to a page fault). This bit should be reset when a page is evicted.
      • All above fields should be initialized to zero (at beginning of simulation).
      • Field frameNumber is a byte (actually, an unsigned char). It points to the actual frame in memory for this page (if inMemory), undefined otherwise.
    • MainMemory is an array of unsigned ints. The size of memory is a multiple of page frame size (28). The number of frames in memory is specified in the simulation input (see below).
      • For this simulation, MainMemory should be initialized to increasing integers starting from 0 (i.e., the first memory cell should contain 0, the second 1, and so on).
  2. For simplicity, we will only run a single process per simulation (this could be easily generalized using last assignment's process scheduling code).
  3. The process will include a number of simulated executable statements. Each simulated statement consists of two numbers:
    • an unsigned int (specifying the address to access in MainMemory)
    • 0 or 1 specifying if this is a read or a write statement. (Hint: Write statements should set the modified bit of the corresponding page.)
    • For write statements you should modify the contents of the corresponding memory location - simply add 1 to the contents.
  4. Each page replacement algorithm (Random-Replacement, First-In-First-Out, and Not-Recently-Used) may use one or more lists to keep allocated frames. These lists should be implemented as linked-lists. (Hint: Implement a simple linked-list data structure and store it in file linkedList.h. Then import this file in any program that needs it.)
  5. Each of your programs (random.c, fifo.c, and nru.c) should be executable on its own. For example, to test your Random-Replacement algorithm, I should be able to compile and run random.c by itself.
  6. Your program should get its input from the standard input. The simulation input looks as follows:
1     # number of frames in main memory
6     # number of statements in program
0 0   # access page 0, offset 0 for read
257 1 # access page 1, offset 1 for write
515 1 # access page 2, offset 3 for write
3 1   # access page 0, offset 3 for write
3 0   # access page 0, offset 3 for read
3 0   # access page 0, offset 3 for read
 

Output

Your program should print the following information to the standard output:

  • For every memory address accessed, it should output the address and contents of that memory location.
  • For every page fault (i.e., page not found in memory), it should output the frame selected to load it (and whether that frame was previously referenced and modified).
  • At the end, it should also output the number of page faults, the hit/miss ratio, the number of modified pages evicted, and the modified evicted page ratio.

For example, given the above input, your program should output the following:

PAGE FAULT: page 0 not in memory - using frame 0 (was referenced 0, modified 0)
Accessing memory location 0 - it contains 0
PAGE FAULT: page 1 not in memory - using frame 0 (was referenced 1, modified 0)
Accessing memory location 257 - it contains 1
PAGE FAULT: page 2 not in memory - using frame 0 (was referenced 1, modified 1)
Accessing memory location 515 - it contains 3
PAGE FAULT: page 0 not in memory - using frame 0 (was referenced 1, modified 1)
Accessing memory location 3 - it contains 4
Accessing memory location 3 - it contains 5
Accessing memory location 3 - it contains 5

Simulation Statistics:
Page faults: 4
Hit/Miss Ratio: 2/4 (50.00 %)
Modified pages evicted: 2
Modified/Total Ratio: 2/4 (50.00 %)
 

Notes

  • To extract groups of bits from an integer use C's bit-mask operations (&, |, ^). For example, the following extracts the 2nd (from the right) group of 4 bits from integer x:
unsigned int x = 4360;   // same as x = 0x1000 + 0x0100 + 0x0008;
int value = x & 0x00F0;
 

Documentation

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." [1]

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
   Assignment: HMWK4
   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.>

*/

 

Submissions

You will submit your assignment via the stono submit command, as follows:

% submit csci340 hmwk4 random.c fifo.c nru.c memoryManagement.h linkedList.h

where memoryManagement.h and linkedList.h contain common data structure and function prototypes and definitions shared by all programs.

No other submission mechanism will be accepted (e.g., email).

Grading

Your assignment will be graded based on the simplicity and elegance of your solution. Avoid verboseness of code. Also on the documentation, formatting, and correctness of your source code. And how well you followed the homework instructions.

Reference

  1. Cooper, D. and Clancy, M. (1985) "Oh! Pascal", 2nd ed., W.W. Norton & Company, New York, p. 42.