圖解 | Linux內(nèi)存回收之LRU算法

內(nèi)存 是操作系統(tǒng)非常重要的資源，操作系統(tǒng)要運(yùn)行一個(gè)程序，必須先把程序代碼段的指令和數(shù)據(jù)段的變量從硬盤加載到內(nèi)存中，然后才能被運(yùn)行。如下圖所示：

但內(nèi)存資源是有限的，隨著系統(tǒng)中運(yùn)行的進(jìn)程越來越多，系統(tǒng)中可用的內(nèi)存就會越來越少。那么，當(dāng)可用內(nèi)存不足時(shí)，Linux 內(nèi)核是怎么處理的呢？

本文將會介紹，當(dāng)可用內(nèi)存不足時(shí)，Linux 內(nèi)核的處理方式。

一、內(nèi)存不足的處理方式

我們思考一下，當(dāng)系統(tǒng)的可用內(nèi)存不足時(shí)，進(jìn)程繼續(xù)申請內(nèi)存會發(fā)生什么事情？

當(dāng)系統(tǒng)的可用內(nèi)存不足時(shí)，內(nèi)核為了保證進(jìn)程有足夠的內(nèi)存可用，將會對內(nèi)存進(jìn)行回收工作。內(nèi)存回收工作主要包括以下幾個(gè)步驟：

• 內(nèi)核為了加速某些操作（如文件 I/O），會對操作的結(jié)果進(jìn)行緩存（如文件頁緩存），而緩存使用的內(nèi)存是可以被回收的。所以，當(dāng)可用內(nèi)存不足時(shí)，首先會回收內(nèi)核中的緩存。
• 如果回收內(nèi)核緩存后，系統(tǒng)的可用內(nèi)存仍然處于不足。那么，內(nèi)核將會觸發(fā) swap 機(jī)制。swap 機(jī)制會將某些進(jìn)程所占用的內(nèi)存交換（寫入）到硬盤中，然后釋放這些內(nèi)存，從而讓系統(tǒng)有更多可用的內(nèi)存。本文將會重點(diǎn)介紹 swap 機(jī)制。
• 如果觸發(fā) swap 機(jī)制后，系統(tǒng)的可用內(nèi)存仍不能滿足系統(tǒng)需求，那么將會觸發(fā) OOM（Out Of Memory） 機(jī)制。OOM 機(jī)制將會挑選一些進(jìn)程，然后將這些進(jìn)程殺死來，從而獲取更多可用內(nèi)存。
  
  

  

由于回收內(nèi)存的方式有三種，所以本文重點(diǎn)以 swap 機(jī)制作為分析對象，來介紹當(dāng)內(nèi)存不足時(shí)，內(nèi)核是怎么進(jìn)行內(nèi)存回收工作的。

二、swap機(jī)制原理

在分析 swap 機(jī)制的實(shí)現(xiàn)前，我們先來介紹一下 swap 機(jī)制的原理。

本文使用 Linux-2.6.23 版本內(nèi)核。

swap 這個(gè)單詞是 交換 的意思，顧名思義就是把某些進(jìn)程所占用的內(nèi)存交換（寫入）到硬盤，然后把內(nèi)存釋放給操作系統(tǒng)，這樣操作系統(tǒng)就有更多可用的內(nèi)存。如下圖所示：

由于 swap 機(jī)制的本質(zhì)是將進(jìn)程所占用的內(nèi)存寫入到硬盤中，然后釋放這些內(nèi)存。那么，就涉及到應(yīng)該將哪些進(jìn)程的內(nèi)存交換到硬盤中。

每個(gè)進(jìn)程都不希望自己占用的內(nèi)存被交換到硬盤中，因?yàn)閮?nèi)存被交換到硬盤后，如果進(jìn)程要使用到這些內(nèi)存時(shí)，必須先將這些內(nèi)存從硬盤中加載到內(nèi)存中，才能繼續(xù)使用，這樣進(jìn)程的性能將會大打折扣。正因?yàn)檫@個(gè)原因，內(nèi)核必須提供一種最優(yōu)的方案來挑選一些內(nèi)存交換到硬盤，并且對進(jìn)程性能的影響降到最小。

由于進(jìn)程的內(nèi)存空間分為多個(gè)段，如 代碼段、數(shù)據(jù)段、mmap段、堆段 和 棧段 等。那么，哪些段的內(nèi)存會被交換到硬盤中呢？

答案就是：所有段的內(nèi)存都有可能交換到硬盤。不過對于 代碼段 和 mmap段 這些與文件有映射關(guān)系的內(nèi)存區(qū)，只需要將數(shù)據(jù)寫回到文件即可（由于代碼段的內(nèi)容不會改變，所以不用進(jìn)行回寫）。

而對于 數(shù)據(jù)段、堆段 和 棧段 這些段中的內(nèi)存頁，由于沒有與文件進(jìn)行映射（稱為 匿名內(nèi)存頁），所以內(nèi)核必須提供一個(gè)文件（或硬盤分區(qū)）來存儲這些內(nèi)存頁的數(shù)據(jù)，這個(gè)文件（或硬盤分區(qū)）被稱為 交換分區(qū)。

從上面的分析可以得出兩個(gè)重要的信息：

• 匿名內(nèi)存頁：沒有與任何文件進(jìn)行映射的內(nèi)存頁。
• 交換分區(qū)：用于存儲匿名內(nèi)存頁數(shù)據(jù)的文件或硬盤分區(qū)。

下面主要介紹當(dāng)系統(tǒng)內(nèi)存不足時(shí)，內(nèi)核是怎樣將進(jìn)程的 匿名內(nèi)存頁 寫入到 交換分區(qū) 中，并且回收這些 匿名內(nèi)存頁 的。

1. LRU 內(nèi)存淘汰算法

當(dāng)系統(tǒng)內(nèi)存不足，并且觸發(fā) swap機(jī)制 時(shí)，內(nèi)核應(yīng)該選擇哪些 匿名內(nèi)存頁 寫入到 交換分區(qū) 中呢？如果隨機(jī)選擇一些 匿名內(nèi)存頁 寫入到 交換分區(qū)，就有可能出現(xiàn)如下問題：

把某個(gè)進(jìn)程的 匿名內(nèi)存頁 寫入到 交換分區(qū) 后，進(jìn)程又馬上訪問這個(gè)內(nèi)存頁，從而又要把這個(gè)內(nèi)存頁從 交換分區(qū) 中讀入到內(nèi)存中。這樣只會增加系統(tǒng)的負(fù)荷，并且不能解決系統(tǒng)內(nèi)存不足的問題。

為了解決這個(gè)問題，Linux 內(nèi)核引入了 LRU內(nèi)存淘汰算法，用過 Memcached 或者 Redis 的同學(xué)應(yīng)該都了解過 LRU算法。當(dāng)系統(tǒng)內(nèi)存不足時(shí)，Memcached 和 Redis 都是使用 LRU算法 來淘汰內(nèi)存的。

LRU（Least Recently Used） 中文翻譯是 最近最少使用 的意思，其原理就是：當(dāng)內(nèi)存不足時(shí)，淘汰系統(tǒng)中最少使用的內(nèi)存，這樣對系統(tǒng)性能的損耗是最小的。

為了實(shí)現(xiàn) LRU算法，內(nèi)核維護(hù)了兩個(gè)雙向鏈表：active_list 和 inactive_list。下面介紹下這兩個(gè)鏈表的作用：

• active_list：活躍內(nèi)存頁鏈表。也就是說進(jìn)程會經(jīng)常訪問這個(gè)鏈表中的內(nèi)存頁，所以進(jìn)行內(nèi)存淘汰時(shí)，不應(yīng)該淘汰這個(gè)鏈表中的內(nèi)存頁。
• inactive_list：不活躍內(nèi)存頁鏈表。也就是說進(jìn)程很少會訪問這個(gè)鏈表中的內(nèi)存頁，所以進(jìn)行內(nèi)存淘汰時(shí)，主要淘汰這個(gè)鏈表中的內(nèi)存頁。

在 Linux 內(nèi)核中，每個(gè) 內(nèi)存區(qū)(zone) 都會維護(hù)著一個(gè) active_list 和一個(gè) inactive_list。內(nèi)存區(qū) 是內(nèi)存管理中的一個(gè)對象，為了描述更加清晰，我們暫時(shí)當(dāng)成內(nèi)核中只有一個(gè)內(nèi)存區(qū)，也就是說暫時(shí)認(rèn)為內(nèi)核中只維護(hù)著一個(gè) active_list 和一個(gè) inactive_list。如下圖所示：

另外，每個(gè)內(nèi)存頁都有個(gè) PG_referenced 的標(biāo)志位，表示此內(nèi)存頁是否被訪問過，這個(gè)標(biāo)志位在內(nèi)存回收過程中起著至關(guān)重要的作用。

當(dāng)某個(gè)進(jìn)程申請一個(gè)匿名內(nèi)存頁時(shí)，內(nèi)核會把這個(gè)內(nèi)存頁添加到 活躍內(nèi)存頁鏈表(active_list) 中，并且將 PG_referenced 標(biāo)志位設(shè)置為 0。如下圖所示：

而當(dāng)某個(gè)匿名內(nèi)存頁被進(jìn)程訪問時(shí)，根據(jù)內(nèi)存頁所在的 LRU 鏈表作不同的操作：

• 如果內(nèi)存頁原來處于 活躍鏈表 中，那么就會把此內(nèi)存頁的 PG_referenced 設(shè)置為 1。
• 如果內(nèi)存頁原來處于 非活躍鏈表 中，并且 PG_referenced 為 0。那么將內(nèi)存頁的 PG_referenced 標(biāo)志位設(shè)置為 1。
• 如果內(nèi)存頁原來處于 非活躍鏈表 中，并且 PG_referenced 為 1。那么將會把內(nèi)存頁從 非活躍鏈表 移動到 活躍鏈表，并且將 PG_referenced 設(shè)置為 0。

下圖展示了上述各種情況的流轉(zhuǎn)過程：

而當(dāng)系統(tǒng)內(nèi)存不足時(shí)，需要進(jìn)行內(nèi)存淘汰過程。內(nèi)存頁淘汰過程與上述過程剛好相反，下面介紹一下內(nèi)存頁淘汰的過程。

內(nèi)存淘汰時(shí)，只能從 非活躍鏈表 中進(jìn)行淘汰，淘汰過程如下：

• 從 非活躍鏈表 的尾部開始進(jìn)行內(nèi)存淘汰，如果內(nèi)存頁的 PG_referenced 標(biāo)志位為 1 時(shí)，將跳過此內(nèi)存頁，并且將此內(nèi)存頁的 PG_referenced 標(biāo)志位設(shè)置為 0。
• 如果內(nèi)存頁的 PG_referenced 標(biāo)志位為 0 時(shí)，那么將此內(nèi)存頁寫入到 交換分區(qū) 中，并且將所有與此內(nèi)存頁的映射解除綁定，然后釋放此內(nèi)存頁。

上述過程是由 shrink_inactive_list 函數(shù)完成，如下圖所示：

另外，處于 活躍鏈表 的內(nèi)存頁也有衰退的過程，衰退過程如下：

• 如果內(nèi)存頁的 PG_referenced 標(biāo)志位為 1，那么衰退過程將會把此內(nèi)存頁的 PG_referenced 標(biāo)志位設(shè)置為 0。
• 如果內(nèi)存頁的 PG_referenced 標(biāo)志位為 0，那么衰退過程將會把此內(nèi)存頁移動到 非活躍鏈表 中。

上述過程是由 shrink_active_list 函數(shù)完成，如下圖所示：

2. LRU算法狀態(tài)流轉(zhuǎn)

我們最后以一張狀態(tài)流轉(zhuǎn)圖來描述 LRU 算法的過程：

三、總結(jié)

本文主要介紹了 Linux 內(nèi)核內(nèi)存回收過程中使用的 LRU 算法的原理，在下一篇文章中，我們將會介紹 Linux 內(nèi)核是如何實(shí)現(xiàn)內(nèi)存回收的，有興趣的敬請期待。