Java代写 | CSI3131 – Lab5 Page Replacement Algorithms (Java)


CSI3131 – Lab5
Page Replacement Algorithms (Java)
To use a simulation for evaluating various page replacement algorithms studied in class. Please read the lab document before starting.
The Simulation Code
You are being provided with a simulation program of a memory management system that consists of the following files (available from the file).
This file contains a number of classes to simulate memory management.
MemManage Class
The simulation class that creates four process objects (see the Process class) and simulates the execution of the four processes using an arbitrary page replacement algorithm. The selected algorithm is provided as an argument to the class constructor. The possible algorithms are defined as enum PagingAlgorithm { FIFO, LRU, CLOCK, COUNT }.
Each process is executed for a random number of memory accesses (varies from process to process). The four processes have the following characteristics:
i. PID = 100, Number of virtual pages = 30 ii. PID = 101, Number of virtual pages = 24 iii. PID = 102, Number of virtual pages = 36 iv. PID = 103, Number of virtual pages = 32
The simulation class monitors the number of page faults and at the end outputs the number of page faults per 1000 memory references to allow you to compare the performance of each page replacement algorithm.
Process Class
This class is used to create process objects. This class is defined in more detail later since you shall be manipulating many of its data structures (for example its page table).
Kernel Class
One kernel object is instantiated when a MemManage object is instantiated. It provides the kernel specifications. For example an integer array defines the available physical frames. There are 32 physical frames available. You will NOT be manipulating the kernel object.

Seeds Class
This is used to create a number of seeds used to initialize the various random number generators used in the simulation program.
This Java program provides a main method to run a simulation for each of the three page replacement algorithms. The simulations are sufficiently long to produce results and can be used to compare the performance of the three page replacement algorithms.
Note that the resulting output should be on the order of 50 to 60 page faults per 1000 memory references.
Each of these Java programs contains a main method for executing a simulation object for each of the page replacement algorithms. They run the simulation for a very short period and do not produce valid results. They are provided for your convenience to allow you to debug your code (if you debug using logging, then the short runs produces manageable output) separately for each page replacement algorithm.
This Java program contains the class KernelFunctions which provides the necessary methods for page replacement. The MemManage class invokes two methods:
– doneMemAccess each time a memory access is completed and
– pageReplacement each time a page Fault occurs.
You will be completing the methods in this class.
Also found in this Java file is the class PgTblEntry specifying the format of the page table entries (and used to create the page table).
JAR Files
colt.jar – see
This file contains the various classes for creating various random number generators used in the simulation program. Be sure to include this file in “classpath”. Use the following command to browse the contents of the colt library: jar tf colt.jar
See for more details. Note, you don’t need to fully understand the library to finish your task.

This file contains the various classes that provide simulation functionality. For example, notice that MemManage extends the EvSched class, an event scheduling simulation class. Be sure to include this file in “classpath” (or imported into your favorite Java development tool). Use the following command to browse the contents of the abcmod library: jar tf abcmod.jar
Running Simulation
To compile the provided code, first create a bin directory to store all class files, then use the following command:
javac -cp “.;abcmod.jar;colt.jar” -d bin *.java
To run the simulation use the following command:
java -cp “bin;colt.jar;abcmod.jar” MemManageExp | tee sim.txt
The simulation runs four page replacement algorithms in sequence and displays the page-fault rate of each algorithm. Three of the four algorithms have been stubbed. Your task is to fill the functionality to compare the 4 algorithms.
Your Tasks
1. Take the time to study the code provided and to understand how the Process class is organized. Review the course notes and text book to understand terms such as working sets, page faults, page replacement algorithms, etc. Compile and run the code to test out the FIFO page replacement algorithm.
2. Complete the KernelFunctions class to implement and compare the three page replacement algorithms.
o FIFO algorithm is provided for you as an example
o CLOCK algorithm is very similar to FIFO, but use a flag (used) to give a second chance to
recently used pages
o Least Recently Used (LRU) algorithm requires a time stamp of pages used and picks the
least recently used page to replace
o COUNT based algorithms uses requires a count of page access, least frequently used
algorithm replace the page with the least count
Your results should show that LRU has the best performance (least number of page faults per 1000) followed by CLOCK, and finally that FIFO has the poorest performance (most page faults per 1000). My simulation shows that the count-based algorithm is even worse than FIFO. Here is a typical result:
Running simulation using FIFO
Number of faults: 158107
Number memory accesses (no faults): 2663272
Number of faults per 1000 references: 56
Running simulation using CLOCK
Number of faults: 155756

Number memory accesses (no faults): 2781233
Number of faults per 1000 references: 53
Running simulation using LRU
Number of faults: 151391
Number memory accesses (no faults): 2958343
Number of faults per 1000 references: 48
Running simulation using COUNT
Number of faults: 193146
Number memory accesses (no faults): 558934
Number of faults per 1000 references: 256
– Use the doneMemAccess function to update page table entry aspects you need to
maintain, e.g. timestamp & used flag.
– Add a count field to the table-entry class to use in count-based algorithm. Also use
doneMemAccess to maintain the count.


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: [email protected]  微信:itcsdx