基于統計分析和預測的低內存進程管理算法

姜 艷，曾學文，孫 鵬

（1.中國科學院大學，北京100049；2.中國科學院聲學研究所國家網絡新媒體工程技術研究中心，北京100190）

0 引 言

嵌入式操作系統的迅猛發展，帶動了一系列新產品的繁榮，如智能手機、平板電腦、智能電視等［1，2］。低內存進程管理算法能夠在有限的嵌入式系統內存［3－5］中，駐留較多應用，從而加快應用切換速度，并避免出現內存不足現象。目前，較為經典和使用廣泛的基于低內存的進程管理主要有Linux的 OOM Killer （out of memory killer）算法［6］和Android的LMK （low memory killer）算法［7］。但這兩種算法只是根據經驗設定算法的閾值，缺乏預測機制，當系統內存的剩余量達到閾值時就開始關閉應用，使得嵌入式系統的內存沒有得到充分利用。本文對LMK算法進行改進優化，提出一種基于統計分析和預測的低內存進程管理算法 （LMK－SAP）。該算法以LMK查詢系統內存狀態的時間窗口為單位，預測下一時間窗口內各類型進程內存增量，根據系統當前可用內存支持的進程等級和進程數，選擇合適的進程關閉順序。該算法避免盲目關閉過多進程，使內存得到高效利用；在內存中保存更多應用，提高應用切換速度；同時對系統應用由于內存不足而崩潰具有一定預防作用。

1 Android的LMK算法

在傳統的Linux操作系統中，只有發生內存不足時，才會觸發OOM Killer使用一系列啟發算法挑選某個進程將其關閉，從而獲得部分內存。它具有兩個明顯的不足：①反應滯后，該算法被觸發時，系統中已經出現OOM現象，嚴重影響用戶體驗；②該算法結束的進程很有可能是用戶或／和系統不希望關閉的。為了克服這兩個缺點，LMK算法對OOM Killer算法進行了補充和優化，它為了盡量減少應用崩潰而引進低內存機制，對內存不足現象具有初步預測的能力：一是可以預先在系統低內存狀態時，判斷是否需要提前關閉部分進程，而盡量避免發生內存不足現象；二是從用戶體驗角度出發，劃分進程類型，根據低內存閾值選擇合理的進程關閉順序。

1.1 進程劃分機制

為避免盲目殺死重要進程，Android操作系統根據進程的優先級將其分為五類，分別為：前臺進程 （foreground）、可見進程 （visible）、服務進程（service）、后臺進程（background）、空進程 （empty）。

1.2 進程選擇算法

LMK算法根據當前系統剩余空閑內存所處低內存閾值而選擇殺死Bad進程，從而獲得空閑內存。Bad進程的選擇標準有兩個：oom＿adj和占用內存的大小。LMK為每一類的進程設置了lowmem＿adj和警戒內存閾值lowmem＿minfree，如以下代碼所示。同時，每個進程都有oom＿adj值。Oom＿adj和lowmem＿adj值越小的進程優先級越高，越不容易被殺死。Android Kernel定時檢查當前空閑內存是否低于某個警戒內存閾值，如果是，則根據lowmem＿minfree和lowmem＿adj確定需要殺死進程的min＿adj值；然后遍歷所有進程的oom＿adj值，找到oom＿adj值最大且大于min＿adj的進程，若找到多個，則殺死占用內存最多的進程；LMK算法流程圖如圖1所示。

static int lowmem＿adj［6］＝ ｛0，1，6，12，｝；

static size＿t lowmem＿minfree［6］＝ ｛3＊512，2＊1024，4＊1024，16＊1024，｝；

1.3 LMK算法的不足

LMK算法同樣存在不足，主要表現在兩個方面：一是關閉某個進程后，有可能仍無法滿足系統下一窗口時間內的內存需求，尤其是無法適應窗口時間內存增量較大的進程；二是LMK算法為了盡量避免出現以上問題，而預留過多空閑內存，體現為內存閾值最小值仍較大，造成內存浪費。在對LMK算法深入分析后可知，引起這兩個問題的主要原因是低內存閾值的確立缺乏依據，每次關閉的進程與系統剩余可用內存之間缺乏明確的關系。因此，本文重點研究低內存閾值的選取和動態調節。

圖1 LMK算法流程

2 LMK－SAP算法

LMK－SAP算法以時間窗口為單位記錄和預測內存增量，而窗口內的內存可能取到的數值，數量巨大，不便于統計和預測，因此LMK－SAP算法首先對內存值進行量化。實際應用的內存使用貌似雜亂無章，但其模式仍然有一定的規律可循［8］，尤其在智能手機、電視等嵌入式產品中，各應用用途固定，且用戶使用習慣相對穩定。在同一應用中，如果用戶操作流程一致，其內存使用的規律性更加明顯。因此，本文通過統計進程的內存使用歷史記錄，基于條件概率［9，10］，計算量化后每個可能出現的內存增量的概率，選取最有可能的值作為下一個時間段應用的內存增量，并根據Android的進程劃分依據，為關閉進程提供內存參考值，從待選進程中選擇占用內存最大的進程進行關閉，有效地提高了系統內存中駐留的進程數，縮短了進程切換時間。

2.1 內存窗口增量量化

根據實際嵌入式系統中為每個進程限制的內存最大值，設計量化階數J?？紤]到增量的正負問題，內存窗口增量值量化為2J種可能，分別表示為±H1、…、±Hj、…、±HJ。而一般內存分配以2的冪次方為單位，因此本文以2的冪次方對內存進行量化。H1＝28B，H2＝29B，……，HJ＝ （2J＋7）B。如，內存增量值M在［ 0，28）范圍內的j取1，以此類推，可由式 （1）計算所屬階數j

對于一般手機系統，為一個進程默認設置最大內存值為一般16MB或32MB。以32MB為例，J＝18。

2.2 內存模式分類

LMK－SAP算法的設計主要基于內存使用存在規律性這一認識。早在1995年，Wilson等人就曾指出實際應用的行為并非隨機的——它們被設計來解決實際問題，選擇的解決問題的方法對內存使用的模式具有很大的影響；他將內存使用分為3種模式：Ramps，緩慢上升；Peaks，急速上升；Plateaus，持平。如圖2所示，Ramps模式下內存增量同樣緩慢上升，Peaks模式下內存增量急速上升，Plat－eaus模式下內存增量基本為零。同時，Wilson等人指出應用內存的使用往往是上面3種模式的組合。

圖2 應用內存使用模式

2.3 進程內存增量預測

記錄某進程的前n－1個窗口內內存增量值，n＞0。預測第n個窗口的內存增量的問題，可以轉化為，在量化后的J種內存增量值中，預測出現概率最大的內存值。對該問題建立模型，其中使用的參數說明如下：

W：時間窗口，即以W時間為單位劃分時間。

Sa：表示a進程運行時，一連串特定順序排列的相鄰n個W時間的內存增加量，同樣的，若無特別強調某個進程，可簡寫為S。S可以表示為時間序列 Mi＋1，Mi＋2，Mi＋3，…，Mi＋n。其中，Mi＋k表示進程運行后第（i＋k）個W時間窗口內的內存增加量。簡單起見，以下由Mx代替Mi＋x。

從概率角度分析，當 Mn＝m（m屬于量化值H1、H2、…、Hj、…、HJ）時，使得序列 S＝（M1，M2，……，Mn）的概率最大，意味著在內存序列M1，M2，…，Mn－1的條件下，下一窗口m出現的可能性最大。因此，計算下一個窗口的內存增加量，就是計算使得P（S）最大的Mn值。根據條件概率公式，S序列出現的概率為

式中：P（M1）——進程運行后第1個W時間（實際為第i＋1個W時間，以下同理）增加的內存量為M1的概率；P（M2｜M1）是在已知第1個W時間增加的內存量為M1的前提下，第2個W時間增加的內存量為M2的概率；以次類推。不難看出，下一W時間段內Mn的出現概率取決于它前面所有內存值概率。為簡化計算量，本研究采用馬爾可夫假設［11］，假定任意W時間的內存增加量Mi的出現概率只同它前面的內存量 Mi－1有關，將式（1）S出現的概率改寫為

式（2）右側的概率值可以通過統計進程過去運行結果計算求出。記錄進程每次運行時，窗口時間內每個量化后內存增量值出現的次數，C（x），x＝±1，±2，…，±J。同時，在二維表（如圖3所示）中記錄該進程在每個量化階數間轉移次數，橫、縱坐標分別表示i時刻窗口和i＋1時刻窗口增加的內存階數，表內數據為該轉移發生的次數。

利用C（x）和圖3，可求得式（3）右側的概率值

將式 （4）和式 （5）帶入式 （3）即可求得P（S）。由于前n－1個窗口內存值已知，因此只需求解J種可能情況的P（S），選取概率最大的情況下的Mn值作為第n個窗口的預測值。

2.4 低內存閾值的確定

根據2.3節算法，可以預測得知當前進程下一窗口所需內存值，從而對前臺進程（F）、可見進程（V）、服務進程（S）、后臺進程（B）、空進程（E）分別求和計算得 Mn（F）、Mn（V）、Mn（S）、Mn（B）、Mn（E）。同時，為了防止預測值低于真實值而增加OOM發生的可能，預留部分少量內存空間Mr。因此，lowmem＿adj［6］可補充為6個取值，低內存閾值lowmem＿minfree［6］定義如下：

圖3 量化階數間轉移次數

size＿t lowmem＿minfree［6］＝｛

Mr；

Mr＋Mn（F）；

Mr＋Mn（F）＋Mn（V）；

Mr＋Mn（F）＋Mn（V）＋Mn（S）；

Mr＋Mn（F）＋Mn（V）＋Mn（S）＋Mn（B）；

Mr＋Mn（F）＋Mn（V）＋Mn（S）＋Mn（B）＋Mn（E）；

｝

2.5 LMK－SAP算法描述

LMK－SAP算法的運行過程如下：

（1）首先預測每個進程的下一時間的窗口內存增量，詳細步驟包括：

1）獲取該進程當前窗口的內存增量值M；

2）將內存增量值M按照量化表量化為Mi；

3）更新內存增量統計值，并根據之前的內存值更新轉移概率表；

4）根據式 （3）逐一計算每個可能值的概率；

5）選擇概率最大的值作為下一個窗口的內存增量預測值；

（2）分別求出各種類型進程的內存增量值；

（3）根據上一節的方法更新各種類型進程的低內存閾值；

（4）執行LMK算法，關閉相應進程。

預測算法和LMK－SAP算法的偽代碼，分別實現如下：

／＊預測進程的下一個時間窗口內的內存增量＊／

Predict＿NextMemSize（task＿struct p）

｛

／＊獲取當前時間窗口內內存大?。?/p>

current＿memsize＝Get＿memsize（p）；

／＊獲取量化值＊／

qua＿memsize＝quantized＿value（current＿memsize）；

／＊獲取進程p對應的轉移概率表＊／

tableinfo＝Get＿protabelinfo （p）；

／＊更新進程p對應的轉移概率表信息＊

Update＿protableinfo （qua＿memsize，tableinfo）；

／＊初始化概率值和預測內存值＊／

max＿pro＝0，targetM＝0

／＊逐一計算每個可能值的概率＊／

for（i＝0；i＜＝N－1；i＋＋）

｛

／＊計算Mi的概率值＊／

curr＿pro＝Cal＿probability （M ［i］，tableinfo）；

if（curr＿pro＞ max＿pro）

｛

max＿pro＝curr＿pro；

targetM＝M ［i］；

｝

｝

return targetM；

｝

／＊LMK－SAP算法實現＊／

LMK＿SAP＿Thread（）

｛

Lasttime＝0，Nowtime＝0；

while （1）

｛

／＊每隔differtime檢測一次系統的內存值，選擇需要關閉的進程＊／

if（Nowtime–Lasttime＞differtime）

｛

Lasttime＝Nowtime；

for＿each＿process （p）

｛

nextmemsize＝ Predict＿NextMemSize（p）；

／＊獲取p所對應的進程類型＊／

Ptype＝ Get＿processtype （p）；

／＊將p對應的內存增量值加入到進程類型＊／

Mn ［Ptype］＋＝nextmemsize；

｝

／＊根據Mn值和系統剩余內存計算當前系統對應的adj

值＊／

sys＿adj＝Cal＿oomadj（Mn ［］）；

／＊根據sys＿adj值選擇需要關閉的進程＊／

selected＝Select＿process （sys＿adj）；

if （selected）

close （selected）；

｝

｝

｝

3 性能仿真分析

為了驗證LMK－SAP算法的性能，設計了兩組實驗。實驗環境采用嵌入式Android機頂盒，其Android版本為Android 4.0，Linux內核版本為3.0.8，CPU 為800MHz，內存為1GBytes，LMK－SAP算法中的時間窗口為1s。

第一組實驗用以驗證本文提出的應用內存預測算法的準確性，在機頂盒上運行一個基于Web HTML5技術開發的在線視頻應用，通過隨機按鍵的方式模擬應用操作，定時監測該應用的內存占用量情況，對比算法預測出的下一個時間窗口的內存量與應用實際占用的內存量，整個實驗持續12個小時。本文采用平均誤差率來衡量預測算法的精確度，平均誤差率即為所有實驗數據點上誤差率的平均值，其計算公式如下其中n為數據的個數，p（i）為i時刻的預測值，r（i）為i時刻的實際值。圖4給出了整個實驗的一段時間結果 （約20分鐘）。

本次實驗中系統的平均誤差率為11%，從圖中不難看出，LMK－SAP的內存預測算法在絕大數據情況下能夠預測應用所需的內存量，因此可以根據該算法預測系統下一時刻的內存需求，將其作為LMK－SAP設定閾值的標準。

第二組實驗用以對比Android的LMK算法和LMKSAP算法的內存駐留應用數，內存中能夠駐留的應用數越多表明下一次切換到該應用的所需時間越短。通過在機頂盒中內置50個應用，每隔10秒鐘隨機選取一個應用運行，當新應用運行時原前臺應用進入后臺運行。圖5中給出了系統運行LMK算法和LMK－SAP算法的內存駐留應用數的對比。

在本次試驗中，LMK－SAP算法使得系統中駐留的進程數目相比于LMK算法平均提高了約56%。實驗結果表明，與LMK算法相比，LMK－SAP算法能夠提高駐留在內存中的應用數，加快應用再次加載時的速度，減少應用切換時間，從而提升多應用運行環境下的用戶體驗。

4 結束語

隨著嵌入式智能操作系統的廣泛應用，低內存進程管理作為影響系統性能重要方面，得到廣泛的重視。尤其是，LMK算法的提出，使得嵌入式智能操作系統中應用的切換速度和內存利用率有了新的突破。本文針對LMK算法的不足提出LMK－SAP算法，分析程序使用內存的特點，預測進程內存增量，動態調節內存閾值，關閉進程釋放內存。該算法避免了LMK算法中閾值選取相對固定且僅以經驗值為依據的缺點，可以保證更多應用駐留在內存中，從而提高了內存利用率并加快了應用切換速度。本文下一步的研究重點是，進一步降低算法的計算復雜度，提高進程內存增量的預測準確度。

［1］YUAN Hong，ZHENG Zhongping.A conclusion of smart TV trend and challenge ［J］.Journal of Network New Media，2012，1 （1）：4－9 （in Chinese）.［袁洪，鄧忠平.智能電視發展趨勢與挑戰 ［J］.網絡新媒體技術，2012，1 （1）：4－9.］

［2］WANG Lei，PIAO Xiwang，LI Shiqun，et al.Time performance testing of embedded real time operating system ［J］.Journal of Inner Mongolia University （Natural Science Edition），2011，42 （5）：547－551 （in Chinese）.［王蕾，樸希望，李世群，等.嵌入式實時操作系統的時間性能測試 ［J］.內蒙古大學學報 （自然科學版），2011，42 （5）：547－551.］

［3］ZHANG Lei，JIANG Haihe，CHU Yannan.Research and implementation of embedded GUI system based on uc／os－ii ［J］.Microcomputer Information，2008，24 （17）：50－52 （in Chinese）.［張磊，江海河，儲焰南.基于uc／os－ii的嵌入式GUI研究與應用 ［J］.微計算機信息，2008，24 （17）：50－52.］

［4］Hasan Y.Upper bounds for dynamic memory allocation ［J］.IEEE Transactions on Computers，2010，59 （4）：468－477.

［5］JIANG Yan，ZENG Xuewen，SUN Peng，et al.Fuzzy threshold coalescence memory algorithm for embedded real－time multimedia systems［J］.Journal of Xidian University，2012，39 （5）：174－180 （in Chinese）.［姜艷，曾學文，孫鵬，等.實時嵌入式多媒體系統模糊閾值合并內存管理算法 ［J］.西安電子科技大學學報，2012，39 （5）：174－180.］

［6］DONG Cheng.A solution on OOM （out of memory）of gallery in Android application ［D］.Shanghai：Donghua University，2012（in Chinese）.［董鋮.針對Android應用中Gallery內存溢出的解決方案 ［D］.上海：東華大學，2012.］

［7］WEI Dong，TAN Gongquan，YE Jianping.Research on android memory management ［J］.Microcontrollers ＆ Embedded Systems，2012，12 （4）：9－12 （in Chinese）.［魏棟，譚功全，葉建平.Android系統的內存管理研究 ［J］.單片機與嵌入式系統應用，2012，12 （4）：9－12.］

［8］CHI Yuanwu.Study on optimizing the embeded real－time operating system dynamic memory management ［D］.Shanghai：Shanghai Jiaotong University，2011：28－30 （in Chinese）.［池元武.嵌入式實時操作系統動態內存管理優化方案的研究［D］.上海：上海交通大學，2011：28－30.］

［9］LIU Qiang.Non－deterministic analysis for transient stability based on transient stability domain and conditional probability［J］.Automation of Electric Power Systems，2007，31 （19）：1－6（in Chinese）.［劉強.基于穩定域及條件概率的暫態穩定不確定性分析 ［J］.電力系統自動化，2007，31 （19）：1－6.］

［10］WANG Xuewu.A equivalence between occurring numbers and sums of condition probability for integer random variables sequence［J］.Mathematics in Practice and Theory，2009，39（10）：180－185 （in Chinese）.［王學武.整值隨機變量序列發生次數與條件概率和的等價性 ［J］.數學的實踐與認識，2009，39 （10）：180－185.］

［11］LIU Jiebin，SONG Maoqiang，ZHAO Fang，et al.Secondorder hidden Markov model based on context ［J］.Computer Engineering，2010，36 （10）：231－235 （in Chinese）.［劉潔彬，宋茂強，趙方，等.基于上下文的二階隱馬爾可夫模型［J］.計算機工程，2010，36 （10）：231－235.］