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