As soon as you have to move buffers around, it won’t be “high performance” in my opinion, however, how about this:
The pages you are going to evict are of a total size of k times page size 512 kB, that is, the size of the incoming page.
The worst-case layout is something like this (four characters (except bars |
) == 512 kB):
|X1 |1 |2 |X2 |3 |4 |
The two X
es are the pages to evict. The issue is now that to make the buffers consecutive, you need to move X2
next to X1
(or the other way round). My approach would be to move the pages after X1
towards the right (into X2
) in place. We are safe to override X2
, because we want to evict it anyways.
That way, we only have to update 3 pages sizes instead of copying the whole buffer.
A more complex problem would be:
|X1 |1 |2 |X2 |3 |X3 |4 |5 |
One can still use the naive algorithm from above, but there are possible optimizations. For example, one can safely move 1
into X2
without touching 2
, because it fits there. The same goes for 2
, which can be moved into X3
.
So in fact, you can always go for the simple moving technique known from dynamic array insertion and swapping, but it might be wise to check for possible optimizations, in this case, enumerate the pages which would have to be moved by the naive algorithm and first try to fit them directly into the to-be-evicted space. Only after that fails (like in the first example) moving should be used.
Copying the whole buffer should only be neccessary if you need atomicity. In that case, the optimized approach from above will also work, but you’ll get into trouble as soon as you cannot fit pages which are in your way into the to-be-evicted pages. You have to recurse in the eviction algorithm in that case to find suitable places, possibly evicting more pages.