動機
階段(phase)論證可以給出標記類算法一個簡單的 競爭界。該論證把每次離線缺頁至多計入兩個相鄰的階段對,因此刻意留下了一段差距。最近最少使用(LRU)分頁算法有更精確的保證:在初始快取相同的條件下,離線算法每缺頁一次,LRU 至多缺頁 次。
證明的做法是在每次請求之後比較兩個快取。僅僅統計兩者不同的頁面數目,不足以說明一次命中如何改變 LRU 的新近程度次序。加權勢函數則同時記錄兩件事:哪些線上頁面不在離線快取中,以及每個這樣的頁面最近被使用的程度。權重的取法使得 LRU 的每次缺頁都能透過勢函數的下降來自行抵償。
定義
定義 7.4.1
(與離線排程比較的按需分頁)
頁面全集可以是有限集或無限集,兩個快取的容量均為 。兩者從相同的 個頁面開始;LRU 另外獲給定一個固定的初始新近程度次序。命中的代價為零。缺頁時,被請求的頁面會被載入,同時逐出一個已快取的頁面,代價為一。離線調度知道整個有限的請求序列,但與 LRU 一樣,只在處理缺頁時才改變快取。這個按需分頁(demand paging)模型包含了本問題的離線最優解。
定義 7.4.2
(LRU 快取與新近排名)
記 為 LRU 的快取, 為離線快取。將 中的頁面排名:最近使用的為第 位,最久未使用的為第 位。一次請求把所請求的頁面移到第一位,位於其前的頁面各向後移一位。缺頁時,LRU 逐出第 位的頁面,並把被請求的頁面插入第一位。
定義 7.4.3
(按新近程度加權的勢函數)
定義非負的勢函數
最近使用的線上頁面權重為 ,最久未使用的權重為一。一個頁面只有在屬於 LRU 的快取而不屬於離線快取時才有貢獻。初始快取相同時,勢函數為零。
定理
定理 7.4.4
(LRU 是 k-競爭的)
對於每個有限請求序列,以及每個初始快取相同的離線按需分頁調度,LRU 的缺頁次數至多是該調度缺頁次數的 倍。特別地,。
定理 7.4.5
(確定性算法中的精確性)
任何確定性線上分頁算法的競爭比都不可能嚴格小於 ,即使容許加上一個與請求序列無關的加性常數。因此,在此模型中,LRU 定理中的因子 對確定性算法而言是最優的。
證明
先計入離線步驟
證明
(先計離線一步,再計 LRU 一步)
把每個請求分成兩個概念上的步驟來處理。先讓離線調度處理該請求,同時保持 LRU 的快取和排名不變;再讓 LRU 處理該請求,同時保持更新後的離線快取不變。這只是記賬的次序;兩個調度仍然互相獨立,且面對同一個請求。
如果離線步驟是命中,則兩個快取和勢函數都不變。如果是缺頁,則被請求的頁面進入 ,並且至多有一個頁面離開 。把一個頁面加入 只可能去掉勢函數中的一項。把一個頁面從 中移出至多增加一項,該項的權重至多為 。因此一次離線缺頁使 至多增加 。這一步之後,被請求的頁面屬於 。
現在考慮 LRU 步驟。如果該請求在 中命中,則其頁面在 中,不貢獻任何項。把它移到第一位,會使另一些頁面各向後移一位,它們的權重各減一,其餘權重不變。勢函數不會增加;LRU 的代價為零。
如果 LRU 缺頁,則被請求的頁面在 中但不在 中。LRU 逐出其第 位的頁面 ,再把被請求的頁面插入第一位。若 ,則被移除的那一項權重為一。若 ,由於兩個快取大小相等,且被請求的頁面屬於 ,故必有某個頁面屬於 。該頁面不是 ,並向後移一位,權重減一。無論哪種情形,新插入的被請求頁面貢獻為零,其他項都不增加, 至少減少一。這一減少抵償了 LRU 的一次缺頁。
設 分別為第 個請求上的兩個缺頁指示量, 為兩個概念步驟合起來的勢函數總變化量。上述各種情形給出
對整個序列求和,勢函數的變化量互相抵消(裂項求和)。初始勢函數為零,最終勢函數非負。因此 LRU 的總缺頁次數至多是離線總缺頁次數的 倍。由於該離線調度是任意的,取一個最優調度即得定理。
證明透視
為甚麼 LRU 缺頁會使勢函數下降
如果被逐出的頁面不在離線快取中,則它那一項權重為一,隨之消失。否則,被請求的頁面是僅在離線快取中的頁面,快取大小相等就迫使存在另一個僅線上的頁面;該頁面的新近程度降低一位,權重減少一個單位。
確定性下界的證明
證明
(缺頁對手與階段)
配套的分頁章節針對任意確定性線上算法構造了一個由 個頁面組成的請求序列:每次都請求當前快取中缺失的那個頁面。於是線上算法對全部 個請求都缺頁。把由此得到的固定序列劃分成每段至多含 個不同頁面的階段,就得到一個代價至多為 的離線調度:第一個階段之後,相鄰階段的頁面集合至多相差一個頁面。
因此,對任意 和固定的加性常數 ,當 足夠大時,不等式 不成立。算法和 一旦給定,該構造就是確定的。它證明了沒有確定性算法能有更小的競爭比,而勢函數的證明則說明 LRU 達到了 。
例題詳解
例題 7.4.6
(兩次請求、一次離線缺頁)
設 ,初始時兩個快取都含有 ,對 LRU 而言 最近使用。請求 。假設離線逐出 ,而 LRU 逐出 。兩者都缺頁。新的快取是 和 ,LRU 的次序為 。只有 有貢獻,它位於第二位,所以 。接著請求 。離線命中;LRU 缺頁並逐出 ,勢函數降為零。LRU 缺頁兩次,離線調度缺頁一次,恰好達到因子二的界。
例題 7.4.7
(離線缺頁可能使勢函數增加)
設 ,兩個快取初始時一致,LRU 的次序為 。請求為 。若離線先逐出 ,則保持不變的 LRU 快取含有 而離線快取不含,於是勢函數從零升到三。隨後 LRU 缺頁,逐出 並插入 ,這個勢函數降為二。離線造成的增加至多為 ,與證明所容許的完全一致。
例題 7.4.8
(LRU 命中不一定改變勢函數)
設 ,,LRU 的次序為 。對 的請求在兩個調度中都是命中。LRU 把次序改為 ,但 仍為空,勢函數保持為零。即使沒有缺頁,新近程度也可能改變。
例題 7.4.9
(被逐出的頁面可能屬於離線快取)
設 ,LRU 的次序為 ,離線快取為 。由於 是僅線上頁面且位於第一位,勢函數為二。請求 :離線命中,LRU 逐出 ,而 在離線快取中。僅線上頁面 後移到第二位,權重從二降為一。即使被逐出的頁面本身沒有貢獻任何勢,這一下降也抵償了 LRU 的這次缺頁。
常見錯誤
反例模式
LRU 缺頁時,僅看基數可能保持不變
在上一個例子中,請求之前 ,請求之後它仍然是 ,基數保持為一。然而按新近程度加權的勢函數卻從二降為一。可見,僅僅統計快取之間的差異數目,並不能說明本證明所用的「減少一個單位」。
常見錯誤
(記賬的次序並不是資訊優勢)
比較的對象是同一個請求序列上的一個固定離線調度。兩個更新在概念上的先後次序,並不表示 LRU 能看到離線快取或其逐出的頁面。這只是在兩個決策都已確定之後使用的分析手段。
常見錯誤
(把因子 當成預測)
因子 是對所有序列的最壞情況保證。它並不表示 LRU 的代價總是最優代價的 倍,也沒有解決隨機化算法的競爭性問題。若對手是能觀察隨機快取內容的自適應對手,則需要另行陳述的模型。
為甚麼這樣安排新近程度權重
一個新近的僅線上頁面很可能在日後許多次 LRU 逐出中倖存。給它較大的權重,就提供了一筆儲備,可以隨著它新近程度的降低而逐步花掉。對不同頁面的每一次請求至多使它後移一位,並使其貢獻減一。在次序的最末位,它的權重恰為一,因此逐出它就取走了最後一個單位。
相反,當被請求的頁面已在離線快取中時,把它移到最前面不會為它自己增加任何貢獻。這正是證明先更新離線一方的原因。離線缺頁可以增加儲備,但只是暴露了離線調度所逐出的那一個線上頁面;該頁面的權重至多為 。把這些局部變化在整個序列上平衡起來,就得到代價的比較。
初始次序的約定會影響 LRU 在早期遇到平局時逐出哪個頁面,但不等式對每個固定的初始次序都成立。兩個快取以相同的頁面集合開始時,勢函數為零。若初始快取不同,同樣的計算會多出一個加性的初始勢函數項,至多為 ;對於彼此無關的初始狀態,本節並不斷言去掉該項後的不等式仍然成立。
理解攤還不等式
勢函數是一個記賬量,並非任何一方實際支付的金錢。單個請求可以使表達式 為負:一次 LRU 命中可能使好幾個僅線上頁面同時在次序中後移。負的攤還代價是無害的,因為在整個執行過程中勢函數不會降到零以下。它表示先前累積的儲備被釋放。
證明中的離線調度本身不必是最優的。例如,若某個調度缺頁十次,而 LRU 至多缺頁 次,則不等式成立,但可能很弱。在對每個調度都證明了不等式之後,再選取代價最小的離線調度,就得到與 的比較。這種推理次序避免了對最優解逐出哪個頁面作任何假設。
實現時需要維護成員關係和新近程度次序,例如用字典加雙向鏈表。其實際運行時間取決於字典的操作和計算模型。該定理只統計缺頁次數;它不統計維護鏈表的 CPU 開銷,也不聲稱任何特定的字典時間界。
面對不知情的對手,隨機標記算法的因子只有對數階。
自然延伸的下一個問題
隨機化能勝過因子 k 嗎?
面對不知情的對手,隨機標記算法的因子只有對數階。
下界 能擊敗所有確定性算法,是因為對手看得見它的快取。若請求序列必須事先固定,隨機標記算法的期望成本與最優值之比,只是 的量級。這在隨機標記一節中展開。
總結
按新近程度加權的勢函數在每次離線缺頁時至多上升 ,在離線步驟之後每次 LRU 缺頁時至少下降一。從相同的初始快取出發,求和抵消即證明了精確的因子 。另一個「請求缺失頁面」的對手構造則排除了任何更小的確定性競爭比,即使容許加性常數。
練習
快速檢查
(設 ,LRU 的次序為 ,離線快取為 ,計算勢函數。)
找出在 LRU 快取而不在離線快取的頁面。
解答 · 答案
只有 屬於 ,且其排名為一。它的權重為 ,所以勢函數為三。
快速檢查
(從上一題的情形出發,請求 且離線命中。給出新的 LRU 次序,並計算新的勢函數。)
先判斷 LRU 是命中還是缺頁,再更新次序。
解答 · 答案
LRU 缺頁,逐出最久未使用的 ,並把 插入最前面,得到次序 。唯一的僅線上頁面仍是 ,現在排名第二,權重為二。勢函數下降一,抵償了這次缺頁。
快速檢查
(在同樣的初始情形下,設 LRU 的次序固定,而離線快取從 變為 。計算勢函數的變化量。)
更改之後哪個頁面是僅線上的?它排第幾?
解答 · 答案
初始時勢函數為三。離線快取改變之後, 屬於 而 不屬於,故唯一的貢獻來自位於第二位的 ,權重為二。勢函數的變化量為 。離線改變也可能使勢函數增加,但在缺頁時增加量絕不超過 。
快速檢查
(解釋為甚麼在裂項求和的證明中可以捨去最終勢函數,而如果初始快取不同則需要額外的一項。)
寫出求和後的不等式,再看勢函數的各項。
解答 · 答案
求和得到 。最終勢函數非負,所以去掉它只會使不等式變弱。初始快取相同時初始勢函數為零;否則初始勢函數作為加性上界項保留下來。