貪婪雙尺寸頻率算法的優化與改進

黎慧源 ，易國洪*，代 瑜 ，馮智莉

1.智能機器人湖北省重點實驗室（武漢工程大學），湖北 武漢 430205；2.武漢工程大學計算機科學與工程學院，湖北 武漢 430205

隨著互聯網的發展，Web服務器的壓力越來越大，用戶對網頁的響應速度要求也越來越高。為了減輕Web服務器在高并發訪問情況下的壓力，縮短用戶訪問Web網站的時間延遲，可以在Web服務器和用戶之間增設Web代理服務器。Web代理服務器將一些經常被訪問到的Web對象緩存在代理服務器中，當用戶由客戶端向Web服務器發出請求時，請求將被發送到代理服務器，由代理服務器來進行處理。如果代理服務器中已經存有用戶請求的Web對象，則經過代理服務器對緩存對象的一致性和有效性進行判斷后，直接將有效的緩存對象返回給用戶，或者去源Web服務器上取回最新的Web對象，存儲在代理服務器中后，再將對象返回給用戶。當代理服務器緩存空間不足時，緩存機制會根據緩存替換算法會將某些緩存對象移出緩存空間來存儲新的Web對象［1］。因此，緩存替換算法的好壞是決定代理服務器性能的重要因素之一。

最著名和最基本的緩存替換算法有最近最少使用替換（Least Recently Used，LRU）算法［2］，該算法優先替換掉那些離上一次被訪問時間的時間間隔最長的對象。先進先出（First In First Out，FIFO）算法［3］，優先替換掉最先進入緩存區的對象。基于對象大小（Size）替換算法［4］，將緩存中最大的對象替換出去。還有最不經常使用替換算法，該算法將自進入內存后使用次數最少的對象替換出去。……