Tuesday, October 31, 2006

Paper: "Operating System Profiling via Latency Analysis"

Operating System Profiling via Latency Analysis
Nikolai Joukov, Avishay Traeger, and Rakesh Iyer, Stony Brook University; Charles P. Wright, Stony Brook University and IBM T.J. Watson Research Center; Erez Zadok, Stony Brook University


Operating systems are complex and their behavior depends on many factors. Source code, if available, does not directly help one to understand the OS's behavior, as the behavior depends on actual workloads and external inputs. Runtime profiling is a key technique to prove new concepts, debug problems, and optimize performance. Unfortunately, existing profiling methods are lacking in important areas-they do not provide enough information about the OS's behavior, they require OS modification and therefore are not portable, or they incur high overheads thus perturbing the profiled OS.

We developed OSprof: a versatile, portable, and efficient OS profiling method based on latency distributions analysis. OSprof automatically selects important profiles for subsequent visual analysis. We have demonstrated that a suitable workload can be used to profile virtually any OS component. OSprof is portable because it can intercept operations and measure OS behavior from user-level or from inside the kernel without requiring source code. OSprof has typical CPU time overheads below 4%. In this paper we describe our techniques and demonstrate their usefulness through a series of profiles conducted on Linux, FreeBSD, and Windows, including client/server scenarios. We discovered and investigated a number of interesting interactions, including scheduler behavior, multi-modal I/O distributions, and a previously unknown lock contention, which we fixed.


Blogger Pradeep said...

Can this method be used to profile the behavior of OSes running in virtual machines ? What are the things I need to worry about if I am profiling using existing tool as described in the paper ?

7:29 AM  
Blogger Nikolai Joukov said...

We have not tried it yet but we believe that the method can be used to profile OSs inside of VMs. An interesting point is that in VMs you can query 1) guest (apparent) time and 2) host time (e.g., by using rdpmc instead of rdtsc instruction to read the clock counter in VMware VMs). In the first case, it may be possible to minimize the influence of the other VMs running on the same host. The second case may be better applicable to observe mutual influence of VMs running on the same host.

11:21 AM  
Blogger agmiklas said...

Operating System Profiling via Latency Analysis
Nikolai Joukov *, Avishay Traeger, and Rakesh Iyer, Stony Brook
University; Charles P. Wright, Stony Brook University and IBM
T.J. Watson Research Center; Erez Zadok, Stony Brook University

Nikolai presented a new approach to operating system profiling. He showed that the logarithmic distributions of an OS's latencies can reveal most if not all aspects of the OS's internal operation. He presented several methods to analyse these profiles and provided interesting examples of the sorts of conclusions that can be drawn using the profiler data. Among others, the authors were able to diagnose a locking error in the Linux kernel without having to examine the source code. Also, because the latency can be measured entirely outside of the kernel, the method can be used to analyze operating systems even if the source is not available.

The basic technique involves repeatedly measuring the times required to complete OS requests. The latency of each request depends on the path taken through the code and interactions with other processes. Therefore, the distribution of these values can be used to make inferences about an operating system's inner workings. The latencies are used to generate histograms that can be analyzed either visually or by a provided automatic data-analysis toolset. Various events, such as being blocked on a lock, show up as spikes on the histogram. Correlations between different requests can reveal their contention on a shared resource. For example, similar spikes on the histograms of two different system calls that only appear when both are run together suggest that both calls contend on the same lock.

Although the profiler can be used without any kernel changes whatsoever, it can take advantage of kernel instrumentation points if they are available. Loadable drivers can also be used as vantage points from which to measure latencies. The authors created a tool that can patch Linux file systems to automatically produce latency data.

The presented profiler adds negligible overheads. The generated profiles are usually smaller than 1KB. The profiler adds less than 200 CPU cycles per profiled call, whereas existing profilers add overheads per profiled event. For example, if a system call is trying to acquire several semaphores and to perform I/O, existing profilers would add overheads for each such event. As a result, the presented profiler is efficient. As measured with the Postmark benchmark, the system's CPU time was affected by less than 4%.

Q: Your technique makes heavy use of CPU cycle counters in order to cheaply measure intervals of time. Have you tested your system on CPUs that use variable clocks, such as those found in notebook computers? (Marcel Rosu, IBM T. J. Watson Research Center)

A: Although we didn't test on variable-clock CPUs, it should be possible to simply apply a scaling factor to handle the cases where the CPU isn't running at its maximum frequency. Also, remember that our system doesn't rely on using CPU cycle counters. We could use an off-CPU high-precision timer if the CPU lacked an appropriate method of measuring intervals.

Q: Can your profiler be used to analyze anomalous cases, rather than just bad implementations of the main case? Wouldn't anomalous cases be "drowned out" in the aggregation process? (Brad Chen, Intel)

A: The paper describes a "sample profile", where instead of folding all the latencies for a given test together, we separate them based on fixed time intervals. We used this method to analyze ReiserFS's performance during the relatively infrequent periods of time when the Linux buffer flushing daemon bdflush was active.

11:38 AM  

Post a Comment

<< Home