Demand paging is a classical assumption used to study and design cache algorithms [2] wherein a page is brought in from the slower memory to the cache only on a miss. Demand paging precludes speculatively pre-fetching pages. Under demand paging, the only question of interest is: When the cache is full, and a new page must be inserted in the cache, which page should be replaced? The best, offline cache replacement policy is Belady's MIN that replaces the page whose next access is farthest in the future [3]. In practice, variants of LRU that replaces the least recently used page [4,5,6] are often used. For a recent detailed survey of cache replacement policies, see [7,8].