Question

python

rhe LRU is a common caching strategy which defines policy to evict elements from a cache to make room for the new elements when the cache is full, i.e., discards the least recently used items first. To solve this question, you should assume your cache has a specific size Solution Approach: Let's assume your cache size 4. The first four values are stored in the cache one after another 4 When it is time to store the 5th value, one of them has to evicted to open room for the 5th element In this case element "1" is the least recently used (since it was the first stored element in the cache). After the eviction, the cache has the following elements 5 4 Now if the element "2" is accessed, its timestamp also changed to one of the recently accessed elements 5 4 If we need to store a new element "6", the least recently element would be "3" since the "5", "2" and "4" elements are accessed /stored after "3": 5 6 4 Hint: You need to implement two data structures to solve this problem. The first one implements the cache itself and the second one keeps track of last access times for each element in the first data structure. The eviction function searches inside the second data structure to find the qualified item and update the first data structure with the new element. After insertion, the second data structure has to be updated with a new timestamp for the inserted item.

Answer 1

Here the idea is to implement LRU through queue structure. Queue in FIFO. The least recently used block will appear at the front of queue

code

cachebl=[]
q=[]
def cache(block):
if((block in cachebl)==0):#This will execute when the requested block not in cache
if(len(q)<4): #This will exeucted when there empty spot in cache
q.append(block)
cachebl.append(block)
print("cache status:",cachebl," queue status:",q)
else:# This will execute when there is a block eviction needed
evict=q[0]
for i in range(0,3):#This loop is needed to shift elements to front
q[i]=q[i+1]
idx=cachebl.index(evict)#evicting element from cache
cachebl[idx]=block#inserting new block at evicted spot
q[3]=block#new block inserted at the end of queue
print("cache status:",cachebl," queue status:",q)
else:#This will execute when the requested block is already in cache
idx=q.index(block)
si=len(q)
for i in range(idx,si-1):#This will move all the blocks coming after the requested block to frot by on step
q[i]=q[i+1]
q[si-1]=block#inserting the requested block at end
print("cache status:",cachebl," queue status:",q)
  
#This part is for taking input from user. Press 'q' for exiting
c='c'
while(c!='q'):
c=input("Enter block number or press q to exit")
if(c!='q'):
cache((int)(c))
  
  
  

cachebl-[] def cache (block) if ((block in cacheb1)==0 ):#This will execute when the requested block not in cache if (len (q)<4) #This will exeucted when there empty spot in cache q.append (block) cachebl.append (block) print ("cache status:",cachebl," queue status:", g) else:# This will execute when there is a block eviction needed evict=q [ 0 ] for i in range (0,3):#This loop is needed to shift elements to front idx-cachebl. index ( evict)# evicting element from cache cachebl[idx-block# inserting new block at evicted spot q[3]-block#new block inserted at the end of queue print ("cache status:",cachebl," queue status:", g) else: #This will execute when the requested block is already in cache idx-q.index (block) si-len (q) for i in range (idx, si-1):#This will move all the blocks coming after the requested block to frot by on step q[31-1]-block# inserting the requested block at end print ("cache status:", cachebl," queue status:", qg) #This part is for taking input from user. Press 'q' for exiting while (c ! = ' q ' ) : c=input ("Enter block number or press q to exit") if (c!q) cache ((int) (c))

Output

RESTART: C:/Users/SIDHARTH/Documents/Python Scripts/queue Enter block number or press q to exitl cache status: [ ueue status: [l] Enter block number or press q to exit2 cache status: [l, 2 queue status: [l, 2] Enter block number or press q to exit3 cache status: [l, 2, 3] uue status: [1, 2, 3] Enter block number or press q to exit4 cache status: [l, 2, 3, 4] ue status: [l, 2, 3, 4] Enter block number or press q to exits cache status: [5, 2, 3, 4] ue status: [2, 3, 4, 5] Enter block number or press q to exit2 cache status: [5, 2, 3, 4] ue status: [3, 4, 5, 2] Enter block number or press q to exitl cache status: [5, 2, 1, 4] ue status: [4, 5, 2, 1] Enter block number or press q to exits cache status: [5, 2, 1, 4] ue status: [4, 2, 1, 5] Enter block number or press q to exit