create new tag
view all tags

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.


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.


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


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.

FIFO.png Figure 1: FIFO

Scan.png Figure 2: Scan

Comparison.png Figure 3: Comparison of Scan and FIFO

-- CoryHayes - 19 Dec 2011

Topic attachments
I Attachment History Action Size Date Who Comment
PNGpng Comparison.png r1 manage 59.0 K 2011-12-19 - 18:44 UnknownUser  
Unknown file formatm DiskSimulator.m r1 manage 3.5 K 2011-12-19 - 20:42 UnknownUser  
PNGpng FIFO.png r1 manage 58.0 K 2011-12-19 - 18:44 UnknownUser  
PNGpng Scan.png r1 manage 53.2 K 2011-12-19 - 18:44 UnknownUser  
Texttxt read_sectors1.txt r1 manage 3.7 K 2011-12-19 - 20:42 UnknownUser  
Texttxt write_sectors.txt r1 manage 33.2 K 2011-12-19 - 20:42 UnknownUser  
Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | More topic actions
Topic revision: r2 - 2011-12-19 - NishaSrinivas
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback