Messages in this thread Patch in this message |  | | From | kumon@flab ... | Date | Tue, 21 Nov 2000 17:38:44 +0900 | Subject | [PATCH] livelock in elevator scheduling |
| |
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).
Problem: 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 reason.
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 @@ break; tmp->elevator_sequence--; } + 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. kumon@flab.fujitsu.co.jp - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org Please read the FAQ at http://www.tux.org/lkml/
|  |