프리페치를 고려한 LRU 기반의 버퍼캐시 블록 교체 알고리즘

Abstract

버퍼캐시 블록 교체 알고리즘들은 프리페치 기법에 대한 고려 없이 연구되어왔다. 따라서 본 논문에서는 가장 널리 쓰이는 LRU 교체 알고리즘을 기반으로 하여 프리페치를 고려한 교체 알고리즘들을 제안한다. LRU 교체 알고리즘에서 프리페치된 블록들로 인해 기존의 유용한 블록들이 교체되는 문제를 해결하기 위해 프리페치 큐를 추가하여 프리페치된 블록들을 관리하는 LRU-PQ와 LRU-SPQ 교체 알고리즘을 제안하고, 한 번만 사용되는 프리페치된 블록들이 많다는 점을 고려하여 이러한 블록들로 인해 LRU의 유용한 블록들이 교체 되는 것을 줄일 수 있도록 LRU-PQ와 LRU-SPQ 교체 알고리즘에 프리페치 히스토리 큐를 추가하는 LRU-PHQ와 LRU-SPHQ 교체 알고리즘들을 제안한다. 마지막으로 시뮬레이션을 통해 제안된 알고리즘들- LRU-PQ와 LRU-SPQ, LRU-PHQ와 LRU-SPHQ -과 기존 LRU 교체 알고리즘의 적중률보다 각각 최대 약 5%, 33% 향상된 결과를 보였다.|To improve file system performance, it is important to design effective block replacement algorithms to minimize buffer cache misses. However, despite the well-known interactions between prefetching and caching, almost all buffer cache block replacement algorithms have been proposed and studied without taking into account file system prefetching that exists in all modern operating systems. Therefore, I suggest new block replacement algorithms based LRU replacement algorithm and prefetching on this paper because LRU algorithm is used widely and frequently. LRU algorithm has many advantages. For example, it is easy and simple to implement the algorithm. However, there are some problems on it, and particularly I focused that useful blocks are replaced by prefetched blocks and are discarded. LRU-PQ and LRU SPQ algorithms use the prefetch queue to manage prefetched blocks, and only hit blocks in prefetch queue move into LRU. Therefore, they can reduce the number of on-demand blocks replaced with prefetched blocks. In addition, I considered that many prefetched blocks are used only once, and I propose LRU-PHQ and LRU-SPHQ replacement algorithms that add the prefetch history queue on each LRU-PQ and LRU-SPQ. I evaluate LRU-PQ, LRU-SPQ, LRU-PHQ and LRU-SPHQ via trace-driven simulations and an implementation in Linux, and compare them to LRU algorithm. The performance improvements are substantial. The hit ratio of LRU-PQ and LRU-SPQ improves by as much as 5%, and the hit ratio of LRU-PHQ and LRU-SPHQ improves by as much as 33%.; To improve file system performance, it is important to design effective block replacement algorithms to minimize buffer cache misses. However, despite the well-known interactions between prefetching and caching, almost all buffer cache block replacement algorithms have been proposed and studied without taking into account file system prefetching that exists in all modern operating systems. Therefore, I suggest new block replacement algorithms based LRU replacement algorithm and prefetching on this paper because LRU algorithm is used widely and frequently. LRU algorithm has many advantages. For example, it is easy and simple to implement the algorithm. However, there are some problems on it, and particularly I focused that useful blocks are replaced by prefetched blocks and are discarded. LRU-PQ and LRU SPQ algorithms use the prefetch queue to manage prefetched blocks, and only hit blocks in prefetch queue move into LRU. Therefore, they can reduce the number of on-demand blocks replaced with prefetched blocks. In addition, I considered that many prefetched blocks are used only once, and I propose LRU-PHQ and LRU-SPHQ replacement algorithms that add the prefetch history queue on each LRU-PQ and LRU-SPQ. I evaluate LRU-PQ, LRU-SPQ, LRU-PHQ and LRU-SPHQ via trace-driven simulations and an implementation in Linux, and compare them to LRU algorithm. The performance improvements are substantial. The hit ratio of LRU-PQ and LRU-SPQ improves by as much as 5%, and the hit ratio of LRU-PHQ and LRU-SPHQ improves by as much as 33%.