#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    2
    Rep Power
    0

    Demand Paging Simulator using OPT Algorithm


    First, thank you in advance for any help or advice provided.

    I have a project to develop a Demand Paging Simulator for FIFO, OPT and LRU. I wrote three Java classes and on the surface they work in NetBeans 7.2.1 BUT...

    The OPT Algorithm is not quite correct and I cam not sure why. OPT is the abbreviation for Optimal and in theory it reads Virtual Frames into the given physical frames and when it runs into a Page Fault it needs to replace a Frame (Victim Frame). It is supposed to remove the Frame that will not be used the longest. Mine is not doing that portion 100% of the time.

    The Reference String we are provided is 01234567890918273645
    The number of Phys Frames is 5 (0-4)
    The number of Virtual Frames is 10 (0-9)

    Here is the code for just the OPT Algorithm:

    Code:
    // OPT algorithm using the stored reference string
        @SuppressWarnings("empty-statement")
        void opt(String rs) {
            // Set up array for physical frames
            ArrayList physicalFrames = new ArrayList();
    
            int[] futureUseBit = new int[5];
            futureUseBit[0] = 0;
            futureUseBit[1] = 0;
            futureUseBit[2] = 0;
            futureUseBit[3] = 0;
            futureUseBit[4] = 0;
            
            int loopFault;
            int victimFrame;
            //for each vframe (character in string) referenced to process 
            for (int i = 0; i < this.referenceString.length(); i++) {
    
                loopFault = 0;
                victimFrame = -1;
    
                //covnvert current ref to int 
                int currentPage = Integer.parseInt(Character.toString
                        (this.referenceString.charAt(i)));
                Integer integerCurrentPage = new Integer(currentPage);
    
                System.out.println("Processing frame " + currentPage + " (frame " 
                        + i + " of " + this.referenceString.length() + ")"); //info
    
                //If there are null pframes add to that 
                //(also make sure it isn't already in there)
                if (this.numOfAvaiableFrames > 0 && 
                        (!physicalFrames.contains(integerCurrentPage))) {
    
                    for (int c = 0; c < physicalFrames.size(); c++) {
                        if (Integer.parseInt(physicalFrames.get(c).toString())
                                >= 0) {
                            //sinceUseBit[c]+=1;
                        }
                    }
    
                    physicalFrames.add(currentPage);
                    int addedat = physicalFrames.indexOf(currentPage);
    
                    loopFault = 1; //for display processing
                    this.numberOfPageFaults++; //track these
                    this.numOfAvaiableFrames--;
    
    
                } else {
                    // either do nothing if there is a match
                    // determine number of future uses for each item in 
                    //"physical frame" - pf   
                    for (int pf = 0; pf < physicalFrames.size(); pf++) {
    
                        int numOfFutureUses = 0;
    
                        for (int rin = i; rin < this.referenceString.length(); 
                                rin++) {
    
                            if (Integer.parseInt(physicalFrames.get(pf).toString())
                                    == Integer.parseInt(Character.toString
                                    (this.referenceString.charAt(rin)))) {
                                numOfFutureUses += 1;
                            }
                        }
                        futureUseBit[pf] = numOfFutureUses;
                    }
    
    
                    if (physicalFrames.indexOf(currentPage) < 0) {
                        // or No Match, time to make a victim and pagefault
    
                        int leastUsefulElement = 0;
                        int smallest = 10;
                        for (int c = 0; c < physicalFrames.size(); c++) {
    
                            if (futureUseBit[c] < smallest) {
                                leastUsefulElement = c;
                                smallest = futureUseBit[c];
    
                            }
                        }
                        victimFrame = Integer.parseInt(physicalFrames.get
                                (leastUsefulElement).toString());
                        physicalFrames.set(leastUsefulElement, currentPage);
    
                        loopFault = 1; //for display processing
                        this.numberOfPageFaults++;
                    }
                }
    
                //System.out.println("futureUseBit " + futureUseBit[0] 
                //+ futureUseBit[1] + futureUseBit[2] + futureUseBit[3]);
                //do a printout    
                System.out.print("Ref String pg: " + currentPage + " |" 
                        + physicalFrames.toString().replaceAll("-1", "-"));
                if (loopFault == 1) {
                    System.out.print(" PAGE FAULT ");
                }
                if (victimFrame != -1) {
                    System.out.print(" VICTIM " + victimFrame);
                }
                System.out.print("\n---------------------------------- "
                        + "(press ENTER to continue)\n");
                //System.out.print("PHYSICAL FRAMES:"+ physicalFrames.get(0)
                //.toString()+physicalFrames.get(1).toString());
                try {
                    System.in.read();
                } catch (Exception e) {
                };
    
    
            } //end for each ref
    Thank you,
    LL
  2. #2
  3. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,711
    Rep Power
    347
    Please edit your post and wrap the code in code tags:
    [code]
    ... the code here
    [/code]
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2012
    Posts
    103
    Rep Power
    3
    That's really neat that you are implementing all these different replacement policies for memory management.

    There is a glaring issue with the code you have shown above. That being that your single method is responsible for doing many different things. That is never a good thing to do when programming. The two reasons are the code will be hard to read and if you have any problems you will have a difficult time finding the problem.

    So, my recommendation to you before we dig into this code would be to separate it into several different methods and make sure they work by testing them. For example, you can write a method that returns the number of times a frame appears in the future.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    2
    Rep Power
    0
    Thank you for that advice. I am really a novice at this, and have not heard that advice before but can see where it can make a huge difference. I am working to break it up now.
  8. #5
  9. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,711
    Rep Power
    347
    It would help if you posted code that can be compiled and executed for testing.
    Also post the program's current output and add some comments explaining what is wrong with it and show what you want it to be.
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2012
    Posts
    103
    Rep Power
    3
    Originally Posted by darkewulfe13
    Thank you for that advice. I am really a novice at this, and have not heard that advice before but can see where it can make a huge difference. I am working to break it up now.
    Fantastic! Be sure to test each method on its own to make sure it is returning the correct results.

IMN logo majestic logo threadwatch logo seochat tools logo