Programming Assignment 2 (updated)

This programming assignment involves experiments with Page-Replacement Algorithms. A framework for creating, running, and evaluating these algorithms has been provided through the following files (see the guide to the framework for more information):

• MemoryInterface.java (updated)

• PageManager.java

• Simulator.java

• ReferenceGenerator.java

• RandomReferenceGenerator.java

• StaticReferenceGenerator.java

• LocalReferenceGenerator.java

• Example.java

• ExamplePageManger.java (updated)

• Info.java (new)

You are asked to implement the following page-replacement algorithms:

1. Random (i.e., always randomly pick a page as the victim)

2. FIFO (First-in-first-out)

3. LRU (Least recently used)

4. Clock (Second-Chance) 

5. ARB (Additional-Reference-Bits Algorithm (4 bits))

6. A page-replacement algorithm you design. It could be a variation of an algorithm discussed in the class or a totally new algorithm that you invent. (Do not use any algorithm that is in the book.)

A guide to the provided framework

How to use class MemoryInterface? (Updated)

The memory interface class defines an interface to a memory whose size is specified in number of memory frames in holds at the time of construction. The memory interface provides the following methods. 
map: maps the given page to the memory.
unmap: removes an already mapped pages from memory.
swap: removes the old page and maps the new page.
getMap: provides an enumeration of the pages in memory, in the order in which it was mapped.
getInfo: returns the info associated with a page in memory.

An object of type Info (see Info.java) is associated with each page. For associating more information with the page, create a subclass extending this Info class as done in ExamplePageManager.java. You may need to use this to maintain additional information such as number of accesses. For mapping a page, an appropriate Info object must be created and passed to the map method. The unmap and swap methods would return the info associated with the removed page. The getMap provides an enumeration strictly in the order in which the pages were mapped using the 'map' method. This should be useful to implement FIFO and second chance algorithms. Also see the definitions in MemoryInterface.java for more clear understanding.

How to use class ReferenceGenerator? 

A reference generator generates page references during the simulation. Three types of reference generators have been defined for your convenience. They are described below.

Static Reference Generator: This reference generator generates page references from a pre-specified array of page numbers called reference string. This is a static generator which can be used for debugging.

Random Reference Generator: This reference generator generates page numbers randomly with a uniform distribution between 0 and a pre-specified maximum.

Local Reference Generator: This reference generator simulates locality of references in a program. A working set of pages is maintained and references are drawn randomly from the working set. The size and contents of the working set may vary over time. It takes as input three user defined parameters. The probability of locality which specifies whether the next reference is drawn from the working set or from the full set of pages. This probability should be high (setting this to 0 makes it behave like random reference generator). The average working set size which specifies the average size of the working set during the simulation. The average number of references per working set which specifies the number of references generated with the current working set. This parameter specifies how frequently the working set varies over time.
The necessary parameters have to be passed at the time of construction. Please read the file Example.java to see how these three types of reference generator can be used. 

How to define a new page manager?

A new page manager is defined by extending from the abstract parent class called PageManager defined in the file PageManager.java. Two abstract methods handlePageReference and handlePageFault must be redefined as per the functions of the new page manager. An example is provided in the file ExamplePageManager.java for your understanding.
In order to process a page fault or a page reference, a handle to the memory interface is also passed along to the above functions. The memory interface may be used to access the information associated with the pages and modify them. The example clearly illustrates how a page manager can be defined.
Note that, immediately after a page fault, a page reference will be generated for the same page access.

How to use the Simulator?

The class simulator allows you to use any page manager and any reference generator. The memory interface may be created and passed on to the simulator during construction time. The parameter numReferences defines the number of references that the simulator calls the reference generator to generate. Then, the simulator either calls the page fault handler or the page reference handler of the page manager. The page reference handler will be called in addition to the page fault handler whenever there is page fault. The method simulate sets the simulator to run. A value for seed may be passed on to it to set the seed for random number generation. Using the same seed is guaranteed to generate the same reference string.
The simulator returns an object called history. This contains an array of page numbers in order of reference and another array indicating whether a page fault occurred for that reference. This information may be used to plot graph, for example. Additional statistics can also be read from the page manager implementation.

Notes:

• Try to experiment with different values for the parameters. For plotting graphs, the number of references should be made high. So avoid cluttering the output with too many print statements. Make sure you do not make any changes to the classes already defined. If you need to make modifications, please consult with the TA before doing so. These interfaces have been designed to be flexible as possible. However, you may not be able to implement certain things elegantly. Please consult the TA on such issues. 
• For clock and ARB algorithms, reset the reference bits for every N references, where N is a parameter to the algorithm. You can set the reference bits by going though every page table entry and setting the bit (which should part of info object associated with each page entry). Counting references can be done in the handlePageReference method in the PageManager class and certain actions can be triggered when the number of references reaches N. 

What to submit

1. For each page-replacement algorithm, create a file containing a class of the same name. These files should be called:

   • Random_PageManager.java

   • FIFO_PageManager.java

   • LRU_PageManager.java

   • Clock_PageManager.java

   • ARB_PageManager.java

   • My_PageManager.java

2. Answer the following questions based on your experience with your experiments. The answers should be included in answers.txt.

   • Compare the RandomPageGenerator and LocalPageGenerator. Explain which might be a better approximation of real system behavior. 

   • When RandomPageGenerator is used, how do the page-replacement algorithms differ from each other? Explain why.

   • Find parameters for the LocalPageGenerator, so that LRU is consistently better than FIFO and Random. How do the page-replacement algorithms perform in terms of page faults in this case? Provide the parameters you use in your experiments. 

   • How do your own page-replacement algorithm perform compared to others? Describe your algorithm and the rationale behind your design. 

3. Generate the following graphs of the page fault rate for each algorithm you implement. All graphs should be created for cases where LocalPageGenerator is used. Set the parameters as follows: the page generator generates 500 pages, there are in total 20 physical frames, and the reference bits are reset for every 50 references. Put all your graphs in a graph directory.

   1. In LocalPageGenerator, set probLocality to 0.9 and avgWorkingSetSize to 20. Create a graph presenting the number of page faults for each implemented algorithm versus avgRefsPerLocality, which ranges from 10 to 210 with interval 20.

   2. In LocalPageGenerator,  set avgRefsPerLocality to 200 and avgWorkingSetSize to 20. Create a graph presenting the number of page faults for each implemented algorithm versus probLocality, which ranges from 0 to 1 with interval 0.1.

4. (Optional Bonus Question) Present any other interesting experiment you have performed (in a file option.txt). Explain the motivation for the experiment (i.e., why is it interesting),  the observation obtained from the experiment, and what you have learned from the experiment.

When to submit (updated)

Final submission (one per team) of all files must be made electronically by 10:00pm on June 24 (Sunday). Instructions for electronic submission can be found here.