背景知識
-
局部性原理：
- 時間局限性：如果程序中某條執(zhí)行被執(zhí)行，則不久后該指令還可能被在次執(zhí)行。如果某條數(shù)據(jù)被訪問過，則不久以后該數(shù)據(jù)還可能被繼續(xù)訪問。產(chǎn)生時間局限性經(jīng)典原因是存在程序中存在大量的循環(huán)操作
- 空間局限性：一旦程序訪問了程序訪問了某個存儲單元，在不久以后其附近的存儲單元也將被訪問，即程序在一段時間內訪問的地址可能集中在一定的范圍之內，其典型情況便是程序的順序執(zhí)行（雖然存在過程調用，使程序的執(zhí)行軌跡由一部分區(qū)域轉向另一部分區(qū)域，，但研究表明，過程調用的深度在大多數(shù)情況下不超過5）。
虛擬存儲器
虛擬存儲器基本工作情況：
基于程序的局部性原理可知，應用程序在運行前沒必要將作業(yè)全部裝入內存，而僅將當前要運行的少數(shù)頁面裝入內存便可運行，其余部分暫留在盤上。程序運行時，若它所要訪問的頁已調入內存，便可繼續(xù)執(zhí)行下去，但若未調入內存（稱為缺頁或缺段），便發(fā)出缺頁/缺段請求，此時，os將利用請求調頁/段功能將它們調入內存，以便進程能繼續(xù)執(zhí)行下去。如果此時內存已滿，無法裝入新的頁/段，os還需利用頁/段置換功能，將內存中暫時不用的頁/段調至盤上，騰出足夠的內存空間后，再將要訪問的頁/段調入內存，是程序繼續(xù)執(zhí)行下去。虛擬存儲器的定義：
具有請求調入功能和置換功能，能從邏輯上對內存容量加以擴充的一種儲存器系統(tǒng)（基于程序的局部性原理）。其邏輯容量由內存容量和外存容量之和所決定，其運行速度接近內存，而每位成本卻又接近于外存。-
虛擬存儲器的實現(xiàn)方法：
- 分頁請求系統(tǒng)：在分頁系統(tǒng)的基礎上增加了請求調頁功能和頁面置換功能所形成的頁面時虛擬存儲系統(tǒng)。置換時以頁為單位。
- 請求分段系統(tǒng)：在分段系統(tǒng)的基礎上，增加了請求調段及分段置換功能所形成的段式虛擬存儲系統(tǒng)。置換時以段為單位。
頁面置換算法：
最佳置換算法：所選擇的被淘汰頁面是以后永不使用的，或是在最長時間內不再被訪問的頁面。但由于目前人們無法預知哪個頁面時未來最長時間內不再被訪問的，因此該算法是無法實現(xiàn)的。
先進先出（FIFO）頁面置換算法：總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。實現(xiàn)方法為：把一個進程已調入內存的頁面按先后次序鏈接成一個隊列，并設置一個指針（稱為替換指針），始終指向最老的頁面。但是該算法與進程實際運行的規(guī)律不相適應，因為在進程中，有些頁面經(jīng)常被訪問，比如含有全局變量，常用函數(shù)，例程等的頁面，F(xiàn)IFO算法不能保證這些頁面不被淘汰。不需要特定的硬件支持，實現(xiàn)方式簡單
最近最久未使用（LRU）置換算法：選擇最近最久未使用的頁面予以淘汰，利用“最近的過去”，作為預測“最近的將來”的依據(jù)。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t。當需要淘汰一個頁面時，選擇現(xiàn)有頁面中t值最大的淘汰。實現(xiàn)方法：可利用一個特殊的棧保存當前使用的各個頁面的頁面號。每當進程訪問某頁面時，便將該頁面的頁面號從棧中移出，再將它壓入棧頂。因此棧頂始終是最新訪問頁面的編號，棧底永遠是最近最久未被訪問的頁，若發(fā)生缺頁中斷，且內存已滿的情況時，應選擇棧底頁面予以淘汰。需要特定的硬件支持，如寄存器和棧，實現(xiàn)方式較FIFO復雜
LRU算法的代碼實現(xiàn)
from collections import OrderedDict
class LruCache():
def __init__(self, size):
self.size = size
self.cache = OrderedDict()
def get(self, key):
if key in self.cache:
self.cache.move_to_end(key)
value = self.cache[key]
else:
value = None
return value
def set(self, key, value):
if key in self.cache:
self.cache[key] = value
self.cache.move_to_end(key)
else:
if self.size <= len(self.cache):
self.cache.popitem(last=False)
self.cache[key] = value
else:
self.cache[key] = value
以上算法采用了collection庫中的Orderdict類，該類為dict的一個子類，詳情見官網(wǎng),簡單來說就是該類實現(xiàn)了有序dict。
以下為測試用例及輸出結果：
a = LruCache(5)
for i in range(0, 4):
a.set(i, i*10)
print(a.cache, a.cache.keys())
print(a.get(2))
print(a.cache, a.cache.keys())
a.set(6, 666)
print(a.cache, a.cache.keys())
a.set(8, 888)
print(a.cache, a.cache.keys())
C:\Users\19205\AppData\Local\Programs\Python\Python36-32\python.exe C:/Users/19205/Desktop/lru.py
OrderedDict([(0, 0), (1, 10), (2, 20), (3, 30)]) odict_keys([0, 1, 2, 3])
20
OrderedDict([(0, 0), (1, 10), (3, 30), (2, 20)]) odict_keys([0, 1, 3, 2])
OrderedDict([(0, 0), (1, 10), (3, 30), (2, 20), (6, 666)]) odict_keys([0, 1, 3, 2, 6])
OrderedDict([(1, 10), (3, 30), (2, 20), (6, 666), (8, 888)]) odict_keys([1, 3, 2, 6, 8])
最少使用（LFU）置換算法：該算法淘汰頁面的依據(jù)是頁面被訪問的頻率，選擇在最近時期使用最少的頁面作為淘汰頁
Clock置換算法：
頁面緩沖算法（PBA）：顯著降低了頁面換進換出的頻率，使磁盤I/O的操作次數(shù)大為減少，因而減少了頁面換進換出的開銷。實現(xiàn)方式：在內存中設置了兩個鏈表：空閑頁面鏈表：實際上該鏈表是一個空閑物理塊鏈表，是系統(tǒng)掌握的空閑物理塊，用于分配給頻繁發(fā)生缺頁的進程，以降低該進程的缺頁率 。修改頁面鏈表：它是由已修改的頁面所形成的鏈表。設置該鏈表的目的是為了減少已修改頁面換出的次數(shù)。
