Problem Statement

We have designed a discrete event simulator that observes the behavior of a magnetic disk drive. We analyze the seek time for two different disk scheduling algorithms.

Disk Activity Tracer

Blktrace is a block layer I/O tracing utility developed by Jens Axboe, Alan Brunelle, and Nathan Scott. Blktrace records information from a specific block device and consists of three major components. The first component is a low-overhead one that resides in the kernel and is triggered by specific events. The second component records I/O trace information stemming from specific operations from the kernel to the user space. The final component, blkparse, analyzes the output and converts it to a readable user-friendly format that can be used for further analysis. Blktrace can run indefinitely or for a certain length of time as specified (in seconds) using the –w flag.

Environment

This mini-project was carried out on an Ubuntu 11.04 virtual machine with 512 MB of base memory within Oracle VM VirtualBox. The host machine was a Mac running MacOSX 10.6.4 with 4GB of memory.

Collecting Data

The data gathered for our discrete event simulator of a hard disk was generated using blktrace and Mozilla Firefox. First, we started up blktrace using the following command:

sudo ./bktrace –d /dev/sda –o output.dat

where /dev/sda is the device from which events are recorded as specified by the -d flag, with sda representing the first scsi device. The –o flag allows the user to name the filename where the output is dumped. sudo is included since blktrace requires root-level privileges. Once blktrace was up and running, the Mozilla Firefox web browser was started up. In an attempt to generate some level of disk activity, we navigated to Youtube and watched a high-quality video for approximately five to six minutes. Once this time period ended, we manually terminated blktrace using CTRL+C.

Blktrace automatically appends “blktrace” and the device number to the output file name, so our output filename was “output.dat.blktrace.0”. Blktrace captured all recorded activity, but since we were only interested in the read and write activity, we filtered this information out using the following commands.

./blkparse –a read –f “%S\n” –i output.dat.blktrace.0 > read_sectors.txt

./blkparse –a write –f “%S\n” –i output.dat.blktrace.0 > write_sectors.txt

Each of these files is a list containing the affected sectors for the associated activity.

Disk Design

We consider the disk to be in the form of an multidimensional array. The row represent the tracks and the columns represent the number of sectors per track. We assume 1KB blocks. Hence there are 2*1KB sectors. It the number of blocks is N then the number of sectors is 2*N. Then we keep the Number of sectors per track a constant (X), hence the number of tracks =(2*N)/X;

Then we compute the seek time for two different algorithm namely, FIFO and SCAN.

FIFO

Fair but near random scheduling. There is no cache. The disk head moves randomly depending on the address.

SCAN

Favor requests for tracks near the ends. Has a cache of size S. And you can access S addresses at a time and find the closest move based on sorting.

Analyzing Blktrace Output

We measure the seek time for the two different algorithms. Figure 1 and Figure 2 presents the time take to access each read address on the disk for FIFO and SCAN. From Figure 3 we observe that the random scheduling performed better than SCAN. Theoretically SCAN should outperform FIFO but that is not the case here. This is mainly due to the implementation of the SCAN algorithm. We did not assume signed distance between address before sorting. If we had assumed signed distance it would have been better.

Figure 1: FIFO

Figure 2: Scan

Figure 3: Comparison of Scan and FIFO

-- CoryHayes - 19 Dec 2011