頁面置換演算法之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... ...
一周排行
  • 一、引言 按照專用隊列解釋: MachineName\Private$\QueueName,只針對於本機的程式才可以調用的隊列,有些情況下為了安全起見定義為私有隊列。所以剛開始的時候認為,要想訪問遠程消息隊列,只能使用公共隊列。但是後來發現,公共隊列依賴Domain Controller(域控),在 ...
  • 本文只對api介面,header請求參數進行簡單驗證,起到拋磚引玉使用,需要深入驗證,請自行擴展 項目目錄結構如圖 中間件類 using ApiMiddleware.Common.DataEnityModel; using ApiMiddleware.Common.DbContext; using ...
  • 前言:由於公司占時沒有運維,出於微服務的需要,Apollo只能先裝在windows 阿裡雲上跑起來,由於環境及網路等問題,在安裝過程中遇到很多坑,算是一個個坑填完後,最終實現。 一. java jdk環境 java jdk 1.8下載地址: https://www.oracle.com/java/t ...
  • 前言 nuget 是 .net 的常用包管理器,目前已經內置到 Visual Studio 2012 以後的版本。大多數 .net 包都托管在 nuget.org,包括 .net core 框架基礎包,得益於 .net core 的模塊化設計,很多非核心包都可以進行一定程度的獨立升級。 製作並上傳 ...
  • 簡單的介紹一下集合,通俗來講就是用來保管多個數據的方案。比如說我們是一個公司的倉庫管理,公司有一堆貨物需要管理,有同類的,有不同類的,總而言之就是很多、很亂。我們對照集合的概念對倉庫進行管理的話,那麼 數組就是將一堆貨整整齊齊的碼在倉庫的某個地方,普通列表也是如此;Set就是在倉庫里有這麼一個貨架, ...
  • 中間件分類 ASP.NET Core 中間件的配置方法可以分為以上三種,對應的Helper方法分別是:Run(), Use(), Map()。 Run(),使用Run調用中間件的時候,會直接返回一個響應,所以後續的中間件將不會被執行了。 Use(),它會對請求做一些工作或處理,例如添加一些請求的上下 ...
  • 字元串的常用操作 很好理解 字元串可以用 ' + ' 連接,或者乘一個常數重覆輸出字元串 字元串的索引操作 通過一對中括弧可以找到字元串中的某個字元 可以通過正負數雙向操作噢 用一個中括弧來實現 為什麼沒有-0??去清醒腦子想想 -0 和 0 有差嗎? 還有一個切片操作 就像切菜那樣簡單,同樣是中括 ...
  • title: Java基礎語法(3) 運算符 blog: "CSDN" data: "Java學習路線及視頻" 1.算術運算符 算術運算符的註意問題 如果對負數取模,可以把模數負號忽略不記,如:5% 2=1。 但被模數是負數則不可忽略。此外,取模運算的結果不一定總是整數。 對於除號“/”,它的整數除 ...
  • 下麵是互相轉換的代碼: 有想要瞭解更多關於python知識的請在下方評論或私信小編 ...
  • 引言 構建分散式系統並不容易。然而,人們日常所使用的應用大多基於分散式系統,在短時間內依賴於分散式系統的現狀並不會改變。ApacheZooKeeper旨在減輕構建健壯的分散式系統的任務。ZooKeeper基於 分散式計算的核心概念而設計,主要目的是給開發人員提供一套容易理解和開發的介面,從而簡化分佈 ...
x