Optimal Page Replacement Algorithm

I was reviewing memory management basics this weekend (don’t ask), and I ran into this “algorithm” that totally cracked me up.

The idea behind all page replacement algorithms is that when the physical memory on a machine is completely full, but a process tries to load something into the memory, something else that is currently in the memory has to be written to disk and removed from memory to make space for the new data. The problem is – which page should be taken out of memory and written to disk?

This should sound quite familiar. Oracle’s buffer cache faces the same problem when you read a block but the cache is full. Oracle solves this problem by maintaining a list of all the blocks in the cache, ordered (roughly) from the most recently used (MRU) to the least recently used (LRU). When it needs to throw out a block, it will pick one of the least recently used blocks. Makes sense, if a block was used recently, there may be someone who still needs it, so throwing it out can be wasteful because we may need to read it back in again soon. On the other hand, if the block wasn’t used recently, perhaps we no longer need it at all, so why waste space?

So this particular method is pretty good, but is it optimal?

A smart scientist called Laszlo Belady came up with the optimal page replacement algorithm – when a page has to be swapped out, we should swap out the page whose next use will occur farthest in the future. So we prefer to swap out a page that will be used in 600 seconds and not in 3 seconds. Optimal indeed.
I’m sure that later on Belady came up with the optimal stock trading algorithm – buy stocks whose value will increase most in the future, and sell those whose value will decrease. The guy is a genius.

Thankfully, the optimal algorithm is useful even for operating system designers who lack regular access to a crystal ball. The idea is that for a given set of processes and actions, you know what the optimal algorithm will do. Then you can compare several practical algorithms (Say Oracle’s vs. MySQL’s) and see which one is closer to doing the optimal thing in your case. Or if someone suggests a modification o Oracle’s algorithm, we can know if the modification makes the system closer to optimal. Its a benchmark of sorts.

BTW. If you enjoy memory management, you should probably read about the paging game.

****

The cool guys from HotSos put up  a video from their symposium on Youtube. I’m there right at the beginning and its my first youtube appearance. Maybe you want to take a look 🙂 While there, I noticed they put up a bunch of videos demonstrating the use of their products. Pretty neat – soon screenshots will be a thing of the past. Oh, and while looking around in their website, I noticed they already put up their 2010 call for papers. Which is funny because its way early and also no one mentioned it anywhere. Don’t panic – you have until September 30 to send your papers 🙂

Advertisements

2 Comments on “Optimal Page Replacement Algorithm”

  1. coskan says:

    Chen,

    There is a presentation from Julian Dyke which explains LRU and MRU in Oracle. I think this one is the best I have ever seen so far. His animations make this hard topic very easy to understand.

    http://www.juliandyke.com/Presentations/Presentations.html#LogicalIO

  2. Noons says:

    A local bookshop chain sells a diary-like book with the title:
    “Faint and Paged”.

    It always reminds me of virtual memory!
    😉


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s