Spring2012.CSCI340Homework4 History

Hide minor edits - Show changes to output

Changed lines 78-79 from:
* At the end, it should also output the number of page faults, the miss rate, the number of modified pages evicted, and the modified/unmodified evicted page ratio.
to:
* 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.
Changed line 98 from:
Modified/Unmodified Ratio: 2/4 (50.00 %)
to:
Modified/Total Ratio: 2/4 (50.00 %)
Changed line 41 from:
*** Field @@frameNumber@@ is a byte (actually, an @@unsigned char@@). It points to the actual frame in memory for this page (if @@present@@), undefined otherwise.
to:
*** Field @@frameNumber@@ is a byte (actually, an @@unsigned char@@). It points to the actual frame in memory for this page (if @@inMemory@@), undefined otherwise.
Changed lines 2-3 from:
'''Due Date''': Monday, Apr. 23, 2012\\
'''Due Time''': 10:50am
to:
'''Due Date''': Monday, Apr. 30, 2012\\
'''Due Time''': 7:50am
Changed line 41 from:
*** Field @@frameNumber@@ is a byte. It points to the actual frame in memory for this page (if @@present@@), undefined otherwise.
to:
*** Field @@frameNumber@@ is a byte (actually, an @@unsigned char@@). It points to the actual frame in memory for this page (if @@present@@), undefined otherwise.
Changed lines 37-39 from:
*** 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. Every page loaded into memory should be viewed as referenced.
*** Field @@modified@@ is a single bit (see above). This is 0 if the corresponding page frame is unmodified, 1 otherwise. Every page loaded into memory should be viewed as unmodified.
*** 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 is set when we load Every page loaded into memory should be viewed as unmodified.
to:
*** 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
.
Changed line 106 from:
unsigned int x = 4360 // same as x = 0x1000 + 0x0100 + 0x0008;
to:
unsigned int x = 4360; // same as x = 0x1000 + 0x0100 + 0x0008;
Changed lines 51-52 from:
** For write statements you should modify the contents of the corresponding memory location - simply add 1 to the contents.
to:
** '''For write statements''' you should modify the contents of the corresponding memory location - simply '''add 1 to the contents.'''
Changed lines 103-104 from:
* To extract groups of bits from an integer use C's bit-mask operations (&, |, ^). For example, the following extracts the 2nd (most-significant) group of 4 bits from integer @@x@@:
to:
* 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@@:
Changed line 110 from:
* Use hexadecimal notation, e.g., 0xF000, to create appropriate masks.
to:
* Use hexadecimal notation, e.g., @@0xF000@@, to create appropriate masks.
Changed line 92 from:
Accessing memory location 3 - it contains 6
to:
Accessing memory location 3 - it contains 5
Changed line 167 from:
where @@memoryManagement.h@@ contains common data structure and function prototypes and definitions shared by all programs.
to:
where @@memoryManagement.h@@ and @@linkedList.h@@ contain common data structure and function prototypes and definitions shared by all programs.
Changed line 165 from:
@@% submit csci340 hmwk4 random.c fifo.c nru.c memoryManagement.h@@
to:
@@% submit csci340 hmwk4 random.c fifo.c nru.c memoryManagement.h linkedList.h@@
Changed lines 53-56 from:
!!!Input

Your
program should get its input from the standard input. The simulation input looks as follows:
to:
# 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.)

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

#
Your program should get its input from the standard input. The simulation input looks as follows:
Changed lines 74-75 from:
* For every memory address accessed, it should output the address and contents of that memory location.:
to:
* For every memory address accessed, it should output the address and contents of that memory location.
Changed line 103 from:
* To extract groups of bits from an integer use C's bit-mask operations (&, |, ^). For example, the following demonstrates how to extract the 2nd (most-significant) group of 4 bits from integer @@x@@:
to:
* To extract groups of bits from an integer use C's bit-mask operations (&, |, ^). For example, the following extracts the 2nd (most-significant) group of 4 bits from integer @@x@@:
Changed line 46 from:
# For simplicity, we will only run a single process per simulation (this could be easily generalized by merging this code with last assignment's process scheduling code).
to:
# For simplicity, we will only run a single process per simulation (this could be easily generalized using last assignment's process scheduling code).
Added lines 98-110:

!!Notes

* To extract groups of bits from an integer use C's bit-mask operations (&, |, ^). For example, the following demonstrates how to extract the 2nd (most-significant) group of 4 bits from integer @@x@@:

(:source lang=c tabwidth=3 -trim:)
unsigned int x = 4360 // same as x = 0x1000 + 0x0100 + 0x0008;
int value = x & 0x00F0;
(:sourcend:)

* Use hexadecimal notation, e.g., 0xF000, to create appropriate masks.

* An [[http://www.mathsisfun.com/binary-decimal-hexadecimal-converter.html | on-line binary/decimal/hexadecimal converter]] may come in handy.
Changed line 1 from:
'''Assigned Date''': Monday, Apr. 16, 2012\\
to:
'+Big text+''''Assigned Date''': Monday, Apr. 16, 2012\\
Changed lines 19-20 from:
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.
to:
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.
Changed lines 32-35 from:
** The '''1st-level''' (or meta) page table is an array of 16 entries (2^4). Each entry is a pointer to a page table.

** Each '''2nd-level''' (or regular) page table is an array of 16 entries (2^4). Each entry is a @@PAGE_TABLE_ENTRY@@ C struct.
to:
** The '''1st-level''' (or meta) page table is an array of 16 entries (2'^4^'). Each entry is a pointer to a page table.

** Each '''2nd-level''' (or regular) page table is an array of 16 entries (2'^4^'). Each entry is a @@PAGE_TABLE_ENTRY@@ C struct.
Changed line 43 from:
** @@MainMemory@@ is an array of unsigned ints. The size of memory is a multiple of page frame size (2^8). The number of frames in memory is specified in the simulation input (see below).
to:
** @@MainMemory@@ is an array of unsigned ints. The size of memory is a multiple of page frame size (2'^8^'). The number of frames in memory is specified in the simulation input (see below).
Changed line 50 from:
** 0 or 1 specifying if this is a read or a write statement. (''Hint:'' Write statements should set the @@modified@@ but of the corresponding page.)
to:
** 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.)
Changed line 150 from:
@@% submit csci340 hmwk4 rr.c fifo.c nru.c memoryManagement.h@@
to:
@@% submit csci340 hmwk4 random.c fifo.c nru.c memoryManagement.h@@
Changed lines 72-82 from:
* For every memory address accessed, it should output the address and contents of that memory location:

Accessing memory location x - it contains y

* For every page fault (i.e., page not found in memory),
it should output:

PAGE FAULT: page x not in memory - using frame y (was referenced 0, modified 0)

* At
the end, it should also output the number of page faults, the miss rate, and the number of modified pages evicted.

For the above input
, your program should produce the following output:
to:
* 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 miss rate, the number of modified pages evicted, and the modified/unmodified evicted page ratio.

For example
, given the above input, your program should output the following:
Added lines 1-166:
'''Assigned Date''': Monday, Apr. 16, 2012\\
'''Due Date''': Monday, Apr. 23, 2012\\
'''Due Time''': 10:50am

Last modified on {$LastModified} (see [[http://www.cs.cofc.edu/~manaris/?n=Spring2012.CSCI340_Homework4?action=diff&source=n&minor=n | 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)''', '''First-In-First-Out (FIFO)''', and '''Not-Recently-Used (NRU)''' 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

# The memory management data structure should be implemented as follows:

** The '''1st-level''' (or meta) page table is an array of 16 entries (2^4). Each entry is a pointer to a page table.

** Each '''2nd-level''' (or regular) page table is an array of 16 entries (2^4). 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. Every page loaded into memory should be viewed as referenced.
*** Field @@modified@@ is a single bit (see above). This is 0 if the corresponding page frame is unmodified, 1 otherwise. Every page loaded into memory should be viewed as unmodified.
*** 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 is set when we load Every page loaded into memory should be viewed as unmodified.
*** All above fields should be initialized to zero (at beginning of simulation).
*** Field @@frameNumber@@ is a byte. It points to the actual frame in memory for this page (if @@present@@), undefined otherwise.

** @@MainMemory@@ is an array of unsigned ints. The size of memory is a multiple of page frame size (2^8). 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).

# For simplicity, we will only run a single process per simulation (this could be easily generalized by merging this code with last assignment's process scheduling code).

# 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@@ but of the corresponding page.)
** For write statements you should modify the contents of the corresponding memory location - simply add 1 to the contents.

!!!Input

Your program should get its input from the standard input. The simulation input looks as follows:

(:source lang=c tabwidth=3 -trim:)
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
(:sourcend:)

!!!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:

Accessing memory location x - it contains y

* For every page fault (i.e., page not found in memory), it should output:

PAGE FAULT: page x not in memory - using frame y (was referenced 0, modified 0)

* At the end, it should also output the number of page faults, the miss rate, and the number of modified pages evicted.

For the above input, your program should produce the following output:

(:source lang=c tabwidth=3 -trim:)
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 6

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

!!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.,

(:source lang=C tabwidth=3 -trim :)
numStudents += 1; /* we have processed one more student */
(:sourcend:)

as opposed to '''how''' it is done, e.g.,

(:source lang=C tabwidth=3 -trim :)
numStudents += 1; /* increment numStudents by one */
(:sourcend:)

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

(:source lang=C tabwidth=3 -trim :)
/*
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.>

*/
(:sourcend:)

!!Submissions

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

@@% submit csci340 hmwk4 rr.c fifo.c nru.c memoryManagement.h@@

where @@memoryManagement.h@@ contains 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

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