分頁（線上快取）
前言
而不是從正式定義開始，目標是通過一系列示例來處理這些主題，並在此過程中引入定義。備註部分理論將包含所有定義，定理和命題，以便為你提供更快速查詢特定方面的所有資訊。
備註部分來源包括用於該主題的基礎材料和用於進一步閱讀的附加資訊。此外，你還可以找到示例中的完整原始碼。請注意，為了使示例的原始碼更具可讀性和更短，它會避免錯誤處理等問題。它還會傳遞一些特定的語言功能，這些功能會模糊示例的清晰度，如廣泛使用高階庫等。
分頁
尋呼問題源於有限空間的限制。我們假設我們的快取 C 有 k 頁面。現在我們要處理一系列 m 頁面請求，這些請求必須在處理之前放入快取中。當然，如果 m<=k 然後我們只是將所有元素放在快取中它會起作用，但通常是 m>>k。
我們說當頁面已經在快取中時，請求是快取命中，否則，它被稱為快取未命中。在這種情況下，我們必須將請求的頁面帶入快取並逐出另一個，假設快取已滿。目標是一種驅逐計劃，可以最大限度地減少驅逐次數。
這個問題有很多策略，讓我們來看看：
- 先進先出（FIFO） ：最舊的頁面被逐出
- 最後，先出（LIFO） ：最新頁面被逐出
- 最近最少使用（LRU） ：最近訪問最早的 Evict 頁面
- 最少使用（LFU） ：最不常請求的 Evict 頁面
- 最長前向距離（LFD） ：快取中的 Evict 頁面，直到將來最遠才會請求。
- 完全重新整理（FWF） ：一旦發生快取未命中，就清除快取完成
有兩種方法可以解決這個問題：
- 離線 ：提前知道頁面請求的順序
- 線上 ：提前查詢頁面請求的順序
離線方法
對於第一種方法，請檢視 “貪婪技術的應用 ”主題。這是第三個示例離線快取考慮了上面的前五個策略，為你提供了以下的良好切入點。
示例程式通過 FWF 策略進行了擴充套件 ：
class FWF : public Strategy {
public:
FWF() : Strategy("FWF")
{
}
int apply(int requestIndex) override
{
for(int i=0; i<cacheSize; ++i)
{
if(cache[i] == request[requestIndex])
return i;
// after first empty page all others have to be empty
else if(cache[i] == emptyPage)
return i;
}
// no free pages
return 0;
}
void update(int cachePos, int requestIndex, bool cacheMiss) override
{
// no pages free -> miss -> clear cache
if(cacheMiss && cachePos == 0)
{
for(int i = 1; i < cacheSize; ++i)
cache[i] = emptyPage;
}
}
};
完整的原始碼可在此處獲得 。如果我們重用主題中的示例，我們將得到以下輸出：
Strategy: FWF
Cache initial: (a,b,c)
Request cache 0 cache 1 cache 2 cache miss
a a b c
a a b c
d d X X x
e d e X
b d e b
b d e b
a a X X x
c a c X
f a c f
d d X X x
e d e X
a d e a
f f X X x
b f b X
e f b e
c c X X x
Total cache misses: 5
儘管 LFD 是最佳的，但 FWF 具有較少的快取未命中。但主要目標是儘量減少驅逐的次數，而對於 FWF 的五次失誤意味著 15 次驅逐，這使得它成為這個例子中最貧窮的選擇。
線上方法
現在我們想要解決分頁的線上問題。但首先我們需要了解如何做到這一點。顯然，線上演算法不能優於最優離線演算法。但它有多糟糕？我們需要正式的定義來回答這個問題：
定義 1.1： 一個優化問題 Π由一組的情況下， ＆Sigma; Π 。對於每一個例項σ∈Σ Π 有一組Ζ σ 的解決方案和一個目標函式 ˚F σ ：Ζ σ →交通ℜ ≥0 其中分配 apositive 真實值的每一個的解決方案。
我們說 OPT（σ）是最優解的值，A（σ）是演算法 A 對於問題Π和 w A （σ）= fσ （A（σ））其值的解。
定義 1.2： 用於最小化問題的線上演算法 A 如果存在常數τ∈ℜ，則競爭比率 r≥1
w A （σ）= fσ （A（σ））≤r·OPT（σ）+τ
所有例項σ∈Σ Π 。A 稱為 r 競爭線上演算法。甚至
w A （σ）≤r⋅OPT（σ）
所有例項σ∈Σ Π 則稱 A 是一個嚴格的 R-競爭力的線上演算法。
所以問題是我們的線上演算法與最優離線演算法相比具有多大的競爭力。在著名的書中， Allan Borodin 和 Ran El-Yaniv 使用另一種方案來描述線上分頁情況：
有一個邪惡的對手知道你的演算法和最優的離線演算法。在每一步中，他都會嘗試請求最適合你的頁面，同時最適合離線演算法。演算法的競爭因素是你的演算法對對手的最佳離線演算法有多麼糟糕的因素。如果你想成為對手，你可以嘗試對手遊戲 （嘗試擊敗分頁策略）。
標記演算法
我們不是單獨分析每個演算法，而是檢視一個特殊的線上演算法系列，用於稱為標記演算法的分頁問題。
令σ=（σ 1 ，…，σ p ）的例項為我們的問題和 k 我們的快取記憶體大小，比σ可以分為幾個階段：
- 階段 1 是從開始到最大 k 請求不同頁面的σ的最大子序列
- 階段 i≥2 是從 pase i-1 結束到最大 k 請求不同頁面的σ的最大子序列
例如，k = 3：
標記演算法（隱式或顯式）維護頁面是否被標記。在每個階段的開始都是未標記的所有頁面。是否在標記的階段期間請求頁面。演算法是一種標記演算法，如果它永遠不會從快取中驅逐標記的頁面。這意味著在一個階段使用的頁面將不會被驅逐。
命題 1.3： LRU 和 FWF 是標記演算法。
證明： 在每個階段的開始（第一個階段除外）， FWF 具有快取未命中並清除快取。這意味著我們有 k 個空頁面。在每個階段都要求最多 k 個不同的頁面，因此在階段期間將會出現逐出的情況。所以 FWF 是一種標記演算法。
假設 LRU 不是標記演算法。然後有一個例項σ，其中 LRU 在階段 i 中被標記的頁面 x 被驅逐。讓σ 噸 在階段 I，其中 x 被逐出該請求。由於 x 被標記，因此在同一階段中 x 必須有較早的請求σt * ，因此 t * <t。T *之後，x 是最新的快取頁面，所以要在 t 序列σ得到了拆遷戶 T * + 1 ，…，σ ŧ 必須從 x 個不同的頁面請求至少 k。這意味著階段 i 已經請求至少 k + 1 個不同的頁面，這與階段定義相矛盾。因此 LRU 必須是標記演算法。
命題 1.4： 每個標記演算法都是嚴格的 k 競爭性。
證明： 設σ是尋呼問題的例項和σ的相位數。當 l = 1 則則每個標記演算法都是最優的並且最優離線演算法不能更好。
我們假設 l≥2。每個標記演算法的成本，例如，σ從上面用 l·k 限制，因為在每個階段中，標記演算法不能驅逐超過 k 個頁面而不驅逐一個標記頁面。
現在我們試圖表明，最優離線演算法在第一階段中為σ，k 驅逐了至少 k + 1-2 頁，並且除了最後一階段之外每個後續階段至少有一個。為了證明，我們定義σ的 l-2 析取子序列。子序列 i∈{1，…，l-2}從階段 i + 1 的第二個位置開始，並以階段 i + 2 的第一個位置結束。
設 x 為階段 i + 1 的第一頁。在子序列 i 的開始處，在最佳離線演算法快取記憶體中存在頁面 x 和至多 k-1 個不同頁面。在子序列中，我的 k 頁面請求與 x 不同，因此最佳離線演算法必須為每個子序列驅逐至少一頁。由於在階段 1 開始快取仍為空，因此最佳離線演算法在第一階段期間導致 k 驅逐。這表明了這一點
w A （σ）≤l⋅k≤（k + l-2）k≤OPT（σ）·k
推論 1.5： LRU 和 FWF 是嚴格 K-競爭力。
練習： 表明 FIFO 不是標記演算法，但嚴格來說是 k 競爭性的。
對於線上演算法 A 是否具有競爭力，我們稱之為 A 不具有競爭力
命題 1.6： LFU 和後進先出法是沒有競爭力。
證明： 設 l≥2 常數，k≥2 快取大小。不同的快取頁面是 nubered 1，…，k + 1。我們看看以下順序：
第一頁 1 被請求 l 次而不是第 2 頁，因此一次。最後，對頁面 k 和 k + 1 存在（l-1）交替請求。
LFU 和 LIFO 用 1-k 頁填充快取。當請求頁面 k + 1 時，頁面 k 被逐出，反之亦然。這意味著子序列（k，k + 1） l-1 的 每個請求都會驅逐一頁。此外，它們是第一次使用第 1-（k-1）頁時的 k-1 快取未命中。所以 LFU 和 LIFO 逐出大致的 k-1 + 2（l-1）頁面。
現在我們必須證明，對於每個常數τ∈ℜ和每個常數 r≤1，都存在 l
等於
為了滿足這種不相等，你必須選擇足夠大的。因此 LFU 和 LIFO 沒有競爭力。
命題 1.7： 有沒有 R-中的競爭與尋呼確定性線上演算法 [R <K 。
最後一個命題的證明相當長，並且基於 LFD 是最優離線演算法的陳述。感興趣的讀者可以在 Borodin 和 El-Yaniv 的書中查閱（參見下面的資料）。
問題是我們能否做得更好。為此，我們必須將確定性方法拋在腦後，開始隨機化我們的演算法。顯然，如果演算法是隨機的，那麼攻擊者就更難以懲罰你的演算法。
隨機分頁將在下一個例子中討論……