唐 云

（湖南科技學(xué)院 電子信息工程系，湖南 永州 425100）

嵌入式瀏覽器設(shè)計的幾個技術(shù)難點研究

唐 云

（湖南科技學(xué)院 電子信息工程系，湖南 永州 425100）

本文主要探討了在嵌入式瀏覽器設(shè)計的三個技術(shù)難點問題，即如何提高瀏覽速度、解決嵌入式系統(tǒng)資源有限問題以及增強解析容錯性。

嵌入式系統(tǒng)；瀏覽器；HTML

1 引 言

隨著信息技術(shù)的飛速發(fā)展和互聯(lián)網(wǎng)的廣泛應(yīng)用，數(shù)字電視、PDA等數(shù)字多媒體和信息設(shè)備日益普及，計算機的發(fā)展已顯示出微型化、智能化、網(wǎng)絡(luò)化的趨勢。嵌入式瀏覽器已成為嵌入式系統(tǒng)中重要的應(yīng)用軟件，而將瀏覽器技術(shù)與嵌入式系統(tǒng)技術(shù)進行集成，實現(xiàn)完整的數(shù)字軟件平臺是嵌入式系統(tǒng)的一個發(fā)展趨勢。本文主要從提高瀏覽速度，節(jié)省系統(tǒng)資源，增強解析容錯性三個方面探討嵌入式瀏覽器的設(shè)計的技術(shù)問題。

2 瀏覽速度問題

由于嵌入式系統(tǒng)的CPU處理能力弱，使得速度慢，因此可以通過一些技術(shù)來掩蓋其速度慢的缺陷，如：邊下載邊顯示，緩存技術(shù)等。邊下載邊顯示的流程是這樣的，瀏覽器先從網(wǎng)上下載一塊數(shù)據(jù)資源(假定為1.5K)，然后等待下一塊數(shù)據(jù)的到來。在這段時間內(nèi)瀏覽器解析顯示已經(jīng)下載的數(shù)據(jù)，而不是傻等。這樣就使資源下載和解析處理同步進行，提高了瀏覽器的表現(xiàn)速度。用戶感覺到的僅僅是下載第一塊數(shù)據(jù)花費的延遲時間。但是邊下載邊顯示增加了瀏覽器實現(xiàn)的難度，如詞法分析器、語義分析器和排版處理器需要保留當前處理位置和狀態(tài)等，還要考慮各部分之間的同步問題。并且邊下載邊顯示技術(shù)只適用于大網(wǎng)頁處理，而對內(nèi)容短小的網(wǎng)頁則不適用；因為一個數(shù)據(jù)塊已經(jīng)可以將整個網(wǎng)頁取回來了。

我們的瀏覽器主要采取的是網(wǎng)頁預(yù)取和緩存技術(shù)相結(jié)合來提高網(wǎng)頁的瀏覽速度，其實現(xiàn)的原理如下。

緩存管理模塊負責網(wǎng)頁、圖像的裝載、淘汰操作。緩存是指為將來可能要用到的信息數(shù)據(jù)開辟的一個緩沖區(qū), 根據(jù)緩存數(shù)據(jù)存放的位置可將緩存分為內(nèi)存緩存和磁盤緩存兩種。桌面瀏覽器一般采用磁盤緩存，嵌入式系統(tǒng)因為體積和成本等原因通常沒有提供磁盤，有的嵌入式系統(tǒng)甚至沒有文件系統(tǒng)，所以嵌入式瀏覽器一般只能使用內(nèi)存作為緩存區(qū)，即采用內(nèi)存緩存方式。在嵌入式環(huán)境中，緩存直接影響嵌入式瀏覽器的工作效率，用戶上網(wǎng)瀏覽信息時，經(jīng)常會使用“返回”等功能來訪問以前的頁面，此時如果網(wǎng)頁數(shù)據(jù)保存在緩存中，則不需要再次網(wǎng)絡(luò)中獲取數(shù)據(jù)，從而大大提高了網(wǎng)頁瀏覽速度。而網(wǎng)頁預(yù)取可以預(yù)測用戶將要用到的資源，并把其下載下來并緩存起來，這也大大提高了網(wǎng)頁瀏覽速度。緩存的實現(xiàn)流程如下圖所示：

2.1 網(wǎng)頁預(yù)取

網(wǎng)頁預(yù)取技術(shù)就是預(yù)測用戶將來的請求，并且在用戶請求之前，將預(yù)測的網(wǎng)頁對象預(yù)取到緩存中，這樣當用戶以后真正請求這些對象時，可以直接從緩存中讀取，這樣就提高了網(wǎng)頁的瀏覽速度。但是，如果預(yù)取的對象是不正確的，那么將會造成對服務(wù)器負載的增加和緩存資源的浪費。所以設(shè)計一套優(yōu)良的網(wǎng)頁預(yù)取算法是非常重要的。

(1)預(yù)取算法研究

預(yù)取算法的核心就是預(yù)測最近的將來用戶最可能訪問的網(wǎng)頁對象。而預(yù)測的信息來源主要有兩個[1]：一個是訪問歷史的統(tǒng)計信息，另一個是被訪問的對象本身。

根據(jù)訪問歷史的統(tǒng)計信息來制定預(yù)取的方法有：

1)通過“熱點”預(yù)取：就是根據(jù)網(wǎng)頁的訪問率，優(yōu)先預(yù)取訪問率較高的網(wǎng)頁；

2)通過單個用戶訪問模式預(yù)?。菏占脩暨^去的訪問行為，從中找出用戶的訪問模式，從而為每個用戶定制預(yù)取模型。

根據(jù)訪問的對象本身來制定預(yù)取的方法有：

1)通過目標鏈接預(yù)取：在解析用戶請求的網(wǎng)頁時，預(yù)取其內(nèi)部鏈接URL（網(wǎng)頁或圖片）；

2)通過目錄預(yù)取：預(yù)取用戶請求的網(wǎng)頁的同一目錄的所有網(wǎng)頁。

分析以上所述的幾種預(yù)取方法，根據(jù)訪問歷史的統(tǒng)計信息的制定預(yù)取方法需要掌握大量的統(tǒng)計信息，實現(xiàn)起來比較困難，所以我們選擇根據(jù)訪問對象本身來預(yù)取的兩種方法，我們采取綜合目標鏈接預(yù)取和目錄預(yù)取的方法。

(2)本瀏覽器網(wǎng)頁預(yù)取的實現(xiàn)

目前，我們的瀏覽器是作為數(shù)據(jù)廣播的終端支持軟件，由于采用的是對象輪播的傳輸協(xié)議，數(shù)據(jù)業(yè)務(wù)被抽象成不同的對象，其中包含目錄對象，所以瀏覽器可以建立整個網(wǎng)頁文件的目錄結(jié)構(gòu)。

根據(jù)用戶所請求的網(wǎng)頁，以及分析其所在的目錄，可以向前端同時申請用戶所要的網(wǎng)頁以及與其在同一目錄下的網(wǎng)頁或鄰近目錄的網(wǎng)頁，具體在操作起來還要考慮同一目錄的網(wǎng)頁的數(shù)目及大小，并還要考慮預(yù)取和緩存的聯(lián)合等問題。

另外，在數(shù)據(jù)播發(fā)前端，我們所設(shè)計了一個網(wǎng)頁文件查錯軟件，在檢查錯誤的同時，我們把每個網(wǎng)頁的相關(guān)鏈接資源一起列出，考慮到有些網(wǎng)頁的鏈接數(shù)目比較多，所以我們只把網(wǎng)頁的圖片資源與每個網(wǎng)頁綁定在一塊，在下載網(wǎng)頁時，連同其圖片資源一起下載到本地緩存起來。

2.2 緩存置換策略

瀏覽器傳輸模塊獲取數(shù)據(jù)或圖像解析模塊解碼圖像時，檢查剩余緩存空間大小，如果剩余空間不足以容納要保存的緩存數(shù)據(jù)，就需要淘汰一些緩存。緩存淘汰盡可能在內(nèi)存緊張時進行，應(yīng)淘汰掉價值最小的數(shù)據(jù)，以最大限度地發(fā)揮緩存的作用。這就需要設(shè)計一套緩存置換策略，一個好的緩存置換策略是提升緩存效率的關(guān)鍵因素。

用緩存對用戶經(jīng)常訪問的頁面進行保存時，由于緩存的大小一般是固定的，不可能存放所有的文件，所以當需要多余的空間來存儲新的文件時，必須以一定的原則來決定哪一個對象文件被置換，這些原則就是所謂的置換策略。

根據(jù)文件上次的存取時間、文件的存取頻率、文件大小以及文件傳輸時間這四個影響因子，就得到下列最簡單的四種單一因子置換策略[2]：

(1)Least Rcently Used Policy(LRU)：以文件上次的存取時間為依據(jù)，將最近沒有被存取的文件替換掉；

(2)Least Frequently Used Policy(LFU)：考慮文件的存取頻率，將文件存取頻率最低者置換掉；

(3)SIZE Policy：是以文件大小為置換依據(jù)，置換掉緩存中最大的文件；

(4)Lowest Latency First Policy(LAT)：考慮文件傳輸延遲時間，將傳輸延遲時間長的文件保留在緩存中。

另外，傳統(tǒng)上大多以以下三個指標來衡量一個緩存的效率：

(1)Hit rate：當使用者欲獲取一個文件時，此時緩存中包含了該文件，則稱為cache hit。反之則稱為cache miss。Hit rate就是cache hit發(fā)生的百分比。Hit rate高表示cache能有效降低直接存取web服務(wù)器的次數(shù)；

(2)Byte hit rate：使用者從cache中取得的數(shù)據(jù)量占所預(yù)取的資料總量的百分比即為Byte hit rate。Byte hit rate高表示使用者直接使用web服務(wù)器得時間較少；

(3)Latency time：從使用者提出文件請求到此文件被下載完成所經(jīng)過得時間。此時間短，則表示cache效率高。

每個單一因子置換策略都有自己的優(yōu)勢和缺點，目前，改進的置換策略很多，如：LRU-K、LFU-aging以及Greedy Dual-Size Frequency(GDSF)[3]等。下面重點介紹一下GDSF置換策略，它考慮了文件存取成本，文件過去的存取頻率與文件的大小。文件優(yōu)先級的計算公式是：

其中Pr(f)為文件存取優(yōu)先級；clock為避免cache pollution所設(shè)的老化因子： Fr( f )為文件 f過去的存取次數(shù)：Cost( f)為文件 f存取成本； Size( f)為文件f大小。當使用者要獲取的文件在緩存中時，此文件的Pr(f)將被重新計算；若沒有在緩存內(nèi)，GDSF策略將會將Pr(f)值最小的文件用新的文件來取代。并且clock更新為被替換置換出的文件的Pr(f)值。此外，GDSF策略可以根據(jù)緩存管理目標而有所變化。例如GDSF(1)為了得到較好的hit rate，將 Cost( f)設(shè)為1，此時GDSF策略會傾向于將較小的文件保留在緩存中。相反的，為了得到較好的byte hit rate，我們可以將 Cost( f)設(shè)置成文件大小 Size( f)的函數(shù)；例如 Size( f)將GDSF(packet)設(shè)成2+ Size( f)/536，便是為了得到較好的byte hit rate值[4]。

在設(shè)計瀏覽器的緩存及置換策略時，需要綜合考慮瀏覽器的緩存空間、網(wǎng)頁存取的特點等因素。如果瀏覽器還支持網(wǎng)頁預(yù)取功能，那么還需要考慮預(yù)取網(wǎng)頁對緩存置換策略的影響。綜合以上因素，在設(shè)計本瀏覽器的緩存模塊及其置換策略時，我們考慮了以下四個因素：

(1)文件大?。阂话惚徽埱蟮奈募蟛糠质禽^小文件，因此選擇存放較小的文件也就代表緩存內(nèi)存放的文件數(shù)會較多，因此能有效提高cache hit rate值；

(2)文件過去的存取次數(shù)：由于使用者有周期存取的習慣，因此若一個文件過去存取的次數(shù)越多，其未來被存取的次數(shù)就越大。選擇過去存取次數(shù)較高的文件存放在cache中，cache值hit rate 和byte hit rate 也往往會因而提升；

(3)文件上次存取時間：一般認為距離文件上次存取時間越久，其未來存取的幾率就越低。所以將此類文件排除在cache之外，以提高cache效率（hit rate與byte hit rate）。另外，考慮此項因子的置換策略還可以有效避免cache pollution的發(fā)生；

(4)考慮數(shù)據(jù)預(yù)取機制對緩存的影響：預(yù)取的文件同樣要緩存到cache空間中，預(yù)取文件數(shù)目以及預(yù)取文件的置換優(yōu)先級都需要設(shè)計合理才能保證置換策略的效率。

GDSF策略是一款簡單、高效且同時兼顧多種因素的優(yōu)秀策略。所以我們設(shè)計瀏覽器緩存策略時，也借鑒了其核心思想，并考慮了瀏覽器預(yù)取機制的影響，于是得到了我們的緩存策略的優(yōu)先級計算公式如下：

其中Pr()f表示文件f的緩存優(yōu)先級；clock是緩存老化因子； ()Fr f為文件f過去存取的次數(shù)； ()Size f為文件 f的大小；另外，pre是預(yù)取影響因子，它表示預(yù)取機制對緩存文件的優(yōu)先級的影響；

3 嵌入式系統(tǒng)資源有限問題

我們知道有限存儲器容量往往會導(dǎo)致系統(tǒng)崩潰，其解決方法如下：

(1)減少存儲器的使用；首先，應(yīng)盡量使用局部變量代替全局或靜態(tài)變量，因為局部變量是動態(tài)創(chuàng)建，使用完后就釋放掉了，第二，為盡可能減少運行時占用的內(nèi)存，使用標量類型代替結(jié)構(gòu)體類型，第三，使用指針類型變量或結(jié)構(gòu)；第四，避免字符串串聯(lián)，因為字符串串聯(lián)不僅會降低性能，而且會增加應(yīng)用程序的內(nèi)存峰值占用量；第五，使用一些圖片工具對圖片進行壓縮處理，不會影響顯示效果。

(2)避免線程同步，任何運行時間超過0.1秒的操作都需要一個獨立的線程，避免同步同樣能提高性能。

(3)進行積極的垃圾回收，一旦一個指針或結(jié)構(gòu)體使用完畢時，應(yīng)該及時釋放掉內(nèi)存空間。

(4)在系統(tǒng)設(shè)計時，使用一邊下載內(nèi)容，一邊解析內(nèi)容，一邊顯示內(nèi)容的方式，而不是等到整個頁面全部下載后再處理。

4 解析容錯性問題

HTML語言是一種結(jié)構(gòu)比較松散的標記語言，并且在HTML語言發(fā)展過程中兩大瀏覽器生產(chǎn)商網(wǎng)景和微軟互相競爭，使瀏覽器功能日益龐大，對HTML語言的容錯能力非常強。對于無論多么不規(guī)范的HTML語言文檔，IE和NetScape都可以解析顯示。此外，兩大瀏覽器廠商競相為HTML語言增加專有標記，以突出自己的顯示效果。這樣就使網(wǎng)頁設(shè)計者養(yǎng)成了不好的編程習慣，只注重顯示效果并不關(guān)心語法。致使目前互聯(lián)網(wǎng)上存在著大量的不合規(guī)范的網(wǎng)頁。針對這種情況，瀏覽器必須采取有效的容錯處理[5]。

主要的語法錯誤有下面四種：

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

(2) 非法標記，除了HTML規(guī)定的任何符號，例如＜tp＞；

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

(4) 標記不匹配，對于 HTML 規(guī)范中規(guī)定必須結(jié)束標記符的元素類型，缺少結(jié)束標記符，或是在文檔中前面沒有這個標記，而在后面多余寫了這個標記的結(jié)束標記符。

針對上述常見的語法錯誤，我們采取的相應(yīng)容錯處理：

(1) 針對非法包含，如果該標記的到來是非法的則跳過，對其不予處理；

(2) 針對非法標記，由于在標記查找表沒有相應(yīng)的符號也就沒有相應(yīng)標記的處理函數(shù)，相當于對該非法標記采取了忽略的作用；

(3) 針對交叉嵌套，當遇到一個結(jié)束標記時，查找棧中是否有該標記，若有，則將其與其上的標記全部出棧；

(4) 針對標記不匹配，對多余的結(jié)束標記，利用堆棧，查找棧內(nèi)的標記是否有該標記，若沒有則不予處理，對于應(yīng)該有結(jié)束標記而沒寫結(jié)束標記的，若下一個開始標記的到來可以肯定前一個標記必須結(jié)束了，則將應(yīng)結(jié)束而沒有結(jié)束的標記出棧。

5 結(jié) 論

本文主要探討了嵌入式瀏覽器設(shè)計的三個技術(shù)難點及其解決方案，其一是瀏覽速度問題，采用網(wǎng)頁預(yù)取和緩存技術(shù)相結(jié)合來提高網(wǎng)頁的瀏覽速度；其二是嵌入式系統(tǒng)資源有限問題，采用減少存儲器的使用、避免線程同步、進行積極的垃圾回收以及邊下載邊解析四種方法來解決；其三是解析容錯性，采用堆棧來檢查標記的位置正確與否。

[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解析器的設(shè)計[J].湖南科技學(xué)院學(xué)報, 2008,(08):94.

(責任編校：何俊華)

TN919

A

1673-2219（2010）12-0029-04

2010－10－22

湖南科技學(xué)院2008年度科學(xué)研究項目（08XKYTC039）

唐云(1984－)，女，碩士，研究方向為多媒體通信。