Re: disk head scheduling

Arvind Sankar (arvinds@mit.edu)
Thu, 18 Mar 1999 13:53:43 -0500

On Wed, Mar 17, 1999 at 11:54:53PM -0800, Yasushi Saito wrote:
> While studying IDE disk performance under high load in 2.2.2, I came
> across a funny-looking line. I guess the below piece of code is
> supposed to implement elevator seeking, but in fact it inserts
> requests in random places when the disk head is moving toward the
> sector 0. Am I missing something?

This patch breaks the code. The current algorithm used is that the elevator
stops at intermediate floors when going up, but not when going down. So it
is ok to add a floor above the top one on the current trip, or below the
lowest on the next.

I have a currently working algo which is greedy instead. i.e. for a new
request, it computes the place where its insertion will produce the least
incremental cost (where cost is the number of additional sectors to seek).
It seems to work for me. No idea how to compare the two algos, though. Can
somebody help me out here...

Another point is that IN_ORDER seems to be called only for two requests
on the same device, so no idea why it compares the device numbers.

-- arvind

Here's the patch (to 2.2.3):

Index: linux/drivers/block/ll_rw_blk.c
diff -u linux/drivers/block/ll_rw_blk.c:1.1.1.3.2.25.2.1 linux/drivers/block/ll_rw_blk.c:1.1.1.3.2.25.2.3
--- linux/drivers/block/ll_rw_blk.c:1.1.1.3.2.25.2.1 Sat Feb 13 12:43:14 1999
+++ linux/drivers/block/ll_rw_blk.c Thu Mar 18 13:38:04 1999
@@ -292,6 +292,9 @@
void add_request(struct blk_dev_struct * dev, struct request * req)
{
struct request * tmp, **current_request;
+ struct request * best;
+ unsigned long mincost = (unsigned long) -1;
+ long cost;
short disk_index;
unsigned long flags;
int queue_new_request = 0;
@@ -330,20 +333,25 @@
queue_new_request = 1;
goto out;
}
- for ( ; tmp->next ; tmp = tmp->next) {
- const int after_current = IN_ORDER(tmp,req);
- const int before_next = IN_ORDER(req,tmp->next);
-
- if (!IN_ORDER(tmp,tmp->next)) {
- if (after_current || before_next)
- break;
- } else {
- if (after_current && before_next)
- break;
+ for (best = tmp; tmp->next ; tmp = tmp->next) {
+ cost = tmp->sector < req->sector
+ ? req->sector - tmp->sector
+ : tmp->sector - req->sector;
+ cost += tmp->next->sector < req->sector
+ ? req->sector - tmp->next->sector
+ : tmp->next->sector - req->sector;
+ if (cost >= 0 && cost < mincost) {
+ best = tmp;
+ mincost = cost;
}
}
- req->next = tmp->next;
- tmp->next = req;
+ cost = tmp->sector < req->sector
+ ? req->sector - tmp->sector
+ : tmp->sector - req->sector;
+ if (cost < mincost)
+ best = tmp;
+ req->next = best->next;
+ best->next = req;

/* for SCSI devices, call request_fn unconditionally */
if (scsi_blk_major(MAJOR(req->rq_dev)))
Index: linux/include/linux/blk.h
diff -u linux/include/linux/blk.h:1.1.1.2.2.16 linux/include/linux/blk.h:1.1.1.2.2.16.2.1
--- linux/include/linux/blk.h:1.1.1.2.2.16 Sat Feb 13 05:30:59 1999
+++ linux/include/linux/blk.h Thu Mar 18 13:38:05 1999
@@ -22,16 +22,6 @@
#define NR_REQUEST 64

/*
- * This is used in the elevator algorithm. We don't prioritise reads
- * over writes any more --- although reads are more time-critical than
- * writes, by treating them equally we increase filesystem throughput.
- * This turns out to give better overall performance. -- sct
- */
-#define IN_ORDER(s1,s2) \
-((s1)->rq_dev < (s2)->rq_dev || (((s1)->rq_dev == (s2)->rq_dev && \
-(s1)->sector < (s2)->sector)))
-
-/*
* Initialization functions.
*/
extern int isp16_init(void);

-
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/