嵌入式瀏覽器設計的幾個技術難點研究

唐 云

（湖南科技學院 電子信息工程系，湖南 永州 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－)，女，碩士，研究方向為多媒體通信。