姜 艷，曾學文，孫 鵬

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

0 引 言

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

1 Android的LMK算法

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

1.1 進程劃分機制

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

1.2 進程選擇算法

LMK算法根據(jù)當前系統(tǒng)剩余空閑內(nèi)存所處低內(nèi)存閾值而選擇殺死Bad進程，從而獲得空閑內(nèi)存。Bad進程的選擇標準有兩個：oom＿adj和占用內(nèi)存的大小。LMK為每一類的進程設(shè)置了lowmem＿adj和警戒內(nèi)存閾值lowmem＿minfree，如以下代碼所示。同時，每個進程都有oom＿adj值。Oom＿adj和lowmem＿adj值越小的進程優(yōu)先級越高，越不容易被殺死。Android Kernel定時檢查當前空閑內(nèi)存是否低于某個警戒內(nèi)存閾值，如果是，則根據(jù)lowmem＿minfree和lowmem＿adj確定需要殺死進程的min＿adj值；然后遍歷所有進程的oom＿adj值，找到oom＿adj值最大且大于min＿adj的進程，若找到多個，則殺死占用內(nèi)存最多的進程；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算法同樣存在不足，主要表現(xiàn)在兩個方面：一是關(guān)閉某個進程后，有可能仍無法滿足系統(tǒng)下一窗口時間內(nèi)的內(nèi)存需求，尤其是無法適應窗口時間內(nèi)存增量較大的進程；二是LMK算法為了盡量避免出現(xiàn)以上問題，而預留過多空閑內(nèi)存，體現(xiàn)為內(nèi)存閾值最小值仍較大，造成內(nèi)存浪費。在對LMK算法深入分析后可知，引起這兩個問題的主要原因是低內(nèi)存閾值的確立缺乏依據(jù)，每次關(guān)閉的進程與系統(tǒng)剩余可用內(nèi)存之間缺乏明確的關(guān)系。因此，本文重點研究低內(nèi)存閾值的選取和動態(tài)調(diào)節(jié)。

圖1 LMK算法流程

2 LMK－SAP算法

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

2.1 內(nèi)存窗口增量量化

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

對于一般手機系統(tǒng)，為一個進程默認設(shè)置最大內(nèi)存值為一般16MB或32MB。以32MB為例，J＝18。

2.2 內(nèi)存模式分類

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

圖2 應用內(nèi)存使用模式

2.3 進程內(nèi)存增量預測

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

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

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

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

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

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

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

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

2.4 低內(nèi)存閾值的確定

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

圖3 量化階數(shù)間轉(zhuǎn)移次數(shù)

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）首先預測每個進程的下一時間的窗口內(nèi)存增量，詳細步驟包括：

1）獲取該進程當前窗口的內(nèi)存增量值M；

2）將內(nèi)存增量值M按照量化表量化為Mi；

3）更新內(nèi)存增量統(tǒng)計值，并根據(jù)之前的內(nèi)存值更新轉(zhuǎn)移概率表；

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

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

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

（3）根據(jù)上一節(jié)的方法更新各種類型進程的低內(nèi)存閾值；

（4）執(zhí)行LMK算法，關(guān)閉相應進程。

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

／＊預測進程的下一個時間窗口內(nèi)的內(nèi)存增量＊／

Predict＿NextMemSize（task＿struct p）

｛

／＊獲取當前時間窗口內(nèi)內(nèi)存大?。?/p>

current＿memsize＝Get＿memsize（p）；

／＊獲取量化值＊／

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

／＊獲取進程p對應的轉(zhuǎn)移概率表＊／

tableinfo＝Get＿protabelinfo （p）；

／＊更新進程p對應的轉(zhuǎn)移概率表信息＊

Update＿protableinfo （qua＿memsize，tableinfo）；

／＊初始化概率值和預測內(nèi)存值＊／

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算法實現(xiàn)＊／

LMK＿SAP＿Thread（）

｛

Lasttime＝0，Nowtime＝0；

while （1）

｛

／＊每隔differtime檢測一次系統(tǒng)的內(nèi)存值，選擇需要關(guān)閉的進程＊／

if（Nowtime–Lasttime＞differtime）

｛

Lasttime＝Nowtime；

for＿each＿process （p）

｛

nextmemsize＝ Predict＿NextMemSize（p）；

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

Ptype＝ Get＿processtype （p）；

／＊將p對應的內(nèi)存增量值加入到進程類型＊／

Mn ［Ptype］＋＝nextmemsize；

｝

／＊根據(jù)Mn值和系統(tǒng)剩余內(nèi)存計算當前系統(tǒng)對應的adj

值＊／

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

／＊根據(jù)sys＿adj值選擇需要關(guān)閉的進程＊／

selected＝Select＿process （sys＿adj）；

if （selected）

close （selected）；

｝

｝

｝

3 性能仿真分析

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

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

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

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

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

4 結(jié)束語

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

［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）.［袁洪，鄧忠平.智能電視發(fā)展趨勢與挑戰(zhàn) ［J］.網(wǎng)絡新媒體技術(shù)，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）.［王蕾，樸希望，李世群，等.嵌入式實時操作系統(tǒng)的時間性能測試 ［J］.內(nèi)蒙古大學學報 （自然科學版），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）.［姜艷，曾學文，孫鵬，等.實時嵌入式多媒體系統(tǒng)模糊閾值合并內(nèi)存管理算法 ［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內(nèi)存溢出的解決方案 ［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系統(tǒng)的內(nèi)存管理研究 ［J］.單片機與嵌入式系統(tǒng)應用，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）.［池元武.嵌入式實時操作系統(tǒng)動態(tài)內(nèi)存管理優(yōu)化方案的研究［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）.［劉強.基于穩(wěn)定域及條件概率的暫態(tài)穩(wěn)定不確定性分析 ［J］.電力系統(tǒng)自動化，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）.［王學武.整值隨機變量序列發(fā)生次數(shù)與條件概率和的等價性 ［J］.數(shù)學的實踐與認識，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.］