CMPUT379, Assignment 3, WINTER 2001

Due Monday, April 9, 2001
 

Key concepts: CPU scheduling, virtual memory management,  page replacement, round robin, simulation



The problem

Implement a trace-driven simulation to explore the interaction between processor scheduling and virtual memory management.  In particular, your system must use round robin CPU scheduling and a demand paging virtual memory management scheme.  Explore the effect of quantum size and memory size on the page fault behaviour for 3 different page replacement strategies.

Input

The command line for executing  one run of the simulator is:

memsim  -Q=-M=-A=a -T=t -P=p -D=d

where
q is the scheduling quantum (in units of memory references). Set default to 100.
m is the size of main memory (that is, number of frames). Set default to 32.
a is the page replacement policy ("R", "F", or "S"). Set default to R.
t is the time to retrieve a page from backing store (in units of memory references). Default is 1000.
p is the degree of multiprogramming. Default is 3.
d is the directory holding process reference strings. Current directory is the default.

For the experiments with this simulator you will only vary q, m and a.  However, having the other parameters on the command line will make it easier for you to test your program, especially if you are using a shell script to drive your experiments. Note the use of "position independent" or "named" parameters here. If programmed properly they should simplify matters.

The other input to this problem is the reference string for each process.  A reference string consists of the page references for the process.  The reference string for each process will be stored in a file.  The first number in each file is the virtual process size (that is, the maximum logical page number).  The remaining numbers are the pages of the reference string.   A set of process files for the experiments may be found in http://ugweb.cs.ualberta.ca/~c379/W01/Assig3.

Note the reference string naming convention is: Pk.string where "k" is the process number. Assume k is in the closed interval [1,N]. That is, N can be determined by the non-existence of a file. Assume that logical page numbers are in the range [0,63].

Operation

This simulation is driven by memory references.  That is, the time unit in the simulation is a memory reference.  The memory references are given by the process reference strings.  The scheduling mechanism specifies the order of processing of the reference strings.    A page fault results in a blocked process.  At any point in time, at most P = 3 processes are allowed to be in the system (includes blocked, running and ready processes).  This is the multiprogramming level.

The CPU scheduling is round robin with a quantum of Q. Note that Q is the same for each process.  Once the CPU is given to a process it will run for Q memory references unless its reference string is finished or it page faults.  If a page fault occurs,  it takes T=1000 memory references until the page arrives back (that is, the missing page is retrieved from disk).   The process is blocked during this time.  Note that a page fault will occur during some process' time quantum. The remaining fraction of the quantum is NOT remembered.  That is, when the faulting process becomes ready again it is put at the end of the ready queue and the next time it comes to the head of the ready queue it is again given a full quantum. Note too that you are doing an "event driven" simulation. In this case an event is a memory reference, and this takes no time. Thus although the transfer of a page takes T memory references or events, this is only a counting operation, not a passage of time.

A page arrival that occurs during a process' quantum, should be handled right away.  However, the CPU will be given right back to the previously running process as if no time had passed.  Context switch times, interrupt handling times and page replacement processing delays are not modelled in this simulation.

The memory management mechanism uses a demand paging scheme with global page replacement.  You are to compare 3 different page replacement policies: Random(R), FIFO(F), and Second Chance(S).  When a page fault occurs, the faulting process becomes blocked and a frame must be found for the missing page.  If there is a free frame, it will be given to the process  (once the page arrives) otherwise, a victim frame must be found based on the replacement policy under consideration.  Note that the state of the process owning the victimized page remains the same (running, ready or blocked).  Once the page arrives for a process, the process becomes ready and is placed at the end of the ready queue.

Initially, there are m free frames in memory and the first p processes are in the ready queue [it is up to you to decide how to achieve this].  A process that finishes its reference string, frees up its memory and leaves the system.  At this point, another process can be started (if one exists).  The simulation ends once all reference strings of all processes have been traversed.
 

Output

The output of this simulation is a count of the number of page faults that arose during the "execution" of the processes.
 

Experiments

Three experiments are to be carried out on the processes in http://ugweb.cs.ualberta.ca/~c379/W01/Assig3

1) Explore the paging behaviour of these processes during the "execution" of the processes.  Consider the case of Q=100 memory references and M=32 frames.  Sample the number of page faults at appropriate points during your simulation and plot your results.  Do this for each of the three page replacement algorithms.  Analyse the results.

2) Explore the effect of quantum size.  Plot the final number of page faults versus Q for quanta of sizes 50, 100, 150, 200, and 250.  Assume memory size is 32 frames.  There should be 1 graph with 3 curves (corresponding to each page replacement strategy).  Analyse the results.

3) Explore the effect of memory size.  Plot the  final number of page faults versus # of frames for  M= 10, 20, 30, 40, 50, 60, 70, 80, 90 and 100.  Assume Q=100.  There should be 1 graph with 3 curves (corresponding to each page replacement strategy).  Analyse the results.

A few words about analysis of results:  Consider both the trend of the curves on your graphs and the comparison of the different algorithms.  It is not enough to just observe the trends or differences between the algorithms.  You must also explain why the algorithms have the performance you have found.

Deliverables

  1. Before the due date (April 9, 2001) you should create a directory called assig3 in your cvs directory. Add to this directory the following files:
  2. Documentation

  3. A hardcopy report must be handed in on Monday, April 9 (in class). The report should be spell-checked.  It should also contain the following information:


    You are also required to put a cover sheet on your documentation which contains the following information:


Copyright © Department of Computing Science.
All rights reserved.
Last update: