Algorithms For Dummies

  Working with Greedy Algorithms 

     291

for how long. It isn’t possible to implement such forecasting in practice because 

computer usage can be unpredictable and not predetermined.

Yet, as a principle, the idea of anticipating the future can inspire an optimal replace-

ment strategy,  a  greedy  choice  based  on  the  idea  of  keeping  the  pages  that  you 

expect to use soon based on previous requests to the cache. Bélády’s optimal page 

replacement policy (also known as the clairvoyant replacement algorithm) works on 

a greedy principle: to discard data from the cache whose next use will likely occur 

farthest in the future in order to minimize the chance of discarding something you 

need soon. To implement this idea, the algorithm follows these steps:

1. 

Fill the computer cache by recording data from every request made. Only when 

the cache is full do you start discarding past stuff to make room for new data.

2. 

Define a method for determining recent usage. This algorithm can use file date 

stamps or a system of memory flags (which flags recently used pages and 

clears all the flags after a certain time) to make the determination.

3. 

When you have to fit new data, you discard data that hasn’t been used recently 

from the cache. The algorithm picks one piece of data randomly among the 

ones not used.

For  instance,  if  your  cache  has  only  four  memory  slots,  and  it  is  filled  by  four 

alphabet letters that arrive in the following order: 

A

B

C

D

when a new letter is processed, such as the letter E, the computer makes space for 

it by removing one of the letters that are less likely to be requested at this point. 

In this example, good candidates are A, B, or C (D is the most recent addition). The 

algorithm will pick one slot randomly and evict its data from the cache in order to 

let E in.