Assignment #2 - Request Trace Analysis

Due on Sunday, March 2. You should turn in a written report. You can either send an electronic copy to me, or you can drop a hard copy in my mailbox in the mailroom adjacent to the 7th floor software lab. I do not have an official late turn-in policy for this course. If you have some good reason to be late, please let me know and I will consider it on a case-by-case basis.

In the class we discussed tracking requests in server systems. After properly tracking each request's execution, we can attribute system events (e.g., CPU context switches, network sends/recvs, file reads/writes, system calls) to corresponding request contexts. The purpose of this assignment is to analyze collected request event traces in order to understand the per-request behavior in traced server workloads.

Server request traces:
From any machine in the department graduate/research network, you can find request traces for four server workloads at /p/com-placement/kshen/csc573-requesttrace/. The traces are in four sub-directories:

For the purpose of this assignment, you don't have to understand high-level semantics of these application workloads. But knowing them may help understanding the results of the trace analysis.

In each sub-directory, you will find around 4000 files, each of which corresponds to the event trace of one request. The name of each file is in the format of tid0000xxxx.trace, in which xxxx indicates the time order of the request arrival --- for instance, request tid00001000 arrives right before tid00001001, which in turn arrives right before tid00001002.

The format of each request event trace file is described as follows. The first line is always "Request Type: ..." which indicates the type or input of this particular request. There may be a few more lines of overall request description and some empty lines before the traced events. Each event is in the format of "event: etype x, pid y, time z, ...".

Later parts of the event format depends on the event type and they should be mostly self-explanatory. Feel free to ask me if you have any questions. Note that there can be more than one spaces as field delimiters. Do NOT assume there is a single space between adjacent fields.

The traces were collected in Linux operating system version 2.6.10. You might not care about the underlying operating system in your trace analysis and I am providing this information just in case. For instance, if you care to know the semantics of each system call id, you can start looking at the bottom of this file. As another example, process id 0 indicates the idle process in Linux.

Task #1: plot CPU time distribution
Your first task is to parse each request trace file to extract the aggregate CPU time of each request. This can be done by aggregating all CPU running spurts, each of which is marked by a pair of adjacent CPU switch-in/out events. Note that there is a chance that some CPU switch in/out events are lost in the trace --- you may find a switch-in event with no matching switch-out. Do some reasonable approximation in such cases.

After extracting the aggregate CPU time of each request for each workload, please plot the distribution of request CPU time for each of the four workloads. In other words, there should be four plots each corresponds to one workload. Each plot shows the distribution of CPU time for all traced requests in this workload.

Task #2: CPU time prediction
In addition to the aggregate CPU time, you can also extract the system call events from each request trace file. In this task, you are asked to explore using request system call events to predict its aggregate CPU time. Specifically, given the knowledge of a request's system call events, the predictor should output a prediction of request CPU time.

For each workload, you divide its traced requests into two groups. You should use the first group to train a predictor that predicts request CPU time from its system call events. You are free to use any (simple or complex) learning techniques that you feel appropriate. Then you apply the predictor on the second group of requests to test its accuracy. Please also comment on the prediction results for the four workloads.

Extra credit tasks:
If you are interested and have the time, feel free to do any additional analysis on the provided server request traces. Examples include:

Good analysis results are those that help understand these workloads and their differences from high level. I may assign extra credit for such additional work.

You are asked to turn in a written report. The report should describe the results of your trace analysis (in graphical illustration in some cases). Describe important implications of your results and any further thoughts you developed through this process. Do me a favor not to turn in a hand-written report unless you are sure your handwriting is perfectly recognizable. You do not need to turn in any source code.