A multithreaded “optimal” page replacement algorithm

Werbung mit Jumbo
Werbung mit Jumbo (Photo credit: Wikipedia)

Any textbook discussion of page replacement algorithms will quickly turn to Belady’s “optimal” (OPT) algorithm. This selects for replacement the page with the longest reuse distance – in other words the memory page currently in the main store that we will not need again for the longest time (possibly never).

As this OPT proposal requires foreknowledge of what a program is going to do it is sometimes described as the “clairvoyant” page replacement algorithm and it is certainly not one you see in a general use operating system.

It can be used in embedded computing environments though – after all if your software does one thing over and over again you can profile it and know the reuse distances of pages at a given moment.

But that really only applies to a single threaded environment. When there are a multitude of threads running I do not really think it is possible to have an OPT algorithm at all – as the system displays some of the characteristics of a “chaotic system” – namely small inaccuracies of measurement at the start become large anomalies over time – thread scheduling algorithms ensure that and I doubt that any two runs of a multithreaded system generate the same global memory reference strings.

So we are left with heuristics in how to approximate OPT.

And I am writing this because I think I picked the wrong one and now need to pick a better one.

My scheme was that each thread had its own record of pages it used and picked the page with the longest reuse distance from that.

But that’s simply not adequate as it favours the first thread to run – it can fill up the main store with its pages and then, when the next thread starts it could be left with only one page in memory at a time. It can force one of the first thread’s pages out at the start but then the page it brings in is more or less automatically the one it has to force out at its next different page reference.

In reality the second thread would likely very slowly grow its page set – as there would be some degree of page sharing with the other thread (through shared libraries and so on) but clearly the first thread would be privileged.

Instead, I think I am going to have to enforce a “global OPT” where each thread picks from the global pool. That arrangement is less than optimal too – because a page in heavy demand by one thread may have an infinite reuse distance for another – and so we would get a sort of “false selection” – where a page is repeatedly being brought in and out of memory.

A true OPT would, in multithreaded code, really have to be clairvoyant as it would have to know how the scheduler and I/O devices were going to work at any moment: unless, that is, we could build a fully deterministic system, which I doubt.

Enhanced by Zemanta

One response to “A multithreaded “optimal” page replacement algorithm”

  1. […] A multithreaded “optimal” page replacement algorithm […]

%d bloggers like this: