CPS 104
Problem PC

Virtual Memory Simulator and Test

You are to modify your MYMIPS simulator so the simulator includes a
simulation of a simple virtual memory system.  You must also write a MYMIPS
program to specifications in this assignment, which can be used to test your
simulator.

1.  Modify your MYMIPS simulator so that it simulates programs that run in a
virtual memory environment.  This version of the simulator should maintain
a small main memory array MEMORY[], whose size is only 2^14 bytes.  That
array should be "backed up" by another, called DISK[], which simulates a
hard disk used as a swapping device.  The simulator should use a page size
of 512 bytes.  When the simulator encounters a page fault, the simulator
itself should perform the actions normally done by an Operating System to
manage memory.  That is, the simulator should select a page frame in MEMORY
to hold the referenced page, save the contents of that page frame in array
DISK if necessary (compute a dirty bit, and use it in selecting which page
to replace), and copy the referenced page from DISK to the selected page
frame of MEMORY.  The simulator should also update its Page Table appropriately.

In selecting a page to replace, use the "Not Recently Referenced"
rule.  See Slide 17 of the lecture on Virtual Memory.  Instead of
moving the "lrp" pointer once on each "clock tick", you can move it
only on a page fault.  Use of this rule requires that the simulated
hardware set the "referenced" bit in the appropriate Page Table entry
whenever the simulated program references a page.

For simplicity, you can assume that DISK holds a complete image
of virtual memory, so that (a) the program to be run can be loaded into
DISK, rather than MEMORY, and (b) the data with virtual address i will be
found at DISK[i].  Note that your program MUST copy the data into MEMORY,
before allowing the simulated program to access it.  Clearly, DISK will
hold 2^19 bytes.

When the program being simulated exits, the simulator should print one line
of output, using the command below:
	printf("Ref=%d, PageIns=%d, PageOuts=%d\n", Refs, PgI, PgO);
where the program computes the number of references to virtual MEMORY (Refs),
the number of Page In operations executed by the simulator (PgI), and
the number of Page Out operations executed by the simulator (PgO).

2.  Translate the following C program into MYMIPS assembly language, and
submit the resulting file, as a test program.  During your own testing, you
should (a) compare the output the C program gets with the output the
translated program gets, when run on your unmodified MYMIPS simulator;
(b) compare the output either program gets with the output the translated
program gets when run on your MODIFIED MYMIPS simulator.


/* Test program to fill an array with Fibbonacci-like integers, then probe
a sequence of locations in it, and report the contents of the last location.
Probed locations will be modified, as well.  */
#include <stdio.h>
int A[1<<16];

int main() {
	int a,b, i,k;
	int t,u,v;
	int max,msk;

	scanf("%d %d %d %d", &a, &b, &i, &k);

	max = 1<<16;
	for (t=0; t<max; t++) {
		A[t] = a;
		u=a+b;
		a=b;
		b=u;
		}

	msk = max-1;
	for (t=0; t<k; t++) {
		u = A[i];
		A[i]--;
		printf(" %d\n",i);
		i = u&msk;
		}

	printf("%d\n",i);
	}

=====
My translation of this program uses 42 lines of mymipsasm source code,
and produces an output file of 42 lines and 378 characters.  (Note: You can
avoid initializing all words in array A to zero, by arranging array A to be
defined AFTER all the code and other data, as ".space 4".  Actually, the
program will use location A, ..., A+2^18, but the program initializes them,
so there is no need for the mymipsasm output file to do so.)

When run on my MYMIPS simulator on the input file
2 3 2 1000
the program takes about 0.20 seconds of user time.