The double paging anomaly

Belady's paging anomaly has illustrated that certain page replacement algorithms can cause more page faults as the size of memory increases. Mattson has shown that there exists a class of algorithms called stack algorithms (such as LRU least recently used) which cannot cause more page faults as memory size increases. In this paper, we investigate the dynamics of double-paging, i.e., running a paged operating system, e.g., IBM's OS/VS2, under a paged virtual machine monitor, e.g., VM/370. In particular, we show that an increase in the size of the memory of the virtual machine without a corresponding increase in its real memory size can lead to a significant increase in the amount of paging, even for the LRU algorithm.