k> Those are good reasons for being able to *allocate* contiguous memory
k> when we need it. Unfortunately, Linux's current algorithm is "throw
k> out random stuff until you luck onto a big hunk of contiguous free
k> memory", which sucks even on high-memory machines. I tried to get
k> reverse lookups implemented at one point, but things kept changing
k> under me and I gave up...there's way too many places you have to
k> change, IMHO...
What may be a better solution for linux is not reverse lookups but a
please free me flag, that the usual vmscan, shrink_mmap, & co can use
to do the work. We traverse the page tables fairly it often it feels
like.
>> > And why if that is important why we don't implement a relocating
>> > defragmentation algorithm in the kernel? On the assumption that I
>> > could pause the kernel for a moment, it would be probably faster to do
>> > that on demand, then the current mess!
>> Even better, make sure that fragmentation doesn't occur very
>> often by freeing pages on demand before we use a free page
>> from a big free area.
This is the problem "make sure fragmentation doesn't occur often".
Fragmentation will occur. Fragmentation will get worse with time.
Period.
I think the concept is called entrophy.
There are only two ways to give the strong garantess about
fragmentation, the kernel needs.
a) Find a set of usages of kernel memory that will keep kernel memory
from becoming too fragmented. Document that in the Documentation
subdirectory. This would require restrictions on such things as
kmalloc.
b) Implement a defragmenter in the kernel.
The truth is (a) is probably the choice to lean towards, but I haven't
seen the work done to show it will work.
>> > There is a defragmentation algorithm that runs in O(mem_size) time
>> > with two passes over memory, and needs no extra memory.
>> But it does need huge amounts of CPU time... memcpy() isn't
>> exactly cheap :(
k> I'd much rather memcpy() a page than wait on the disk, even on a slow
k> 386...
Right this isn't the days of the early lisp machines when copying all
active memory to disk, and then back into memory was a good method of
garbage collection. Disks are much slower.
Still a memcpy(all of memory) would probably take to long, for
interrupts and a few other type realtime tasks, so the trivial memory
compactor alogorithm wouldn't work. :( And that is certainly not
something that would be easy to have for 2.2...
Besides the fact it represents a whole different philosophy of memory
use. Well except for the gc for unix domain sockets.
Eric
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu