Results 1 to 17 of 17
  1. #1
    Asvin is offline Member
    Join Date
    Nov 2010
    Posts
    66
    Rep Power
    0

    Default Optimal Page Replacement Algorithm!

    Hey guys,

    I have searched online for an "Optimal Page Replacement" algorithm for java, and have found none. Question is.. is there any? Also, once I store the reference string into an array, how will I then "look ahead" and see which of the numbers wouldn't be used for the longest? Here is my code so far:

    Java Code:
    package optimalpagereplacement;
    
    public class OptimalPageReplacement {
    
        public static void main(String[] args) {
           
            int[] referenceString = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
            
            int[] pageFrames = {-1, -1, -1};
            
            for(int a=0; a<pageFrames.length; a++) {
                
                if(pageFrames[a]==-1)
                    
                    pageFrames[a] = referenceString[0];
                    System.out.println(pageFrames);
            }
        }
    }
    Thanks in advance! :D

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,730
    Blog Entries
    7
    Rep Power
    21

    Default Re: Optimal Page Replacement Algorithm!

    You do have to describe your problem in more detail (or supply a link), because I don't understand what you're talking about now ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    Asvin is offline Member
    Join Date
    Nov 2010
    Posts
    66
    Rep Power
    0

    Default Re: Optimal Page Replacement Algorithm!

    Sorry for not being clear.. Here is a link to its description:

    Page replacement algorithm - Wikipedia, the free encyclopedia

    Basically, it's a page[memory] replacement algorithm!

    Thanks in advance!

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,730
    Blog Entries
    7
    Rep Power
    21

    Default Re: Optimal Page Replacement Algorithm!

    Quote Originally Posted by Asvin View Post
    Sorry for not being clear.. Here is a link to its description:

    Page replacement algorithm - Wikipedia, the free encyclopedia

    Basically, it's a page[memory] replacement algorithm!

    Thanks in advance!
    Ah, ok, I know what you're talking about now; nope, such an algorithm doesn't exist because it simply can't predict the future; only for very special cases where a process is known and completely analyzed, its memory consumption is known, otherwise we have to use one of the heuristics described in the link you supplied.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    Asvin is offline Member
    Join Date
    Nov 2010
    Posts
    66
    Rep Power
    0

    Default Re: Optimal Page Replacement Algorithm!

    I'm sorry, I don't understand what you mean by "heuristics." Is that a kind of algorithm or basic framework for implementing an optimal page replacement system?

  6. #6
    Asvin is offline Member
    Join Date
    Nov 2010
    Posts
    66
    Rep Power
    0

    Default Re: Optimal Page Replacement Algorithm!

    Bump!

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,730
    Blog Entries
    7
    Rep Power
    21

    Default Re: Optimal Page Replacement Algorithm!

    A heuristic is an algoritm/strategy that doesn't necessarily produces an optimal solution but it produces a good one most of the time; and it is generally faster than an algorithm that always produces an optimal solution.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    Asvin is offline Member
    Join Date
    Nov 2010
    Posts
    66
    Rep Power
    0

    Default Re: Optimal Page Replacement Algorithm!

    So, what would be the heuristic for optimal page replacement?

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,730
    Blog Entries
    7
    Rep Power
    21

    Default Re: Optimal Page Replacement Algorithm!

    Quote Originally Posted by Asvin View Post
    So, what would be the heuristic for optimal page replacement?
    It's not the heuristic, it's a heuristic and some of them are described in the link you supplied (see above).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  10. #10
    jlczuk is offline Senior Member
    Join Date
    Apr 2012
    Location
    New York State of Confusion, USA
    Posts
    137
    Blog Entries
    1
    Rep Power
    0

    Default Re: Optimal Page Replacement Algorithm!

    Jos, I've been following this thread, curious to see where it went.

    It seems Asvin isn't grasping, as you do, that there is no ONE SINGLE optimal solution for his page replacement quandary. He doesn't seem to grasp that the efficacy of algorithms and heuristics depends highly on the environment and constraints under which they are applied. An optimal algorithm for one set of constraints won't be optimal for another set of constraints.

    Optimal in what regard? Everything we do has tradeoffs, like memory vs. speed/processor consumption as applied to sorting or traversal problems. An optimal solution in a constrained memory environment will not be give optimal speed or minimal processor consumption.

    When I am asked to provide an optimal solution to a problem, I immediately start asking questions in order to bound what the person making the request means by "optimal".

    So, forgive my intrusion as I'm sure you are aware of these things. This was intended for Asvin's benefit. Asvin clearly needs to do a bit of researching rather than vainly hoping for a cookie cutter answer that does not exist.

    ...crawling back under my rock...

  11. #11
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,730
    Blog Entries
    7
    Rep Power
    21

    Default Re: Optimal Page Replacement Algorithm!

    Quote Originally Posted by jlczuk View Post
    ...crawling back under my rock...
    Nonono, there's no need to crawl anywhere unless it's too hot here in this vale of tears ;-) Your remark made sense (at least to me) and is much appreciated.

    kind regard,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  12. #12
    Asvin is offline Member
    Join Date
    Nov 2010
    Posts
    66
    Rep Power
    0

    Default Re: Optimal Page Replacement Algorithm!

    Quote Originally Posted by jlczuk View Post
    Jos, I've been following this thread, curious to see where it went.

    It seems Asvin isn't grasping, as you do, that there is no ONE SINGLE optimal solution for his page replacement quandary. He doesn't seem to grasp that the efficacy of algorithms and heuristics depends highly on the environment and constraints under which they are applied. An optimal algorithm for one set of constraints won't be optimal for another set of constraints.

    Optimal in what regard? Everything we do has tradeoffs, like memory vs. speed/processor consumption as applied to sorting or traversal problems. An optimal solution in a constrained memory environment will not be give optimal speed or minimal processor consumption.

    When I am asked to provide an optimal solution to a problem, I immediately start asking questions in order to bound what the person making the request means by "optimal".

    So, forgive my intrusion as I'm sure you are aware of these things. This was intended for Asvin's benefit. Asvin clearly needs to do a bit of researching rather than vainly hoping for a cookie cutter answer that does not exist.

    ...crawling back under my rock...
    I guess my question is malformed! The assignment has nothing to do with memory, processor speed, or processor consumption. I just wanted to know if there is an algorithm that looks at the first value of the reference string, adds it to the page table.. then looks at the second, adds it to the page table.. then looks at the third, adds it to the page table.. the page table is a three-element sized array! So, after the first three reference strings are added, the program needs to see which one will not be used for the longest time. Whichever one that is, the program should figure it out and replace it! Hope I am being clear!

  13. #13
    Asvin is offline Member
    Join Date
    Nov 2010
    Posts
    66
    Rep Power
    0

    Default Re: Optimal Page Replacement Algorithm!

    Bump!

  14. #14
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,730
    Blog Entries
    7
    Rep Power
    21

    Default Re: Optimal Page Replacement Algorithm!

    Quote Originally Posted by Asvin View Post
    Bump!
    Bump what? You now know (or should know) that an optimal algorithm doesn't exist and all you can do is rely on a (not 'the') heuristic method.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  15. #15
    jlczuk is offline Senior Member
    Join Date
    Apr 2012
    Location
    New York State of Confusion, USA
    Posts
    137
    Blog Entries
    1
    Rep Power
    0

    Default Re: Optimal Page Replacement Algorithm!

    A better bump would have been one where you demonstrated putting some effort into solving this rather than waiting for us to hand you a solution.

    So, after the first three reference strings are added, the program needs to see which one will not be used for the longest time. Whichever one that is, the program should figure it out and replace it!
    So you tell us, how do you determine the age of the 'pages' in order to know which one to replace in the list?

  16. #16
    jlczuk is offline Senior Member
    Join Date
    Apr 2012
    Location
    New York State of Confusion, USA
    Posts
    137
    Blog Entries
    1
    Rep Power
    0

    Default Re: Optimal Page Replacement Algorithm!

    Quote Originally Posted by JosAH View Post
    Bump what? You now know (or should know) that an optimal algorithm doesn't exist and all you can do is rely on a (not 'the') heuristic method.

    kind regards,

    Jos
    I think part of the problem here is that he is using the words page and optimal differently from we would. From what he wrote, I was thinking he was working on virtual memory simulation or caching types of problems. I don't think that's what he's doing.

  17. #17
    Asvin is offline Member
    Join Date
    Nov 2010
    Posts
    66
    Rep Power
    0

    Default Re: Optimal Page Replacement Algorithm!

    Quote Originally Posted by jlczuk View Post
    I think part of the problem here is that he is using the words page and optimal differently from we would. From what he wrote, I was thinking he was working on virtual memory simulation or caching types of problems. I don't think that's what he's doing.
    I don't know how else to explain this assignment. I guess I will just wait for my professor to reply via e-mail. Apologies for wasting your time!

Similar Threads

  1. $1500 for Optimal Job Scheduling Algorithm
    By bart_bl in forum Jobs Offered
    Replies: 0
    Last Post: 05-04-2011, 04:21 PM
  2. replacement for complicated if else?
    By TopNFalvors in forum New To Java
    Replies: 12
    Last Post: 04-09-2011, 08:05 PM
  3. String Replacement
    By pr3diker in forum Java Applets
    Replies: 7
    Last Post: 12-16-2010, 01:04 PM
  4. String replacement...
    By diskhub in forum New To Java
    Replies: 6
    Last Post: 05-19-2010, 05:20 AM
  5. Be Optimal! - DNA's Vehicle Routing Initiative 2008
    By dnaevolutions in forum Java Software
    Replies: 0
    Last Post: 10-05-2008, 02:19 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •