Practical and Theoretical Issues in Prebriefing and Caching

摘要

This thesis has two parts, the first more practical, and the second more theoretical. The first part considers informed prefetching and caching in which an application provides information about its upcoming I/O accesses to the operating system, allowing the system to prefetch data and to make informed cache replacement decisions. I compare existing algorithms for this problem using trace-driven simulation, and use the results to develop a new algorithm that performs better than previous approaches, again under trace-driven simulation. The second part considers weighted caching, a theoretical problem from the domain of on-line algorithms. I present an algorithm with competitive ratio O(log(2) k) on (k + 1)-point spaces, the first poly-logarithmic ratio for this problem. I also give an almost-tight lower bound of omega(log k) for any weighted caching problem on at least k + 1 points. I then show a connection between this problem and a new on-line k-server model in which the servers may rearrange themselves without cost during 'free-time' between requests, and describe a series of results in the free-time model.