頁面置換演算法之Clock演算法

来源:https://www.cnblogs.com/wingsless/archive/2020/02/11/12295246.html

1.前言 緩衝池是資料庫最終的概念,資料庫可以將一部分數據頁放在記憶體中形成緩衝池,當需要一個數據頁時,首先檢查記憶體中的緩衝池是否有這個頁面,如果有則直接命中返回,沒有則從磁碟中讀取這一頁,然後緩存到記憶體並返回。 但是記憶體的價值較高,一般來說伺服器的記憶體總是小於磁碟大小的,而且記憶體不能完全分配給資料庫 ...


1.前言

緩衝池是資料庫最終的概念,資料庫可以將一部分數據頁放在記憶體中形成緩衝池,當需要一個數據頁時,首先檢查記憶體中的緩衝池是否有這個頁面,如果有則直接命中返回,沒有則從磁碟中讀取這一頁,然後緩存到記憶體並返回。

但是記憶體的價值較高,一般來說伺服器的記憶體總是小於磁碟大小的,而且記憶體不能完全分配給資料庫作為緩衝池。這就意味著資料庫基本上無法將所有的數據都緩衝到記憶體中。

當緩衝池滿後,如果還有新的頁面要被緩衝到池中,就要設計一種頁面置換的演算法,將一個舊的頁面替換成新的頁面。

一般來說我們熟悉的演算法有下麵幾種:

圖片.png

下麵逐一介紹各種演算法。

2. 最佳置換演算法

如果被替換掉的頁是以後再也不會使用的,那麼這種演算法無疑是最優秀的。因為不管什麼演算法,替換掉的頁也有可能再次被緩存,替換掉其它的頁。

但是這種演算法是無法實現的,我們不可能知道哪個頁面以後也在不會被使用。

或者我們退一步,將這個演算法改成被替換掉的頁是以後很長一段時間都不會再次被使用的,那麼這種演算法無疑也是最優秀的。

但是還是會面對一個無法實現的問題,我們還是不知道哪些頁面會在未來多長一段時間內不會被再次訪問。頁面無法確認,時間也無法確定。

雖然這種演算法無法被實現,但是可以作為一種度量,如果有一種演算法其效率最接近OPT,那麼這種演算法無疑是優秀的演算法。

3. 先進先出演算法

先進先出演算法是一種很簡單的演算法,其基本思想是形成一個隊列,最先入隊的頁面最先被逐出。我們用示意圖來模擬一下FIFO演算法:
圖片.png
我們的記憶體假設只能保存4個頁面,此時的訪問請求按照時間順序是1->2->3->4->5,那麼按照時間順序,當訪問到4號頁面時隊列正好填滿,當要訪問5號頁面時,會將最先入隊的1號頁面逐出。

這種演算法實現起來很簡單,但是從實現上來看,性能和OPT演算法差距最大。因為被替換出去的頁面很有可能是最常使用的頁面,因此這個演算法很少見出現在資料庫緩衝池管理中的。

FIFO演算法會出現一個叫做Belay異常的現象,就這個現象我們解釋如下。

我們首先定義一個4個頁面長度的隊列作為緩衝池,然後按照下麵的順序訪問:1->2->3->4->5->3->9->1->4->2->7->4->7。那麼我們按照剛纔描述的FIFO來看看訪問的過程:

訪問順序 訪問頁 記憶體隊列 是否命中
1 1 1
2 2 1,2
3 3 1,2,3
4 4 1,2,3,4
5 5 2,3,4,5
6 3 2,3,4,5
7 9 3,4,5,9
8 1 4,5,9,1
9 4 4,5,9,1
10 2 5,9,1,2
11 7 9,1,2,7
12 4 1,2,7,4
13 7 1,2,7,4

從這個表格上看到,非命中次數有9次,那麼我們將這個隊列的容量增加到5,然後再次重覆這個訪問序列,看看效果:

訪問順序 訪問頁 記憶體隊列 是否命中
1 1 1
2 2 1,2
3 3 1,2,3
4 4 1,2,3,4
5 5 1,2,3,4,5
6 3 1,2,3,4,5
7 9 2,3,4,5,9
8 1 3,4,5,9,1
9 4 3,4,5,9,1
10 2 4,5,9,1,2
11 7 5,9,1,2,7
12 4 9,1,2,7,4
13 7 9,1,2,7,4

這樣的話,非命中的次數是10次,奇怪的是增加了緩衝池的容量,非命中緩衝的數量還增加了,這種現象就叫做Belay異常。

這種演算法不應該被考慮。

4. 最近最少使用演算法

LRU演算法的思想也很簡單,實現一個鏈表(雙向鏈表),每次要緩衝新的頁面時,遍歷鏈表,選擇最近最少使用的頁面進行逐出操作。

這種演算法要求每個頁面上記錄一個上次使用時間t,程式決定逐出時,以這個時間t為準,t距離當前時間最大的,就是要被逐出的頁面。

下圖中按照1->5->2->2->6->5->4的順序訪問,記憶體和訪問示意圖如下:
圖片.png
其中最接近頂端的頁面我們認為其t最小,最接近底部,我們認為其t最大。

訪問6號頁面的時候,記憶體被填滿,下一次訪問5號頁面的時候,會將5號頁面提升到頂部,也就是t最小,之後訪問4號頁面,因為原先記憶體中沒有4號頁面,因此會選擇逐出一個頁面。此時1號頁面在底部,其t最大,因此被逐出。

那麼LRU演算法是否解決了Belay異常呢?

還是按照上一節的實驗順序,測試容量為4和5的記憶體,左側到右側,t逐漸增大:

訪問順序 訪問頁 記憶體隊列 是否命中
1 1 1
2 2 1,2
3 3 1,2,3
4 4 1,2,3,4
5 5 2,3,4,5
6 3 2,4,5,3
7 9 4,5,3,9
8 1 5,3,9,1
9 4 3,9,1,4
10 2 9,1,4,2
11 7 1,4,2,7
12 4 1,2,7,4
13 7 1,2,4,7

一共有10次未命中。增加容量到5,看一下新的情況:

訪問順序 訪問頁 記憶體隊列 是否命中
1 1 1
2 2 1,2
3 3 1,2,3
4 4 1,2,3,4
5 5 1,2,3,4,5
6 3 1,2,4,5,3
7 9 2,4,5,3,9
8 1 4,5,3,9,1
9 4 5,3,9,1,4
10 2 3,9,1,4,2
11 7 9,1,4,2,7
12 4 9,1,2,7,4
13 7 9,1,2,4,7

未命中的次數已經變成了9次,減少了一次,如果我設計的隊列中有大量的重覆,那麼這個改進應該更加明顯。

LRU演算法在InnoDB的實現中是被改進的,每次新添加進去的頁面會被放在隊列的3/8處。

無論如何,LRU演算法都被認為是最接近OPT的演算法。

5. 時鐘置換演算法

時鐘置換演算法可以認為是一種最近未使用演算法,即逐出的頁面都是最近沒有使用的那個。我們給每一個頁面設置一個標記位u,u=1表示最近有使用u=0則表示該頁面最近沒有被使用,應該被逐出。

按照1-2-3-4的順序訪問頁面,則緩衝池會以這樣的一種順序被填滿:

圖片.png

註意中間的指針,就像是時鐘的指針一樣在移動,這樣的訪問結束後,緩衝池裡現在已經被填滿了,此時如果要按照1-5的順序訪問,那麼在訪問1的時候是可以直接命中緩存返回的,但是訪問5的時候,因為緩衝池已經滿了,所以要進行一次逐出操作,其操作示意圖如下:

圖片.png

最初要經過一輪遍歷,每次遍歷到一個節點發現u=1的,將該標記位置為0,然後遍歷下一個頁面,一輪遍歷完後,發現沒有可以被逐出的頁面,則進行下一輪遍歷,這次遍歷之後發現原先1號頁面的標記位u=0,則將該頁面逐出,置換為頁面5,並將指針指向下一個頁面。

假設我們接下來會訪問2號頁面,那麼可以直接命中指針指向的頁面,並將這個頁面的標記為u置為1。

但是考慮一個問題,資料庫里逐出的頁面是要寫回磁碟的,這是一個很昂貴的操作,因此我們應該優先考慮逐出那些沒有被修改的頁面,這樣可以降低IO。

因此在時鐘置換演算法的基礎上可以做一個改進,就是增加一個標記為m,修改過標記為1,沒有修改過則標記為0。那麼u和m組成了一個元組,有四種可能,其被逐出的優先順序也不一樣:

  • (u=0, m=0) 沒有使用也沒有修改,被逐出的優先順序最高;
  • (u=1, m=0) 使用過,但是沒有修改過,優先順序第二;
  • (u=0, m=1) 沒有使用過,但是修改過,優先順序第三;
  • (u=1, m=1) 使用過也修改過,優先順序第四。

您的分享是我們最大的動力!

更多相關文章
  • btrfs,它名字挺多:B tree fs;Butter fs;Better fs 開源協議是GPL,2007年由Oracle研發 核心特性: 多物理捲支持,btrfs可由多個物理捲組成;支持RAID,可以聯機狀態下,添加,移除,修改 寫時複製(Cow:copy on write):修改前的文件內容 ...
  • 平臺預設 pmic 線性充電 sprd_2721_charge.c 命名以 pmic 型號+charge 為規則,實現平臺預設線性充電方案,文件將硬體實現和邏輯介面註冊放在同一個文件中。 probe函數: 其中來簡單介紹下sprd_2721_op的回調函數的: 其中sprdchg_chip_init ...
  • 半導體設備頭龍大廠應用材料推出新的製造系統,能夠以原子級的精準度,進行新式材料的沉積,而這些新材料是生產前述新型存儲器的關鍵。應用材料推出最先進的系統,讓這些新型存儲器能以工業級的規模穩定生產。 台積電近年來積極推動將嵌入式快快閃記憶體儲器(eFlash)製程改成MRAM及ReRAM等新型存儲器嵌入式製程 ...
  • 鼠年春節,大家都在時刻關心 2019nCoV 疫情發展,沒太多心思搞技術,就在這個時候,ARM 不聲不響搞了個大新聞,如果你登錄 ARM developer 網站,會發現 Cortex-M 家族多了一個新成員:Cortex-M55 ...
  • 為了在伺服器上跑爬蟲,以及學SegNet,研究了一圈看來linux是必學品了。在自己電腦上安裝了一個 1。官網下載iso,一個linux dvd是穩定版,選之,另一個stream版是更新更快的測試版,裡面軟體更新。 https://www.centos.org/download/ 2。刻u盤,用Wi ...
  • 該文為《 MySQL 實戰 45 講》的學習筆記,感謝查看,如有錯誤,歡迎指正 一、事務簡介 事務就是為了保證一組資料庫操作,要麼全部成功,要麼全部失敗。 事務是在引擎層實現的,也就是說並不是所有引擎都可以使用事務,MyISAM 就不支持事務,這也是為什麼會被 InnoDB 取代的原因。 說到事務, ...
  • [20200211]使用DBMS_SHARED_POOL.MARKHOT與sql_id的計算.txt--//以前寫的,使用DBMS_SHARED_POOL.MARKHOT標記熱的sql_id,這樣相同的sql語句使用不同的sql_id.--//鏈接:http://blog.itpub.net/267 ...
  • 什麼是PAGEIOLATCH_EX等待事件? 下麵我們將對PAGEIOLATCH_EX等待事件的相關資料做一個簡單的歸納、整理。關於PAGEIOLATCH_EX,官方文檔的簡單介紹如下: PAGEIOLATCH_EX: Occurs when a task is waiting on a latch... ...
一周排行
  • 最近由於疫情緊張,遂在家辦公,在領導的帶領下,學習了一下.Net Core MVC。 一,構建web應用 1.選擇c#-所有平臺-web 找到ASP.NET Core web應用程式 2.項目命名之後轉至如下界面:選擇Web應用程式(模型視圖控制器)。 Ok點擊創建,這個項目的基本框架就生成了。 二 ...
  • 本筆記摘抄自:https://www.cnblogs.com/PatrickLiu/p/7792973.html,記錄一下學習過程以備後續查用。 一、引言 今天我們要講結構型設計模式的第六個模式--享元模式,先從名字上來看,“享元”可以這樣理解--共用“單元”。單元是什麼呢?舉例說明:對於圖形而言就 ...
  • 本筆記摘抄自:https://www.cnblogs.com/PatrickLiu/p/7814004.html,記錄一下學習過程以備後續查用。 一、引言 今天我們要講結構型設計模式的第七個模式,也是結構型設計模式中的最後一個模式--代理模式。先從名字上來看,“代理”可以理解為“代替”,代替“主人” ...
  • 本筆記摘抄自:https://www.cnblogs.com/PatrickLiu/p/7837716.html,記錄一下學習過程以備後續查用。 一、引言 今天我們要講行為型設計模式的第一個模式--模板方法模式,先從名字上來看。“模板方法”理解為有一個方法的名字叫“模板方法”,也可以換個理解方法: ...
  • 本筆記摘抄自:https://www.cnblogs.com/PatrickLiu/p/7873322.html,記錄一下學習過程以備後續查用。 一、引言 今天我們要講行為型設計模式的第二個模式--命令模式,又稱為行動(Action)模式或交易(Transaction)模式,先從名字上來看。“命令模 ...
  • 前面幾章介紹了處理適量適中的圖形內容的最佳方法。通過使用幾何圖形、圖畫和路徑,可以降低2D圖形的開銷。即使正在使用複雜的具有分層效果的組合形狀和漸變畫刷,這種方法也仍然能夠正常得很好。 然而,這樣設計不適合需要渲染大量圖形元素的繪圖密集型應用程式。例如繪圖程式、演示粒子碰撞的物理模型程式或橫向卷軸形 ...
  • Dubbo的服務暴露是一個重要的特性,瞭解其機制很重要。之前有很多人寫了有關的源代碼分析,在本文中不再重新分析。官方文檔中的一篇寫的就很好,本文主要是有關內容進行補充與總結。 傳送門: "服務導出" 為什麼要服務暴露 服務暴露分為遠程暴露和本地暴露。在遠程服務暴露中會將服務信息上傳到註冊中心。這時客 ...
  • 在上一篇文章 Dubbo之服務暴露分析 中介紹了當遠程暴露時,如果有註冊中心,需要在服務暴露後再將服務註冊到註冊中心。該篇將介紹該功能的有關步驟。 註冊的起點 在 方法包含了服務導出,註冊,以及數據訂閱等邏輯。其中服務註冊先調用 方法。 可以看出,服務註冊主要包括兩部分, 獲取註冊中心實例 和 向註 ...
  • 從今天開始,將會逐步介紹關於DUbbo的有關知識。首先先簡單介紹一下DUbbo的整體概述。 概述 Dubbo是SOA(面向服務架構)服務治理方案的核心框架。用於分散式調用,其重點在於分散式的治理。 簡單的來說,可以把它分為四個角色。服務提供方(Provider)、服務消費方(Consumer)、註冊 ...
  • [TOC] python是數據分析的主要工具,它包含的數據結構和數據處理工具的設計讓python在數據分析領域變得十分快捷。它以NumPy為基礎,並對於需要類似 for迴圈 的大量數據處理的問題有非常快捷的數組處理函數。 但是pandas最擅長的領域還是在處理表格型二維以上不同數據類型數據。 基本導 ...
x