Abstract—The study of optimal offline cache replacement policies has theoretical significance from which near-optimal but practical cache replacement schemes can be sound established. This paper has re-defined known offline cache replacement policies for nonuniform objects and proposed novel policies. All of them have been evaluated for their optimalities and complexities. The results have showed that the optimal policy has the highest time complexity whereas the other policies are sub-optimal that have lower complexities.
Index Terms—Cache replacement, nonuniform objects, optimal replacement, offline replacement.
The author is with Computer Science Department, Faculty of Science, Kasetsart University, Bangkok, Thailand (e-mail: thepparit.b@ku.th).
[PDF]
Cite: Thepparit Banditwattanawong, "The Optimality and Complexity of Offline Cache Replacement Policies for Nonuniform Objects," International Journal of Future Computer and Communication vol. 7, no.3, pp. 63-67, 2018.
