Implementation and Performance of Application-Controlled File Caching

The paper discusses a two-level replacement scheme that allows applications
to control their cache replacement, while letting the kernel control the
allocation of cache space among processes. The kernel uses LRU-SP allocation
policy which fairly distributes cache blocks and offers protection against
foolish processes.

The two-level replacement scheme basically splits the responsibility of
cache allocation between kernel and user level. On a cache miss the kernel
uses its allocation policy to decide which process should give up a cache
block. The manager process is then notified that it should give up a block
and it is free to decide which one of all its blocks it should give up. The
kernel suggests a candidate for replacement but the process manager can
overwrite this decision at any time. The block suggested by the manager is
freed by the kernel.

The kernel uses a modification of LRU called LRU-SP. LRU-SP acctes as a
regular LRU except that if the kernel suggests a block candidate A and the
manager overwrites it with B, the kernel frees B and puts A in its place in
the list and also creates a record ^Ö placeholder for B that points to A. If
later on there is a cache miss on B and there is a placeholder for B, then
the block pointed to by the placeholder is picked as the candidate.
The authors suggest that the swapping extension of the algorithm is
necessary so that the process is not penalized by the kernel if it uses a
better policy. On the other hand the placeholder makes sure that if the
process uses a worse policy it will not hurt other processes. I was not
convinced that this modification of LRU has a better performance and
protects processes. The authors provided some empirical results but no
theoretical analysis to explain why LRU-SP really does what they claim it
does.

Applications assign priorities to files and specify file cache replacement
policy for each priority level. The kernel always replaces blocks with the
lowest priority first.

The kernel implementation of the two-level replacement policy involves two
modules ^Ö Buffer Cache Module handling cache management and bookkeeping and
Application Control Module implementing the interface calls and acting as a
proxy for user-level managers.

The performance section shows that for applications that will profit from
having their own cache replacement policy using the two-level replacement
algorithm really increases performance. However,  there is some overhead in
this new implementation, due to the communication between BUD and ACM as
well as ACM and processes and it would have been interesting to see how this
overhead affects applications which rely entirely on the kernel to do the
replacement for them. I am inclined to think that if there is some overhead
in the case of oblivious processes, having the two-level replacement
algorithm will be a bad idea especially since very few of the apps will take
advantage of managing their own cache.