問題描述：一進(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é)果：