基于资源预测的智能终端资源缓存算法

徐 超,曾学文,郭志川

(1.中国科学院声学研究所国家网络新媒体工程技术研究中心,北京100190;2.中国科学院大学,北京100049)

基于资源预测的智能终端资源缓存算法

徐 超1,2,曾学文1,郭志川1

(1.中国科学院声学研究所国家网络新媒体工程技术研究中心,北京100190;2.中国科学院大学,北京100049)

针对智能电视终端应用间资源竞争导致的系统性能下降问题,基于资源消耗预测,提出一种智能终端资源缓存算法。根据系统记录的各应用程序的资源消耗统计数据,应用Markov模型预测下一时间段可能出现的资源瓶颈和应用的资源状态,利用应用的资源状态动态调整应用权重,并以最小化应用切换时间为目标,将资源缓存问题转化为多维多选择背包问题,采用轻量级的启发式算法求解资源缓存问题。仿真实验结果表明,在智能终端中该算法对于资源消耗的预测精确度比其他算法提高5.4%,而应用响应时间缩短约45%。

智能电视终端;资源预测;Markov模型;资源缓存算法;多维多选择背包问题;启发式算法

1 概述

在智能终端系统中,应用程序(以下简称应用)的正常运行需要多种资源,资源主要包括:CPU,内存,内存I/O带宽,存储容量,磁盘I/O带宽,网络带宽,解码器,解复用器,解调器等。每个终端上拥有的资源有限,难以支撑大量应用同时运行,多应用对资源的竞争将导致系统的用户体验下降。在移动设备操作系统中,应用一般退出时不关闭而转为后台运行状态,操作系统对其资源进行缓存,以提高应用重新启动时的资源加载速度。如何提高资源缓存算法的效率,缩短应用的切换时间,成为智能终端系统亟待解决的问题。

学术界一般采用降载算法［1-2］或负载均衡算法［3］缓解资源瓶颈现象。这些方法的缺点是:(1)不能判断出现资源瓶颈现象的根本原因,即没有采用合适模型描述资源状态;(2)算法反映均滞后于系统实际状态,将导致系统的QoS下降。在非线性预测

领域,应用较多的算法包括人工神经网络、支持向量机等［4］,而资源消耗预测一般采用线性预测算法,在资源状态频繁切换的场景,基于回归的预测算法［5］性能劣于基于Markov模型的预测算法。基于Markov模型的预测算法分为2类:(1)分别对每种资源建立Markov模型进行预测［6-8］;(2)采用聚类算法将应用对所有资源的消耗数据聚类为一种资源状态,再对资源状态建立Markov模型进行预测［9］。

综合考虑预测精确度和系统开销,本文采用Markov模型来预测资源消耗。现有研究具有如下缺点:监测的资源类型局限于CPU、内存、磁盘容量、网络带宽等资源,但是对智能终端上特有的设备资源,如解码器、解复用器、解调器等缺乏恰当的监测机制。并且,针对智能电视终端的应用特点,资源预测算法没有做相应的优化。建模成Markov模型须满足以下条件:(1)状态构成一阶Markov链,即当前状态仅与前一状态有关,与之前状态无关;(2)状态的转移是时齐的,即状态与具体时间数值无关。智能终端中应用的资源消耗状态的具备这些特性。

本文算法由资源预测算法和资源缓存算法两部分构成。资源预测算法根据应用的资源消耗历史数据,预测某一时间段内可能出现的资源瓶颈和资源消耗状态;资源缓存算法通过优先缓存资源消耗增量较大应用的资源,防止产生资源瓶颈现象,缩短应用间的切换时间。

2 基于统计分析的资源消耗预测算法

本文采用基于资源消耗状态的Markov模型来预测应用的资源消耗。预测下一个时间段内的资源消耗问题,可以转化为,在离散化的若干种资源消耗状态中,预测出现概率最大的资源消耗状态。Markov模型的输入为资源管理组件采集的资源消耗数据,输出为预测的下一时间窗口的资源消耗状态。资源消耗预测算法分为数据采集、获取资源消耗状态、构造状态转移矩阵、资源消耗预测4个步骤。

2.1 数据采集

对于CPU和内存消耗数据,采用top工具获取当前时刻所有应用的CPU和内存占用,之后从系统日志中解析出每个应用进程的CPU和内存占用。对于网络带宽的消耗数据,采用开源工具iftop监测应用占用的端口,之后从日志中解析每个应用进程的网络带宽占用。设备资源一般在终端系统BSP层提供封装,其资源占用信息不能从内核中获取,因此,在智能电视操作系统中,由资源管理模块进行设备资源记录和分析。

2.2 资源消耗状态的获取

对于连续性的资源如CPU资源,首先将其离散化为若干区间。如资源状态数N=10,则离散化为［0,0.1),［0.1,0.2),…,［0.9,1］,每个区间分别表示一个CPU资源状态,即s1=［0,0.1),s2=［0.1, 0.2),…,s10=［0.9,1］。状态空间S={s1,s2,…,sN}。在离散时间点t,采集系统中每个应用的CPU资源消耗数据,得到应用的资源消耗状态序列X:

X=(x0,x1,…,xt),t=0,1,…

2.3 状态转移矩阵的构造

资源消耗状态序列X是一个有限状态Markov链,属于离散时间随机过程。假设由N个资源状态组成{s1,s2,…,sN},各状态的出现概率可用N×N的转移概率矩阵表征。转移矩阵由系统日志中若干时间窗口中的资源消耗数据构造。

由有限状态齐次Markov链的性质,有:

转移概率pab(h,t)=P{xt=sb|xh=sa},满足pab(h,t)≥0,∑bpab(h,t)=1,其中1≤h≤t。定义一步转移概率pab(t)=P{xt=sb|xt-1=sa}。由于资源消耗的转移概率与具体时刻t无关,即系统为齐次Markov链,一步转移概率可以简写为pab(t)=pab。求解一步转移概率矩阵的方法如下:应用的进程运行时,将窗口时间内每次资源消耗状态转移出现的次数记录于资源消耗矩阵C中,即每次出现xt-1=sa且xt=sb时,令cab=cab+1,由此得到C:

其中,1≤a;b≤N。

应用资源消耗状态的转移概率构成强联通的有向图,保证了Markov链的稳定性。

2.4 预测值的计算

由查普曼-科尔莫戈罗夫等式,由当前时间的资源消耗状态的分布向量和式(2),求得t时刻应用资源的分布向量:

由式(3),可求得每种资源t时刻后资源消耗增量的期望。应用所需的m种资源构成一个m维的资源消耗增量向量I=(xt1,xt2,…,xtm)。如果资源消耗增量向量I的模较大,认为该应用在t时刻具有较大概率发生状态切换,即具有较大概率从后台切换到前台。

3 资源缓存算法

与CPU、内存等资源不同,电视设备资源如解码器、解复用器,其初始化和释放都涉及多层接口的调用,带来较大的系统开销,切换时间也较长,甚至高达秒级。在系统剩余资源不多时,如果启动消耗资源较多的应用,资源抢占将触发系统的进程调度策略,这是十分耗时的操作。这种情况下系统将按照进程优先级选择性关闭进程,频繁的调度导致系统响应速度变慢,用户体验下降。

因此,在智能电视系统中,当进行应用切换或系统资源过载时,采用资源缓存算法对系统缓存资源进行处理［10］。资源缓存算法的思想是在系统资源的约束内,尽可能多地缓存后台应用的资源状态,将有限的空闲资源在后台应用之类进行合理分配,缩短应用间的切换时间。其工程实现方法是引入资源管理组件,监控系统中的后台应用的资源缓存状态信息,同时隔离应用层资源获取接口和BSP层资源接口。资源管理组件对上为应用层提供统一的资源管理和访问API,对下实现对物理资源的访问。

假设系统中有n个应用,应用集合为{t1,t2,…,ti,…,tn},系统中有m种资源,资源集合为{r1,r2,…,rj,…,rm}。对于智能电视应用来说,某些资源间存在约束,如网络视频播放业务,播放特定码率视频流需要固定等级的网络带宽、解码器、解复用器、CPU和内存。因此,缓存资源必须以特定资源组为单位,应用的资源缓存状态为单种资源组合之集合的子集。假设应用共有l个缓存状态,为{g1,g2,…,gk,…,gl},缓存状态从g1到gl缓存资源的数量递增,g1表示不缓存任何资源,gl表示缓存全部资源。

应用i转入后台之后,如果其拥有的资源j被释放,在其回到前台时,必须重新初始化资源j。不同资源的初始化时间不同,应用的切换时间则为所有资源初始化时间之和。

资源缓存问题指的是求解系统下一时刻内全部资源的最优缓存方案。其优化目标为最小化应用切换时间的期望,可建模为以下问题:

文献［10］算法的缺点是,仅仅最优化的系统中应用切换时间的加权和,但未根据当前的资源消耗估计资源消耗变化趋势,导致权重较小的应用缺乏资源保障,同时应用间权重的确定成为关键而困难的问题。

本文算法的思路是,根据应用当前时刻的资源消耗,估计应用下一时刻的资源消耗,增加资源消耗增量较大的应用权重,优先缓存此类应用的资源,达到优化应用切换时间的目标。

应用从后台切换到前台时,其资源消耗将增加,增量大小则取决于系统的缓存资源量。消耗增量越大,则发生应用切换的概率越大。设资源增量向量为Ri,Ri=(Δri1,Δri2,…,Δrim),由Ri模的大小可以表征应用切换的概率,代入式(5),得:

此时,优化问题转化为一个多维多选择背包问题(MMKP)［11］。采用启发式解法,可快速求得次优解:启发式解法通常首先由贪心策略得到初始可行解,再基于初始解迭代调整找到更好的可行解。如M-HEU［11］可在多项式时间内求得最优解约96%值的次优解,C-HEU［12］基于凸包构建搜索空间,可在线性时间内求得90%以上最优值的次优解。

为减小系统的开销,本文在C-HEU算法基础上设计资源缓存算法。定义惩罚向量q=(q1,q2,…,qm),惩罚向量将m维资源向量转化为一维。受惩后的资源向量R=(r1q1,r2q2,…,rjqj,…,rmqm)。此时应用的资源Ri和切换时间Tik构成二维平面。

算法迭代3次后,即可达到较好的寻优结果［12］。迭代开始前,由式(6)初始化惩罚向量:

其中,rsum为各应用当前资源向量之和;rsumj表示rsum中资源j的分量大小,以下Rj和R′j含义相同。

惩罚向量的更新公式为:

搜索开始后,对于k=1,2,…,l,按各个点形成的凸包边界与R轴夹角大小进行排序。再按降序依次是否满足资源约束(伪代码中的check_ point函数)。整体算法伪代码如下:

资源缓存算法

算法第3行～第5行、第29行～第31行仅需m次计算。18行排序的时间复杂度为O(nllgn)。最坏情况下,每个应用有l个缓存状态,均消耗m种资源,每个应用的12行复杂度为O(lm),15行复杂度为O(llgl)［12］,第12行～第15行复杂度为O(nlm+nllgl)。因此,资源缓存算法总体最坏时间复杂度为O(nml+nllgl+nllgn)。

4 仿真实验结果与分析

仿真实验采用的工具为Matlab 7.0,仿真实验平台的配置为Intel Core i5-2400 3.10 GHz,RAM 4 GB。采用MATLAB中tic/toc命令计算算法执行时间。应用集包括15个常见周期型应用,应用类型涵盖音视频播放、音频播放、PVR、网页浏览、文件下载等。每个应用均有5个资源缓存状态。

4.1 资源消耗预测精确度

图1 预测精确度

4.2 应用切换时间

进行20次重复实验,每次从应用集中随机选择

一个应用运行,此应用进入前台状态,其他应用进入后台状态。实验分为3组,第1组不采用任何资源缓存算法,第2组采用文献［10］的资源缓存算法;第2组采用本文资源缓存算法。由图2所示,实验中无资源缓存时平均响应时间为630 ms,文献［10］算法平均响应时间为456 ms,本文算法的平均响应时间为253 ms。本文算法通过预测应用的资源消耗状态,缓存部分资源,显著缩短某些应用的响应时间。

图2 应用切换时间

4.3 资源缓存算法的计算时间

资源缓存算法的计算时间随运行的应用数变化的仿真结果如图3所示。精确解法如分支限界法(BBLP)的时间复杂度为指数级,M-HEU时间复杂度为O(n2ml2),其中,n为应用数;m为资源数;l为应用的资源缓存状态数。本文资源缓存算法的时间复杂度对于应用数n是O(nlgn)级算法,显著低于M-HEU。

图3 资源缓存算法耗时

5 结束语

本文提出一种基于资源消耗预测的智能终端资源缓存算法,根据资源消耗的历史统计数据,利用Markov模型预测应用切换概率,动态调整应用权重,并采用轻量级的资源缓存算法求解资源缓存问题,动态最小化应用切换时间,有效解决了智能电视终端中资源瓶颈现象导致的应用响应缓慢问题。实验结果表明,本文算法的预测精确度比其他算法提高5.4%,而应用响应时间缩短了约45%,算法本身复杂度低,带来较小的额外开销。下一步的研究重点为在各种类型的应用和业务场景中,进一步提高预测精确度。

［1]Tu Yicheng,Liu Song,Prabhakar S,et al.Load Shedding in Stream Databases:A Control-basedApproach［C］// Proceedings of the 32nd International Conference on Very Large Data Bases.Seoul,Korea:ACM Press,2006:787-798.

［2]Tatbul N,Cetintemel U,Zdonik S,et al.Load Shedding in a Data Stream Manager［C］//Proceedings of the 29th International Conference on Very Large Data Bases.Berlin,Germany:ACM Press,2003:309-320.

［3]Xing Ying,Zdonik S B,Hwang J H.Dynamic Load Distribution in the Borealis Stream Processor［C］// Proceedings of the 21st International Conference on Data Engineering.Tokyo,Japan:IEEE Press,2005.

［4]Sapankevych N I,SankarR.TimeSeriesPrediction Using Support Vector Machine:A Survey［J］.IEEE Computational Intelligence Magazine,2009,4(2): 24-38.

［5]Wood T,Cherkasova L,Ozonat K,et al.Profiling and ModelingResourceUsageofVirtualizedApplications［C］//Proceedings of the 9th ACM International Conference on Middleware.Leuven,Belgium:ACM Press,2008:366-387.

［6]Mallick S,Hains G,Deme C S.A Resource Prediction Model for Virtualization Servers［C］//Proceedings of International Conference on High Performance Computing and Simulation.Palermo,Italy:IEEE Press,2012: 667-671.

［7]Shi Lili,Shoubao Y,Liangmin G,et al.A Markov Chain Based Resource Prediction in Computational Grid［C］// Proceedings of the 4th International Conference on FrontierofComputerScienceandTechnology.Washington D.C.,USA:IEEE Press,2009:119-124.

［8]Gong Zhenhuan,Gu Xiaohui,Wilkes J.Press:Predictive Elastic Resource Scaling for Cloud Systems［C］// Proceedings of the 6th International Conference on Network and Service Management.Ontario,Canada: IEEE Press,2010:9-16.

［9]Gu Xiaohui,Wang Haixun.Online Anomaly Prediction for Robust Cluster Systems［C］//Proceedings of the 25th International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2009:1000-1011.

［10]姜 艳.面向体验的智能电视多应用运行优化关键技术研究［D］.北京:中国科学院大学,2013.

［11]Akbar M M,Manning E G,Shoja G C,et al.Heuristic SolutionsfortheMultiple-choiceMulti-dimension Knapsack Problem［C］//Proceedings of International Conference on Computational Science.London,UK: Springer,2001:659-668.

［12]Mostofa A M,Sohel R M,Kaykobad M,et al.Solving the Multidimensional Multiple-choice Knapsack Problem by ConstructingConvexHulls［J］.Computers& Operations Research,2006,33(5):1259-1273.

编辑 顾逸斐

Smart Terminal Resource Cache Algorithm Based on Resource Prediction

XU Chao1,2,ZENG Xuewen1,GUO Zhichuan1
(1.National Network New Media Engineering Research Center,Institute of Acoustics, Chinese Academy of Sciences,Beijing 100190,China;2.University of Chinese Academy of Sciences,Beijing 100049,China)

In order to solve the problem of the performance degradation caused by the resource competition among the applications in smart TV,this paper presents a resource usage prediction based resource cache algorithm.The applications’resource consumption data is recorded and the resource state and resource bottleneck of the next time interval are predicted by Markov model.The weight of each application is adjusted dynamically and the resource cache problem is converted to multidimensional multiple-choice knapsack problem to minimize the switch time of the application.A lightweight heuristic solution algorithm with lower time complicity is presented.Simulation results show that the precision of the resource usage prediction of the algorithm is superior to others by about 5.4%,and the switch time of the application is reduced by about 45%.

smart TV terminal;resource prediction;Markov model;resource cache algorithm;multidimensional multiple-choice knapsack problem;heuristic algorithm

徐 超,曾学文,郭志川.基于资源预测的智能终端资源缓存算法［J］.计算机工程,2015,41(3):59-63.

英文引用格式:Xu Chao,Zeng Xuewen,Guo Zhichuan.Smart Terminal Resource Cache Algorithm Based on Resource Prediction［J］.Computer Engineering,2015,41(3):59-63.

1000-3428(2015)03-0059-05

:A

:TP301.6

10.3969/j.issn.1000-3428.2015.03.011

国家科技支撑计划基金资助项目“电视商务综合体新业态运营支撑系统开发”(2012BAH73F01);中国科学院先导专项课题基金资助项目“智能电视平台与服务支撑环境研制”(XDA06040501)。

徐 超(1986-),男,博士研究生,主研方向:嵌入式系统,多媒体技术;曾学文,研究员、博士生导师;郭志川,副研究员。

2014-04-01

:2014-04-29E-mail:xuc@dsp.ac.cn