python學(xué)習(xí)之路——python切片模擬LRU算法
問題描述:一進(jìn)程剛獲得三個(gè)主存塊的使用權(quán),若該進(jìn)程訪問頁面的次序是1,2,3,4,1,2,5,1,2,3,4,5。當(dāng)采用LRU算法時(shí),發(fā)生的缺頁次數(shù)是多少?
Hint:LRU(Least Recently Used)意思是近期最少使用。
這個(gè)算法常用于頁面置換算法中。當(dāng)我們新要訪問的頁面不在主存中時(shí),就將最近最少使用的頁面移除主存,將新的頁面存入主存??梢杂靡粋€(gè)隊(duì)列來模擬這個(gè)算法:目前訪問的網(wǎng)頁在隊(duì)列的尾部,最近最少訪問的網(wǎng)頁在隊(duì)列的頭部,如果新訪問的網(wǎng)頁在隊(duì)列中就把這個(gè)頁面移到隊(duì)尾,其他頁面依次前移;如果新訪問的網(wǎng)頁不在隊(duì)列中那就把隊(duì)頭出隊(duì)然后其他頁面前移,新要訪問的頁面入隊(duì)。所謂缺頁就是指在主存中沒有需要訪問的頁面。
用python模擬LRU算法:
- List=[1,2,3,4,1,2,5,1,2,3,4,5] #此列表中存放將要訪問的頁面
- a_list=[] #此列表用來模擬LRU算法中的主存 最多存放3個(gè)數(shù)
- count=0 #記錄缺頁數(shù)
- tag=1 #標(biāo)記是否缺頁
- for i in List: #將要訪問的列表元素進(jìn)行循環(huán)
- 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] #等價(jià)于a_list.append(i)將元素i添加到a_list尾部
- else: #如果列表滿了
- a_list[:2:]=a_list[1::] #利用切片,將前兩個(gè)元素替換為后兩個(gè)元素,列表首元素出列表的功能
- a_list[2::]=[i] #將i元素放移動(dòng)后的到列表***
- 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元素插入到移動(dòng)后的列表后面
- print(a_list,"缺頁了"if tag==1 else "不缺頁")
- print("缺頁數(shù)為:",count)
運(yùn)算結(jié)果:



























