問(wèn)題描述：一進(jìn)程剛獲得三個(gè)主存塊的使用權(quán)，若該進(jìn)程訪問(wèn)頁(yè)面的次序是1，2，3，4，1，2，5，1，2，3，4，5。當(dāng)采用LRU算法時(shí)，發(fā)生的缺頁(yè)次數(shù)是多少?

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

這個(gè)算法常用于頁(yè)面置換算法中。當(dāng)我們新要訪問(wèn)的頁(yè)面不在主存中時(shí)，就將最近最少使用的頁(yè)面移除主存，將新的頁(yè)面存入主存。可以用一個(gè)隊(duì)列來(lái)模擬這個(gè)算法：目前訪問(wèn)的網(wǎng)頁(yè)在隊(duì)列的尾部，最近最少訪問(wèn)的網(wǎng)頁(yè)在隊(duì)列的頭部，如果新訪問(wèn)的網(wǎng)頁(yè)在隊(duì)列中就把這個(gè)頁(yè)面移到隊(duì)尾，其他頁(yè)面依次前移;如果新訪問(wèn)的網(wǎng)頁(yè)不在隊(duì)列中那就把隊(duì)頭出隊(duì)然后其他頁(yè)面前移，新要訪問(wèn)的頁(yè)面入隊(duì)。所謂缺頁(yè)就是指在主存中沒(méi)有需要訪問(wèn)的頁(yè)面。

用python模擬LRU算法：

List=[1,2,3,4,1,2,5,1,2,3,4,5]  #此列表中存放將要訪問(wèn)的頁(yè)面 
a_list=[]                       #此列表用來(lái)模擬LRU算法中的主存 最多存放3個(gè)數(shù) 
count=0                         #記錄缺頁(yè)數(shù) 
tag=1                           #標(biāo)記是否缺頁(yè) 
for i in List:                  #將要訪問(wèn)的列表元素進(jìn)行循環(huán) 
    if i not in a_list:         #如果要訪問(wèn)的元素不在a_list中 即為缺頁(yè) 
        count+=1 
        tag=1 
        if len(a_list)<3:                   #如果a_list中沒(méi)有放滿 
            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開(kāi)始和元素后面的元素替換為i元素后面的元素 
        a_list[len(a_list)::]=[i]                            #將i元素插入到移動(dòng)后的列表后面 
    print(a_list,"缺頁(yè)了"if tag==1 else "不缺頁(yè)") 
print("缺頁(yè)數(shù)為:",count) 

運(yùn)算結(jié)果：