唐 云

（湖南科技学院 电子信息工程系，湖南 永州 425100）

嵌入式浏览器设计的几个技术难点研究

唐 云

（湖南科技学院 电子信息工程系，湖南 永州 425100）

本文主要探讨了在嵌入式浏览器设计的三个技术难点问题，即如何提高浏览速度、解决嵌入式系统资源有限问题以及增强解析容错性。

嵌入式系统；浏览器；HTML

1 引 言

随着信息技术的飞速发展和互联网的广泛应用，数字电视、PDA等数字多媒体和信息设备日益普及，计算机的发展已显示出微型化、智能化、网络化的趋势。嵌入式浏览器已成为嵌入式系统中重要的应用软件，而将浏览器技术与嵌入式系统技术进行集成，实现完整的数字软件平台是嵌入式系统的一个发展趋势。本文主要从提高浏览速度，节省系统资源，增强解析容错性三个方面探讨嵌入式浏览器的设计的技术问题。

2 浏览速度问题

由于嵌入式系统的CPU处理能力弱，使得速度慢，因此可以通过一些技术来掩盖其速度慢的缺陷，如：边下载边显示，缓存技术等。边下载边显示的流程是这样的，浏览器先从网上下载一块数据资源(假定为1.5K)，然后等待下一块数据的到来。在这段时间内浏览器解析显示已经下载的数据，而不是傻等。这样就使资源下载和解析处理同步进行，提高了浏览器的表现速度。用户感觉到的仅仅是下载第一块数据花费的延迟时间。但是边下载边显示增加了浏览器实现的难度，如词法分析器、语义分析器和排版处理器需要保留当前处理位置和状态等，还要考虑各部分之间的同步问题。并且边下载边显示技术只适用于大网页处理，而对内容短小的网页则不适用；因为一个数据块已经可以将整个网页取回来了。

我们的浏览器主要采取的是网页预取和缓存技术相结合来提高网页的浏览速度，其实现的原理如下。

缓存管理模块负责网页、图像的装载、淘汰操作。缓存是指为将来可能要用到的信息数据开辟的一个缓冲区, 根据缓存数据存放的位置可将缓存分为内存缓存和磁盘缓存两种。桌面浏览器一般采用磁盘缓存，嵌入式系统因为体积和成本等原因通常没有提供磁盘，有的嵌入式系统甚至没有文件系统，所以嵌入式浏览器一般只能使用内存作为缓存区，即采用内存缓存方式。在嵌入式环境中，缓存直接影响嵌入式浏览器的工作效率，用户上网浏览信息时，经常会使用“返回”等功能来访问以前的页面，此时如果网页数据保存在缓存中，则不需要再次网络中获取数据，从而大大提高了网页浏览速度。而网页预取可以预测用户将要用到的资源，并把其下载下来并缓存起来，这也大大提高了网页浏览速度。缓存的实现流程如下图所示：

2.1 网页预取

网页预取技术就是预测用户将来的请求，并且在用户请求之前，将预测的网页对象预取到缓存中，这样当用户以后真正请求这些对象时，可以直接从缓存中读取，这样就提高了网页的浏览速度。但是，如果预取的对象是不正确的，那么将会造成对服务器负载的增加和缓存资源的浪费。所以设计一套优良的网页预取算法是非常重要的。

(1)预取算法研究

预取算法的核心就是预测最近的将来用户最可能访问的网页对象。而预测的信息来源主要有两个[1]：一个是访问历史的统计信息，另一个是被访问的对象本身。

根据访问历史的统计信息来制定预取的方法有：

1)通过“热点”预取：就是根据网页的访问率，优先预取访问率较高的网页；

2)通过单个用户访问模式预取：收集用户过去的访问行为，从中找出用户的访问模式，从而为每个用户定制预取模型。

根据访问的对象本身来制定预取的方法有：

1)通过目标链接预取：在解析用户请求的网页时，预取其内部链接URL（网页或图片）；

2)通过目录预取：预取用户请求的网页的同一目录的所有网页。

分析以上所述的几种预取方法，根据访问历史的统计信息的制定预取方法需要掌握大量的统计信息，实现起来比较困难，所以我们选择根据访问对象本身来预取的两种方法，我们采取综合目标链接预取和目录预取的方法。

(2)本浏览器网页预取的实现

目前，我们的浏览器是作为数据广播的终端支持软件，由于采用的是对象轮播的传输协议，数据业务被抽象成不同的对象，其中包含目录对象，所以浏览器可以建立整个网页文件的目录结构。

根据用户所请求的网页，以及分析其所在的目录，可以向前端同时申请用户所要的网页以及与其在同一目录下的网页或邻近目录的网页，具体在操作起来还要考虑同一目录的网页的数目及大小，并还要考虑预取和缓存的联合等问题。

另外，在数据播发前端，我们所设计了一个网页文件查错软件，在检查错误的同时，我们把每个网页的相关链接资源一起列出，考虑到有些网页的链接数目比较多，所以我们只把网页的图片资源与每个网页绑定在一块，在下载网页时，连同其图片资源一起下载到本地缓存起来。

2.2 缓存置换策略

浏览器传输模块获取数据或图像解析模块解码图像时，检查剩余缓存空间大小，如果剩余空间不足以容纳要保存的缓存数据，就需要淘汰一些缓存。缓存淘汰尽可能在内存紧张时进行，应淘汰掉价值最小的数据，以最大限度地发挥缓存的作用。这就需要设计一套缓存置换策略，一个好的缓存置换策略是提升缓存效率的关键因素。

用缓存对用户经常访问的页面进行保存时，由于缓存的大小一般是固定的，不可能存放所有的文件，所以当需要多余的空间来存储新的文件时，必须以一定的原则来决定哪一个对象文件被置换，这些原则就是所谓的置换策略。

根据文件上次的存取时间、文件的存取频率、文件大小以及文件传输时间这四个影响因子，就得到下列最简单的四种单一因子置换策略[2]：

(1)Least Rcently Used Policy(LRU)：以文件上次的存取时间为依据，将最近没有被存取的文件替换掉；

(2)Least Frequently Used Policy(LFU)：考虑文件的存取频率，将文件存取频率最低者置换掉；

(3)SIZE Policy：是以文件大小为置换依据，置换掉缓存中最大的文件；

(4)Lowest Latency First Policy(LAT)：考虑文件传输延迟时间，将传输延迟时间长的文件保留在缓存中。

另外，传统上大多以以下三个指标来衡量一个缓存的效率：

(1)Hit rate：当使用者欲获取一个文件时，此时缓存中包含了该文件，则称为cache hit。反之则称为cache miss。Hit rate就是cache hit发生的百分比。Hit rate高表示cache能有效降低直接存取web服务器的次数；

(2)Byte hit rate：使用者从cache中取得的数据量占所预取的资料总量的百分比即为Byte hit rate。Byte hit rate高表示使用者直接使用web服务器得时间较少；

(3)Latency time：从使用者提出文件请求到此文件被下载完成所经过得时间。此时间短，则表示cache效率高。

每个单一因子置换策略都有自己的优势和缺点，目前，改进的置换策略很多，如：LRU-K、LFU-aging以及Greedy Dual-Size Frequency(GDSF)[3]等。下面重点介绍一下GDSF置换策略，它考虑了文件存取成本，文件过去的存取频率与文件的大小。文件优先级的计算公式是：

其中Pr(f)为文件存取优先级；clock为避免cache pollution所设的老化因子： Fr( f )为文件 f过去的存取次数：Cost( f)为文件 f存取成本； Size( f)为文件f大小。当使用者要获取的文件在缓存中时，此文件的Pr(f)将被重新计算；若没有在缓存内，GDSF策略将会将Pr(f)值最小的文件用新的文件来取代。并且clock更新为被替换置换出的文件的Pr(f)值。此外，GDSF策略可以根据缓存管理目标而有所变化。例如GDSF(1)为了得到较好的hit rate，将 Cost( f)设为1，此时GDSF策略会倾向于将较小的文件保留在缓存中。相反的，为了得到较好的byte hit rate，我们可以将 Cost( f)设置成文件大小 Size( f)的函数；例如 Size( f)将GDSF(packet)设成2+ Size( f)/536，便是为了得到较好的byte hit rate值[4]。

在设计浏览器的缓存及置换策略时，需要综合考虑浏览器的缓存空间、网页存取的特点等因素。如果浏览器还支持网页预取功能，那么还需要考虑预取网页对缓存置换策略的影响。综合以上因素，在设计本浏览器的缓存模块及其置换策略时，我们考虑了以下四个因素：

(1)文件大小：一般被请求的文件大部分是较小文件，因此选择存放较小的文件也就代表缓存内存放的文件数会较多，因此能有效提高cache hit rate值；

(2)文件过去的存取次数：由于使用者有周期存取的习惯，因此若一个文件过去存取的次数越多，其未来被存取的次数就越大。选择过去存取次数较高的文件存放在cache中，cache值hit rate 和byte hit rate 也往往会因而提升；

(3)文件上次存取时间：一般认为距离文件上次存取时间越久，其未来存取的几率就越低。所以将此类文件排除在cache之外，以提高cache效率（hit rate与byte hit rate）。另外，考虑此项因子的置换策略还可以有效避免cache pollution的发生；

(4)考虑数据预取机制对缓存的影响：预取的文件同样要缓存到cache空间中，预取文件数目以及预取文件的置换优先级都需要设计合理才能保证置换策略的效率。

GDSF策略是一款简单、高效且同时兼顾多种因素的优秀策略。所以我们设计浏览器缓存策略时，也借鉴了其核心思想，并考虑了浏览器预取机制的影响，于是得到了我们的缓存策略的优先级计算公式如下：

其中Pr()f表示文件f的缓存优先级；clock是缓存老化因子； ()Fr f为文件f过去存取的次数； ()Size f为文件 f的大小；另外，pre是预取影响因子，它表示预取机制对缓存文件的优先级的影响；

3 嵌入式系统资源有限问题

我们知道有限存储器容量往往会导致系统崩溃，其解决方法如下：

(1)减少存储器的使用；首先，应尽量使用局部变量代替全局或静态变量，因为局部变量是动态创建，使用完后就释放掉了，第二，为尽可能减少运行时占用的内存，使用标量类型代替结构体类型，第三，使用指针类型变量或结构；第四，避免字符串串联，因为字符串串联不仅会降低性能，而且会增加应用程序的内存峰值占用量；第五，使用一些图片工具对图片进行压缩处理，不会影响显示效果。

(2)避免线程同步，任何运行时间超过0.1秒的操作都需要一个独立的线程，避免同步同样能提高性能。

(3)进行积极的垃圾回收，一旦一个指针或结构体使用完毕时，应该及时释放掉内存空间。

(4)在系统设计时，使用一边下载内容，一边解析内容，一边显示内容的方式，而不是等到整个页面全部下载后再处理。

4 解析容错性问题

HTML语言是一种结构比较松散的标记语言，并且在HTML语言发展过程中两大浏览器生产商网景和微软互相竞争，使浏览器功能日益庞大，对HTML语言的容错能力非常强。对于无论多么不规范的HTML语言文档，IE和NetScape都可以解析显示。此外，两大浏览器厂商竞相为HTML语言增加专有标记，以突出自己的显示效果。这样就使网页设计者养成了不好的编程习惯，只注重显示效果并不关心语法。致使目前互联网上存在着大量的不合规范的网页。针对这种情况，浏览器必须采取有效的容错处理[5]。

主要的语法错误有下面四种：

(1) 非法包含，例如＜a＞和＜/a＞之间包含一个表格，或是＜td＞ ＜tr＞ ＜/td＞；

(2) 非法标记，除了HTML规定的任何符号，例如＜tp＞；

(3) 交叉嵌套，如＜a＞ ＜em＞ ＜/a＞ ＜/em＞；

(4) 标记不匹配，对于 HTML 规范中规定必须结束标记符的元素类型，缺少结束标记符，或是在文档中前面没有这个标记，而在后面多余写了这个标记的结束标记符。

针对上述常见的语法错误，我们采取的相应容错处理：

(1) 针对非法包含，如果该标记的到来是非法的则跳过，对其不予处理；

(2) 针对非法标记，由于在标记查找表没有相应的符号也就没有相应标记的处理函数，相当于对该非法标记采取了忽略的作用；

(3) 针对交叉嵌套，当遇到一个结束标记时，查找栈中是否有该标记，若有，则将其与其上的标记全部出栈；

(4) 针对标记不匹配，对多余的结束标记，利用堆栈，查找栈内的标记是否有该标记，若没有则不予处理，对于应该有结束标记而没写结束标记的，若下一个开始标记的到来可以肯定前一个标记必须结束了，则将应结束而没有结束的标记出栈。

5 结 论

本文主要探讨了嵌入式浏览器设计的三个技术难点及其解决方案，其一是浏览速度问题，采用网页预取和缓存技术相结合来提高网页的浏览速度；其二是嵌入式系统资源有限问题，采用减少存储器的使用、避免线程同步、进行积极的垃圾回收以及边下载边解析四种方法来解决；其三是解析容错性，采用堆栈来检查标记的位置正确与否。

[1]Chen Xin, Zhang Xiaodong. A popularity-based prediction model for Web perfecting[J].Computer, 2003:63-70.

[2]NuQi Huang. A new cache replacement policy based on document information value[J].Chao Yang Science Technology University of Taiwan. 2004.

[3]Cherkasova,ludmila. Improving WWWP roxies Perfomance with Greedy-Dual-Size-Frequency Caching Policy. HP Labs TechnicalReports[DB/OL]. http://www.hpl.hp.com/techreports,1998.

[4]L. Cherkasova, G. Ciardo:Role of Aging, Frequency, and Size in Web CacheReplacement Policies[A]. Lecture Notes in Computer Science, Springer-Verlag, vol.2110, pp. 114-123, Proceedings on High Performance Computing and Networking,HPCN’01, Amsterdam, June 25-27, 2001.

[5]唐云.一种嵌入式浏览器中的HTML解析器的设计[J].湖南科技学院学报, 2008,(08):94.

(责任编校：何俊华)

TN919

A

1673-2219（2010）12-0029-04

2010－10－22

湖南科技学院2008年度科学研究项目（08XKYTC039）

唐云(1984－)，女，硕士，研究方向为多媒体通信。