" Is there a Linux utility available which defragments hard disks to optimize the disk storage, like the MS-DOS defragmentation utilities? "
The straight answer -Yes.
There is a program called defrag that defragments ext2 filesystems. It is available at better sunsite mirrors, and notably at Sunsite - /pub/linux/system/Filesystems/
According to the documentation for defrag, random access is only likely to be assisted by a few percent; possibly up to 25 for sequential access if files are highly fragmented. This isn't the "black mark" one might expect: it merely indicates that ext2 is not affected very adversely by fragmentation.
ext2fs (the most commonly used file system under Linux) is somewhat resilient against fragmentation, and more importantly is not severely affected by it when it does happen.
This is quite different from the "MS-DOS experience," where fragmentation has significant deleterious effects on system performance.
If you've religiously defragmented your MS-DOS disks, then you'll find that you have minimal need to do so under Linux.
I've never defragged in the 10 years I've been using Linux,and have not noticed any injury to filesystem access speeds. Whereas I have noticed slowdowns on fragmented MS-DOS partitions...
All of this being said, the sorts of situations in which fragmentation are most likely to also be situations where the benefits of defragmentation are liable to be minimal. A typical cause of heavy fragmentation is when there are many processes simultaneously modifying data all over a file system.
The benefits of defragmentation are limited in this situation because the primary cause of "slowness" is that the disk heads will be seeking all over the disk in order to access and write data. Even without any fragmentation, with files strewn around, similar amounts of seeking around will be needed.
... since Linux is a multi-user operating system, head position after a read is mostly irrelevant as other tasks and users will also be reading and writing that drive and the buffer cache will be flushing older data out also moving the drives' heads. This is why one does not notice as quickly any performance impact from 'fragmented' files. The normal head movement that is part of a multi-tasking multi-user system masks most performance impact and the intelligent cacheing and inode design improve performance by normally fetching the next block from disk to the cache before it is called for so that applications do not notice any slowdown.
There is a
There is one situation where many filesystems are likely to start to behave badly, and that is where the filesystem is almost totally full. Every new block written to will require a search through the remaining space; every block freed up requires work done to make sure it can be found. If you consistently run into problems when you attempt to completely fill a filesystem, your problem isn't bad performance; it is that you're an idiot that aren't planning disk availability properly...
Can anyone explain EXT2's file allocation algorithm? "Why doesn't Linux have a defragmentor" is a frequently asked question which always gets the same answer "because EXT2 doesn't need one." I'd like to know just what it is that EXT2 does to prevent fragmentation that other file systems don't do. Does EXT2 segregate large files from small files so that there is a better chance that it can find an appropriate sized hole for each file?
You have it the wrong way round! Filesystems never need "defragmentation". It's only msdos's botches that did need it, instead of organizing things correctly as they went. Besides that, fragmentation is (obviously!) good for a FS.
It keeps files fairly well separated yes, but so does any decent file system. It also leaves space for them to grow. It also uses clustering algorithms. The principal fault of msdos is choosing the first hole that will accept a file as the receptacle for it. This leads to maximum fragmentation in minimum time. In fact the "worst fit" algorithm is generally know to be best .. i.e. you put the file in the hole that it fits in worst, not first, or best. This has been the case for twenty years. Why msdos still insists on doing it wrong is beyond everyone.
Not really. FAT is an "optimal" way of doing things, if all you have is a 5mhz 8088, less than 512k of RAM, and a 360K floppy and are only writing not more than 10-20 files, each over 18kbytes in size and will probably not delete them, ever, since when the disk becomes full, you'll pop in a fresh disk. Where you are more likely to FORMAT A: than DEL A:FOO.BAR. It is indeed silly to do this with a 500mhz PIII, 128meg of RAM and a 30gig hard drive. Hell, it is silly with a 66mhz '486, with 16meg of RAM and a 500meg hard drive!