Programming Project 3: Paging

Assigned: March 30.
Due: April 29.

In this assignment, the STM has been modified to support paging. The JAVA code attached here provides a simulated architecture, a simulated disk, much of the "OS" code, and all of the data structures that you will need. Your task is to write the page fault handler and the disk driver for the simulated disk.

The Simulated Hardware

The STML language and the format of an STML file are unchanged from project 1.

The simulated hardware, which you may not change, is found in the file STM.java. The methods included here are:

The major data structures are

The Simulated Disk

The simulated disk is found in Disk.java. You are not allowed to change this code.

The disk communicates with the OS using an object of type DiskTask, found in DiskTask.java. A DiskTask consists of a disk address, a memory address, a size (number of words to transfer) and a flag "write". The flag "write" is true if the task is to write from memory to disk; it is false if the task is to read from disk to memory.

The disk works as follows: The OS sends the disk a series of requests, which it maintains in a set called "Requests". At each "machine cycle" -- more precisely, each time the method "DiskAction" is called -- if the set of pending requests is non-empty, the disk flips a coin to determine whether to take any action. With probability 3/4, it does nothing. With probability 1/4, it picks a pending request at random and carries it out. The method "DiskAction" returns the DiskTask that it has executed.

Note on random selection: My information is that the Java method java.util.Random, starting with a specified seed, returns the same sequence of random values in all valid implementations of Java. You can make sure that your Java is giving the same sequence of random numbers as my Java by compiling and running the code in RandomTest.java and comparing it to my output in randomnums.txt . If these are not the same, let me know.

There are three public methods in Disk.java:

The command line

The command line accepts two additional flags.

The Operating System

The "operating system" is found in file Project3.java. It is basically the same as the operating system in the first project. (It does not include the semaphores that you implemented for the second project.) You can make any changes you want to this part of the code. However, it is not _necessary_ to make any changes beyond writing the bodies of "execPageFault" and "HandleDiskReport".

The one major change is that, since processes can block waiting for a disk event, the CPU can become idle. The methods "contextSwitch" and "run" have been rewritten to accommodate this possibility. Additional minor changes include the following:

The file "Project3.java" also contains a number of data structures and utility methods that you may find useful in doing the assignment.

What you have to do

What you have to do is to implement demand paging in this simulated system. You are _allowed_ to make any changes you want to the code in Project3.java. However, it is _possible_ to do the assignment without doing anything more than writing the bodies of the methods "execPageFault" and "HandleDiskReport", plus, if you want, writing subroutines specific to those methods.

This should require about one or two hundred lines of code. What is critical in this assignment, and a little tricky, is making sure that you've taken care of all the cases, and that you've made all the updates to the data structures that you need to in each case.

Page Faults

In deciding what to do in execPageFault, there are two main issues:

Any of the 6 combinations of A,B with X,Y,Z may occur.

Let PR be the current process; PG be the page that is faulting; F be the frame to be used; OPG be the old page in F; and OPR be the old process holding F. In all cases, the relevant page tables and the inverted page table have to be updated.

In all these cases, execPageFault deals with reading or writing from disk by calling myDisk.PostRequest. execPageFault deals with blocking process PR by calling "contextSwitch(true)".

In case Z, OPR does not have to block. However, OPG's page table must record that OPG is no longer in memory, so that if OPR will page fault if it tries to access OPG.

Page Replacement algorithm

You need to implement two variants on the "least recently used" page replacement algorithm: global LRU and local LRU. In either case, you go through the candidate frames and choose the one with the earliest time stamp. It's unlikely that you will run into a tie, but not impossible; if it happens, you can resolve it any way you want.

A frame is a candidate for replacement if

Note that, in the global algorithm, the timestamp for pages for the current process are found in the global "stm.pageTable", where as pages for a non-running process PR are found in "procTable[PR].pageTable".

HandleDiskReport

HandleDiskReport(Task) implements the OS's reaction to receiving a report from the disk that some task has been completed. This task report contains the disk address, the physical address, and whether the operation was read or write, so it takes a little work for the OS to determine what has happened. First, the frame involved is calculated using the formula
  int frame = Task.memAddress / stm.PAGESIZE;
Second the process PR and page PG waiting for this frame are retrieved from InvTable[frame].holdingProc and InvTable[frame].holdingPage.

Now there are three cases:

Comments on Implementation

I hope to have a C version of this available soon.

You need not reproduce the debugging output exactly, though of course this will make it easier for you to check that you have done the assignment correctly. You do have to generate enough debugging output with -d 2 to establish that the code is actually using demand paging in a reasonable way. Since the behavior of this kind of system can be quite sensitive to small changes in sequence, it is possible that there could be correct code that gives substantively different behavior in terms of what happens to which pages when. If you think your code is behaving correctly but it is doing something different from the sample outputs, consult with me.

Error checking

You can assume that the STML code is correct, that the command line is correctly formatted, and that the input format is correct. That is, you don't have to do any error checking.

Partial credit and extra credit

I will give 85% credit if you get this to work for a single process which uses more pages than the frames in RAM. The code is not that much shorter, but I think that it is noticeably less confusing. Note that, if there is only one process P, then at any given time either the CPU is running P or P is blocked. Also, of course, there is no difference between the local and the global replacement algorithms.

I will give 10% extra credit if you integrate the semaphores from project 2 with this. A test STML file for this may be found in primessem.stm . This file modifies primesx.stm by protecting the reading and writing by semaphores, so that, if several instances of primessem.stm are run together, each instance reads its inputs consecutively and produces its outputs consecutively.

Be sure to alert the grader if you are doing either the partial credit or the extra credit version of the assignment.

Late Submissions

Because the due date is so close to the end of the semester, I have to be stricter about it.

Test STML files

There are currently two test STML files. Both of these are variants of the "primes.stm" file used in the first project, modified to create frequent page faults. If I have time, I'll create some more test files. It is unlikely that I will have time.

The file primesx.stm modifies the original code in primes.stm by scattering the sieve of Eratosthenes around memory. The program reads two values from input, N and D. It outputs the primes up to N. D governs the scattering of the sieve in memory; specifically, Specifically the Ith entry in the sieve is located at virtual address 100 + (D*I) mod 131072. D should be chosen to be an odd number. The larger D is relative to the page size S, the more frequent the page faults. If D is between S and 2S then each of the first (131072/S) entries in the sieve is on a different page.

The file primesy.stm is the same as primesx.stm except that the code is scattered over two pages (assuming a page size of 8192) by placing 8192 0's in the input file. This generates an example where one of the pages of code ends up being paged out.

Code

Here are links to the code files: The code needs more comments, in places. I'll try to get that done soon.

Submitting the assignment

When you submit the assignment, you should send to the grader _only_ the source code files that you have modified or created. As always, be sure to include your name as a comment at the start of the file.

C version

C code
Examples of I/O from C code.

Examples in Java

Example 1

Input 1
Command line Output
1A: java Project3 primesx.stm out1-d0
1B: java Project3 -d 1 primesx.stm out1-d1
1C: java Project3 -d 2 primesx.stm out1-d2.

Example 2

Input 2
Command line Output
2A: java Project3 primesx.stm primesx.stm out1-d0
2B: java Project3 -d 1 primesx.stm primesx.stm out2-d1
2C: java Project3 -d 2 primesx.stm primesx.stm out2-d2

Example 3

Input 3
Command line Output
3A: java Project3 primesy.stm out3-d0
3B: java Project3 -d 1 primesy.stm out3-d1
3B: java Project3 -d 2 primesy.stm out3-d2

Example 4

Input 2
Command line Output
4A: java Project3 -a LN primesx.stm primesx.stm out4-d0
4B: java Project3 -d 1 -a LN primesx.stm primesx.stm out4-d1
4B: java Project3 -d 2 -a LN primesx.stm primesx.stm out4-d2