python-模拟页面调度LRU算法

【题目描述】所谓LRU算法，是指在发生缺页并且没有空闲主存块时，把最近最少使用的页面换出主存块，腾出地方来调入新页面。问题描述：一进程获得n个主存块的使用权，对于给定的进程访问页面次序，问当采用LRU算法时，输出发生的缺页次数。

【练习要求】请给出源代码程序和运行测试结果，源代码程序要求添加必要的注释。

【输入格式】在第一行中输入进程获得使用权的主存块数量n。在第二行中输入进程访问页面的次序，各数据之间以空格为间隔。

【输出格式】输出对于给定的n和进程访问页面的次序，输出采用LRU算法时的缺页次数。

【输入样例】3

　　　　　　1 2 3 4 1 2 5 1 2 3 4 5

【输出样例】7

首先了解一下什么是LRU算法

可以参考这篇博客，里面举的例子非常好：如何实现LRU算法？ - murphy_gb

那么这道题，我们应该怎么分析？

代码实现：

queue = []

count = 0

piece = int(input())

process = input()

page = process.split(" ")

for i in page[::]:

    if i == '':

        page.remove(i)

for i in range(0, len(page)):

    queue.append(page[i])

    if i == len(page) - 1:

        break

    if len(queue) == piece:

        j = 0

        while j in range(0, piece):

            if page[i + 1] == queue[j]:

                queue.append(queue[j])  # 如果后一个页面与这三个页面中的相同，那么就将这个页面提前

                queue.pop(j)    # 删除到原来所处的位置

                page.pop(i + 1)  # 删除，进入下一个页面

                j = 0

            else:

                j += 1

        queue.pop(0) # 淘汰页面

        count += 1

print(count)

巴特西

python-模拟页面调度LRU算法

最新文章

热门文章