lkml.org 
[lkml]   [1999]   [Mar]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: disk head scheduling
    From: Arvind Sankar <arvinds@mit.edu>

> Now everyone knows in advance that an attempt to try and use this
> geometry information would be misguided

> But just for fun: what would be the fastest way of writing a given
> collection of sectors to disk? Hmm. Sounds like the travelling salesman
> problem, which is NP complete in general.

No, because roughly we are on a line.

A 3-dimensional grid is more like it, I suppose.

The most efficient way is to do them in increasing order,

Hmm. Head switch time 1.9 msec. Cylinder switch time 3.4 msec.
Revolution 11.1 msec. This means that it could be profitable
to make a small detour to another head, or a neighbouring cylinder,
to quickly catch a block there before continuing on the same track.

I sure hope its not NP.

I think the general abstract problem may well be NP complete
when formulated appropriately (say, n vertices on an infinite 3-dimensional
grid have to be visited). Of course, any given disk is finite, and there
are only finitely many possibilities, which one can check in constant time.
(Maybe not before the end of the universe, but constant.)

> ... But different disks use different
> orders (as one can most easily demonstrate by making a graph of transfer
> speed versus sector number; if that is roughly monotonically decreasing
> the numbering is canonical and discontinuities in the graph show zone limits;
> but one also sees different graphs, e.g. with a decrease followed by an increase).

Ugh! Why do these sicko's do that? I would have expected that sector 0 was on
the outside and the last sector on the inside.

I don't know why, but can easily invent reasons.
Suppose you buy a 1 GB disk and install SuSE. Greedy as you are,
you want all these nice packages, and you fill 900 MB, leaving
100 MB for yourself. In case you have only one partition this may
well mean that all your daily work is done on the last 10% of the disk.
If that is the inner rim, and your work is disk I/O limited, then things
go at only half of the maximum possible speed.
But if the disk manufacturer had numbered the N cylinders like
0, 2, 4, ..., N-4, N-2, N-1, N-3, ..., 5, 3, 1
then the last 10% of the disk would be just as fast as the first 10%.

> So, maybe we lack information, and cannot really use the spec data to improve
> the disk strategy for this single particular disk, even if we wanted to.

Ok. Is the strat of trying to merge reads that are close together possible?

Everything is possible, but:

(i) This disk does not use interleave. Why not? Perhaps because it is
able to produce the next few blocks immediately after a given one was read,
for example because it anticipates upon the next request.
So, maybe this strategy does not gain you anything at all.

(ii) These days disks are smart.
If the kernel does normal things, the disk firmware will optimize
for that particular disk. If the kernel tries to be smart, the heuristics
in the firmware will fail and everything may become slower.

(iii) It is very difficult to get a correct kernel source.
- Indeed, it is painful to see how many bugs there are in 2.2.* -
Thus, one should aim for a kernel source that is as simple as possible.
No strange dubious tricks.



-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

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