scs@hstbme.mit.edu (Steve Summit) (09/07/89)
A while ago, I had an idea on freelist defragmentation which I
wonder if anyone has thought about and/or implemented. Suppose
the free list were first-in, first out; that is, free blocks
return to the opposite end of the list from the allocation end.
(The Unix freelist is, I believe, typically last-in, first-out.)
Then, an additional wrinkle would allow returning them not quite
to the extreme end, but searching the last (say) 100 blocks and
placing the returned block in (relative) order. By the time the
free blocks percolated through to the other, allocation end, they
would have a high probability of being in fairly good order.
And, of course, an unfragmented, ordered free list tends to lead
to unfragmented, ordered files.
A second advantage of this technique is that it would make
recovery of accidentally deleted files (common on MS-DOS,
problematical on secure, timesharing systems) more generally
successful, because deleted (freed) blocks wouldn't be the first
ones to be reallocated.
Steve Summit