Operating Systems

Assignment 2 3/27/2000

Due 4/17/2000

The purpose of this assignment is to simulate a paging environment to see how page size, program size, page replacement algorithm (PRA), program behavior, and multi programming level control the number of page faults.

We will simulate different kinds of process behavior in order to understand how a well behaved process behaves as compared to a poorly behaved process.

We will assume that we have a machine with 16,384 bytes of memory. We will try page sizes of

64 bytes (256 page frames)

128 bytes (128 page frames)

256 bytes (64 page frames)

512 bytes (32 page frames)

Assume that we have a virtual memory size of 65,536 bytes, so we will have

1024 pages with 64 byte pages

512 pages with 128 byte pages

256 pages with 256 byte pages

128 pages with 512 byte pages

Processes will make instruction and data accesses, and all accesses will be on 4 byte (word) boundaries. We will assume that processes have a set of pages for instructions and a set of pages for data. We will assume that there are 4 sizes of processes;

[2048 bytes of instructions (512 instructions), 4096 bytes of data (1024 data words)] Size1

[2048 bytes of instructions (512 instructions), 8192 bytes of data (2048 data words)] Size 2

[4096 bytes of instructions (1024 instructions), 8192 bytes of data (2048 data words)] Size 3

[8192 bytes of instructions (2048 instructions), 16384 bytes of data (4096 data words)] Size 4

The way we will simulate these processes is to have the process generate an instruction memory access followed by zero or more data accesses. We will have 2 probabilities associated with each process:

A1 is the probability that the next instruction follows the current instruction by one word

1 - A1 is the probability that the instruction is randomly located

B1 is the probability that the next data access follows the current access by one word

1 - B1 is the probability that the next data access is randomly located

All memory accesses are mod N where N is the number of words either in the instruction space or the data space.

Assume that any instruction has a 10% chance of accessing 0 data locations, a 50% chance of accessing 1 data location, a 35% chance of accessing 2 data locations, and a 5% chance of accessing 3 data locations.

Example: If a process was accessing byte 2044 for an instruction, and the next instruction followed this one, it would be instruction 0 in byte 0 (if there are 2048 bytes of instructions).

Each process will be run for 5000 instructions before terminating.

We will simulate various job mixes:

Mix 1: 6 processes of Size 1 with A=B=0; this will be 6 processes that are accessing instructions and data in a completely random fashion

Mix 2: 6 processes of Size 1 with A=1 and B=0.9; this will be 6 processes that are accessing instructions in a sequential fashion and accessing data in a mostly sequential fashion

Mix 3: 2 processes of Size 4 with A=0.8 and B=0.9; this will be two processes that are accessing instructions and data in a mostly sequential fashion

Mix 4: 2 processes of Size 4 with A=0.8 and B=0.9. 1 process of Size 2 with A=0 and B= 0; this will be two processes that are accessing instructions and data in a mostly sequential fashion and one process accessing instructions and data in a random fashion

Mix 5: 2 processes of Size 2 with A=0.9 and B=0.5. 2 processes of Size 3 with A=1 and B=0; this will be two processes mostly accessing instructions sequentially and two processes accessing instructions sequentially and data randomly.

Mix 6: 3 processes of Size 1 with A=1 and B=0.9. 3 processes of Size 1 with A=B=0; this will be three processes as in Mix 2 and 3 processes as in Mix 1.

For each mix, assume that the first instruction to be executed is instruction 0, and assume that each process starts with page 0 in memory. Run each process in turn for 1 instruction (Round Robin).

The paging algorithms we will simulate are:

FIFO

LIFO

Clock

LRU

We have 4 paging algorithms, 4 page sizes, and 6 job mixes, so we have 96 combinations. Since we are running for a reasonable number of instructions, we can run each thing only once. I would expect that the output should look something like:

Mix 1:

64 byte page 128 byte page 256 byte page 512 byte page

FIFO xxxxx yyyyy zzzzz qqqqq

LIFO

Clock

LRU

Assume that we have global allocation for all of these PRAs.

For extra credit, implement the optimal PRA (hint: you will have to generate all accesses in advance), and run it for each of the job mixes and each of the page sizes.

Remember, we are interested in page faults, but we need to be careful because we have bytes, words (4 byte chunks), and pages as our units. For any instruction or data access, we need to decide which page it falls in, whether that page has a page frame, which page frame, etc. We are trying to count page faults.

---------

To determine a probability, we can simply use rand(). If rand() returns a number in the range 0..32767, then a function:

int prob(double d) {

int r;

int x;

r = rand() % 100;

x = d * 100;

if (r > x)

return 0;

return 1;

}

Then, to decide the next address we could have a function like:

/* p is either an A or a B, lastaddr is the last address, size is the size in words */

int res1;

int next;

res1 = prob(p);

if (res1) {

next = (lastaddr + 1) % size;

} else {

next = rand() % size;

}

return next;

}