Use of page replacement algorithms inside a cache
In a cache memory, page replacement algorithms are used very often. What is a page replacement algorithm? What function does it perform? Which are the different page replacement algorithms?
In a cache memory, page replacement algorithms are used very often. What is a page replacement algorithm? What function does it perform? Which are the different page replacement algorithms?
A page replacement algorithm is an algorithm which searches for a page in the cache and when it doesn’t find it in the cache, it looks out for the same page in the main memory and transports it into the cache. It is used to keep the frame size of the cache memory restricted, but at the same time, look out on a page in the cache memory efficiently.
The different page Replacement algorithms include: FIFO, LRU, LFU and Optimal Page replacement algorithm.
A page replacement algorithm, in a computer operating system or OS, is the thing responsible for deciding which memory pages should be paged out or swapped out or written to disk when an allocation is required for a page of memory.
This is only applicable to operating systems that implements paging for virtual memory management. Paging occurs when there is a page fault and it cannot use the free page to meet the allocation either because there are no available free pages or the amount of free pages is lesser than some threshold. Back in the 1960s and 1970s, page replacement algorithms were a hot topic of debate and research.
The page replacement algorithms requirements have changed because of the variation in operating system kernel architectures. Specifically, the majority of the modern operating system kernels have integrated or unified file system caches and virtual memory which then requires the page replacement algorithm to pick a page from among the pages of both cached files and user program virtual address spaces. Replacement algorithms can be global or local.