This thesis has two parts, the first more practical, and the second more theoretical. The first part considers informed preteching and caching in which an application provides information about its upcoming I/A 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 weights caching, a theoretical problem from the domain of on-line algorithms. I present an algorithm with competitive ratio O(log²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.

206 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu