Python列表模拟页面调度LRU算法（京东2016笔试题）

问题描述：一进程刚获得3个主存块的使用权，若该进程访问页面的次序是1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。当采用LRU算法时，发生的缺页次数是多少？

解析：所谓LRU算法，是指在发生缺页并且没有空闲主存块时，把最近最少使用的页面换出主存块，腾出地方来调入新页面。

在下面的代码中，应重点理解列表切片模拟LRU算法的用法。

def LRU(pages, maxNum): temp = [] times = 0

for page in lst: num = len(temp) if num < 3: times += 1 temp.append(page) elif num == 3: #要访问的新页面已在主存块中 if page in temp: #处理“主存块”，把最新访问的页面交换到列表尾部 pos = temp.index(page) temp = temp[:pos] + temp[pos+1:] + [page] else: #把最早访问的页面踢掉，调入新页面 temp.pop(0) temp.append(page) times += 1

return times

lst = (1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5) print(LRU(lst, 3))

本题答案为10