動機
快取之所以有用,是因為最近被請求過的頁面很可能再次被需要。然而,當所請求的頁面不在快取中時,快取必須在看到後續請求之前先騰出空間。這個決策是線上的:只能根據迄今已見到的請求序列來作出。離線基準則知道整個序列,因而可以據此規劃其驅逐。
競爭分析把線上算法的成本與離線最優算法在同一請求序列上的成本相比較。本章給出標記算法 上界的一個清晰的階段式證明,並另行給出確定性算法 的對抗性下界。這裏的上界是有意取得初等的;它並不表示 是最近最少使用(LRU)分頁所能達到的最佳保證。
定義
定義 7.3.1
(分頁模型:命中、缺頁與成本)
給定一個頁面全集和容量為 的快取。對快取中頁面的請求稱為命中,成本為零。對不在快取中的頁面的請求稱為缺頁,成本為一:被請求的頁面會被載入,若快取已滿,則驅逐一個頁面。線上算法與離線最優算法都從同一個指定的、含 個互異頁面的快取開始。我們考慮有限的請求序列;離線算法在決定驅逐哪個頁面時可以利用未來的資訊。
定義 7.3.2
(帶加性常數的競爭比)
若對每個有限序列 都有
則稱算法 是帶加性常數 的 -競爭的,其中 取決於 和固定的初始快取,但不取決於 。加性項對短序列很重要;若不帶加性項,則當離線最優成本為零時,比值沒有定義。
定義 7.3.3
(請求序列的階段)
把一個非空請求序列貪心地劃分為階段。第一個階段從第一個請求開始。只要下一個請求屬於該階段最初的 個互異頁面名之一,該階段就繼續;對第 個互異新頁面的請求則開啟下一個階段。因此除了可能的最後一個階段外,每個階段恰好包含 個互異頁面。
定義 7.3.4
(標記算法)
標記算法在每個階段開始時清除所有標記,並對每個被請求的頁面加上標記。發生缺頁時,它驅逐一個未被標記的頁面。這樣的頁面總是存在的:在一個階段內處理一個新的互異頁面之前,被標記的不同頁面少於 個,而快取持有 個頁面。最近最少使用(LRU)是一種標記算法,因為每個被標記的頁面都在當前階段被使用過,而每個未被標記的快取頁面最後一次使用都在更早的時候。
定理
定理 7.3.5
(一個簡單的標記算法上界)
對於任何被劃分為 個階段的請求序列,標記算法至多產生 次缺頁,而離線最優算法至少產生 次缺頁。因此每個標記算法都是帶加性常數 的 -競爭的。
定理 7.3.6
(確定性算法的下界)
對於快取大小為 的每個確定性線上分頁算法,以及每個 ,都不存在常數 使得其成本在每個序列上至多為 。即使頁面全集只有 個頁面,只要初始快取包含於該全集中,這一結論依然成立。
證明
證明:標記階段
證明
(標記算法的階段計數)
在一個階段內,標記算法絕不會驅逐一個已被請求並被標記的頁面。因此每個互異頁面在該階段內至多缺頁一次,故至多發生 次缺頁。對 個階段求和即得線上上界。
對於相鄰兩個階段之間的每個邊界,後一階段的第一個請求是前一階段中未被請求過的頁面。由於前一階段含有 個互異頁面,這兩個階段的聯集至少含有 個互異頁面。若離線最優算法在這個兩階段區間內沒有任何缺頁,則其快取在整個區間內保持不變,並且包含所有這些頁面,而這與容量為 矛盾。因此每一對相鄰階段中至少包含一次離線缺頁。
一次缺頁只屬於單一階段,因此至多落在兩個相鄰階段對中。對 個階段對計數,得 。結合兩個界即得
這種配對論證把每次缺頁至多計兩次,而不是恰好計兩次。它是有意保守的,只證明了所述的因子,而並不聲稱這是一個緊的上界。
證明透視
因子二從何而來
標記規則與快取容量各自發揮作用。在線上一側,僅憑標記規則,每個互異頁面在每個階段至多缺頁一次,故每個階段至多缺頁 次;這裏沒有用到離線調度的任何性質。在離線一側,關鍵的一步是憑證:階段 的 個頁面加上階段 的第一個請求,共是 個互異頁面名,而容量為 且不發生改變的快取無法容納它們,所以這一對階段之中必有缺頁。相鄰的階段對互相重疊:階段 同時屬於 與 ,因此內部階段中的一次離線缺頁可以同時為兩個階段對作證。於是階段對的數目至多是離線缺頁次數的兩倍。若把這些見證缺頁自動視為互不相同,便會得到 ,這是沒有根據的更強斷言,並會把因子 錯誤地變成 。
證明:針對任意確定性算法的對手
證明
(針對確定性算法的適應性對手)
固定一個確定性線上算法,以及恰含 個頁面且包含其初始快取的頁面全集 。不斷請求 中不在該算法當前快取裏的頁面。這樣的頁面總是至少有一個。該算法在每個請求上都缺頁。由於算法是確定性的,一旦固定長度 ,這個自適應過程就確定了一個特定的有限序列;所得序列可作為針對該算法的固定最壞情況輸入。
為了界定該序列上的離線最優成本,把它劃分為同樣的階段。每個完整階段含有 個互異請求,因此至少含有 個請求。所以階段數 滿足 。
若 ,請求的不同頁面至多有 個;每個頁面首次請求後將其保留即可,因此離線最優代價至多為 。現在假設 ,則第一個階段包含恰好 個互異頁面。一個知道各階段的離線策略在第一個階段至多缺頁 次:它保留該階段所請求的每個頁面,並在缺頁時驅逐一個不屬於第一階段頁面集合的頁面。需要空間時,總是存在這樣的頁面。到該階段結束時,其快取恰好含有該階段的 個互異頁面。
元全集的任意兩個 元子集至多相差一個頁面。在下一個完整階段,離線策略保留兩者共有的頁面,並且若那個新頁面被請求,就驅逐不屬於新階段集合的那一個頁面。因此它在該階段至多缺頁一次,並以整個集合都在快取中而結束。對於最後一個不完整的階段,把其被請求的集合任意擴充為 的一個 元子集,並使用同樣的論證。所以
線上成本恰為 。若對某個 有一個固定的不等式 成立,則對每個 都有 。右邊 的係數嚴格小於一,因此足夠大的 會與該不等式矛盾。這就證明了下界,並且包含了加性常數的約定。
例題詳解
例題 7.3.7
(一個兩頁面的 LRU 軌跡)
取快取 ,容量為二,請求為 。LRU 在 上命中,在 上缺頁並驅逐 ,在 上缺頁並驅逐 ,然後在 上缺頁並驅逐 。其成本為三。各階段為 與 ,各含兩個互異頁面。它們的聯集含有三個互異頁面,因此任何離線調度在這兩個階段中至少要缺頁一次。
例題 7.3.8
(一個簡短的離線比較)
對同樣的快取和請求,一個離線策略在 上命中,然後載入 並驅逐 ,因為下一個請求是 。它在 上命中,然後載入 ,共缺頁兩次。一次缺頁不可能足夠:在請求 時,快取必須驅逐 或 ,而被驅逐的頁面稍後會被請求,其間沒有任何零成本的方式把它載入。因此離線最優恰為二。
例題 7.3.9
(容量為一時的確定性對手)
頁面全集為 ,初始快取為 ,先請求 ,然後請求 中缺失的那一個。容量為一迫使序列交替為 ,線上算法與離線算法在每個請求上都缺頁。下界為 ,與這個特例一致。
例題 7.3.10
(兩個階段集合高度重疊)
取 ,頁面全集為 ,相鄰的完整階段集合可以是 與 。持有第一個集合的離線快取,只需在第二階段首次請求 時把 換成 。請求的內部順序可以是任意的;一旦這三個頁面為該階段載入,離線策略就會保留全部三個。
常見錯誤
反例模式
驅逐已標記頁面的規則
斷言:每個確定性的按需分頁規則都滿足 保證。缺少標記性質時這是錯的。取 ,初始快取為 (依此次序載入),規則是永遠驅逐最近載入的頁面。對長度為 的請求 ,每次請求都缺頁:載入 時驅逐 ,載入 時驅逐 ,如此類推,成本為 。離線調度在第一個請求時驅逐 ,保留 和 ,總成本為 。界 在 時已被違反,任何常數都補救不了。這條規則不是標記算法:在第一階段中 與 都已被請求之後,它卻驅逐已標記的頁面 。補救之道就在定理的假設:只驅逐未標記的頁面。
常見錯誤
(把對手論證推廣到隨機化算法)
對於確定性算法和固定長度,一旦模擬該構造,其選擇便事先決定唯一的一個序列,因此可作為固定的最壞情況輸入。這個推理不會自動推廣到面對不經意對手的隨機化算法:快取中缺失的頁面可能取決於私有的隨機選擇,因此量詞與期望必須另行說明。
常見錯誤
(把兩個界之間的差距當作確切競爭比)
上界與 下界並不吻合。它們顯示的是一個有效的保證和一個普適的障礙,而不是某條線上規則的確切競爭比。更精細的分析也許能縮小這一差距,但本章並未證明。
為甚麼階段是有用的
階段記錄的是近期請求的工作集,而不是固定數目的時間步。如果同樣的少數頁面反覆出現,階段可以非常長,但標記算法在一個階段內對其中任何一個頁面至多付出一次成本。這使得上界對重複命中不敏感。
離線比較更困難,因為最優算法進入一個階段時,其頁面可能是借助未來資訊選定的。它不必在每個單獨的階段都缺頁。考察兩個連續階段則提供了一個憑證:它們合起來的請求超出了快取容量。這個簡單憑證的代價是,一次離線缺頁可以支持兩個相鄰的憑證。
下界用到的是另一個事實。在含 個頁面的全集上,兩個完整階段集合至少重疊 個頁面。知道下一個集合,使離線策略每個階段至多改動一次即可做好準備。與此同時,線上算法被迫在每個請求上都缺頁。重疊和離線知識這兩者對該論證都是必不可少的。
總結
標記算法把線上算法限制在每個階段每個互異頁面至多缺頁一次。連續的階段之間必然有一次離線缺頁,由此得到帶加性常數 的 競爭保證。 個頁面上的確定性對手則迫使任何確定性線上算法面對漸近下界 。
練習
快速檢查
(對 ,把 劃分為階段,並給出每個階段中互異頁面的個數。)
解答 · 答案
各階段為 、 和 。它們的互異頁面個數分別為二、二和一。請求 開啟第二階段,因為它會是第一階段中的第三個互異頁面;同理 開啟第三階段。
快速檢查
(在同一序列中,為甚麼即使一個階段含有許多請求,標記算法在每個階段中至多缺頁兩次?)
解答 · 答案
一個頁面在該階段中第一次被請求之後即被標記,在該階段內不能被驅逐。每個階段至多含有兩個互異頁面,因此每個頁面至多缺頁一次,總共至多缺頁兩次。
快速檢查
(取 ,,離線快取持有 ,下一個完整階段使用 。描述一個至多缺頁一次的策略。)
解答 · 答案
保留 。若請求 ,則缺頁一次,載入 並驅逐 。此時該階段所請求的全部頁面都在快取中,因此之後的請求都命中。若 沒有被請求,則該階段集合並不像題設所說是完整的。
快速檢查
(對 ,確定性對手產生一個長度為 的序列。根據證明陳述離線成本的一個上界,並解釋為甚麼線上成本為 。)
解答 · 答案
證明給出 。在每個請求上,對手都選取一個不在線上快取中的頁面,因此線上算法在全部 個請求上都缺頁。離線上界不必是整數;它是對一個整數成本的上界。