問題描述：一進程剛獲得三個主存塊的使用權，若該進程訪問頁面的次序是1，2，3，4，1，2，5，1，2，3，4，5。當採用LRU演算法時，發生的缺頁次數是多少？ Hint：LRU(Least Recently Used)意思是近期最少使用。 這個演算法常用於頁面置換演算法中。當我們新要訪問的頁面不在主存中時 ...
問題描述：一進程剛獲得三個主存塊的使用權，若該進程訪問頁面的次序是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)
運算結果：
總結:
python列表中的切片返回的是一個新的列表，是對原列表的一個淺複製，直接對切片返回的列表操作能改變原列表，但是如果將切片操作返回的列表賦值給一個新的變數那麼原列表的地址並沒有被覆制，對新列表的操作不影響原列表；與之相對應的“=”賦值運算操作是一個深拷貝的引用。
2017-04-17
