python学习之路——python切片模拟LRU算法

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

Hint：LRU(Least Recently Used)意思是近期最少使用。

这个算法常用于页面置换算法中。当我们新要访问的页面不在主存中时，就将最近最少使用的页面移除主存，将新的页面存入主存。可以用一个队列来模拟这个算法：目前访问的网页在队列的尾部，最近最少访问的网页在队列的头部，如果新访问的网页在队列中就把这个页面移到队尾，其他页面依次前移；如果新访问的网页不在队列中那就把队头出队然后其他页面前移，新要访问的页面入队。所谓缺页就是指在主存中没有需要访问的页面。

用python模拟LRU算法：

				List=[
				1
				,
				2
				,
				3
				,
				4
				,
				1
				,
				2
				,
				5
				,
				1
				,
				2
				,
				3
				,
				4
				,
				5
				]
				#此列表中存放将要访问的页面
				a_list=[]
				#此列表用来模拟LRU算法中的主存 最多存放3个数
				count=
				0
				#记录缺页数
				tag=
				1
				#标记是否缺页
				for
				i
				in
				List:
				#将要访问的列表元素进行循环
				if
				i
				not
				in
				a_list:
				#如果要访问的元素不在a_list中 即为缺页
				count+=
				1
				tag=
				1
				if
				len(a_list)<
				3
				:
				#如果a_list中没有放满
				a_list[len(a_list)::]=[i]
				#等价于a_list.append(i)将元素i添加到a_list尾部
				else
				:
				#如果列表满了
				a_list[:
				2
				:]=a_list[
				1
				::]
				#利用切片，将前两个元素替换为后两个元素，列表首元素出列表的功能
				a_list[
				2
				::]=[i]
				#将i元素放移动后的到列表最后
				else
				:
				#i元素在列表中
				tag=
				0
				a_list[a_list.index(i)::]=a_list[a_list.index(i)+
				1
				::]
				#将i开始和元素后面的元素替换为i元素后面的元素
				a_list[len(a_list)::]=[i]
				#将i元素插入到移动后的列表后面
				print(a_list,
				"缺页了"
				if
				tag==
				1
				else
				"不缺页"
				)
				print(
				"缺页数为:"
				,count)
			

运算结果：

End.

转载请注明来自36大数据（36dsj.com)： 36大数据 » python学习之路——python切片模拟LRU算法