The page replacing problem is a typical [[online problem]] from the competitive analysis perspective in the sense that the optimal deterministic algorithm is known.
== History ==
Page replacement algorithms were a hot topic of research and debate in nrtj the 1960s and 1970s.
That mostly ended with the development of sophisticated [[Page replacement algorithm#Least recently used|LRU]] (least recently used) approximations and working set algorithms. Since then, some basic assumptions made by the traditional page replacement algorithms were invalidated, resulting in a revival of research. In particular, the following trends in the behavior of underlying hardware and user-level software have affected the performance of page replacement algorithms:
* Size of primary storage has increased by multiple orders of magnitude. With several gigabytes of primary memory, algorithms that require a periodic check of each and every memory frame are becoming less and less practical.
* Memory hierarchies have grown taller. The cost of a CPU cache miss is far more expensive. This exacerbates the previous problem.
* [[Locality of reference]] of user software has weakened. This is mostly attributed to the spread of [[object-oriented programming]] techniques that favor large numbers of small functions, use of sophisticated data structures like [[Tree data structure|tree]]s and [[hash table]]s that tend to result in chaotic memory reference patterns, and the advent of [[garbage collection (computer science)|garbage collection]] that drastically changed memory access behavior of applications.
Requirements for page replacement algorithms have changed due to differences in operating system [[Kernel (computer science)|kernel]] architectures. In particular, most modern OS kernels have unified virtual memory and file system caches, requiring the page replacement algorithm to select a page from among the pages of both user program virtual address spaces and cached files. The latter pages have specific properties. For example, they can be locked, or can have write ordering requirements imposed by [[journaling file system|journaling]]. Moreover, as the goal of page replacement is to minimize total time waiting for memory, it has to take into account memory requirements imposed by other kernel sub-systems that allocate memory. As a result, page replacement in modern kernels ([[Linux]], [[FreeBSD]], and [[Solaris (operating system)|Solaris]]) tends to work at the level of a general purpose kernel memory allocator, rather than at the higher level of a virtual memory subsystem.
