defraggers
Roedy Green
defragger might work in Unix.
I have been interested in defraggers since the DOS days. Unix people
assure me they are not needed on Unix machines. I don't see how this
could be possible.
I can see how Unix might reserve some space at the end of a file for
it to grow into to avoid fragmenting an individual file, but I don't
see how it could ensure frequently used files live close together on
disk. I don't see how it would not have many tiny slices of unused
space. It would eventually have to consolidate them to allocate new
files.
1. Does Unix so any sort of file moving on its own?
2. Do Unix people periodically back up, erase and restore in
last-file-access order to defrag?
3. Is there some clever allocation strategy that keeps things tidy?
I am thinking about a defrag that uses a spare physical drive. It
would copy files to it in last access date order. As files are copied
the system would flip over to using the tidied version, on a
file-by-file basis. When the drive were completely copied, it would
become the empty work drive.
You might copy the files in physical order by the way they are on the
source or the target disk.
The defrag would work in the background whenever the system was
lightly loaded.
You have to figure out what to do with files that are in use. It might
be possible to have them logically span both disks during the copy,
with all writes directed to the new copy.
I thought perhaps you might build such an algorithm into the firmware
of a hard disk controller, so that a pair of disks looked like one. It
would present a high level file system interface to the CPU.
This is similar to my marthaing idea.
See http://mindprod.com/jgloss/martha.html
--
Roedy Green Canadian Mind Products
http://mindprod.com
"Patriotism is fierce as a fever, pitiless as the grave, blind as a stone, and as irrational as a headless hen."
~ Ambrose Bierce (born: 1842-06-24 died: 1914 at age: 71)
Thomas Pornin
> 3. Is there some clever allocation strategy that keeps things tidy?
Yes, almost. Filesystems used in Unix for the last 20 years routinely
include allocation strategies which result in low fragmentation under
typical usage. Those strategies work better when the disk is not almost
full; these days, the time it takes me to fill up my hard disk is quite
bigger than the time it takes for the PC to break up and require a
replacement, which comes with a disk which is at least 5 times larger.
In other words, the last disk I filled up was a 30 GB disk and that was
seven years ago. Nowadays, my disks remain mostly empty, and with very
low fragmentation.
Traditional FAT implementations use a very simple allocation strategy
(use the free sector of lowest address, always) which is almost
guaranteed to result in high fragmentation. Newer filesystems used in
Windows (namely NTFS) fare much better.
Some newer filesystem designs include on-the-fly defragmentation, based
on access pattern. Recent Windows versions do that, especially to speed up
the boot process: they record the read sectors (with ordering) and move
things around so that next boot runs faster. The boot process is "special"
in the following:
-- it is mostly deterministic and reproducible;
-- it begins with a "fresh" system with an empty disk cache;
-- when it occurs, the user is waiting and cannot do anything else.
These characteristics make the defragmentation optimization both
worthwhile and efficient.
> I am thinking about a defrag that uses a spare physical drive. It
> would copy files to it in last access date order. As files are copied
> the system would flip over to using the tidied version, on a
> file-by-file basis. When the drive were completely copied, it would
> become the empty work drive.
Usage of a spare disk may speed up the defragmentation process, but is
not theoretically required, since any defragmentation can be viewed as a
permutation of sectors, and any permutation can be decomposed into a
sequence of transpositions. With good allocation strategies,
fragmentation accumulates slowly enough that defragmentation, if
applied, needs not be fast.
A parallel can be made with memory allocators: a scavenging garbage
collector with semi-spaces is faster than an in-place compactor (using
e.g. Jonkers's algorithm) but it needs a spare semi-space, i.e. twice
as much memory.
--Thomas Pornin