archive mirror
 help / color / mirror / Atom feed
Cc: Dave Jones <>, Andrea Arcangeli <>
Cc: Jens Axboe <>
Subject: [PATCH] livelock in elevator scheduling
Date: Tue, 21 Nov 2000 17:38:44 +0900	[thread overview]
Message-ID: <> (raw)

The current elevator_linus() doesn't obey the true elevator
scheduling, and causes I/O livelock during frequent random write
traffics. In such environment I/O (read/write) transactions may be
delayed almost infinitely (more than 1 hour).

 Current elevator_linus() traverses the I/O requesting queue from the
tail to top. And when the current request has smaller sector number
than the request on the top of queue, it is always placed just after
the top.
 This means, if requests in some sector range are continuously
generated, a request with larger sector number is always places at the
last and has no chance to go to the front.  e.g. it is not scheduled.

 This is not hypothetical but actually observed.  Running a random
disk write benchmark can completely supress other disk I/O by this

 The following patch fixes this problem. It still doesn't follow a
strict elevator scheduling, but it does much better.  Additionally, it
may be better to add extra priority to reads than writes to obtain
better response, but this patch doesn't.

diff -ru linux-2.4.0-test11-pre2/drivers/block/elevator.c linux-2.4.0-test11-pre2-test5/drivers/block/elevator.c
--- linux-2.4.0-test11-pre2/drivers/block/elevator.c	Wed Aug 23 14:33:46 2000
+++ linux-2.4.0-test11-pre2-test5/drivers/block/elevator.c	Tue Nov 21 15:32:01 2000
@@ -47,6 +47,11 @@
+	if (entry == head) {
+		tmp = blkdev_entry_to_request(entry);
+		if (IN_ORDER(req, tmp))
+			entry = real_head->prev;
+	}
 	list_add(&req->queue, entry);

To implement a complete elevator scheduling, preparing an alternate
waiting queue is better, I think.

Computer Systems Laboratory, Fujitsu Labs.
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

             reply	other threads:[~2000-11-21  9:09 UTC|newest]

Thread overview: 16+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2000-11-21  8:38 kumon [this message]
2000-11-21 10:28 ` Jens Axboe
2000-11-21 11:30 ` kumon
2000-11-21 11:36   ` Jens Axboe
2000-12-02  0:22     ` Russell Cattelan
2000-12-02 15:42       ` Jens Axboe
2000-12-04 23:25         ` Russell Cattelan
2000-12-05  1:38         ` Russell Cattelan
2000-12-05 23:01           ` Jens Axboe
2000-12-06  0:53             ` Russell Cattelan
2000-11-21 12:39   ` kumon
2000-11-21 13:01     ` Jens Axboe
2000-11-22  6:08     ` kumon
2000-11-22 10:59 ` kumon
2000-11-22 15:50   ` davej
     [not found] <>
2000-11-21 15:12 ` Andrea Arcangeli

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \ \ \
    --subject='Re: [PATCH] livelock in elevator scheduling' \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).