Question

python页面置换算法问题

写了个OPT置换算法，但是有点问题，帮忙看下应该怎么改，谢谢啦！（另外LFU算法应该怎么写）最好能给出代码~





Answer 1

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

LRU是最近最少使用页面置换算法，该算法用一个开放的栈来保存当前正在使用的各个页面号。当有一个新的页面要被访问时，就将该页面号加入栈顶(如果分配的内存不够，就将栈底页面号删除，其它页面号前移以给新页面腾出位置)。当要访问的页面已经在栈中时，就只要将这个页面移到栈顶，其它页面维持顺序即可。

缺页中断就是要访问的页不在主存，也就是本题中的开放的栈中没有保存要访问的页面号的情况。

*列表切片模拟LRU算法

[python] view plain copy

• List_flora=[1,2,3,4,1,2,5,1,2,3,4,5] #存放页面访问次序的列表  

• lzh=[] #列表lzh最多(在填满后不多不少)3个元素，用来实现LRU算法  

• count=0 #count用于计算缺页次数  

• flag=True #True表示缺页  

• print("三个主存块的数据变化情况:")  

• for i in List_flora: #i从List_flora的第一个元素开始  

• if i not in lzh: #如果i不在lzh中，即缺页  

• flag=True #表示缺页  

• if len(lzh)<3: #如果lzh的长度还没到达3  

• lzh[len(lzh)::]=[i] #就在其尾部添加i  

• else: #如果lzh的长度已经到达3了  

• lzh[0:2:]=lzh[1:3:] #将lzh[1]和lzh[2]复制到lzh[0]和lzh[1]  

• lzh[2::]=[i] #将i放入lzh[2]的位置  

• count+=1 #缺页的，记录之  

• else: #如果i在lzh中，即不缺页  

• flag=False #表示不缺页  

• lzh[lzh.index(i):len(lzh)-1:]=lzh[lzh.index(i)+1::] #将i之后的元素都复制到i开始向后的位置，并在最后留一个空位保证不改变lzh长度  

• lzh[len(lzh)-1::]=[i] #将最后一个元素用i覆盖  

• print(lzh,"缺页了" if flag is True else "不缺页")  

• print("LRU算法结束，总的缺页次数为",count)  




运行结果：




一开始还以为python中没有bool型变量，原来是这里的true和false要写成True和False才行。

在切片中，如果对切片所得的东西赋值，就能改变原列表中该位置的数据。在这样的赋值中应尽量保证左右两侧的list长度一致，如果将

[python] view plain copy

• lzh[lzh.index(i):len(lzh)-1:]=lzh[lzh.index(i)+1::]  



• 改为

[python] view plain copy

• lzh[lzh.index(i)::]=lzh[lzh.index(i)+1::]  

就会发现得不到想要的结果了。