# Thread: Optimal Page Replacement Algorithm!

1. Member
Join Date
Nov 2010
Posts
66
Rep Power
0

## 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);
}
}
}```

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

3. Member
Join Date
Nov 2010
Posts
66
Rep Power
0

## 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!

4. ## Re: Optimal Page Replacement Algorithm!

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!

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

5. Member
Join Date
Nov 2010
Posts
66
Rep Power
0

## 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. Member
Join Date
Nov 2010
Posts
66
Rep Power
0

Bump!

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

8. Member
Join Date
Nov 2010
Posts
66
Rep Power
0

## Re: Optimal Page Replacement Algorithm!

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

9. ## Re: Optimal Page Replacement Algorithm!

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

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

## 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. ## Re: Optimal Page Replacement Algorithm!

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

12. Member
Join Date
Nov 2010
Posts
66
Rep Power
0

## Re: Optimal Page Replacement Algorithm!

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!

13. Member
Join Date
Nov 2010
Posts
66
Rep Power
0

Bump!

14. ## Re: Optimal Page Replacement Algorithm!

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

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

## 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. Senior Member
Join Date
Apr 2012
Location
New York State of Confusion, USA
Posts
137
Blog Entries
1
Rep Power
0

## Re: Optimal Page Replacement Algorithm!

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.

17. Member
Join Date
Nov 2010
Posts
66
Rep Power
0

## Re: Optimal Page Replacement Algorithm!

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!

#### Posting Permissions

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