|| ||Andrew Morton <email@example.com>|
|| ||firstname.lastname@example.org, email@example.com|
|| ||Thu, 23 Jan 2003 19:50:44 -0800|
. -mm3 and -mm4 were not announced - they were sync-up patches as we
worked on the I/O scheduler.
. -mm5 has the first cut of Nick Piggin's anticipatory I/O scheduler.
Here's the scoop:
The problem being addressed here is (mainly) kernel behaviour when there
is a stream of writeout happening, and someone submits a read.
In 2.4.x, the disk queues contain up to 30 megabytes of writes (say, one
seconds's worth). When a read is submitted the 2.4 I/O scheduler will try
to insert that at the right place between the writes. Usually, there is no
right place and the read is appended to the queue. That is: it will be
serviced in one second.
But the problem with reads is that they are dependent - neither the
application nor the kernel can submit read #N until read #N-1 has
completed. So something as simple as
cat /usr/src/linux/kernel/*.c > /dev/null
requires several hundred dependent reads. And in the presence of a
streaming write, each and every one of those reads gets stuck at the end of
the queue, and takes a second to propagate to the head. The `cat' takes
hundreds of seconds.
The celebrated read-latency2 patch recognises the fact that appending a
read to a tail of writes is dumb, and puts the read near the head of the
queue of writes. It provides an improvement of up to 30x. The deadline
I/O scheduler in 2.5 does the same thing: if reads are queued up, promote
them past writes, even if those writes have been waiting longer.
So far so good, but these fixes are still dumb. Because we're solving
the dependent read problem by creating a seek storm. Every time someone
submits a read, we stop writing, seek over and service the read, and then
*immediately* seek back and start servicing writes again.
But in the common case, the application which submitted a read is about
to go and submit another one, closeby on-disk to the first. So whoops, we
have to seek back to service that one as well.
So what anticipatory scheduling does is very simple: if an application
has performed a read, do *nothing at all* for a few milliseconds. Just
return to userspace (or to the filesystem) in the expectation that the
application or filesystem will quickly submit another read which is
If the application _does_ submit the read then fine - we service that
quickly. If it does not submit a read then we lose. Time out and go back
to doing writes.
The end result is a large reduction in seeking - decreased read latency,
increased read bandwidth and increased write bandwidth.
The code as-is has rough spots and still needs quite some work. But it
appears to be stable. The test which I have concentrated on is "how long
does my laptop take to compile util-linux when there is a continuous write
happening". On ext2, mounted noatime:
2.4.20: 538 seconds
2.5.59: 400 seconds
2.5.59-mm5: 70 seconds
No streaming write: 48 seconds
A couple of VFS changes were needed as well.
More details on anticipatory scheduling may be found at
Changes since 2.5.59-mm2:
Speed up the smp preempt locking.
ext2 ENOSPC crash fix
A form of software watchdog
Fix a BUG() in slab when memory exhaustion happens at a bad time.
Reinstate lost security hooks around sendfile()
Fix IO-wait acounting
aic7xxx driver update
file locking fix
reworked reiserfs write code.
Fix MAP_PRIVATE mmaps for filesystems which don't support ->writepage()
Fix the exit_mmap() problem in arch code.
Fix oops in show_task()
software suspend fix
remove some junk from fs-writeback.c
Fix large delays in the writeback path
Fix large delays in unlink()
Anticipatory scheduling implementation
All 65 patches:
remove lock_kernel() from exec of setuid apps
reiserfs v3 readpages support
ext3: fix scheduling storm and lockups
self-unplugging request queues
Remove most of the blk_run_queues() calls
hugetlb: fix MAP_FIXED handling
Subject: Re: 2.5.59-mm1
ext3: explicitly free truncated pages
add stats for page reclaim via inode freeing
cleanup in read_cache_pages()
quota locking fix
quota semaphore fix
Subject: spinlock efficiency problem [was 2.5.57 IO slowdown with CONFIG_PREEMPT enabled)
stack overflow checking fix
Subject: [PATCH] ext2 allocation failures
ext2_new_block cleanups and fixes
slab IRQ fix
Subject: [PATCH] Richard Henderson for President!
Subject: i386 pgd_index() doesn't parenthesize its arg
Subject: [RFC][PATCH] Restore LSM hook calls to sendfile
Subject: Re: i386 pgd_index() doesn't parenthesize its arg
asm-i386/mmzone.h macro paren/eval fixes
correct wait accounting in wait_on_buffer()
MAX_IO_APICS #ifdef'd wrongly
Subject: [PATCH] linux2.5.56 patch to DAC960 driver for error retry
Remove __ from topology macros
ftruncate/truncate oopses with mandatory locking
Subject: Re: Linux 2.5.59
Subject: reiserfs file_write patch
soundcore.c referenced non-existent errno variable
Include <asm/page.h> in fs/seq_file.c, as it uses PAGE_SIZE
Fix ia64's 64bit->32bit app switching
Subject: [PATCH] 2.5.59: show_task() oops
scsi_eh_* needs to run even during suspend
NUMAQ io_apic programming fix
Subject: [PATCH] 2.5.59-mm3 antic io sched
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to firstname.lastname@example.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/