Lab Assignment 3: Comp. Sys. Org. II
Paging Algorithms

Assigned: April 3
Due: April 24

In this assignment you will simulate several basic paging algorithms in a multiprogramming environment.

Machine Specs

The machine has a 10 bit virtual address space (size = 1024) and a physical memory of size 128. A request for I/O requires 3 machine cycles. Requests for I/O are handled sequentially, in first-come, first-served order. The process scheduler uses round robin. Assume that the processes are entirely CPU bound, so that the only time they block is when they page fault. Assume that the activities of the OS require no memory and no time. In particular, no time is required for a context switch.


The input to the program has the following format.


Initially all frames are empty. Process number 0 (as ordered in line 3) is running. The remaining processes are in the ready queue in the specified order.

At each time cycle,

Thus, the internal clock for A is incremented when A executes an instruction. The global clock (cycle number) is incremented under three circumstances.


Two levels of output are required ; a third is strongly recommended, but not required

Summary output: (Required) If there is no flag in the command line, then just output the summary data. This consists of:

Detailed output: (Required) If the flag "--verbose" is given in the command line, then output the summary data plus a sequential log of all the events that occur. There are five types of events:

Debugging output (strongly suggested) If the flag "-debug" is given in the command line, then output the state of all the major data structures at each cycle, in addition to the detailed output. If you follow the implementation suggestions below, then you would want to output the inverted page table, the process table, and the end time for the disk driver.

The e-tutors and I will find it much easier to help you if you provide debugging output.

Page replacement algorithms

Implement the following four algorithms: Local NRU, global NRU, local LRU, global LRU. These are actually all very similar. In particular, the local and global versions of each algorithm need differ in only about one line. Note that:

Implementation suggestions

You can implement this project in any way that gives the correct answer. You need not worry about efficiency. My suggestion would be as follows: The main data structures should be:

Process types

There are two functions associated with each process type. The first returns a virtual address; the second returns a boolean of 0 for reads and 1 for writes. Seven process types are defined below. The system can have more than one process of the same type at a given time.

In all the following, T is the internal clock for the process.

Type 0:
Address: ((7*T)%32 + T/4) % 1024
Op: 0.
Comment: 1 read-only segment moving slowly forward through memory.
First few values: R0, R7, R14, R21, R29, R4, R11, R18, R26, ...

Type 1:
Address: (((6*T+T/5)%32) + (123*(T/40)))%1024
Op: 1.
Comment: 1 write segment jumping every 40 cycles.
First few values: W0, W6, W12, W18, W24, W31, W5, W11, ...

Type 2:
Address: ((T%2)==0) ? ((3*T)+(T/5))%16 : 101+((5*T+T/5)%16)
(The notation Q ? A : B evaluates to A if Q !=0 and to B if Q =0.)
Op: T%2.
Comment: Alternates between a read segment from 0-15 and a write segment from 101-116.
First few values: R0, W106, R6, W116, R12, W111, R3, W105 ...

Type 3:

{ V = 1+T%62;
  U = V < 32 ? V : 64-V;
  (T%2==0) ? (23*T)%(1+T%U) : (1023 - (7*T)%(32-(T%U))); } 
Op: T%2
Comment: Two segments. The first is a read segment that starts at 0 with size 1, gradually grows to size 32, then shrinks, grows, shrinks, grows ... The second is a write segment that extends downward from 1023. It starts with size 32, gradually shrinks, then grows , shrinks, grows, shrinks, ... The total size of the working set is always 32.
First few values: R0, W1016, R1, W1002, R2, W1015, R5, ...

Type 4:
Address: ((T%19)!=0) ? (17*T)%24 : (633*(1+T/60) + (5*T)%8)%1024
Op: (T%19)==0 ? 1 : 0.
Comment: A static read segment from 0-23, plus occasional random writes to a segment of size 8 which jumps randomly around memory.
First few values: W633, R17, R10, R3, R20 ....

Type 5:
Address: (100*(T%5) + (T/9)*(T%5) + (2*T)%7) % 1024
Op: (T%5)%2
Comment: 5 segments, 3 read and 2 write, moving gradually through memory at different rates.
First few values: R0, W102, R204, W306, R401, R3, W105, ...

Type 6:
Address: ((T%2)==0) ? ((7*T)%17+T/4) : ((4*T+T/5)%15) + (123*(1+T/40))%1024
Op: T%2.
Comment: Alternate between a slowly moving read segment of size 17, and an occasionally jumping write segment of size 15.
First few values: R0, W127, R14, W135, R12, W129 ...


For K=1 to 7, run the following experiment in summary mode:
Quantum: 5 cycles.
Tick frequency: 20 cycles.
Number of cycles: 2000.
K processes of types 0 ... K-1.
Page size: 8
Algorithm: GLRU.
Report how the CPU efficiency and the average page fault rate vary as K increases. (You may write a driver to do this any part of this automatically, or you may do the experiment entirely by hand.)

To Hand In

Email your source code to the grader. The results of the experiment may be either emailed to the grader or handed in in hard-copy.