I. Paging
 
   In the paging problem we have a two-level memory system, in which the first level is small and has short access time, while the second level is very large but slow.  We will refer to the first memory level as the cache, and we denote its size by k.  A request to a page p can result either in a hit, when p is in the cache, or a fault, when it isn't.  In response to a fault we need to bring p into the cache.  If the cache does not have enough room for p then we have to evict a page q in order to make room.  The goal of a paging algorithm is to choose the evicted page so as to minimize the cost, defined as the number of faults.  Note:  All of the pages are of the same size in the paging problem.
 
Some common algorithms for paging are:

Least Recently Used (LRU).  When swapping is necessary, replace the page whose most recent access is earliest.

First-in, First-out (FIFO).  Replace the page that has been in fast memory longest.

Last-in, First-out (LIFO).  Replace the page most recently moved to fast memory.

Least Frequently Used (LFU).  Replace the page that has been accessed the least.

Longest Forward Distance (MIN).  Replace the page whose next access is latest.  Unfortunately this algorithm is an off-line algorithm.  Meaning, it knows the entire sequence of page requests from the start as opposed to all of the above algorithms which are on-line algorithms, which do not have the knowledge of future requests.   The MIN algorithm was given by Belady [1] and is the optimum algorithm for paging.
 

II. Caching

  Caching is the same as paging, but the pages are not all the same size.  A model for multi-size caching is given in the notes on the first page.

Here are some caching links:
  1. Raj's caching links: http://dimacs.rutgers.edu/~rraj/Caching/caching.html
  2. Caching papers ( with some notes about them ).
 

GoBack

[1]Belady, L.A. A study of replacement algorithms for virtual storage computers. IBM Syst. J. 5(1966), 78-101.