block on disk block in the external memory address space figure blocks in external memory when implemented with caching and blockingvirtual memory often allows us to perceive secondary-level memory as being faster than it really is there is still problemhowever primary-level memory is much smaller than secondarylevel memory moreoverbecause memory systems use blockingany program of substance will likely reach point where it requests data from secondary-level memorybut the primary memory is already full of blocks in order to fulfill the request and maintain our use of caching and blockingwe must remove some block from primary memory to make room for new block from secondary memory in this case deciding which block to evict brings up number of interesting data structure and algorithm design issues caching in web browsers for motivationwe consider related problem that arises when revisiting information presented in web pages to exploit temporal locality of referenceit is often advantageous to store copies of web pages in cache memoryso these pages can be quickly retrieved when requested again this effectively creates two-level memory hierarchywith the cache serving as the smallerquicker internal memoryand the network being the external memory in particularsuppose we have cache memory that has "slotsthat can contain web pages we assume that web page can be placed in any slot of the cache this is known as fully associative cache as browser executesit requests different web pages each time the browser requests such web page pthe browser determines (using quick testif is unchanged and currently contained in the cache if is contained in the cachethen the browser satisfies the request using the cached copy if is not in the cachehoweverthe page for is requested over the internet and transferred into the cache if one of the slots in the cache is availablethen the browser assigns to one of the empty slots but if all the cells of the cache are occupiedthen the computer must determine which previously viewed web page to evict before bringing in to take its place there areof coursemany different policies that can be used to determine the page to evict