Maybe it's 4am and I ought to sleep, but I'm having trouble understanding this article.
Is this phenomenon the same reason some PC game engines render objects in alternating reverse order each frame, rather than something theoretically more optimal like depth-sorted? I understand that in the case of 3D graphics if the textures don't fit in the GPUs memory, FIFO ordering will cause ALL textures to be ejected every frame as you cycle through the same objects in the same order, whereas reversing the order every frame means just the same batch of overflow textures "at the end" will get ejected every other frame.
As I understand it, it is not the same phenomena. Because in your case increasing the number of texture that the GPU can hold won't increase the number of page faults. The number of texture to re-fetch will stay the same (i.e. all of them), or best case scenario the entire texture set now fits in the GPU memory and there is no page faults at all.
The anomaly descibed here is that there exist some access patterns that will increase the number of page faults if you increase the number of page the memory can hold (using a FIFO page replacement strategy). Very counter-intuitive, hence the term 'anomaly'.
Edit: thinking about it, I think what you describe is a clever trick to simulate an effective MRU policy when the actual hardware uses LRU (see oso2k first link for the definition of those acronyms).
Is this phenomenon the same reason some PC game engines render objects in alternating reverse order each frame, rather than something theoretically more optimal like depth-sorted? I understand that in the case of 3D graphics if the textures don't fit in the GPUs memory, FIFO ordering will cause ALL textures to be ejected every frame as you cycle through the same objects in the same order, whereas reversing the order every frame means just the same batch of overflow textures "at the end" will get ejected every other frame.