Replacement Algorithms

Before we discuss more deeper about the replacement algorithm, we need to understand what and how cache memory works. Cache memory is a component used by CPU (central processing unit) to reduce average time access main memory.  Data that frequently used will be store inside cache memory obtain from main memory. The cache memory is faster and smaller.

storage cache memory

storage cache memory

If the CPU want to read or write data from memory, it will check it first is it exist or not. If yes, CPU directly read or write from cache memory because it’s more faster rather than access to main memory. The block that contain data inside cache memory will be replace the block of data from main memory using replacement algorithm technique if all the blocks already been fill up in cache memory.

There are a lot of cache levels that can rely only one single replacement algorithm. There are two types of page, HOT (active) page and COLD (passive) page. The blocks will be distributed into HOT pages and store in cache memory meanwhile COLD pages will be store in main memory (sometimes can be in cache memory).

Current processors technology are able to support from L1,L2 until L3. L4 will be in future because limitation in terms of hardware size and cost. L1 stores HOT pages compare to L2 stores both HOT and COLD pages. L1 used LRU (Less Recently Used), FIFO (First In First Out) and LFU (Less Frequently Used).