The effectiveness of buffer cache replacement algorithm is critical to the performance of the I/O system. In this paper, we propose a degree of inter-reference gap (DIG) based block replacement scheme that retains merits of the least recently used (LRU) such as simple implementation and good cache hit ratio (CHR) for general patterns of references, and also further improves CHR. In the proposed scheme, cache blocks with low DIGs are distinguished from blocks with high DIGs and the replacement block is selected from among high DIGs blocks, as is done in the low inter-reference recency set (LIRS) scheme. Thus, by having the cache memory dynamically partitioned based on DIGs, CHR is improved. Trace-driven simulation is employed to verify the superiority of the DIG based scheme and shows that the performance improves up to about 175% compared to the LRU scheme and 3% compared to the LIRS scheme for the same traces.
展开▼