[lkml]   [1998]   [Nov]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: elevator algorithm bug in ll_rw_blk.c

On Mon, 9 Nov 1998, Stephen C. Tweedie wrote:

> No. The queue is always kept sorted, yes, but as soon as an IO starts,
> the current request is not removed from the queue until IO is complete
> (except for SCSI, which does its own queue ordering). Once that single
> IO request is complete, the driver then moves on to the *next* request
> in the queue. It doesn't start again at the beginning. So, we do
> correctly service the higher numbered requests before going back to the
> low ones.

as a demonstration of the above mechanizm, here is an IO trace of 60
threads doing random seek&reads on a 1G file on SMP 2.1.127, and what the
IO-scheduler did with this random IO load:

CPU#0 4126.731 ms IRQ: 8/32 B 00237b8c (2) 99.398 ms
CPU#1 4135.309 ms IRQ: 8/32 B 0023aeba (2) 82.948 ms
CPU#0 4143.220 ms IRQ: 8/32 B 0023d06a (2) 79.771 ms
CPU#1 4148.771 ms IRQ: 8/32 B 0023fbd0 (2) 51.181 ms
CPU#0 4155.009 ms IRQ: 8/32 B 0024b30c (2) 68.256 ms
CPU#1 4160.937 ms IRQ: 8/32 B 00253e80 (2) 55.609 ms
CPU#1 4175.446 ms IRQ: 8/32 B 0025702c (2) 12.207 ms
CPU#0 4193.711 ms IRQ: 8/32 B 00008640 (2) 12.757 ms
CPU#1 4200.760 ms IRQ: 8/32 B 000052b6 (2) 65.730 ms
CPU#1 4207.374 ms IRQ: 8/32 B 00000a2e (2) 68.584 ms
CPU#1 4222.454 ms IRQ: 8/32 B 00012b14 (2) 16.988 ms
CPU#0 4227.609 ms IRQ: 8/32 B 0001376e (2) 53.874 ms
CPU#1 4233.397 ms IRQ: 8/32 B 000143bc (2) 52.618 ms
CPU#0 4239.237 ms IRQ: 8/32 B 00025e9c (2) 51.847 ms
CPU#1 4254.037 ms IRQ: 8/32 B 0002b1ca (2) 11.565 ms
CPU#1 4267.383 ms IRQ: 8/32 B 0002cb3c (2) 19.758 ms

The 'elevator' is nicely monotonic. This trace also shows the point where
the elevator goes 'down' to start working up again. (how to read the
trace, columns are: cpu, absolute timestamp, device, sector number in
hexa, size of request, IRQ completion latency) [IRQ completion means:
from the point where the request is queued to the adapter, to the point
where the IRQ is serviced. As the numbers reveal, this disk has tagged
queueing, effective length 4]

As the high queuing->IRQ latencies show, there is a quite big backlog, the
IO-scheduler has lots of time to optimize the request queue. (the disk has
an average seek time of 10-15 msecs, a full 0-to-max seek time of ~20
msecs, a rotational latency of 4-5 msecs. Looking at absolute timestamps
reveals that the scheduler has reduced the latency of random requests to
~5-9 millisecs, compared to the raw disk numbers this is quite good ...)

-- mingo

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:45    [W:0.124 / U:39.888 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site