導語

在使用移動設備時，用戶同時打開多個app是很常見的。而這很容易造成移動設備的內存緊缺。在現有的方法中，無論是殺死進程（lmkd）來釋放內存還是基于壓縮算法的in-memory swap方式，都面臨用戶切換回被殺死的進程過程效率低下問題，這會影響用戶體驗。

ASAP是一種全新的swap機制，基于預取策略很好地改進了用戶體驗。其來自韓國首爾大學/谷歌等合作，發表于ATC 21。接下來本文將分成背景和動機、設計和實現和測試結果評估三個部分分別介紹ASAP誕生的背景、具體設計和效能。

背景和動機

安卓操作系統的內存管理機制

在安卓操作系統中，用戶正在使用的app被認為是在前臺（foreground），而其他啟動過但是當前沒有被使用的app則是在后臺的。

內存緊缺時，Android有個守護進程lmkd，負責殺死最不重要的進程（比如某個后臺進程），而該進程的數據自然就被釋放了。內存中有個數據集存儲被移入后臺的進程的狀態，用戶切換回被lmkd殺死的進程時，根據這個數據集恢復進程數據。除此之外還有另一種方式即使用基于壓縮算法的in-memory swap（ZRAM），下圖為安卓操作系統in-memory swap機制示意圖，其特點是需要壓縮和解壓縮匿名頁，比通過I/O將匿名頁寫入磁盤更快，但是壓縮的頁依然占用內存空間且壓縮解壓縮占用CPU時鐘周期。通常來說，lmkd會比這個機制先執行。

安卓操作系統in-memoryswap機制示意圖

為了更加直白地展示lmkd和in-memory swap、普通的swap之間的差異，此處定義兩個變量：

1） Launch Time：應用數據已經不在內存中，但是內存中依然有它的狀態信息。應用利用這些狀態信息從頭重建所有活動所需要的時間，即被lmkd殺死的進程的重啟時間；

2） Switch Time：應用數據依然在內存中。此使啟動應用所需要的時間。

根據文件頁和匿名頁是否在內存中，進而進一步分成四個不同的時間：

1） Ideal Switch Time：進程的文件頁和匿名頁都在內存中

2） Switch Time（file-backed pages in disk）：進程的文件頁在磁盤中，匿名頁在內存中

3） Switch Time（most pages not in memory）：大部分頁都不在內存中

4） Launch Time：所有頁都不在內存中

下圖展示了四種時間的差異。橫軸是用來測試的八個應用和平均值，縱軸是四種時間的值，可見使用lmkd會比理想情況滿四倍左右，應該盡可能減少lmkd的使用。

四種時間的比較

請求調頁的缺陷

內存壓力下，switch time的overhead來自于以下兩個方面：

1）解壓縮匿名頁

2）從磁盤檢索文件頁

而造成switch time大大增加的罪魁禍首就是請求調頁的低效率。下圖表示switch過程中CPU和磁盤帶寬利用率。在switch的過程中，CPU的平均利用率僅僅34.2%；，而磁盤帶寬利用率僅9.4%。究其原因， 在于解壓縮和讀磁盤操作只在一次page fault時啟動。

同時，實驗者們發現，文件頁和匿名頁的交換足跡（footprint）不一樣。文件頁更加“不變”。即同一個應用被重新啟動時，往往訪問大量相同的文件頁。原因是要訪問許多相同的庫文件。因此這給予實驗者一個啟示——為匿名頁和文件頁設計不同的預取器，利用預取來提高硬件利用率。

switch過程中CPU和磁盤帶寬利用率

設計和實現

正如前文所說，為文件頁和匿名頁設計不同的預取器。對于文件頁，利用不變的特點減少負載；對于匿名頁，則利用實時信息追蹤變化的switch footprint。其中的挑戰是，如何準確地預測footprint。

1）針對文件頁，如下圖，設計了以下五個部分：

?Offline profiling

利用前十次交換，把訪問超過八次的頁當作預取的候選頁。其結果被存儲在一個文件中。（ offline candidate table ）。

?Fault logging

記錄每次交換時的缺頁信息。存放在fault buffer中。

?Prepaging Target Management – Insertion

匹配fault buffer和offline candidate table，能匹配到，則插入prepaging target table。

?Prepaging Target Management – Extent Merging

Extent：一次切換時同一文件中被訪問的頁的集合。

兩個extent相近（小于16頁的差距），則合并。

?Prepaging Target Management – Eviction

被預取的頁只要在一次交換中沒有被用到（檢查mapcount是否為0），則從prepaging target table中移除。

文件頁的預取過程

2）針對匿名頁，如下圖，設計了如下五個部分：

?Fault logging

記錄所有匿名頁的缺頁中斷。

?Access logging

根據頁表的訪問位，記錄Prepaging Target Table和Online Candidate Table中的頁在應用切換時的訪問情況。

?Prepaging Target Management – Check & Insertion

把新的缺頁中斷加入Online Candidate Table。

?Prepaging Target Management – Promotion

若在Online Candidate Table中的頁被訪問了，則加入prepaging target table。

?Prepaging Target Management – Eviction

在prepaging target table和Online Candidate Table中的頁有個超時計時器，每次切換時計時器減小，而頁被訪問時計時器重置，超時后頁被丟棄。

匿名頁的預取過程

測試結果評估

1. 在switch latency方面，在兩種不同設備上（Pixel 4代表高端設備，Pixel 3a代表低端設備），基于baseline，平均性能提高了22.2%、28.3%。

寫延遲示意圖

2. 在預測器性能方面，平均準確率分別為匿名頁68.4%，文件頁79.3%；平均召回率分別為匿名頁60.4%，文件頁52.2%。

預測器性能示意圖

3. 在資源利用率方面，平均提高CPU利用率1.18倍（反映了預取匿名頁的影響）；平均提高I/O帶寬的使用率25.2%（反映了預取文件頁的影響）。

總結

ASAP通過合理設計預取機制，在兩種設備上，平均性能分別提高了22.2%、28.3%，取得了不錯的效果。