1 The paging/caching problem
The paging/caching problem arises from memory management, between external storage and main memory and between main memory and the cache. We consider a two-level virtual memory system. Each level can store a number of fixed-size memory units called pages. The slow memory contains N pages. The fast memory has a fixed size k < N which can store a subset of the N pages. We call the fast memory the cache. Given a request for a page is issued. If the requested page is already in the cache, we call it a hit. If the requested page is not in the cache, we call it a miss and we have to evict (remove) a page from the cache to make room for the requested page. Pages that are not evicted must stay in the same location in the cache. Different eviction algorithms use different criteria to choose the page to be evicted. We consider the following eviction algorithms. To illustrate, we assume the cache contains 3 pages with initial ID content 20, 30, 10 and the sequence of requests is 20, 30, 5, 30, 5, 20.