代写Algorithms程序、代做program编程、c/c++程序语言调试

日期：2020-12-04 09:21

Simulating Page Replacement Algorithms

The goal of this assignment is to evaluate several page replacement algorithms. You will use

real memory trace data from UNIX systems to test these algorithms.

Your assignment is to write a program that reads in the trace data and simulates the page

replacement scheduling. You will keep track of various performance statistics and print these

out at the completion of the trace file.

A. Running your Program

You will build three executables called "537pfsim-fifo", "537pfsim-lru", and "537pfsim-clock".

The trace file will be named as the a value on the command line. For example:

pfsim-lru -p 8192 -m 2 tracefile1

The parameters are described below in the Simulator Parameters section.

B. The Trace Files

The trace files contain a sequence of records that report on memory references made by the

running process (and not the operating system) Each record is a line in the file that describes

one memory reference. The record has two decimal numbers, the process ID (PID) and virtual

page number (not the full address, but just the VPN). Each number in the trace file is a long

integer ("unsigned long"). For example, a line in the trace file might be:

1234 10000

which indicates that process 1234 referenced page 10000.

The trace files can be found on AFS at ~cs537-1/public/proj4.

Some of the trace files are large, in the millions of lines, so you will have to be conscious of

efficiency issues in your program design. This means that any linear time algorithm will cause

your program to run unacceptably slow.

C. Program Information

CS 537 - Programming Assignment #3

file:///C/Users/12542/OneDrive/桌面/Programming Assignment #3.html[11/29/2020 10:55:24 PM]

Your program will be structured as a continuous loop that reads trace records and advances

the simulated time.

C.1. Important Events

Your program will maintain a notion of current time. The "clock" in your simulator will be a

variable that holds the value of the current time. the clock tick will be 1 ns. The clock will start

at time zero (0) and advances each time a process makes a memory reference and also while

waiting for a disk I/O to complete.

Several things can happen while a simulator is running:

1. A successful (mapped) memory reference will be made. In this case, you simply advance

the simulated time by 1 ns.

2. The process will have a page fault, so the process will block until I/O is completed.

3. The process that is currently running completes. This happens after you execute the last

memory reference in the trace file for that process. In this case, you need to update the

various performance statistics (see below) and remove the process from any run/ready

queues.

4. A disk I/O will complete: The process that completed its I/O will be considered to be

runable again.

C.2. Simulator Details

Here are some important details:

1. The traces in the files don't include information about whether the references are reads or

writes. For simplicity, assume that all references are reads (you don't have to handle dirty

pages).

2. Memory references take 1 ns. Transferring a page from disk to memory takes 2 ms.

3. Memory starts out empty; all page frames are free. You are tracking only the memory

used by processes and not considering any memory used by the operating system kernel.

4. There is only one disk, so requests for pages must be queued. The disk can do only one

read at a time.

5. Some simplifying assumptions:

Not that you should not account for time to handle a disk I/O. Assume that it takes

zero time to start a disk I/O or handle its completion.

Do not try to account for process context switch time.

6. You will need to make two passes over the trace file. The first pass will include finding all

the PID's, and marking the start and end of execution (first and last memory reference) of

each process. A process is considered to have terminated (freeing all of its memory) after

its last memory reference in the trace file.

7. Do not read all the traces into a data structure at one time; process the traces from the

file. Real trace files have billions of records and this does not work in the real world.

8. If a process has a page fault then it is blocked until the page is loaded into memory; do

not process any further memory references from that process until the page is loaded.

You should, however continue to process memory references from other unblocked

processes. This means that you will need to have one pointer into the trace file for each

active process.

To move around in the file, you can use the fseek() library call

CS 537 - Programming Assignment #3

file:///C/Users/12542/OneDrive/桌面/Programming Assignment #3.html[11/29/2020 10:55:24 PM]

To get the value of your current position in a file, you can use ftell().

9. When a process blocks for a page fault, you have to remember where you were in the

trace file for that process. You then start processing references from another process.

10. Important rule: In general, you are always processing the earliest unprocessed trace in

the file for a runable process.

C.3. Scheduling Algorithms

The details of the particular scheduling algorithm (you will implement three) should be isolated

in a single module. All your program, except for the scheduling algorithm, should be the same

for the different versions.

1. The first version of your program will implement global FIFO page scheduling. Pages are

first brought into memory will be discarded first.

2. The second version of your program will implement global LRU (least recently used)

scheduling. Pages are kept in memory according to their overall wall clock reference time.

When all the page frames are filled and a new page is references, the page that is

referenced the furthest in the page is removed.

3. The third version of your program will implement a global Clock algorithm.

C.4. Simulator Parameters

Your simulator can take the following values as command line parameters. These values are:

Page size (-p option):

This value is the number of bytes and must be a power of two. So a parameter of -p 512

means that the page size is 512 bytes. The default value if this option is not specified is

4096.

Real memory size (-m option):

This value is the number of MB. So a parameter of -m 4 means that the memory size is

4MB. The default value if this option is not specified is 1 (MB).

C.5. Performance Data

Your simulator will keep trace of several performance statistics and print out these results

when the simulator completes. These statistics are:

Average Memory Utilization (AMU):

For each clock tick, examine how many pages frames are occupied and average this over

each clock tick that the simulator runs.

Average Runable Processes (ARP):

This value is an average of the number of processes that are running (or runable). This

value is averaged over each clock tick for which the simulator runs.

Total Memory References (TMR):

This is simply a count of the total number of memory references in the trace file.

Total Page Ins (TPI):

This is the total number of page faults (resulting in disk transfers into memory).

CS 537 - Programming Assignment #3

file:///C/Users/12542/OneDrive/桌面/Programming Assignment #3.html[11/29/2020 10:55:24 PM]

Running Time:

This is the total number of clock ticks for the simulator run.

D. Software Design Issues

Good design on this assignment will save you, literally thousands of lines of code. The page

replacement algorithm should be encapsulated in a PageAlgorithm module. In one version of

the program, this module will do something simple, like a FIFO scan of pages. In another

version, it may need much more complicated bookkeeping information to track last reference

times for LRU.

All other parts of your program should be the same, so you can re-use them for the different

versions.

You have plenty of time for this assignment, but don't delay in getting started! Work on a

design and and initial structure for your module and then talk with your TA.

Some of the modules that you might want to build will be for input, processes, page tables,

page frame table, paging device (disk queue), and statistics.

Your makefile will have build rules for the three separate programs: 537pfsim-fifo, 537pfsim-lru,

and 537pfsim-clock.

E. Deliverables

You can work individually or in a group of two. In either case, you will turn in a single copy of

your program, clearly labeled with the name and logins of both authors.

You will turn in your programs, including all .c and .h files and your makefile. Also include a

README file which describes a little bit about what you did for this project.

Note that you must run your programs on the Linux systems provided by the CS

Department. You can access these machines from the labs on the first floor of the Computer

Sciences Building or from anywhere on the Internet using the ssh remote login facility. If you

do not have ssh on your Windows machine, you can download this client:

SSHSecureShellClient-3.2.9.exe

Your program should run on the test trace files we provide. These files can be found in ~cs537-

1/public/proj4

You should run your simulator with page sizes of 512 and 4096 bytes and with physical memory

sizes of 1 MB, 4MB, and 32 MB. That's a total of 6 runs per trace file per algorithm.

(Of course, you'll probably want to use a shell script to run all these different variations.)