Spring2012.CSCI340Homework4 History

Hide minor edits - Show changes to markup

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:
  1. 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.)
  2. 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.
  3. 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:
  1. 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:
  1. 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 on-line binary/decimal/hexadecimal converter may come in handy.
Changed line 1 from:

Assigned Date: Monday, Apr. 16, 2012\\

to:

Big textAssigned 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 (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.
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 (28). 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: