AccuSim: Accurate Simulation of Cache Replacement Algorithms
|
|
AccuSim: Accurate Simulation of Cache Replacement Algorithms |
|
A critical problem in improving file system performance is to design an effective block replacement algorithm for the buffer cache. Despite the well-known interactions between prefetching and caching, almost all buffer cache replacement algorithms have been proposed and studied comparatively without taking into account file system prefetching which exists in all modern operating systems. It has been shown [1] that kernel prefetching can have a significant impact on the relative performance in terms of the number of actual disk I/Os of many well-known replacement algorithms; it can not only narrow the performance gap but also change the relative performance benefits of different algorithms. Moreover, the response time for all disk I/Os is not the same, and hence the improvement in disk I/Os does not directly translate to improvement in execution time. These results demonstrate the importance for buffer caching research to take file system prefetching into consideration, and to study actual disk I/Os and execution time for comparing different algorithms.
Figure 1: Various kernel subsystems on the path from file system to the disk
Figure 1 shows the various kernel subsystems that come into play before an I/O access from an application is delivered to the actual disk. The complexity of interactions between such subsystems entails that the various buffer caching algorithms are comparatively studied in a realistic setting. However, creating an actual kernel implementation of the algorithm being designed and the algorithms to be compared against can be a laborious task. In addition, even with such a kernel implementation, it is often non-trivial to obtain a controlled environment, e.g., a fixed cache size in the presence of a unified buffer cache, in the actual kernel for comparing various algorithms on an even basis. To overcome this challenge faced by cache replacement algorithm designers, we have developed a buffer cache simulator AccuSim that realistically models all the kernel subsystems involved in buffer cache management in modern operating systems. AccuSim has the following features:
AccuSim is a trace-driven simulator and uses traces which can easily be collected using system call tracing tools such as strace.
AccuSim faithfully implements the Linux kernel prefetching and I/O clustering mechanisms.
AccuSim interfaces with a realistic disk simulator, DiskSim, to enable the compensative study of the hit ratios, the number of disk requests, and the execution times of applications.
AccuSim accurately simulates I/O time under I/O clustering and prefetching.
AccuSim implements eight representative cache replacement algorithms.
AccuSim greatly simplifies the otherwise difficult task of systematic and accurate evaluation of various caching algorithms.
AccuSim provides for easy integration of a new replacement algorithm, and allow the replacement algorithm designer to focus on the algorithm by providing support functionality.
Figure 2: The architecture of AccuSim
Figure 2 shows the various modules of AccuSim.
AccuSim is driven by a trace that records the I/O operations during
the execution of an application. In particular, for each I/O
operation, the trace contains the identifier (inode) of the file
that is accessed, the offset into the file of the first block that is
accessed, the number of blocks being accessed, the I/O issue time, and
the I/O completion time. A trace with this information can easily be
collected using the standard system call tracing tool strace,
which can be easily modified to collect only the desired information.
The trace is then processed to caculate the time difference between
completion time of an I/O operation and the issue time of the next
which is interpreted as the computation time in between the two I/O
operations. Afterwards, the I/O issue and completion times are
discarded and the processed trace only records the sequence of I/O
operations interleaved with the computation time in between.
Each recorded entry in the trace contains a head which has the
following format:
typedef struct _tracehead
{
unsigned type:5;
unsigned pid:27;
union
{
unsigned inode;
unsigned child;
unsigned fnamesize;
};
} trace_head;
The trace entry can be for many different types, e.g., TREAD, TWRITE,
etc. For example read and write> system
calls, the recorded trace entry has the following format:
typedef struct _rwEntry
{
unsigned pc;
unsigned pcf;
unsigned pcall;
int iosize;
int iosizer;
unsigned filedes:16;
unsigned execTime;
unsigned fsize;
} rwEntry;
AssuSim has been made freely available in order to further file system research. You can obtain the source code of AccuSim and the traces used in our study by following the instructions at the download page.
AccuSim has been used extensively for a comparative
study [1] of the hit ratios, number of disk requests, and
execution time of eight modern cache replacement algorithms. Moreover,
AccuSim has also been used for designing a new cache replacement
algorithm in [2].
[2]
Program Counter Based Pattern Classification in Buffer Caching.
Chris Gniady, Ali R. Butt, and Y. Charlie Hu.
Proceedings of the 6th Symposium on Operating Systems Design and Implementation
(OSDI), San Francisco, CA, December 6-8, 2004.
PDF