Another Simple Policy: Random

This lesson describes how the Random policy works as a replacement policy for ​evicting pages in the operating system.

We'll cover the following

Another similar replacement policy is Random, which simply picks a random page to replace under memory pressure. Random has properties similar to FIFO. It is simple to implement, but it doesn’t really try to be too intelligent in picking which blocks to evict.

Example

Let’s look at how Random does on our famous example reference stream (see figure below).

Of course, how Random does depends entirely upon how lucky (or unlucky) Random gets in its choices. In the example above, Random does a little better than FIFO, and a little worse than optimal. In fact, we can run the Random experiment thousands of times and determine how it does in general. The figure below shows how many hits Random achieves over 10,000 trials, each with a different random seed. As you can see, sometimes (just over 40% of the time), Random is as good as optimal, achieving 6 hits on the example trace; sometimes it does much worse, achieving 2 hits or fewer. How Random does depends on the luck of the draw.

Get hands-on with 1400+ tech skills courses.