CIS 657 - OPERATING SYSTEMS

		     SEMESTER PROGRAMMING PROJECT

Objective:
----------

To design and implement a paging system.

Description:
------------

You are to design and implement a paging system. You are expected to
select or design a paging algorithm, design and implement the necessary
data structures, and test your system. You will be graded on the
correctness and performance of your system, and on the quality of
your analysis of its strengths and weaknesses.

The C programming language is to be used.

You must maintain running, waiting (ready), and blocked queues for
the processes in the system, and page tables for the processes.
You must not only program the mechanism, but must measure its
performance in appropriate ways, and submit a report describing the
performance, strengths, and weaknesses of your system.

Assumptions:
------------

Your computer has 8 page frames, numbered from 0 to 7.

There are at most 16 processes in the system at any time. They
are numbered from 0 to 15.

Each process has a virtual address space of 16 pages, numbered from
0 to 15.

Program Specification:
----------------------

Your program must be interactive and accept the following commands:

	Wi means that process i has entered the waiting (ready) queue

	Ri means that process i is running (only one process runs at
		a time)

	Bi means that process i is blocked

	i (integers by themselves) are page references for the
		running process

	DM instructs the program to display memory. Your program should
		then print the current contents of the page frames as
		a list of pairs (process, page). For example, the
		first call to DM above should give the output:
		1,0  1,1  1,2  1,5  1,6  1,9,  1,10  X
		which states that page 0 of process 1 is in the first
		page frame, page 1 of process 1 in the second page
		frame, and so on until the last page frame, which is
		empty (signified by an X).

For example, the following sequence of commands:

W0 W1 W2 R1 0 1 2 1 2 5 6 5 1 2 9 10 DM B1 R2 0 1 0 1 7 4 2 9 DM ...

means that processes 0, 1, and 2 enter the wait queue, then process
1 begins running and requests pages 0, 1, 2, 1, 2, 5, 6, 5, 1, 2, 9,
and 10, then memory should be displayed, then process 1 blocks, etc.

Your program must also print a message every time a page fault occurs.
This message must be of the following form:
	Page Fault: (i,j) put in frame k replacing (m,n)
which means that page j of process i was not present in memory, so
it caused a page fault, was placed in frame k, replacing the page
that was in frame k, which was page n of process m.

Your program MUST read standard input. We will compile and run your
program on our input data, to grade it. We will name your compiled
file "pager", so your program will be able to be run by the command:

	pager < myinput > myoutput

You should follow the same procedure in debugging your system.

Your program MUST output the contents of the page frames whenever
instructed by a DM command.

What to Submit:
---------------

Submit the source code for your program along with a report
analyzing your program's strengths and weaknesses. The report
may be submitted either by email (ascii only) or hardcopy.
Everything is due by the beginning of the final exam. No
credit will be given for late projects.