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:

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

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

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!

Quote:

---

Originally Posted by Asvin

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

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?

Bump!

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

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

Quote:

---

Originally Posted by Asvin

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

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...

Quote:

---

Originally Posted by jlczuk

...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

Quote:

---

Originally Posted by jlczuk

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!

Bump!

Quote:

---

Originally Posted by Asvin

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

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.

Quote:

---

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?

Quote:

---

Originally Posted by JosAH

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.

Quote:

---

Originally Posted by jlczuk

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!