Key concepts: CPU scheduling, virtual memory management, page replacement, round robin, simulation
memsim -Q=q -M=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].
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.
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.
You are also required to put a cover sheet on your documentation
which contains the following information: