It costs a long time for CPUs to access data from memory, so most of CPUs have caches where requests for data can be served faster. To be cost-effective and to enable efficient use of data, caches mus
It costs a long time for CPUs to access data from memory, so most of CPUs have caches where requests for data can be served faster. To be cost-effective and to enable efficient use of data, caches must be relatively small. Therefore, we must use some policies to choose some data wisely and storage them in the cache. We divide the memory into many blocks which have the same size and index them from 1 to 10910^9109, and every block has an unique index. A cache will have a capacity for KKK blocks, which means it can storage at most KKK blocks simultaneously. A cache hit occurs when the requested block is available in the cache, or we say a cache miss occurs. Now we introduce a LRU (Least Recently Used) placement policy on a fully associative cache. If the requested block is available in the cache, a cache hit occurs. If not, CPU can only access the block from the memory and write the block into the cache. If cache is not full, append the block into the cache. If the cache is full, cache is full, the block which haven't been visited for the longest time in the cache will be replaced by the new block. An example for cache with capacity of 333 blocks is shown below. The 8th8^{th}8th, 4th4^{th}4th and 3rd3^{rd}3rd are in the cache when the 6th6^{th}6th block is requested, so a cache miss occurs. At that time, the cache is full, and we must decide the block to be replaced. The most recent request of 8th8^{th}8th block is the 13th13^{th}13th request, the most recent request of 4th4^{th}4th block is the 14th14^{th}14th request and the most recent request of 3rd3^{rd}3rd block is the 11th11^{th}11th request. The 3rd3^{rd}3rd block will be replaced by the 6th6^{th}6th block because the 3rd3^{rd}3rd block hasn't been visited for longest time. Now the sequence of requested blocks and the capacity of the cache are given, please determine the minimum capacity for the cache in order to ensure at least K requests to hit the cache.
标签： HBC229318欧拉 数论LRU题解
