動機
對於大小為 的快取,確定性分頁算法的最壞情況競爭比為 。當請求序列獨立於算法的隨機選擇而固定時,隨機化可以改變這一比較。隨機化標記算法在一個階段內保護最近被請求的頁面,並在必須逐出頁面時,從其餘候選頁面中均勻隨機地選擇。
期望缺頁次數由一個調和和控制。證明把必然缺頁的新出現頁面,與可能已被隨機逐出的舊頁面區分開來。證明同時明確陳述了對手模型:固定的序列不能在觀察到算法私有的隨機逐出之後才選定。
定義
定義 7.5.1
(按需分頁與不經意對手)
採用按需分頁模型,快取容量為 ,線上排程與離線排程的初始快取相同。每次缺頁成本為一。輸入是在任何隨機選擇之前就已固定的有限請求序列;這稱為不經意對手(oblivious adversary)。下文的期望是針對該固定輸入,對算法的隨機選擇取的期望。
定義 7.5.2
(隨機化標記算法)
把序列貪婪地劃分為若干階段:當某個請求將引入第 個不同頁面時,開始新的階段。因此除最後一個階段外,每個階段恰好含有 個不同頁面。在每個階段開始時清除所有標記。服務完一個請求後,標記其頁面。發生缺頁時,從快取中未被標記的頁面裏均勻隨機地選一個逐出。在本階段內請求一個新頁面之前,被標記的頁面少於 個,因此存在未被標記的快取頁面。
定義 7.5.3
(全新頁面與舊頁面)
對於第一個階段之後的階段,若某個被請求的不同頁面沒有在前一階段出現過,稱其為全新頁面(clean),否則稱為舊頁面(stale)。設 為第 個階段中全新頁面的個數。由於前一階段是完整的,它的 個頁面恰好就是下一階段開始時的快取內容:每個頁面在被請求時都被標記,因此在該階段其後不可能被逐出。
定義 7.5.4
(調和數)
記 。
定理
定理 7.5.5
(隨機化標記算法的期望成本)
對於每個固定的有限請求序列,隨機化標記算法滿足
期望是對算法的選擇而取的,而 是同一固定序列上離線算法的最小缺頁次數。
定理 7.5.6
(單個階段的期望缺頁次數)
在固定請求序列的條件下,第一個階段之後的任意階段的期望缺頁次數至多為 。
證明
證明:缺失舊頁面構成均勻集合
證明
(一個階段的期望成本)
固定第一個階段之後的某個階段,以及它的前一階段的頁面集合 ,該集合恰好含有 個頁面。在當前階段已請求 個不同的舊頁面之後, 中有 個頁面在本階段尚未被請求。設 為已經被請求的不同全新頁面的個數。所有已請求的頁面都被標記並留在快取中。 中未被請求的頁面裏恰有 個不在快取中:快取有 個槽位,被標記的全新頁面佔據了 個槽位,而這些槽位在階段邊界處原本由 中的頁面佔據。
在 的 個未被請求的頁面中,缺失的 個頁面構成一個均勻隨機的 元子集。這一不變量在開始時成立,因為此時 。對一個新的全新頁面的請求會缺頁,並從 中未被標記的快取頁面裏均勻隨機地選一個逐出;把該被逐出的頁面加入缺失集合,得到一個大小為 的均勻子集。對於一個新的舊頁面請求:若所請求的頁面在快取中,標記它就把一個在快取中的頁面移出考慮範圍;若它不在快取中,則載入並標記它,把一個缺失頁面移出考慮範圍,同時從在快取中且未被標記的頁面裏均勻隨機地選一個逐出。無論哪種情形,在以該命中或未命中為條件時,剩餘的缺失集合在相應剩餘大小的子集中仍是均勻的。對已標記頁面的重複請求不改變該不變量。
序列的固定獨立於隨機選擇,所以它的下一個此前未被請求的舊頁面並不是透過查看隨機的缺失集合而選出的。因此它缺頁的概率為 ,至多為 。不同的舊頁面請求至多有 個。對其可能的位置把上界求和,得到舊頁面的期望缺頁次數至多為 。每個全新頁面恰好缺頁一次,而對已標記頁面的重複請求都命中。因此該階段的總期望成本至多為 。
證明透視
為甚麼下一個頁面必須獨立地固定
三個要素結合在一起,每個只用一次。計數:每個被請求的頁面都被標記,因而留在快取中,而快取有 個槽位,所以在 個尚未被請求的舊頁面中,恰有 個在快取中, 個缺失。對稱性:每次驅逐都在未被標記的快取頁面中均勻選擇,所以沒有哪個未被請求的舊頁面比其他頁面更可能屬於缺失集合,下一個被請求的舊頁面缺失的概率是 。不經意性:最後這一步用到下一個被請求的頁面在擲硬幣之前已經固定。若請求是看著快取而選的,它總可以指名一個缺失的頁面,概率就是一而不是 ,調和數的界便不成立。最後, 並對 的可能取值求和,便得到 。
證明:比較全新頁面與離線缺頁次數
證明
(把各階段與離線最優相加)
對於 ,第 與第 個階段的頁面集合之併,包含第 階段的 個頁面加上 個全新頁面。在這兩個階段中,大小為 的離線快取至少要缺頁 次:開始時至多有 個頁面,每次缺頁至多能多引入一個被請求的不同頁面。
對各階段邊界把這個不等式求和,任何一次離線缺頁至多被計入相鄰階段對中的兩對。因此 。隨機化算法在第一個階段至多缺頁 次,因為每個頁面在首次被請求後即被標記。由期望的線性性和階段上界得到
期望的線性性不需要各階段之間互相獨立。該不變量在每個階段邊界都成立,因為標記使整個前一階段的頁面集合都留在快取中。附加的 用來容納第一個階段,而無需給它賦予一個虛構的前置請求集合。
例題詳解
例題 7.5.7
(容量為二、含一個全新頁面)
設前一階段的頁面集合為 ,下一階段以對新頁面 的請求開始。算法缺頁,並以各一半的概率逐出 或 。若下一個請求是固定的舊頁面 ,則它以二分之一的概率缺頁。這兩次請求的期望缺頁次數為 。
例題 7.5.8
(容量為三時的調和估計)
當 且一個階段中有一個全新頁面時,。定理把該階段的期望成本界定為 。這是一個上界,對於給定的請求次序並不一定是精確的期望值;證明中把到目前為止已請求的全新頁面個數 替換為其最大值 。
例題 7.5.9
(不含全新頁面的階段)
若當前階段只請求前一階段的頁面,則這些頁面在階段邊界處全部在快取中。沒有任何請求缺頁,所以該階段的成本為零。這與上界 一致,對最後一個不完整的階段也是如此。
例題 7.5.10
(離線的相鄰階段對證明)
取 ,設第 階段請求 ,第 階段請求 。全新頁面有兩個,即 ,這兩個階段共出現五個不同頁面。一個在這一對階段開始時僅含三個頁面的離線快取,無論其初始內容和逐出選擇如何,在這一對階段中都必須至少缺頁兩次。
常見錯誤
反例模式
觀察隨機逐出會改變博弈
設快取為 ,,請求一個全新頁面 。固定的下一個請求 以二分之一的概率缺頁。若對手觀察到 與 中哪個被逐出,然後請求被逐出的那個頁面,則缺頁概率為一。後一種序列依賴於隨機選擇,不在固定輸入的計算範圍之內。
常見錯誤
(把均勻性用於整個頁面全集)
均勻子集的陳述針對的是前一階段中尚未被請求的頁面,而不是全體頁面中的任意頁面。已被請求的全新頁面都已被標記並留在快取中。一個被請求兩次的舊頁面只可能在第一次請求時缺頁;此後直到下一個階段,它一直處於被標記狀態。
常見錯誤
(誇大對數界所顯示的內容)
由於對 有 ,該定理給出 的上界。它並沒有確立最優的隨機化下界,也沒有聲稱所給出的常數是緊的。離線最優值是在同一固定序列上計算的,而不是對響應隨機快取而生成的序列取平均。
理解均勻不變量
設想給尚未被請求的舊頁面貼上標籤,但不賦予它們不同的未來重要性。在一次全新頁面的缺頁處,當前每個在快取中且未被標記的舊頁面被逐出的可能性相同。原本均勻分佈的缺失集合,在加入這個隨機被逐出的頁面之後仍保持均勻。在一次舊頁面的缺頁處,被請求的缺失頁面被恢復,而均勻隨機選出的被逐出頁面在其餘舊頁面中取而代之。這些操作對其餘未被請求的舊頁面是對稱的。
只要下一個舊頁面的身份是在隨機選擇之前就已固定的,它可以是任意的。它本身不需要是均勻選出的。隨機性體現在哪些頁面缺失上,而對稱性使每個特定的未被請求的舊頁面具有相同的缺失概率。當把該論證用於任意固定序列、而不是隨機輸入分佈時,這一區別至關重要。
調和和之所以出現,是因為隨著不同的舊頁面請求陸續到來,符合條件的舊頁面數量不斷減少。我們把缺失概率界定為剩餘數量的倒數,並對可能的位置求和。這個界可能比較鬆,但它給出一個簡單的上界,而無需假設缺失事件互相獨立。
從倒數項到對數
對於每個整數 ,倒數 至多等於 在 到 上的積分。把這些不等式相加得到 ,其中包括 。所得的界隨快取大小對數增長,而確定性算法的下界則線性增長。這兩個陳述使用了不同的對手假設,因此不帶著量詞就不應當比較它們。
階段估計的證明所求和的是概率,而不是概率的乘積。設某個特定的首次舊頁面請求缺頁時指示變量為一,否則為零。它的期望就是其缺頁概率。舊頁面缺頁的總次數是這些指示變量之和,所以即使一次逐出會影響之後的缺頁,其期望仍是各期望之和。假設各次缺頁互相獨立既不必要,通常也是錯誤的。
一個階段可能在所有舊頁面都被請求之前就結束。分析仍然可以對全部 個可能的舊頁面位置求倒數上界之和:不存在的位置不會產生實際缺頁,而加上非負項只會使上界變鬆。這就是為甚麼該論證也能處理最後一個不完整的階段,而不要求它含有 個不同的請求。
面對不經意對手,每個隨機算法的比值至少為 H_k。
自然延伸的下一個問題
對數增長可以避免嗎?
面對不經意對手,每個隨機算法的比值至少為 H_k。
不可以。已知面對不經意對手,沒有隨機分頁算法的競爭比低於 ,所以像 那樣增長的因子無法避免。因此標記算法的界 在量級上是正確的;對應的下界證明超出本單元範圍。
總結
隨機化標記算法保留一個階段中被請求的頁面,並使缺失的、未被請求的舊頁面服從均勻分佈。它們的邊際缺失概率之和給出一個調和界。隨後透過相鄰階段的計數,把全新頁面的個數與離線缺頁次數聯繫起來,從而得到針對固定序列的 保證。
練習
快速檢查
(計算 ,並在 、 時計算所給出的階段上界。)
解答 · 答案
。上界為 。一個界可以超過該階段中可能出現的最多兩次缺頁;它仍然有效,但並不緊。
快速檢查
(在完整的前一階段之後的階段開始時,為甚麼前一階段的所有頁面都在快取中?)
解答 · 答案
前一階段恰好請求了 個不同頁面。每個頁面在被請求時都被標記,而被標記的頁面在階段結束之前不可能被逐出。由於快取有 個槽位,在階段邊界處它恰好包含這些頁面。
快速檢查
(若相鄰兩個階段共含有 個不同頁面,為甚麼任何離線排程在這一對階段中都必須至少缺頁三次?)
解答 · 答案
離線快取在這一對階段開始之前至多含有 個不同頁面。其餘三個被請求的不同頁面都必須在某次缺頁時被載入快取。一次缺頁至多載入一個被請求的頁面,因此至少需要三次缺頁。
快速檢查
(解釋為甚麼對一個階段中已被標記的頁面的重複請求,在該階段不會造成額外的缺頁。)
解答 · 答案
第一次請求被服務之後,該頁面即被標記。逐出規則只在未被標記的頁面中選擇,直到下一個階段邊界清除所有標記,所以該頁面在當前階段的其餘時間一直留在快取中。